ITK  4.6.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  typedef TTreeType TreeType;
34  typedef typename TTreeType::ValueType ValueType;
36  typedef typename Superclass::NodeType NodeType;
37 
40 
42  NodeType GetType() const;
43 
46 
47 protected:
49  const ValueType & Next();
50 
52  bool HasNext() const;
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, ITK_NULLPTR)
67 {
68  if ( tree->GetRoot() == ITK_NULLPTR )
69  {
70  this->m_Begin = ITK_NULLPTR;
71  }
72  else
73  {
74  const TreeNodeType *root = dynamic_cast<const TreeNodeType *>(tree->GetRoot());
75  if(root == ITK_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() ) != ITK_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 == ITK_NULLPTR || this->m_Position == this->m_Root )
123  {
124  return ITK_NULLPTR;
125  }
126  TreeNodeType *sister = const_cast< TreeNodeType * >( FindSister(this->m_Position) );
128 
129  if ( sister != ITK_NULLPTR )
130  {
131  return FindMostRightLeaf(sister);
132  }
133  if(this->m_Position->GetParent() == ITK_NULLPTR)
134  {
135  return ITK_NULLPTR;
136  }
137  TreeNodeType *rval = dynamic_cast<TreeNodeType *>(this->m_Position->GetParent());
138  if(rval == ITK_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 ITK_NULLPTR;
153  }
154 
155  TreeNodeType *parent = dynamic_cast<TreeNodeType *>(node->GetParent());
156  if(parent == ITK_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) == ITK_NULLPTR)
167  {
168  childPosition++;
169  }
170  else
171  {
172  TreeNodeType *sister = dynamic_cast<TreeNodeType *>(parent->GetChild(childPosition + 1));
173  if ( sister == ITK_NULLPTR)
174  {
175  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
176  }
177  return sister;
178  }
179  }
180  return ITK_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) == ITK_NULLPTR)
198  {
199  helpNode = ITK_NULLPTR;
200  }
201  else
202  {
203  helpNode = dynamic_cast<TreeNodeType *>(node->GetChild(i));
204  if(helpNode == ITK_NULLPTR)
205  {
206  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
207  }
208  }
209  i++;
210  }
211  while ( helpNode == ITK_NULLPTR && i < childCount );
212 
213  if ( helpNode == ITK_NULLPTR )
214  {
215  return node;
216  }
217  node = helpNode;
218  }
219  return node;
220 }
221 
223 template< typename TTreeType >
225 {
227  new PostOrderTreeIterator< TTreeType >( const_cast< TTreeType * >( this->m_Tree ) );
228  *clone = *this;
229  return clone;
230 }
231 } // end namespace itk
233 
234 #endif
TTreeType::TreeNodeType TreeNodeType
const TreeNodeType * FindSister(TreeNodeType *node) const
TreeIteratorBase< TTreeType > * Clone()
const TreeNodeType * FindMostRightLeaf(TreeNodeType *node) const
const TreeNodeType * FindNextNode() const
TreeIteratorBase< TTreeType > Superclass
This class provides the base implementation for tree iterators.
Superclass::TreeNodeType TreeNodeType