KWStyle - itkLevelOrderTreeIterator.h

Matrix View

Description

---

1		/*=========================================================================
2
3		Program:   Insight Segmentation & Registration Toolkit
4		Module:    $RCSfile: itkLevelOrderTreeIterator.h.html,v $
5		Language:  C++
6		Date:      $Date: 2006/01/17 19:15:40 $
7		Version:   $Revision: 1.4 $
8
9		Copyright (c) Insight Software Consortium. All rights reserved.
10		See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
11
12		This software is distributed WITHOUT ANY WARRANTY; without even
13		the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
14		PURPOSE.  See the above copyright notices for more information.
15
16		=========================================================================*/
17		#ifndef __itkLevelOrderTreeIterator_h
18		#define __itkLevelOrderTreeIterator_h
19
20		#include <queue>
21		#include <itkTreeIteratorBase.h>
22
23	NMS	namespace itk{
24
25		template <class TTreeType>
26		class LevelOrderTreeIterator : public TreeIteratorBase<TTreeType>
27		{
28		public:
29
30		/** Typedefs */
31		typedef TreeIteratorBase<TTreeType> Superclass;
32	TDA	typedef typename Superclass::Self Self;
33	TDA	typedef TTreeType TreeType;
34	TDA	typedef typename TTreeType::ValueType ValueType;
35	TDA	typedef typename Superclass::TreeNodeType TreeNodeType;
36
37		/** Constructors */
38	LEN	LevelOrderTreeIterator( TreeType* tree, int endLevel = INT_MAX, const TreeNodeType* start = NULL);
39	LEN	LevelOrderTreeIterator( TreeType* tree, int startLevel, int endLevel, const TreeNodeType* start = NULL);
40
41		virtual ~LevelOrderTreeIterator() {};
42
43		/** Get the type of the iterator */
44	SEM	int GetType() const ;
45
46		/** Get the start level */
47		int GetStartLevel() const;
48
49		/** Get the end level */
50		int GetEndLevel() const;
51
52		/** Get the current level */
53		int GetLevel() const;
54
55		/** Clone function */
56		TreeIteratorBase<TTreeType>* Clone();
57
58		/** operator = */
59		Self& operator=(Superclass& iterator)
60		{
61		Superclass::operator=(iterator);
62	LEN	LevelOrderTreeIterator<TTreeType>& it = static_cast<LevelOrderTreeIterator<TTreeType>&>(iterator);
63		m_StartLevel = it.m_StartLevel;
64		m_EndLevel = it.m_EndLevel;
65		m_Queue = it.m_Queue;
66		return *this;
67		}
68
69
70		protected:
71
72		/** Return the next node */
73		const ValueType& Next();
74		/** Return true if the next node exists */
75		bool HasNext() const;
76
77		private:
78
79		const TreeNodeType* FindNextNode() const;
80	SEM	const TreeNodeType* FindNextNodeHelp() const ;
81		int GetLevel( const TreeNodeType* node ) const;
82		int m_StartLevel;
83		int m_EndLevel;
84		mutable std::queue<const TreeNodeType*> m_Queue;
85
86		};
87
88
89		/** Constructor with end level specification */
90		template <class TTreeType>
91		LevelOrderTreeIterator<TTreeType>
92	LEN	::LevelOrderTreeIterator( TTreeType* tree, int endLevel, const TreeNodeType* start)
93	IND	*:TreeIteratorBase<TTreeType>(tree,start)
94		{
95		m_StartLevel =  -1;
96		m_EndLevel = endLevel;
97		if ( start != NULL )
98		{
99		m_Queue.push( start );
100		this->m_Position = const_cast<TreeNodeType*>(start);
101		}
102		else
103		{
104		if(tree->GetRoot())
105		{
106		m_Queue.push( dynamic_cast<const TreeNodeType*>(tree->GetRoot()) );
107	LEN	this->m_Position = const_cast<TreeNodeType*>(dynamic_cast<const TreeNodeType*>(tree->GetRoot()));
108		}
109		}
110		this->m_Begin = this->m_Position;
111		}
112
113		/** Constructor with end level specification */
114		template <class TTreeType>
115		LevelOrderTreeIterator<TTreeType>
116	LEN	::LevelOrderTreeIterator( TTreeType* tree, int startLevel, int endLevel, const TreeNodeType* start)
117	IND	*:TreeIteratorBase<TTreeType>(tree,start)
118		{
119		m_StartLevel = startLevel;
120		m_EndLevel = endLevel;
121		if ( start != NULL )
122		{
123		m_Queue.push( start );
124		this->m_Position = const_cast<TreeNodeType*>(start);
125		}
126		else
127		{
128		if(tree->GetRoot())
129		{
130		m_Queue.push( dynamic_cast<const TreeNodeType*>(tree->GetRoot()) );
131	LEN	this->m_Position = const_cast<TreeNodeType*>(dynamic_cast<const TreeNodeType*>(tree->GetRoot()));
132		}
133		}
134		this->m_Begin = this->m_Position;
135		}
136
137		/** Return the type of iterator */
138		template <class TTreeType>
139		int
140		LevelOrderTreeIterator<TTreeType>::GetType() const
141		{
142		return TreeIteratorBase<TTreeType>::LEVELORDER;
143		}
144
145		/** Return true if the next value exists */
146		template <class TTreeType>
147		bool
148		LevelOrderTreeIterator<TTreeType>::HasNext() const
149		{
150	IND	*if(const_cast<TreeNodeType*>(FindNextNode()))
151	IND	***{
152	IND	***return true;
153	IND	***}
154		return false;
155		}
156
157		/** Return the next node */
158		template <class TTreeType>
159		const typename LevelOrderTreeIterator<TTreeType>::ValueType&
160		LevelOrderTreeIterator<TTreeType>::Next()
161		{
162		this->m_Position = const_cast<TreeNodeType* >(FindNextNode());
163		return this->m_Position->Get();
164		}
165
166		/** Get the start Level */
167		template <class TTreeType>
168		int LevelOrderTreeIterator<TTreeType>::GetStartLevel() const
169		{
170		return m_StartLevel;
171		}
172
173		/** Get the end level */
174		template <class TTreeType>
175		int
176		LevelOrderTreeIterator<TTreeType>::GetEndLevel() const
177		{
178		return m_EndLevel;
179		}
180
181		/** Find the next available node */
182		template <class TTreeType>
183		const typename LevelOrderTreeIterator<TTreeType>::TreeNodeType*
184		LevelOrderTreeIterator<TTreeType>::FindNextNode() const
185		{
186		int level;
187		const TreeNodeType* node;
188
189		do{
190		node = FindNextNodeHelp();
191		if ( node == NULL )
192		{
193		return NULL;
194		}
195		level = GetLevel( node );
196		if ( level > m_EndLevel )
197		{
198		return NULL;
199		}
200	IND	**} while ( level < m_StartLevel );
201
202		return node;
203		}
204
205		/** Return the current level */
206		template <class TTreeType>
207		int
208		LevelOrderTreeIterator<TTreeType>::GetLevel() const
209		{
210		if( this->m_Position == NULL )
211		{
212		return -1;
213		}
214
215		int level = 0;
216		TreeNodeType* node = this->m_Position;
217		while( node->HasParent() && node != this->m_Root )
218		{
219		node = dynamic_cast<TreeNodeType*>(node->GetParent());
220		level++;
221		}
222		return level;
223		}
224
225		/** Return the level given a node */
226		template <class TTreeType>
227		int
228		LevelOrderTreeIterator<TTreeType>::GetLevel( const TreeNodeType* node ) const
229		{
230		if( node == NULL )
231		{
232		return -1;
233		}
234		int level = 0;
235
236		while( node->HasParent() && node != this->m_Root )
237		{
238		node = dynamic_cast<const TreeNodeType*>(node->GetParent());
239		level++;
240		}
241		return level;
242		}
243
244		/** Helper function to find the next node */
245		template <class TTreeType>
246		const typename LevelOrderTreeIterator<TTreeType>::TreeNodeType*
247		LevelOrderTreeIterator<TTreeType>::FindNextNodeHelp() const
248		{
249		if( m_Queue.empty() )
250		{
251		return NULL;
252		}
253
254		const TreeNodeType *currentNode = m_Queue.front();
255		m_Queue.pop();
256
257		if ( currentNode == NULL)
258		{
259		return NULL;
260		}
261
262		int size = currentNode->CountChildren();
263
264		for ( int i=0; i < size; i++ )
265		{
266	LEN	TreeNodeType *child = dynamic_cast<TreeNodeType*>(currentNode->GetChild( i ));
267		if ( child != NULL )
268		{
269		m_Queue.push(child);
270		}
271		}
272
273		// If the current node is the root we try again
274		if(currentNode == this->m_Root)
275		{
276		currentNode = const_cast<TreeNodeType*>(FindNextNodeHelp());
277		}
278		return currentNode;
279		}
280
281		/** Clone function */
282		template <class TTreeType>
283		TreeIteratorBase<TTreeType>* LevelOrderTreeIterator<TTreeType>::Clone()
284		{
285	LEN	LevelOrderTreeIterator<TTreeType>* clone = new LevelOrderTreeIterator<TTreeType>( const_cast<TTreeType*>(this->m_Tree), m_StartLevel, m_EndLevel );
286		*clone = *this;
287		return clone;
288		}
289
290
291	EML
292		} // end namespace itk
293
294		#endif
295

---

Generated by KWStyle 1.0b on Tuesday January,17 at 02:14:18PM

© Kitware Inc.