ITK  4.8.0
Insight Segmentation and Registration Toolkit
itkPreOrderTreeIterator.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 itkPreOrderTreeIterator_h
19 #define itkPreOrderTreeIterator_h
20 
21 #include "itkTreeIteratorBase.h"
22 
23 namespace itk
24 {
25 
26 template< typename TTreeType >
27 class LeafTreeIterator;
28 
29 template< typename TTreeType >
30 class PreOrderTreeIterator:public TreeIteratorBase< TTreeType >
31 {
32 public:
33 
35  typedef typename TTreeType::ValueType ValueType;
38  typedef typename Superclass::NodeType NodeType;
39 
41  PreOrderTreeIterator(const TTreeType *tree, const TreeNodeType *start = ITK_NULLPTR);
42 
44  NodeType GetType() const;
45 
48 
49 protected:
51  const ValueType & Next();
52 
54  bool HasNext() const;
55 
56 private:
57 
59  const TreeNodeType * FindNextNode() const;
60 
64  friend class LeafTreeIterator< TTreeType >;
65 };
66 
68 template< typename TTreeType >
70  TreeIteratorBase< TTreeType >(tree, start)
71 {}
72 
74 template< typename TTreeType >
77 {
79 }
80 
82 template< typename TTreeType >
83 bool
85 {
86  if ( const_cast< TreeNodeType * >( FindNextNode() ) != ITK_NULLPTR )
87  {
88  return true;
89  }
90  return false;
91 }
93 
95 template< typename TTreeType >
98 {
99  this->m_Position = const_cast< TreeNodeType * >( FindNextNode() );
100  return this->m_Position->Get();
101 }
103 
105 template< typename TTreeType >
108 {
109  if ( this->m_Position == ITK_NULLPTR )
110  {
111  return ITK_NULLPTR;
112  }
113  if ( this->m_Position->HasChildren() )
114  {
115  return dynamic_cast< const TreeNodeType * >( this->m_Position->GetChild(0) );
116  }
118 
119  if ( !this->m_Position->HasParent() )
120  {
121  return ITK_NULLPTR;
122  }
123 
124  TreeNodeType *child = this->m_Position;
125  TreeNodeType *parent = dynamic_cast< TreeNodeType * >( this->m_Position->GetParent() );
126 
127  // Are we a subtree? Then we are done.
128  if ( parent && parent->ChildPosition(this->m_Root) >= 0 )
129  {
130  return ITK_NULLPTR;
131  }
132 
133  int childPosition = parent->ChildPosition(child);
134  int lastChildPosition = parent->CountChildren() - 1;
135 
136  while ( childPosition < lastChildPosition )
137  {
138  TreeNodeType *help = dynamic_cast< TreeNodeType * >( parent->GetChild(childPosition + 1) );
139 
140  if ( help != ITK_NULLPTR )
141  {
142  return help;
143  }
144  childPosition++;
145  }
146 
147  while ( parent->HasParent() )
148  {
149  child = parent;
150  parent = dynamic_cast< TreeNodeType * >( parent->GetParent() );
151 
152  // Subtree
153  if ( parent->ChildPosition(this->m_Root) >= 0 )
154  {
155  return ITK_NULLPTR;
156  }
157 
158  childPosition = parent->ChildPosition(child);
159  lastChildPosition = parent->CountChildren() - 1;
160 
161  while ( childPosition < lastChildPosition )
162  {
163  TreeNodeType *help = dynamic_cast< TreeNodeType * >( parent->GetChild(childPosition + 1) );
164 
165  if ( help != ITK_NULLPTR )
166  {
167  return help;
168  }
169  }
170  }
171  return ITK_NULLPTR;
172 }
173 
175 template< typename TTreeType >
177 {
178  PreOrderTreeIterator< TTreeType > *clone = new PreOrderTreeIterator< TTreeType >(this->m_Tree, this->m_Position);
179  *clone = *this;
180  return clone;
181 }
182 } // end namespace itk
184 
185 #endif
TTreeType::TreeNodeType TreeNodeType
TreeIteratorBase< TTreeType > * Clone()
Superclass::TreeNodeType TreeNodeType
PreOrderTreeIterator(const TTreeType *tree, const TreeNodeType *start=nullptr)
const TreeNodeType * FindNextNode() const
TreeIteratorBase< TTreeType > Superclass
This class provides the base implementation for tree iterators.