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 itkLeafTreeIterator_h
19 #define itkLeafTreeIterator_h
20 
21 #include "itkPreOrderTreeIterator.h"
22 
23 namespace itk
24 {
25 template< typename TTreeType >
26 class ITK_TEMPLATE_EXPORT LeafTreeIterator:public TreeIteratorBase< TTreeType >
27 {
28 public:
29 
30   /** Typedefs */
31   using Self = LeafTreeIterator;
32   using Superclass = TreeIteratorBase< TTreeType >;
33   using TreeType = TTreeType;
34   using ValueType = typename TreeType::ValueType;
35   using TreeNodeType = typename Superclass::TreeNodeType;
36   using NodeType = typename Superclass::NodeType;
37 
38   /** Constructor */
39   LeafTreeIterator(const TreeType *tree);
40 
41   /** Constructor */
42   LeafTreeIterator(TreeType *tree);
43 
44   /** Destructor */
45   ~LeafTreeIterator() override;
46 
47   /** Return the type of iterator */
48   NodeType GetType() const override;
49 
50   /** Clone function */
51   TreeIteratorBase< TTreeType > * Clone() override;
52 
53 protected:
54 
55   /** Return the next value */
56   const ValueType & Next() override;
57 
58   /** Return true if the next value exists */
59   bool HasNext() const override;
60 
61 private:
62 
63   /** Find the next node */
64   const TreeNodeType * FindNextNode() const;
65 };
66 
67 /** Constructor */
68 template< typename TTreeType >
LeafTreeIterator(const TTreeType * tree)69 LeafTreeIterator< TTreeType >::LeafTreeIterator(const TTreeType *tree):
70   TreeIteratorBase< TTreeType >(tree, nullptr)
71 {
72   this->m_Begin = const_cast< TreeNodeType * >( this->FindNextNode() ); //
73                                                                         //
74                                                                         // Position
75                                                                         // the
76                                                                         //
77                                                                         // iterator
78                                                                         // to
79                                                                         // the
80                                                                         // first
81                                                                         // leaf;
82 }
83 
84 /** Constructor */
85 template< typename TTreeType >
LeafTreeIterator(TTreeType * tree)86 LeafTreeIterator< TTreeType >::LeafTreeIterator(TTreeType *tree):
87   TreeIteratorBase< TTreeType >(tree, nullptr)
88 {
89   this->m_Begin = const_cast< TreeNodeType * >( this->FindNextNode() ); //
90                                                                         //
91                                                                         // Position
92                                                                         // the
93                                                                         //
94                                                                         // iterator
95                                                                         // to
96                                                                         // the
97                                                                         // first
98                                                                         // leaf;
99 }
100 
101 /** Destructor */
102 template< typename TTreeType >
103 LeafTreeIterator< TTreeType >::~LeafTreeIterator() = default;
104 
105 /** Return the type of iterator */
106 template< typename TTreeType >
107 typename LeafTreeIterator< TTreeType >::NodeType
GetType()108 LeafTreeIterator< TTreeType >::GetType() const
109 {
110   return TreeIteratorBase< TTreeType >::LEAF;
111 }
112 
113 /** Return true if the next value exists */
114 template< typename TTreeType >
HasNext()115 bool LeafTreeIterator< TTreeType >::HasNext() const
116 {
117   if ( this->m_Position == nullptr )
118     {
119     return false;
120     }
121   if ( const_cast< TreeNodeType * >( FindNextNode() ) != nullptr )
122     {
123     return true;
124     }
125   return false;
126 }
127 
128 /** Return the next node */
129 template< typename TTreeType >
130 const typename LeafTreeIterator< TTreeType >::ValueType &
Next()131 LeafTreeIterator< TTreeType >::Next()
132 {
133   this->m_Position = const_cast< TreeNodeType * >( FindNextNode() );
134   return this->m_Position->Get();
135 }
136 
137 /** Find the next node given the position */
138 template< typename TTreeType >
139 const typename LeafTreeIterator< TTreeType >::TreeNodeType *
FindNextNode()140 LeafTreeIterator< TTreeType >::FindNextNode() const
141 {
142   PreOrderTreeIterator< TTreeType > it(this->m_Tree, this->m_Position);
143   it.m_Root = this->m_Root;
144   ++it; // go next
145   if ( it.IsAtEnd() )
146     {
147     return nullptr;
148     }
149 
150   if ( !it.HasChild() )
151     {
152     return it.GetNode();
153     }
154 
155   while ( !it.IsAtEnd() )
156     {
157     if ( !it.HasChild() )
158       {
159       return it.GetNode();
160       }
161     ++it;
162     }
163 
164   return nullptr;
165 }
166 
167 /** Clone function */
168 template< typename TTreeType >
Clone()169 TreeIteratorBase< TTreeType > *LeafTreeIterator< TTreeType >::Clone()
170 {
171   auto * clone = new LeafTreeIterator< TTreeType >(this->m_Tree);
172   *clone = *this;
173   return clone;
174 }
175 } // end namespace itk
176 
177 #endif
178