KWStyle - itkPostOrderTreeIterator.h

Matrix View

Description

---

1		/*=========================================================================
2
3		Program:   Insight Segmentation & Registration Toolkit
4		Module:    $RCSfile: itkPostOrderTreeIterator.h.html,v $
5		Language:  C++
6		Date:      $Date: 2006/01/17 19:15:45 $
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 __itkPostOrderTreeIterator_h
18		#define __itkPostOrderTreeIterator_h
19
20		#include <itkTreeIteratorBase.h>
21
22	NMS	namespace itk{
23
24		template <class TTreeType>
25		class PostOrderTreeIterator : public TreeIteratorBase<TTreeType>
26		{
27		public:
28
29		/** Typedefs */
30		typedef TreeIteratorBase<TTreeType>  Superclass;
31	TDA	typedef TTreeType TreeType;
32	TDA	typedef typename TTreeType::ValueType ValueType;
33	TDA	typedef typename Superclass::TreeNodeType TreeNodeType;
34
35		/** Constructor */
36		PostOrderTreeIterator(TreeType* tree);
37
38		/** Get the type of the iterator */
39		int GetType() const;
40		/** Clone function */
41		TreeIteratorBase<TTreeType>* Clone();
42
43		protected:
44		/** Return the next node */
45		const ValueType& Next();
46		/** Return true if the next node exists */
47		bool HasNext() const;
48
49		protected:
50
51		const TreeNodeType* FindNextNode() const;
52		const TreeNodeType* FindMostRightLeaf(TreeNodeType* node) const;
53		const TreeNodeType* FindSister(TreeNodeType* node) const;
54
55		};
56
57		/** Constructor */
58		template <class TTreeType>
59		PostOrderTreeIterator<TTreeType>::PostOrderTreeIterator( TTreeType* tree)
60	IND	****:TreeIteratorBase<TTreeType>(tree,NULL)
61		{
62		this->m_Position = const_cast<TreeNode<ValueType>*>(tree->GetRoot());
63
64		if ( this->m_Position == NULL )
65	IND	**{
66		this->m_Begin = NULL;
67	IND	**}
68		else
69	IND	**{
70	LEN	this->m_Position =const_cast<TreeNodeType* >(FindMostRightLeaf(this->m_Position));
71		this->m_Begin = this->m_Position;
72	IND	**}
73		}
74
75
76		/** Return the type of the iterator */
77		template <class TTreeType>
78		int
79		PostOrderTreeIterator<TTreeType>::GetType() const
80		{
81		return TreeIteratorBase<TTreeType>::POSTORDER;
82		}
83
84
85		/** Return true if the next node exists */
86		template <class TTreeType>
87		bool
88		PostOrderTreeIterator<TTreeType>::HasNext() const
89		{
90		if(const_cast<TreeNodeType* >(FindNextNode()) != NULL)
91		{
92		return true;
93		}
94		return false;
95		}
96
97		/** Go to the next node */
98		template <class TTreeType>
99		const typename PostOrderTreeIterator<TTreeType>::ValueType&
100		PostOrderTreeIterator<TTreeType>::Next()
101		{
102		this->m_Position = const_cast<TreeNodeType*>(FindNextNode());
103		return this->m_Position->Get();
104		}
105
106		/** Find the next node */
107		template <class TTreeType>
108		const typename PostOrderTreeIterator<TTreeType>::TreeNodeType*
109		PostOrderTreeIterator<TTreeType>::FindNextNode() const
110		{
111		if ( this->m_Position == NULL || this->m_Position == this->m_Root )
112		{
113		return NULL;
114		}
115	LEN	TreeNodeType* sister = const_cast<TreeNodeType*>(FindSister( this->m_Position ));
116
117		if ( sister != NULL )
118		{
119		return FindMostRightLeaf( sister );
120		}
121
122		return this->m_Position->GetParent();
123		}
124
125
126		/** Find the sister node */
127		template <class TTreeType>
128		const typename PostOrderTreeIterator<TTreeType>::TreeNodeType*
129		PostOrderTreeIterator<TTreeType>::FindSister( TreeNodeType* node ) const
130		{
131		if ( !node->HasParent() )
132		{
133		return NULL;
134		}
135
136		TreeNodeType* parent = node->GetParent();
137		int childPosition = parent->ChildPosition( node );
138		int lastChildPosition = parent->CountChildren() - 1;
139
140		while ( childPosition < lastChildPosition )
141		{
142		TreeNodeType* sister = parent->GetChild( childPosition + 1);
143
144		if ( sister != NULL )
145		{
146		return sister;
147		}
148		childPosition++;
149		}
150		return NULL;
151		}
152
153		/** Find the most right leaf */
154		template <class TTreeType>
155		const typename PostOrderTreeIterator<TTreeType>::TreeNodeType*
156		PostOrderTreeIterator<TTreeType>::FindMostRightLeaf(TreeNodeType* node) const
157		{
158	IND	*while ( node->HasChildren() )
159	IND	***{
160	IND	***TreeNodeType* helpNode;
161	IND	***int childCount = node->CountChildren();
162	IND	***int i = 0;
163
164	IND	***do
165	IND	*****{
166	IND	*****helpNode = node->GetChild( i );
167	IND	*****i++;
168	IND	*****} while ( helpNode == NULL && i < childCount );
169
170		if ( helpNode == NULL )
171		{
172		return node;
173		}
174		node = helpNode;
175		}
176		return node;
177		}
178
179		/** Clone function */
180		template <class TTreeType>
181		TreeIteratorBase<TTreeType>* PostOrderTreeIterator<TTreeType>::Clone()
182		{
183	LEN	PostOrderTreeIterator<TTreeType>* clone = new PostOrderTreeIterator<TTreeType>( const_cast<TTreeType*>(this->m_Tree) );
184		*clone = *this;
185		return clone;
186		}
187
188		} // end namespace itk
189
190		#endif
191
192	EOF

---

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

© Kitware Inc.