#include <elm/avl/GenTree.h>

Inheritance diagram for GenTree< T, K, C, A >:

Classes
class	Iter

class	Node

class	Stack

class	VisitStack

Public Types
typedef T	t

typedef GenTree< T, K, C, A >	self_t

Public Types inherited from Comparator< typename IdAdapter< T > ::key_t >
typedef typename IdAdapter< T > ::key_t	t

Public Member Functions
	GenTree (void)

	GenTree (const GenTree< T > &tree)

	~GenTree (void)

const C &	comparator () const

C &	comparator ()

const A &	allocator () const

A &	allocator ()

T *	get (const typename K::key_t &key)

const T *	get (const typename K::key_t &key) const

void	set (const T &item)

void	removeByKey (const typename K::key_t &item)

int	count (void) const

bool	contains (const typename K::key_t &item) const

template<class CC >
bool	containsAll (const CC &c) const

bool	isEmpty (void) const

	operator bool (void) const

Iter	begin (void) const

Iter	end (void) const

bool	equals (const GenTree< T, K, C > &tree) const

bool	operator== (const GenTree< T, K, C > &tree) const

bool	operator!= (const GenTree< T, K, C > &tree) const

void	clear (void)

void	add (const T &item)

template<class CC >
void	addAll (const CC &c)

void	remove (const T &x)

template<class CC >
void	removeAll (const CC &c)

void	remove (const Iter &iter)

self_t &	operator+= (const T &x)

self_t &	operator-= (const T &x)

void	copy (const GenTree< T, K, C > &tree)

GenTree< T, K, C > &	operator= (const GenTree< T, K, C > &tree)

Public Member Functions inherited from AbstractTree
int	count (void) const

Public Member Functions inherited from Comparator< typename IdAdapter< T > ::key_t >
int	doCompare (const typename IdAdapter< T > ::key_t &v1, const typename IdAdapter< T > ::key_t &v2) const

Public Member Functions inherited from DefaultAllocatorDelegate
t::ptr	allocate (t::size size) const

void	free (t::ptr p) const

template<class T >
T *	alloc () const

Protected Member Functions
Node *	root (void) const

void	remove (Stack &s, Node *n)

int	compare (const typename K::key_t &k1, const typename K::key_t &k2) const

Node *	lookup (Stack &s, const typename K::key_t &key) const

Node *	find (const typename K::key_t &key) const

void	exchange (Node n, Node p)

Protected Member Functions inherited from AbstractTree
	AbstractTree (void)

Node **	link (const Stack &s)

void	exchange (Node n, Node m)

void	insert (Stack &stack, Node *node)

void	rotateRight (Stack &s)

void	rotateLeft (Stack &s)

void	remove (Stack &stack, Node *n)

Node *	leftMost (Stack &s, Node *n)

Additional Inherited Members
Static Public Member Functions inherited from Comparator< typename IdAdapter< T > ::key_t >
static int	compare (const typename IdAdapter< T > ::key_t &v1, const typename IdAdapter< T > ::key_t &v2)

Protected Types inherited from AbstractTree
enum	dir_t { LEFT = -1, NONE = 0, RIGHT = +1 }

typedef signed char	balance_t

Protected Attributes inherited from AbstractTree
Node *	_root

int	_cnt

Static Protected Attributes inherited from AbstractTree
static const int	MAX_HEIGHT = 32

Detailed Description

template<class T, class K = IdAdapter<T>, class C = elm::Comparator<typename K::key_t>, class A = DefaultAlloc>
class elm::avl::GenTree< T, K, C, A >

This class implements an AVL tree collection based on C++ templates as provided by: Ben Pfaff, "An Introduction to Binary Search Trees and Balanced Trees", Libavl Binary Search Tree Library, Volume 1: Source Code, Version 2.0.2.

: This class is rarely used as is but used as a base class for elm::avl::Set or elm::avl::Map.

Parameters

T	Type of contained items.
C	Comparator for T items (default to elm::Comparator<T>).

Implemented concepts

See also: elm::avl::Set, elm::avl::Map

Member Typedef Documentation

◆ self_t

typedef GenTree<T, K, C, A> self_t

◆ t

typedef T t

Constructor & Destructor Documentation

◆ GenTree() [1/2]

GenTree ( void )

inline

◆ GenTree() [2/2]

GenTree ( const GenTree< T > & tree )

inline

◆ ~GenTree()

~GenTree ( void )

inline

Member Function Documentation

◆ add()

void add ( const T & item )

inline

Add an item to the tree. Note that the item is still added even if it is already contained in the tree, leading to duplicates.

Parameters

item	Item to add.

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::addAll(), Set< T, C >::insert(), Set< T, C >::join(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::operator+=(), Queue< T, C, A >::put(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::set().

◆ addAll()

void addAll ( const CC & c )

inline

Add a collection to this tree.

Parameters

coll	Collection to add.
C	Type of the collection.

◆ allocator() [1/2]

A& allocator ( )

inline

◆ allocator() [2/2]

const A& allocator ( ) const

inline

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::allocator(), and Map< Pair< K, K >, T, segment_comparator_t >::allocatr().

◆ begin()

Iter begin ( void ) const

inline

Referenced by Set< T, C >::subsetOf().

◆ clear()

void clear ( void )

inline

Remove all items from the tree and let it cleared.

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::clear(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::copy(), Queue< T, C, A >::reset(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::~GenTree().

◆ comparator() [1/2]

C& comparator ( )

inline

◆ comparator() [2/2]

const C& comparator ( ) const

inline

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::comparator().

◆ compare()

int compare	(	const typename K::key_t &	k1,
		const typename K::key_t &	k2
	)		const

inlineprotected

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::find(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::lookup().

◆ contains()

bool contains ( const typename K::key_t & item ) const

inline

Test if the tree contains the given item.

Parameters

item	Item to look for.

Returns: True if it is contained, false else. @notice Access time in log2(item number).

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::containsAll().

◆ containsAll()

bool containsAll ( const CC & c ) const

inline

Test if the given collection is contained in the current one.

Parameters

coll	Collection to test.

Returns: True if the collection is containted, false else.

Parameters

C	Type of the collection.

◆ copy()

void copy ( const GenTree< T, K, C > & tree )

inline

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::copy(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::GenTree(), Set< T, C >::operator=(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::operator=().

◆ count()

int count ( void ) const

inline

Get the count of items in the tree.

Returns: Item count. @notice This function call is fast as the item count is maintained during each insertion and removal.

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::count().

◆ end()

Iter end ( void ) const

inline

◆ equals()

bool equals ( const GenTree< T, K, C > & tree ) const

inline

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::equals(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::operator!=(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::operator==().

◆ exchange()

void exchange	(	Node *	n,
		Node *	p
	)

inlineprotected

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::remove().

◆ find()

Node* find ( const typename K::key_t & key ) const

inlineprotected

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::contains(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::get().

◆ get() [1/2]

T* get ( const typename K::key_t & key )

inline

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::get(), Map< Pair< K, K >, T, segment_comparator_t >::hasKey(), and Map< Pair< K, K >, T, segment_comparator_t >::operator[]().

◆ get() [2/2]

const T* get ( const typename K::key_t & key ) const

inline

◆ isEmpty()

bool isEmpty ( void ) const

inline

Test if the tree is empty.

Returns: True if the tree is empty, false else.

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::isEmpty(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::operator bool().

◆ lookup()

Node* lookup	(	Stack &	s,
		const typename K::key_t &	key
	)		const

inlineprotected

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::add(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::removeByKey().

◆ operator bool()

operator bool ( void ) const

inline

◆ operator!=()

bool operator!= ( const GenTree< T, K, C > & tree ) const

inline

◆ operator+=()

self_t& operator+= ( const T & x )

inline

◆ operator-=()

self_t& operator-= ( const T & x )

inline

◆ operator=()

GenTree<T, K, C>& operator= ( const GenTree< T, K, C > & tree )

inline

◆ operator==()

bool operator== ( const GenTree< T, K, C > & tree ) const

inline

◆ remove() [1/3]

void remove ( const Iter & iter )

inline

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::remove().

◆ remove() [2/3]

void remove ( const T & item )

inline

Remove an item from a tree. Notice that if the tree contains duplicates of the item, only the first duplicate is removed.

Parameters

item	Item to remove.

Warning: Attempting to remove an item not contained in the tree is an error.

Referenced by Set< T, C >::diff(), Queue< T, C, A >::get(), Set< T, C >::operator-=(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::operator-=(), Map< Pair< K, K >, T, segment_comparator_t >::remove(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::removeAll(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::removeByKey().

◆ remove() [3/3]

void remove	(	Stack &	s,
		Node *	n
	)

inlineprotected

◆ removeAll()

void removeAll ( const CC & c )

inline

Remove a collection from this tree.

Parameters

coll	Collection to remove.
C	Type of the collection.

◆ removeByKey()

void removeByKey ( const typename K::key_t & item )

inline

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::remove(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::remove().

◆ root()

Node* root ( void ) const

inlineprotected

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::clear(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::copy(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::find(), Queue< T, C, A >::get(), Queue< T, C, A >::head(), GenTree< T, K, C, A >::Iter::Iter(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::lookup().

◆ set()

void set ( const T & item )

inline

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::put().

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

include/elm/avl/GenTree.h
src/avl_GenTree.cpp

Classes

Public Types

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

template<class T, class K = IdAdapter<T>, class C = elm::Comparator<typename K::key_t>, class A = DefaultAlloc> class elm::avl::GenTree< T, K, C, A >

Member Typedef Documentation

◆ self_t

◆ t

Constructor & Destructor Documentation

◆ GenTree() [1/2]

◆ GenTree() [2/2]

◆ ~GenTree()

Member Function Documentation

◆ add()

◆ addAll()

◆ allocator() [1/2]

◆ allocator() [2/2]

◆ begin()

◆ clear()

◆ comparator() [1/2]

◆ comparator() [2/2]

◆ compare()

◆ contains()

◆ containsAll()

◆ copy()

◆ count()

◆ end()

◆ equals()

◆ exchange()

◆ find()

◆ get() [1/2]

◆ get() [2/2]

◆ isEmpty()

◆ lookup()

◆ operator bool()

◆ operator!=()

◆ operator+=()

◆ operator-=()

◆ operator=()

◆ operator==()

◆ remove() [1/3]

◆ remove() [2/3]

◆ remove() [3/3]

◆ removeAll()

◆ removeByKey()

◆ root()

◆ set()

template<class T, class K = IdAdapter<T>, class C = elm::Comparator<typename K::key_t>, class A = DefaultAlloc>
class elm::avl::GenTree< T, K, C, A >