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 itkTreeIteratorBase_hxx
19 #define itkTreeIteratorBase_hxx
20
21 #include "itkTreeChangeEvent.h"
22
23 /** There are some weird circular #include dependencies between TreeChangeEvent
24 * and TreeIteratorBase that cause the HeaderTest to fail without these forward
25 * declarations. */
26 template< typename TTreeType >
27 class ITK_TEMPLATE_EXPORT TreeNodeChangeEvent;
28
29 template< typename TTreeType >
30 class ITK_TEMPLATE_EXPORT TreeAddEvent;
31
32 template< typename TTreeType >
33 class ITK_TEMPLATE_EXPORT TreePruneEvent;
34
35 template< typename TTreeType >
36 class ITK_TEMPLATE_EXPORT TreeRemoveEvent;
37
38 namespace itk
39 {
40 /** Constructor */
41 template< typename TTreeType >
TreeIteratorBase(TTreeType * tree,const TreeNodeType * start)42 TreeIteratorBase< TTreeType >::TreeIteratorBase(TTreeType *tree, const TreeNodeType *start)
43 {
44 if ( start )
45 {
46 m_Root = start;
47 }
48 else
49 {
50 m_Root = dynamic_cast< const TreeNodeType * >( tree->GetRoot() );
51 }
52
53 m_Position = const_cast< TreeNodeType * >( m_Root );
54 m_Tree = tree;
55 m_Begin = m_Position;
56 m_End = nullptr;
57 }
58
59 /** Constructor */
60 template< typename TTreeType >
TreeIteratorBase(const TTreeType * tree,const TreeNodeType * start)61 TreeIteratorBase< TTreeType >::TreeIteratorBase(const TTreeType *tree, const TreeNodeType *start)
62 {
63 if ( start )
64 {
65 m_Root = start;
66 }
67 else
68 {
69 m_Root = const_cast< TreeNodeType * >( dynamic_cast< const TreeNodeType * >( tree->GetRoot() ) );
70 }
71 m_Position = const_cast< TreeNodeType * >( m_Root );
72 m_Tree = const_cast< TTreeType * >( tree );
73 m_Begin = m_Position;
74 m_End = nullptr;
75 }
76
77 /** Return the current value of the node */
78 template< typename TTreeType >
79 const typename TreeIteratorBase< TTreeType >::ValueType &
Get() const80 TreeIteratorBase< TTreeType >::Get() const
81 {
82 return m_Position->Get();
83 }
84
85 /** Set the current value of the node */
86 template< typename TTreeType >
87 void
Set(ValueType element)88 TreeIteratorBase< TTreeType >::Set(ValueType element)
89 {
90 // itkAssertInDebugAndIgnoreInReleaseMacro(m_Position);
91 m_Position->Set(element);
92 m_Tree->Modified();
93 m_Tree->InvokeEvent( TreeNodeChangeEvent< TTreeType >(*this) );
94 }
95
96 /** Add a value to the node. This creates a new child node */
97 template< typename TTreeType >
98 bool
Add(ValueType element)99 TreeIteratorBase< TTreeType >::Add(ValueType element)
100 {
101 if ( m_Position == nullptr && m_Root == nullptr )
102 {
103 bool returnValue = const_cast< TTreeType * >( m_Tree )->SetRoot(element);
104 // signal AddEvent for self
105 m_Root = dynamic_cast< const TreeNodeType * >( const_cast< TTreeType * >( m_Tree )->GetRoot() );
106 m_Position = const_cast< TreeNodeType * >( m_Root );
107 m_Tree->Modified();
108 m_Tree->InvokeEvent( TreeAddEvent< TTreeType >(*this) );
109 return returnValue;
110 }
111 else if ( m_Position == nullptr )
112 {
113 return false;
114 }
115
116 typename TreeNodeType::Pointer node = TreeNodeType::New();
117 node->Set(element);
118 m_Position->AddChild(node);
119 m_Tree->Modified();
120
121 // signal AddEvent for new child
122 TreeIteratorBase< TTreeType > *childIterator = Clone();
123 childIterator->m_Position = dynamic_cast< TreeNodeType * >( m_Position->GetChild( m_Position->ChildPosition(node) ) );
124 // signal "child has been added deleted"
125 m_Tree->InvokeEvent( TreeAddEvent< TTreeType >(*childIterator) );
126 delete childIterator;
127
128 return true;
129 }
130
131 /** Add a new element at a given position */
132 template< typename TTreeType >
133 bool
Add(int itkNotUsed (childPosition),ValueType element)134 TreeIteratorBase< TTreeType >::Add(int itkNotUsed(childPosition), ValueType element)
135 {
136 if ( m_Position )
137 {
138 typename TreeNodeType::Pointer node = TreeNodeType::New();
139 node->Set(element);
140 m_Position->AddChild(node);
141 m_Tree->Modified();
142
143 // signal AddEvent
144 TreeIteratorBase< TTreeType > *childIterator = Clone();
145 childIterator->m_Position = dynamic_cast< TreeNodeType * >( m_Position->GetChild( m_Position->ChildPosition(node) ) );
146 // signal "child has been added deleted"
147 m_Tree->InvokeEvent( TreeAddEvent< TTreeType >(*childIterator) );
148 delete childIterator;
149
150 return true;
151 }
152 return false;
153 }
154
155 /** Return true if the current pointed node is a leaf */
156 template< typename TTreeType >
157 bool
IsLeaf() const158 TreeIteratorBase< TTreeType >::IsLeaf() const
159 {
160 return !( m_Position->HasChildren() );
161 }
162
163 /** Return true if the current pointed node is a root */
164 template< typename TTreeType >
165 bool
IsRoot() const166 TreeIteratorBase< TTreeType >::IsRoot() const
167 {
168 if ( m_Root == nullptr )
169 {
170 return false;
171 }
172
173 if ( m_Position == m_Root )
174 {
175 return true;
176 }
177 return false;
178 }
179
180 /** Add a subtree */
181 template< typename TTreeType >
182 bool
Add(TTreeType & subTree)183 TreeIteratorBase< TTreeType >::Add(TTreeType & subTree)
184 {
185 if ( subTree.Count() == 0 )
186 {
187 return false;
188 }
189
190 if ( !subTree.GetRoot() )
191 {
192 return false;
193 }
194
195 if ( m_Root == nullptr )
196 {
197 m_Root = static_cast< const TreeNodeType * >( subTree.GetRoot() );
198 }
199 else
200 {
201 if ( m_Position == nullptr )
202 {
203 return false;
204 }
205 m_Position->AddChild( const_cast< TreeNodeType * >( static_cast< const TreeNodeType * >( subTree.GetRoot() ) ) );
206 }
207 return true;
208 }
209
210 /** Return the subtree */
211 template< typename TTreeType >
212 TTreeType *
GetSubTree() const213 TreeIteratorBase< TTreeType >::GetSubTree() const
214 {
215 typename TTreeType::Pointer tree = TTreeType::New();
216 tree->SetRoot(m_Position);
217 tree->SetSubtree(true);
218 return tree;
219 }
220
221 /** Return true of the current node has a child */
222 template< typename TTreeType >
223 bool
HasChild(int number) const224 TreeIteratorBase< TTreeType >::HasChild(int number) const
225 {
226 if ( m_Position == nullptr )
227 {
228 return false;
229 }
230 if ( m_Position->GetChild(number) != nullptr )
231 {
232 return true;
233 }
234 return false;
235 }
236
237 /** Return the current position of the child */
238 template< typename TTreeType >
239 int
ChildPosition(ValueType element) const240 TreeIteratorBase< TTreeType >::ChildPosition(ValueType element) const
241 {
242 if ( !m_Position )
243 {
244 return -1;
245 }
246 return m_Position->ChildPosition(element);
247 }
248
249 /** Remove a child */
250 template< typename TTreeType >
251 bool
RemoveChild(int number)252 TreeIteratorBase< TTreeType >::RemoveChild(int number)
253 {
254 if ( !HasChild(number) )
255 {
256 return false;
257 }
258 auto * child = dynamic_cast< TreeNodeType * >( m_Position->GetChild(number) );
259
260 if ( child != nullptr )
261 {
262 // signal PruneEvent (node plus all children are removed)
263 TreeIteratorBase< TTreeType > *childIterator = Clone();
264 childIterator->m_Position = child;
265 // signal "child has been added deleted"
266 m_Tree->InvokeEvent( TreePruneEvent< TTreeType >(*childIterator) );
267 delete childIterator;
268
269 // and really remove child (and subitems)
270 const_cast< TreeNodeType * >( m_Position )->Remove(child);
271 m_Tree->Modified();
272 return true;
273 }
274 return false;
275 }
276
277 /** Count the number of children */
278 template< typename TTreeType >
279 int
CountChildren() const280 TreeIteratorBase< TTreeType >::CountChildren() const
281 {
282 if ( m_Position == nullptr )
283 {
284 return -1;
285 }
286 return m_Position->CountChildren();
287 }
288
289 /** Return true of the pointed node has a parent */
290 template< typename TTreeType >
291 bool
HasParent() const292 TreeIteratorBase< TTreeType >::HasParent() const
293 {
294 return ( m_Position != nullptr && m_Position->GetParent() != nullptr );
295 }
296
297 /** Disconnect the tree */
298 template< typename TTreeType >
299 bool
Disconnect()300 TreeIteratorBase< TTreeType >::Disconnect()
301 {
302 if ( m_Position == nullptr )
303 {
304 return false;
305 }
306
307 if ( m_Position->HasParent() == false )
308 {
309 return false;
310 }
311
312 //keep node alive just a bit longer
313 typename TreeNodeType::Pointer position = m_Position;
314
315 auto * parent = dynamic_cast< TreeNodeType * >( m_Position->GetParent() );
316 parent->Remove( const_cast< TreeNodeType * >( m_Position ) );
317 m_Tree->Modified();
318
319 while ( m_Position->CountChildren() > 0 )
320 {
321 // always add first child in list, because AddChild() removes the added node
322 // from
323 // its former parent (== m_position)
324 auto * child = dynamic_cast< TreeNodeType * >( m_Position->GetChild(0) );
325 parent->AddChild(child);
326 }
327
328 m_Tree->InvokeEvent( TreeRemoveEvent< TTreeType >(*this) );
329
330 m_Position = nullptr;
331 return true;
332 }
333
334 /** Return the children list */
335 template< typename TTreeType >
336 TreeIteratorBase< TTreeType > *
Children()337 TreeIteratorBase< TTreeType >::Children()
338 {
339 itkGenericOutputMacro("Not implemented yet");
340 ::itk::ExceptionObject e_(__FILE__, __LINE__, "Not implemented yet", ITK_LOCATION);
341 throw e_; /* Explicit naming to work around Intel compiler bug. */
342 return nullptr;
343 }
344
345 /** Return the first parent found */
346 template< typename TTreeType >
347 const typename TreeIteratorBase< TTreeType >::TreeNodeType *
GetParent() const348 TreeIteratorBase< TTreeType >::GetParent() const
349 {
350 if ( m_Position == nullptr )
351 {
352 return nullptr;
353 }
354
355 return m_Position->GetParent();
356 }
357
358 /** Return the list of parents */
359 template< typename TTreeType >
Parents()360 TreeIteratorBase< TTreeType > *TreeIteratorBase< TTreeType >::Parents()
361 {
362 itkGenericOutputMacro("Not implemented yet");
363 ::itk::ExceptionObject e_(__FILE__, __LINE__, "Not implemented yet", ITK_LOCATION);
364 throw e_; /* Explicit naming to work around Intel compiler bug. */
365 return nullptr;
366 }
367
368 /** Go to a child */
369 template< typename TTreeType >
GoToChild(ChildIdentifier number)370 bool TreeIteratorBase< TTreeType >::GoToChild(ChildIdentifier number)
371 {
372 if ( m_Position == nullptr )
373 {
374 return false;
375 }
376
377 auto * next = dynamic_cast< TreeNodeType * >( m_Position->GetChild(number) );
378
379 if ( next == nullptr )
380 {
381 return false;
382 }
383 m_Position = next;
384 return true;
385 }
386
387 /** Go to a parent */
388 template< typename TTreeType >
GoToParent()389 bool TreeIteratorBase< TTreeType >::GoToParent()
390 {
391 if ( m_Position == nullptr )
392 {
393 return false;
394 }
395
396 if ( !m_Position->HasParent() )
397 {
398 return false;
399 }
400
401 m_Position = dynamic_cast< TreeNodeType * >( m_Position->GetParent() );
402 return true;
403 }
404
405 /** Get a child given a number */
406 template< typename TTreeType >
GetChild(int number) const407 TreeIteratorBase< TTreeType > *TreeIteratorBase< TTreeType >::GetChild(int number) const
408 {
409 if ( !m_Position )
410 {
411 return nullptr;
412 }
413
414 auto * child = dynamic_cast< TreeNodeType * >( m_Position->GetChild(number) );
415
416 if ( !child )
417 {
418 return nullptr;
419 }
420 // return new WalkTreeIterator<ValueType,P>( child, m_Root, m_Tree, getType()
421 // );
422 return nullptr;
423 }
424
425 /** Count the number of nodes from the beginning */
426 template< typename TTreeType >
Count()427 int TreeIteratorBase< TTreeType >::Count()
428 {
429 int size = 0;
430
431 this->GoToBegin();
432 if ( !m_Position->HasChildren() )
433 {
434 return 0;
435 }
436 while ( this->Next() )
437 {
438 size++;
439 }
440 return size;
441 }
442
443 /** Get the node pointed by the iterator */
444 template< typename TTreeType >
445 typename TreeIteratorBase< TTreeType >::TreeNodeType *
GetNode()446 TreeIteratorBase< TTreeType >::GetNode()
447 {
448 return const_cast< TreeNodeType * >( m_Position );
449 }
450
451 /** Get the node pointed by the iterator */
452 template< typename TTreeType >
453 const typename TreeIteratorBase< TTreeType >::TreeNodeType *
GetNode() const454 TreeIteratorBase< TTreeType >::GetNode() const
455 {
456 return m_Position;
457 }
458
459 /** Get the root */
460 template< typename TTreeType >
461 typename TreeIteratorBase< TTreeType >::TreeNodeType *
GetRoot()462 TreeIteratorBase< TTreeType >::GetRoot()
463 {
464 return const_cast< TreeNodeType * >( m_Root );
465 }
466
467 /** Get the root (const) */
468 template< typename TTreeType >
469 const typename TreeIteratorBase< TTreeType >::TreeNodeType *
GetRoot() const470 TreeIteratorBase< TTreeType >::GetRoot() const
471 {
472 return m_Root;
473 }
474
475 /** Remove a specific node (and its child nodes!) */
476 template< typename TTreeType >
477 bool
Remove()478 TreeIteratorBase< TTreeType >::Remove()
479 {
480 if ( m_Position == nullptr )
481 {
482 return false;
483 }
484
485 //keep node alive just a bit longer (for the notification)
486 typename TreeNodeType::Pointer position = m_Position;
487
488 if ( m_Position->HasParent() )
489 {
490 TreeNodeType *parent = m_Position->GetParent();
491 // removes this node (and implicitly all children, too)
492 parent->Remove(m_Position);
493 }
494 else if ( m_Root == m_Position )
495 {
496 m_Root = nullptr;
497 m_Tree->SetRoot( (TreeNodeType *)nullptr );
498 // this won't do anything if root is already != nullptr ==> root cannot be
499 // removed
500 }
501
502 m_Position->SetParent(nullptr); // we don't have a parent anymore
503 m_Tree->InvokeEvent( TreePruneEvent< TTreeType >(*this) );
504 while ( m_Position->CountChildren() > 0 ) // remove all children
505 {
506 //always remove first child (id 0)
507 auto * child = dynamic_cast< TreeNodeType * >( m_Position->GetChild(0) );
508 m_Position->Remove(child);
509 }
510
511 position = nullptr;
512 m_Position = nullptr; // Smart pointer, deletes *m_Position
513
514 m_Tree->Modified();
515
516 return true;
517 }
518
519 /** Return the tree */
520 template< typename TTreeType >
521 TTreeType *
GetTree() const522 TreeIteratorBase< TTreeType >::GetTree() const
523 {
524 return m_Tree;
525 }
526 } // namespace itk
527
528 #endif
529