BaseAvlTree Class Reference

Common base class for the template AVL tree class. More...

#include <avl.hxx>

Inheritance diagram for BaseAvlTree:

List of all members.

Public Member Functions
	BaseAvlTree (BaseCmpFn_t cmp)
	~BaseAvlTree ()
Protected Types
typedef int(*	BaseCmpFn_t )(const BaseAvlNode &n1, const BaseAvlNode &n2)
typedef int(*	AvlIterFunc )(BaseAvlNode &)
Protected Member Functions
void	insert (BaseAvlNode *nd)
BaseAvlNode *	choose ()
BaseAvlNode *	least ()
BaseAvlNode *	greatest ()
void	remove (BaseAvlNode &node)
BaseAvlNode *	lookup (const BaseAvlNode &key)
BaseAvlNode *	lookupGLE (const BaseAvlNode &key)
void	iterate (AvlIterFunc avlFunc)

---

Detailed Description

Common base class for the template AVL tree class.

Note that on desctruction all of the internally allocated node structures are deleted. This means that outstanding pointers to them should not be retained.

Definition at line 98 of file avl.hxx.

---

Member Typedef Documentation

typedef int(* BaseAvlTree::AvlIterFunc)(BaseAvlNode &) [protected]

Reimplemented in AvlTree< KeyType >, AvlMap< KeyType, ValueType >, AvlMap< MutName, bool >, AvlMap< AvlPtrWrap< DiffToken >, bool >, AvlMap< TrueName, bool >, and AvlMap< KeyType, bool >. Definition at line 163 of file avl.hxx.

typedef int(* BaseAvlTree::BaseCmpFn_t)(const BaseAvlNode &n1, const BaseAvlNode &n2) [protected]

Definition at line 100 of file avl.hxx.

---

Constructor & Destructor Documentation

BaseAvlTree::BaseAvlTree (  BaseCmpFn_t  cmp  )

BaseAvlTree::~BaseAvlTree (   )

Definition at line 89 of file avl.cxx. References choose(), and remove().

---

Member Function Documentation

BaseAvlNode * BaseAvlTree::choose (   )  [protected]

Selects an arbitrary node from within the avl tree (if any) and returns it, or NULL if no nodes remain. The returned node remains in the tree. Reimplemented in AvlTree< KeyType >, AvlMap< KeyType, ValueType >, AvlMap< MutName, bool >, AvlMap< AvlPtrWrap< DiffToken >, bool >, AvlMap< TrueName, bool >, and AvlMap< KeyType, bool >. Definition at line 597 of file avl.cxx. Referenced by AvlMap< KeyType, bool >::choose(), iterate(), and ~BaseAvlTree().

BaseAvlNode * BaseAvlTree::greatest (   )  [protected]

Returns the greatest node in the avl tree (if any) or NULL. The returned node remains in the tree. Reimplemented in AvlTree< KeyType >, AvlMap< KeyType, ValueType >, AvlMap< MutName, bool >, AvlMap< AvlPtrWrap< DiffToken >, bool >, AvlMap< TrueName, bool >, and AvlMap< KeyType, bool >. Definition at line 617 of file avl.cxx. References BaseAvlNode::rchild. Referenced by AvlMap< KeyType, bool >::greatest(), and lookupGLE().

void BaseAvlTree::insert (  BaseAvlNode *  nd  )  [protected]

Insert a new node into an existing AVL tree. The lchild/rchild fields of the inserted node will be set to NULL prior to insertion. Definition at line 369 of file avl.cxx. References BaseAvlNode::balance, BaseAvlNode::lchild, and BaseAvlNode::rchild. Referenced by AvlMap< KeyType, bool >::insert(), and iterate().

void BaseAvlTree::iterate (  AvlIterFunc  avlFunc  )  [protected]

Reimplemented in AvlTree< KeyType >, AvlMap< KeyType, ValueType >, AvlMap< MutName, bool >, AvlMap< AvlPtrWrap< DiffToken >, bool >, AvlMap< TrueName, bool >, and AvlMap< KeyType, bool >. Definition at line 649 of file avl.cxx. References choose(), insert(), and root. Referenced by AvlMap< KeyType, bool >::iterate(), and AvlTree< KeyType >::iterate().

BaseAvlNode * BaseAvlTree::least (   )  [protected]

Returns the least node in the avl tree (if any) or NULL. The returned node remains in the tree. Reimplemented in AvlTree< KeyType >, AvlMap< KeyType, ValueType >, AvlMap< MutName, bool >, AvlMap< AvlPtrWrap< DiffToken >, bool >, AvlMap< TrueName, bool >, and AvlMap< KeyType, bool >. Definition at line 603 of file avl.cxx. References BaseAvlNode::lchild. Referenced by AvlMap< KeyType, bool >::least().

BaseAvlNode * BaseAvlTree::lookup (  const BaseAvlNode &  key  )  [protected]

Test whether and existing value exists within an AVL tree. It may seem wasteful that the client must supply an BaseAvlNode rather than some more compact AvlKey structure. In our experience with tree structures it is usually the case that the search key structure is stack allocated. Since the only fields that need to be initialized are the ones consulted by the comparator routine, allocating a full BaseAvlNode actually isn't any more expensive -- it just bumps the stack by a few more words. The advantage of reusing the BaseAvlNode structure for this purpose is that it allows the tree itself to remain completely agnostic about key types and value types. Definition at line 550 of file avl.cxx. References BaseAvlNode::lchild, and BaseAvlNode::rchild. Referenced by AvlMap< KeyType, bool >::lookup(), and remove().

BaseAvlNode * BaseAvlTree::lookupGLE (  const BaseAvlNode &  key  )  [protected]

Similar to avl_lookup(), but returns the BaseAvlNode whose key is the greatest (according to provided comparator) key less than or equal to the search key. Definition at line 569 of file avl.cxx. References greatest(), and BaseAvlNode::rchild. Referenced by AvlMap< KeyType, bool >::lookupGLE().

void BaseAvlTree::remove (  BaseAvlNode &  node  )  [protected]

Remove a node from an AVL tree. On return, the node structure is no longer referenced by the tree (though it may be referenced by other user data structures). It is the caller's responsibility to deallocate the storage of the Node structure if appropriate. Definition at line 535 of file avl.cxx. References lookup(). Referenced by AvlMap< KeyType, bool >::remove(), and ~BaseAvlTree().

---

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

• avl.hxx
• avl.cxx

---