irrMap.h

// Copyright (C) 2006-2012 by Kat'Oun
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h
 
#ifndef __IRR_MAP_H_INCLUDED__
#define __IRR_MAP_H_INCLUDED__
 
#include "irrTypes.h"
#include "irrMath.h"
 
namespace irr
{
namespace core
{

template <class KeyType, class ValueType>
class map
{
    template <class KeyTypeRB, class ValueTypeRB>
    class RBTree
    {
    public:
 
        RBTree(const KeyTypeRB& k, const ValueTypeRB& v)
            : LeftChild(0), RightChild(0), Parent(0), Key(k),
                Value(v), IsRed(true) {}
 
        void setLeftChild(RBTree* p)
        {
            LeftChild=p;
            if (p)
                p->setParent(this);
        }
 
        void setRightChild(RBTree* p)
        {
            RightChild=p;
            if (p)
                p->setParent(this);
        }
 
        void setParent(RBTree* p) { Parent=p; }
 
        void setValue(const ValueTypeRB& v) { Value = v; }
 
        void setRed() { IsRed = true; }
        void setBlack() { IsRed = false; }
 
        RBTree* getLeftChild() const { return LeftChild; }
        RBTree* getRightChild() const { return RightChild; }
        RBTree* getParent() const { return Parent; }
 
        const ValueTypeRB& getValue() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return Value;
        }
 
        ValueTypeRB& getValue()
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return Value;
        }
 
        const KeyTypeRB& getKey() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return Key;
        }
 
        bool isRoot() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return Parent==0;
        }
 
        bool isLeftChild() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return (Parent != 0) && (Parent->getLeftChild()==this);
        }
 
        bool isRightChild() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return (Parent!=0) && (Parent->getRightChild()==this);
        }
 
        bool isLeaf() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return (LeftChild==0) && (RightChild==0);
        }
 
        unsigned int getLevel() const
        {
            if (isRoot())
                return 1;
            else
                return getParent()->getLevel() + 1;
        }
 
 
        bool isRed() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return IsRed;
        }
 
        bool isBlack() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return !IsRed;
        }
 
    private:
        RBTree();
 
        RBTree* LeftChild;
        RBTree* RightChild;
 
        RBTree* Parent;
 
        KeyTypeRB Key;
        ValueTypeRB Value;
 
        bool IsRed;
    }; // RBTree
 
    public:
 
    typedef RBTree<KeyType,ValueType> Node;
    // We need the forwad declaration for the friend declaration
    class ConstIterator;

    class Iterator
    {
        friend class ConstIterator;
    public:
 
        Iterator() : Root(0), Cur(0) {}
 
        // Constructor(Node*)
        Iterator(Node* root) : Root(root)
        {
            reset();
        }
 
        // Copy constructor
        Iterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {}
 
        void reset(bool atLowest=true)
        {
            if (atLowest)
                Cur = getMin(Root);
            else
                Cur = getMax(Root);
        }
 
        bool atEnd() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return Cur==0;
        }
 
        Node* getNode() const
        {
            return Cur;
        }
 
        Iterator& operator=(const Iterator& src)
        {
            Root = src.Root;
            Cur = src.Cur;
            return (*this);
        }
 
        void operator++(int)
        {
            inc();
        }
 
        void operator--(int)
        {
            dec();
        }
 
        Node* operator->()
        {
            return getNode();
        }
 
        Node& operator*()
        {
            _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
 
            return *Cur;
        }
 
    private:
 
        Node* getMin(Node* n) const
        {
            while(n && n->getLeftChild())
                n = n->getLeftChild();
            return n;
        }
 
        Node* getMax(Node* n) const
        {
            while(n && n->getRightChild())
                n = n->getRightChild();
            return n;
        }
 
        void inc()
        {
            // Already at end?
            if (Cur==0)
                return;
 
            if (Cur->getRightChild())
            {
                // If current node has a right child, the next higher node is the
                // node with lowest key beneath the right child.
                Cur = getMin(Cur->getRightChild());
            }
            else if (Cur->isLeftChild())
            {
                // No right child? Well if current node is a left child then
                // the next higher node is the parent
                Cur = Cur->getParent();
            }
            else
            {
                // Current node neither is left child nor has a right child.
                // Ie it is either right child or root
                // The next higher node is the parent of the first non-right
                // child (ie either a left child or the root) up in the
                // hierarchy. Root's parent is 0.
                while(Cur->isRightChild())
                    Cur = Cur->getParent();
                Cur = Cur->getParent();
            }
        }
 
        void dec()
        {
            // Already at end?
            if (Cur==0)
                return;
 
            if (Cur->getLeftChild())
            {
                // If current node has a left child, the next lower node is the
                // node with highest key beneath the left child.
                Cur = getMax(Cur->getLeftChild());
            }
            else if (Cur->isRightChild())
            {
                // No left child? Well if current node is a right child then
                // the next lower node is the parent
                Cur = Cur->getParent();
            }
            else
            {
                // Current node neither is right child nor has a left child.
                // Ie it is either left child or root
                // The next higher node is the parent of the first non-left
                // child (ie either a right child or the root) up in the
                // hierarchy. Root's parent is 0.
 
                while(Cur->isLeftChild())
                    Cur = Cur->getParent();
                Cur = Cur->getParent();
            }
        }
 
        Node* Root;
        Node* Cur;
    }; // Iterator

    class ConstIterator
    {
        friend class Iterator;
    public:
 
        ConstIterator() : Root(0), Cur(0) {}
 
        // Constructor(Node*)
        ConstIterator(const Node* root) : Root(root)
        {
            reset();
        }
 
        // Copy constructor
        ConstIterator(const ConstIterator& src) : Root(src.Root), Cur(src.Cur) {}
        ConstIterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {}
 
        void reset(bool atLowest=true)
        {
            if (atLowest)
                Cur = getMin(Root);
            else
                Cur = getMax(Root);
        }
 
        bool atEnd() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return Cur==0;
        }
 
        const Node* getNode() const
        {
            return Cur;
        }
 
        ConstIterator& operator=(const ConstIterator& src)
        {
            Root = src.Root;
            Cur = src.Cur;
            return (*this);
        }
 
        void operator++(int)
        {
            inc();
        }
 
        void operator--(int)
        {
            dec();
        }
 
        const Node* operator->()
        {
            return getNode();
        }
 
        const Node& operator*()
        {
            _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
 
            return *Cur;
        }
 
    private:
 
        const Node* getMin(const Node* n) const
        {
            while(n && n->getLeftChild())
                n = n->getLeftChild();
            return n;
        }
 
        const Node* getMax(const Node* n) const
        {
            while(n && n->getRightChild())
                n = n->getRightChild();
            return n;
        }
 
        void inc()
        {
            // Already at end?
            if (Cur==0)
                return;
 
            if (Cur->getRightChild())
            {
                // If current node has a right child, the next higher node is the
                // node with lowest key beneath the right child.
                Cur = getMin(Cur->getRightChild());
            }
            else if (Cur->isLeftChild())
            {
                // No right child? Well if current node is a left child then
                // the next higher node is the parent
                Cur = Cur->getParent();
            }
            else
            {
                // Current node neither is left child nor has a right child.
                // Ie it is either right child or root
                // The next higher node is the parent of the first non-right
                // child (ie either a left child or the root) up in the
                // hierarchy. Root's parent is 0.
                while(Cur->isRightChild())
                    Cur = Cur->getParent();
                Cur = Cur->getParent();
            }
        }
 
        void dec()
        {
            // Already at end?
            if (Cur==0)
                return;
 
            if (Cur->getLeftChild())
            {
                // If current node has a left child, the next lower node is the
                // node with highest key beneath the left child.
                Cur = getMax(Cur->getLeftChild());
            }
            else if (Cur->isRightChild())
            {
                // No left child? Well if current node is a right child then
                // the next lower node is the parent
                Cur = Cur->getParent();
            }
            else
            {
                // Current node neither is right child nor has a left child.
                // Ie it is either left child or root
                // The next higher node is the parent of the first non-left
                // child (ie either a right child or the root) up in the
                // hierarchy. Root's parent is 0.
 
                while(Cur->isLeftChild())
                    Cur = Cur->getParent();
                Cur = Cur->getParent();
            }
        }
 
        const Node* Root;
        const Node* Cur;
    }; // ConstIterator
 


    class ParentFirstIterator
    {
    public:
 
    ParentFirstIterator() : Root(0), Cur(0) {}
 
    explicit ParentFirstIterator(Node* root) : Root(root), Cur(0)
    {
        reset();
    }
 
    void reset()
    {
        Cur = Root;
    }
 
    bool atEnd() const
    {
        _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
        return Cur==0;
    }
 
    Node* getNode()
    {
        return Cur;
    }
 
    ParentFirstIterator& operator=(const ParentFirstIterator& src)
    {
        Root = src.Root;
        Cur = src.Cur;
        return (*this);
    }
 
    void operator++(int)
    {
        inc();
    }
 
    Node* operator -> ()
    {
        return getNode();
    }
 
    Node& operator* ()
    {
        _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
 
        return *getNode();
    }
 
    private:
 
    void inc()
    {
        // Already at end?
        if (Cur==0)
            return;
 
        // First we try down to the left
        if (Cur->getLeftChild())
        {
            Cur = Cur->getLeftChild();
        }
        else if (Cur->getRightChild())
        {
            // No left child? The we go down to the right.
            Cur = Cur->getRightChild();
        }
        else
        {
            // No children? Move up in the hierarcy until
            // we either reach 0 (and are finished) or
            // find a right uncle.
            while (Cur!=0)
            {
                // But if parent is left child and has a right "uncle" the parent
                // has already been processed but the uncle hasn't. Move to
                // the uncle.
                if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
                {
                    Cur = Cur->getParent()->getRightChild();
                    return;
                }
                Cur = Cur->getParent();
            }
        }
    }
 
    Node* Root;
    Node* Cur;
 
    }; // ParentFirstIterator
 


    class ParentLastIterator
    {
    public:
 
        ParentLastIterator() : Root(0), Cur(0) {}
 
        explicit ParentLastIterator(Node* root) : Root(root), Cur(0)
        {
            reset();
        }
 
        void reset()
        {
            Cur = getMin(Root);
        }
 
        bool atEnd() const
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return Cur==0;
        }
 
        Node* getNode()
        {
            return Cur;
        }
 
        ParentLastIterator& operator=(const ParentLastIterator& src)
        {
            Root = src.Root;
            Cur = src.Cur;
            return (*this);
        }
 
        void operator++(int)
        {
            inc();
        }
 
        Node* operator -> ()
        {
            return getNode();
        }
 
        Node& operator* ()
        {
            _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
 
            return *getNode();
        }
    private:
 
        Node* getMin(Node* n)
        {
            while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0))
            {
                if (n->getLeftChild())
                    n = n->getLeftChild();
                else
                    n = n->getRightChild();
            }
            return n;
        }
 
        void inc()
        {
            // Already at end?
            if (Cur==0)
                return;
 
            // Note: Starting point is the node as far down to the left as possible.
 
            // If current node has an uncle to the right, go to the
            // node as far down to the left from the uncle as possible
            // else just go up a level to the parent.
            if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
            {
                Cur = getMin(Cur->getParent()->getRightChild());
            }
            else
                Cur = Cur->getParent();
        }
 
        Node* Root;
        Node* Cur;
    }; // ParentLastIterator
 
 
    // AccessClass is a temporary class used with the [] operator.
    // It makes it possible to have different behavior in situations like:
    // myTree["Foo"] = 32;
    // If "Foo" already exists update its value else insert a new element.
    // int i = myTree["Foo"]
    // If "Foo" exists return its value.
    class AccessClass
    {
        // Let map be the only one who can instantiate this class.
        friend class map<KeyType, ValueType>;
 
    public:
 
        // Assignment operator. Handles the myTree["Foo"] = 32; situation
        void operator=(const ValueType& value)
        {
            // Just use the Set method, it handles already exist/not exist situation
            Tree.set(Key,value);
        }
 
        // ValueType operator
        operator ValueType()
        {
            Node* node = Tree.find(Key);
 
            // Not found
            _IRR_DEBUG_BREAK_IF(node==0) // access violation
 
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return node->getValue();
        }
 
    private:
 
        AccessClass(map& tree, const KeyType& key) : Tree(tree), Key(key) {}
 
        AccessClass();
 
        map& Tree;
        const KeyType& Key;
    }; // AccessClass
 
 
    // Constructor.
    map() : Root(0), Size(0) {}
 
    // Destructor
    ~map()
    {
        clear();
    }
 
    //------------------------------
    // Public Commands
    //------------------------------


    bool insert(const KeyType& keyNew, const ValueType& v)
    {
        // First insert node the "usual" way (no fancy balance logic yet)
        Node* newNode = new Node(keyNew,v);
        if (!insert(newNode))
        {
            delete newNode;
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return false;
        }
 
        // Then attend a balancing party
        while (!newNode->isRoot() && (newNode->getParent()->isRed()))
        {
            if (newNode->getParent()->isLeftChild())
            {
                // If newNode is a left child, get its right 'uncle'
                Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();
                if ( newNodesUncle!=0 && newNodesUncle->isRed())
                {
                    // case 1 - change the colors
                    newNode->getParent()->setBlack();
                    newNodesUncle->setBlack();
                    newNode->getParent()->getParent()->setRed();
                    // Move newNode up the tree
                    newNode = newNode->getParent()->getParent();
                }
                else
                {
                    // newNodesUncle is a black node
                    if ( newNode->isRightChild())
                    {
                        // and newNode is to the right
                        // case 2 - move newNode up and rotate
                        newNode = newNode->getParent();
                        rotateLeft(newNode);
                    }
                    // case 3
                    newNode->getParent()->setBlack();
                    newNode->getParent()->getParent()->setRed();
                    rotateRight(newNode->getParent()->getParent());
                }
            }
            else
            {
                // If newNode is a right child, get its left 'uncle'
                Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
                if ( newNodesUncle!=0 && newNodesUncle->isRed())
                {
                    // case 1 - change the colors
                    newNode->getParent()->setBlack();
                    newNodesUncle->setBlack();
                    newNode->getParent()->getParent()->setRed();
                    // Move newNode up the tree
                    newNode = newNode->getParent()->getParent();
                }
                else
                {
                    // newNodesUncle is a black node
                    if (newNode->isLeftChild())
                    {
                        // and newNode is to the left
                        // case 2 - move newNode up and rotate
                        newNode = newNode->getParent();
                        rotateRight(newNode);
                    }
                    // case 3
                    newNode->getParent()->setBlack();
                    newNode->getParent()->getParent()->setRed();
                    rotateLeft(newNode->getParent()->getParent());
                }
 
            }
        }
        // Color the root black
        Root->setBlack();
        return true;
    }


    void set(const KeyType& k, const ValueType& v)
    {
        Node* p = find(k);
        if (p)
            p->setValue(v);
        else
            insert(k,v);
    }


    Node* delink(const KeyType& k)
    {
        Node* p = find(k);
        if (p == 0)
            return 0;
 
        // Rotate p down to the left until it has no right child, will get there
        // sooner or later.
        while(p->getRightChild())
        {
            // "Pull up my right child and let it knock me down to the left"
            rotateLeft(p);
        }
        // p now has no right child but might have a left child
        Node* left = p->getLeftChild();
 
        // Let p's parent point to p's child instead of point to p
        if (p->isLeftChild())
            p->getParent()->setLeftChild(left);
 
        else if (p->isRightChild())
            p->getParent()->setRightChild(left);
 
        else
        {
            // p has no parent => p is the root.
            // Let the left child be the new root.
            setRoot(left);
        }
 
        // p is now gone from the tree in the sense that
        // no one is pointing at it, so return it.
 
        --Size;
        return p;
    }


    bool remove(const KeyType& k)
    {
        Node* p = find(k);
        return remove(p);
    }


    bool remove(Node* p)
    {
        if (p == 0)
        {
            _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
            return false;
        }
 
        // Rotate p down to the left until it has no right child, will get there
        // sooner or later.
        while(p->getRightChild())
        {
            // "Pull up my right child and let it knock me down to the left"
            rotateLeft(p);
        }
        // p now has no right child but might have a left child
        Node* left = p->getLeftChild();
 
        // Let p's parent point to p's child instead of point to p
        if (p->isLeftChild())
            p->getParent()->setLeftChild(left);
 
        else if (p->isRightChild())
            p->getParent()->setRightChild(left);
 
        else
        {
            // p has no parent => p is the root.
            // Let the left child be the new root.
            setRoot(left);
        }
 
        // p is now gone from the tree in the sense that
        // no one is pointing at it. Let's get rid of it.
        delete p;
 
        --Size;
        return true;
    }

    void clear()
    {
        ParentLastIterator i(getParentLastIterator());
 
        while(!i.atEnd())
        {
            Node* p = i.getNode();
            i++; // Increment it before it is deleted
                // else iterator will get quite confused.
            delete p;
        }
        Root = 0;
        Size= 0;
    }

    bool empty() const
    {
        _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
        return Root == 0;
    }

    _IRR_DEPRECATED_ bool isEmpty() const
    {
        return empty();
    }

    Node* find(const KeyType& keyToFind) const
    {
        Node* pNode = Root;
 
        while(pNode!=0)
        {
            const KeyType& key=pNode->getKey();
 
            if (keyToFind == key)
                return pNode;
            else if (keyToFind < key)
                pNode = pNode->getLeftChild();
            else //keyToFind > key
                pNode = pNode->getRightChild();
        }
 
        return 0;
    }

    Node* getRoot() const
    {
        return Root;
    }

    u32 size() const
    {
        return Size;
    }


    void swap(map<KeyType, ValueType>& other)
    {
        core::swap(Root, other.Root);
        core::swap(Size, other.Size);
    }
 
    //------------------------------
    // Public Iterators
    //------------------------------

    Iterator getIterator() const
    {
        Iterator it(getRoot());
        return it;
    }

    ConstIterator getConstIterator() const
    {
        Iterator it(getRoot());
        return it;
    }

    ParentFirstIterator getParentFirstIterator() const
    {
        ParentFirstIterator it(getRoot());
        return it;
    }

    ParentLastIterator getParentLastIterator() const
    {
        ParentLastIterator it(getRoot());
        return it;
    }
 
    //------------------------------
    // Public Operators
    //------------------------------


    AccessClass operator[](const KeyType& k)
    {
        return AccessClass(*this, k);
    }
    private:
 
    //------------------------------
    // Disabled methods
    //------------------------------
    // Copy constructor and assignment operator deliberately
    // defined but not implemented. The tree should never be
    // copied, pass along references to it instead.
    explicit map(const map& src);
    map& operator = (const map& src);


    void setRoot(Node* newRoot)
    {
        Root = newRoot;
        if (Root != 0)
        {
            Root->setParent(0);
            Root->setBlack();
        }
    }


    bool insert(Node* newNode)
    {
        bool result=true; // Assume success
 
        if (Root==0)
        {
            setRoot(newNode);
            Size = 1;
        }
        else
        {
            Node* pNode = Root;
            const KeyType& keyNew = newNode->getKey();
            while (pNode)
            {
                const KeyType& key=pNode->getKey();
 
                if (keyNew == key)
                {
                    result = false;
                    pNode = 0;
                }
                else if (keyNew < key)
                {
                    if (pNode->getLeftChild() == 0)
                    {
                        pNode->setLeftChild(newNode);
                        pNode = 0;
                    }
                    else
                        pNode = pNode->getLeftChild();
                }
                else // keyNew > key
                {
                    if (pNode->getRightChild()==0)
                    {
                        pNode->setRightChild(newNode);
                        pNode = 0;
                    }
                    else
                    {
                        pNode = pNode->getRightChild();
                    }
                }
            }
 
            if (result)
                ++Size;
        }
 
        _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
        return result;
    }

    void rotateLeft(Node* p)
    {
        Node* right = p->getRightChild();
 
        p->setRightChild(right->getLeftChild());
 
        if (p->isLeftChild())
            p->getParent()->setLeftChild(right);
        else if (p->isRightChild())
            p->getParent()->setRightChild(right);
        else
            setRoot(right);
 
        right->setLeftChild(p);
    }

    void rotateRight(Node* p)
    {
        Node* left = p->getLeftChild();
 
        p->setLeftChild(left->getRightChild());
 
        if (p->isLeftChild())
            p->getParent()->setLeftChild(left);
        else if (p->isRightChild())
            p->getParent()->setRightChild(left);
        else
            setRoot(left);
 
        left->setRightChild(p);
    }
 
    //------------------------------
    // Private Members
    //------------------------------
    Node* Root; // The top node. 0 if empty.
    u32 Size; // Number of nodes in the tree
};
 
} // end namespace core
} // end namespace irr
 
#endif // __IRR_MAP_H_INCLUDED__