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 itkTreeContainer_hxx
19 #define itkTreeContainer_hxx
20
21 #include "itkTreeContainer.h"
22
23 namespace itk
24 {
25 /** Constructor */
26 template< typename TValue >
TreeContainer()27 TreeContainer< TValue >::TreeContainer()
28 {
29 m_Root = nullptr;
30 this->SetSubtree(false);
31 m_DefaultChildrenCount = 2;
32 }
33
34 /** Constructor with default children count */
35 template< typename TValue >
TreeContainer(int dcc)36 TreeContainer< TValue >::TreeContainer(int dcc)
37 {
38 m_Root = nullptr;
39 this->SetSubtree(false);
40 m_DefaultChildrenCount = dcc;
41 }
42
43 /** Constructor by adding a tree */
44 template< typename TValue >
TreeContainer(TreeContainer<TValue> &)45 TreeContainer< TValue >::TreeContainer(TreeContainer< TValue > & )
46 {
47 m_Root = nullptr;
48 this->SetSubtree(false);
49 m_DefaultChildrenCount = 3;
50 }
51
52 /** Set the root of the tree */
53 template< typename TValue >
54 bool
SetRoot(const TValue element)55 TreeContainer< TValue >::SetRoot(const TValue element)
56 {
57 m_Root = TreeNodeType::New();
58 m_Root->Set(element);
59 m_Root->SetParent(nullptr);
60 return true;
61 }
62
63 /** Set the root of the tree */
64 template< typename TValue >
65 bool
SetRoot(TreeNode<TValue> * node)66 TreeContainer< TValue >::SetRoot(TreeNode< TValue > *node)
67 {
68 m_Root = node;
69 return true;
70 }
71
72 /** Count the number of nodes in the tree */
73 template< typename TValue >
74 int
Count() const75 TreeContainer< TValue >::Count() const
76 {
77 if ( !m_Root )
78 {
79 return 0;
80 }
81 int size = 0;
82 PreOrderTreeIterator< Self > it(this, this->m_Root);
83 it.GoToBegin();
84 while ( !it.IsAtEnd() )
85 {
86 size++;
87 ++it;
88 }
89 return size;
90 }
91
92 /** Swap the iterators */
93 template< typename TValue >
94 bool
Swap(IteratorType & v,IteratorType & w)95 TreeContainer< TValue >::Swap(IteratorType & v, IteratorType & w)
96 {
97 TreeNode< TValue > *nv = v.GetNode();
98 TreeNode< TValue > *nw = w.GetNode();
99
100 if ( nv == nullptr || nw == nullptr )
101 {
102 return false;
103 }
104 TreeNode< TValue > *pv = nv->GetParent();
105 TreeNode< TValue > *pw = nw->GetParent();
106
107 if ( pv == nullptr && pw == nullptr )
108 {
109 return false;
110 }
111 else if ( pv == nullptr )
112 {
113 pw->ReplaceChild(nw, nv);
114 m_Root = nw;
115 }
116 else if ( pw == nullptr )
117 {
118 pv->ReplaceChild(nv, nw);
119 m_Root = nv;
120 }
121 else
122 {
123 pv->ReplaceChild(nv, nw);
124 pw->ReplaceChild(nw, nv);
125 }
126
127 nv->SetParent(pw);
128 nw->SetParent(pv);
129
130 return true;
131 }
132
133 /** Return true if the tree contains this element */
134 template< typename TValue >
135 bool
Contains(const TValue element)136 TreeContainer< TValue >::Contains(const TValue element)
137 {
138 PreOrderTreeIterator< Self > it(this, m_Root);
139 it.GoToBegin();
140 while ( !it.IsAtEnd() )
141 {
142 if ( it.Get() == element )
143 {
144 return true;
145 }
146 ++it;
147 }
148 return false;
149 }
150
151 /** Equal operator */
152 template< typename TValue >
153 bool
operator ==(TreeContainer<TValue> & tree)154 TreeContainer< TValue >::operator==(TreeContainer< TValue > & tree)
155 {
156 PreOrderTreeIterator< Self > it(this, m_Root);
157 it.GoToBegin();
158 PreOrderTreeIterator< Self > it2( &tree, tree.GetRoot() );
159 it2.GoToBegin();
160
161 while ( ( !it.IsAtEnd() ) && ( !it2.IsAtEnd() ) )
162 {
163 if ( it.Get() != it2.Get() )
164 {
165 return false;
166 }
167 ++it;
168 ++it2;
169 }
170
171 return true;
172 }
173
174 /** Return true if the given element is a leaf of the tree */
175 template< typename TValue >
176 bool
IsLeaf(TValue element)177 TreeContainer< TValue >::IsLeaf(TValue element)
178 {
179 PreOrderTreeIterator< Self > it(this, m_Root);
180 it.GoToBegin();
181 while ( !it.IsAtEnd() )
182 {
183 if ( it.Get() == element )
184 {
185 if ( it.IsLeaf() )
186 {
187 return true;
188 }
189 else
190 {
191 return false;
192 }
193 }
194 }
195 return false;
196 }
197
198 /** Return true of the node containing the element is the root */
199 template< typename TValue >
200 bool
IsRoot(TValue element)201 TreeContainer< TValue >::IsRoot(TValue element)
202 {
203 PreOrderTreeIterator< Self > it(this, m_Root);
204 it.GoToBegin();
205 while ( !it.IsAtEnd() )
206 {
207 if ( it.Get() == element )
208 {
209 if ( !it.HasParent() )
210 {
211 return true;
212 }
213 else
214 {
215 return false;
216 }
217 }
218 ++it;
219 }
220 return false;
221 }
222
223 /** Clear the tree */
224 template< typename TValue >
Clear()225 bool TreeContainer< TValue >::Clear()
226 {
227 PreOrderTreeIterator< Self > it(this, m_Root);
228 bool success = it.Remove();
229 m_Root = nullptr;
230 return success;
231 }
232
233 /** Get node given a value */
234 template< typename TValue >
235 const TreeNode< TValue > *
GetNode(TValue val) const236 TreeContainer< TValue >::GetNode(TValue val) const
237 {
238 PreOrderTreeIterator< Self > it(this, m_Root);
239 it.GoToBegin();
240 while ( !it.IsAtEnd() )
241 {
242 if ( it.Get() == val )
243 {
244 return it.GetNode();
245 }
246 ++it;
247 }
248 return nullptr;
249 }
250
251 /** Set the root of the tree from the iterator position */
252 template< typename TValue >
253 bool
SetRoot(IteratorType & pos)254 TreeContainer< TValue >::SetRoot(IteratorType & pos)
255 {
256 if ( this->m_SubTree )
257 {
258 return false;
259 }
260 TreeNode< TValue > *node = pos.GetNode();
261 if ( node == nullptr )
262 {
263 return false;
264 }
265
266 TreeNode< TValue > *parent = node->GetParent();
267 TreeNode< TValue > *help = nullptr;
268
269 if ( parent == nullptr )
270 {
271 return false;
272 }
273
274 m_Root = node;
275 node->AddChild(parent);
276 parent->Remove(node);
277 node->SetParent(nullptr);
278 help = parent->GetParent();
279 parent->SetParent(node);
280 node = parent;
281
282 while ( help != nullptr )
283 {
284 parent = help;
285 help = help->GetParent();
286 node->AddChild(parent);
287 parent->Remove(node);
288 parent->SetParent(node);
289 node = parent;
290 }
291 return true;
292 }
293
294 /** Add a child to a given parent */
295 template< typename TValue >
296 bool
Add(const TValue child,const TValue parent)297 TreeContainer< TValue >::Add(const TValue child, const TValue parent)
298 {
299 if ( !m_Root )
300 {
301 std::cout << "TreeContainer<TValue>::Add() : The tree is empty" << std::endl;
302 return false;
303 }
304 // Find the first node in the tree that has the parent value
305 PreOrderTreeIterator< Self > it(this, m_Root);
306 it.GoToBegin();
307 while ( !it.IsAtEnd() )
308 {
309 if ( it.Get() == parent )
310 {
311 it.Add(child);
312 return true;
313 }
314 ++it;
315 }
316 return false;
317 }
318
319 /** Print self */
320 template< typename TValue >
321 void
PrintSelf(std::ostream & os,Indent indent) const322 TreeContainer< TValue >::PrintSelf(std::ostream & os, Indent indent) const
323 {
324 Superclass::PrintSelf(os, indent);
325 os << indent << "Number of objects = " << this->Count() << std::endl;
326
327 if ( this->Count() > 0 )
328 {
329 os << indent << "Tree:" << std::endl;
330 // Now prints the tree
331 PreOrderTreeIterator< Self > it(this, m_Root);
332 it.GoToBegin();
333 while ( !it.IsAtEnd() )
334 {
335 if ( it.GetParent() )
336 {
337 std::cout << it.GetParent()->Get() << " <- ";
338 }
339 std::cout << it.Get() << std::endl;
340 ++it;
341 }
342 }
343 }
344 } // namespace itk
345
346 #endif
347