![]() |
Elm
2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
|
#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_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 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 | |
| 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 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 |
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.
| T | Type of contained items. |
| C | Comparator for T items (default to elm::Comparator<T>). |
| typedef T t |
References GenTree< T, K, C, A >::copy().
References GenTree< T, K, C, A >::clear().
|
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.
| item | Item 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().
|
inline |
Add a collection to this tree.
| coll | Collection to add. |
| C | Type of the collection. |
References GenTree< T, K, C, A >::add().
|
inline |
|
inline |
Referenced by Map< K, T, C, E, A >::allocator(), and Map< K, T, C, E, A >::allocatr().
Referenced by Set< T, C >::subsetOf().
Remove all items from the tree and let it cleared.
References AbstractTree::_cnt, AbstractTree::_root, GenTree< T, K, C, A >::Node::free(), StaticStack< T, N >::isEmpty(), GenTree< T, K, C, A >::Node::left(), StaticStack< T, N >::pop(), StaticStack< T, N >::push(), GenTree< T, K, C, A >::Node::right(), and GenTree< T, K, C, A >::root().
Referenced by GenTree< T, K, C, A >::~GenTree(), Map< K, T, C, E, A >::clear(), GenTree< T, K, C, A >::copy(), and Queue< T, C, A >::reset().
|
inline |
|
inline |
Referenced by Map< K, T, C, E, A >::comparator().
|
inlineprotected |
Referenced by GenTree< T, K, C, A >::find(), and GenTree< T, K, C, A >::lookup().
|
inline |
Test if the tree contains the given item.
| item | Item to look for. |
References GenTree< T, K, C, A >::find().
Referenced by GenTree< T, K, C, A >::containsAll(), and Set< T, C >::meet().
|
inline |
Test if the given collection is contained in the current one.
| coll | Collection to test. |
| C | Type of the collection. |
References GenTree< T, K, C, A >::contains().
References AbstractTree::_cnt, AbstractTree::_root, GenTree< T, K, C, A >::clear(), StaticStack< T, N >::pop(), and GenTree< T, K, C, A >::root().
Referenced by GenTree< T, K, C, A >::GenTree(), Map< K, T, C, E, A >::copy(), Set< T, C >::meet(), GenTree< T, K, C, A >::operator=(), and Set< T, C >::operator=().
|
inline |
Get the count of items in the tree.
References AbstractTree::_cnt.
Referenced by Map< K, T, C, E, A >::count().
References GenTree< T, K, C, A >::Node::data, and elm::io::p().
Referenced by GenTree< T, K, C, A >::remove().
|
inlineprotected |
References GenTree< T, K, C, A >::compare(), elm::io::p(), and GenTree< T, K, C, A >::root().
Referenced by GenTree< T, K, C, A >::contains(), and GenTree< T, K, C, A >::get().
|
inline |
References GenTree< T, K, C, A >::Node::data, and GenTree< T, K, C, A >::find().
Referenced by Map< K, T, C, E, A >::get(), Map< K, T, C, E, A >::hasKey(), and Map< K, T, C, E, A >::operator[]().
|
inline |
References GenTree< T, K, C, A >::Node::data, and GenTree< T, K, C, A >::find().
Test if the tree is empty.
References AbstractTree::_cnt.
Referenced by Map< K, T, C, E, A >::isEmpty(), and GenTree< T, K, C, A >::operator bool().
References GenTree< T, K, C, A >::isEmpty().
References GenTree< T, K, C, A >::equals().
|
inline |
References GenTree< T, K, C, A >::add().
|
inline |
References GenTree< T, K, C, A >::remove().
References GenTree< T, K, C, A >::copy().
References GenTree< T, K, C, A >::equals().
References GenTree< T, K, C, A >::remove().
Referenced by GenTree< T, K, C, A >::remove().
|
inline |
Remove an item from a tree. Notice that if the tree contains duplicates of the item, only the first duplicate is removed.
| item | Item to remove. |
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().
|
inline |
Remove a collection from this tree.
| coll | Collection to remove. |
| C | Type of the collection. |
References GenTree< T, K, C, A >::remove().
|
inline |
References GenTree< T, K, C, A >::lookup(), and GenTree< T, K, C, A >::remove().
Referenced by Map< K, T, C, E, A >::remove(), and GenTree< T, K, C, A >::remove().
|
inline |
References GenTree< T, K, C, A >::add().
Referenced by Map< K, T, C, E, A >::put().