AvlMap< KeyType, ValueType > Class Template Reference

#include <avl.hxx>

Inheritance diagram for AvlMap< KeyType, ValueType >:

List of all members.

Public Types
typedef AvlMapNode< KeyType, ValueType >	NodeType
typedef AvlNode< KeyType >	KeyNodeType
typedef int(*	AvlIterFunc )(NodeType *)
Public Member Functions
	AvlMap ()
	~AvlMap ()
bool	contains (const KeyType &key)
void	insert (const KeyType &key, const ValueType &v)
NodeType *	choose ()
NodeType *	least ()
NodeType *	greatest ()
void	remove (NodeType &node)
NodeType *	lookup (const KeyNodeType &key)
NodeType *	lookup (const KeyType &key)
NodeType *	lookupGLE (const NodeType &key)
NodeType *	lookupGLE (KeyType key)
void	iterate (AvlIterFunc avlFunc)

---

Detailed Description

template<typename KeyType, typename ValueType>
class AvlMap< KeyType, ValueType >

Definition at line 316 of file avl.hxx.

---

Member Typedef Documentation

template<typename KeyType, typename ValueType> typedef int(* AvlMap< KeyType, ValueType >::AvlIterFunc)(NodeType *)

Reimplemented from BaseAvlTree. Definition at line 420 of file avl.hxx.

template<typename KeyType, typename ValueType> typedef AvlNode<KeyType> AvlMap< KeyType, ValueType >::KeyNodeType

Definition at line 319 of file avl.hxx.

template<typename KeyType, typename ValueType> typedef AvlMapNode<KeyType, ValueType> AvlMap< KeyType, ValueType >::NodeType

Reimplemented in AvlSet< KeyType >, AvlSet< MutName >, AvlSet< AvlPtrWrap< DiffToken > >, and AvlSet< TrueName >. Definition at line 318 of file avl.hxx.

---

Constructor & Destructor Documentation

template<typename KeyType, typename ValueType> AvlMap< KeyType, ValueType >::AvlMap (   )  [inline]

Definition at line 321 of file avl.hxx.

template<typename KeyType, typename ValueType> AvlMap< KeyType, ValueType >::~AvlMap (   )  [inline]

Definition at line 325 of file avl.hxx.

---

Member Function Documentation

template<typename KeyType, typename ValueType> NodeType* AvlMap< KeyType, ValueType >::choose (   )  [inline]

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 from BaseAvlTree. Definition at line 345 of file avl.hxx.

template<typename KeyType, typename ValueType> bool AvlMap< KeyType, ValueType >::contains (  const KeyType &  key  )  [inline]

Definition at line 329 of file avl.hxx. Referenced by mark_mutname(), and mark_truename().

template<typename KeyType, typename ValueType> NodeType* AvlMap< KeyType, ValueType >::greatest (   )  [inline]

Returns the least node in the avl tree (if any) or NULL. The returned node remains in the tree. Reimplemented from BaseAvlTree. Definition at line 359 of file avl.hxx.

template<typename KeyType, typename ValueType> void AvlMap< KeyType, ValueType >::insert (  const KeyType &  key, const ValueType &  v )  [inline]

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 337 of file avl.hxx. Referenced by AvlSet< TrueName >::insert().

template<typename KeyType, typename ValueType> void AvlMap< KeyType, ValueType >::iterate (  AvlIterFunc  avlFunc  )  [inline]

Reimplemented from BaseAvlTree. Definition at line 423 of file avl.hxx.

template<typename KeyType, typename ValueType> NodeType* AvlMap< KeyType, ValueType >::least (   )  [inline]

Returns the least node in the avl tree (if any) or NULL. The returned node remains in the tree. Reimplemented from BaseAvlTree. Definition at line 352 of file avl.hxx.

template<typename KeyType, typename ValueType> NodeType* AvlMap< KeyType, ValueType >::lookup (  const KeyType &  key  )  [inline]

Definition at line 399 of file avl.hxx.

template<typename KeyType, typename ValueType> NodeType* AvlMap< KeyType, ValueType >::lookup (  const KeyNodeType &  key  )  [inline]

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 395 of file avl.hxx. Referenced by AvlMap< KeyType, bool >::contains(), TokenSet::intern(), and AvlMap< KeyType, bool >::lookup().

template<typename KeyType, typename ValueType> NodeType* AvlMap< KeyType, ValueType >::lookupGLE (  KeyType  key  )  [inline]

Definition at line 411 of file avl.hxx.

template<typename KeyType, typename ValueType> NodeType* AvlMap< KeyType, ValueType >::lookupGLE (  const NodeType &  key  )  [inline]

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 407 of file avl.hxx. Referenced by AvlMap< KeyType, bool >::lookupGLE().

template<typename KeyType, typename ValueType> void AvlMap< KeyType, ValueType >::remove (  NodeType &  node  )  [inline]

Remove a node from an AVL tree. On return, the node structure has been freed. Definition at line 367 of file avl.hxx. Referenced by AvlSet< TrueName >::remove().

---

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

• avl.hxx

---