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 
30   /** Typedefs */
31   using Self = InOrderTreeIterator;
32   using Superclass = TreeIteratorBase< TTreeType >;
33   using TreeType = TTreeType;
34   using ValueType = typename TTreeType::ValueType;
35   using TreeNodeType = typename Superclass::TreeNodeType;
36   using NodeType = typename Superclass::NodeType;
37 
38   /** Constructors */
39   InOrderTreeIterator(TreeType & start);
40   InOrderTreeIterator(TreeType *tree, TreeNodeType *start = nullptr);
41 
42   /** Get the type of iterator */
43   NodeType GetType() const override;
44 
45   /** Clone function */
46   TreeIteratorBase< TTreeType > * Clone() override;
47 
48 protected:
49 
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 
62 /** Constructor */
63 template< typename TTreeType >
InOrderTreeIterator(TTreeType & start)64 InOrderTreeIterator< TTreeType >::InOrderTreeIterator(TTreeType & start):
65   TreeIteratorBase< TTreeType >(start)
66 {}
67 
68 /** Constructor */
69 template< typename TTreeType >
InOrderTreeIterator(TTreeType * tree,TreeNodeType * start)70 InOrderTreeIterator< TTreeType >::InOrderTreeIterator(TTreeType *tree, TreeNodeType *start):
71   TreeIteratorBase< TTreeType >(tree, start)
72 {}
73 
74 /** Get the type of the iterator */
75 template< typename TTreeType >
76 typename InOrderTreeIterator< TTreeType >::NodeType
GetType()77 InOrderTreeIterator< TTreeType >::GetType() const
78 {
79   return TreeIteratorBase< TTreeType >::INORDER;
80 }
81 
82 /** Return true if the next node exists */
83 template< typename TTreeType >
HasNext()84 bool InOrderTreeIterator< 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 InOrderTreeIterator< TTreeType >::ValueType &
Next()96 InOrderTreeIterator< TTreeType >::Next()
97 {
98   this->m_Position =  const_cast< TreeNodeType * >( FindNextNode() );
99   return this->m_Position->Get();
100 }
101 
102 /** Find the next node */
103 template< typename TTreeType >
104 const typename InOrderTreeIterator< TTreeType >::TreeNodeType *
FindNextNode()105 InOrderTreeIterator< TTreeType >::FindNextNode() const
106 {
107   if ( this->m_Position == nullptr )
108     {
109     return nullptr;
110     }
111 
112   if ( this->m_Position->HasChildren() )
113     {
114     return this->m_Position->GetChild(0);
115     }
116 
117   if ( !this->m_Position->HasParent() )
118     {
119     return nullptr;
120     }
121 
122   TreeNodeType *child = this->m_Position;
123   TreeNodeType *parent = this->m_Position->GetParent();
124 
125   int childPosition = parent->ChildPosition(child);
126   int lastChildPosition = parent->CountChildren() - 1;
127 
128   while ( childPosition < lastChildPosition )
129     {
130     TreeNodeType *help = parent->GetChild(childPosition + 1);
131     if ( help != nullptr )
132       {
133       return help;
134       }
135     childPosition++;
136     }
137 
138   while ( parent->HasParent() )
139     {
140     child = parent;
141     parent = parent->GetParent();
142 
143     // Subtree
144     if ( parent->ChildPosition(this->m_Root) >= 0 )
145       {
146       return nullptr;
147       }
148     childPosition = parent->ChildPosition(child);
149     lastChildPosition = parent->CountChildren() - 1;
150 
151     while ( childPosition < lastChildPosition )
152       {
153       TreeNodeType *help = parent->GetChild(childPosition + 1);
154       if ( help != nullptr )
155         {
156         return help;
157         }
158       }
159     }
160   return nullptr;
161 }
162 
163 /** Clone function */
164 template< typename TTreeType >
Clone()165 TreeIteratorBase< TTreeType > *InOrderTreeIterator< TTreeType >::Clone()
166 {
167   auto * clone = new InOrderTreeIterator( const_cast< TTreeType * >( this->m_Tree ) );
168 
169   *clone = *this;
170   return clone;
171 }
172 } // end namespace itk
173 
174 #endif
175