A templated class for directed rooted trees. More...

#include <Tree.h>

Collaboration diagram for DRAIN_TREE_NAME< T, EXCLUSIVE, P >:

Public Types
typedef drain::DRAIN_TREE_NAME< T, EXCLUSIVE, P >	tree_t

typedef T	node_data_t

typedef P	path_t

typedef path_t::elem_t	key_t

typedef std::pair< key_t, tree_t >	pair_t

typedef container_t::iterator	iterator

typedef container_t::const_iterator	const_iterator

typedef std::pair< key_t, node_data_t >	node_pair_t
	Experimental. Given pair<elem, data> assigns child[elem] = data;.

Public Member Functions
typedef	DRAIN_TREE_CONTAINER (key_t, tree_t) container_t

	DRAIN_TREE_NAME ()
	Default constructor.

	DRAIN_TREE_NAME (const node_data_t &data)
	Copy constructor; copy only node data at the root.

	DRAIN_TREE_NAME (const DRAIN_TREE_NAME &t)
	Copy constructor; copy only node data at the root.

virtual bool	hasMultipleData () const

virtual const node_data_t &	getData () const

virtual node_data_t &	getData ()

virtual const node_data_t &	getData (const key_t &key) const

virtual node_data_t &	getData (const key_t &key)

container_t::const_iterator	begin () const
	Child iterator pointing to the first child.

container_t::const_iterator	end () const
	Child iterator pointing beyond the last child.

container_t::iterator	begin ()
	Child iterator pointing to the first child.

container_t::iterator	end ()
	Child iterator end.

tree_t &	operator= (const tree_t &t)
	Copies the data of another node. Does not copy the children. More...

template<class S >
tree_t &	operator= (const std::initializer_list< S > &l)
	Assigns value to contents.

template<class T2 >
tree_t &	operator= (const T2 &v)
	Assigns a value to contents.

tree_t &	operator<< (const node_pair_t &entry)

tree_t &	ensureChild (const node_pair_t &entry)

	operator const node_data_t & () const

	operator node_data_t & ()

tree_t &	operator[] (const key_t &key)
	Child addressing operator.

const tree_t &	operator[] (const key_t &key) const
	Child addressing operator.

tree_t &	operator() (const path_t &path)
	Returns a descendant. Creates one if not existing already. More...

template<class S >
tree_t &	operator() (const S &arg)
	Returns a descendant. Creates one if not existing already. More...

tree_t &	operator() (const char *arg)
	Redirects the call to operator()(const std::string & arg) . More...

const tree_t &	operator() (const path_t &path) const
	Returns a descendant if that exists, else returns an empty node. Otherwise like non-const counterpart. More...

template<class S >
const tree_t &	operator() (const S &arg) const
	Returns a descendant if that exists, else returns an empty node. Otherwise like non-const counterpart.

const tree_t &	operator() (const char *arg) const
	Redirects the call to operator()(const std::string & arg) .

void	clear ()
	Clear children and node data. More...

void	clearData ()

void	clearChildren ()
	Clears the children of this node. Does not clear data. More...

void	erase (const path_t &path)
	Deletes a descendant node and hence its subtrees. More...

virtual const tree_t &	getEmpty () const

virtual bool	empty () const
	Check if the tree structure is empty.

bool	hasChildren () const

virtual int	hasChildren (const key_t &key) const
	The number of children with name key. More...

virtual bool	hasChild (const key_t &key) const
	Check if the tree node has a direct descendant with name `key`. More...

bool	hasPath (const path_t &path) const

virtual tree_t &	addChild (const key_t &key=key_t())
	Add a child node. If unordered and UNIQUE, reuse existing nodes. More...

virtual tree_t &	retrieveChild (const key_t &key)

virtual const tree_t &	retrieveChild (const key_t &key) const

container_t &	getChildren ()
	Returns the map containing the children. More...

const container_t &	getChildren () const
	Returns the map containing the children.

const node_data_t *	operator-> () const
	Fast access to data, applied widely in TreeXML (HTML/SVG)

node_data_t *	operator-> ()
	Fast access to data, applied widely in TreeXML (HTML/SVG)

void	swap (tree_t &t)
	Replace children (but no data?)

Static Public Member Functions
static bool	isExclusive ()

static bool	isMulti ()

static bool	isOrdered ()

Public Attributes
node_data_t	data
	Contents (data) of the node.

Protected Member Functions
bool	hasPath (typename path_t::const_iterator it, typename path_t::const_iterator eit) const
	Checks if there is a node with a given path name. More...

tree_t &	get (typename path_t::const_iterator it, typename path_t::const_iterator eit)
	Returns a descendant. Creates one, if not present.

const tree_t &	get (typename path_t::const_iterator it, typename path_t::const_iterator eit) const
	Given the descendant pointed to by a given path segment. More...

Protected Attributes
container_t	children

Static Protected Attributes
static const tree_t	emptyNode

Detailed Description

template<class T, bool EXCLUSIVE = false, class P = drain::Path<std::string,'/'>>
class drain::DRAIN_TREE_NAME< T, EXCLUSIVE, P >

A templated class for directed rooted trees.

This file provides templates of for basic types of trees (directed rooted trees):

OrderedTree – std::map<>
OrderedMultiTree – std::multimap
UnorderedTree – std::list
UnorderedMultiTree – std::list

Template Parameters

T	- node type, containing user-designed data implementing clear(), size() and empty() for future compatibility.
EXCLUSIVE	- node can contains either data or children but not both (JSON-like convention)
P	- applied path structure, like std::list – must implement empty() both for path and keys (path elements)

Data:

The nodes in a tree contain user defined data, the type of which is given as template T.

Currenty, data Concept is requires the following methods:

clear() – resetting the data to default initial (empty) value.
empty() – returning true if the data is empty, or can be identified with empty.

A tree is EXCLUSIVE, if a node contains either data or children. For example, a JSON tree is EXCLUSIVE and an XML tree is not (a tag can containg attributes (data) and inner tages (children).

Further, each type listed above has two variants:

inclusive (implicit, default) – each node may contain data and child nodes.
exclusive – each node may contain data or child nodes, but not both. In the code, both data and children exist as members but in exclusive trees data is automatically cleared if children are added, and inversely, chilren are cleared (removed) if data is assigned.

Limitation: in OrderedTree the children are in a std::map, and threrefore each child of a node has a unique key. In UnorderedTree there may be children having the same key.

Addressing:

tree(<path>) return a descendant tree[<path_element>] returns childs only (complains separators, for some time)

Child nodes can be addressed with operator[] with std::string valued keys:

OrderedTree<std::string> tree;
t["first"] = "Hello!";
t["second"] = "Another greeting...";

As the operator[] returns a reference, it may be used recursively:

OrderedTree<std::string> & subTree1 = t["first"]["child"]["grandChild"];

Tree also recognizes a path separator, which is '/' by default. Hence, the node created in the above example could be likewise created or addressed as:

OrderedTree<std::string> & subTree = t("first/child/grandChild"); // equivalent

One may iterate the children directly:

for (auto & entry: tree){
  std::cout << entry.first << ':' << entry.second << '\n';
}

Each node contains data of type T. It may be unused (empty), that is, a node can be used only as a branching point.

OrderedTree<std::string> t;
t.data = "Hello world";
std::string s = t;  // Now contains "Hello world".

(Direct assignments to and from the node data has been supported, but is now disabled for c++ compatibility reasons.)

Also direct referencing of the node data is now disabled:

Tree<std::string> t;
t = "Hello world";
Tree<std::string> &r = t; // Refers to tree.
std::string &s = t;       // Refers to data, "Hello world".

Obsolete: template C - path element comparison functor, should be compatible with Path<P>::key_t. #ifndef DRAIN_AMBIVALUE #define DRAIN_AMBIVALUE "0.1beta" template <class T, class K> class CombiValue { public:

typedef T data_t;
typedef K key_t;

T data; CONSIDER! But Hi5Node heavy?

inline
~CombiValue(){};

/ True, if data is structured. virtual bool hasMultipleData() const = 0;

virtual
const data_t & getData() const = 0;

virtual
data_t & getData() = 0;

virtual
const data_t & getData(const key_t &) const = 0;

virtual
data_t & getData(const key_t &) = 0;

}; #endif

Template Parameters

K	– key type
K	– key type

Member Function Documentation

◆ addChild()

virtual tree_t& addChild ( const key_t & key = key_t() )

inlinevirtual

Add a child node. If unordered and UNIQUE, reuse existing nodes.

Behaviour of this function varies as follows:

OrderedTree: return child named key, if exists
UnorderedTree, UNIQUE==true: return the first child named key, if exists, else create one.
UnorderedTree, UNIQUE==false: always create a new child named key and return it.

◆ clear()

void clear ( )

inline

Clear children and node data.

See also: erase(); clearChildren(); clearData()

◆ clearChildren()

void clearChildren ( )

inline

Clears the children of this node. Does not clear data.

x *

See also: clearData(); clear(); erase()

◆ clearData()

void clearData ( )

inline

See also: clear(); clearChildren(); erase()

◆ erase()

void erase ( const path_t & path )

inline

Deletes a descendant node and hence its subtrees.

As opposite of clear() which focuses on a (current) node, this function refers to a descendant.

See also: clear()

◆ get()

const tree_t& get	(	typename path_t::const_iterator	it,
		typename path_t::const_iterator	eit
	)		const

inlineprotected

Given the descendant pointed to by a given path segment.

Returns: – descendant node, or the node itself if the path is empty.

◆ getChildren()

container_t& getChildren ( )

inline

Returns the map containing the children.

This is useful for example for map::swap ?

◆ getEmpty()

virtual const tree_t& getEmpty ( ) const

inlinevirtual

GENERAL (independent from container type) Empty "default" node; typically initialized with empty data as well.

◆ hasChild()

virtual bool hasChild ( const key_t & key ) const

inlinevirtual

Check if the tree node has a direct descendant with name key.

A multiple tree may have more than one children with the same name. With them, consider hasChildren(const key_t &key) .

See also: OrderedMultiTree; UnorderedMultiTree

Returns: – the number of children with name 'key'.

◆ hasChildren()

virtual int hasChildren ( const key_t & key ) const

inlinevirtual

The number of children with name key.

Checks how many immediate descendants with name key exist.

A multiple tree may have more than one children with the same name.

See also: OrderedMultiTree, UnorderedMultiTree

With simple trees, use the faster hasChild(const key_t &key).

See also: OrderedTree; UnorderedTree.

Returns: – the number of children with name 'key'.

◆ hasPath()

bool hasPath	(	typename path_t::const_iterator	it,
		typename path_t::const_iterator	eit
	)		const

inlineprotected

Checks if there is a node with a given path name.

Could be called hasDescendant; hence is like hasChild() but calls children recursively.

Parameters

eit - end()

◆ operator()() [1/4]

tree_t& operator() ( const char * arg )

inline

Redirects the call to operator()(const std::string & arg) .

Parameters

arg	- by default, the path from the current node to the child node.

◆ operator()() [2/4]

tree_t& operator() ( const path_t & path )

inline

Returns a descendant. Creates one if not existing already.

Parameters

path	- the path from the current node to the child node.

This function, using native path_t type, should be reserved for this semantic by not redefining (specialising) this function in template classes.

◆ operator()() [3/4]

const tree_t& operator() ( const path_t & path ) const

inline

Returns a descendant if that exists, else returns an empty node. Otherwise like non-const counterpart.

Parameters

path	- the path from the current node to the child node.

This function, using native path_t type, should be reserved for this semantic by not redefining (specialising) this function in template classes.

◆ operator()() [4/4]

tree_t& operator() ( const S & arg )

inline

Returns a descendant. Creates one if not existing already.

Parameters

path	- the path from the current node to the child node.

This function, not using native path_t type, can be redefined in template classes. For example, an important attribute can be set using this method. Method operator()(const char *arg) should be redefined to produce equivalent result with const string &arg.

◆ operator=()

tree_t& operator= ( const tree_t & t )

inline

Copies the data of another node. Does not copy the children.

Default use to reset a node (re-initialize its data).

The documentation for this class was generated from the following file:

src/drain/util/Tree.h

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

template<class T, bool EXCLUSIVE = false, class P = drain::Path<std::string,'/'>> class drain::DRAIN_TREE_NAME< T, EXCLUSIVE, P >

Member Function Documentation

◆ addChild()

◆ clear()

◆ clearChildren()

◆ clearData()

◆ erase()

◆ get()

◆ getChildren()

◆ getEmpty()

◆ hasChild()

◆ hasChildren()

◆ hasPath()

◆ operator()() [1/4]

◆ operator()() [2/4]

◆ operator()() [3/4]

◆ operator()() [4/4]

◆ operator=()

template<class T, bool EXCLUSIVE = false, class P = drain::Path<std::string,'/'>>
class drain::DRAIN_TREE_NAME< T, EXCLUSIVE, P >