2.10.0
Freundlich's C++ toolkit
Classes | Functions
fcppt.container.tree

Description

A tree data structure.

Introduction

An fcppt::container::tree::object<T> is a container modeling a tree of arbitrary arity where nodes are labelled by objects of type T and its children are of type fcppt::container::tree::object<T>. Internally, an fcppt::container::tree::object<T> holds a std::list of fcppt::container::tree::object<T>.

Here is an example:

typedef
>
string_tree;
string_tree tree(
FCPPT_TEXT("hello")
);
// Immediately change the value
tree.value(
tree.value() + FCPPT_TEXT(" world")
);
// The tree is empty since it has no children
<< FCPPT_TEXT("Is the tree empty? ")
<< tree.empty()
<< FCPPT_TEXT('\n');
{
// Adding two items by moving
string_tree child1(
FCPPT_TEXT("blubb")
);
tree.push_back(
std::move(
child1
)
);
string_tree child2(
FCPPT_TEXT("blah")
);
tree.push_back(
std::move(
child2
)
);
}
// adding "by value"
tree.push_back(
FCPPT_TEXT("foobar")
);
// Now the tree isn't empty anymore
<< FCPPT_TEXT("Is the tree empty? ")
<< tree.empty()
<< FCPPT_TEXT('\n');
// Outputs 3
<< FCPPT_TEXT("How many children does the tree have: ")
<< tree.size()
<< FCPPT_TEXT('\n');
// Outputs: hello world
<< FCPPT_TEXT("The tree value is: ")
<< tree.value()
<< FCPPT_TEXT('\n');
// Output the first level of the tree below the root.
// Note that iterator::value_type is string_tree.
for(
string_tree const &item
:
tree
)
<< item.value()
<< FCPPT_TEXT('\n');
tree.front(),
[](
string_tree
> const _first_child
)
{
<< FCPPT_TEXT("First child has a parent: ")
<< _first_child.get().parent().has_value()
<< FCPPT_TEXT('\n');
}
);

Iterators/Traversals

A tree can be used as a range by using begin and end to iterate over its children.

There are also traversal classes that can be used to iterate over the whole tree. Here is an example:

> string_tree;
// Create a tree, insert 5 elements below the root
string_tree tree(
FCPPT_TEXT("hello")
);
tree.push_back(
FCPPT_TEXT("foo")
);
tree.push_back(
FCPPT_TEXT("bar")
);
tree.push_back(
FCPPT_TEXT("baz")
);
tree.front().get_unsafe().get().push_back(
FCPPT_TEXT("qux")
);
// Create a traversal and "attach" it to the tree in the ctor
// Then use it like a forward-iterable container!
// This outputs:
//
// hello, foo, qux, bar, baz
for(
string_tree const &item
:
string_tree const
>(
tree
)
)
<< item.value()
<< std::endl;

Aside from pre_order , no other traversals are implemented as of yet.

Classes

struct  fcppt::container::tree::is_object< T >
 A meta function testing if the given type is really a tree object. More...
 
struct  fcppt::container::tree::object< T >>
 A meta function testing if the given type is really a tree object. More...
 
class  fcppt::container::tree::object< T >
 A tree data structure. More...
 
class  fcppt::container::tree::pre_order< Tree >
 Wraps a tree to make it iterable in a pre-order fashion. More...
 

Functions

template<typename Value >
fcppt::container::tree::object< Value >::size_type fcppt::container::tree::level (fcppt::container::tree::object< Value > const &_tree)
 Calculates the level of a tree. More...
 
template<typename Tree >
fcppt::container::tree::pre_order< Tree > fcppt::container::tree::make_pre_order (Tree &_tree)
 Creates a pre_order object. More...
 
template<typename Tree >
fcppt::container::tree::to_root< Tree > fcppt::container::tree::make_to_root (Tree &_tree)
 Creates a to_root object. More...
 
template<typename Result , typename Value , typename Function >
Result fcppt::container::tree::map (fcppt::container::tree::object< Value > const &_tree, Function const &_function)
 Maps a tree to another tree. More...
 

Function Documentation

◆ level()

template<typename Value >
fcppt::container::tree::object< Value>::size_type fcppt::container::tree::level ( fcppt::container::tree::object< Value > const &  _tree)

Calculates the level of a tree.

Calculates the level of _tree. A node without a parent has level 0. A node with a parent has the level of its parent plus one.

◆ make_pre_order()

template<typename Tree >
fcppt::container::tree::pre_order< Tree> fcppt::container::tree::make_pre_order ( Tree &  _tree)
inline

Creates a pre_order object.

◆ make_to_root()

template<typename Tree >
fcppt::container::tree::to_root< Tree> fcppt::container::tree::make_to_root ( Tree &  _tree)
inline

Creates a to_root object.

◆ map()

template<typename Result , typename Value , typename Function >
Result fcppt::container::tree::map ( fcppt::container::tree::object< Value > const &  _tree,
Function const &  _function 
)

Maps a tree to another tree.

Maps _tree to another tree using _function.