Humble Framework

00001 /*!**************************************************************************
00002 **
00003 **  $Header: /SkyOS.root/pig/Humble/HTree.h 3     12/08/04 5:06p Neusel $
00004 **
00005 **  \file       HTree.h
00006 **
00007 **  The HTree.h header files contains the interface and implementation to the
00008 **  HTree and HTreeNode template classes.  These classes combine to provide a 
00009 **  balanced AVL tree, and were based on source code published by Andreas Jäger 
00010 **  (Jaeger-Geitersdorf@t-online.de) at www.codejockey.com; this site has since 
00011 **  changed hands, and the original posting is no longer available.
00012 **
00013 ****************************************************************************/
00014 #ifndef HTREE_H
00015     #define HTREE_H
00016 /*  ----------------------------------------------------------------------
00017     AVL Tree Node declaration
00018     ----------------------------------------------------------------------  */
00028 template <class T> class HTree;
00029 
00030 template <class T>
00031 class HTreeNode : public HObj
00032     {
00033     typedef HObj        base_class;
00034     static StringPtr    ClassName(void) { return "HTreeNode<T>"; }
00035 
00036     friend class HTree<T>;
00037     
00038     typedef HTreeNode<T> *  HTreeNodePtr;
00039 /*
00040 **  Variables
00041 */
00042 protected:
00043     typedef enum { BAL_LEFT, BAL_EVEN, BAL_RIGHT }  Balance;
00044 
00045     T                   m_data;         
00046     Balance             m_balance;      
00047     HTreeNodePtr        m_pnLeft;       
00048     HTreeNodePtr        m_pnRight;      
00049     HTreeNodePtr        m_pnParent;     
00050 /*
00051 **  Methods
00052 */
00053 protected:
00057     void                
00058     afterDelete(void)
00059         {
00060         HTreeNodePtr    pn = this;
00061         /*  Rule 1  */
00062         if (pn->m_balance == BAL_EVEN && NULL_PTR(pn->m_pnLeft)) 
00063             {
00064             pn->m_balance = BAL_RIGHT;
00065             return;
00066             }
00067         if (pn->m_balance == BAL_EVEN && NULL_PTR(pn->m_pnRight)) 
00068             {
00069             pn->m_balance = BAL_LEFT;
00070             return;
00071             }
00072         /*  Rule 2  */
00073         if ((pn->m_balance == BAL_LEFT && NULL_PTR(pn->m_pnLeft)) ||
00074             (pn->m_balance == BAL_RIGHT && NULL_PTR(pn->m_pnRight)))
00075             {
00076             pn->m_balance = BAL_EVEN;
00077             }
00078         /*  Rule 3  */
00079         if (pn->m_balance == BAL_LEFT && NULL_PTR(pn->m_pnRight))
00080             {
00081             if (pn->m_pnLeft->m_balance == BAL_RIGHT)
00082                 {
00083                 pn->rotateLeftLeft();
00084                 pn = pn->m_pnParent;
00085                 }
00086             else
00087                 {
00088                 pn->rotateRight();
00089                 pn = pn->m_pnParent;
00090                 }
00091             
00092             if (pn->m_balance == BAL_RIGHT)
00093                 return;
00094             }
00095 
00096         if (pn->m_balance == BAL_RIGHT && NULL_PTR(pn->m_pnLeft))
00097             {
00098             if (pn->m_pnRight->m_balance == BAL_LEFT)
00099                 {
00100                 pn->rotateRightRight();
00101                 pn = pn->m_pnParent;
00102                 }
00103             else
00104                 {
00105                 pn->rotateLeft();
00106                 pn = pn->m_pnParent;
00107                 }
00108 
00109             if (pn->m_balance == BAL_LEFT)
00110                 return;
00111             }
00112 
00113         while (pn->hasParent())
00114             {
00115         /*  Rule 1  */
00116             if (pn->isLeftSibling() && pn->m_pnParent->m_balance == BAL_EVEN)
00117                 {
00118                 pn->m_pnParent->m_balance = BAL_RIGHT;
00119                 break;
00120                 }
00121 
00122             if (pn->isRightSibling() && pn->m_pnParent->m_balance == BAL_EVEN)
00123                 {
00124                 pn->m_pnParent->m_balance = BAL_LEFT;
00125                 break;
00126                 }
00127         /*  Rule 2  */
00128             if ((pn->isLeftSibling() && pn->m_pnParent->m_balance == BAL_LEFT) ||
00129                 (pn->isRightSibling() && pn->m_pnParent->m_balance == BAL_RIGHT))
00130                 {
00131                 pn->m_pnParent->m_balance = BAL_EVEN;
00132                 pn = pn->m_pnParent;
00133                 continue;
00134                 }
00135         /*  Rule 3  */
00136             if (pn->isRightSibling() && pn->m_pnParent->m_balance == BAL_LEFT)
00137                 {
00138                 if (pn->m_pnParent->m_pnLeft->m_balance == BAL_RIGHT)
00139                     {
00140                     pn->m_pnParent->rotateLeftLeft();
00141                     pn = pn->m_pnParent->m_pnParent;
00142                     }
00143                 else
00144                     {
00145                     pn->m_pnParent->rotateRight();
00146                     pn = pn->m_pnParent->m_pnParent;
00147                     }
00148                 
00149                 if (pn->m_balance == BAL_RIGHT)
00150                     return;
00151                 
00152                 continue;
00153                 }
00154             
00155             if (pn->isLeftSibling() && pn->m_pnParent->m_balance == BAL_RIGHT)
00156                 {
00157                 if (pn->m_pnParent->m_pnRight->m_balance == BAL_LEFT)
00158                     {
00159                     pn->m_pnParent->rotateRightRight();
00160                     pn = pn->m_pnParent->m_pnParent;
00161                     }
00162                 else
00163                     {
00164                     pn->m_pnParent->rotateLeft();
00165                     pn = pn->m_pnParent->m_pnParent;
00166                     }
00167 
00168                 if (pn->m_balance == BAL_LEFT)
00169                     return;
00170                 
00171                 continue;
00172                 }
00173 
00174             break;
00175             }
00176         }
00180     void                
00181     afterInsert(void)
00182         {
00183         HTreeNodePtr    pn = this;
00184 
00185         while (pn->hasParent())
00186             {
00187         /*  Rule 1  */
00188             if (pn->isLeftSibling() && pn->m_pnParent->m_balance == BAL_EVEN)
00189                 {
00190                 pn->m_pnParent->m_balance = BAL_LEFT;
00191                 pn = pn->m_pnParent;
00192                 continue;
00193                 }
00194 
00195             if (pn->isRightSibling() && pn->m_pnParent->m_balance == BAL_EVEN)
00196                 {
00197                 pn->m_pnParent->m_balance = BAL_RIGHT;
00198                 pn = pn->m_pnParent;
00199                 continue;
00200                 }
00201         /*  Rule 2  */
00202             if ((pn->isLeftSibling() && pn->m_pnParent->m_balance == BAL_RIGHT) ||
00203                 (pn->isRightSibling() && pn->m_pnParent->m_balance == BAL_LEFT))
00204                 {
00205                 pn->m_pnParent->m_balance = BAL_EVEN;
00206                 break;
00207                 }
00208         /*  Rule 3  */
00209             if (pn->isLeftSibling() && pn->m_pnParent->m_balance == BAL_LEFT)
00210                 {
00211                 if (pn->m_balance == BAL_RIGHT)
00212                     pn->m_pnParent->rotateLeftLeft();
00213                 else
00214                     pn->m_pnParent->rotateRight();
00215                 break;
00216                 }
00217 
00218             if (pn->isRightSibling() && pn->m_pnParent->m_balance == BAL_RIGHT)
00219                 {
00220                 if (pn->m_balance == BAL_LEFT)
00221                     pn->m_pnParent->rotateRightRight();
00222                 else
00223                     pn->m_pnParent->rotateLeft();
00224                 break;
00225                 }
00226             }
00227         }
00235     HTreeNodePtr        
00236     getInsertPos(const T &  data, HTreeNodePtr & pnFound)
00237         {
00238         const int   nCmp = Compare(m_data, data);
00239 
00240         if (nCmp == 0)
00241             {
00242             pnFound = this;
00243             return NULL;    // already in tree!
00244             }
00245             
00246         pnFound = NULL;
00247         return (nCmp > 0) ? 
00248                 (NULL_PTR(m_pnLeft) ?   this : m_pnLeft->getInsertPos(data, pnFound)) :
00249                 (NULL_PTR(m_pnRight) ?  this : m_pnRight->getInsertPos(data, pnFound));
00250         }
00254     void                
00255     rotateLeft(void)
00256         {
00257         HTreeNodePtr    pn = m_pnRight;
00258 
00259         if (NULL_PTR(pn))
00260             {
00261             DEBUG_LOG("HTreeNode::rotateLeft() => invalid right child!\n");
00262             return; // fail gracefully in release builds
00263             }
00264 
00265         if (hasParent())
00266             {
00267             if (isLeftSibling())
00268                 m_pnParent->m_pnLeft = pn;
00269             else
00270                 m_pnParent->m_pnRight = pn;
00271 
00272             pn->m_pnParent = m_pnParent;
00273             }
00274         else
00275             pn->m_pnParent = NULL;
00276             
00277         m_pnRight = pn->m_pnLeft;
00278         pn->m_pnLeft = this;
00279 
00280         m_pnParent = pn;
00281         if (GOOD_PTR(m_pnRight)) 
00282             m_pnRight->m_pnParent = this;
00283             
00284         if (pn->m_balance == BAL_EVEN)
00285             {
00286             m_balance = BAL_RIGHT;
00287             pn->m_balance = BAL_LEFT;
00288             }
00289         else
00290             m_balance = pn->m_balance = BAL_EVEN;
00291         }
00295     void                
00296     rotateRight()
00297         {
00298         HTreeNodePtr    pn = m_pnLeft;
00299 
00300         if (NULL_PTR(pn))
00301             {
00302             DEBUG_LOG("HTreeNode::rotateRight() => invalid left child!\n");
00303             return; // fail gracefully in release builds
00304             }
00305 
00306         if (hasParent())
00307             {
00308             if (isLeftSibling())
00309                 m_pnParent->m_pnLeft = pn;
00310             else
00311                 m_pnParent->m_pnRight = pn;
00312 
00313             pn->m_pnParent = m_pnParent;
00314             }
00315         else
00316             pn->m_pnParent = NULL;  // no parent if we're the new root
00317             
00318         m_pnLeft = pn->m_pnRight;
00319         pn->m_pnRight = this;
00320 
00321         m_pnParent = pn;
00322         if (GOOD_PTR(m_pnLeft))
00323             m_pnLeft->m_pnParent = this;
00324 
00325         if (pn->m_balance == BAL_EVEN)
00326             {
00327             m_balance = BAL_LEFT;
00328             pn->m_balance = BAL_RIGHT;
00329             }
00330         else
00331             m_balance = pn->m_balance = BAL_EVEN;
00332         }
00336     void                
00337     rotateLeftLeft(void)
00338         {
00339         if (NULL_PTR(m_pnLeft) || NULL_PTR(m_pnLeft->m_pnRight))
00340             {
00341             DEBUG_LOG("HTreeNode::rotateLeftLeft() => invalid node pointer!\n");
00342             return; // fail gracefully under release builds (tree gets out of balance)
00343             }
00344             
00345         HTreeNodePtr    pn1 = m_pnLeft;
00346         HTreeNodePtr    pn2 = m_pnLeft->m_pnRight;
00347 
00348         if (hasParent())
00349             {
00350             if (isLeftSibling())
00351                 m_pnParent->m_pnLeft = pn2;
00352             else
00353                 m_pnParent->m_pnRight = pn2;
00354             }
00355 
00356         pn1->m_pnRight = pn2->m_pnLeft;
00357         m_pnLeft = pn2->m_pnRight;
00358         pn2->m_pnLeft = pn1;
00359         pn2->m_pnRight = this;
00360 
00361         pn2->m_pnParent = m_pnParent;
00362         m_pnParent = pn1->m_pnParent = pn2;
00363         if (GOOD_PTR(pn1->m_pnRight)) 
00364             pn1->m_pnRight->m_pnParent = pn1;
00365 
00366         if (GOOD_PTR(m_pnLeft))
00367             m_pnLeft->m_pnParent = this;
00368 
00369         switch (pn2->m_balance)
00370             {
00371             case BAL_LEFT:
00372                 m_balance = BAL_RIGHT;
00373                 pn1->m_balance = BAL_EVEN;
00374                 break;
00375             case BAL_EVEN:
00376                 m_balance = pn1->m_balance = BAL_EVEN;
00377                 break;
00378             case BAL_RIGHT:
00379                 m_balance = BAL_EVEN;
00380                 pn1->m_balance = BAL_LEFT;
00381                 break;
00382             }
00383 
00384         pn2->m_balance = BAL_EVEN;
00385         }
00389     void                
00390     rotateRightRight(void)
00391         {
00392         if (NULL_PTR(m_pnRight) || NULL_PTR(m_pnRight->m_pnLeft))
00393             {
00394             DEBUG_LOG("HTreeNode::rotateRightRigth() => invalid node pointer!\n");
00395             return; // fail gracefully under release builds (tree gets out of balance)
00396             }
00397 
00398         HTreeNodePtr    pn1 = m_pnRight;
00399         HTreeNodePtr    pn2 = m_pnRight->m_pnLeft;
00400 
00401         if (hasParent())
00402             {
00403             if (isLeftSibling())
00404                 m_pnParent->m_pnLeft = pn2;
00405             else
00406                 m_pnParent->m_pnRight = pn2;
00407             }
00408 
00409         m_pnRight = pn2->m_pnLeft;
00410         pn1->m_pnLeft = pn2->m_pnRight;
00411         pn2->m_pnLeft = this;
00412         pn2->m_pnRight = pn1;
00413 
00414         pn2->m_pnParent = m_pnParent;
00415         m_pnParent = pn1->m_pnParent = pn2;
00416         if (GOOD_PTR(m_pnRight)) 
00417             m_pnRight->m_pnParent = this;
00418 
00419         if (GOOD_PTR(pn1->m_pnLeft))
00420             pn1->m_pnLeft->m_pnParent = pn1;
00421 
00422         switch (pn2->m_balance)
00423             {
00424             case BAL_LEFT:
00425                 m_balance = BAL_EVEN;
00426                 pn1->m_balance = BAL_RIGHT;
00427                 break;
00428             case BAL_EVEN:
00429                 m_balance = pn1->m_balance = BAL_EVEN;
00430                 break;
00431             case BAL_RIGHT:
00432                 m_balance = BAL_LEFT;
00433                 pn1->m_balance = BAL_EVEN;
00434                 break;
00435             }
00436         pn2->m_balance = BAL_EVEN;
00437         }
00438 
00444     bool                
00445     hasParent(void) const
00446         { return GOOD_PTR(m_pnParent); }
00452     bool
00453     hasLeftSibling() const
00454         { return isRightSibling() && GOOD_PTR(m_pnParent->m_pnLeft); }
00460     bool
00461     hasRightSibling() const
00462         { return isLeftSibling() && GOOD_PTR(m_pnParent->m_pnRight); }
00468     bool
00469     isLeftSibling() const
00470         { return (GOOD_PTR(m_pnParent) && m_pnParent->m_pnLeft == this); }
00476     bool                
00477     isRightSibling() const
00478         { return (GOOD_PTR(m_pnParent) && m_pnParent->m_pnRight == this); }
00479 //
00480 //  OPERATORS
00481 //
00482     HTreeNode & 
00483     operator = (HTreeNode<T> const &)
00484         { return *this; }
00485 
00486 public:
00492     const T &           
00493     GetData() const
00494         { return m_data; }
00507     ErrCode
00508     SetData(const T & data)
00509         { 
00510         ErrCode     ec = HError::NoError();
00511         
00512         if (Compare(m_data, data) == 0)
00513             m_data = data; 
00514         else
00515             ec = HError::Set(ERR_DATA_INVALID, __FILE__, __LINE__);
00516             
00517         return ec;
00518         }
00527     uint32
00528     GetDepth(void) const
00529         {
00530         uint32  uDepthL,
00531                 uDepthR;
00532 
00533         uDepthL = GOOD_PTR(m_pnLeft) ? m_pnLeft->GetDepth() : 0;
00534         uDepthR = GOOD_PTR(m_pnRight) ?  m_pnRight->GetDepth() : 0;
00535 
00536         return 1 + max(uDepthL, uDepthR);
00537         }
00545     uint32              
00546     GetCount(void) const
00547         {
00548         uint32  uNodes = 1;
00549 
00550         if (GOOD_PTR(m_pnLeft)) 
00551             uNodes += m_pnLeft->GetCount();
00552 
00553         if (GOOD_PTR(m_pnRight))
00554             uNodes += m_pnRight->GetCount();
00555 
00556         return uNodes;
00557         }
00563     HTreeNodePtr        
00564     GetFirst(void)
00565         {
00566         HTreeNodePtr pn = this;
00567 
00568         while (GOOD_PTR(pn->m_pnLeft))
00569             pn = pn->m_pnLeft;
00570 
00571         return pn;
00572         }
00578     HTreeNodePtr        
00579     GetLast(void)
00580         {
00581         HTreeNodePtr pn = this;
00582 
00583         while (GOOD_PTR(pn->m_pnRight))
00584             pn = pn->m_pnRight;
00585 
00586         return pn;
00587         }
00593     HTreeNodePtr        
00594     GetNext(void)
00595         {
00596         HTreeNodePtr    pnNext = NULL;
00597 
00598         if (GOOD_PTR(m_pnRight))
00599             pnNext = m_pnRight->GetFirst();
00600         else if (isLeftSibling()) 
00601             pnNext = m_pnParent;
00602         else
00603             {
00604             for (HTreeNodePtr pn = this; pn->hasParent(); pn = pn->m_pnParent)
00605                 if (!pn->isRightSibling()) 
00606                     {
00607                     pnNext = pn->m_pnParent;
00608                     break;
00609                     }
00610             }
00611 
00612         return pnNext;
00613         }
00619     HTreeNodePtr        
00620     GetPrev(void)
00621         {
00622         HTreeNodePtr    pnPrev = NULL;
00623 
00624         if (GOOD_PTR(m_pnLeft))
00625             pnPrev = m_pnLeft->GetLast();
00626         else if (isRightSibling()) 
00627             pnPrev = m_pnParent;
00628         else
00629             {
00630             for (HTreeNodePtr pn = this; pn->hasParent(); pn = pn->m_pnParent)
00631                 if (!pn->isLeftSibling()) 
00632                     {
00633                     pnPrev =  pn->m_pnParent;
00634                     break;
00635                     }
00636             }
00637 
00638         return pnPrev;
00639         }
00645     HTreeNodePtr        
00646     GetRoot(void)
00647         {
00648         HTreeNodePtr pn = this; 
00649 
00650         while (GOOD_PTR(pn->m_pnParent))
00651             pn = pn->m_pnParent;
00652 
00653         return pn;
00654         }
00661     HTreeNodePtr        
00662     Search(T const & data)
00663         {
00664         const int   nCmp = Compare(m_data, data);
00665 
00666         if (nCmp == 0)
00667             return this;
00668 
00669         if (nCmp < 0 && GOOD_PTR(m_pnRight))
00670             return m_pnRight->Search(data);
00671         else if (nCmp > 0 && GOOD_PTR(m_pnLeft))
00672             return m_pnLeft->Search(data);
00673 
00674         return NULL;
00675         }
00683     static int          
00684     Compare(const T & t1, const T & t2)
00685         { return t1.Compare(t2); }
00686 //
00687 // CTOR/DTOR
00688 //
00689     HTreeNode(const T & data, HTreeNodePtr pn = NULL)
00690         {
00691         m_data = data;
00692         m_pnParent = pn;
00693         m_balance = BAL_EVEN;
00694         m_pnLeft = m_pnRight = NULL;
00695         }
00696 
00697     virtual             
00698     ~HTreeNode(void)
00699         { delete m_pnLeft; delete m_pnRight; }
00700     };
00701 /*  ----------------------------------------------------------------------
00702     AVL Tree declaration
00703     ----------------------------------------------------------------------  */
00713 template <class T>
00714 class HTree : public HObjNoCopy
00715     {
00716     typedef HObjNoCopy  base_class;
00717     static StringPtr    ClassName(void) { return "HTree<T>"; }
00718 
00719     typedef HTreeNode<T> *  HTreeNodePtr;
00720 /*
00721 **  Variables
00722 */
00723 protected:
00724     uint32              m_uNodes;       
00725     HTreeNodePtr        m_pnRoot;       
00726 public:
00727 /*
00728 **  Methods
00729 */
00730 protected:
00737     ErrCode             
00738     deleteNode(HTreeNodePtr pn)
00739         {
00740         ErrCode         ec = HError::NoError();
00741         HTreeNodePtr    pnHere = NULL;
00742 
00743         if (NULL_PTR(pn))
00744             return HError::Set(ERR_BAD_PARAMETER, __FILE__, __LINE__);
00745 
00746         if (NULL_PTR(pn->m_pnLeft) && NULL_PTR(pn->m_pnRight))
00747             {   // node to delete has no children
00748             if (pn == m_pnRoot) // special case if deleting last node in tree...
00749                 {
00750                 delete m_pnRoot;
00751                 m_pnRoot = NULL;
00752 
00753                 return ec;
00754                 }
00755 
00756             pnHere = pn->m_pnParent;
00757             if (pn->isLeftSibling())
00758                 pnHere->m_pnLeft = NULL;
00759             else
00760                 pnHere->m_pnRight = NULL;
00761 
00762             delete pn;
00763             pn = NULL;
00764             }
00765 
00766         if (GOOD_PTR(pn) && NULL_PTR(pn->m_pnLeft) && GOOD_PTR(pn->m_pnRight))
00767             {   // node to delete has only right child
00768             pnHere = pn;
00769             pn->m_data = pn->m_pnRight->m_data;
00770 
00771             delete pn->m_pnRight;
00772             pn->m_pnRight = NULL;
00773             }
00774 
00775         if (GOOD_PTR(pn) && GOOD_PTR(pn->m_pnLeft) && NULL_PTR(pn->m_pnRight))
00776             {   // node to delete has only left child
00777             pnHere = pn;
00778             pn->m_data = pn->m_pnLeft->m_data;
00779 
00780             delete pn->m_pnLeft;
00781             pn->m_pnLeft = NULL;
00782             }
00783 
00784         if (GOOD_PTR(pn) && GOOD_PTR(pn->m_pnLeft) && GOOD_PTR(pn->m_pnRight))
00785             {   // node to delete has both children
00786             HTreeNodePtr    pnX = pn->m_pnLeft->GetLast();
00787             HTreeNodePtr    pnY = pnX->m_pnLeft;
00788 
00789             pn->m_data = pnX->m_data;
00790 
00791             if (GOOD_PTR(pnY))
00792                 {
00793                 pnHere = pnX;
00794                 pnX->m_data = pnY->m_data;
00795                 pnX->m_pnLeft = NULL;
00796 
00797                 delete pnY;
00798                 pnY = NULL;
00799                 }
00800             else
00801                 {
00802                 pnHere = pnX->m_pnParent;
00803                 if (pnX->isLeftSibling())
00804                     pnHere->m_pnLeft = NULL;
00805                 else
00806                     pnHere->m_pnRight = NULL;
00807 
00808                 delete pnX;
00809                 pnX = NULL;
00810                 }
00811             }
00812 
00813         pnHere->afterDelete();
00814         m_pnRoot = m_pnRoot->GetRoot();
00815 
00816         return ec;
00817         }
00818 
00819 public:
00826     ErrCode             
00827     Delete(const T & data)
00828         {
00829         ErrCode         ec = HError::NoError();
00830         HTreeNodePtr    pn = m_pnRoot->Search(data);
00831         
00832         if (GOOD_PTR(pn))
00833             {
00834             if ((ec = deleteNode(pn)) == NO_ERROR)
00835                 m_uNodes--;
00836             }
00837         else
00838             ec = HError::Set(ERR_NOT_FOUND, __FILE__, __LINE__);
00839             
00840         return ec;
00841         }
00842 
00848     ErrCode             
00849     DeleteAll(void)
00850         {
00851         ErrCode     ec = HError::NoError();
00852         
00853         if (IsNotEmpty())
00854             {
00855             DEBUG_LOG("HTree::DeleteAll() => deleting %lu nodes.\n", m_uNodes);
00856             
00857             delete m_pnRoot;    // this causes nodes to delete themselves and children
00858             m_pnRoot = NULL;
00859             m_uNodes = 0;
00860             }
00861         
00862         return ec;
00863         }
00871     ErrCode     
00872     Insert(const T & data, const bool bUpdate = false)
00873         {
00874         ErrCode         ec = HError::NoError();
00875         HTreeNodePtr    pnParent = NULL;
00876         
00877         try
00878             {
00879             //
00880             //  Check to make sure we don't step on an existing node
00881             //
00882             if (!IsEmpty())
00883                 {
00884                 HTreeNodePtr    pnFound = NULL;
00885                 
00886                 pnParent = m_pnRoot->getInsertPos(data, pnFound);
00887                 if (NULL_PTR(pnParent)) // true if already in tree (or on error)
00888                     {
00889                     if (bUpdate && GOOD_PTR(pnFound))
00890                         {
00891                         ASSERT( HTreeNode<T>::Compare(data, pnFound->m_data) == 0 );
00892                         
00893                         pnFound->m_data = data;
00894                         DEBUG_LOG("HTree::Insert() => updated existing node.\n");
00895                         return HError::NoError();
00896                         }
00897                         
00898                     HError::Throw(ERR_DUPLICATE, __FILE__, __LINE__);
00899                     }
00900                 }
00901             //
00902             //  Now create a new node
00903             //
00904             HTreeNodePtr    pnNew;
00905             
00906             pnNew = new HTreeNode<T>(data, pnParent);
00907             ASSERT_PTR(pnNew);
00908             m_uNodes++;
00909             //
00910             //  And add the node to the appropriate location
00911             //
00912             if (IsEmpty())
00913                 m_pnRoot = pnNew;   // Trivial case if tree is empty
00914             else if (HTreeNode<T>::Compare(pnParent->m_data, data) < 0)
00915                 {
00916                 ASSERT_PTR(pnParent);
00917                 ASSERT( NULL_PTR(pnParent->m_pnRight) );
00918                 pnParent->m_pnRight = pnNew;
00919                 }
00920             else
00921                 {
00922                 ASSERT_PTR(pnParent);
00923                 ASSERT( NULL_PTR(pnParent->m_pnLeft) );
00924                 pnParent->m_pnLeft = pnNew;
00925                 }
00926             
00927             pnNew->afterInsert();
00928             m_pnRoot = m_pnRoot->GetRoot();
00929             }
00930         catch (const std::exception & e)
00931             {
00932             DEBUG_LOG("HTree::Insert() => caught %s\n", e.what());
00933             
00934             if ((ec = ErrCode( HError::GetLastError() )) == NO_ERROR)
00935                 ec = HError::Set(ERR_STL_EXCEPTION, __FILE__, __LINE__);
00936             }
00937             
00938         return ec;
00939         }
00946     virtual HTreeNodePtr    
00947     Search(const T * pData)
00948         { return GOOD_PTR(pData) ? Search(*pData) : NULL; }
00954     virtual HTreeNodePtr
00955     Search(T const & data) const
00956         { return GOOD_PTR(m_pnRoot) ? m_pnRoot->Search(data) : NULL; }
00965     uint32              
00966     GetDepth(void) const
00967         { return GOOD_PTR(m_pnRoot) ? m_pnRoot->GetDepth() : 0; }
00975     uint32              
00976     GetCount() const
00977         { return m_uNodes; }
00983     HTreeNodePtr        
00984     GetRoot() const
00985         { return m_pnRoot; }
00991     inline bool             
00992     IsEmpty(void) const
00993         { return NULL_PTR(m_pnRoot); }
00999     inline bool             
01000     IsNotEmpty(void) const
01001         { return GOOD_PTR(m_pnRoot); }
01002 //
01003 // CTOR/DTOR
01004 //
01005     HTree() : m_uNodes(0), m_pnRoot(NULL)
01006         { /* STUB CTOR */ }
01007 
01008     virtual             
01009     ~HTree()
01010         { (void) DeleteAll(); }
01011     };
01012 #endif  // HTREE_H
01013 /****************************************************************************
01014 **
01015 **  $History: HTree.h $
01016  * 
01017  * *****************  Version 3  *****************
01018  * User: Neusel       Date: 12/08/04   Time: 5:06p
01019  * Updated in $/SkyOS.root/pig/Humble
01020  * 20041208
01021  * 
01022  * *****************  Version 2  *****************
01023  * User: Neusel       Date: 11/30/04   Time: 1:01p
01024  * Updated in $/SkyOS.root/pig/Humble
01025  * Released as HUMBLE_VER 20041130.
01026  * 
01027  * *****************  Version 1  *****************
01028  * User: Neusel       Date: 11/23/04   Time: 8:24a
01029  * Created in $/SkyOS.root/pig/Humble
01030 **
01031 **  -------------------------------------------------------------------------
01032 **
01033 **  End of HTree.h
01034 **
01035 ****************************************************************************/
Humble Framework for SkyOS

HTree.h
