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.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 Fri Feb 16 10:33:34 2007 for APPSPACK 5.0.1 by doxygen 1.3.9.1 written by Dimitri van Heesch, © 1997-2002