RBTree< T, Comparator, key_t, KeyComparator > Class Template Reference

Implementation template for red-black tree class. More...

#include <RBTree.h>

Inheritance diagram for RBTree< T, Comparator, key_t, KeyComparator >:

Collaboration diagram for RBTree< T, Comparator, key_t, KeyComparator >:

List of all members.

Public Member Functions
virtual int	Compare (EntryBase *e1, EntryBase *e2)
	This method should be overloaded in derived class.
virtual int	Compare (EntryBase *e, void *key)
	This method should be overloaded in derived class.
T *	InsertProbe (T *obj, Entry *e)
	Try to insert an object in the tree.
T *	Insert (T *obj, Entry *e)
	Insert an object in the tree.
T *	Lookup (key_t &key)
	Lookup object by a key.
void	Delete (Entry *e)
	Delete a node by its entry in user object.
T *	Delete (key_t &key)
	Delete a node by its key.
T *	Lowest ()
	Get the object with the lowest value.
T *	Highest ()
	Get the object with the highest value.

---

Detailed Description

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>
class RBTree< T, Comparator, key_t, KeyComparator >

Implementation template for red-black tree class.

Usage example:

 class MyItem {
 public:

    int Compare(MyItem &item);
    int Compare(int key);
    typedef class RBTree<Item, &MyItem::Compare, int, &MyItem::Compare> MyTree;
 private:
    friend class RBTree<MyItem, &MyItem::Compare, int, &MyItem::Compare>;
    MyTree::Entry _rbEntry;
 };

 MyItem::MyTree tree;

Parameters:

T	Class for objects which are stored in a tree.
Comparator	method of class T which can be used to compare two objects. It should have the following prototype: int Compare(T &obj); Its obj argument is another object against this object should be compared. The method must return positive value if this object is greater than the provided one, negative value if it is less, and zero if they are equal.
key_t	Type for key.
KeyComparator	Method to compare object with a key value. The method must return positive value if key value is greater than this object value, negative value if it is less, and zero if they are equal. It should have the following prototype: int Compare(key_t &key);

---

Member Function Documentation

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>

virtual int RBTree< T, Comparator, key_t, KeyComparator >::Compare	(	EntryBase *	e1,
		EntryBase *	e2
	)		[inline, virtual]

This method should be overloaded in derived class.

It must compare two nodes.

Parameters:

e1	The first node to compare.
e2	The second node to compare.

Returns:

Positive value if e1 greater than e2, negative value if e1 less than e2, zero if e1 equal to e2.

Implements RBTreeBase.

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>

virtual int RBTree< T, Comparator, key_t, KeyComparator >::Compare	(	EntryBase *	e,
		void *	key
	)		[inline, virtual]

This method should be overloaded in derived class.

It must compare a node with a key.

Parameters:

e	Node to compare.
key	Pointer to a key.

Returns:

Positive value if key is greater than e, negative value if key is less than e, zero if key is equal to e.

Implements RBTreeBase.

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>

void RBTree< T, Comparator, key_t, KeyComparator >::Delete

(

Entry *

e

)

[inline]

Delete a node by its entry in user object.

Parameters:

e	Tree entry of a node to delete.

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>

T* RBTree< T, Comparator, key_t, KeyComparator >::Delete

(

key_t &

key

)

[inline]

Delete a node by its key.

Parameters:

key	Key of the node to delete.

Returns:

Corresponding object if found, 0 if no such object in the tree.

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>

T* RBTree< T, Comparator, key_t, KeyComparator >::Highest

(

)

[inline]

Get the object with the highest value.

Returns:

Object with the highest value, NULL if the tree is empty.

Reimplemented from RBTreeBase.

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>

T* RBTree< T, Comparator, key_t, KeyComparator >::Insert	(	T *	obj,
		Entry *	e
	)		[inline]

Insert an object in the tree.

The object is inserted only if there is no another object with the same key in the tree.

Parameters:

obj	Object to insert.
e	Pointer to the tree entry.

Returns:

Pointer to inserted object. It is either obj if the object was inserted or pointer to another existing object with the same key (obj is not inserted in such case).

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>

T* RBTree< T, Comparator, key_t, KeyComparator >::InsertProbe	(	T *	obj,
		Entry *	e
	)		[inline]

Try to insert an object in the tree.

The object is inserted only if there is no another object with the same key in the tree.

Parameters:

obj	Object to insert.
e	Pointer to the tree entry.

Returns:

Pointer to inserted object. It is either obj if the object was inserted or pointer to another existing object with the same key (obj is not inserted in such case).

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>

T* RBTree< T, Comparator, key_t, KeyComparator >::Lookup

(

key_t &

key

)

[inline]

Lookup object by a key.

Parameters:

key	Key for lookup.

Returns:

Pointer to found object, 0 if not found.

template<class T, int(T::*)(T &obj) Comparator, typename key_t, int(T::*)(key_t &key) KeyComparator>

T* RBTree< T, Comparator, key_t, KeyComparator >::Lowest

(

)

[inline]

Get the object with the lowest value.

Returns:

Object with the lowest value, NULL if the tree is empty.

Reimplemented from RBTreeBase.

---

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

• include/common/RBTree.h