- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# FMath/FMTree.h

Go to the documentation of this file.

    00001 /*
    00002     Copyright (C) 2005-2007 Feeling Software Inc.
    00003     Portions of the code are:
    00004     Copyright (C) 2005-2007 Sony Computer Entertainment America
    00005
    00006     MIT License: http://www.opensource.org/licenses/mit-license.php
    00007 */
    00008
    00014 #ifndef _FM_TREE_H_
    00015 #define _FM_TREE_H_
    00016
    00017 #ifndef _FM_ALLOCATOR_H_
    00018 #include "FMath/FMAllocator.h"
    00019 #endif // _FM_ALLOCATOR_H_
    00020
    00021 namespace fm
    00022 {
    00027     template <class _Kty, class _Ty>
    00028     class pair
    00029     {
    00030     public:
    00031         _Kty first;
    00032         _Ty second;
    00035         pair() : first(), second() {}
    00036
    00040         pair(const _Kty& f, const _Ty& s) : first(f), second(s) {}
    00041
    00044         pair(const pair& p) : first(p.first), second(p.second) {}
    00045
    00049         inline bool operator==(const pair& p) const { return p.first == first && p.second == second; }
    00050
    00054         inline bool operator!=(const pair& p) const { return p.first != first || p.second != second; }
    00055     };
    00056
    00064     template <class KEY, class DATA>
    00065     class tree
    00066     {
    00067     private:
    00068         typedef fm::pair<KEY, DATA> pair;
    00069
    00070         class node
    00071         {
    00072         public:
    00073             node* left;
    00074             node* right;
    00075             node* parent;
    00076
    00077             int32 weight;
    00078
    00079             pair data;
    00080
    00081         public:
    00082             node() : left(NULL), right(NULL), parent(NULL), weight(0) {}
    00083
    00084             void rotateLeft()
    00085             {
    00086                 node** parentLink = (parent->left == this) ? &parent->left : &parent->right;
    00087
    00088                 // detach right
    00089                 node* oldRight = right;
    00090
    00091                 // detach right's left and attach to the parent's right.
    00092                 node* right_left = right->left;
    00093                 right = right_left;
    00094                 if (right_left != NULL) right_left->parent = this;
    00095
    00096                 // attach the right to the double parent.
    00097                 oldRight->left = this;
    00098
    00099                 // attach the parent on the right's left.
    00100                 oldRight->parent = parent;
    00101                 parent = oldRight;
    00102                 (*parentLink) = oldRight;
    00103
    00104                 // adjust the weights
    00105                 weight = weight - 1 - (oldRight->weight > 0 ? oldRight->weight : 0);
    00106                 oldRight->weight = oldRight->weight - (0 > -weight ? 0 : -weight) - 1;
    00107             }
    00108
    00109             void rotateRight()
    00110             {
    00111                 node** parentLink = (parent->left == this) ? &parent->left : &parent->right;
    00112
    00113                 // detach left
    00114                 node* oldLeft = left;
    00115
    00116                 // detach left's right and attach to the parent's left.
    00117                 node* left_right = left->right;
    00118                 left = left_right;
    00119                 if (left_right != NULL) left_right->parent = this;
    00120
    00121                 // attach the parent on the left's right.
    00122                 oldLeft->right = this;
    00123
    00124                 // attach the left to the double parent.
    00125                 oldLeft->parent = parent;
    00126                 parent = oldLeft;
    00127                 (*parentLink) = oldLeft;
    00128
    00129                 // adjust the weights
    00130                 weight = weight + 1 + (0 > oldLeft->weight ? -oldLeft->weight : 0);
    00131                 oldLeft->weight = (oldLeft->weight + 1) + (0 > weight ? 0 : weight);
    00132             }
    00133
    00134 #ifdef TREE_DEBUG
    00135             intptr_t depth() const
    00136             {
    00137                 intptr_t leftDepth = left != NULL ? left->depth() : 0;
    00138                 intptr_t rightDepth = right != NULL ? right->depth() : 0;
    00139                 return max(leftDepth, rightDepth) + 1;
    00140             }
    00141
    00142             void is_correct()
    00143             {
    00144                 if (left != NULL) left->is_correct();
    00145                 if (right != NULL) right->is_correct();
    00146                 intptr_t leftDepth = left != NULL ? left->depth() : 0;
    00147                 intptr_t rightDepth = right != NULL ? right->depth() : 0;
    00148                 FUAssert(rightDepth - leftDepth == weight,);
    00149                 FUAssert(abs(weight) < 2,);
    00150             }
    00151 #endif // TREE_DEBUG
    00152         };
    00153
    00154     public:
    00155         class const_iterator;
    00156
    00161         class iterator
    00162         {
    00163         private:
    00164             friend class tree;
    00165             friend class const_iterator;
    00166             node* currentNode;
    00167
    00168         public:
    00170             iterator() {}
    00172             iterator(node* n) : currentNode(n) {}
    00174             iterator& operator=(const iterator& copy) { currentNode = copy.currentNode; return *this; }
    00175
    00179             inline bool operator==(const iterator& other) const { return other.currentNode == currentNode; }
    00180             inline bool operator==(const const_iterator& other) const;
    00185             inline bool operator!=(const iterator& other) const { return other.currentNode != currentNode; }
    00186             inline bool operator!=(const const_iterator& other) const;
    00190             iterator& operator++()
    00191             {
    00192                 // Go one right or one up.
    00193                 if (currentNode->right == NULL)
    00194                 {
    00195                     node* oldNode;
    00196                     do
    00197                     {
    00198                         oldNode = currentNode;
    00199
    00200                         // Go one up.
    00201                         // We control the root node, which is the only with parent == NULL.
    00202                         // if you crash here, you don't check for iterator == end() correctly.
    00203                         currentNode = currentNode->parent;
    00204                     }
    00205                     while (currentNode->right == oldNode && currentNode->parent != NULL);
    00206                 }
    00207                 else
    00208                 {
    00209                     // Go one right.
    00210                     currentNode = currentNode->right;
    00211
    00212                     // Go all the way left.
    00213                     while (currentNode->left != NULL) currentNode = currentNode->left;
    00214                 }
    00215                 return (*this);
    00216             }
    00217
    00220             iterator& operator--()
    00221             {
    00222                 // Go one left or one up.
    00223                 if (currentNode->left == NULL)
    00224                 {
    00225                     node* oldNode;
    00226                     do
    00227                     {
    00228                         oldNode = currentNode;
    00229
    00230                         // Go one up.
    00231                         // We control the root node, which is the only with parent == NULL.
    00232                         // if you crash here, you don't check for iterator == begin() correctly.
    00233                         currentNode = currentNode->parent;
    00234                     }
    00235                     while (currentNode->left == oldNode && currentNode->parent != NULL);
    00236                 }
    00237                 else
    00238                 {
    00239                     // Go one left.
    00240                     currentNode = currentNode->left;
    00241
    00242                     // Go all the way right.
    00243                     while (currentNode->right != NULL) currentNode = currentNode->right;
    00244                 }
    00245                 return (*this);
    00246             }
    00247
    00250             inline pair& operator*() { return currentNode->data; }
    00251             inline pair* operator->() { return &currentNode->data; }
    00252         };
    00253
    00258         class const_iterator
    00259         {
    00260         private:
    00261             friend class tree;
    00262             friend class iterator;
    00263             const node* currentNode;
    00264
    00265         public:
    00267             const_iterator() {}
    00270             const_iterator(const iterator& copy) : currentNode(copy.currentNode) {}
    00272             const_iterator(const node* n) : currentNode(n) {}
    00274             const_iterator& operator=(const iterator& copy) { currentNode = copy.currentNode; return *this; }
    00275             const_iterator& operator=(const const_iterator& copy) { currentNode = copy.currentNode; return *this; }
    00280             inline bool operator==(const iterator& other) const { return other.currentNode == currentNode; }
    00281             inline bool operator==(const const_iterator& other) const { return other.currentNode == currentNode; }
    00286             inline bool operator!=(const iterator& other) const { return other.currentNode != currentNode; }
    00287             inline bool operator!=(const const_iterator& other) const { return other.currentNode != currentNode; }
    00291             const_iterator& operator++()
    00292             {
    00293                 // Go one right or one up.
    00294                 if (currentNode->right == NULL)
    00295                 {
    00296                     const node* oldNode;
    00297                     do
    00298                     {
    00299                         oldNode = currentNode;
    00300
    00301                         // Go one up.
    00302                         // We control the root node, which is the only with parent == NULL.
    00303                         // if you crash here, you don't check for iterator == end() correctly.
    00304                         currentNode = currentNode->parent;
    00305                     }
    00306                     while (currentNode->right == oldNode && currentNode->parent != NULL);
    00307                 }
    00308                 else
    00309                 {
    00310                     // Go one right.
    00311                     currentNode = currentNode->right;
    00312
    00313                     // Go all the way left.
    00314                     while (currentNode->left != NULL) currentNode = currentNode->left;
    00315                 }
    00316                 return (*this);
    00317             }
    00318
    00321             const_iterator& operator--()
    00322             {
    00323                 // Go one left or one up.
    00324                 if (currentNode->left == NULL)
    00325                 {
    00326                     const node* oldNode;
    00327                     do
    00328                     {
    00329                         oldNode = currentNode;
    00330
    00331                         // Go one up.
    00332                         // We control the root node, which is the only with parent == NULL.
    00333                         // if you crash here, you don't check for iterator == end() correctly.
    00334                         currentNode = currentNode->parent;
    00335                     }
    00336                     while (currentNode->left == oldNode && currentNode->parent != NULL);
    00337                 }
    00338                 else
    00339                 {
    00340                     // Go one left.
    00341                     currentNode = currentNode->left;
    00342
    00343                     // Go all the way right.
    00344                     while (currentNode->right != NULL) currentNode = currentNode->right;
    00345                 }
    00346                 return (*this);
    00347             }
    00348
    00351             inline const pair& operator*() { return currentNode->data; }
    00352             inline const pair* operator->() { return &currentNode->data; }
    00353         };
    00354
    00355     private:
    00356         node* root;
    00357         size_t sized;
    00358
    00359     public:
    00361         tree() : root(NULL), sized(0)
    00362         {
    00363             root = (node*) fm::Allocate(sizeof(node));
    00364             fm::Construct(root);
    00365         }
    00366
    00368         ~tree()
    00369         {
    00370             clear();
    00371             root->data.first.~KEY();
    00372             root->data.second.~DATA();
    00373             fm::Release(root);
    00374             root = NULL;
    00375         }
    00376
    00379         inline iterator begin() { iterator it(root); return (root->right == NULL) ? it : ++it; }
    00380         inline const_iterator begin() const { const_iterator it(root); return (root->right == NULL) ? it : ++it; }
    00385         inline iterator end() { return iterator(root); }
    00386         inline const_iterator end() const { return const_iterator(root); }
    00390         inline iterator last() { node* n = root; while (n->right != NULL) n = n->right; return iterator(n); }
    00391         inline const_iterator last() const { const node* n = root; while (n->right != NULL) n = n->right; return const_iterator(n); }
    00399         iterator find(const KEY& key)
    00400         {
    00401             node* out = root->right;
    00402             while (out != NULL)
    00403             {
    00404                 if (key < out->data.first) out = out->left;
    00405                 else if (key == out->data.first) return iterator(out);
    00406                 else out = out->right;
    00407             }
    00408             return end();
    00409         }
    00410         inline const_iterator find(const KEY& key) const { return const_iterator(const_cast<tree<KEY, DATA>* >(this)->find(key)); }
    00418         iterator insert(const KEY& key, const DATA& data)
    00419         {
    00420             // First step: look for an already existing entry.
    00421             node** insertAt = &root->right,* parent = root;
    00422             while (*insertAt != NULL)
    00423             {
    00424                 parent = *insertAt;
    00425                 if (key < parent->data.first) insertAt = &parent->left;
    00426                 else if (key == parent->data.first)
    00427                 {
    00428                     parent->data.second = data;
    00429                     return iterator(parent);
    00430                 }
    00431                 else insertAt = &parent->right;
    00432             }
    00433
    00434             // Insert the new node.
    00435             node* n = ((*insertAt) = (node*) fm::Allocate(sizeof(node)));
    00436             fm::Construct(*insertAt); // could be get rid of this one? it would work for all pointer and primitive types..
    00437             n->parent = parent;
    00438             n->data.first = key;
    00439             n->data.second = data;
    00440             ++sized;
    00441
    00442             // Balance the tree.
    00443             parent->weight += (*insertAt == parent->right) ? 1 : -1;
    00444             node* it = parent;
    00445             while (it != root)
    00446             {
    00447                 // Check whether we need to balance this level.
    00448                 if (it->weight > 1)
    00449                 {
    00450                     if (it->right->weight < 0) it->right->rotateRight();
    00451                     it->rotateLeft();
    00452                     it = it->parent;
    00453                     break;
    00454                 }
    00455                 else if (it->weight < -1)
    00456                 {
    00457                     if (it->left->weight > 0) it->left->rotateLeft();
    00458                     it->rotateRight();
    00459                     it = it->parent;
    00460                     break;
    00461                 }
    00462                 else if (it->weight == 0) break; // no height change.
    00463
    00464                 // go up one level.
    00465                 it->parent->weight += (it == it->parent->right) ? 1 : -1;
    00466                 it = it->parent;
    00467             }
    00468
    00469 #ifdef TREE_DEBUG
    00470             root->right->is_correct();
    00471 #endif // TREE_DEBUG
    00472
    00473             return iterator(n);
    00474         }
    00475
    00481         inline DATA& operator[](const KEY& k) { iterator it = find(k); if (it != end()) return it->second; else { DATA d; return insert(k, d)->second; } }
    00482         inline const DATA& operator[](const KEY& k) const { return find(k)->second; }
    00486         inline void erase(const KEY& key) { iterator it = find(key); erase(it); }
    00487
    00490         inline void erase(const iterator& it)
    00491         {
    00492             node* n = it.currentNode;
    00493             if (n != root)
    00494             {
    00495                 node* release;
    00496                 if (n->left == NULL && n->right == NULL) release = n;
    00497                 else
    00498                 {
    00499                     // choose whether to reduce on the left or right.
    00500                     if (n->weight <= 0 && n->left != NULL)
    00501                     {
    00502                         // take out the left's rightmost node.
    00503                         release = n->left;
    00504                         while (release->right != NULL) release = release->right;
    00505                         n->data = release->data;
    00506
    00507                         // push up any left node on the rightmost node.
    00508                         if (release->left != NULL)
    00509                         {
    00510                             release->data = release->left->data;
    00511                             release = release->left;
    00512                         }
    00513                     }
    00514                     else
    00515                     {
    00516                         // take out the right's leftmost node.
    00517                         release = n->right;
    00518                         while (release->left != NULL) release = release->left;
    00519                         n->data = release->data;
    00520
    00521                         // push up any right node on the leftmost node.
    00522                         if (release->right != NULL)
    00523                         {
    00524                             release->data = release->right->data;
    00525                             release = release->right;
    00526                         }
    00527                     }
    00528                 }
    00529
    00530                 // Release the selected node and re-adjust its parent's weight.
    00531                 node* rebalance = release->parent;
    00532                 if (rebalance->left == release) { rebalance->left = NULL; ++rebalance->weight; }
    00533                 else { rebalance->right = NULL; --rebalance->weight; }
    00534                 release->data.first.~KEY();
    00535                 release->data.second.~DATA();
    00536                 fm::Release(release);
    00537                 --sized;
    00538
    00539                 // Rebalance the tree.
    00540                 node* it = rebalance;
    00541                 while (it != root)
    00542                 {
    00543                     // Check whether we need to balance this level.
    00544                     if (it->weight > 1)
    00545                     {
    00546                         if (it->right->weight < 0) it->right->rotateRight();
    00547                         it->rotateLeft();
    00548                         it = it->parent;
    00549                     }
    00550                     else if (it->weight < -1)
    00551                     {
    00552                         if (it->left->weight > 0) it->left->rotateLeft();
    00553                         it->rotateRight();
    00554                         it = it->parent;
    00555                     }
    00556                     if (it->weight != 0) break;
    00557
    00558                     // go up one level.
    00559                     it->parent->weight -= (it == it->parent->right) ? 1 : -1;
    00560                     it = it->parent;
    00561                 }
    00562             }
    00563
    00564 #ifdef TREE_DEBUG
    00565             if (root->right != NULL) root->right->is_correct();
    00566 #endif // TREE_DEBUG
    00567         }
    00568
    00571         inline bool empty() const { return sized == 0; }
    00572
    00575         inline size_t size() const { return sized; }
    00576
    00579         void clear()
    00580         {
    00581             // Need to delete all the nodes.
    00582             if (root->right != NULL)
    00583             {
    00584                 node* n = root->right;
    00585                 while (n != root)
    00586                 {
    00587                     if (n->left != NULL) n = n->left;
    00588                     else if (n->right != NULL) n = n->right;
    00589                     else
    00590                     {
    00591                         // destroy this node.
    00592                         node* release = n;
    00593                         n = n->parent;
    00594                         if (n->left == release) n->left = NULL;
    00595                         else if (n->right == release) n->right = NULL;
    00596                         release->data.first.~KEY();
    00597                         release->data.second.~DATA();
    00598                         fm::Release(release);
    00599                         --sized;
    00600                     }
    00601                 }
    00602                 root->right = NULL;
    00603             }
    00604         }
    00605
    00610         inline tree<KEY,DATA>& operator= (const tree<KEY,DATA>& copy)
    00611         {
    00612             clear();
    00613
    00614             // Function based on the iterator..
    00615             // Go one right or one up.
    00616             node* currentNode = copy.root;
    00617             node* cloneNode = root;
    00618             if (currentNode->right != NULL)
    00619             {
    00620                 do
    00621                 {
    00622                     if (currentNode->right == NULL)
    00623                     {
    00624                         const node* oldNode;
    00625                         do
    00626                         {
    00627                             oldNode = currentNode;
    00628
    00629                             // Go one up.
    00630                             // We control the root node, which is the only with parent == NULL.
    00631                             // if you crash here, you don't check for iterator == end() correctly.
    00632                             currentNode = currentNode->parent;
    00633                             cloneNode = cloneNode->parent;
    00634                         }
    00635                         while (currentNode->right == oldNode && currentNode->parent != NULL);
    00636                     }
    00637                     else
    00638                     {
    00639                         // Create and go one right.
    00640                         currentNode = currentNode->right;
    00641
    00642                         cloneNode->right = (node*) fm::Allocate(sizeof(node));
    00643                         fm::Construct(cloneNode->right);
    00644                         cloneNode->right->parent = cloneNode;
    00645                         cloneNode->right->data = currentNode->data;
    00646                         cloneNode->right->weight = currentNode->weight;
    00647                         ++sized;
    00648
    00649                         cloneNode = cloneNode->right;
    00650
    00651                         // Create and go one all the way left.
    00652                         while (currentNode->left != NULL)
    00653                         {
    00654                             currentNode = currentNode->left;
    00655
    00656                             cloneNode->left = (node*) fm::Allocate(sizeof(node));
    00657                             fm::Construct(cloneNode->left);
    00658                             cloneNode->left->parent = cloneNode;
    00659                             cloneNode->left->data = currentNode->data;
    00660                             cloneNode->left->weight = currentNode->weight;
    00661                             ++sized;
    00662
    00663                             cloneNode = cloneNode->left;
    00664                         }
    00665                     }
    00666                 }
    00667                 while (currentNode != copy.root);
    00668             }
    00669
    00670             return (*this);
    00671         }
    00672     };
    00673
    00674     template <class KEY, class DATA>
    00675     bool tree<KEY,DATA>::iterator::operator==(const const_iterator& other) const { return other.currentNode == currentNode; }
    00676     template <class KEY, class DATA>
    00677     bool tree<KEY,DATA>::iterator::operator!=(const const_iterator& other) const { return other.currentNode != currentNode; }
    00678
    00680     template <class _Kty>
    00681     class set : public fm::tree<_Kty, _Kty> {};
    00682
    00684     template <class _Kty, class _Ty>
    00685     class map : public fm::tree<_Kty, _Ty> {};
    00686 };
    00687
    00688 #endif // _FM_TREE_H_
    00689
    00690