Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

# APPSPACK::Cache::SplayTree< Comparable > Class Template Reference

`#include <APPSPACK_Cache_SplayTree.hpp>`

List of all members.

## Detailed Description

### template<class Comparable>
class APPSPACK::Cache::SplayTree< Comparable >

The splay tree is a binary storage structure.

A templated splay tree. The template takes is based on a Comparable class that must support the following five operations.

- Empty Constructor

  `Comparable();`

  Called indirectly by splay, which creates a SplayTreeNode that doesn't actually have an element in it.

- Copy Constructor

  `Comparable(const Comparable& source);`

  The copy constructor is used only when insert is called.

- Copy Data

  `void copyData(const Comparable& source);`

  The copy data is used only when find is called and a match is found in the splay tree. It is used to copy the relevant data from the matching entry to the input to find.

- Not Equal

  `bool operator!=(const Comparable& source);`

  This is used only when find is called.

- Less Than

  `bool operator<(const Comparable& source);`

  This is used by insert and repeatedly by splay.

- Greater Than

  `bool operator>(const Comparable& source);`

  This is used by insert and repeatedly by splay.

Author:
  H. Alton Patrick, Summer 2000.

  Tammy Kolda

Definition at line 143 of file APPSPACK_Cache_SplayTree.hpp.

## Public Member Functions
| SplayTree ()
| Construct an empty splay tree.
| ~SplayTree ()
| Destruct the splay tree.
bool | find (Comparable &x)
| Return true if x is in the splay tree. Furthermore, call x.copyData() with the splay tree's matching entry (which may not be exactly the same).
bool | insert (const Comparable &x)
| Insert x into the splay tree if it is not already there.
## Private Member Functions
void | splay (const Comparable &x, SplayTreeNode< Comparable > *&r)
| Re-organize the splay tree.
bool | isEmpty ()
| Return true if the splay tree is empty.
## Private Attributes
SplayTreeNode< Comparable > * | root
| Root node of the splay tree.

## Constructor & Destructor Documentation

template<class Comparable>
APPSPACK::Cache::SplayTree< Comparable >::SplayTree | ( |  | ) |

| Construct an empty splay tree. Definition at line 186 of file APPSPACK_Cache_SplayTree.hpp. References APPSPACK::Cache::SplayTree< Comparable >::root.

template<class Comparable>
APPSPACK::Cache::SplayTree< Comparable >::~SplayTree | ( |  | ) |

| Destruct the splay tree. Definition at line 192 of file APPSPACK_Cache_SplayTree.hpp. References APPSPACK::Cache::SplayTree< Comparable >::isEmpty(), APPSPACK::Cache::SplayTreeNode< Comparable >::right, APPSPACK::Cache::SplayTree< Comparable >::root, and APPSPACK::Cache::SplayTree< Comparable >::splay().

## Member Function Documentation

template<class Comparable>
bool APPSPACK::Cache::SplayTree< Comparable >::find | ( | Comparable & | x | ) |

| Return true if x is in the splay tree. Furthermore, call x.copyData() with the splay tree's matching entry (which may not be exactly the same). Definition at line 215 of file APPSPACK_Cache_SplayTree.hpp. References APPSPACK::Cache::SplayTree< Comparable >::isEmpty(), APPSPACK::Cache::SplayTree< Comparable >::root, and APPSPACK::Cache::SplayTree< Comparable >::splay().

template<class Comparable>
bool APPSPACK::Cache::SplayTree< Comparable >::insert | ( | const Comparable & | x | ) |

  | Insert x into the splay tree if it is not already there. Return values:
  | Returns | true if x is inserted into the tree, false otherwise.
Definition at line 232 of file APPSPACK_Cache_SplayTree.hpp. References APPSPACK::Cache::SplayTree< Comparable >::isEmpty(), APPSPACK::Cache::SplayTreeNode< Comparable >::left, APPSPACK::Cache::SplayTreeNode< Comparable >::right, APPSPACK::Cache::SplayTree< Comparable >::root, and APPSPACK::Cache::SplayTree< Comparable >::splay().

template<class Comparable>
void APPSPACK::Cache::SplayTree< Comparable >::splay | ( | const Comparable & | x,
|  | SplayTreeNode< Comparable > *& | r
| ) | `[private]`

| Re-organize the splay tree. If x is in the tree rooted at r, moves x to the root. If x is not in the tree rooted at r, then the node placed at the root is the one which would have been reached directly before x in a normal binary search. This top-down splay is based on D. Sleator's implementation, which can be found at ftp://ftp.cs.cmu.edu/user/sleator/splaying/top-down-splay.c. Definition at line 265 of file APPSPACK_Cache_SplayTree.hpp. References APPSPACK::Cache::SplayTreeNode< Comparable >::element, APPSPACK::Cache::SplayTreeNode< Comparable >::left, and APPSPACK::Cache::SplayTreeNode< Comparable >::right. Referenced by APPSPACK::Cache::SplayTree< Comparable >::find(), APPSPACK::Cache::SplayTree< Comparable >::insert(), and APPSPACK::Cache::SplayTree< Comparable >::~SplayTree().

template<class Comparable>
bool APPSPACK::Cache::SplayTree< Comparable >::isEmpty | ( |  | ) | `[private]`

| Return true if the splay tree is empty. Definition at line 333 of file APPSPACK_Cache_SplayTree.hpp. References APPSPACK::Cache::SplayTree< Comparable >::root. Referenced by APPSPACK::Cache::SplayTree< Comparable >::find(), APPSPACK::Cache::SplayTree< Comparable >::insert(), and APPSPACK::Cache::SplayTree< Comparable >::~SplayTree().

## Member Data Documentation

template<class Comparable>
SplayTreeNode<Comparable>* APPSPACK::Cache::SplayTree< Comparable >::root`[private]`

| Root node of the splay tree. Definition at line 180 of file APPSPACK_Cache_SplayTree.hpp. Referenced by APPSPACK::Cache::SplayTree< Comparable >::find(), APPSPACK::Cache::SplayTree< Comparable >::insert(), APPSPACK::Cache::SplayTree< Comparable >::isEmpty(), APPSPACK::Cache::SplayTree< Comparable >::SplayTree(), and APPSPACK::Cache::SplayTree< Comparable >::~SplayTree().

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

- APPSPACK_Cache_SplayTree.hpp

© Sandia Corporation | Site Contact | Privacy and Security

Generated on Wed Dec 14 18:41:05 2005 for APPSPACK 4.0.2 by 1.3.8 written by Dimitri van Heesch, © 1997-2002