include/Tree/Avl.hpp

Go to the documentation of this file.

#ifndef hpp_CPP_AVLTree_CPP_hpp
#define hpp_CPP_AVLTree_CPP_hpp

// Need comparable declaration
#include "Comparable.hpp"
// Need FIFO for iterator
#include "FIFO.hpp"
// We need Bool2Type
#include "Bool2Type.hpp"

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable: 4251)
#endif 

#ifdef _MSC_VER
#pragma warning(disable: 4786)
#endif

namespace Tree
{
    namespace AVL
    {
        using namespace ::Comparator;

        template <typename T, typename KeyType>
        struct NoDeletion
        {   inline static void deleter(T &, KeyType) {} };
        template <typename T, typename KeyType>
        struct PointerDeletion
        {   inline static void deleter(T & t, KeyType) { delete t; t = 0; } };
        template <typename T, typename KeyType>
        struct ArrayDeletion
        {   inline static void deleter(T & t, KeyType) { delete[] t; t = 0; } };

        struct AllNodes
        {
            enum Balance { LeftTreeIsHeavier = -1, Balanced = 0, RightTreeIsHeavier = 1 };
        };

        template <typename T, typename KeyType, typename DeleterT = NoDeletion<T, KeyType> > 
        struct Node : public AllNodes
        {
        // The direction
            enum { Left = 0, Right = 1 };
        
        // Interface
            inline Node*& left() { return child[Left]; } 
            inline Node*& right() { return child[Right]; }
            inline const Node*& left() const { return child[Left]; } 
            inline const Node*& right() const { return child[Right]; }

            inline void left(Node * left) { child[Left] = left; }
            inline void right(Node * right) { child[Right] = right; }

            inline Node *& fromCompare(const Comparator::CompareType comp) { return child[comp == Comparator::Greater]; }
            inline Node *& fromInverseCompare(const Comparator::CompareType comp) { return child[comp != Comparator::Greater]; }

            static inline const Balance balanceFromCompare(const Comparator::CompareType comp) { return comp == Comparator::Greater ? RightTreeIsHeavier : LeftTreeIsHeavier; }
            static inline const Balance balanceFromInverseCompare(const Comparator::CompareType comp) { return comp != Comparator::Greater ? RightTreeIsHeavier : LeftTreeIsHeavier; }
            static inline const Balance strictBalanceFromCompare(const Comparator::CompareType comp) { return comp == Comparator::Greater ? RightTreeIsHeavier : (comp == Comparator::Equal ? Balanced : LeftTreeIsHeavier); }

        // Constructor
            inline Node( Node* _root, const T& _data, KeyType _key) : rootNode(_root), data(_data), key(_key), balance(Balanced) { child[Left] = child[Right] = 0; } 
            inline ~Node() {  DeleterT::deleter(data, key); }

        // Members
            Balance                                             balance;
            Node*                                               child[2];
            Node*                                               rootNode;
            T                                                   data;
            KeyType                                             key;
        };




        template <typename T, typename KeyType, typename DeleterT = NoDeletion<T, KeyType> > 
        class Iterator
        {
        public:
            typedef Node<T, KeyType, DeleterT>  NodeT;

        public:
            mutable NodeT *             node;

        public:
            inline Iterator( NodeT* _node = NULL ) : node(_node)
            {   if(node != NULL )
                {   if( node->left() != NULL) nodes.Push( node->left() );
                    if( node->right()!= NULL) nodes.Push( node->right()); }
            }

            inline Iterator( const Iterator& iter ) : node(iter.node), nodes(iter.nodes) {}             

            // Operators
        public:
            inline T& operator *()                  { return  node->data; }
            inline const T& operator *() const      { return  node->data; }
//          inline T* operator ->()                 { return node->data; } 
//          inline const T* operator ->() const     { return node->data; } 

            inline void Mutate(const T & newData)   { node->data = newData; }
            
            inline Iterator& operator ++() const
            {   if (nodes.getSize())
                {
                    node = nodes.Pop();
                    if( node->left() ) nodes.Push( node->left() );
                    if( node->right()) nodes.Push( node->right());
                }
                else node = 0;
                return *const_cast<Iterator*>( this );
            }

            inline Iterator operator ++(int) const                  { Iterator tmp(*this); ++(*this); return tmp; }
            inline bool operator ==( const Iterator& rhs ) const    { return(node==rhs.node); }
            inline bool operator !=( const Iterator& rhs ) const    { return(node!=rhs.node); }

            inline Iterator& operator = ( const Iterator& iter ) const { node = iter.node; nodes = iter.nodes; return *const_cast< Iterator* >(this); }

            inline bool isValid() const { return node != NULL; }

            inline Iterator getLeftIterator() const { return Iterator( node != NULL ? node->left() : NULL ); }
            inline Iterator getRightIterator() const { return Iterator( node != NULL ? node->right() : NULL ); }
            inline Iterator getParentIterator() const { return Iterator( node != NULL ? node->rootNode : NULL ); }
            inline bool isTerminal() const { return node != NULL && node->left() == NULL && node->right() == NULL; }
            inline const KeyType * getKey() const { if (node) return &node->key; return 0; } 

        private:
            mutable Stack::PlainOldData::FIFO< NodeT* >   nodes;
        };


        typedef Bool2Type<true>     LeftSide;
        typedef Bool2Type<false>    RightSide;


        template <bool bLeft>       struct selectBalance { enum { Result = AllNodes::LeftTreeIsHeavier }; };
        template <>                 struct selectBalance<false> { enum { Result = AllNodes::RightTreeIsHeavier }; };
        template <bool bLeft>       struct invSelectBalance { enum { Result = AllNodes::RightTreeIsHeavier }; };
        template <>                 struct invSelectBalance<false> { enum { Result = AllNodes::LeftTreeIsHeavier }; };


        template < typename T, typename KeyType, class Policy = Comparator::DefaultComparator, typename DeleterT = NoDeletion<T, KeyType> > 
        class Tree
        {   
            // Members
        private:
            typedef Node<T, KeyType, DeleterT>              NodeT;
            typedef typename NodeT::Balance                     ResultT;
            typedef ::Comparator::Comparable<KeyType, Policy>   CompareT;

            NodeT *     root;
            uint32      size;

        private:
            enum OperationResult { Ok = 1, NeedReBalancing = 0, Invalid = -1 };
            
        protected:
            enum { NoRelativeParent =  NULL, };

            // Interface which still keep the tree balanced
        public:
            typedef Iterator<T, KeyType, DeleterT>      IterT;

            inline bool insertObject( const T& obj, KeyType key)
            {
                if (insertInTree(&root, obj, key) == Invalid) return false;
                size++; return true;
            }

            inline bool Delete( KeyType key )
            {
                return deleteInTree(&root, key) != Invalid;
            }

            inline bool Delete( const IterT & iter )
            {
                // Check invariant 
                if(!iter.isValid()) return false;

                // Suppose it is going to work
                OperationResult result = Ok;

                // If we are working with the root node, then handle the case correctly
                if (iter.node->rootNode == NULL || iter.node->rootNode->rootNode == NULL)
                {   // We can use the other function for this (as the search will directly give the correct result)
                    return deleteInTree(&root, iter.node->key) != Invalid;
                }
                // Else perform the search from the root itself
                else 
                {
                    // We need to walk up the tree until we find a parent whose balance is Balanced
                    NodeT * current = iter.node->rootNode->rootNode;
                    while (current && current->balance != AllNodes::Balanced)
                    {   // Simply go up
                        current = current->rootNode;
                    }
                    // Not found, so call the other algorithm to sort this out
                    if (!current || !current->rootNode) return deleteInTree(&root, iter.node->key) != Invalid;
                    
                    // Need to find the right root node address then
                    NodeT ** newRoot = current->rootNode->left() == current ? &current->rootNode->left() : &current->rootNode->right();
                    return deleteInTree(newRoot, iter.node->key) != Invalid;
                }
            }

            inline void Clear()
            {
                if (root)   deleteTree(root);
                root = 0; size = 0;
            }

            inline bool checkTree()
            {
                return checkTree(root);
            }
            inline bool checkTree(NodeT * node)
            {
                if (!node) return true;
                CompareT        key(node->key);
                if (node->left() && node->left()->rootNode != node && key.Compare(node->left()->key) != Comparator::Less) 
                    return false; 
                if (node->right() && node->right()->rootNode != node && key.Compare(node->left()->key) != Comparator::Greater) 
                    return false;
                if (!node->right() && !node->left())
                {
                    if (node->balance != AllNodes::Balanced)
                        return false;
                } else
                {
                    if (!node->right() && node->balance != AllNodes::LeftTreeIsHeavier)
                        return false;
                    if (!node->left() && node->balance != AllNodes::RightTreeIsHeavier)
                        return false;
                }
                return checkTree(node->left()) && checkTree(node->right());
            }

            // Construction and destruction
        public:
            Tree() : root(NULL), size(0) {}
            virtual ~Tree() { Clear(); }
            
            // Helpers functions
        private:
            NodeT * rotate2(NodeT ** parent, typename CompareT::Result result)
            {
                NodeT *B, *C, *D, *E;
                NodeT *Bparent = (*parent)->rootNode;
                B = *parent;
                if (result == Comparator::Greater)
                {
                    D = B->right();
                    C = D->left();
                    E = D->right();

                    *parent = D;
                
                    D->left(B);
                    B->right(C);
                } else
                {
                    D = B->left();
                    C = D->right();
                    E = D->left();

                    *parent = D;
                
                    D->right(B);
                    B->left(C);
                }
                // Fix the parent nodes
                if (C) C->rootNode = B;
                B->rootNode = D;
                D->rootNode = Bparent;
                B->balance = AllNodes::Balanced;
                D->balance = AllNodes::Balanced;
                return E;
            }

            NodeT * rotate3(NodeT ** parent, typename CompareT::Result result, AllNodes::Balance third)
            {
                NodeT *B, *F, *D, *C, *E;
                NodeT *Bparent = (*parent)->rootNode;
                B = *parent;

                if (result == Comparator::Greater)
                {
                    F = B->right();
                    D = F->left();
                    C = D->left();
                    E = D->right();

                    *parent = D;
                
                    D->left(B);
                    D->right(F);
                    B->right(C);
                    F->left(E);
                } else
                {
                    F = B->left();
                    D = F->right();
                    C = D->right();
                    E = D->left();

                    *parent = D;
                
                    D->right(B);
                    D->left(F);
                    B->left(C);
                    F->right(E);
                }

                // Fix the parent nodes
                if (F) F->rootNode = D;
                if (C) C->rootNode = B;
                if (E) E->rootNode = F; 
                B->rootNode = D;
                D->rootNode = Bparent;

                D->balance = B->balance = F->balance = AllNodes::Balanced;

                if (third == AllNodes::Balanced) return 0;
                else if (third == D->balanceFromCompare(result)) 
                {
                    /* E holds the insertion so B is unbalanced */ 
                    B->balance = B->balanceFromInverseCompare(result);
                    return E;
                } else 
                {
                    /* C holds the insertion so F is unbalanced */
                    F->balance = F->balanceFromCompare(result);
                    return C;
                }
            }            

            OperationResult rebalancePath(NodeT* current, CompareT & keyToCheck)
            {
                typename CompareT::Result result = current ? keyToCheck.Compare(current->key) : Comparator::Equal;
                while (current && result != Comparator::Equal)
                {
                    current->balance = current->balanceFromCompare(result);
                    current = current->fromCompare(result);
                    result = keyToCheck.Compare(current->key);
                }
                return Ok;
            }


            OperationResult rebalanceAfterInsert(NodeT** parent, CompareT & keyToCheck)
            {
                NodeT * current = *parent;
                typename CompareT::Result first, second;
                if (current->balance != AllNodes::Balanced)
                {
                    first = keyToCheck.Compare(current->key);
                    NodeT * next = current->fromCompare(first); 
                    if (!next) return Invalid;
                    second = keyToCheck.Compare(next->key);
                    bool biggerFirst = first == Comparator::Greater;
                    bool biggerSecond = second == Comparator::Greater;

                    if (current->balance != current->balanceFromCompare(first))
                    {   // Follow the shorter path
                        current->balance = AllNodes::Balanced;
                        current = next;
                    }
                    else if (biggerFirst == biggerSecond)
                    {   // Two point rotate
                        current = rotate2(parent, first);
                    } else
                    {   // Double rotation
                        current = next->fromCompare(second);
                        AllNodes::Balance third;
                        second = keyToCheck.Compare(current->key);
                        third = current->strictBalanceFromCompare(second);
                        current = rotate3(parent, first, third);
                    }
                }
                return rebalancePath(current, keyToCheck);
            }

            OperationResult insertInTree( NodeT** parent, const T& obj, KeyType key)
            {
                // Let's consider it will succeed 
                OperationResult result = Ok;
                CompareT        keyToCheck(key);

                // Find where to insert the node
                // A parent node exists, need to select the right subtree
                NodeT * current = *parent;
                NodeT ** balancer = parent;
                NodeT ** previousRoot = parent;
                typename CompareT::Result compareResult = Comparator::Greater;
                while (current && compareResult != Comparator::Equal)
                {
                    typename CompareT::Result compareResult = keyToCheck.Compare(current->key);
                    if (current->balance != AllNodes::Balanced) balancer = parent;

                    previousRoot = parent;
                    parent = &current->fromCompare(compareResult);
                    current = *parent;
                }

                // Already exist, so reject the insert
                if (current) return Invalid;

                // Create the node
                current = new NodeT(*previousRoot, obj, key);
                *parent = current;

                return rebalanceAfterInsert(balancer, keyToCheck);
            }
            
            static inline void SwapAndDelete(NodeT ** targetParent, NodeT ** parent, typename CompareT::Result result)
            {
                bool same = targetParent == parent;
                
                NodeT * newTarget = *targetParent;
                NodeT * current = *parent;

                NodeT * rootNode = newTarget->rootNode;
                *targetParent = current;
                int currentOnLeft = -1;
                if (current->rootNode) currentOnLeft = current->rootNode->left() == current;
                *parent = current->fromInverseCompare(result);
                
                current->left(newTarget->left());
                current->right(newTarget->right());
                current->balance = newTarget->balance;
                if (currentOnLeft != -1)
                {
                    if (currentOnLeft)
                    {
                        if (current->rootNode->left()) current->rootNode->left()->rootNode = current->rootNode;
                    }
                    else if (current->rootNode->right()) current->rootNode->right()->rootNode = current->rootNode;
                }
                current->rootNode = rootNode;
                if (current->left()) current->left()->rootNode = current;
                if (current->right()) current->right()->rootNode = current;
                
                if (same && *parent) (*parent)->rootNode = rootNode;
                delete newTarget;
            }

            NodeT** rebalanceAfterDelete(NodeT** parent, CompareT & keyToCheck, NodeT ** targetParent)
            {
                NodeT * newTarget = *targetParent;

                while (1)
                {
                    NodeT * current = *parent;
                    typename CompareT::Result compareResult = keyToCheck.Compare(current->key);
                    NodeT * next = current->fromCompare(compareResult);
                    if (!next) break;

                    if (current->balance == AllNodes::Balanced)
                        current->balance = current->balanceFromInverseCompare(compareResult);
                    else if (current->balance == current->balanceFromCompare(compareResult))
                        current->balance = AllNodes::Balanced;
                    else
                    {
                        NodeT * invertNext = current->fromInverseCompare(compareResult);
                        typename CompareT::Result invertResult = compareResult == Comparator::Greater ? Comparator::Less : Comparator::Greater;
                        if (invertNext->balance == current->balanceFromCompare(compareResult))
                        {   
                            NodeT * nextInvertNext = invertNext->fromCompare(compareResult);
                            rotate3(parent, invertResult, nextInvertNext->balance);
                        } else if (invertNext->balance == AllNodes::Balanced)
                        {
                            rotate2(parent, invertResult);
                            current->balance = current->balanceFromInverseCompare(compareResult);
                            (*parent)->balance = current->balanceFromCompare(compareResult);
                        } else rotate2(parent, invertResult);

                        if (current == newTarget)
                            targetParent = &(*parent)->fromCompare(compareResult);
                    }

                    parent = &current->fromCompare(compareResult);
                }
                
                return targetParent;
            }

            OperationResult deleteInTree( NodeT** parent, KeyType key )
            {
                // Check parameters
                if (parent == NULL || *parent == NULL)  return Invalid;

                CompareT keyToFind(key);
                OperationResult             result = Ok;

                NodeT * current = *parent;
                NodeT ** targetParent = 0;
                NodeT ** balanced = parent;

                typename CompareT::Result compareResult = Comparator::Equal;
                while (current)
                {
                    compareResult = keyToFind.Compare(current->key);
                    if (compareResult == Comparator::Equal)
                    {   // Ok, we have found it
                        targetParent = parent;
                    }
                    // Then need to find with node to swap this one (or continue searching)
                    NodeT * next = current->fromCompare(compareResult);
                    if (!next) break;

                    // Check the balance to determine which node to balance with once deleted
                    NodeT * invertNext = current->fromInverseCompare(compareResult);
                    if (current->balance == AllNodes::Balanced
                        || (current->balance == current->balanceFromInverseCompare(compareResult) && invertNext->balance == AllNodes::Balanced))
                        balanced = parent;

                    parent = &current->fromCompare(compareResult);
                    current = *parent;
                }

                // Not found ?
                if (!targetParent) return Invalid;

                targetParent = rebalanceAfterDelete(balanced, keyToFind, targetParent);
                SwapAndDelete(targetParent, parent, compareResult);
                
                --size;
                return Ok;
            }           


            void deleteTree(NodeT* node)
            {
                NodeT * current = node;
                while (current)
                {
                    if (current->left()) { current = current->left(); continue; }
                    if (current->right()) { current = current->right(); continue; }
                    NodeT * previous = current->rootNode;
                    delete current;
                    if (previous && previous->left() == current) previous->left(0);
                    if (previous && previous->right() == current) previous->right(0);
                    current = previous;
                }
            }

            inline  NodeT** getRootOf(NodeT* node)
            {
                // If the node is already root, or the tree as no node
                if (root == NULL || node == NULL || node->rootNode == NULL) return NULL;
                // If the root node of the given node is the tree root node, return our root node
                else if (node->rootNode->rootNode == NULL)  return &root;
                // Else check if the root node is the left node of the root node, and return the left node
                else if (node->rootNode == node->rootNode->rootNode->left())    return &node->rootNode->rootNode->left();
                // Else it is the right node
                return &node->rootNode->rootNode->right();              
            }


            inline NodeT *& selectSide(NodeT * node, LeftSide *)        { return node->left(); }
            inline NodeT *& selectSide(NodeT * node, RightSide *)       { return node->right();}
            inline NodeT *& invSelectSide(NodeT * node, LeftSide *)     { return node->right();}
            inline NodeT *& invSelectSide(NodeT * node, RightSide *)    { return node->left();}

            template <bool bLeft>   inline void rotate(NodeT ** node, Bool2Type<bLeft>* select)
            {
                // Check argument
                if (node == NULL) return;
                
                // Rotate right and left (or vice versa)
                NodeT* tmp = *node;
                *node = invSelectSide(tmp, select);
                invSelectSide(tmp, select) = selectSide(*node, select);
                selectSide(*node, select) = tmp;

                // Rotate root node with left/right node
                (*node)->rootNode = tmp->rootNode;
                tmp->rootNode = *node;
                if (invSelectSide(tmp, select) != NULL) invSelectSide(tmp, select)->rootNode = selectSide(*node, select);                   
            }
            
            template <bool bLeft>   inline OperationResult balanceShrunk(NodeT ** node, Bool2Type<bLeft>* select)
            {
                switch( (*node)->balance )
                {
                    case selectBalance<bLeft>::Result :
                        {   (*node)->balance = NodeT::Balanced;
                            return NeedReBalancing; }
                    case NodeT::Balanced:
                        {   (*node)->balance = (typename NodeT::Balance)invSelectBalance<bLeft>::Result;
                            return Ok;  }
                    case invSelectBalance<bLeft>::Result:
                    {
                        switch (invSelectSide(*node, select)->balance)
                        {
                            case selectBalance<bLeft>::Result:
                            {
                                switch (selectSide(invSelectSide(*node, select), select)->balance)
                                {
                                    case selectBalance<bLeft>::Result:
                                    {
                                        (*node)->balance = NodeT::Balanced;
                                        invSelectSide(*node, select)->balance = (typename NodeT::Balance)invSelectBalance<bLeft>::Result;
                                        break;
                                    }

                                    case NodeT::Balanced:
                                    {
                                        (*node)->balance = NodeT::Balanced;
                                        invSelectSide(*node, select)->balance = NodeT::Balanced;
                                        break;
                                    }

                                    case invSelectBalance<bLeft>::Result:
                                    {
                                        (*node)->balance = (typename NodeT::Balance)selectBalance<bLeft>::Result;
                                        invSelectSide(*node, select)->balance = NodeT::Balanced;
                                        break;
                                    }
                                }

                                selectSide(invSelectSide(*node, select), select)->balance = NodeT::Balanced;

                                // Inverted rotate invoked
                                rotate(&invSelectSide(*node, select), (Bool2Type<!bLeft>*)0);
                                // Normal rotate here
                                rotate(node, select);

                                return NeedReBalancing;
                            }

                            case NodeT::Balanced:
                            {
                                (*node)->balance = (typename NodeT::Balance)invSelectBalance<bLeft>::Result;
                                invSelectSide(*node, select)->balance = (typename NodeT::Balance)selectBalance<bLeft>::Result;
                                rotate(node, select);
                                return Ok;
                            }

                            case invSelectBalance<bLeft>::Result:
                            {
                                (*node)->balance = invSelectSide(*node, select)->balance = NodeT::Balanced;
                                rotate(node, select);
                                return NeedReBalancing;
                            }
                        }
                        break;
                    }
                }
                return Invalid;
            }

            template <bool bLeft>   inline OperationResult balanceExpanded(NodeT ** node, Bool2Type<bLeft>* select)
            {
                switch ((*node)->balance)
                {
                    case selectBalance<bLeft>::Result :
                        {
                            if (selectSide(*node, select)->balance == (typename NodeT::Balance)selectBalance<bLeft>::Result)
                                {   (*node)->balance = selectSide(*node, select)->balance = NodeT::Balanced;
                                    // Inverted rotate invoked
                                    rotate(node, (Bool2Type<!bLeft>*)0);    }
                            else
                            {   switch (invSelectSide(selectSide(*node, select), select)->balance)
                                {
                                case selectBalance<bLeft>::Result :
                                    {
                                        (*node)->balance = (typename NodeT::Balance)invSelectBalance<bLeft>::Result;
                                        selectSide(*node, select)->balance = NodeT::Balanced;
                                        break;
                                    }
                                    
                                case NodeT::Balanced:
                                    {
                                        (*node)->balance = NodeT::Balanced;
                                        selectSide(*node, select)->balance = NodeT::Balanced;
                                        break;
                                    }
                                    
                                case invSelectBalance<bLeft>::Result:
                                    {
                                        (*node)->balance = NodeT::Balanced;
                                        selectSide(*node, select)->balance = (typename NodeT::Balance)selectBalance<bLeft>::Result;
                                        break;
                                    }
                                }
                                
                                invSelectSide(selectSide(*node, select), select)->balance = NodeT::Balanced;
                                
                                // Forward rotate
                                rotate(&selectSide(*node, select), select);
                                // Inverted rotate
                                rotate(node, (Bool2Type<!bLeft>*)0);    
                            }
                            return Ok;
                        }
                        
                    case NodeT::Balanced:
                        {
                            (*node)->balance = (typename NodeT::Balance)selectBalance<bLeft>::Result;
                            return NeedReBalancing;
                        }
                        
                    case invSelectBalance<bLeft>::Result:
                        {
                            (*node)->balance = NodeT::Balanced;
                            return Ok;
                        }
                }
                return Invalid;
            }

            template <class U>
            void Swap(U & a, U & b)
            {
                U tmp = a;
                a = b;
                b = tmp;
            }

            inline void SwapNodes(NodeT * & a, NodeT * & b)
            {
                // We want to do a = b and b = a
                // First, save the side of a and b compared to their root node
                int aWasLeftOfARoot = a->rootNode ? a->rootNode->left() == a : -1;
                int bWasLeftOfBRoot = b->rootNode ? b->rootNode->left() == b : -1;

                // This means a.left = b.left and a.right = b.right and a.root = b.root and a.balance = b.balance while (same thing for b)
                NodeT * oldBRight = b->right(), * oldBLeft = b->left(), * oldBRoot = b->rootNode, * tmpNode = b;
                NodeT::Balance oldBBalance = b->balance;

                // Set swap the pointers
                b->rootNode = a->rootNode;
                b->left(a->left());
                b->right(a->right());
                b->balance = a->balance;

                a->rootNode = oldBRoot;
                // Check if we are not overwriting the address
                bool bLeftHack = false, bRightHack = false;
                if (&a->left() != &b) a->left(oldBLeft);
                else // We are
                {   // This means that a->left was b initially, it must be cleaned after the swap
                    bLeftHack = true;
                }
                
                if (&a->right() != &b) a->right(oldBRight);
                else // We are
                {   // This means that a->left was b initially, it must be cleaned after the swap
                    bRightHack = true;
                }
                a->balance = oldBBalance;

                // Swap the nodes themselves
                Swap(a, b);

                // Make sure the child node have correct pointers too
                if (a->left()) a->left()->rootNode = a;
                if (a->right()) a->right()->rootNode = a;
                if (b->left()) b->left()->rootNode = b;
                if (b->right()) b->right()->rootNode = b;

                // And update the root pointers
                if (a->rootNode) 
                {
                    if (aWasLeftOfARoot == 0) a->rootNode->right(a); 
                    else if (aWasLeftOfARoot == 1) a->rootNode->left(a);
                }
                if (b->rootNode) 
                {
                    if (bWasLeftOfBRoot == 0) b->rootNode->right(b); 
                    else if (bWasLeftOfBRoot == 1) b->rootNode->left(b);
                }

                // Don't let error propagate
                if (bLeftHack) { a->left(0); b->left(0); a->balance = a->right() ? AllNodes::RightTreeIsHeavier : AllNodes::Balanced; }
                if (bRightHack) { a->right(0); b->right(0); a->balance = a->left() ? AllNodes::LeftTreeIsHeavier : AllNodes::Balanced; }
            }


            template <bool bLeft> inline bool replaceWith(NodeT*& target, NodeT** subtree, OperationResult& result, Bool2Type<bLeft> * select)
            {
                if (subtree == NULL) return false;

                result = NeedReBalancing;
                if (*subtree == NULL) return false;

                if (invSelectSide(*subtree, select) != NULL)
                {
                    NodeT *& oldSubtreeNode = (*subtree)->rootNode;
                    if (oldSubtreeNode == NULL) return false;
                    bool wasOnLeft = oldSubtreeNode->left() == *subtree;
                    NodeT *& oldSubtree = wasOnLeft ? oldSubtreeNode->left() : oldSubtreeNode->right();
                    if (!replaceWith(target, & invSelectSide(*subtree, select), result, select))
                        return false;
                    
                    // Subtree has probably been deleted, so handle the case
                    subtree = wasOnLeft ? &oldSubtreeNode->left() : &oldSubtreeNode->right();
                    if (result == NeedReBalancing)  result = balanceShrunk(subtree, (Bool2Type<!bLeft>*)0);
                    return true;
                }

                // Perform the replacement
                // Try the swap method
                NodeT * stSave = target;
                SwapNodes(target, *subtree);
                if (*subtree)
                {   // If the swap was done on a different node than the left node of target
                    stSave = *subtree;
                    if ((*subtree)->rootNode != NULL) 
                    {
                        if ((*subtree)->rootNode->left == *subtree)     (*subtree)->rootNode->left(NULL);
                        else                                            (*subtree)->rootNode->right(NULL);
                    }
                } else result = Ok;
                delete stSave;
                return true;
            }

            template <bool bLeft> inline bool replaceAndRebalance(NodeT *& target, NodeT ** subtree, NodeT **& self, NodeT **& relativeRoot, Bool2Type<bLeft> * select)
            {
                OperationResult result = Ok;
                if (!replaceWith(target, subtree, result, select))
                {
                    if (result == NeedReBalancing)
                    {
                        result = balanceShrunk(self, select);
                        while ((result == NeedReBalancing) && relativeRoot)
                        {
                            bool left = (*self ==(*relativeRoot)->left());
                            self = relativeRoot;
                            relativeRoot = getRootOf(*self);
                            if (left) result = balanceShrunk(self, (LeftSide*)0);
                            else      result = balanceShrunk(self, (RightSide*)0);
                        }
                    }
                    return true;
                } else if (result == NeedReBalancing)
                {   // We can't assume self is correct anymore
                    self = &target;
                    if (!relativeRoot)
                        result = balanceShrunk(self, select);
                    else while ((result == NeedReBalancing) && relativeRoot)
                    {
                        bool left = (*self ==(*relativeRoot)->left());
                        self = relativeRoot;
                        relativeRoot = getRootOf(*self);
                        if (left) result = balanceShrunk(self, (LeftSide*)0);
                        else      result = balanceShrunk(self, (RightSide*)0);
                    }
                }
                return true;
            }

            // Accessors
        public:
            inline uint32 getSize() const { return (uint32)size; }
            
            inline bool isEmpty() const { return root == NULL; }
            
            inline IterT getFirstIterator() { return IterT(root); }
            inline const IterT getFirstIterator() const { return IterT(root); }
            
            inline IterT getLastIterator() { return IterT(NULL); }
            inline const IterT getLastIterator() const { return IterT(NULL); }
            
            inline IterT searchFor(KeyType key) const
            {
                if (root == NULL) return getLastIterator();
                NodeT * node = root;
                NodeT * best = NULL;
                CompareT keyToLookFor(key);
                while (node != NULL)
                {
                    typename CompareT::Result result = keyToLookFor.Compare(node->key);
                    // Found ?
                    if (result == Comparator::Equal)    { best = node; break; }
                    // No, let's select the correct subtree based on comparison
                    else if (result == Comparator::Less)
                    {   node = node->left(); }
                    else // Less
                    {   node = node->right();   }
                }
                return IterT(best != NULL ? best : NULL);               
            }

            inline IterT    searchExtreme(const bool lowest) const
            {
                if (root == NULL) return getLastIterator();
                NodeT * node = root;
                if (lowest)
                {
                    while (node->left() != NULL) node = node->left(); 
                } else
                {
                    while (node->right() != NULL) node = node->right(); 
                }
                return IterT(node);
            }
        };
    }
}

#ifdef _MSC_VER
#pragma warning(pop)
#endif

#endif  

(C) An X-Ryl669 project 2007

This document describes Unlimited Zooming Interface source code. UZI stands for Unlimited Zooming Interface, and source code license is