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