| //##################################################################### |
| // Copyright 2004, Geoffrey Irving, Frank Losasso, Andrew Selle. |
| // This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt. |
| //##################################################################### |
| // Class SPLAY_TREE |
| //##################################################################### |
| #ifndef __SPLAY_TREE__ |
| #define __SPLAY_TREE__ |
| |
| #include <string> |
| #include <iostream> |
| #include <assert.h> |
| #include "SPLAY_TREE_NODE.h" |
| namespace PhysBAM |
| { |
| |
| template<class T, class TV> |
| class SPLAY_TREE |
| { |
| public: |
| int m; |
| mutable SPLAY_TREE_NODE<T, TV>* root; |
| static const T* goal_key; |
| |
| SPLAY_TREE() |
| : m (0), root (0) |
| {} |
| |
| ~SPLAY_TREE() |
| { |
| delete root; |
| } |
| |
| void Clean_Up_Memory() |
| { |
| delete root; |
| root = 0; |
| m = 0; |
| } |
| |
| bool Find (const T& key) const |
| { |
| return !Splay_Equal (key); |
| } |
| |
| bool Find (const T& key, TV& value) const |
| { |
| if (Splay_Equal (key)) return false; |
| |
| value = root->value; |
| return true; |
| } |
| |
| void Set (const T& key, const TV& value) |
| { |
| if (!root) |
| { |
| root = new SPLAY_TREE_NODE<T, TV> (0, 0, key, value); |
| m++; |
| } |
| else |
| { |
| int cut = Splay_Equal (key); |
| |
| if (cut == 0) root->value = value; |
| else if (cut < 0) |
| { |
| SPLAY_TREE_NODE<T, TV>* old = root; |
| root = new SPLAY_TREE_NODE<T, TV> (old->left, old, key, value); |
| old->left = 0; |
| m++; |
| } |
| else |
| { |
| SPLAY_TREE_NODE<T, TV>* old = root; |
| root = new SPLAY_TREE_NODE<T, TV> (old, old->right, key, value); |
| old->right = 0; |
| m++; |
| } |
| } |
| } |
| |
| bool Remove (const T& key, TV& value) |
| { |
| if (Splay_Equal (key)) return false; |
| |
| value = root->value; |
| Remove_Root(); |
| return true; |
| } |
| |
| static void Iterator_Print (std::ostream* output_stream, SPLAY_TREE_NODE<T, TV>* node) |
| { |
| *output_stream << node->key << " (with value '" << node->value << "')\n"; |
| } |
| |
| template<class T2> void Iterate (T2 data, void (*f) (T2, SPLAY_TREE_NODE<T, TV>*)) |
| { |
| if (root) root->Iterate (data, f); |
| } |
| |
| private: |
| static int Cut_Equal (const T& key) |
| { |
| return *goal_key < key ? -1 : *goal_key == key ? 0 : 1; |
| } |
| |
| int Splay_Equal (const T& key) const |
| { |
| goal_key = &key; |
| return Splay (Cut_Equal, root); |
| } |
| |
| void Remove_Root() |
| { |
| assert (root); |
| SPLAY_TREE_NODE<T, TV> *left = root->left, *old = root; |
| |
| if (!left) root = old->right; |
| else |
| { |
| Splay_Max (left); |
| left->right = old->right; |
| root = left; |
| } |
| |
| old->left = old->right = 0; |
| delete old; |
| m--; |
| } |
| |
| //##################################################################### |
| int Splay (int (*cut) (const T&), SPLAY_TREE_NODE<T, TV>*& tree) const; |
| void Splay_Min (SPLAY_TREE_NODE<T, TV>*& tree) const; |
| void Splay_Max (SPLAY_TREE_NODE<T, TV>*& tree) const; |
| //##################################################################### |
| }; |
| template<> inline int SPLAY_TREE<std::string, int>::Cut_Equal (const std::string& key) |
| { |
| return goal_key->compare (key); |
| } |
| template<> inline int SPLAY_TREE<std::string, std::string>::Cut_Equal (const std::string& key) |
| { |
| return goal_key->compare (key); |
| } |
| |
| template<class T, class TV> |
| std::ostream& operator<< (std::ostream& output_stream, SPLAY_TREE<T, TV>& tree) |
| { |
| tree.Iterate (&output_stream, SPLAY_TREE<T, TV>::Iterator_Print); |
| return output_stream; |
| } |
| } |
| #endif |