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 itkLevelOrderTreeIterator_hxx
19 #define itkLevelOrderTreeIterator_hxx
20
21 #include "itkLevelOrderTreeIterator.h"
22
23 namespace itk
24 {
25 /** Constructor with end level specification */
26 template< typename TTreeType >
27 LevelOrderTreeIterator< TTreeType >
LevelOrderTreeIterator(TTreeType * tree,int endLevel,const TreeNodeType * start)28 ::LevelOrderTreeIterator(TTreeType *tree, int endLevel, const TreeNodeType *start):
29 TreeIteratorBase< TTreeType >(tree, start)
30 {
31 m_StartLevel = -1;
32 m_EndLevel = endLevel;
33 if ( start != nullptr )
34 {
35 m_Queue.push(start);
36 this->m_Position = const_cast< TreeNodeType * >( start );
37 }
38 else
39 {
40 if ( tree->GetRoot() )
41 {
42 m_Queue.push( dynamic_cast< const TreeNodeType * >( tree->GetRoot() ) );
43 this->m_Position = const_cast< TreeNodeType * >( dynamic_cast< const TreeNodeType * >( tree->GetRoot() ) );
44 }
45 }
46 this->m_Begin = this->m_Position;
47 }
48
49 /** Constructor with end level specification */
50 template< typename TTreeType >
51 LevelOrderTreeIterator< TTreeType >
LevelOrderTreeIterator(TTreeType * tree,int startLevel,int endLevel,const TreeNodeType * start)52 ::LevelOrderTreeIterator(TTreeType *tree, int startLevel, int endLevel, const TreeNodeType *start):
53 TreeIteratorBase< TTreeType >(tree, start)
54 {
55 m_StartLevel = startLevel;
56 m_EndLevel = endLevel;
57 if ( start != nullptr )
58 {
59 m_Queue.push(start);
60 this->m_Position = const_cast< TreeNodeType * >( start );
61 }
62 else
63 {
64 if ( tree->GetRoot() )
65 {
66 m_Queue.push( dynamic_cast< const TreeNodeType * >( tree->GetRoot() ) );
67 this->m_Position = const_cast< TreeNodeType * >( dynamic_cast< const TreeNodeType * >( tree->GetRoot() ) );
68 }
69 }
70 this->m_Begin = this->m_Position;
71 }
72
73 /** Return the type of iterator */
74 template< typename TTreeType >
75 typename LevelOrderTreeIterator< TTreeType >::NodeType
GetType() const76 LevelOrderTreeIterator< TTreeType >::GetType() const
77 {
78 return TreeIteratorBase< TTreeType >::LEVELORDER;
79 }
80
81 /** Return true if the next value exists */
82 template< typename TTreeType >
83 bool
HasNext() const84 LevelOrderTreeIterator< TTreeType >::HasNext() const
85 {
86 if ( const_cast< TreeNodeType * >( FindNextNode() ) )
87 {
88 return true;
89 }
90 return false;
91 }
92
93 /** Return the next node */
94 template< typename TTreeType >
95 const typename LevelOrderTreeIterator< TTreeType >::ValueType &
Next()96 LevelOrderTreeIterator< TTreeType >::Next()
97 {
98 this->m_Position = const_cast< TreeNodeType * >( FindNextNode() );
99 if ( this->m_Position == nullptr )
100 {
101 return this->m_Root->Get(); //value irrelevant, but we have to return something
102 }
103 return this->m_Position->Get();
104 }
105
106 /** Get the start Level */
107 template< typename TTreeType >
GetStartLevel() const108 int LevelOrderTreeIterator< TTreeType >::GetStartLevel() const
109 {
110 return m_StartLevel;
111 }
112
113 /** Get the end level */
114 template< typename TTreeType >
115 int
GetEndLevel() const116 LevelOrderTreeIterator< TTreeType >::GetEndLevel() const
117 {
118 return m_EndLevel;
119 }
120
121 /** Find the next available node */
122 template< typename TTreeType >
123 const typename LevelOrderTreeIterator< TTreeType >::TreeNodeType *
FindNextNode() const124 LevelOrderTreeIterator< TTreeType >::FindNextNode() const
125 {
126 int level;
127 const TreeNodeType *node;
128
129 do
130 {
131 node = FindNextNodeHelp();
132 if ( node == nullptr )
133 {
134 return nullptr;
135 }
136 level = GetLevel(node);
137 if ( level > m_EndLevel )
138 {
139 return nullptr;
140 }
141 }
142 while ( level < m_StartLevel );
143
144 return node;
145 }
146
147 /** Return the current level */
148 template< typename TTreeType >
149 int
GetLevel() const150 LevelOrderTreeIterator< TTreeType >::GetLevel() const
151 {
152 if ( this->m_Position == nullptr )
153 {
154 return -1;
155 }
156
157 int level = 0;
158 TreeNodeType *node = this->m_Position;
159 while ( node->HasParent() && node != this->m_Root )
160 {
161 node = dynamic_cast< TreeNodeType * >( node->GetParent() );
162 level++;
163 }
164 return level;
165 }
166
167 /** Return the level given a node */
168 template< typename TTreeType >
169 int
GetLevel(const TreeNodeType * node) const170 LevelOrderTreeIterator< TTreeType >::GetLevel(const TreeNodeType *node) const
171 {
172 if ( node == nullptr )
173 {
174 return -1;
175 }
176 int level = 0;
177
178 while ( node->HasParent() && node != this->m_Root )
179 {
180 node = dynamic_cast< const TreeNodeType * >( node->GetParent() );
181 level++;
182 }
183 return level;
184 }
185
186 /** Helper function to find the next node */
187 template< typename TTreeType >
188 const typename LevelOrderTreeIterator< TTreeType >::TreeNodeType *
FindNextNodeHelp() const189 LevelOrderTreeIterator< TTreeType >::FindNextNodeHelp() const
190 {
191 if ( m_Queue.empty() )
192 {
193 return nullptr;
194 }
195
196 const TreeNodeType *currentNode = m_Queue.front();
197 m_Queue.pop();
198
199 if ( currentNode == nullptr )
200 {
201 return nullptr;
202 }
203
204 int size = currentNode->CountChildren();
205
206 for ( int i = 0; i < size; i++ )
207 {
208 auto * child = dynamic_cast< TreeNodeType * >( currentNode->GetChild(i) );
209 if ( child != nullptr )
210 {
211 m_Queue.push(child);
212 }
213 }
214
215 // If the current node is the root we try again
216 if ( currentNode == this->m_Root )
217 {
218 currentNode = const_cast< TreeNodeType * >( FindNextNodeHelp() );
219 }
220 return currentNode;
221 }
222
223 /** Clone function */
224 template< typename TTreeType >
Clone()225 TreeIteratorBase< TTreeType > *LevelOrderTreeIterator< TTreeType >::Clone()
226 {
227 auto * clone = new LevelOrderTreeIterator< TTreeType >(
228 const_cast< TTreeType * >( this->m_Tree ), m_StartLevel, m_EndLevel);
229 *clone = *this;
230 return clone;
231 }
232 } // end namespace itk
233
234 #endif
235