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 // Forward reference because of circular dependencies
26 template< typename TTreeType >
27 class ITK_TEMPLATE_EXPORT LeafTreeIterator;
28
29 template< typename TTreeType >
30 class PreOrderTreeIterator:public TreeIteratorBase< TTreeType >
31 {
32 public:
33
34 /** Typedefs */
35 using ValueType = typename TTreeType::ValueType;
36 using Superclass = TreeIteratorBase< TTreeType >;
37 using TreeNodeType = typename Superclass::TreeNodeType;
38 using NodeType = typename Superclass::NodeType;
39
40 /** Constructor */
41 PreOrderTreeIterator(const TTreeType *tree, const TreeNodeType *start = nullptr);
42
43 /** Get the type of the iterator */
44 NodeType GetType() const override;
45
46 /** Clone function */
47 TreeIteratorBase< TTreeType > * Clone() override;
48
49 protected:
50 /** Return the next node */
51 const ValueType & Next() override;
52
53 /** Return true if the next node exists */
54 bool HasNext() const override;
55
56 private:
57
58 /** Find the next node */
59 const TreeNodeType * FindNextNode() const;
60
61 /** LeafTreeIterator uses PreOrderTreeIterator in its implementation, but it
62 * needs to adjust its root. A friend designation is added to correct
63 * behavior and retain backwards compatible behavior. */
64 friend class LeafTreeIterator< TTreeType >;
65 };
66
67 /** Constructor */
68 template< typename TTreeType >
PreOrderTreeIterator(const TTreeType * tree,const TreeNodeType * start)69 PreOrderTreeIterator< TTreeType >::PreOrderTreeIterator(const TTreeType *tree, const TreeNodeType *start):
70 TreeIteratorBase< TTreeType >(tree, start)
71 {}
72
73 /** Return the type of the iterator */
74 template< typename TTreeType >
75 typename PreOrderTreeIterator< TTreeType >::NodeType
GetType()76 PreOrderTreeIterator< TTreeType >::GetType() const
77 {
78 return TreeIteratorBase< TTreeType >::PREORDER;
79 }
80
81 /** Return true if the next node exists */
82 template< typename TTreeType >
83 bool
HasNext()84 PreOrderTreeIterator< TTreeType >::HasNext() const
85 {
86 if ( const_cast< TreeNodeType * >( FindNextNode() ) != nullptr )
87 {
88 return true;
89 }
90 return false;
91 }
92
93 /** Return the next node */
94 template< typename TTreeType >
95 const typename PreOrderTreeIterator< TTreeType >::ValueType &
Next()96 PreOrderTreeIterator< 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 /** Find the next node */
107 template< typename TTreeType >
108 const typename PreOrderTreeIterator< TTreeType >::TreeNodeType *
FindNextNode()109 PreOrderTreeIterator< TTreeType >::FindNextNode() const
110 {
111 if ( this->m_Position == nullptr )
112 {
113 return nullptr;
114 }
115 if ( this->m_Position->HasChildren() )
116 {
117 return dynamic_cast< const TreeNodeType * >( 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;
127
128 while ( parent->HasParent() )
129 {
130 child = parent;
131 parent = dynamic_cast< TreeNodeType * >( parent->GetParent() );
132
133 // Subtree
134 if ( parent->ChildPosition(this->m_Root) >= 0 )
135 {
136 return nullptr;
137 }
138
139 int childPosition = parent->ChildPosition(child);
140 int lastChildPosition = parent->CountChildren() - 1;
141
142 while ( childPosition < lastChildPosition )
143 {
144 auto * help = dynamic_cast< TreeNodeType * >( parent->GetChild(childPosition + 1) );
145
146 if ( help != nullptr )
147 {
148 return help;
149 }
150 childPosition++;
151 }
152 }
153 return nullptr;
154 }
155
156 /** Clone function */
157 template< typename TTreeType >
Clone()158 TreeIteratorBase< TTreeType > *PreOrderTreeIterator< TTreeType >::Clone()
159 {
160 auto * clone = new PreOrderTreeIterator< TTreeType >(this->m_Tree, this->m_Position);
161 *clone = *this;
162 return clone;
163 }
164 } // end namespace itk
165
166 #endif
167