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_h
19 #define itkLevelOrderTreeIterator_h
20 
21 #include <queue>
22 #include <climits>
23 #include "itkTreeIteratorBase.h"
24 
25 namespace itk
26 {
27 /**
28  * \class LevelOrderTreeIterator
29  * \brief Iterate over a tree in level order.
30  *
31  * \ingroup ITKCommon
32  */
33 template< typename TTreeType >
34 class ITK_TEMPLATE_EXPORT LevelOrderTreeIterator:public TreeIteratorBase< TTreeType >
35 {
36 public:
37 
38   /** Typedefs */
39   using Self = LevelOrderTreeIterator;
40   using Superclass = TreeIteratorBase< TTreeType >;
41   using TreeType = TTreeType;
42   using ValueType = typename TTreeType::ValueType;
43   using TreeNodeType = typename Superclass::TreeNodeType;
44   using NodeType = typename Superclass::NodeType;
45 
46   /** Constructor with end level specification */
47   LevelOrderTreeIterator(TreeType *tree, int endLevel = INT_MAX, const TreeNodeType *start = nullptr);
48 
49   /** Constructor with end level specification */
50   LevelOrderTreeIterator(TreeType *tree, int startLevel, int endLevel, const TreeNodeType *start = nullptr);
51 
52   ~LevelOrderTreeIterator() override = default;
53 
54   /** Get the type of the iterator */
55   NodeType GetType() const override;
56 
57   /** Get the start level */
58   int GetStartLevel() const;
59 
60   /** Get the end level */
61   int GetEndLevel() const;
62 
63   /** Get the current level */
64   int GetLevel() const;
65 
66   /** Clone function */
67   TreeIteratorBase< TTreeType > * Clone() override;
68 
69   /** operator = */
70   const Self & operator=(const Self & iterator)
71   {
72     if(this != &iterator)
73       {
74       this->Superclass::operator=(iterator);
75       m_StartLevel = iterator.m_StartLevel;
76       m_EndLevel = iterator.m_EndLevel;
77       m_Queue = iterator.m_Queue;
78       }
79     return *this;
80   }
81 
82 protected:
83 
84   /** Return the next node */
85   const ValueType & Next() override;
86 
87   /** Return true if the next node exists */
88   bool HasNext() const override;
89 
90 private:
91 
92   const TreeNodeType * FindNextNode() const;
93 
94   const TreeNodeType * FindNextNodeHelp() const;
95 
96   int GetLevel(const TreeNodeType *node) const;
97 
98   int                                        m_StartLevel;
99   int                                        m_EndLevel;
100   mutable std::queue< const TreeNodeType * > m_Queue;
101 };
102 
103 } // end namespace itk
104 
105 #ifndef ITK_MANUAL_INSTANTIATION
106 #include "itkLevelOrderTreeIterator.hxx"
107 #endif
108 
109 #endif
110