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 itkPostOrderTreeIterator_h
19 #define itkPostOrderTreeIterator_h
20 
21 #include "itkTreeIteratorBase.h"
22 
23 namespace itk
24 {
25 template< typename TTreeType >
26 class PostOrderTreeIterator:public TreeIteratorBase< TTreeType >
27 {
28 public:
29 
30   /** Typedefs */
31   using Self = PostOrderTreeIterator;
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   /** Constructor */
39   PostOrderTreeIterator(TreeType *tree);
40 
41   /** Get the type of the iterator */
42   NodeType GetType() const override;
43 
44   /** Clone function */
45   TreeIteratorBase< TTreeType > * Clone() override;
46 
47 protected:
48   /** Return the next node */
49   const ValueType & Next() override;
50 
51   /** Return true if the next node exists */
52   bool HasNext() const override;
53 
54 protected:
55 
56   const TreeNodeType * FindNextNode() const;
57 
58   const TreeNodeType * FindMostRightLeaf(TreeNodeType *node) const;
59 
60   const TreeNodeType * FindSister(TreeNodeType *node) const;
61 };
62 
63 /** Constructor */
64 template< typename TTreeType >
PostOrderTreeIterator(TTreeType * tree)65 PostOrderTreeIterator< TTreeType >::PostOrderTreeIterator(TTreeType *tree):
66   TreeIteratorBase< TTreeType >(tree, nullptr)
67 {
68   if ( tree->GetRoot() == nullptr )
69     {
70     this->m_Begin = nullptr;
71     }
72   else
73     {
74     const auto * root = dynamic_cast<const TreeNodeType *>(tree->GetRoot());
75     if(root == nullptr)
76       {
77       itkGenericExceptionMacro(<< "Can't downcast root node to TreeNodeType *");
78       }
79     this->m_Position = const_cast<TreeNodeType *>(root);
80     this->m_Position = const_cast< TreeNodeType * >( FindMostRightLeaf(this->m_Position) );
81     this->m_Begin = this->m_Position;
82     }
83 }
84 
85 /** Return the type of the iterator */
86 template< typename TTreeType >
87 typename PostOrderTreeIterator< TTreeType >::NodeType
GetType()88 PostOrderTreeIterator< TTreeType >::GetType() const
89 {
90   return TreeIteratorBase< TTreeType >::POSTORDER;
91 }
92 
93 /** Return true if the next node exists */
94 template< typename TTreeType >
95 bool
HasNext()96 PostOrderTreeIterator< TTreeType >::HasNext() const
97 {
98   if ( const_cast< TreeNodeType * >( FindNextNode() ) != nullptr )
99     {
100     return true;
101     }
102   return false;
103 }
104 
105 /** Go to the next node */
106 template< typename TTreeType >
107 const typename PostOrderTreeIterator< TTreeType >::ValueType &
Next()108 PostOrderTreeIterator< TTreeType >::Next()
109 {
110   this->m_Position = const_cast< TreeNodeType * >( FindNextNode() );
111   return this->m_Position->Get();
112 }
113 
114 /** Find the next node */
115 template< typename TTreeType >
116 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType *
FindNextNode()117 PostOrderTreeIterator< TTreeType >::FindNextNode() const
118 {
119   if ( this->m_Position == nullptr || this->m_Position == this->m_Root )
120     {
121     return nullptr;
122     }
123   auto * sister = const_cast< TreeNodeType * >( FindSister(this->m_Position) );
124 
125   if ( sister != nullptr )
126     {
127     return FindMostRightLeaf(sister);
128     }
129   if(this->m_Position->GetParent() == nullptr)
130     {
131     return nullptr;
132     }
133   auto * rval = dynamic_cast<TreeNodeType *>(this->m_Position->GetParent());
134   if(rval == nullptr)
135     {
136       itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
137     }
138   return rval;
139 }
140 
141 /** Find the sister node */
142 template< typename TTreeType >
143 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType *
FindSister(TreeNodeType * node)144 PostOrderTreeIterator< TTreeType >::FindSister(TreeNodeType *node) const
145 {
146   if ( !node->HasParent() )
147     {
148     return nullptr;
149     }
150 
151   auto * parent = dynamic_cast<TreeNodeType *>(node->GetParent());
152   if(parent == nullptr)
153     {
154     itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
155     }
156 
157   int childPosition = parent->ChildPosition(node);
158   int lastChildPosition = parent->CountChildren() - 1;
159 
160   while ( childPosition < lastChildPosition )
161     {
162     if(parent->GetChild(childPosition + 1) == nullptr)
163       {
164       childPosition++;
165       }
166     else
167       {
168       auto * sister = dynamic_cast<TreeNodeType *>(parent->GetChild(childPosition + 1));
169       if ( sister == nullptr)
170       {
171       itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
172       }
173       return sister;
174       }
175     }
176   return nullptr;
177 }
178 
179 /** Find the most right leaf */
180 template< typename TTreeType >
181 const typename PostOrderTreeIterator< TTreeType >::TreeNodeType *
FindMostRightLeaf(TreeNodeType * node)182 PostOrderTreeIterator< TTreeType >::FindMostRightLeaf(TreeNodeType *node) const
183 {
184   while ( node->HasChildren() )
185     {
186     TreeNodeType *helpNode;
187     int           childCount = node->CountChildren();
188     int           i = 0;
189 
190     do
191       {
192       if(node->GetChild(i) == nullptr)
193         {
194         helpNode = nullptr;
195         }
196       else
197         {
198         helpNode = dynamic_cast<TreeNodeType *>(node->GetChild(i));
199        if(helpNode == nullptr)
200           {
201           itkGenericExceptionMacro(<< "Can't downcast to TreeNodeType *");
202           }
203         }
204       i++;
205       }
206     while ( helpNode == nullptr && i < childCount );
207 
208     if ( helpNode == nullptr )
209       {
210       return node;
211       }
212     node = helpNode;
213     }
214   return node;
215 }
216 
217 /** Clone function */
218 template< typename TTreeType >
Clone()219 TreeIteratorBase< TTreeType > *PostOrderTreeIterator< TTreeType >::Clone()
220 {
221   auto * clone = new PostOrderTreeIterator< TTreeType >( const_cast< TTreeType * >( this->m_Tree ) );
222   *clone = *this;
223   return clone;
224 }
225 } // end namespace itk
226 
227 #endif
228