AbstractSplayTree Class Template Reference

Implements an abstract class for defining the core operations of a top-down splay tree. More...

#include <AbstractSplayTree.h>

List of all members.

Public Methods
	AbstractSplayTree (const char *nameBuff="Unnamed")
	Constructor, which specifies a name for the tree.
virtual	~AbstractSplayTree ()
	Destructor.
bool	empty () const
	Returns true if the tree is empty and false otherwise.
	operator bool () const
	Returns true if the tree is not empty and false otherwise.
int	size () const
	Returns the size of the splay tree.
OrderSense	sense ()
	Return the value of Sense.
void	setSense (OrderSense sense_)
	Set the value of Sense.
void	splay (const KEY &key)
	Perform a splay operation starting from the root of the tree.
virtual T *	find_rank (int r)
	Return the item in the splay tree with rank r. More...
virtual T *	find (const KEY &key)
	Return the item in the splay tree with the given key. More...
T *	top ()
	Return the top of the splay tree.
virtual void	add (KEY &key)
	Add a key to the splay tree.
virtual void	add (KEY &key, T *&item)
	Add a key to the splay tree and return the splay tree item that contains it.
virtual void	remove (KEY &key, bool &status)
	Remove a splay tree item with the given key. More...
virtual void	remove (T *&item, bool &status)
	Remove a splay tree item. More...
virtual void	remove (T *&item, KEY &key, bool &status)
	Remove a splay tree item and return the item's key. More...
int	write (ostream &os)
	Write the splay tree to an output stream.
int	read (istream &is)
	Read the splay tree from an input stream.
int	rank (const KEY &key)
	Returns the rank of the top (0...size-1).
void	clear ()
	Empty out a splay tree.
Protected Methods
T *	exec_splay (const KEY *key, T *item)
	Search for an item with a given key on a tree rooted at item. More...
virtual T *	insert (KEY *key)
	Add a key to the tree.
virtual void	extract (T *item, bool &status)
	Remove a splay tree item. More...
Protected Attributes
T *	tree
	The current root of the splay tree.
OrderSense	Sense
	Specifies the ordering within the tree: increasing or decreasing.
const char *	name
	The name of the class instance.

---

Detailed Description

template<class T, class KEY>
class AbstractSplayTree< T, KEY >

Implements an abstract class for defining the core operations of a top-down splay tree.

This is adapted from code developed by D. Sleator, which itself is adapted from simple top-down splay, at the bottom of 669 of \cite [SleTar85 unknown reference! ]. Sleator's code can be aquired from

http://www-cgi.cs.cmu.edu/afs/cs/user/sleator/www/home.html

---

Member Function Documentation

template<class T, class KEY> T * AbstractSplayTree< T, KEY >::exec_splay (  const KEY *    key, T *    t )  [protected]

Search for an item with a given key on a tree rooted at item. If an item is found in the tree, it is splayed to the root. Otherwise, the item put at the root is the last one before NULL that would have been reached in a normal binary search. (It is a neighbor of i in the tree.) This method of splaying is very convenient for facilitating a variety of other operations.

template<class T, class KEY> void AbstractSplayTree< T, KEY >::extract (  T *    node, bool &    status )  [protected, virtual]

Remove a splay tree item. The status flag is true if the item was found and false otherwise.

template<class T, class KEY> virtual T* AbstractSplayTree< T, KEY >::find (  const KEY &    key )  [inline, virtual]

Return the item in the splay tree with the given key. Returns null if the tree is empty or if the item is not in the tree.

template<class T, class KEY> T * AbstractSplayTree< T, KEY >::find_rank (  int    r )  [virtual]

Return the item in the splay tree with rank r. Returns a null item if a bad rank value is passed in.

template<class T, class KEY> virtual void AbstractSplayTree< T, KEY >::remove (  T *&    item, KEY &    key, bool &    status )  [inline, virtual]

Remove a splay tree item and return the item's key. The status flag is true if the item was found and false otherwise.

template<class T, class KEY> virtual void AbstractSplayTree< T, KEY >::remove (  T *&    item, bool &    status )  [inline, virtual]

Remove a splay tree item. The status flag is true if the item was found and false otherwise.

template<class T, class KEY> virtual void AbstractSplayTree< T, KEY >::remove (  KEY &    key, bool &    status )  [inline, virtual]

Remove a splay tree item with the given key. The status flag is true if the key was found and false otherwise.

---

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

• AbstractSplayTree.h