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

# APPSPACK_Cache_SplayTree.hpp

Go to the documentation of this file.

    00001 // $Id: APPSPACK_Cache_SplayTree.hpp,v 1.5 2003/11/26 16:27:11 tgkolda Exp $
    00002 // $Source: /space/CVS-Acro/acro/packages/appspack/appspack/src/APPSPACK_Cache_SplayTree.hpp,v $
    00003
    00004 //@HEADER
    00005 // ************************************************************************
    00006 //
    00007 //          APPSPACK: Asynchronous Parallel Pattern Search
    00008 //                 Copyright (2003) Sandia Corporation
    00009 //
    00010 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
    00011 // license for use of this work by or on behalf of the U.S. Government.
    00012 //
    00013 // This library is free software; you can redistribute it and/or modify
    00014 // it under the terms of the GNU Lesser General Public License as
    00015 // published by the Free Software Foundation; either version 2.1 of the
    00016 // License, or (at your option) any later version.
    00017 //
    00018 // This library is distributed in the hope that it will be useful, but
    00019 // WITHOUT ANY WARRANTY; without even the implied warranty of
    00020 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    00021 // Lesser General Public License for more details.
    00022 //
    00023 // You should have received a copy of the GNU Lesser General Public
    00024 // License along with this library; if not, write to the Free Software
    00025 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
    00026 // USA.                                                                           .
    00027 //
    00028 // Questions? Contact Tammy Kolda (tgkolda@sandia.gov)
    00029 //
    00030 // ************************************************************************
    00031 //@HEADER
    00032
    00038 #ifndef APPSPACK_CACHE_SPLAYTREE_HPP
    00039 #define APPSPACK_CACHE_SPLAYTREE_HPP
    00040
    00041 namespace APPSPACK {
    00042
    00043 namespace Cache
    00044 {
    00045
    00046 // Forward declaration
    00047 template <class Comparable> class SplayTree;
    00048 }
    00049 }
    00050
    00051 namespace APPSPACK {
    00052 namespace Cache {
    00053
    00062 template <class Comparable>
    00063 class SplayTreeNode
    00064 {
    00065
    00066 private:
    00067
    00069   SplayTreeNode() : left(NULL), right(NULL) {};
    00072   SplayTreeNode(const Comparable& e, SplayTreeNode* l = NULL, SplayTreeNode* r = NULL)
    00073     : element(e), left(l), right(r) {};
    00074
    00076   ~SplayTreeNode() {};
    00077
    00079   Comparable element;
    00081   SplayTreeNode* left;
    00083   SplayTreeNode* right;
    00084
    00086   friend class SplayTree<Comparable>;
    00087 };
    00088
    00142 template <class Comparable>
    00143 class SplayTree
    00144 {
    00145 public:
    00146
    00148   SplayTree();
    00150   ~SplayTree();
    00154   bool find(Comparable& x);
    00158   bool insert(const Comparable& x);
    00159
    00160 private:
    00161
    00174   void splay(const Comparable& x, SplayTreeNode<Comparable>*& r);
    00175
    00177   bool isEmpty();
    00178
    00180   SplayTreeNode<Comparable>* root;
    00181
    00182
    00183 };
    00184
    00185 template <class Comparable>
    00186 SplayTree<Comparable>::SplayTree()
    00187 {
    00188   root = NULL;
    00189 }
    00190
    00191 template <class Comparable>
    00192 SplayTree<Comparable>::~SplayTree()
    00193 {
    00194   // Keep deleting the root node until everything is gone.
    00195   SplayTreeNode<Comparable>* newroot;
    00196
    00197   while(!isEmpty()){
    00198     if(root->left == NULL)
    00199       newroot = root->right;
    00200     else{
    00201       // This trick for joining the left and right subtrees works because
    00202       // splaying on an element larger than any other in the subtree (as
    00203       // splay(root->element, root->left) does) moves the largest element
    00204       // in the subtree to the root of the subtree.
    00205       newroot = root->left;
    00206       splay(root->element, newroot);
    00207       newroot->right = root->right;
    00208     }
    00209     delete root;
    00210     root = newroot;
    00211   }
    00212 }
    00213
    00214 template <class Comparable>
    00215 bool SplayTree<Comparable>::find(Comparable& x)
    00216 {
    00217   // Find x in the tree.  If it is present, replace x with the matching
    00218   // node in the tree and return true.  Otherwise, return false.
    00219
    00220   if(isEmpty())
    00221     return false;
    00222
    00223   splay(x, root);
    00224   // If x is in the tree, it will be at the root.
    00225   if(x != root->element)
    00226     return false;
    00227   x.copyData(root->element);
    00228   return true;
    00229 }
    00230
    00231 template <class Comparable>
    00232 bool SplayTree<Comparable>::insert(const Comparable& x)
    00233 {
    00234   if (isEmpty())
    00235   {
    00236     root = new SplayTreeNode<Comparable>(x);
    00237     return true;
    00238   }
    00239
    00240   splay(x, root);
    00241   if (x < root->element)
    00242   {
    00243     SplayTreeNode<Comparable>* newNode = new SplayTreeNode<Comparable>(x);
    00244     newNode->left = root->left;
    00245     newNode->right = root;
    00246     root->left = NULL;
    00247     root = newNode;
    00248     return true;
    00249   }
    00250   else if (x > root->element)
    00251   {
    00252     SplayTreeNode<Comparable>* newNode = new SplayTreeNode<Comparable>(x);
    00253     newNode->right = root->right;
    00254     newNode->left = root;
    00255     root->right = NULL;
    00256     root = newNode;
    00257     return true;
    00258   }
    00259
    00260   // else x already in tree, do nothing
    00261   return false;
    00262 }
    00263
    00264 template <class Comparable>
    00265 void SplayTree<Comparable>::splay(const Comparable& x, SplayTreeNode<Comparable>*& r)
    00266 {
    00267   // header's left and right branches hold, respectively, the *right* and
    00268   // *left* subtrees of the reorganized tree.
    00269   SplayTreeNode<Comparable> header;
    00270
    00271   // SplayTreeNode being inspected in the main tree.
    00272   SplayTreeNode<Comparable> *current = r;
    00273
    00274   // SplayTreeNodes being used in the left and right subtrees.
    00275   SplayTreeNode<Comparable> *leftcur, *rightcur;
    00276   SplayTreeNode<Comparable> *temp;
    00277
    00278   if (r == NULL)
    00279     return;
    00280
    00281   leftcur = rightcur = &header;
    00282
    00283   for (;;){
    00284     if (x < current->element){
    00285       if (current->left == NULL)
    00286         break;
    00287       if (x < current->left->element){
    00288         // Rotate current with its left child.
    00289         temp = current->left;
    00290         current->left = temp->right;
    00291         temp->right = current;
    00292         current = temp;
    00293         if (current->left == NULL)
    00294           break;
    00295       }
    00296       // Place current in the tree of elements greater than x.
    00297       rightcur->left = current;
    00298       rightcur = current;
    00299       current = current->left;
    00300     }
    00301     else if (x > current->element){
    00302       if (current->right ==  NULL)
    00303         break;
    00304       if (x > current->right->element){
    00305         // Rotate current with its right child.
    00306         temp = current->right;
    00307         current->right = temp->left;
    00308         temp->left = current;
    00309         current = temp;
    00310         if (current->right == NULL)
    00311           break;
    00312       }
    00313       // Place current in the tree of elements less than x.
    00314         // Rotate current with its right child.
    00315       leftcur->right = current;
    00316       leftcur = current;
    00317       current = current->right;
    00318     }
    00319     else
    00320       break;
    00321   }
    00322
    00323   // Assemble the tree.
    00324   leftcur->right = current->left;
    00325   rightcur->left = current->right;
    00326   current->left = header.right;
    00327   current->right = header.left;
    00328   r = current;
    00329
    00330 }
    00331
    00332 template <class Comparable>
    00333 bool SplayTree<Comparable>::isEmpty()
    00334 {
    00335   return (root == NULL);
    00336 }
    00337
    00338 }
    00339 }
    00340
    00341 #endif

© Sandia Corporation | Site Contact | Privacy and Security

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