ITK  4.2.0
Insight Segmentation and Registration Toolkit
itkPreOrderTreeIterator.h
Go to the documentation of this file.
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 __itkPreOrderTreeIterator_h
19 #define __itkPreOrderTreeIterator_h
20 
21 #include "itkTreeIteratorBase.h"
22 
23 namespace itk
24 {
25 template< class TTreeType >
26 class PreOrderTreeIterator:public TreeIteratorBase< TTreeType >
27 {
28 public:
29 
31  typedef typename TTreeType::ValueType ValueType;
34  typedef typename Superclass::NodeType NodeType;
35 
37  PreOrderTreeIterator(const TTreeType *tree, const TreeNodeType *start = NULL);
38 
40  NodeType GetType() const;
41 
44 
45 protected:
47  const ValueType & Next();
48 
50  bool HasNext() const;
51 
52 private:
53 
55  const TreeNodeType * FindNextNode() const;
56 };
57 
59 template< class TTreeType >
61  TreeIteratorBase< TTreeType >(tree, start)
62 {}
63 
65 template< class TTreeType >
68 {
70 }
71 
73 template< class TTreeType >
74 bool
76 {
77  if ( const_cast< TreeNodeType * >( FindNextNode() ) != NULL )
78  {
79  return true;
80  }
81  return false;
82 }
84 
86 template< class TTreeType >
89 {
90  this->m_Position = const_cast< TreeNodeType * >( FindNextNode() );
91  return this->m_Position->Get();
92 }
94 
96 template< class TTreeType >
99 {
100  if ( this->m_Position == NULL )
101  {
102  return NULL;
103  }
104  if ( this->m_Position->HasChildren() )
105  {
106  return dynamic_cast< const TreeNodeType * >( this->m_Position->GetChild(0) );
107  }
109 
110  if ( !this->m_Position->HasParent() )
111  {
112  return NULL;
113  }
114 
115  TreeNodeType *child = this->m_Position;
116  TreeNodeType *parent = dynamic_cast< TreeNodeType * >( this->m_Position->GetParent() );
117 
118  // Are we a subtree? Then we are done.
119  if ( parent && parent->ChildPosition(this->m_Root) >= 0 )
120  {
121  return NULL;
122  }
123 
124  int childPosition = parent->ChildPosition(child);
125  int lastChildPosition = parent->CountChildren() - 1;
126 
127  while ( childPosition < lastChildPosition )
128  {
129  TreeNodeType *help = dynamic_cast< TreeNodeType * >( parent->GetChild(childPosition + 1) );
130 
131  if ( help != NULL )
132  {
133  return help;
134  }
135  childPosition++;
136  }
137 
138  while ( parent->HasParent() )
139  {
140  child = parent;
141  parent = dynamic_cast< TreeNodeType * >( parent->GetParent() );
142 
143  // Subtree
144  if ( parent->ChildPosition(this->m_Root) >= 0 )
145  {
146  return NULL;
147  }
148 
149  childPosition = parent->ChildPosition(child);
150  lastChildPosition = parent->CountChildren() - 1;
151 
152  while ( childPosition < lastChildPosition )
153  {
154  TreeNodeType *help = dynamic_cast< TreeNodeType * >( parent->GetChild(childPosition + 1) );
155 
156  if ( help != NULL )
157  {
158  return help;
159  }
160  }
161  }
162  return NULL;
163 }
164 
166 template< class TTreeType >
168 {
169  PreOrderTreeIterator< TTreeType > *clone = new PreOrderTreeIterator< TTreeType >(this->m_Tree, this->m_Position);
170  *clone = *this;
171  return clone;
172 }
173 } // end namespace itk
175 
176 #endif
177