Sierra Toolkit Version of the Day
red_black_tree_eastl.cpp
00001 /*
00002 Copyright (C) 2005,2009-2010 Electronic Arts, Inc.  All rights reserved.
00003 
00004 Redistribution and use in source and binary forms, with or without
00005 modification, are permitted provided that the following conditions
00006 are met:
00007 
00008 1.  Redistributions of source code must retain the above copyright
00009     notice, this list of conditions and the following disclaimer.
00010 2.  Redistributions in binary form must reproduce the above copyright
00011     notice, this list of conditions and the following disclaimer in the
00012     documentation and/or other materials provided with the distribution.
00013 3.  Neither the name of Electronic Arts, Inc. ("EA") nor the names of
00014     its contributors may be used to endorse or promote products derived
00015     from this software without specific prior written permission.
00016 
00017 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
00018 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00019 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00020 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
00021 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00022 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00023 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00024 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027 */
00028 
00030 // EASTL/red_black_tree.cpp
00031 //
00032 // Written and maintained by Paul Pedriana - 2005.
00034 
00035 
00037 // The tree insert and erase functions below are based on the original
00038 // HP STL tree functions. Use of these functions was been approved by
00039 // EA legal on November 4, 2005 and the approval documentation is available
00040 // from the EASTL maintainer or from the EA legal deparatment on request.
00041 //
00042 // Copyright (c) 1994
00043 // Hewlett-Packard Company
00044 //
00045 // Permission to use, copy, modify, distribute and sell this software
00046 // and its documentation for any purpose is hereby granted without fee,
00047 // provided that the above copyright notice appear in all copies and
00048 // that both that copyright notice and this permission notice appear
00049 // in supporting documentation. Hewlett-Packard Company makes no
00050 // representations about the suitability of this software for any
00051 // purpose. It is provided "as is" without express or implied warranty.
00053 
00054 
00055 
00056 
00057 #include <stk_util/util/config_eastl.h>
00058 #include <stk_util/util/red_black_tree_eastl.h>
00059 #include <stddef.h>
00060 
00061 
00062 
00063 namespace eastl
00064 {
00065     // Forward declarations
00066     rbtree_node_base* RBTreeRotateLeft(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot);
00067     rbtree_node_base* RBTreeRotateRight(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot);
00068 
00069 
00070 
00074     EASTL_API rbtree_node_base* RBTreeIncrement(const rbtree_node_base* pNode)
00075     {
00076         if(pNode->mpNodeRight)
00077         {
00078             pNode = pNode->mpNodeRight;
00079 
00080             while(pNode->mpNodeLeft)
00081                 pNode = pNode->mpNodeLeft;
00082         }
00083         else
00084         {
00085             rbtree_node_base* pNodeTemp = pNode->mpNodeParent;
00086 
00087             while(pNode == pNodeTemp->mpNodeRight)
00088             {
00089                 pNode = pNodeTemp;
00090                 pNodeTemp = pNodeTemp->mpNodeParent;
00091             }
00092 
00093             if(pNode->mpNodeRight != pNodeTemp)
00094                 pNode = pNodeTemp;
00095         }
00096 
00097         return const_cast<rbtree_node_base*>(pNode);
00098     }
00099 
00100 
00101 
00105     EASTL_API rbtree_node_base* RBTreeDecrement(const rbtree_node_base* pNode)
00106     {
00107         if((pNode->mpNodeParent->mpNodeParent == pNode) && (pNode->mColor == kRBTreeColorRed))
00108             return pNode->mpNodeRight;
00109         else if(pNode->mpNodeLeft)
00110         {
00111             rbtree_node_base* pNodeTemp = pNode->mpNodeLeft;
00112 
00113             while(pNodeTemp->mpNodeRight)
00114                 pNodeTemp = pNodeTemp->mpNodeRight;
00115 
00116             return pNodeTemp;
00117         }
00118 
00119         rbtree_node_base* pNodeTemp = pNode->mpNodeParent;
00120 
00121         while(pNode == pNodeTemp->mpNodeLeft)
00122         {
00123             pNode     = pNodeTemp;
00124             pNodeTemp = pNodeTemp->mpNodeParent;
00125         }
00126 
00127         return const_cast<rbtree_node_base*>(pNodeTemp);
00128     }
00129 
00130 
00131 
00138     EASTL_API size_t RBTreeGetBlackCount(const rbtree_node_base* pNodeTop, const rbtree_node_base* pNodeBottom)
00139     {
00140         size_t nCount = 0;
00141 
00142         for(; pNodeBottom; pNodeBottom = pNodeBottom->mpNodeParent)
00143         {
00144             if(pNodeBottom->mColor == kRBTreeColorBlack)
00145                 ++nCount;
00146 
00147             if(pNodeBottom == pNodeTop)
00148                 break;
00149         }
00150 
00151         return nCount;
00152     }
00153 
00154 
00159     rbtree_node_base* RBTreeRotateLeft(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot)
00160     {
00161         rbtree_node_base* const pNodeTemp = pNode->mpNodeRight;
00162 
00163         pNode->mpNodeRight = pNodeTemp->mpNodeLeft;
00164 
00165         if(pNodeTemp->mpNodeLeft)
00166             pNodeTemp->mpNodeLeft->mpNodeParent = pNode;
00167         pNodeTemp->mpNodeParent = pNode->mpNodeParent;
00168 
00169         if(pNode == pNodeRoot)
00170             pNodeRoot = pNodeTemp;
00171         else if(pNode == pNode->mpNodeParent->mpNodeLeft)
00172             pNode->mpNodeParent->mpNodeLeft = pNodeTemp;
00173         else
00174             pNode->mpNodeParent->mpNodeRight = pNodeTemp;
00175 
00176         pNodeTemp->mpNodeLeft = pNode;
00177         pNode->mpNodeParent = pNodeTemp;
00178 
00179         return pNodeRoot;
00180     }
00181 
00182 
00183 
00188     rbtree_node_base* RBTreeRotateRight(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot)
00189     {
00190         rbtree_node_base* const pNodeTemp = pNode->mpNodeLeft;
00191 
00192         pNode->mpNodeLeft = pNodeTemp->mpNodeRight;
00193 
00194         if(pNodeTemp->mpNodeRight)
00195             pNodeTemp->mpNodeRight->mpNodeParent = pNode;
00196         pNodeTemp->mpNodeParent = pNode->mpNodeParent;
00197 
00198         if(pNode == pNodeRoot)
00199             pNodeRoot = pNodeTemp;
00200         else if(pNode == pNode->mpNodeParent->mpNodeRight)
00201             pNode->mpNodeParent->mpNodeRight = pNodeTemp;
00202         else
00203             pNode->mpNodeParent->mpNodeLeft = pNodeTemp;
00204 
00205         pNodeTemp->mpNodeRight = pNode;
00206         pNode->mpNodeParent = pNodeTemp;
00207 
00208         return pNodeRoot;
00209     }
00210 
00211 
00212 
00213 
00218     EASTL_API void RBTreeInsert(rbtree_node_base* pNode,
00219                                 rbtree_node_base* pNodeParent,
00220                                 rbtree_node_base* pNodeAnchor,
00221                                 RBTreeSide insertionSide)
00222     {
00223         rbtree_node_base*& pNodeRootRef = pNodeAnchor->mpNodeParent;
00224 
00225         // Initialize fields in new node to insert.
00226         pNode->mpNodeParent = pNodeParent;
00227         pNode->mpNodeRight  = NULL;
00228         pNode->mpNodeLeft   = NULL;
00229         pNode->mColor       = kRBTreeColorRed;
00230 
00231         // Insert the node.
00232         if(insertionSide == kRBTreeSideLeft)
00233         {
00234             pNodeParent->mpNodeLeft = pNode; // Also makes (leftmost = pNode) when (pNodeParent == pNodeAnchor)
00235 
00236             if(pNodeParent == pNodeAnchor)
00237             {
00238                 pNodeAnchor->mpNodeParent = pNode;
00239                 pNodeAnchor->mpNodeRight = pNode;
00240             }
00241             else if(pNodeParent == pNodeAnchor->mpNodeLeft)
00242                 pNodeAnchor->mpNodeLeft = pNode; // Maintain leftmost pointing to min node
00243         }
00244         else
00245         {
00246             pNodeParent->mpNodeRight = pNode;
00247 
00248             if(pNodeParent == pNodeAnchor->mpNodeRight)
00249                 pNodeAnchor->mpNodeRight = pNode; // Maintain rightmost pointing to max node
00250         }
00251 
00252         // Rebalance the tree.
00253         while((pNode != pNodeRootRef) && (pNode->mpNodeParent->mColor == kRBTreeColorRed))
00254         {
00255             rbtree_node_base* const pNodeParentParent = pNode->mpNodeParent->mpNodeParent;
00256 
00257             if(pNode->mpNodeParent == pNodeParentParent->mpNodeLeft)
00258             {
00259                 rbtree_node_base* const pNodeTemp = pNodeParentParent->mpNodeRight;
00260 
00261                 if(pNodeTemp && (pNodeTemp->mColor == kRBTreeColorRed))
00262                 {
00263                     pNode->mpNodeParent->mColor = kRBTreeColorBlack;
00264                     pNodeTemp->mColor = kRBTreeColorBlack;
00265                     pNodeParentParent->mColor = kRBTreeColorRed;
00266                     pNode = pNodeParentParent;
00267                 }
00268                 else
00269                 {
00270                     if(pNode == pNode->mpNodeParent->mpNodeRight)
00271                     {
00272                         pNode = pNode->mpNodeParent;
00273                         pNodeRootRef = RBTreeRotateLeft(pNode, pNodeRootRef);
00274                     }
00275 
00276                     pNode->mpNodeParent->mColor = kRBTreeColorBlack;
00277                     pNodeParentParent->mColor = kRBTreeColorRed;
00278                     pNodeRootRef = RBTreeRotateRight(pNodeParentParent, pNodeRootRef);
00279                 }
00280             }
00281             else
00282             {
00283                 rbtree_node_base* const pNodeTemp = pNodeParentParent->mpNodeLeft;
00284 
00285                 if(pNodeTemp && (pNodeTemp->mColor == kRBTreeColorRed))
00286                 {
00287                     pNode->mpNodeParent->mColor = kRBTreeColorBlack;
00288                     pNodeTemp->mColor = kRBTreeColorBlack;
00289                     pNodeParentParent->mColor = kRBTreeColorRed;
00290                     pNode = pNodeParentParent;
00291                 }
00292                 else
00293                 {
00294                     if(pNode == pNode->mpNodeParent->mpNodeLeft)
00295                     {
00296                         pNode = pNode->mpNodeParent;
00297                         pNodeRootRef = RBTreeRotateRight(pNode, pNodeRootRef);
00298                     }
00299 
00300                     pNode->mpNodeParent->mColor = kRBTreeColorBlack;
00301                     pNodeParentParent->mColor = kRBTreeColorRed;
00302                     pNodeRootRef = RBTreeRotateLeft(pNodeParentParent, pNodeRootRef);
00303                 }
00304             }
00305         }
00306 
00307         pNodeRootRef->mColor = kRBTreeColorBlack;
00308 
00309     } // RBTreeInsert
00310 
00311 
00312 
00313 
00317     EASTL_API void RBTreeErase(rbtree_node_base* pNode, rbtree_node_base* pNodeAnchor)
00318     {
00319         rbtree_node_base*& pNodeRootRef      = pNodeAnchor->mpNodeParent;
00320         rbtree_node_base*& pNodeLeftmostRef  = pNodeAnchor->mpNodeLeft;
00321         rbtree_node_base*& pNodeRightmostRef = pNodeAnchor->mpNodeRight;
00322         rbtree_node_base*  pNodeSuccessor    = pNode;
00323         rbtree_node_base*  pNodeChild        = NULL;
00324         rbtree_node_base*  pNodeChildParent  = NULL;
00325 
00326         if(pNodeSuccessor->mpNodeLeft == NULL)         // pNode has at most one non-NULL child.
00327             pNodeChild = pNodeSuccessor->mpNodeRight;  // pNodeChild might be null.
00328         else if(pNodeSuccessor->mpNodeRight == NULL)   // pNode has exactly one non-NULL child.
00329             pNodeChild = pNodeSuccessor->mpNodeLeft;   // pNodeChild is not null.
00330         else
00331         {
00332             // pNode has two non-null children. Set pNodeSuccessor to pNode's successor. pNodeChild might be NULL.
00333             pNodeSuccessor = pNodeSuccessor->mpNodeRight;
00334 
00335             while(pNodeSuccessor->mpNodeLeft)
00336                 pNodeSuccessor = pNodeSuccessor->mpNodeLeft;
00337 
00338             pNodeChild = pNodeSuccessor->mpNodeRight;
00339         }
00340 
00341         // Here we remove pNode from the tree and fix up the node pointers appropriately around it.
00342         if(pNodeSuccessor == pNode) // If pNode was a leaf node (had both NULL children)...
00343         {
00344             pNodeChildParent = pNodeSuccessor->mpNodeParent;  // Assign pNodeReplacement's parent.
00345 
00346             if(pNodeChild)
00347                 pNodeChild->mpNodeParent = pNodeSuccessor->mpNodeParent;
00348 
00349             if(pNode == pNodeRootRef) // If the node being deleted is the root node...
00350                 pNodeRootRef = pNodeChild; // Set the new root node to be the pNodeReplacement.
00351             else
00352             {
00353                 if(pNode == pNode->mpNodeParent->mpNodeLeft) // If pNode is a left node...
00354                     pNode->mpNodeParent->mpNodeLeft  = pNodeChild;  // Make pNode's replacement node be on the same side.
00355                 else
00356                     pNode->mpNodeParent->mpNodeRight = pNodeChild;
00357                 // Now pNode is disconnected from the bottom of the tree (recall that in this pathway pNode was determined to be a leaf).
00358             }
00359 
00360             if(pNode == pNodeLeftmostRef) // If pNode is the tree begin() node...
00361             {
00362                 // Because pNode is the tree begin(), pNode->mpNodeLeft must be NULL.
00363                 // Here we assign the new begin() (first node).
00364                 if(pNode->mpNodeRight)
00365                     pNodeLeftmostRef = RBTreeGetMinChild(pNodeChild);
00366                 else
00367                     pNodeLeftmostRef = pNode->mpNodeParent; // This  makes (pNodeLeftmostRef == end()) if (pNode == root node)
00368             }
00369 
00370             if(pNode == pNodeRightmostRef) // If pNode is the tree last (rbegin()) node...
00371             {
00372                 // Because pNode is the tree rbegin(), pNode->mpNodeRight must be NULL.
00373                 // Here we assign the new rbegin() (last node)
00374                 if(pNode->mpNodeLeft)
00375                     pNodeRightmostRef = RBTreeGetMaxChild(pNodeChild);
00376                 else // pNodeChild == pNode->mpNodeLeft
00377                     pNodeRightmostRef = pNode->mpNodeParent; // makes pNodeRightmostRef == &mAnchor if pNode == pNodeRootRef
00378             }
00379         }
00380         else // else (pNodeSuccessor != pNode)
00381         {
00382             // Relink pNodeSuccessor in place of pNode. pNodeSuccessor is pNode's successor.
00383             // We specifically set pNodeSuccessor to be on the right child side of pNode, so fix up the left child side.
00384             pNode->mpNodeLeft->mpNodeParent = pNodeSuccessor;
00385             pNodeSuccessor->mpNodeLeft = pNode->mpNodeLeft;
00386 
00387             if(pNodeSuccessor == pNode->mpNodeRight) // If pNode's successor was at the bottom of the tree... (yes that's effectively what this statement means)
00388                 pNodeChildParent = pNodeSuccessor; // Assign pNodeReplacement's parent.
00389             else
00390             {
00391                 pNodeChildParent = pNodeSuccessor->mpNodeParent;
00392 
00393                 if(pNodeChild)
00394                     pNodeChild->mpNodeParent = pNodeChildParent;
00395 
00396                 pNodeChildParent->mpNodeLeft = pNodeChild;
00397 
00398                 pNodeSuccessor->mpNodeRight = pNode->mpNodeRight;
00399                 pNode->mpNodeRight->mpNodeParent = pNodeSuccessor;
00400             }
00401 
00402             if(pNode == pNodeRootRef)
00403                 pNodeRootRef = pNodeSuccessor;
00404             else if(pNode == pNode->mpNodeParent->mpNodeLeft)
00405                 pNode->mpNodeParent->mpNodeLeft = pNodeSuccessor;
00406             else
00407                 pNode->mpNodeParent->mpNodeRight = pNodeSuccessor;
00408 
00409             // Now pNode is disconnected from the tree.
00410 
00411             pNodeSuccessor->mpNodeParent = pNode->mpNodeParent;
00412             eastl::swap(pNodeSuccessor->mColor, pNode->mColor);
00413         }
00414 
00415         // Here we do tree balancing as per the conventional red-black tree algorithm.
00416         if(pNode->mColor == kRBTreeColorBlack)
00417         {
00418             while((pNodeChild != pNodeRootRef) && ((pNodeChild == NULL) || (pNodeChild->mColor == kRBTreeColorBlack)))
00419             {
00420                 if(pNodeChild == pNodeChildParent->mpNodeLeft)
00421                 {
00422                     rbtree_node_base* pNodeTemp = pNodeChildParent->mpNodeRight;
00423 
00424                     if(pNodeTemp->mColor == kRBTreeColorRed)
00425                     {
00426                         pNodeTemp->mColor = kRBTreeColorBlack;
00427                         pNodeChildParent->mColor = kRBTreeColorRed;
00428                         pNodeRootRef = RBTreeRotateLeft(pNodeChildParent, pNodeRootRef);
00429                         pNodeTemp = pNodeChildParent->mpNodeRight;
00430                     }
00431 
00432                     if(((pNodeTemp->mpNodeLeft  == NULL) || (pNodeTemp->mpNodeLeft->mColor  == kRBTreeColorBlack)) &&
00433                         ((pNodeTemp->mpNodeRight == NULL) || (pNodeTemp->mpNodeRight->mColor == kRBTreeColorBlack)))
00434                     {
00435                         pNodeTemp->mColor = kRBTreeColorRed;
00436                         pNodeChild = pNodeChildParent;
00437                         pNodeChildParent = pNodeChildParent->mpNodeParent;
00438                     }
00439                     else
00440                     {
00441                         if((pNodeTemp->mpNodeRight == NULL) || (pNodeTemp->mpNodeRight->mColor == kRBTreeColorBlack))
00442                         {
00443                             pNodeTemp->mpNodeLeft->mColor = kRBTreeColorBlack;
00444                             pNodeTemp->mColor = kRBTreeColorRed;
00445                             pNodeRootRef = RBTreeRotateRight(pNodeTemp, pNodeRootRef);
00446                             pNodeTemp = pNodeChildParent->mpNodeRight;
00447                         }
00448 
00449                         pNodeTemp->mColor = pNodeChildParent->mColor;
00450                         pNodeChildParent->mColor = kRBTreeColorBlack;
00451 
00452                         if(pNodeTemp->mpNodeRight)
00453                             pNodeTemp->mpNodeRight->mColor = kRBTreeColorBlack;
00454 
00455                         pNodeRootRef = RBTreeRotateLeft(pNodeChildParent, pNodeRootRef);
00456                         break;
00457                     }
00458                 }
00459                 else
00460                 {
00461                     // The following is the same as above, with mpNodeRight <-> mpNodeLeft.
00462                     rbtree_node_base* pNodeTemp = pNodeChildParent->mpNodeLeft;
00463 
00464                     if(pNodeTemp->mColor == kRBTreeColorRed)
00465                     {
00466                         pNodeTemp->mColor        = kRBTreeColorBlack;
00467                         pNodeChildParent->mColor = kRBTreeColorRed;
00468 
00469                         pNodeRootRef = RBTreeRotateRight(pNodeChildParent, pNodeRootRef);
00470                         pNodeTemp = pNodeChildParent->mpNodeLeft;
00471                     }
00472 
00473                     if(((pNodeTemp->mpNodeRight == NULL) || (pNodeTemp->mpNodeRight->mColor == kRBTreeColorBlack)) &&
00474                         ((pNodeTemp->mpNodeLeft  == NULL) || (pNodeTemp->mpNodeLeft->mColor  == kRBTreeColorBlack)))
00475                     {
00476                         pNodeTemp->mColor = kRBTreeColorRed;
00477                         pNodeChild       = pNodeChildParent;
00478                         pNodeChildParent = pNodeChildParent->mpNodeParent;
00479                     }
00480                     else
00481                     {
00482                         if((pNodeTemp->mpNodeLeft == NULL) || (pNodeTemp->mpNodeLeft->mColor == kRBTreeColorBlack))
00483                         {
00484                             pNodeTemp->mpNodeRight->mColor = kRBTreeColorBlack;
00485                             pNodeTemp->mColor              = kRBTreeColorRed;
00486 
00487                             pNodeRootRef = RBTreeRotateLeft(pNodeTemp, pNodeRootRef);
00488                             pNodeTemp = pNodeChildParent->mpNodeLeft;
00489                         }
00490 
00491                         pNodeTemp->mColor = pNodeChildParent->mColor;
00492                         pNodeChildParent->mColor = kRBTreeColorBlack;
00493 
00494                         if(pNodeTemp->mpNodeLeft)
00495                             pNodeTemp->mpNodeLeft->mColor = kRBTreeColorBlack;
00496 
00497                         pNodeRootRef = RBTreeRotateRight(pNodeChildParent, pNodeRootRef);
00498                         break;
00499                     }
00500                 }
00501             }
00502 
00503             if(pNodeChild)
00504                 pNodeChild->mColor = kRBTreeColorBlack;
00505         }
00506 
00507     } // RBTreeErase
00508 
00509 
00510 
00511 } // namespace eastl
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines