ITK  5.0.0
Insight Segmentation and Registration Toolkit
itkInOrderTreeIterator.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 itkInOrderTreeIterator_h
19 #define itkInOrderTreeIterator_h
20 
21 #include "itkTreeIteratorBase.h"
22 
23 namespace itk
24 {
25 template< typename TTreeType >
26 class InOrderTreeIterator: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  InOrderTreeIterator(TreeType *tree, TreeNodeType *start = nullptr);
42 
44  NodeType GetType() const override;
45 
48 
49 protected:
50 
52  const ValueType & Next() override;
53 
55  bool HasNext() const override;
56 
57 private:
58 
60  const TreeNodeType * FindNextNode() const;
61 };
62 
64 template< typename TTreeType >
66  TreeIteratorBase< TTreeType >(start)
67 {}
68 
70 template< typename TTreeType >
72  TreeIteratorBase< TTreeType >(tree, start)
73 {}
74 
76 template< typename TTreeType >
79 {
81 }
82 
84 template< typename TTreeType >
86 {
87  if ( const_cast< TreeNodeType * >( FindNextNode() ) != nullptr )
88  {
89  return true;
90  }
91  return false;
92 }
94 
96 template< typename TTreeType >
99 {
100  this->m_Position = const_cast< TreeNodeType * >( FindNextNode() );
101  return this->m_Position->Get();
102 }
104 
106 template< typename TTreeType >
109 {
110  if ( this->m_Position == nullptr )
111  {
112  return nullptr;
113  }
114 
115  if ( this->m_Position->HasChildren() )
116  {
117  return this->m_Position->GetChild(0);
118  }
119 
120  if ( !this->m_Position->HasParent() )
121  {
122  return nullptr;
123  }
124 
125  TreeNodeType *child = this->m_Position;
126  TreeNodeType *parent = this->m_Position->GetParent();
127 
128  int childPosition = parent->ChildPosition(child);
129  int lastChildPosition = parent->CountChildren() - 1;
130 
131  while ( childPosition < lastChildPosition )
132  {
133  TreeNodeType *help = parent->GetChild(childPosition + 1);
134  if ( help != nullptr )
135  {
136  return help;
137  }
138  childPosition++;
139  }
140 
141  while ( parent->HasParent() )
142  {
143  child = parent;
144  parent = parent->GetParent();
145 
146  // Subtree
147  if ( parent->ChildPosition(this->m_Root) >= 0 )
148  {
149  return nullptr;
150  }
151  childPosition = parent->ChildPosition(child);
152  lastChildPosition = parent->CountChildren() - 1;
153 
154  while ( childPosition < lastChildPosition )
155  {
156  TreeNodeType *help = parent->GetChild(childPosition + 1);
157  if ( help != nullptr )
158  {
159  return help;
160  }
161  }
162  }
163  return nullptr;
164 }
165 
167 template< typename TTreeType >
169 {
170  auto * clone = new InOrderTreeIterator( const_cast< TTreeType * >( this->m_Tree ) );
171 
172  *clone = *this;
173  return clone;
174 }
175 } // end namespace itk
176 
177 #endif
typename Superclass::TreeNodeType TreeNodeType
typename TTreeType::ValueType ValueType
NodeType GetType() const override
const TreeNodeType * FindNextNode() const
InOrderTreeIterator(TreeType &start)
TreeIteratorBase< TTreeType > * Clone() override
This class provides the base implementation for tree iterators.
const ValueType & Next() override
typename TTreeType::TreeNodeType TreeNodeType
typename Superclass::NodeType NodeType
bool HasNext() const override