Tree< K, T, C > Class Template Reference

#include <elm/stree/Tree.h>

Classes
struct	node_t

Public Types
typedef struct elm::stree::Tree::node_t	node_t

Public Member Functions
	Tree (void)
	Tree (int _root, node_t *_nodes)
void	set (int _root, node_t *_nodes)
	~Tree (void)
const T &	get (const K &key, const T &def) const
const T &	get (const K &key) const
T &	get (const K &key)
bool	contains (const K &key) const

Protected Member Functions
T *	find (const K &key) const

Detailed Description

template<class K, class T, class C = Comparator<K>>
class elm::stree::Tree< K, T, C >

A segmented tree allows to retrieve items associated with a segment, that is, a value range. The access is quite fast (log2(n)) but the creation of the tree is not dynamic: all segment must be provided at creation time.

To help to build such a structure, several builder are provided:

• elm::stree::Builder
• elm::stree::MakerBuilder

Parameters

K	Key type.
T	Retrieven item type.
C	Comparator to compare keys (default to Comparator<K>).

Member Typedef Documentation

node_t

typedef struct elm::stree::Tree::node_t node_t

Constructor & Destructor Documentation

Tree() [1/2]

Tree ( void  )

inline

Build an empty tree.

Tree() [2/2]

Tree ( int  _root, node_t *  _nodes  )

inline

Build form the given list of nodes. The tree is responsible to release the node array at destruction time.

Parameters

_root	Index of root node in the node array.
_nodes	List of nodes.

~Tree()

~Tree ( void  )

inline

Member Function Documentation

contains()

bool contains ( const K &  key ) const

inline

Referenced by Tree< K, T, C >::find().

find()

T* find ( const K &  key ) const

inlineprotected

References Tree< K, T, C >::contains(), Tree< K, T, C >::node_t::data, Tree< K, T, C >::node_t::left(), Tree< K, T, C >::node_t::right(), and elm::io::right().

Referenced by Tree< K, T, C >::get().

get() [1/3]

T& get ( const K &  key )

inline

References Tree< K, T, C >::find().

get() [2/3]

const T & get ( const K &  key ) const

inline

Find a value by its key or raise an assertion failure.

Parameters

key	Key to look for.

Returns

Found value.

References Tree< K, T, C >::find().

get() [3/3]

const T & get ( const K &  key, const T &  def  ) const

inline

Find the value associated with the given key. If not found, return the default value.

Parameters

key	Key to look for.
def	Default value.

Returns

Found value or default value.

References Tree< K, T, C >::find().

Referenced by GroupedGC::mark(), and SimpleGC::mark().

set()

void set ( int  _root, node_t *  _nodes  )

inline

Initialize the current tree with the current configuration.

Parameters

_root	Index of root node in the node array.
_nodes	List of nodes.

Referenced by MarkerBuilder< K, T, C >::make(), and SegmentBuilder< K, T, C >::make().

---

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

• include/elm/stree/Tree.h
• src/stree_Tree.cpp