EASTL-Electronic Arts Standard Template Library

/* Copyright (C) 2005,2009-2010 Electronic Arts, Inc. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 3. Neither the name of Electronic Arts, Inc. ("EA") nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /////////////////////////////////////////////////////////////////////////////// // EASTL/red_black_tree.cpp // // Written and maintained by Paul Pedriana - 2005. /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// // The tree insert and erase functions below are based on the original // HP STL tree functions. Use of these functions was been approved by // EA legal on November 4, 2005 and the approval documentation is available // from the EASTL maintainer or from the EA legal deparatment on request. // // Copyright (c) 1994 // Hewlett-Packard Company // // Permission to use, copy, modify, distribute and sell this software // and its documentation for any purpose is hereby granted without fee, // provided that the above copyright notice appear in all copies and // that both that copyright notice and this permission notice appear // in supporting documentation. Hewlett-Packard Company makes no // representations about the suitability of this software for any // purpose. It is provided "as is" without express or implied warranty. /////////////////////////////////////////////////////////////////////////////// #include <EASTL/internal/config.h> #include <EASTL/internal/red_black_tree.h> #include <stddef.h> namespace eastl { // Forward declarations rbtree_node_base* RBTreeRotateLeft(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot); rbtree_node_base* RBTreeRotateRight(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot); /// RBTreeIncrement /// Returns the next item in a sorted red-black tree. /// EASTL_API rbtree_node_base* RBTreeIncrement(const rbtree_node_base* pNode) { if(pNode->mpNodeRight) { pNode = pNode->mpNodeRight; while(pNode->mpNodeLeft) pNode = pNode->mpNodeLeft; } else { rbtree_node_base* pNodeTemp = pNode->mpNodeParent; while(pNode == pNodeTemp->mpNodeRight) { pNode = pNodeTemp; pNodeTemp = pNodeTemp->mpNodeParent; } if(pNode->mpNodeRight != pNodeTemp) pNode = pNodeTemp; } return const_cast<rbtree_node_base*>(pNode); } /// RBTreeIncrement /// Returns the previous item in a sorted red-black tree. /// EASTL_API rbtree_node_base* RBTreeDecrement(const rbtree_node_base* pNode) { if((pNode->mpNodeParent->mpNodeParent == pNode) && (pNode->mColor == kRBTreeColorRed)) return pNode->mpNodeRight; else if(pNode->mpNodeLeft) { rbtree_node_base* pNodeTemp = pNode->mpNodeLeft; while(pNodeTemp->mpNodeRight) pNodeTemp = pNodeTemp->mpNodeRight; return pNodeTemp; } rbtree_node_base* pNodeTemp = pNode->mpNodeParent; while(pNode == pNodeTemp->mpNodeLeft) { pNode = pNodeTemp; pNodeTemp = pNodeTemp->mpNodeParent; } return const_cast<rbtree_node_base*>(pNodeTemp); } /// RBTreeGetBlackCount /// Counts the number of black nodes in an red-black tree, from pNode down to the given bottom node. /// We don't count red nodes because red-black trees don't really care about /// red node counts; it is black node counts that are significant in the /// maintenance of a balanced tree. /// EASTL_API size_t RBTreeGetBlackCount(const rbtree_node_base* pNodeTop, const rbtree_node_base* pNodeBottom) { size_t nCount = 0; for(; pNodeBottom; pNodeBottom = pNodeBottom->mpNodeParent) { if(pNodeBottom->mColor == kRBTreeColorBlack) ++nCount; if(pNodeBottom == pNodeTop) break; } return nCount; } /// RBTreeRotateLeft /// Does a left rotation about the given node. /// If you want to understand tree rotation, any book on algorithms will /// discussion the topic in good detail. rbtree_node_base* RBTreeRotateLeft(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot) { rbtree_node_base* const pNodeTemp = pNode->mpNodeRight; pNode->mpNodeRight = pNodeTemp->mpNodeLeft; if(pNodeTemp->mpNodeLeft) pNodeTemp->mpNodeLeft->mpNodeParent = pNode; pNodeTemp->mpNodeParent = pNode->mpNodeParent; if(pNode == pNodeRoot) pNodeRoot = pNodeTemp; else if(pNode == pNode->mpNodeParent->mpNodeLeft) pNode->mpNodeParent->mpNodeLeft = pNodeTemp; else pNode->mpNodeParent->mpNodeRight = pNodeTemp; pNodeTemp->mpNodeLeft = pNode; pNode->mpNodeParent = pNodeTemp; return pNodeRoot; } /// RBTreeRotateRight /// Does a right rotation about the given node. /// If you want to understand tree rotation, any book on algorithms will /// discussion the topic in good detail. rbtree_node_base* RBTreeRotateRight(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot) { rbtree_node_base* const pNodeTemp = pNode->mpNodeLeft; pNode->mpNodeLeft = pNodeTemp->mpNodeRight; if(pNodeTemp->mpNodeRight) pNodeTemp->mpNodeRight->mpNodeParent = pNode; pNodeTemp->mpNodeParent = pNode->mpNodeParent; if(pNode == pNodeRoot) pNodeRoot = pNodeTemp; else if(pNode == pNode->mpNodeParent->mpNodeRight) pNode->mpNodeParent->mpNodeRight = pNodeTemp; else pNode->mpNodeParent->mpNodeLeft = pNodeTemp; pNodeTemp->mpNodeRight = pNode; pNode->mpNodeParent = pNodeTemp; return pNodeRoot; } /// RBTreeInsert /// Insert a node into the tree and rebalance the tree as a result of the /// disturbance the node introduced. /// EASTL_API void RBTreeInsert(rbtree_node_base* pNode, rbtree_node_base* pNodeParent, rbtree_node_base* pNodeAnchor, RBTreeSide insertionSide) { rbtree_node_base*& pNodeRootR