SplayTree< Key, Data > Class Template Reference

A splay tree implementation. More...

#include <splaytree.h>

List of all members.

Public Member Functions
	SplayTree ()
	The default constructor.
	~SplayTree ()
	The destructor.
void	empty ()
	Empties the entire tree.
bool	insert (Key const &_key, Data const &_rec)
	Inserts data into the tree.
bool	exists (Key const &_key) const
	Tests whether a key is in the tree or not.
bool	replace (Key const &_key, Data const &_rec)
	Change the data at the given node.
bool	find (Key const &_key, Data &_data) const
	Finds a node in the tree and copies the data from that node to a specified location.
Data	find (Key const &_key) const
	Finds a node in the tree and returns the data at that node.
bool	erase (Key const &_key)
	Deletes a node from the tree, specified by the node's key.
size_t	size () const
	Indicates the size of the tree.
DArray< Data > *	ConvertToDArray () const
	Converts the tree data into a linearized DArray.
DArray< Key > *	ConvertIndexToDArray () const
	Converts the tree keys into a linearized DArray.
size_t	mem_usage () const
	Returns the overhead caused by the data structure.
Private Member Functions
	SplayTree (const SplayTree< Key, Data > &)
	Private copy constructor.
SplayTree< Key, Data > &	operator= (const SplayTree< Key, Data > &)
	Private assignment operator.

---

Detailed Description

template<class Key, class Data>
class CrissCross::Data::SplayTree< Key, Data >

A splay tree implementation.

This is a tree which does NOT allow duplicate keys.

---

Constructor & Destructor Documentation

SplayTree

(

const SplayTree< Key, Data > &

)

[private]

Private copy constructor.

If your code needs to invoke the copy constructor, you've probably written the code wrong. A tree copy is generally unnecessary, and in cases that it is, it can be achieved by other means.

---

Member Function Documentation

DArray<Key>* ConvertIndexToDArray

(

)

const

Converts the tree keys into a linearized DArray.

Returns:

A DArray containing the keys in the tree.

Warning:

Delete the returned DArray when done with it.

DArray<Data>* ConvertToDArray

(

)

const

Converts the tree data into a linearized DArray.

Returns:

A DArray containing the data of the tree.

Warning:

Delete the returned DArray when done with it.

void empty

(

)

Empties the entire tree.

Warning:

This won't free the memory occupied by the data, so the data must be freed separately. The preferred way to do this is to serialize the data into a DArray with ConvertToDArray() and then iterate through it to delete the data in whatever way is proper.

bool erase

(

Key const &

_key

)

Deletes a node from the tree, specified by the node's key.

Warning:

This won't free the memory occupied by the data, so the data must be freed separately.

Parameters:

_key

The key of the node to delete.

Returns:

True on success, false on failure

bool exists

(

Key const &

_key

)

const

Tests whether a key is in the tree or not.

Parameters:

_key

The key of the node to find.

Returns:

True if the key is in the tree, false if not.

Data find

(

Key const &

_key

)

const

Finds a node in the tree and returns the data at that node.

Parameters:

_key

The key of the node to find.

Returns:

The data at the node. NULL if not found.

Deprecated:

The return value of this function could be unpredictable if the contents of the table was anything but pointers or integers.

See also:

find

bool find	(	Key const &	_key,
		Data &	_data
	)			const

Finds a node in the tree and copies the data from that node to a specified location.

Parameters:

	_key	The key of the node to find.
	_data	On return, will contain the data at the node. If not found, _data does not change.

Returns:

True on success, false on failure.

bool insert	(	Key const &	_key,
		Data const &	_rec
	)

Inserts data into the tree.

Parameters:

	_key	The key of the data.
	_rec	The data to insert.

Returns:

True on success, false on failure.

size_t mem_usage

(

)

const

Returns the overhead caused by the data structure.

Returns:

Memory usage in bytes.

SplayTree<Key, Data>& operator=

(

const SplayTree< Key, Data > &

)

[private]

Private assignment operator.

If your code needs to invoke the assignment operator, you've probably written the code wrong. A tree copy is generally unnecessary, and in cases that it is, it can be achieved by other means.

bool replace	(	Key const &	_key,
		Data const &	_rec
	)

Change the data at the given node.

Parameters:

	_key	The key of the node to be modified.
	_rec	The data to insert.

Returns:

True on success, false on failure.

size_t size

(

)

const [inline]

Indicates the size of the tree.

Returns:

Size of the tree.