3.8.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:

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::io::cout() << 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::io::cout() << FCPPT_TEXT("Is the tree empty? ") << tree.empty() << FCPPT_TEXT('\n');
// Outputs 3
fcppt::io::cout() << FCPPT_TEXT("How many children does the tree have: ") << tree.size()
<< FCPPT_TEXT('\n');
// Outputs: hello world
fcppt::io::cout() << 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)
{
fcppt::io::cout() << item.value() << FCPPT_TEXT('\n');
}
fcppt::optional::maybe_void(tree.front(), [](fcppt::reference<string_tree> const _first_child) {
fcppt::io::cout() << 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:

// 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 : fcppt::container::tree::pre_order<string_tree const>(tree))
{
fcppt::io::cout() << item.value() << std::endl;
}

Aside from fcppt::container::tree::pre_order 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::is_object< 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...
 
template<typename Ch , typename Traits , typename Value >
std::basic_ostream< Ch, Traits > & fcppt::container::tree::operator<< (std::basic_ostream< Ch, Traits > &_stream, fcppt::container::tree::object< Value > const &_tree)
 Outputs a 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.

◆ operator<<()

template<typename Ch , typename Traits , typename Value >
std::basic_ostream<Ch, Traits>& fcppt::container::tree::operator<< ( std::basic_ostream< Ch, Traits > &  _stream,
fcppt::container::tree::object< Value > const &  _tree 
)

Outputs a tree.