ITK  5.1.0
Insight Toolkit
Examples/DataRepresentation/Containers/TreeContainer.cxx
/*=========================================================================
*
* Copyright Insight Software Consortium
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0.txt
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
*=========================================================================*/
// Software Guide : BeginLatex
//
// \index{itk::TreeContainer}
//
// This example demonstrates use of the \doxygen{TreeContainer} class and
// associated \code{TreeIterator}s.
// \code{TreeContainer} implements the notion of a tree, which is a branching
// data structure composed of nodes and edges, where the edges indicate
// a parent/child relationship between nodes. Each node may have exactly one
// parent, except for the root node, which has none. A tree must have
// exactly one root node, and a node may not be its own parent. To round out
// the vocabulary used to discuss this data structure, two nodes
// sharing the same parent node are called ``siblings,'' a childless node
// is termed a ``leaf,'' and a ``forest'' is a collection of disjoint trees.
// Note that in the present implementation, it is the user's responsibility
// to enforce these relationships, as no checking is done to ensure a
// cycle-free tree. \code{TreeContainer} is templated over the type of node,
// affording the user great flexibility in using the structure for their
// particular problem.
//
// Let's begin by including the appropriate header files.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
// Software Guide : EndCodeSnippet
int
main(int, char *[])
{
// Software Guide : BeginLatex
//
// We first instantiate a tree with \code{int} node type.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
using NodeType = int;
using TreeType = itk::TreeContainer<NodeType>;
TreeType::Pointer tree = TreeType::New();
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// Next we set the value of the root node using \code{SetRoot()}.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
tree->SetRoot(0);
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// Nodes may be added to the tree using the \code{Add()} method,
// where the first argument is the value of the new node, and the second
// argument is the value of the parent node.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
tree->Add(1, 0);
tree->Add(2, 0);
tree->Add(3, 0);
tree->Add(4, 2);
tree->Add(5, 2);
tree->Add(6, 5);
tree->Add(7, 1);
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// If two nodes have the same value, it is ambiguous which node is intended
// to be the parent of the new node; in this case, the first node with that
// value is selected. As will be demonstrated shortly, this ambiguity can be avoided
// by constructing the tree with \code{TreeIterator}s.
//
// Let's begin by defining a \doxygen{ChildTreeIterator}.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// Before discussing the particular features of this iterator, however, we will
// illustrate features common to all \code{TreeIterator}s, which inherit
// from \doxygen{TreeIteratorBase}. Basic use follows the convention of other
// iterators in ITK, relying on the \code{GoToBegin()} and \code{IsAtEnd()} methods.
// The iterator is advanced using the prefix increment \code{++} operator,
// whose behavior naturally depends on the particular iterator being used.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
for (childIt.GoToBegin(); !childIt.IsAtEnd(); ++childIt)
{
std::cout << childIt.Get() << std::endl;
}
std::cout << std::endl;
// Software Guide : EndCodeSnippet
childIt.GoToBegin();
// Software Guide : BeginLatex
//
// Note that, though not illustrated here, trees may also be traversed using
// the \code{GoToParent()} and \code{GoToChild()} methods.
//
// \code{TreeIterator}s have a number of useful functions for testing properties
// of the current node. For example, \code{GetType()} returns an enumerated type
// corresponding to the type of the particular iterator being used. These types
// are as follows:
//
// \code{UNDEFIND}, \code{PREORDER}, \code{INORDER}, \code{POSTORDER},
// \code{LEVELORDER}, \code{CHILD}, \code{ROOT}, and \code{LEAF}.
//
// In the following snippet, we test whether the iterator is of type \code{CHILD},
// and return from the program indicating failure if the test returns \code{false}.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
{
std::cerr << "Error: The iterator was not of type CHILD." << std::endl;
return EXIT_FAILURE;
}
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// The value associated with the node can be retrieved and modified using
// \code{Get()} and \code{Set()} methods:
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
int oldValue = childIt.Get();
std::cout << "The node's value is " << oldValue << std::endl;
int newValue = 2;
childIt.Set(newValue);
std::cout << "Now, the node's value is " << childIt.Get() << std::endl;
// Software Guide : EndCodeSnippet
childIt.Set(oldValue);
// Software Guide : BeginLatex
//
// A number of member functions are defined allowing the user to query
// information about the current node's parent/child relationships:
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
std::cout << "Is this a leaf node? " << childIt.IsLeaf() << std::endl;
std::cout << "Is this the root node? " << childIt.IsRoot() << std::endl;
std::cout << "Does this node have a parent? " << childIt.HasParent() << std::endl;
std::cout << "How many children does this node have? " << childIt.CountChildren()
<< std::endl;
std::cout << "Does this node have a child 1? " << childIt.HasChild(1) << std::endl;
// Software Guide : EndCodeSnippet
std::cout << std::endl;
// Software Guide : BeginLatex
//
// In addition to traversing the tree and querying for information,
// \code{TreeIterator}s can alter the structure of the tree itself. For example, a
// node can be added using the \code{Add()} methods, child nodes can be removed using
// the \code{RemoveChild()} method, and the current node can be removed using the
// \code{Remove()} method. Each of these methods returns a bool indicating whether
// the alteration was successful.
//
// To illustrate this, in the following snippet we clear the tree of all nodes, and
// then repopulate it using the iterator.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
tree->Clear();
it.GoToBegin();
it.Add(0);
it.Add(1);
it.Add(2);
it.Add(3);
it.GoToChild(2);
it.Add(4);
it.Add(5);
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// Every \code{TreeIterator} has a \code{Clone()} function which returns
// a copy of the current iterator. Note that the user should delete
// the created iterator by hand.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
itk::TreeIteratorBase<TreeType> * childItClone = childIt.Clone();
delete childItClone;
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// Alternatively, \doxygen{TreeIteratorClone} can be used to create a generic copy of
// an iterator.
//
// Software Guide : EndLatex
// Software Guide : BeginCodeSnippet
using IteratorType = itk::TreeIteratorBase<TreeType>;
using IteratorCloneType = itk::TreeIteratorClone<IteratorType>;
IteratorCloneType anotherChildItClone = childIt;
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// We now turn our attention to features of the specific \code{TreeIterator}
// specializations. \code{ChildTreeIterator}, for example, provides a way
// to iterate through all the children of a node.
//
// Software Guide : EndLatex
std::cout << "ChildTreeIterator:" << std::endl;
// Software Guide : BeginCodeSnippet
for (childIt.GoToBegin(); !childIt.IsAtEnd(); ++childIt)
{
std::cout << childIt.Get();
}
std::cout << std::endl;
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// The \doxygen{LeafTreeIterator} iterates through the leaves of the tree.
//
// Software Guide : EndLatex
std::cout << "LeafTreeIterator:" << std::endl;
// Software Guide : BeginCodeSnippet
for (leafIt.GoToBegin(); !leafIt.IsAtEnd(); ++leafIt)
{
std::cout << leafIt.Get() << std::endl;
}
std::cout << std::endl;
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
// \doxygen{LevelOrderTreeIterator} takes three arguments in its constructor:
// the tree to be traversed, the maximum depth (or `level'), and the starting node.
// Naturally, this iterator provides a method for returning the current level.
//
// Software Guide : EndLatex
std::cout << "LevelOrderTreeIterator:" << std::endl;
// Software Guide : BeginCodeSnippet
itk::LevelOrderTreeIterator<TreeType> levelIt(tree, 10, tree->GetNode(0));
for (levelIt.GoToBegin(); !levelIt.IsAtEnd(); ++levelIt)
{
std::cout << levelIt.Get() << " (" << levelIt.GetLevel() << ")" << std::endl;
}
std::cout << std::endl;
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// \doxygen{InOrderTreeIterator} iterates through the tree
// from left to right.
//
// Software Guide : EndLatex
std::cout << "InOrderTreeIterator:" << std::endl;
// Software Guide : BeginCodeSnippet
for (inOrderIt.GoToBegin(); !inOrderIt.IsAtEnd(); ++inOrderIt)
{
std::cout << inOrderIt.Get() << std::endl;
}
std::cout << std::endl;
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// \doxygen{PreOrderTreeIterator} iterates through the tree
// from left to right but do a depth first search.
//
// Software Guide : EndLatex
std::cout << "PreOrderTreeIterator:" << std::endl;
// Software Guide : BeginCodeSnippet
for (preOrderIt.GoToBegin(); !preOrderIt.IsAtEnd(); ++preOrderIt)
{
std::cout << preOrderIt.Get() << std::endl;
}
std::cout << std::endl;
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// The \doxygen{PostOrderTreeIterator} iterates through the tree
// from left to right but goes from the leaves to the root in the search.
//
// Software Guide : EndLatex
std::cout << "PostOrderTreeIterator:" << std::endl;
// Software Guide : BeginCodeSnippet
for (postOrderIt.GoToBegin(); !postOrderIt.IsAtEnd(); ++postOrderIt)
{
std::cout << postOrderIt.Get() << std::endl;
}
std::cout << std::endl;
// Software Guide : EndCodeSnippet
// Software Guide : BeginLatex
//
// The \doxygen{RootTreeIterator} goes from one node to the
// root. The second arguments is the starting node. Here we go from the leaf
// node (value = 6) up to the root.
//
// Software Guide : EndLatex
std::cout << "RootTreeIterator:" << std::endl;
// Software Guide : BeginCodeSnippet
itk::RootTreeIterator<TreeType> rootIt(tree, tree->GetNode(4));
for (rootIt.GoToBegin(); !rootIt.IsAtEnd(); ++rootIt)
{
std::cout << rootIt.Get() << std::endl;
}
std::cout << std::endl;
// Software Guide : EndCodeSnippet
return EXIT_SUCCESS;
}
itk::ChildTreeIterator
Definition: itkChildTreeIterator.h:26
itk::TreeIteratorClone
Definition: itkTreeIteratorClone.h:32
itk::TreeIteratorBase::GoToChild
virtual bool GoToChild(ChildIdentifier number=0)
itk::TreeIteratorBase::Get
virtual const ValueType & Get() const
itk::PostOrderTreeIterator
Definition: itkPostOrderTreeIterator.h:26
itk::TreeIteratorBase::IsRoot
virtual bool IsRoot() const
itkPostOrderTreeIterator.h
itkInOrderTreeIterator.h
itk::TreeIteratorBase::Add
virtual bool Add(ValueType element)
itkRootTreeIterator.h
itk::TreeIteratorBase::IsLeaf
virtual bool IsLeaf() const
itkLevelOrderTreeIterator.h
itkTreeContainer.h
itkTreeIteratorClone.h
itk::LeafTreeIterator
Definition: itkLeafTreeIterator.h:26
itk::TreeIteratorBase::HasChild
virtual bool HasChild(int number=0) const
itk::TreeIteratorBase
This class provides the base implementation for tree iterators.
Definition: itkTreeIteratorBase.h:58
itk::TreeIteratorBaseNodeEnum::CHILD
itk::PreOrderTreeIterator
Definition: itkPreOrderTreeIterator.h:30
itk::ChildTreeIterator::Clone
TreeIteratorBase< TTreeType > * Clone() override
itk::LevelOrderTreeIterator
Iterate over a tree in level order.
Definition: itkLevelOrderTreeIterator.h:34
itk::TreeIteratorBase::IsAtEnd
bool IsAtEnd() const
Definition: itkTreeIteratorBase.h:215
itkChildTreeIterator.h
itk::TreeIteratorBase::HasParent
virtual bool HasParent() const
itk::ChildTreeIterator::GetType
NodeType GetType() const override
itk::TreeIteratorBase::GoToBegin
void GoToBegin()
Definition: itkTreeIteratorBase.h:194
itk::TreeIteratorBase::CountChildren
virtual int CountChildren() const
itk::InOrderTreeIterator
Definition: itkInOrderTreeIterator.h:26
itkLeafTreeIterator.h
itk::TreeIteratorBase::Set
void Set(ValueType element)
itk::RootTreeIterator
Definition: itkRootTreeIterator.h:26
itk::TreeContainer
A tree container.
Definition: itkTreeContainer.h:38