Sandia Home Sandia Home
Main Page | Publications | Downloads | Configuration | Running the Code | Solver Parameters | FAQ | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

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

#include <APPSPACK_Cache_SplayTree.hpp>

Inheritance diagram for APPSPACK::Cache::SplayTree< Comparable >:

Inheritance graph
[legend]
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.

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 >::left, 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().

Referenced by APPSPACK::Cache::Manager::isCached().

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().

Referenced by APPSPACK::Cache::Manager::insert().

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:

 

© Sandia Corporation | Site Contact | Privacy and Security

Generated on Fri Feb 16 10:33:36 2007 for APPSPACK 5.0.1 by doxygen 1.3.9.1 written by Dimitri van Heesch, © 1997-2002