Orfeo Toolbox  4.0
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, NULL)
67 {
68  if ( tree->GetRoot() == 0 )
69  {
70  this->m_Begin = 0;
71  }
72  else
73  {
74  const TreeNodeType *root = dynamic_cast<const TreeNodeType *>(tree->GetRoot());
75  if(root == 0)
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 }
84 
86 template< typename TTreeType >
89 {
91 }
92 
94 template< typename TTreeType >
95 bool
97 {
98  if ( const_cast< TreeNodeType * >( FindNextNode() ) != NULL )
99  {
100  return true;
101  }
102  return false;
103 }
104 
106 template< typename TTreeType >
109 {
110  this->m_Position = const_cast< TreeNodeType * >( FindNextNode() );
111  return this->m_Position->Get();
112 }
113 
115 template< typename TTreeType >
118 {
119  if ( this->m_Position == NULL || this->m_Position == this->m_Root )
120  {
121  return NULL;
122  }
123  TreeNodeType *sister = const_cast< TreeNodeType * >( FindSister(this->m_Position) );
124 
125  if ( sister != NULL )
126  {
127  return FindMostRightLeaf(sister);
128  }
129  if(this->m_Position->GetParent() == 0)
130  {
131  return 0;
132  }
133  TreeNodeType *rval = dynamic_cast<TreeNodeType *>(this->m_Position->GetParent());
134  if(rval == 0)
135  {
136  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
137  }
138  return rval;
139 }
140 
142 template< typename TTreeType >
145 {
146  if ( !node->HasParent() )
147  {
148  return NULL;
149  }
150 
151  TreeNodeType *parent = dynamic_cast<TreeNodeType *>(node->GetParent());
152  if(parent == 0)
153  {
154  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
155  }
156 
157  int childPosition = parent->ChildPosition(node);
158  int lastChildPosition = parent->CountChildren() - 1;
159 
160  while ( childPosition < lastChildPosition )
161  {
162  if(parent->GetChild(childPosition + 1) == 0)
163  {
164  childPosition++;
165  }
166  else
167  {
168  TreeNodeType *sister = dynamic_cast<TreeNodeType *>(parent->GetChild(childPosition + 1));
169  if ( sister == 0)
170  {
171  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
172  }
173  return sister;
174  }
175  }
176  return NULL;
177 }
178 
180 template< typename TTreeType >
183 {
184  while ( node->HasChildren() )
185  {
186  TreeNodeType *helpNode;
187  int childCount = node->CountChildren();
188  int i = 0;
189 
190  do
191  {
192  if(node->GetChild(i) == 0)
193  {
194  helpNode = 0;
195  }
196  else
197  {
198  helpNode = dynamic_cast<TreeNodeType *>(node->GetChild(i));
199  if(helpNode == 0)
200  {
201  itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
202  }
203  }
204  i++;
205  }
206  while ( helpNode == NULL && i < childCount );
207 
208  if ( helpNode == NULL )
209  {
210  return node;
211  }
212  node = helpNode;
213  }
214  return node;
215 }
216 
218 template< typename TTreeType >
220 {
222  new PostOrderTreeIterator< TTreeType >( const_cast< TTreeType * >( this->m_Tree ) );
223  *clone = *this;
224  return clone;
225 }
226 } // end namespace itk
227 
228 #endif

Generated at Sat Mar 8 2014 15:23:51 for Orfeo Toolbox with doxygen 1.8.3.1