fcppt.container.tree

Description

A tree data structure.

Introduction Iterators/Traversals

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:

  using string_tree = fcppt::container::tree::object<std::string>;
 
  string_tree tree{"hello"};
 
  // Immediately change the value
  tree.value(tree.value() + " world");
 
  // The tree is empty since it has no children
  std::cout << "Is the tree empty? " << tree.empty() << '\n';
 
  {
    // Adding two items by moving
    string_tree child1{"blubb"};
 
    tree.push_back(std::move(child1));
 
    string_tree child2{"blah"};
 
    tree.push_back(std::move(child2));
  }
 
  // adding "by value"
  tree.push_back("foobar");
 
  // Now the tree isn't empty anymore
  std::cout << "Is the tree empty? " << tree.empty() << '\n';
 
  // Outputs 3
  std::cout << "How many children does the tree have: " << tree.size() << '\n';
 
  // Outputs: hello world
  std::cout << "The tree value is: " << tree.value() << '\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)
  {
    std::cout << item.value() << '\n';
  }
 
  fcppt::optional::maybe_void(
      tree.front(),
      [](fcppt::reference<string_tree> const _first_child) {
        std::cout << "First child has a parent: " << _first_child.get().parent().has_value()
                  << '\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:

  using string_tree = fcppt::container::tree::object<std::string>;
 
  // Create a tree, insert 5 elements below the root
  string_tree tree{"hello"};
 
  tree.push_back("foo");
 
  tree.push_back("bar");
 
  tree.push_back("baz");
 
  tree.front().get_unsafe().get().push_back("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))
  {
    std::cout << item.value() << '\n';
  }

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 T >
fcppt::optional::object< fcppt::container::to_iterator_type< T > >	fcppt::container::tree::child_position (T &_parent, T &_child)
	Returns an iterator pointing to the position in the parent's child container where this object resides.
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.
template<typename Tree >
fcppt::container::tree::pre_order< Tree >	fcppt::container::tree::make_pre_order (Tree &_tree)
	Creates a pre_order object.
template<typename Tree >
fcppt::container::tree::to_root< Tree >	fcppt::container::tree::make_to_root (Tree &_tree)
	Creates a to_root object.
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.
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.

Function Documentation

child_position()

template<typename T >

fcppt::optional::object< fcppt::container::to_iterator_type< T > > fcppt::container::tree::child_position	(	T &	_parent,
		T &	_child )

Returns an iterator pointing to the position in the parent's child container where this object resides.

Parameters

_parent	The parent tree to search
_child	The child to search for

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.