Elm  2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
GenTree< T, K, C, A > Class Template Reference

#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 K::key_t >
typedef typename K::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_toperator+= (const T &x)
 
self_toperator-= (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 K::key_t >
int doCompare (const typename K::key_t &v1, const typename K::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

Noderoot (void) const
 
void remove (Stack &s, Node *n)
 
int compare (const typename K::key_t &k1, const typename K::key_t &k2) const
 
Nodelookup (Stack &s, const typename K::key_t &key) const
 
Nodefind (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)
 
NodeleftMost (Stack &s, Node *n)
 

Additional Inherited Members

- Static Public Member Functions inherited from Comparator< typename K::key_t >
static int compare (const typename K::key_t &v1, const typename K::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
TType of contained items.
CComparator 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
itemItem to add.

References AbstractTree::insert(), and GenTree< T, K, C, A >::lookup().

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

◆ addAll()

void addAll ( const CC &  c)
inline

Add a collection to this tree.

Parameters
collCollection to add.
CType of the collection.

References GenTree< T, K, C, A >::add().

◆ allocator() [1/2]

A& allocator ( )
inline

◆ allocator() [2/2]

const A& allocator ( ) const
inline

◆ begin()

Iter begin ( void  ) const
inline

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

◆ clear()

◆ comparator() [1/2]

C& comparator ( )
inline

◆ comparator() [2/2]

const C& comparator ( ) const
inline

◆ compare()

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

◆ contains()

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

Test if the tree contains the given item.

Parameters
itemItem to look for.
Returns
True if it is contained, false else. @notice Access time in log2(item number).

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

Referenced by GenTree< T, K, C, A >::containsAll(), and Set< T, C >::meet().

◆ containsAll()

bool containsAll ( const CC &  c) const
inline

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

Parameters
collCollection to test.
Returns
True if the collection is containted, false else.
Parameters
CType of the collection.

References GenTree< T, K, C, A >::contains().

◆ copy()

◆ 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.

References AbstractTree::_cnt.

Referenced by Map< K, T, C, E, A >::count().

◆ end()

Iter end ( void  ) const
inline

◆ equals()

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

◆ exchange()

void exchange ( Node n,
Node p 
)
inlineprotected

◆ find()

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

◆ get() [1/2]

◆ 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.

References AbstractTree::_cnt.

Referenced by Map< K, T, C, E, A >::isEmpty(), and GenTree< T, K, C, A >::operator bool().

◆ lookup()

◆ 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

◆ 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
itemItem to remove.
Warning
Attempting to remove an item not contained in the tree is an error.

References GenTree< T, K, C, A >::removeByKey().

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

◆ remove() [3/3]

◆ removeAll()

void removeAll ( const CC &  c)
inline

Remove a collection from this tree.

Parameters
collCollection to remove.
CType of the collection.

References GenTree< T, K, C, A >::remove().

◆ removeByKey()

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

◆ root()

◆ set()

void set ( const T &  item)
inline

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