ITK  5.0.0
Insight Segmentation and Registration Toolkit
itkPostOrderTreeIterator.h
Go to the documentation of this file.
1 /*=========================================================================
2  *
3  * Copyright Insight Software Consortium
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0.txt
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17  *=========================================================================*/
18 #ifndef itkPostOrderTreeIterator_h
19 #define itkPostOrderTreeIterator_h
20 
21 #include "itkTreeIteratorBase.h"
22 
23 namespace itk
24 {
25 template< typename TTreeType >
26 class PostOrderTreeIterator:public TreeIteratorBase< TTreeType >
27 {
28 public:
29 
33  using TreeType = TTreeType;
34  using ValueType = typename TTreeType::ValueType;
36  using NodeType = typename Superclass::NodeType;
37 
40 
42  NodeType GetType() const override;
43 
46 
47 protected:
49  const ValueType & Next() override;
50 
52  bool HasNext() const override;
53 
54 protected:
55 
56  const TreeNodeType * FindNextNode() const;
57 
58  const TreeNodeType * FindMostRightLeaf(TreeNodeType *node) const;
59 
60  const TreeNodeType * FindSister(TreeNodeType *node) const;
61 };
62 
64 template< typename TTreeType >
66  TreeIteratorBase< TTreeType >(tree, nullptr)
67 {
68  if ( tree->GetRoot() == nullptr )
69  {
70  this->m_Begin = nullptr;
71  }
72  else
73  {
74  const auto * root = dynamic_cast<const TreeNodeType *>(tree->GetRoot());
75  if(root == nullptr)
76  {
77  itkGenericExceptionMacro(<< "Can't downcast root node to TreeNodeType *");
78  }
79  this->m_Position = const_cast<TreeNodeType *>(root);
80  this->m_Position = const_cast< TreeNodeType * >( FindMostRightLeaf(this->m_Position) );
81  this->m_Begin = this->m_Position;
82  }
83 }
85 
87 template< typename TTreeType >
90 {
92 }
93 
95 template< typename TTreeType >
96 bool
98 {
99  if ( const_cast< TreeNodeType * >( FindNextNode() ) != nullptr )
100  {
101  return true;
102  }
103  return false;
104 }
106 
108 template< typename TTreeType >
111 {
112  this->m_Position = const_cast< TreeNodeType * >( FindNextNode() );
113  return this->m_Position->Get();
114 }
116 
118 template< typename TTreeType >
121 {
122  if ( this->m_Position == nullptr || this->m_Position == this->m_Root )
123  {
124  return nullptr;
125  }
126  auto * sister = const_cast< TreeNodeType * >( FindSister(this->m_Position) );
128 
129  if ( sister != nullptr )
130  {
131  return FindMostRightLeaf(sister);
132  }
133  if(this->m_Position->GetParent() == nullptr)
134  {
135  return nullptr;
136  }
137  auto * rval = dynamic_cast<TreeNodeType *>(this->m_Position->GetParent());
138  if(rval == nullptr)
139  {
140  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
141  }
142  return rval;
143 }
144 
146 template< typename TTreeType >
149 {
150  if ( !node->HasParent() )
151  {
152  return nullptr;
153  }
154 
155  auto * parent = dynamic_cast<TreeNodeType *>(node->GetParent());
156  if(parent == nullptr)
157  {
158  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
159  }
160 
161  int childPosition = parent->ChildPosition(node);
162  int lastChildPosition = parent->CountChildren() - 1;
163 
164  while ( childPosition < lastChildPosition )
165  {
166  if(parent->GetChild(childPosition + 1) == nullptr)
167  {
168  childPosition++;
169  }
170  else
171  {
172  auto * sister = dynamic_cast<TreeNodeType *>(parent->GetChild(childPosition + 1));
173  if ( sister == nullptr)
174  {
175  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
176  }
177  return sister;
178  }
179  }
180  return nullptr;
181 }
182 
184 template< typename TTreeType >
187 {
188  while ( node->HasChildren() )
189  {
190  TreeNodeType *helpNode;
191  int childCount = node->CountChildren();
192  int i = 0;
194 
195  do
196  {
197  if(node->GetChild(i) == nullptr)
198  {
199  helpNode = nullptr;
200  }
201  else
202  {
203  helpNode = dynamic_cast<TreeNodeType *>(node->GetChild(i));
204  if(helpNode == nullptr)
205  {
206  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
207  }
208  }
209  i++;
210  }
211  while ( helpNode == nullptr && i < childCount );
212 
213  if ( helpNode == nullptr )
214  {
215  return node;
216  }
217  node = helpNode;
218  }
219  return node;
220 }
221 
223 template< typename TTreeType >
225 {
226  auto * clone = new PostOrderTreeIterator< TTreeType >( const_cast< TTreeType * >( this->m_Tree ) );
227  *clone = *this;
228  return clone;
229 }
230 } // end namespace itk
232 
233 #endif
const TreeNodeType * FindSister(TreeNodeType *node) const
typename TTreeType::ValueType ValueType
const TreeNodeType * FindMostRightLeaf(TreeNodeType *node) const
const TreeNodeType * FindNextNode() const
typename Superclass::NodeType NodeType
NodeType GetType() const override
This class provides the base implementation for tree iterators.
typename Superclass::TreeNodeType TreeNodeType
const ValueType & Next() override
TreeIteratorBase< TTreeType > * Clone() override
typename TTreeType::TreeNodeType TreeNodeType