Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# deBST.hpp

Go to the documentation of this file.

    00001 ///////////////////////////////////////////////////////////////////////////////
    00002 /// @file deBST.hpp
    00003 ///
    00004 /// @brief Templated Binary Search Tree with chaining
    00005 ///
    00006 /// @author Assassin
    00007 ///
    00008 /// This file is the intellectual property of Novus Delta, LLC.. Usage of the
    00009 /// contents of this file is subject to the Destiny3D Member License which
    00010 /// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
    00011 ///
    00012 /// This file is distributed "AS IS" without warranty of any kind.  Novus
    00013 /// Delta, LLC. does not guarantee the fitness of the contents of this file
    00014 /// for any particular purpose.
    00015 ///
    00016 /// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
    00017 ///
    00018 /// <hr>
    00019 ///                                 Change History
    00020 /// <hr>
    00021 ///
    00022 /// @date Apr 2002
    00023 /// @author Assassin
    00024 /// @remarks Creation
    00025 ///
    00026 ///////////////////////////////////////////////////////////////////////////////
    00027
    00028 #ifndef DEBST_HPP
    00029 #define DEBST_HPP
    00030
    00031 #include "deList.hpp"
    00032
    00033 #pragma warning (disable : 4710)
    00034
    00035 /// templated binary tree storage class
    00036 template <class T, long N>
    00037 class deTBST
    00038 {
    00039 private:
    00040     class TBSTNode
    00041     {
    00042     public:
    00043         TBSTNode(const T & ref, const DWORD Val[N])
    00044             :Data(ref), Left(NULL), Right(NULL), Parent(NULL), Chain(NULL), BST(NULL)
    00045         {
    00046             memcpy(Value, Val, sizeof(DWORD)*N);
    00047         }
    00048         TBSTNode(const TBSTNode & ref)
    00049             :Data(ref.Data), Left(NULL), Right(NULL), Parent(NULL), Chain(NULL), BST(NULL)
    00050         {
    00051             memcpy(Value, ref.Value, sizeof(DWORD)*N);
    00052         }
    00053         ~TBSTNode()
    00054             {}
    00055         bool operator ==(const DWORD Val[N])
    00056         {
    00057             for (int i = 0; i < N; i++)
    00058             {
    00059                 if (Value[i] != Val[i])
    00060                     return false;
    00061             }
    00062             return true;
    00063         }
    00064         bool operator >(const DWORD Val[N])
    00065         {
    00066             for (int i = 0; i < N; i++)
    00067             {
    00068                 if (Value[i] <= Val[i])
    00069                     return false;
    00070             }
    00071             return true;
    00072         }
    00073         bool operator <(const DWORD Val[N])
    00074         {
    00075             for (int i = 0; i < N; i++)
    00076             {
    00077                 if (Value[i] >= Val[i])
    00078                     return false;
    00079             }
    00080             return true;
    00081         }
    00082         void Destroy()
    00083         {
    00084             if (Left)
    00085                 Left->Destroy();
    00086             if (Right)
    00087                 Right->Destroy();
    00088             if (Chain)
    00089                 Chain->Destroy();
    00090             delete this;
    00091         }
    00092         void AddDataToList(deTList <T*> &list)
    00093         {
    00094             list.AddElement(&Data);
    00095             if (Chain)
    00096                 Chain->AddDataToList(list);
    00097             if (Left)
    00098                 Left->AddDataToList(list);
    00099             if (Right)
    00100                 Right->AddDataToList(list);
    00101         }
    00102         void AddValueToList(deTList <DWORD> &list)
    00103         {
    00104             list.AddElement(Value);
    00105             if (Left)
    00106                 Left->AddValueToList(list);
    00107             if (Right)
    00108                 Right->AddValueToList(list);
    00109         }
    00110
    00111         TBSTNode *Left, *Right;
    00112         TBSTNode *Parent, *Chain;
    00113         deTBST * BST;
    00114         T Data;
    00115         DWORD Value[N];
    00116 /*      //Temp fix for the crash when deleting
    00117         void *operator new (size_t Size)
    00118         {
    00119             return malloc(Size);
    00120         }
    00121         void operator delete (void *p)
    00122         {
    00123             free(p);
    00124             return;
    00125         }
    00126 */  };
    00127
    00128 public:
    00129     class iterator
    00130     {
    00131     private:
    00132         friend class deTBST<T,N>;
    00133         TBSTNode* m_Node;
    00134     protected:
    00135         iterator(TBSTNode* node) : m_Node(node) {}
    00136     public:
    00137         iterator() : m_Node(NULL) {}
    00138         ~iterator() {}
    00139         T& operator*() const
    00140         {
    00141             DE_ASSERT (m_Node != 0);
    00142             return m_Node->Data;
    00143         }
    00144         T* operator->() const { return &operator*(); }
    00145         void operator++()
    00146         {
    00147             TBSTNode *Node = m_Node;
    00148             if (Node->Chain)
    00149             {
    00150                 Node = Node->Chain;
    00151             }
    00152             else
    00153             {
    00154                 while (Node->Parent && Node->Parent->Chain == Node)
    00155                     Node = Node->Parent;
    00156                 if (Node->Right)
    00157                 {
    00158                     Node = Node->Right;
    00159                     while (Node->Left)
    00160                         Node = Node->Left;
    00161                 }
    00162                 else if (Node->Parent)
    00163                 {
    00164                     while (Node && Node->Parent && Node == Node->Parent->Chain)
    00165                         Node = Node->Parent;
    00166                     while (Node && Node->Parent)
    00167                     {
    00168                         if (Node->Parent->Left == Node)
    00169                         {
    00170                             Node = Node->Parent;
    00171                             break;
    00172                         }
    00173                         else
    00174                         {
    00175                             Node = Node->Parent;
    00176                             if (!Node->Parent)
    00177                                 Node = NULL;
    00178                         }
    00179                     }
    00180                 }
    00181                 else
    00182                     Node = NULL;
    00183             }
    00184             m_Node = Node;
    00185         }
    00186         //void operator--() { m_Node = m_Node->Prev; }
    00187         bool operator==(const iterator & other) const
    00188         { return m_Node == other.m_Node; }
    00189         bool operator!=(const iterator & other) const
    00190         { return m_Node != other.m_Node; }
    00191     };
    00192
    00193 private:
    00194     TBSTNode * m_Root;
    00195     long m_Length;
    00196
    00197 public:
    00198     deTBST()
    00199     {
    00200         m_Root = NULL;
    00201         m_Length = 0;
    00202     }
    00203     deTBST(const deTBST <T, N> & ref)
    00204     {
    00205         m_Root = NULL;
    00206         m_Length = 0;
    00207
    00208         TBSTNode * Node = ref.m_Root;
    00209         while(Node)
    00210         {
    00211             AddElement(Node->Data, Node->Value);
    00212             Node = Node->Left;
    00213         }
    00214     }
    00215     const deTBST <T, N> & operator=(const deTBST <T, N> & ref)
    00216     {
    00217         // not implemented
    00218         throw;
    00219
    00220         EmptyBST();
    00221
    00222         return *this;
    00223     }
    00224     ~deTBST()
    00225     {
    00226         EmptyBST();
    00227     }
    00228
    00229     void EmptyBST()
    00230     {
    00231         if (m_Root)
    00232             m_Root->Destroy();
    00233         m_Root = 0;
    00234         m_Length = 0;
    00235     }
    00236
    00237     void* GetRoot(T* &obj, DWORD value[N]) const
    00238     {
    00239         TBSTNode *Node = m_Root;
    00240         obj = NULL;
    00241         if (!Node)
    00242         {
    00243             return NULL;
    00244         }
    00245         obj = &(Node->Data);
    00246         if (value)
    00247             memcpy(value, Node->Value, N);
    00248         return Node;
    00249     }
    00250     void* FindValue(const DWORD Val[N], T* &obj) const
    00251     {
    00252         TBSTNode *Node = m_Root;
    00253         while (Node)
    00254         {
    00255             if (*Node == Val)
    00256                 break;
    00257             if (*Node > Val)
    00258                 Node = Node->Left;
    00259             else
    00260                 Node = Node->Right;
    00261         }
    00262         obj = NULL;
    00263         if (!Node)
    00264         {
    00265             return NULL;
    00266         }
    00267         if (Node)
    00268             obj = &(Node->Data);
    00269         return Node;
    00270     }
    00271     void* FindValue(const DWORD Val[N], T & obj) const
    00272     {
    00273         T * objptr;
    00274         void * ptr;
    00275         ptr = FindValue(Val, objptr);
    00276         if (objptr)
    00277             obj = *objptr;
    00278         return ptr;
    00279     }
    00280     void * GetLeftMost(T* &obj, DWORD value[N])
    00281     {
    00282         TBSTNode *Node = (TBSTNode*)m_Root;
    00283         obj = NULL;
    00284         if (!Node)
    00285         {
    00286             return NULL;
    00287         }
    00288         while (Node->Left)
    00289             Node = Node->Left;
    00290         if (Node)
    00291         {
    00292             obj = &(Node->Data);
    00293             if (value)
    00294                 memcpy(value, Node->Value, N);
    00295         }
    00296         return Node;
    00297     }
    00298     void * GetLeftMostLeaf(T* &obj, DWORD value[N])
    00299     {
    00300         TBSTNode *Node = (TBSTNode*)m_Root;
    00301         obj = NULL;
    00302         if (!Node)
    00303         {
    00304             return NULL;
    00305         }
    00306         while (Node->Left || Node->Right)
    00307         {
    00308             if (Node->Left)
    00309                 Node = Node->Left;
    00310             Node = Node->Right;
    00311         }
    00312         if (Node)
    00313         {
    00314             obj = &(Node->Data);
    00315             if (value)
    00316                 memcpy(value, Node->Value, N);
    00317         }
    00318         return Node;
    00319     }
    00320     void * GetLeftMost(T &obj, DWORD value[N])
    00321     {
    00322         T * objptr;
    00323         void * ptr;
    00324         ptr = GetLeftMost(objptr, value);
    00325         if (objptr)
    00326             obj = *objptr;
    00327         return ptr;
    00328     }
    00329     void * GetNextRight(void * current, T* &obj, DWORD value[N])
    00330     {
    00331         TBSTNode *Node = (TBSTNode*)current;
    00332         obj = NULL;
    00333         if (!Node)
    00334         {
    00335             return NULL;
    00336         }
    00337         if (Node->Right)
    00338         {
    00339             Node = Node->Right;
    00340             while (Node->Left)
    00341                 Node = Node->Left;
    00342         }
    00343         else if (Node->Parent)
    00344         {
    00345             while (Node && Node->Parent && Node == Node->Parent->Chain)
    00346                 Node = Node->Parent;
    00347             while (Node && Node->Parent)
    00348             {
    00349                 if (Node->Parent->Left == Node)
    00350                 {
    00351                     Node = Node->Parent;
    00352                     break;
    00353                 }
    00354                 else
    00355                 {
    00356                     Node = Node->Parent;
    00357                     if (!Node->Parent)
    00358                         Node = NULL;
    00359                 }
    00360             }
    00361         }
    00362         else
    00363             Node = NULL;
    00364         if (Node)
    00365         {
    00366             obj = &(Node->Data);
    00367             if (value)
    00368                 memcpy(value, Node->Value, N);
    00369         }
    00370         return Node;
    00371     }
    00372     void * GetNextRight(void * current, T &obj, DWORD value[N])
    00373     {
    00374         T * objptr;
    00375         void * ptr;
    00376         ptr = GetNextRight(current, objptr, value);
    00377         if (objptr)
    00378             obj = *objptr;
    00379         return ptr;
    00380     }
    00381     void* GetNextChain(void* current, T* &obj) const
    00382     {
    00383         TBSTNode *Node = (TBSTNode*)current;
    00384         obj = NULL;
    00385         if (!Node || !Node->Chain)
    00386         {
    00387             return NULL;
    00388         }
    00389         Node = Node->Chain;
    00390         if (Node)
    00391             obj = &(Node->Data);
    00392         return Node;
    00393     }
    00394     void* GetNextChain(void* current, T & obj) const
    00395     {
    00396         T * objptr;
    00397         void * ptr;
    00398         ptr = GetNextChain(current, objptr);
    00399         if (objptr)
    00400             obj = *objptr;
    00401         return ptr;
    00402     }
    00403     void* AddElement(const T & data, const DWORD Val[N])
    00404     {
    00405         TBSTNode *Node, *NewNode = new TBSTNode(data, Val);
    00406         if (!NewNode)
    00407             return NULL;
    00408
    00409         NewNode->BST = this;
    00410         m_Length++;
    00411         if (m_Root == NULL)
    00412             m_Root = NewNode;
    00413         else
    00414         {
    00415             Node = m_Root;
    00416             while (Node != NULL)
    00417             {
    00418                 if (*Node == Val)
    00419                 {
    00420                     while (Node->Chain != NULL)
    00421                         Node = Node->Chain;
    00422                     Node->Chain = NewNode;
    00423                     NewNode->Parent = Node;
    00424                     break;
    00425                 }
    00426                 else
    00427                 if (*Node > Val)
    00428                 {
    00429                     if (Node->Left)
    00430                     {
    00431                         Node = Node->Left;
    00432                     }
    00433                     else
    00434                     {
    00435                         Node->Left = NewNode;
    00436                         NewNode->Parent = Node;
    00437                         break;
    00438                     }
    00439                 }
    00440                 else
    00441                 {
    00442                     if (Node->Right)
    00443                     {
    00444                         Node = Node->Right;
    00445                     }
    00446                     else
    00447                     {
    00448                         Node->Right = NewNode;
    00449                         NewNode->Parent = Node;
    00450                         break;
    00451                     }
    00452                 }
    00453             }
    00454         }
    00455
    00456         return NewNode;
    00457     }
    00458     static void StaticRemoveElement(void * ptr)
    00459     {
    00460         TBSTNode * Node = (TBSTNode*)ptr;
    00461         if (Node->BST)
    00462             Node->BST->RemoveElement(ptr);
    00463     }
    00464 //#pragma todo (make sure RemoveElement really works) // I think it does
    00465     deBoolean RemoveElement(void * ptr)
    00466     {
    00467         TBSTNode * Node = (TBSTNode*)ptr;
    00468         if (Node == NULL)
    00469             return deFALSE;
    00470
    00471         // if we have a chain, can just shift the next link up into this node's spot
    00472         if (Node->Chain)
    00473         {
    00474             // point the chain at our left child and the child at the chain
    00475             if (Node->Left)
    00476             {
    00477                 Node->Chain->Left = Node->Left;
    00478                 Node->Left->Parent = Node->Chain;
    00479             }
    00480             // point the chain at our right child and the child at the chain
    00481             if (Node->Right)
    00482             {
    00483                 Node->Chain->Right = Node->Right;
    00484                 Node->Right->Parent = Node->Chain;
    00485             }
    00486             // if we aren't the root, then the parent needs to update its linkage
    00487             if (Node->Parent)
    00488             {
    00489                 Node->Chain->Parent = Node->Parent;
    00490                 if (Node->Parent->Chain == Node)
    00491                 {
    00492                     Node->Parent->Chain = Node->Chain;
    00493                 }
    00494                 else if (Node->Parent->Left == Node)
    00495                 {
    00496                     Node->Parent->Left = Node->Chain;
    00497                 }
    00498                 else if (Node->Parent->Right == Node)
    00499                 {
    00500                     Node->Parent->Right = Node->Chain;
    00501                 }
    00502             }
    00503             else
    00504                 m_Root = Node->Chain;
    00505         }
    00506         else if (Node->Left || Node->Right)
    00507         {
    00508             // we have children
    00509             if (Node->Right == NULL)
    00510             {
    00511                 // only have a left node
    00512                 Node->Left->Parent = Node->Parent;
    00513                 if (Node->Parent)
    00514                 {
    00515                     if (Node->Parent->Chain == Node)
    00516                     {
    00517                         Node->Parent->Chain = Node->Left;
    00518                     }
    00519                     else if (Node->Parent->Left == Node)
    00520                     {
    00521                         Node->Parent->Left = Node->Left;
    00522                     }
    00523                     else if (Node->Parent->Right == Node)
    00524                     {
    00525                         Node->Parent->Right = Node->Left;
    00526                     }
    00527                 }
    00528                 else
    00529                     m_Root = Node->Left;
    00530             }
    00531             else if (Node->Left == NULL)
    00532             {
    00533                 // only have a right node
    00534                 Node->Right->Parent = Node->Parent;
    00535                 if (Node->Parent)
    00536                 {
    00537                     if (Node->Parent->Chain == Node)
    00538                     {
    00539                         Node->Parent->Chain = Node->Right;
    00540                     }
    00541                     else if (Node->Parent->Left == Node)
    00542                     {
    00543                         Node->Parent->Left = Node->Right;
    00544                     }
    00545                     else if (Node->Parent->Right == Node)
    00546                     {
    00547                         Node->Parent->Right = Node->Right;
    00548                     }
    00549                 }
    00550                 else
    00551                     m_Root = Node->Right;
    00552             }
    00553             else
    00554             {
    00555                 // have two children. This is the "Nasty Case"
    00556                 TBSTNode * tempNode = Node->Right;
    00557                 while (tempNode->Left)
    00558                 {
    00559                     tempNode = tempNode->Left;
    00560                 }
    00561                 // now we have the smallest value that's greater than value in 'Node'
    00562                 {
    00563                     // first move its right child into place
    00564                     if (tempNode->Right)
    00565                         tempNode->Right->Parent = tempNode->Parent;
    00566                     if (Node->Parent)
    00567                     {
    00568                         if (tempNode->Parent->Chain == tempNode)
    00569                         {
    00570                             tempNode->Parent->Chain = tempNode->Right;
    00571                         }
    00572                         else if (tempNode->Parent->Left == tempNode)
    00573                         {
    00574                             tempNode->Parent->Left = tempNode->Right;
    00575                         }
    00576                         else if (tempNode->Parent->Right == tempNode)
    00577                         {
    00578                             tempNode->Parent->Right = tempNode->Right;
    00579                         }
    00580                     }
    00581                     else
    00582                         m_Root = tempNode;
    00583                 }
    00584                 // now swap it out
    00585                 tempNode->Right = Node->Right;
    00586                 tempNode->Left = Node->Left;
    00587                 tempNode->Parent = Node->Parent;
    00588                 if (Node->Left)
    00589                     Node->Left->Parent = tempNode;
    00590                 if (Node->Right)
    00591                     Node->Right->Parent = tempNode;
    00592             }
    00593         }
    00594         else
    00595         {
    00596             //no children, just point the parent at NULL
    00597             if (Node->Parent)
    00598             {
    00599                 if (Node->Parent->Chain == Node)
    00600                 {
    00601                     Node->Parent->Chain = NULL;
    00602                 }
    00603                 else if (Node->Parent->Left == Node)
    00604                 {
    00605                     Node->Parent->Left = NULL;
    00606                 }
    00607                 else if (Node->Parent->Right == Node)
    00608                 {
    00609                     Node->Parent->Right = NULL;
    00610                 }
    00611             }
    00612             else
    00613                 m_Root = NULL;
    00614         }
    00615
    00616         delete Node;
    00617         m_Length--;
    00618         return deTRUE;
    00619     }
    00620     T* GetData(void* ptr)
    00621     {
    00622         TBSTNode * Node = (TBSTNode*)ptr;
    00623         if (Node == NULL)
    00624             return NULL;
    00625         return &(Node->Data);
    00626     }
    00627     void GetDataPList(deTList <T*> &list)
    00628     {
    00629         if (m_Root)
    00630             m_Root->AddDataToList(list);
    00631     }
    00632     void GetValueList(deTList <DWORD> &list)
    00633     {
    00634         if (m_Root)
    00635             m_Root->AddValueToList(list);
    00636     }
    00637     long Length() const
    00638     {
    00639         return m_Length;
    00640     }
    00641     long size() const { return m_Length; }
    00642
    00643     // iterator stuff
    00644     inline iterator begin() {
    00645         TBSTNode *Node = (TBSTNode*)m_Root;
    00646         while (Node && Node->Left)
    00647             Node = Node->Left;
    00648         return iterator(Node);
    00649     }
    00650     inline iterator end()   { return iterator(0); }
    00651
    00652     iterator insert(const T & data, const DWORD Val[N])
    00653     {
    00654         TBSTNode * Node = (TBSTNode*)AddElement(data, Val);
    00655         return iterator(Node);
    00656     }
    00657
    00658     inline iterator erase(iterator& it)
    00659     {
    00660         iterator next = it;
    00661         ++next;
    00662         RemoveElement(it.m_Node);
    00663         return next;
    00664     }
    00665 };
    00666
    00667 //#pragma warning (default : 4710)
    00668
    00669 #endif