/***************************************************************************
*                                                                          *
*  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 "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 _Ty>
    class GlmSetIter;

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

        friend class GlmSetIter<_Ty>;

    public:
        GLM_CLASS_STAT_ID( getDefaultArrayMemoryStatId())

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

        typedef _Ty 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 value_type& reference;
        typedef const value_type& const_reference;
        typedef value_type* pointer;
        typedef const value_type* const_pointer;
        typedef GlmSetIter<_Ty> iterator;
        typedef GlmSetIter<_Ty> const_iterator; // for set, the const_iterator and iterator are both forbidding the modification of value, so this is basically the same.
        //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;

    public:
        // ----------------------------------------------------------------------------------
        class GlmSetNode
        {

        public:
            GLM_CLASS_STAT_ID( glm::GlmSet<_Ty>::getDefaultArrayMemoryStatId())

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

            GlmSetNode(const value_type& value, GlmSetNode* nil, GlmSetNode* parent = NULL)
                : _parent(parent)
                , _left(nil)
                , _right(nil)
            {
                _value = value;
                _color = RED;
            }
        };

        typedef GlmSetNode* (GlmSet<_Ty>::*NewSetNodePtrType)(const value_type& value, GlmSetNode* nil, GlmSetNode* parent);
        typedef void (GlmSet<_Ty>::*DeleteSetNodePtrType)(GlmSetNode* nodeToDelete);

        // provides a pool of set nodes to avoid reallocating each frame, recycling deleted nodes. Allocate per static arrays to limit allocation calls
        class SetNodePool
        {
            GLM_CLASS_STAT_ID( glm::GlmSet<_Ty>::getDefaultArrayMemoryStatId())

        public:
            typedef typename GlmSet<_Ty>::GlmSetNode node_type;

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

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

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

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

                return toReturn;
            }

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

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

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

            // ---------------------------------------------------------------------
            MemAllocStatId getMemAllocStatId() const
            {
                return _memAllocStatId;
            }

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

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

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

            MemAllocStatId _memAllocStatId;
        };

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

        MemAllocStatId _memAllocStatId;

    public:
        // ----------------------------------------------------------------------------------
        GlmSet(const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId())
            : _size(0)
            , _nilInstance(value_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->_value;

            _deleteNodeFuncPtr = &GlmSet<_Ty>::deleteNodeInternal;
            _newNodeFuncPtr = &GlmSet<_Ty>::newNodeInternal;
        }

        // ----------------------------------------------------------------------------------
        GlmSet(SetNodePool* sharedRecycler, const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId())
            : _size(0)
            , _nilInstance(value_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 = &glm::GlmSet<_Ty>::deleteNodeWithRecycler;
            _newNodeFuncPtr = &glm::GlmSet<_Ty>::newNodeWithRecycler;
        }

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

        // ----------------------------------------------------------------------------------
        GlmSetNode* newNodeInternal(const value_type& value, GlmSetNode* nil, GlmSetNode* parent /* = NULL*/)
        {
			GlmSetNode* newNode = GLM_NEW( GlmSetNode, newNode, _memAllocStatId,  value,  nil,  parent);
			return newNode;
        }

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

        // ----------------------------------------------------------------------------------
        GlmSetNode* newNodeWithRecycler(const value_type& value, GlmSetNode* nil, GlmSetNode* parent = NULL)
        {
            return _recycler->obtain(value, nil, parent);
        }

        // ----------------------------------------------------------------------------------
        GlmSet(const GlmSet<value_type>& other)
            : _size(0)
            , _nilInstance(value_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;
        }

        // ----------------------------------------------------------------------------------
        ~GlmSet()
        {
            // 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);
        }

        // ----------------------------------------------------------------------------------
        // initial insert returns pair of inserted stuff with boolean if it is inserted, this version does not
        iterator insert(const value_type& value)
        {
            return iterator(internalInsert(value), this);
        }

        // ----------------------------------------------------------------------------------
        template <class OtherIterator>
        void insert(OtherIterator otherFirst, OtherIterator otherLast)
        {
            OtherIterator otherIter = otherFirst;
            while (otherIter != otherLast)
            {
                internalInsert(*otherIter);
                ++otherIter;
            }
        }

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

        // ----------------------------------------------------------------------------------
        size_t erase(const value_type& value)
        {
            GlmSetNode* foundNode = internalFind(value);
            if (foundNode != _nil)
            {
                internalErase(foundNode);
            }
            return _size;
        }

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

        // ----------------------------------------------------------------------------------
        iterator find(const value_type& value)
        {
            return iterator(internalFind(value), this);
        }

        // ----------------------------------------------------------------------------------
        const_iterator find(const value_type& value) const
        {
            return const_iterator(internalFind(value), this);
        }

        // ----------------------------------------------------------------------------------
        size_t count(const value_type& value) const
        {
            GLM_EXIT("not implemented");
        }

        // ----------------------------------------------------------------------------------
        GlmSet<value_type>& operator=(const GlmSet<value_type>& other)
        {
            // make space for new map
            clear();

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

            _size = other._size;

            return *this;
        }

        // ----------------------------------------------------------------------------------
        bool operator==(const GlmSet<value_type>& other) const
        {
            GlmSetIter<value_type> thisIter = begin();
            GlmSetIter<value_type> otherIter = other.begin();

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

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

        // ----------------------------------------------------------------------------------
        bool operator!=(const GlmSet<value_type>& other) const
        {
            return !operator==(other);
        }

    protected:
        // ----------------------------------------------------------------------------------
        void rotateLeft(GlmSetNode* node)
        {
            // rotate node node to _left
            GlmSetNode* 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(GlmSetNode* node)
        {
            // rotate node node to _right

            GlmSetNode* 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(GlmSetNode* 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)
                {
                    GlmSetNode* 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
                    GlmSetNode* 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(GlmSetNode* node)
        {
            // maintain red-black tree balance after deleting node node
            while (node != _root && node->_color == BLACK)
            {
                if (node == node->_parent->_left)
                {
                    GlmSetNode* 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
                {
                    GlmSetNode* 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 glm::MemoryStatIds::GolaemShared;
        }

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

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

            return currentNode;
        }

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

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

            return currentNode;
        }

        // ----------------------------------------------------------------------------------
        void copyChildren(GlmSetNode* thisNode, const GlmSetNode* fromNode, const GlmSetNode* fromNil)
        {
            if (fromNode->_left != fromNil)
            {
                thisNode->_left = (*this.*_newNodeFuncPtr)(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->_value, _nil, thisNode);
                thisNode->_right->_color = fromNode->_right->_color;
                copyChildren(thisNode->_right, fromNode->_right, fromNil);
            }
        }

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

        // ----------------------------------------------------------------------------------
        GlmSetNode* internalFind(const value_type& value) const
        {
            GlmSetNode* current = _root;
            while (current != _nil)
            {
                if (value < current->_value)
                    current = current->_left;
                else if (current->_value < value)
                    current = current->_right;
                else
                    return current;
            }
            return _nil;
        }

        // ----------------------------------------------------------------------------------
        void internalErase(GlmSetNode* node)
        {
            GlmSetNode *x, *y;
            GlmSetNode* z = node;

            if (z->_left == _nil || z->_right == _nil)
            {
                // y has a SENTINEL node as a child
                y = z;
            }
            else
            {
                // find tree successor with a SENTINEL node as a child
                y = z->_right;
                while (y->_left != _nil)
                    y = y->_left;
            }

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

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

            if (y != z)
            {
                z->_value = y->_value;
            }

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

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

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

            if (yPreviousColor == BLACK)
                deleteFixUp(x);

            (*this.*_deleteNodeFuncPtr)(z);
            _size--;
        }

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

            // find future parent
            GlmSetNode* current = _root;
            GlmSetNode* parent = NULL;
            while (current != _nil)
            {
                if (value < current->_value)
                {
                    parent = current;
                    current = current->_left;
                }
                else if (current->_value < value)
                {
                    parent = current;
                    current = current->_right;
                }
                else
                    return current;
            }

            // actually growing :
            _size++;

            GlmSetNode* newNode = (*this.*_newNodeFuncPtr)(value, _nil, parent);

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

            insertFixup(newNode);

            return newNode;
        }

    private:
        DeleteSetNodePtrType _deleteNodeFuncPtr;
        NewSetNodePtrType _newNodeFuncPtr;

        SetNodePool* _recycler;
    };

    template <typename _Ty>
    class GlmSetIter
    {

        friend class GlmSet<_Ty>;

    public:
        typedef _Ty value_type;
        typedef typename GlmSet<_Ty>::GlmSetNode node_type;
        typedef GlmSet<_Ty> tree_type;

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

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

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

        // ----------------------------------------------------------------------------------
        const value_type& operator*() const
        {
            GLM_DEBUG_ASSERT(_node != NULL);
            return _node->_value;
        }

        // ----------------------------------------------------------------------------------
        const value_type& operator->() const
        {
            GLM_DEBUG_ASSERT(_node != NULL);
            return _node->_value;
        }

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

        // ----------------------------------------------------------------------------------
        GlmSetIter& 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;
        }

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

        // ----------------------------------------------------------------------------------
        GlmSetIter& 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;
        }

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

        // ----------------------------------------------------------------------------------
        bool operator==(const GlmSetIter& other) const
        {
            return _node == other._node;
        }
        bool operator!=(const GlmSetIter& 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
