Sandia Home Sandia Home
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 doxygen 1.3.8 written by Dimitri van Heesch, © 1997-2002