#include <APPSPACK_Cache_SplayTree.hpp>
A templated splay tree. The template takes is based on a Comparable class that must support the following five operations.
Comparable();
Called indirectly by splay, which creates a SplayTreeNode that doesn't actually have an element in it.
Comparable(const Comparable& source);
The copy constructor is used only when insert is called.
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.
bool operator!=(const Comparable& source);
This is used only when find is called.
bool operator<(const Comparable& source);
This is used by insert and repeatedly by splay.
bool operator>(const Comparable& source);
This is used by insert and repeatedly by splay.
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. |
|
Construct an empty splay tree. Definition at line 186 of file APPSPACK_Cache_SplayTree.hpp. References APPSPACK::Cache::SplayTree< Comparable >::root. |
|
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(). |
|
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(). |
|
Insert x into the splay tree if it is not already there.
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(). |
|
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(). |
|
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(). |
|
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(). |
© 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