elm::stree::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

template<class K, class T, class C = Comparator<K>>

typedef struct elm::stree::Tree::node_t elm::stree::Tree< K, T, C >::node_t

Constructor & Destructor Documentation

template<class K, class T, class C = Comparator<K>>

elm::stree::Tree< K, T, C >::Tree

(

void

)

Build an empty tree.

template<class K, class T, class C = Comparator<K>>

elm::stree::Tree< K, T, C >::Tree	(	int	_root,
		node_t *	_nodes
	)

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.

template<class K, class T, class C = Comparator<K>>

elm::stree::Tree< K, T, C >::~Tree

(

void

)

Member Function Documentation

template<class K, class T, class C = Comparator<K>>

bool elm::stree::Tree< K, T, C >::contains

(

const K &

key

)

const

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

template<class K, class T, class C = Comparator<K>>

T* elm::stree::Tree< K, T, C >::find ( const K &  key ) const

protected

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

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

template<class K, class T, class C = Comparator<K>>

const T & elm::stree::Tree< K, T, C >::get	(	const K &	key,
		const T &	def
	)		const

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 elm::stree::Tree< K, T, C >::find().

Referenced by elm::SimpleGC::mark().

template<class K, class T, class C = Comparator<K>>

const T & elm::stree::Tree< K, T, C >::get

(

const K &

key

)

const

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

Parameters

key	Key to look for.

Returns

Found value.

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

template<class K, class T, class C = Comparator<K>>

T& elm::stree::Tree< K, T, C >::get

(

const K &

key

)

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

template<class K, class T, class C = Comparator<K>>

void elm::stree::Tree< K, T, C >::set	(	int	_root,
		node_t *	_nodes
	)

Initialize the current tree with the current configuration.

Parameters

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

Referenced by elm::stree::MarkerBuilder< K, T, C >::make(), and elm::stree::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