/***************************************************************************
*                                                                          *
*  Copyright (C) Golaem S.A.  All Rights Reserved.                         *
*                                                                          *
***************************************************************************/

#pragma once

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable : 4949)
#pragma managed(push, off)
#endif

#include "glmCoreDefinitions.h"
#include "glmAssert.h"
#include "glmTypes.h"
#include "glmMemory.h"
#include "glmArray.h"
#include "glmPODArray.h"
#include "glmMemoryStats.h"

#include "glmContainersUtils.h"

#if GLM_IS_COMPILER_MSVC

#ifdef min
// save min definition and remove it
#define minWasDefined
#pragma push_macro("min")
#undef min
#endif

#ifdef max
// save max definition and remove it
#define maxWasDefined
#pragma push_macro("max")
#undef max
#endif

#endif

namespace glm
{
    template <typename _kTy, typename _Ty>
    class GlmMapIter;

    template <typename _kTy, typename _Ty>
    class GlmMapConstIter;

    // adapted from http://epaperpress.com/sortsearch/rbt.html
    // A map based on implementation of a red black tree
    // Note : this class does not implement complete std::map interface.
    template <typename _kTy, typename _Ty>
    class GlmMap
    {

        friend class GlmMapIter<_kTy, _Ty>;
        friend class GlmMapConstIter<_kTy, _Ty>;

    public:
        static const bool RED = true;
        static const bool BLACK = false;

        typedef _kTy key_type;
        typedef _Ty mapped_type;
        //typedef Entry value_type;
        //typedef _Comp key_compare;
        //typedef xxx value_compare
        //typedef xxx allocator_type;					// depends on allocator
        //typedef xxx allocator_type;					// depends on allocator
        typedef mapped_type& reference;
        typedef const mapped_type& const_reference;
        typedef mapped_type* pointer;
        typedef const mapped_type* const_pointer;
        typedef GlmMapIter<_kTy, _Ty> iterator;
        typedef GlmMapConstIter<_kTy, _Ty> const_iterator;
        //typedef xxx reverse_iterator;			// not used, would require another specific iterator class, lets keep it simple
        //typedef xxx const_reverse_iterator;	// not used, would require another specific iterator class, lets keep it simple
        //typedef xxx difference_type;
        typedef size_t size_type;

        typedef glm::GlmMap<_kTy, _Ty> ThisGlmMap;

        GLM_CLASS_STAT_ID( getDefaultArrayMemoryStatId())

    public:
        // ----------------------------------------------------------------------------------
        class GlmMapNode
        {

        public:
            GLM_CLASS_STAT_ID( ThisGlmMap::getDefaultArrayMemoryStatId())

            // place value before key as it is often bigger (for data size alignment)
            mapped_type _value;  // its associated data
            key_type _key;       // key
            GlmMapNode* _parent; // for iteration, maybe not optimal
            GlmMapNode* _left;   // left...
            GlmMapNode* _right;  // ...and right subtrees
            bool _color;         // color of parent link

            GlmMapNode(const key_type& key, const mapped_type& value, GlmMapNode* nil, GlmMapNode* parent = NULL)
                : _parent(parent)
                , _left(nil)
                , _right(nil)
            {
                _key = key;
                _value = value;
                _color = RED;
            }
        };

        typedef GlmMapNode* (glm::GlmMap<_kTy, _Ty>::*NewMapNodePtrType)(const key_type& key, const mapped_type& value, GlmMapNode* nil, GlmMapNode* parent);
        typedef void (glm::GlmMap<_kTy, _Ty>::*DeleteMapNodePtrType)(GlmMapNode* nodeToDelete);

        // provides a pool of Map nodes to avoid reallocating each frame, recycling deleted nodes. Allocate per static arrays to limit allocation calls
        class MapNodePool
        {
            GLM_CLASS_STAT_ID( ThisGlmMap::getDefaultArrayMemoryStatId())

        public:
            typedef typename GlmMap<_kTy, _Ty>::GlmMapNode node_type;

            // ---------------------------------------------------------------------
            MapNodePool(size_t allocationSize = 64, const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId())
                : _arrayOfStaticArraysOfMapNodes(memAllocStatId)
                , _chainedFreeNodes(NULL)
                , _allocationSize(allocationSize)
				, _memAllocStatId(memAllocStatId)
            {
            }

            // ---------------------------------------------------------------------
            ~MapNodePool()
            {
                clear();
            }

            // ---------------------------------------------------------------------
            node_type* obtain(const key_type& key, const mapped_type& value, GlmMapNode* nil, GlmMapNode* parent = NULL)
            {
                if (_chainedFreeNodes == NULL)
                {
                    allocateNewArray();
                }
                GlmMapNode* toReturn = _chainedFreeNodes;
                _chainedFreeNodes = _chainedFreeNodes->_right;

                // call placement new (constructor) to reset data of this node
                new (toReturn) GlmMapNode(key, value, nil, parent);

                return toReturn;
            }

            // ---------------------------------------------------------------------
            void recycle(node_type* nodeToRecycle)
            {
                nodeToRecycle->~GlmMapNode();
                nodeToRecycle->_right = _chainedFreeNodes;
                _chainedFreeNodes = nodeToRecycle;
            }

            // ---------------------------------------------------------------------
            void clear()
            {
                // delete array
                for (size_t i = 0; i < _arrayOfStaticArraysOfMapNodes.size(); i++)
                {
                    GLM_FREE( _arrayOfStaticArraysOfMapNodes[i],  _memAllocStatId);
                }
                _arrayOfStaticArraysOfMapNodes.clear();
                _chainedFreeNodes = NULL;
            }

            // ---------------------------------------------------------------------
            void setAllocationSize(size_t allocationSize)
            {
                _allocationSize = allocationSize;
            }

            MemAllocStatId getMemAllocStatId() const
            {
                return _memAllocStatId;
            }

        private:
            // ---------------------------------------------------------------------
            void allocateNewArray()
            {
				void* newValue = GLM_ALLOC(_allocationSize * sizeof(GlmMapNode), newValue, _memAllocStatId);
                _arrayOfStaticArraysOfMapNodes.push_back(static_cast<GlmMapNode*>(newValue));

                // chain in free array
                node_type* mapNodeArray = _arrayOfStaticArraysOfMapNodes.back();
                for (size_t i = 0, iEnd = (_allocationSize - 1); i < iEnd; ++i)
                {
                    mapNodeArray[i]._right = &(mapNodeArray[i + 1]);
                }
                mapNodeArray[_allocationSize - 1]._right = NULL;
                _chainedFreeNodes = &(mapNodeArray[0]);
            }

            glm::Array<node_type*> _arrayOfStaticArraysOfMapNodes;
            node_type* _chainedFreeNodes;
            size_t _allocationSize;

            MemAllocStatId _memAllocStatId;
        };

    protected:
        GlmMapNode* _root;
        size_t _size;
        GlmMapNode* _nil;
        GlmMapNode _nilInstance; // "sentinel" node to avoid testing a lot of stuff, replaces NULL
        MemAllocStatId _memAllocStatId;

    public:
        // ----------------------------------------------------------------------------------
        GlmMap(const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId())
            : _size(0)
            , _nilInstance(key_type(), mapped_type(), NULL, NULL)
			, _memAllocStatId(memAllocStatId)
            , _recycler(NULL)
        {
            _nil = &_nilInstance;

            _root = _nil;
            _nilInstance._left = _nil;
            _nilInstance._right = _nil;
            _nilInstance._parent = NULL;
            _nilInstance._color = BLACK;
            // uninitialized
            //_nilInstance->_key;
            //_nilInstance->_val;

            _deleteNodeFuncPtr = &ThisGlmMap::deleteNodeInternal;
            _newNodeFuncPtr = &ThisGlmMap::newNodeInternal;
        }

        // ----------------------------------------------------------------------------------
        GlmMap(MapNodePool* sharedRecycler, const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId())
            : _size(0)
            , _nilInstance(key_type(), mapped_type(), NULL, NULL)
			, _memAllocStatId(memAllocStatId)
            , _recycler(sharedRecycler)
        {
            // insure that the recycler is compatible with this container
            GLM_DEBUG_ASSERT(_recycler != NULL);

            _nil = &_nilInstance;

            _root = _nil;
            _nilInstance._left = _nil;
            _nilInstance._right = _nil;
            _nilInstance._parent = NULL;
            _nilInstance._color = BLACK;
            // uninitialized
            //_nilInstance->_value;

            _deleteNodeFuncPtr = &ThisGlmMap::deleteNodeWithRecycler;
            _newNodeFuncPtr = &ThisGlmMap::newNodeWithRecycler;
        }

        // ----------------------------------------------------------------------------------
        void deleteNodeInternal(GlmMapNode* nodeToDelete)
        {
            GLM_DELETE(nodeToDelete,  _memAllocStatId);
        }

        // ----------------------------------------------------------------------------------
        GlmMapNode* newNodeInternal(const key_type& key, const mapped_type& value, GlmMapNode* nil, GlmMapNode* parent /* = NULL*/)
        {
			GlmMapNode* newMapNode = GLM_NEW( GlmMapNode, newMapNode, _memAllocStatId,  key,  value,  nil,  parent);
			return newMapNode;
        }

        // ----------------------------------------------------------------------------------
        void deleteNodeWithRecycler(GlmMapNode* nodeToDelete)
        {
            _recycler->recycle(nodeToDelete);
        }

        // ----------------------------------------------------------------------------------
        GlmMapNode* newNodeWithRecycler(const key_type& key, const mapped_type& value, GlmMapNode* nil, GlmMapNode* parent = NULL)
        {
            return _recycler->obtain(key, value, nil, parent);
        }

        // ----------------------------------------------------------------------------------
        GlmMap(const GlmMap<key_type, mapped_type>& other)
            : _size(0)
            , _nilInstance(key_type(), mapped_type(), NULL, NULL)
			, _memAllocStatId(other._memAllocStatId)
            , _recycler(other._recycler)
        {
            _deleteNodeFuncPtr = other._deleteNodeFuncPtr;
            _newNodeFuncPtr = other._newNodeFuncPtr;

            _nil = &_nilInstance;

            _root = _nil;
            _nilInstance._left = _nil;
            _nilInstance._right = _nil;
            _nilInstance._parent = NULL;
            _nilInstance._color = BLACK;

            *this = other;
        }

        // ----------------------------------------------------------------------------------
        ~GlmMap()
        {
            // one shot clean
            if (_recycler != NULL)
            {
                _root = _nil;
                _size = 0;
                _recycler->clear();
            }
            else // recursive clean
                clear();
        }

        // ----------------------------------------------------------------------------------
        bool empty() const
        {
            return _root == _nil;
        }

        // ----------------------------------------------------------------------------------
        size_t size() const
        {
            return _size;
        }

        // ----------------------------------------------------------------------------------
        iterator begin()
        {
            return iterator(min(), this);
        }

        // ----------------------------------------------------------------------------------
        const_iterator begin() const
        {
            return const_iterator(min(), this);
        }

        // ----------------------------------------------------------------------------------
        iterator end()
        {
            return iterator(_nil, this);
        }

        // ----------------------------------------------------------------------------------
        const_iterator end() const
        {
            return const_iterator(_nil, this);
        }

        // ----------------------------------------------------------------------------------
        mapped_type& operator[](const key_type& key)
        {
            GlmMapNode* foundNode = internalFind(key);
            if (foundNode == _nil)
            {
                foundNode = internalInsert(key, mapped_type());
            }
            return foundNode->_value;
        }

        // ----------------------------------------------------------------------------------
        // initial insert returns pair of inserted stuff, this version does not (don't want to depend on std::pair or alike)
        iterator insert(const key_type& key, const mapped_type& value)
        {
            return iterator(internalInsert(key, value), this);
        }

        // ----------------------------------------------------------------------------------
        void insert(const_iterator otherFirst, const_iterator otherLast)
        {
            const_iterator otherIter = otherFirst;
            while (otherIter != otherLast)
            {
                internalInsert(otherIter.getKey(), otherIter.getValue());
                ++otherIter;
            }
        }

        // ----------------------------------------------------------------------------------
        void erase(iterator position)
        {
            internalErase(position._node);
        }

        // ----------------------------------------------------------------------------------
        size_t erase(const key_type& key)
        {
            GlmMapNode* foundNode = internalFind(key);
            if (foundNode != _nil)
            {
                internalErase(foundNode);
            }
            return _size;
        }

        // ----------------------------------------------------------------------------------
        void clear()
        {
            if (_root != _nil)
            {
                internalClear(_root);
                _root = _nil;
                _size = 0;
            }
        }

        // ----------------------------------------------------------------------------------
        iterator find(const key_type& key)
        {
            return iterator(internalFind(key), this);
        }

        // ----------------------------------------------------------------------------------
        const_iterator find(const key_type& key) const
        {
            return const_iterator(internalFind(key), this);
        }

        // ----------------------------------------------------------------------------------
        //size_t count(const key_type& key) const
        //{
        //	GLM_EXIT("not implemented");
        //}

        // ----------------------------------------------------------------------------------
        GlmMap<key_type, mapped_type>& operator=(const GlmMap<key_type, mapped_type>& other)
        {
            // make space for new map
            clear();

            // descend the other tree :
            if (other._root != other._nil)
            {
                _root = (*this.*_newNodeFuncPtr)(other._root->_key, other._root->_value, _nil, NULL);
                _root->_color = other._root->_color;
                copyChildren(_root, other._root, other._nil);
            }

            _size = other._size;

            return *this;
        }

        // ----------------------------------------------------------------------------------
        bool operator==(const GlmMap<key_type, mapped_type>& other) const
        {
            GlmMapConstIter<key_type, mapped_type> thisIter = begin();
            GlmMapConstIter<key_type, mapped_type> otherIter = other.begin();

            while (thisIter != end() && otherIter != other.end() && thisIter.getKey() == otherIter.getKey() && thisIter.getValue() == otherIter.getValue())
            {
                ++thisIter;
                ++otherIter;
            }

            // if both ends are reached, we have equal maps
            return (thisIter == end() && otherIter == other.end());
        }

        // ----------------------------------------------------------------------------------
        bool operator!=(const GlmMap<key_type, mapped_type>& other) const
        {
            return !operator==(other);
        }

    protected:
        // ----------------------------------------------------------------------------------
        void rotateLeft(GlmMapNode* node)
        {
            // rotate node node to _left
            GlmMapNode* rightChild = node->_right;

            // establish node->_right link
            node->_right = rightChild->_left;
            if (rightChild->_left != _nil)
                rightChild->_left->_parent = node;

            // establish rightChild->_parent link
            if (rightChild != _nil)
                rightChild->_parent = node->_parent;
            if (node->_parent)
            {
                if (node == node->_parent->_left)
                    node->_parent->_left = rightChild;
                else
                    node->_parent->_right = rightChild;
            }
            else
            {
                _root = rightChild;
            }

            // link node and rightChild
            rightChild->_left = node;
            if (node != _nil)
                node->_parent = rightChild;
        }

        // ----------------------------------------------------------------------------------
        void rotateRight(GlmMapNode* node)
        {
            // rotate node node to _right

            GlmMapNode* leftChild = node->_left;

            // establish node->_left link
            node->_left = leftChild->_right;
            if (leftChild->_right != _nil)
                leftChild->_right->_parent = node;

            // establish leftChild->_parent link
            if (leftChild != _nil)
                leftChild->_parent = node->_parent;
            if (node->_parent)
            {
                if (node == node->_parent->_right)
                    node->_parent->_right = leftChild;
                else
                    node->_parent->_left = leftChild;
            }
            else
            {
                _root = leftChild;
            }

            // link node and leftChild
            leftChild->_right = node;
            if (node != _nil)
                node->_parent = leftChild;
        }

        // ----------------------------------------------------------------------------------
        void insertFixup(GlmMapNode* node)
        {
            // maintain red-black tree balance after inserting node node

            // check red-black properties
            while (node != _root && node->_parent->_color == RED)
            {
                // we have a violation
                if (node->_parent == node->_parent->_parent->_left)
                {
                    GlmMapNode* y = node->_parent->_parent->_right;
                    if (y->_color == RED)
                    {

                        // uncle is RED
                        node->_parent->_color = BLACK;
                        y->_color = BLACK;
                        node->_parent->_parent->_color = RED;
                        node = node->_parent->_parent;
                    }
                    else
                    {

                        // uncle is BLACK
                        if (node == node->_parent->_right)
                        {
                            // make node a _left child
                            node = node->_parent;
                            rotateLeft(node);
                        }

                        // recolor and rotate
                        node->_parent->_color = BLACK;
                        node->_parent->_parent->_color = RED;
                        rotateRight(node->_parent->_parent);
                    }
                }
                else
                {

                    // mirror image of above code
                    GlmMapNode* y = node->_parent->_parent->_left;
                    if (y->_color == RED)
                    {

                        // uncle is RED
                        node->_parent->_color = BLACK;
                        y->_color = BLACK;
                        node->_parent->_parent->_color = RED;
                        node = node->_parent->_parent;
                    }
                    else
                    {

                        // uncle is BLACK
                        if (node == node->_parent->_left)
                        {
                            node = node->_parent;
                            rotateRight(node);
                        }
                        node->_parent->_color = BLACK;
                        node->_parent->_parent->_color = RED;
                        rotateLeft(node->_parent->_parent);
                    }
                }
            }
            _root->_color = BLACK;
        }

        // ----------------------------------------------------------------------------------
        void deleteFixUp(GlmMapNode* node)
        {
            // maintain red-black tree balance after deleting node node
            while (node != _root && node->_color == BLACK)
            {
                if (node == node->_parent->_left)
                {
                    GlmMapNode* w = node->_parent->_right;
                    if (w->_color == RED)
                    {
                        w->_color = BLACK;
                        node->_parent->_color = RED;
                        rotateLeft(node->_parent);
                        w = node->_parent->_right;
                    }
                    if (w->_left->_color == BLACK && w->_right->_color == BLACK)
                    {
                        w->_color = RED;
                        node = node->_parent;
                    }
                    else
                    {
                        if (w->_right->_color == BLACK)
                        {
                            w->_left->_color = BLACK;
                            w->_color = RED;
                            rotateRight(w);
                            w = node->_parent->_right;
                        }
                        w->_color = node->_parent->_color;
                        node->_parent->_color = BLACK;
                        w->_right->_color = BLACK;
                        rotateLeft(node->_parent);
                        node = _root;
                    }
                }
                else
                {
                    GlmMapNode* w = node->_parent->_left;
                    if (w->_color == RED)
                    {
                        w->_color = BLACK;
                        node->_parent->_color = RED;
                        rotateRight(node->_parent);
                        w = node->_parent->_left;
                    }
                    if (w->_right->_color == BLACK && w->_left->_color == BLACK)
                    {
                        w->_color = RED;
                        node = node->_parent;
                    }
                    else
                    {
                        if (w->_left->_color == BLACK)
                        {
                            w->_right->_color = BLACK;
                            w->_color = RED;
                            rotateLeft(w);
                            w = node->_parent->_left;
                        }
                        w->_color = node->_parent->_color;
                        node->_parent->_color = BLACK;
                        w->_left->_color = BLACK;
                        rotateRight(node->_parent);
                        node = _root;
                    }
                }
            }
            node->_color = BLACK;
        }

        // ----------------------------------------------------------------------------------
        static inline MemAllocStatId getDefaultArrayMemoryStatId()
        {
            return (MemAllocStatId)glm::MemoryStatIds::GolaemShared;
        }

    private:
        // ----------------------------------------------------------------------------------
        GlmMapNode* min() const
        {
            GlmMapNode* currentNode = _root;

            for (; currentNode->_left != _nil; currentNode = currentNode->_left)
                ;

            return currentNode;
        }

        // ----------------------------------------------------------------------------------
        GlmMapNode* max() const
        {
            GlmMapNode* currentNode = _root;

            for (; currentNode->_right != _nil; currentNode = currentNode->_right)
                ;

            return currentNode;
        }

        // ----------------------------------------------------------------------------------
        void copyChildren(GlmMapNode* thisNode, const GlmMapNode* fromNode, const GlmMapNode* fromNil)
        {
            if (fromNode->_left != fromNil)
            {
                thisNode->_left = (*this.*_newNodeFuncPtr)(fromNode->_left->_key, fromNode->_left->_value, _nil, thisNode);
                thisNode->_left->_color = fromNode->_left->_color;
                copyChildren(thisNode->_left, fromNode->_left, fromNil);
            }
            if (fromNode->_right != fromNil)
            {
                thisNode->_right = (*this.*_newNodeFuncPtr)(fromNode->_right->_key, fromNode->_right->_value, _nil, thisNode);
                thisNode->_right->_color = fromNode->_right->_color;
                copyChildren(thisNode->_right, fromNode->_right, fromNil);
            }
        }

        // ----------------------------------------------------------------------------------
        void internalClear(GlmMapNode* node)
        {
            if (node != _nil)
            {
                internalClear(node->_right);
                internalClear(node->_left);
                (*this.*_deleteNodeFuncPtr)(node);
                // size will be set to 0
            }
        }

        // ----------------------------------------------------------------------------------
        GlmMapNode* internalFind(const key_type& key) const
        {
            GlmMapNode* current = _root;
            while (current != _nil)
            {
                // operator== is not defined by default for structs, operator< is
                if (key < current->_key)
                    current = current->_left;
                else if (current->_key < key)
                    current = current->_right;
                else
                    return current;
            }
            return _nil;
        }

        // ----------------------------------------------------------------------------------
        void internalErase(GlmMapNode* node)
        {
            GlmMapNode *nodeBelowMovedOne, *nodeToMoveAtErasePlace;
            GlmMapNode* nodeToErase = node;

            if (nodeToErase->_left == _nil || nodeToErase->_right == _nil)
            {
                // y has a SENTINEL node as a child, node will be replaced by itsef (not replaced)
                nodeToMoveAtErasePlace = nodeToErase;
            }
            else
            {
                // find tree successor with a SENTINEL node as a child
                nodeToMoveAtErasePlace = nodeToErase->_right;
                while (nodeToMoveAtErasePlace->_left != _nil)
                    nodeToMoveAtErasePlace = nodeToMoveAtErasePlace->_left;
            }

            // x is y's only child
            if (nodeToMoveAtErasePlace->_left != _nil)
                nodeBelowMovedOne = nodeToMoveAtErasePlace->_left;
            else
                nodeBelowMovedOne = nodeToMoveAtErasePlace->_right;

            // remove nodeToMoveAtErasePlace from the _parent chain
            nodeBelowMovedOne->_parent = nodeToMoveAtErasePlace->_parent;
            if (nodeToMoveAtErasePlace->_parent)
                if (nodeToMoveAtErasePlace == nodeToMoveAtErasePlace->_parent->_left)
                    nodeToMoveAtErasePlace->_parent->_left = nodeBelowMovedOne;
                else
                    nodeToMoveAtErasePlace->_parent->_right = nodeBelowMovedOne;
            else
                _root = nodeBelowMovedOne;

            // nodeToMoveAtErasePlace is disconnected from the parent chain
            // need to set it in nodeToErase place :
            bool nodeToMovePreviousColor = nodeToMoveAtErasePlace->_color;
            if (nodeToMoveAtErasePlace != nodeToErase)
            {
                nodeToMoveAtErasePlace->_parent = nodeToErase->_parent;
                nodeToMoveAtErasePlace->_left = nodeToErase->_left;
                nodeToMoveAtErasePlace->_right = nodeToErase->_right;
                nodeToMoveAtErasePlace->_color = nodeToErase->_color;

                // and fix parent chain :
                if (nodeToMoveAtErasePlace->_parent != NULL)
                {
                    if (nodeToErase == nodeToMoveAtErasePlace->_parent->_left)
                        nodeToMoveAtErasePlace->_parent->_left = nodeToMoveAtErasePlace;
                    else
                        nodeToMoveAtErasePlace->_parent->_right = nodeToMoveAtErasePlace;
                }
                else
                    _root = nodeToMoveAtErasePlace;

                // children chain
                nodeToMoveAtErasePlace->_left->_parent = nodeToMoveAtErasePlace;
                nodeToMoveAtErasePlace->_right->_parent = nodeToMoveAtErasePlace;
            }

            if (nodeToMovePreviousColor == BLACK)
                deleteFixUp(nodeBelowMovedOne);

            (*this.*_deleteNodeFuncPtr)(nodeToErase);

            _size--;
        }

        // ----------------------------------------------------------------------------------
        // initial insert returns pair of inserted stuff, this version does not (don't want to depend on std::pair or alike)
        GlmMapNode* internalInsert(const key_type& key, const mapped_type& val)
        {
            // allocate node for data and insert in tree

            // find future parent
            GlmMapNode* current = _root;
            GlmMapNode* parent = NULL;
            while (current != _nil)
            {
                if (key < current->_key)
                {
                    parent = current;
                    current = current->_left;
                }
                else if (current->_key < key)
                {
                    parent = current;
                    current = current->_right;
                }
                else
                    return current;
                //if (key == current->_key)
                //	return current;
                //parent = current;
                //current = (key < current->_key) ? current->_left : current->_right;
            }

            // actually growing :
            _size++;

            GlmMapNode* newNode = (*this.*_newNodeFuncPtr)(key, val, _nil, parent);

            // insert node in tree
            if (parent)
            {
                if (key < parent->_key)
                    parent->_left = newNode;
                else
                    parent->_right = newNode;
            }
            else
            {
                _root = newNode;
            }

            insertFixup(newNode);

            return newNode;
        }

    private:
        DeleteMapNodePtrType _deleteNodeFuncPtr;
        NewMapNodePtrType _newNodeFuncPtr;

        MapNodePool* _recycler;
    };

    template <typename _kTy, typename _Ty>
    class GlmMapIter
    {

        friend class GlmMap<_kTy, _Ty>;
        friend class GlmMapConstIter<_kTy, _Ty>; // for constIter constructor based on iteer

    public:
        typedef _kTy key_type;
        typedef _Ty mapped_type;
        typedef typename GlmMap<_kTy, _Ty>::GlmMapNode node_type;
        typedef GlmMap<_kTy, _Ty> tree_type;

        // ----------------------------------------------------------------------------------
        GlmMapIter(node_type* aNode = NULL, const tree_type* aTree = NULL)
            : _node(aNode)
            , _tree(aTree)
        {
        }

        // ----------------------------------------------------------------------------------
        GlmMapIter(const GlmMapIter& other)
            : _node(other._node)
            , _tree(other._tree)
        {
        }

        // ----------------------------------------------------------------------------------
        GlmMapIter& operator=(const GlmMapIter& other)
        {
            _node = other._node;
            _tree = other._tree;
            return *this;
        }

        // ----------------------------------------------------------------------------------
        const _kTy& getKey()
        {
            GLM_DEBUG_ASSERT(_node != NULL && _tree != NULL && _node != _tree->_nil);
            return _node->_key;
        }

        // ----------------------------------------------------------------------------------
        _Ty& getValue() // can modify value on non const iterator
        {
            GLM_DEBUG_ASSERT(_node != NULL && _tree != NULL && _node != _tree->_nil);
            return _node->_value;
        }

        // ----------------------------------------------------------------------------------
        GlmMapIter& operator++()
        {
            GLM_DEBUG_ASSERT(_node != NULL && _tree != NULL);
            node_type* nil = _tree->_nil;

            if (_node->_right != nil)
            {
                // go right 1, then left to the end
                for (_node = _node->_right; _node->_left != nil; _node = _node->_left)
                    ;
            }
            else
            {
                // while you're the right child, chain up parent link
                node_type* p = _node->_parent;
                while (p && _node == p->_right)
                {
                    _node = p;
                    p = p->_parent;
                }

                // return the "inorder" next node
                _node = p;
                if (_node == NULL)
                    _node = nil;
            }
            return *this;
        }

        // ----------------------------------------------------------------------------------
        GlmMapIter operator++(int)
        {
            GlmMapIter tmp = *this;
            ++*this;
            return (tmp);
        }

        // ----------------------------------------------------------------------------------
        GlmMapIter& operator--()
        {
            GLM_DEBUG_ASSERT(_node != NULL && _tree != NULL);
            node_type* nil = _tree->_nil;
            if (_node == nil)
            {
                _node = _tree->max();
            }
            else
            {
                if (_node->_left != nil)
                {
                    // go right 1, then left to the end
                    for (_node = _node->_left; _node->_right != nil; _node = _node->_right)
                        ;
                }
                else
                {
                    // while you're the right child, chain up parent link
                    node_type* p = _node->_parent;
                    while (p && _node == p->_left)
                    {
                        _node = p;
                        p = p->_parent;
                    }

                    // return the "inorder" previous node
                    _node = p;
                    if (_node == NULL)
                        _node = nil;
                }
            }
            return *this;
        }

        // ----------------------------------------------------------------------------------
        GlmMapIter operator--(int)
        {
            GlmMapIter tmp = *this;
            --*this;
            return (tmp);
        }

        // ----------------------------------------------------------------------------------
        bool operator==(const GlmMapIter& other) const
        {
            return _node == other._node;
        }
        bool operator!=(const GlmMapIter& other) const
        {
            return _node != other._node;
        }

    private:
        node_type* _node;
        const tree_type* _tree; // in case end--, need to be able to access last
    };

    template <typename _kTy, typename _Ty>
    class GlmMapConstIter
    {

        friend class GlmMap<_kTy, _Ty>;

    public:
        typedef _kTy key_type;
        typedef _Ty mapped_type;
        typedef typename GlmMap<_kTy, _Ty>::GlmMapNode node_type;
        typedef GlmMap<_kTy, _Ty> tree_type;

        // ----------------------------------------------------------------------------------
        GlmMapConstIter(node_type* aNode = NULL, const tree_type* aTree = NULL)
            : _node(aNode)
            , _tree(aTree)
        {
        }

        // ----------------------------------------------------------------------------------
        GlmMapConstIter(const GlmMapConstIter& other)
            : _node(other._node)
            , _tree(other._tree)
        {
        }

        // ----------------------------------------------------------------------------------
        GlmMapConstIter(const GlmMapIter<_kTy, _Ty>& other)
            : _node(other._node)
            , _tree(other._tree)
        {
        }

        // ----------------------------------------------------------------------------------
        GlmMapConstIter& operator=(const GlmMapConstIter& other)
        {
            _node = other._node;
            _tree = other._tree;
            return *this;
        }

        // ----------------------------------------------------------------------------------
        GlmMapConstIter& operator=(const GlmMapIter<_kTy, _Ty>& other)
        {
            _node = other._node;
            _tree = other._tree;
            return *this;
        }

        // ----------------------------------------------------------------------------------
        const _kTy& getKey()
        {
            GLM_DEBUG_ASSERT(_node != NULL && _tree != NULL && _node != _tree->_nil);
            return _node->_key;
        }

        // ----------------------------------------------------------------------------------
        const _Ty& getValue()
        {
            GLM_DEBUG_ASSERT(_node != NULL && _tree != NULL && _node != _tree->_nil);
            return _node->_value;
        }

        // ----------------------------------------------------------------------------------
        GlmMapConstIter& operator++()
        {
            GLM_DEBUG_ASSERT(_node != NULL && _tree != NULL);
            node_type* nil = _tree->_nil;

            if (_node->_right != nil)
            {
                // go right 1, then left to the end
                for (_node = _node->_right; _node->_left != nil; _node = _node->_left)
                    ;
            }
            else
            {
                // while you're the right child, chain up parent link
                node_type* p = _node->_parent;
                while (p && _node == p->_right)
                {
                    _node = p;
                    p = p->_parent;
                }

                // return the "inorder" next node
                _node = p;
                if (_node == NULL)
                    _node = nil;
            }
            return *this;
        }

        // ----------------------------------------------------------------------------------
        GlmMapConstIter operator++(int)
        {
            GlmMapConstIter tmp = *this;
            ++*this;
            return (tmp);
        }

        // ----------------------------------------------------------------------------------
        GlmMapConstIter& operator--()
        {
            GLM_DEBUG_ASSERT(_node != NULL && _tree != NULL);
            node_type* nil = _tree->_nil;
            if (_node == nil)
            {
                _node = _tree->max();
            }
            else
            {
                if (_node->_left != nil)
                {
                    // go right 1, then left to the end
                    for (_node = _node->_left; _node->_right != nil; _node = _node->_right)
                        ;
                }
                else
                {
                    // while you're the right child, chain up parent link
                    node_type* p = _node->_parent;
                    while (p && _node == p->_left)
                    {
                        _node = p;
                        p = p->_parent;
                    }

                    // return the "inorder" previous node
                    _node = p;
                    if (_node == NULL)
                        _node = nil;
                }
            }
            return *this;
        }

        // ----------------------------------------------------------------------------------
        GlmMapConstIter operator--(int)
        {
            GlmMapConstIter tmp = *this;
            --*this;
            return (tmp);
        }

        // ----------------------------------------------------------------------------------
        bool operator==(const GlmMapConstIter& other) const
        {
            return _node == other._node;
        }
        bool operator!=(const GlmMapConstIter& other) const
        {
            return _node != other._node;
        }

    private:
        node_type* _node;
        const tree_type* _tree; // in case end--, need to be able to access last
    };
} // namespace glm

#if GLM_IS_COMPILER_MSVC

#ifdef minWasDefined
// restore min definition
#pragma pop_macro("min")
#endif

#ifdef maxWasDefined
// restore max definition
#pragma pop_macro("max")
#endif

#endif
