/*
    Copyright (c) 1999-2002 Redshift Software, Inc.
    All Rights Reserved.
    
    In case it's not obvious this code is being made available
    for informational use only. It is meant to provoke
    discussion regarding Boost tree implementrations and
    interfaces. It can not be used within any other context,
    commercial nor non-commercial.
*/
#ifndef com_redshift_software_libraries_base_ranktree_h
#define com_redshift_software_libraries_base_ranktree_h

#include <memory>
#include <iterator>
#include <algorithm>
#include <stdexcept>

#include <com/redshift-software/libraries/base/Packages.h>


com_redshift_software_libraries_base_p {
    
template <typename ValueType, typename SizeType>
struct rank_tree_node
{
    rank_tree_node * mLeft;
    rank_tree_node * mRight;
    rank_tree_node * mParent;
    SizeType mCount;
    ValueType mValue;
};

template <typename Traits>
class rank_tree_iterator
    : public std::iterator<std::bidirectional_iterator_tag,
        typename Traits::value_type,
        typename Traits::difference_type,
        typename Traits::pointer,
        typename Traits::reference>
{
    public:
    
    // reflective type
    typedef rank_tree_iterator<Traits> iterator_type;
    
    // construction
    rank_tree_iterator() : mCurrent(0) { }
    rank_tree_iterator(const rank_tree_iterator & aOther) : mCurrent(aOther.mCurrent) { }
    rank_tree_iterator(typename Traits::node_pointer aNode) : mCurrent(aNode) { }
    
    // access
    typename Traits::reference operator*() const { return mCurrent->mValue; }
    typename Traits::pointer operator->() const { return &mCurrent->mValue; }
    
    // iteration
    rank_tree_iterator & operator++()
    {
        if (mCurrent->mRight != 0) mCurrent = mCurrent->mRight;
        else if (mCurrent->mParent != 0 && mCurrent->mParent->mLeft == mCurrent) mCurrent = mCurrent->mParent;
        else mCurrent = 0;
        while (mCurrent != 0 && mCurrent->mLeft != 0) mCurrent = mCurrent->mLeft;
        return *this;
    }
    rank_tree_iterator operator++(int)
    {
        iterator_type t(*this);
        ++(*this);
        return t;
    }
    rank_tree_iterator & operator--()
    {
        if (mCurrent->mLeft != 0) mCurrent = mCurrent->mLeft;
        else if (mCurrent->mParent != 0 && mCurrent->mParent->mRight == mCurrent) mCurrent = mCurrent->mParent;
        else mCurrent = 0;
        while (mCurrent != 0 && mCurrent->mRight != 0) mCurrent = mCurrent->mRight;
        return *this;
    }
    rank_tree_iterator operator--(int)
    {
        iterator_type t(*this);
        --(*this);
        return t;
    }
    
    // comparison
    bool operator==(const rank_tree_iterator & aOther) { return mCurrent == aOther.mCurrent; }
    bool operator!=(const rank_tree_iterator & aOther) { return mCurrent != aOther.mCurrent; }
    
    // misc.
    typename Traits::size_type position() const
    {
        typename Traits::size_type rank = 0;
        if (mCurrent->mLeft != 0)
            rank += mCurrent->mLeft->mCount;
        if (mCurrent->mParent != 0 && mCurrent->mParent->mRight == mCurrent)
            rank += mCurrent->mParent->mCount;
        return rank;
    }
    
    
    protected:
    
    typename Traits::node_pointer mCurrent;
};

template <typename ValueType,typename ValueAllocator,typename NodeAllocator>
struct rank_tree_traits
{
    // public value types.
    typedef ValueType value_type;
    typedef ValueAllocator allocator_type;
    typedef typename ValueAllocator::size_type size_type;
    typedef typename ValueAllocator::difference_type difference_type;
    
    typedef typename ValueAllocator::pointer pointer;
    typedef typename ValueAllocator::const_pointer const_pointer;
    typedef typename ValueAllocator::reference reference;
    typedef typename ValueAllocator::const_reference const_reference;
    
    // private node types.
    typedef rank_tree_node<value_type,size_type> node_type;
    typedef NodeAllocator node_allocator_type;
    typedef typename NodeAllocator::size_type node_size_type;
    typedef typename NodeAllocator::difference_type node_difference_type;
    
    typedef typename NodeAllocator::pointer node_pointer;
    typedef typename NodeAllocator::const_pointer node_const_pointer;
    typedef typename NodeAllocator::reference node_reference;
    typedef typename NodeAllocator::const_reference const_node_reference;
};

template <
    typename ValueType,
    typename ValueAllocator = std::allocator<ValueType>,
    typename NodeAllocator = typename ValueAllocator::rebind<
        rank_tree_node<ValueType,typename ValueAllocator::size_type> >::other
    >
class rank_tree
{
    protected:
    
    typedef rank_tree_traits<ValueType,ValueAllocator,NodeAllocator> traits;
    typedef rank_tree_traits<const ValueType,ValueAllocator,NodeAllocator> const_traits;
    
    public:
    
    // generic programming types
    typedef typename traits::value_type value_type;
    typedef typename traits::allocator_type allocator_type;
    typedef typename traits::size_type size_type;
    typedef typename traits::difference_type difference_type;
    
    typedef typename traits::pointer pointer;
    typedef typename traits::const_pointer const_pointer;
    typedef typename traits::reference reference;
    typedef typename traits::const_reference const_reference;
    
    // iterator types
    typedef rank_tree_iterator<traits> iterator;
    typedef rank_tree_iterator<const_traits> const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    
    // construction
    explicit rank_tree(
        const ValueAllocator & aAllocator = ValueAllocator(),
        const NodeAllocator & aNodeAllocator = NodeAllocator());
    rank_tree(size_type aCount, const ValueType & aValue,
        const ValueAllocator & aAllocator = ValueAllocator(),
        const NodeAllocator & aNodeAllocator = NodeAllocator());
    explicit rank_tree(size_type aCount,
        const ValueAllocator & aAllocator = ValueAllocator(),
        const NodeAllocator & aNodeAllocator =  NodeAllocator());
    rank_tree(const rank_tree & aSource);
    
    // destruction
    ~rank_tree();
    
    // iterators
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator rend() const;
    
    // unchecked element access
    reference operator[](size_type n);
    const_reference operator[](size_type n) const;
    
    // checked element access
    reference at(size_type n);
    const_reference at(size_type n) const;
    
    // endpoint element access
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;
    
    // asignment
    rank_tree & operator=(const rank_tree & aSource);
    void assign(size_type aCount, const ValueType & aValue);
    
    //stack operations
    void push_front(const ValueType & aValue);
    void pop_front();
    void push_back(const ValueType & aValue);
    void pop_back();
    
    // list operations, non-iterator indexed
    void insert(size_type aPosition, const ValueType & aValue);
    void insert(size_type aPosition, size_type aCount, const ValueType & aValue);
    void erase(size_type aPosition);
    void erase(size_type aFirst, size_type aLast);
    void clear();
    
    // size and capacity
    size_type size() const;
    bool empty() const;
    size_type max_size() const;
    void resize(size_type aCount, const ValueType & aValue);
    void resize(size_type aCount);
    size_type capacity() const;
    void reserve(size_type aExtent);
    
    // misc.
    size_type depth();
    bool verify() const;
    
    
    protected:
    
    typedef typename traits::node_type node_type;
    typedef typename traits::node_allocator_type node_allocator_type;
    typedef typename traits::node_size_type node_size_type;
    typedef typename traits::node_difference_type node_difference_type;
    
    typedef typename traits::node_pointer node_pointer;
    typedef typename traits::node_const_pointer node_const_pointer;
    typedef typename traits::node_reference node_reference;
    typedef typename traits::const_node_reference const_node_reference;
    
    node_pointer mRoot;
    
    node_allocator_type mNodeAllocator;
    
    allocator_type mValueAllocator;
    
    void clear_node(node_pointer aNode);
    
    node_pointer balance_node(node_pointer aNode);
    
    void balance_from_node(node_pointer aNode);
    
    bool verify_node(node_pointer aNode) const;
    
    node_pointer node_at(size_type aPosition) const;
    
    node_pointer node_at(size_type aPosition, size_type aUpdateCount);
    
    node_pointer leftmost_node(node_pointer aNode, size_type aUpdateCount = 0);
    
    node_pointer rightmost_node(node_pointer aNode, size_type aUpdateCount = 0);
    
    void insert_node(size_type aPosition, node_pointer aNode);
    
    void erase_node(node_pointer aNode);
    
    node_pointer allocate_nodes(size_type aCount);
    
    void erase_single_node(node_pointer aNode);
};

// construction
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    rank_tree(const ValueAllocator & aAllocator, const NodeAllocator & aNodeAllocator)
    : mRoot(0), mNodeAllocator(aNodeAllocator), mValueAllocator(aAllocator)
{
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    rank_tree(size_type aCount, const ValueType & aValue, const ValueAllocator & aAllocator, const NodeAllocator & aNodeAllocator)
    : mRoot(0), mNodeAllocator(aNodeAllocator), mValueAllocator(aAllocator)
{
    assign(aCount,aValue);
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    rank_tree(size_type aCount, const ValueAllocator & aAllocator, const NodeAllocator & aNodeAllocator)
    : mRoot(0), mNodeAllocator(aNodeAllocator), mValueAllocator(aAllocator)
{
    assign(aCount,value_type());
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    rank_tree(const rank_tree & aSource)
    : mRoot(0), mNodeAllocator(aSource.mNodeAllocator), mValueAllocator(aSource.mValueAllocator)
{
    *this = aSource;
}

// destruction
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    ~rank_tree()
{
    clear();
}

// iterators
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::iterator
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    begin()
{
    return iterator(node_at(0));
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::const_iterator
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    begin() const
{
    return const_iterator(node_at(0));
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::iterator
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    end()
{
    return iterator(node_pointer(0));
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::const_iterator
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    end() const
{
    return const_iterator(node_pointer(0));
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::reverse_iterator
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    rbegin()
{
    return reverse_iterator(iterator(node_at(size()-1)));
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::const_reverse_iterator
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    rbegin() const
{
    return const_reverse_iterator(const_iterator(node_at(size()-1)));
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::reverse_iterator
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    rend()
{
    return reverse_iterator(iterator(node_pointer(0)));
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::const_reverse_iterator
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    rend() const
{
    return const_reverse_iterator(const_iterator(node_pointer(0)));
}

// unchecked element access
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::reference
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    operator[](size_type n)
{
    if (n >= size())
    {
        resize(n+1);
    }
    return node_at(n)->mValue;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::const_reference
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    operator[](size_type n) const
{
    if (n >= size())
    {
        return reinterpret_cast<const_reference>(0);
    }
    else
    {
        return const_cast<const_reference>(node_at(n)->mValue);
    }
}

// checked element access
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::reference
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    at(size_type n)
{
    if (n >= size())
    {
        throw std::out_of_range("Out of range error.");
    }
    else
    {
        return node_at(n)->mValue;
    }
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::const_reference
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    at(size_type n) const
{
    if (n >= size())
    {
        throw std::out_of_range("Out of range error.");
    }
    else
    {
        return const_cast<const_reference>(node_at(n)->mValue);
    }
}

// endpoint element access
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::reference
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    front()
{
    return (*this)[0];
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::const_reference
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    front() const
{
    return (*this)[0];
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::reference
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    back()
{
    return (*this)[size()-1];
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::const_reference
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    back() const
{
    return (*this)[size()-1];
}

// assignment
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    rank_tree<ValueType,ValueAllocator,NodeAllocator> &
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    operator=(const rank_tree<ValueType,ValueAllocator,NodeAllocator> & aSource)
{
    clear();
    mRoot = allocate_nodes(aSource.size());
    const_iterator si = aSource.begin();
    iterator i = begin();
    iterator e = end();
    while (i != e)
    {
        mValueAllocator.construct(mValueAllocator.address(*i),*si);
        ++i;
        ++si;
    }
    return *this;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    assign(size_type aCount, const ValueType & aValue)
{
    clear();
    resize(aCount,aValue);
}

//stack operations
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    push_front(const ValueType & aValue)
{
    insert(0,aValue);
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    pop_front()
{
    erase(0);
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    push_back(const ValueType & aValue)
{
    insert(size(),aValue);
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    pop_back()
{
    erase(size()-1);
}

// list operations, non-iterator indexed
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    insert(size_type aPosition, const ValueType & aValue)
{
    insert(aPosition,1,aValue);
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    insert(size_type aPosition, size_type aCount, const ValueType & aValue)
{
    for (; aCount > 0; --aCount)
    {
        node_pointer node = mNodeAllocator.allocate(1);
        node->mLeft = 0;
        node->mRight = 0;
        node->mParent = 0;
        node->mCount = 1;
        mValueAllocator.construct(&node->mValue,aValue);
        insert_node(aPosition,node);
    }
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    erase(size_type aPosition)
{
    erase(aPosition,aPosition);
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    erase(size_type aFirst, size_type aLast)
{
    if (aFirst == aLast)
    {
        erase_single_node(node_at(aFirst));
    }
    else
    {
        //! @todo Implement this.
    }
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    clear()
{
    clear_node(mRoot);
    mRoot = 0;
}

// size and capacity
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::size_type
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    size() const
{
    if (mRoot != 0) return mRoot->mCount;
    else return 0;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    bool
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    empty() const
{
    return mRoot == 0;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::size_type
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    max_size() const
{
    return std::min(mValueAllocator.max_size(),mNodeAllocator.max_size());
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    resize(size_type aCount, const ValueType & aValue)
{
    if (aCount < size())
    {
        erase(aCount,size()-1);
    }
    else
    {
        insert(size(),aCount-size(),aValue);
    }
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    resize(size_type aCount)
{
    if (aCount < size())
    {
        erase(aCount,size()-1);
    }
    else
    {
        insert(size(),aCount-size(),value_type());
    }
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::size_type
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    capacity() const
{
    return size();
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    reserve(size_type /* aExtent */)
{
}

// misc.
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::size_type
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    depth()
{
    size_type depth = 1;
    size_type maxDepth = 0;
    node_pointer cursor = mRoot;
    while (cursor != 0)
    {
        // find the leftmost leaf, lowest rank element
        while (true)
        {
            if (cursor->mLeft != 0) { depth += 1; cursor = cursor->mLeft; }
            else if (cursor->mRight != 0) { depth += 1; cursor = cursor->mRight; }
            else break;
        }
        //
        if (depth > maxDepth) maxDepth = depth;
        // find the leftmost leaf of the parent, next-next (ranked) node
        {
            node_pointer last;
            while (true)
            {
                last = cursor;
                depth -= 1;
                cursor = cursor->mParent;
                if (cursor == 0)
                {
                    break;
                }
                else if (cursor->mRight != 0 && cursor->mRight != last)
                {
                    depth += 1;
                    cursor = cursor->mRight;
                    break;
                }
            }
        }
        //
        if (depth > maxDepth) maxDepth = depth;
    }
    return maxDepth;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    bool
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    verify() const
{
    return verify_node(mRoot);
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    clear_node(node_pointer aNode)
{
    if (aNode != 0)
    {
        // ensure in-order destruction of the values, for some measure of consistency
        clear_node(aNode->mLeft);
        mValueAllocator.destroy(&aNode->mValue);
        clear_node(aNode->mRight);
        // nuke the node itself
        mNodeAllocator.destroy(aNode);
        mNodeAllocator.deallocate(aNode,1);
    }
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::node_pointer
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    balance_node(node_pointer aNode)
{
    size_type leftCount = aNode->mLeft != 0 ? aNode->mLeft->mCount : 0;
    size_type rightCount = aNode->mRight != 0 ? aNode->mRight->mCount : 0;
    if (leftCount > rightCount && leftCount-rightCount > 4)
    {
        // rotate the root to the right, because the left is overloaded
        node_pointer leftRightChild = aNode->mLeft->mRight;
        node_pointer rootLeftChild = aNode->mLeft;
        //
        aNode->mLeft = leftRightChild;
        if (leftRightChild != 0) leftRightChild->mParent = aNode;
        //
        rootLeftChild->mRight = aNode;
        rootLeftChild->mParent = aNode->mParent; // this would be null if aNode is mRoot
        // repoint the parent of aNode, if it has one
        if (aNode->mParent != 0 && aNode->mParent->mLeft == aNode) aNode->mParent->mLeft = rootLeftChild;
        else if (aNode->mParent != 0 && aNode->mParent->mRight == aNode) aNode->mParent->mRight = rootLeftChild;
        aNode->mParent = rootLeftChild;
        // recalc the counts
        aNode->mCount =
            (aNode->mLeft != 0 ? aNode->mLeft->mCount : 0)+
            (aNode->mRight != 0 ? aNode->mRight->mCount : 0)+1;
        rootLeftChild->mCount =
            (rootLeftChild->mLeft != 0 ? rootLeftChild->mLeft->mCount : 0)+
            (rootLeftChild->mRight != 0 ? rootLeftChild->mRight->mCount : 0)+1;
        // return the new root
        return rootLeftChild;
    }
    else if (rightCount > leftCount && rightCount-leftCount > 4)
    {
        // rotate the root to the left, because the right is overloaded
        node_pointer rightLeftChild = aNode->mRight->mLeft;
        node_pointer rootRightChild = aNode->mRight;
        //
        aNode->mRight = rightLeftChild;
        if (rightLeftChild != 0) rightLeftChild->mParent = aNode;
        //
        rootRightChild->mLeft = aNode;
        rootRightChild->mParent = aNode->mParent; // this would be null if aNode is mRoot
        // repoint the parent of aNode, if it has one
        if (aNode->mParent != 0 && aNode->mParent->mLeft == aNode) aNode->mParent->mLeft = rootRightChild;
        else if (aNode->mParent != 0 && aNode->mParent->mRight == aNode) aNode->mParent->mRight = rootRightChild;
        aNode->mParent = rootRightChild;
        // recalc the counts
        aNode->mCount =
            (aNode->mLeft != 0 ? aNode->mLeft->mCount : 0)+
            (aNode->mRight != 0 ? aNode->mRight->mCount : 0)+1;
        rootRightChild->mCount =
            (rootRightChild->mLeft != 0 ? rootRightChild->mLeft->mCount : 0)+
            (rootRightChild->mRight != 0 ? rootRightChild->mRight->mCount : 0)+1;
        // return the new root
        return rootRightChild;
    }
    else
    {
        // nothing to balance, return the same root
        return aNode;
    }
}
    
template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    balance_from_node(node_pointer aNode)
{
    // balance as much of the tree as we can
    for (node_pointer balanceNode = aNode; balanceNode != 0; balanceNode = balanceNode->mParent)
    {
        balanceNode = balance_node(balanceNode);
        if (balanceNode->mParent == 0)
        {
            // this is the new root of the tree, make it so
            mRoot = balanceNode;
        }
    }
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    bool
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    verify_node(node_pointer aNode) const
{
    if (aNode != 0)
    {
        size_type r = 1;
        if (aNode->mLeft != 0)
        {
            if (aNode != aNode->mLeft->mParent)
                return false;
            r += aNode->mLeft->mCount;
        }
        if (aNode->mRight != 0)
        {
            if (aNode != aNode->mRight->mParent)
                return false;
            r += aNode->mRight->mCount;
        }
        if (r != aNode->mCount)
            return false;
        else
            return
                (aNode->mLeft != 0 ? verify_node(aNode->mLeft) : true) &&
                (aNode->mRight != 0 ? verify_node(aNode->mRight) : true);
    }
    else
        return true;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::node_pointer
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    node_at(size_type aPosition) const
{
    if (mRoot != 0)
    {
        if (aPosition < size())
        {
            node_pointer node = mRoot;
            size_type rank = aPosition;
            while (true)
            {
                size_type r = 0;
                if (node->mLeft != 0) r += node->mLeft->mCount;
                if (rank == r)
                {
                    return node;
                }
                else if (rank < r)
                {
                    node = node->mLeft;
                }
                else
                {
                    node = node->mRight;
                    rank -= r+1;
                }
            }
        }
        else
            return 0;
    }
    else
        return 0;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::node_pointer
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    node_at(size_type aPosition, size_type aUpdateCount)
{
    if (mRoot != 0)
    {
        if (aPosition < size())
        {
            node_pointer node = mRoot;
            node->mCount += aUpdateCount;
            size_type rank = aPosition;
            while (true)
            {
                size_type r = 0;
                if (node->mLeft != 0) r += node->mLeft->mCount;
                if (rank == r)
                {
                    return node;
                }
                else if (rank < r)
                {
                    node = node->mLeft;
                }
                else
                {
                    node = node->mRight;
                    rank -= r+1;
                }
                node->mCount += aUpdateCount;
            }
        }
        else
            return 0;
    }
    else
        return 0;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::node_pointer
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    leftmost_node(node_pointer aNode, size_type aUpdateCount)
{
    if (aNode != 0)
    {
        // find the leftmost node, while updating the counts
        node_pointer rNode = aNode;
        rNode->mCount += aUpdateCount;
        while (rNode->mLeft != 0)
        {
            rNode = rNode->mLeft;
            rNode->mCount += aUpdateCount;
        }
        return rNode;
    }
    else
        return 0;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::node_pointer
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    rightmost_node(node_pointer aNode, size_type aUpdateCount)
{
    if (aNode != 0)
    {
        // find the rightmost node, while updating the counts
        node_pointer rNode = aNode;
        rNode->mCount += aUpdateCount;
        while (rNode->mRight != 0)
        {
            rNode = rNode->mRight;
            rNode->mCount += aUpdateCount;
        }
        return rNode;
    }
    else
        return 0;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    insert_node(size_type aPosition, node_pointer aNode)
{
    if (aPosition >= size())
    {
        // new node is past the end...
        size_type newCount = aPosition-size()+1;
        if (newCount == 1)
        {
            // only one to insert do it quick...
            // where to insert?
            if (mRoot == 0)
            {
                // we are inserting the first single node at the root
                mRoot = aNode;
            }
            else
            {
                // find the rightmost node, while updating the counts
                node_pointer rNode = rightmost_node(mRoot,aNode->mCount);
                // splice the new new node to the end
                rNode->mRight = aNode;
                aNode->mParent = rNode;
            }
        }
        else
        {
            // one to insert, many to pad...
            // create the pads as a separate balanced subtree.
            node_pointer pad = allocate_nodes(newCount-1);
            // where to insert?
            if (mRoot == 0)
            {
                // nothing in here, make it the root.
                mRoot = pad;
            }
            else
            {
                // insert the pad at the right to enlarge the size
                insert_node(size(),pad);
            }
            // now insert the node at the new right
            insert_node(size(),aNode);
        }
    }
    else
    {
        // new node is somewhere in the middle...
        // find the current node to insert behind, and update count as we go
        node_pointer rNode = node_at(aPosition,aNode->mCount);
        // splice the new node to the left of the target node...
        if (rNode->mLeft == 0)
        {
            /*
                     [rNode@aPoaition]                [rNode@aPosition+1]
                      /              \      =>         /                \
                    [L]              [R]        [aNode@aPosition]       [R]
                                                     /  \
                                                   [l]  [r]
            */
            rNode->mLeft = aNode;
            aNode->mParent = rNode;
        }
        else
        {
            node_pointer L = rNode->mLeft;
            aNode->mCount += L->mCount;
            node_pointer l_ = aNode->mLeft;
            if (l_ == 0)
            {
                /*
                     [rNode@aPoaition]                [rNode@aPosition+1]
                      /              \      =>         /                \
                    [L]              [R]        [aNode@aPosition]       [R]
                                                     /  \
                                                   [L]  [r]
                */
                aNode->mLeft = L;
                rNode->mLeft = aNode;
                aNode->mParent = rNode;
                L->mParent = aNode;
            }
            else
            {
                /*
                     [rNode@aPoaition]                [rNode@aPosition+1]
                      /              \      =>         /                \
                    [L]              [R]        [aNode@aPosition]       [R]
                                                     /  \
                                                   [l]  [r]
                                                   /
                                                 [l']
                                                 /
                                               [L]
                */
                // find the left of the inserted node/tree
                l_ = leftmost_node(l_,L->mCount);
                l_->mLeft = L;
                rNode->mLeft = aNode;
                aNode->mParent = rNode;
                L->mParent = l_;
            }
        }
    }
    // amortize by rebalancing at each insert.
    balance_from_node(aNode);
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    erase_node(node_pointer aNode)
{
    node_pointer parent = aNode->mParent;
    size_type erase_count = aNode->mCount;
    clear_node(aNode);
    if (parent != 0)
    {
        if (parent->mLeft == aNode)
        {
            parent->mLeft = 0;
        }
        else
        {
            parent->mRight = 0;
        }
        do
        {
            parent->mCount -= erase_count;
            parent = balance_node(parent);
            if (parent->mParent == 0)
            {
                mRoot = parent;
            }
            parent = parent->mParent;
        } while (parent != 0);
    }
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    typename rank_tree<ValueType,ValueAllocator,NodeAllocator>::node_pointer
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    allocate_nodes(size_type aCount)
{
    node_pointer result = mNodeAllocator.allocate(1);
    result->mParent = 0;
    result->mCount = aCount;
    size_type residue = aCount-1;
    if (residue > 0)
    {
        result->mLeft = allocate_nodes(std::max(residue/2,size_type(1)));
        residue -= result->mLeft->mCount;
    }
    if (residue > 0)
    {
        result->mRight = allocate_nodes(residue);
    }
    return result;
}

template <typename ValueType, typename ValueAllocator, typename NodeAllocator>
    void
    rank_tree<ValueType,ValueAllocator,NodeAllocator>::
    erase_single_node(node_pointer aNode)
{
    node_pointer left = aNode->mLeft;
    node_pointer right = aNode->mRight;
    node_pointer parent = aNode->mParent;
    aNode->mLeft = 0;
    aNode->mRight = 0;
    aNode->mParent = 0;
    clear_node(aNode);
    if (left != 0 && right != 0)
    {
        // reposition the left subtree, to the left of the right subtree
        node_pointer r_ = leftmost_node(right,left->mCount);
        r_->mLeft = left;
        left->mParent = r_;
    }
    else if (left != 0 && right == 0)
    {
        // only a left subtree, just make it the right subtree
        right = left;
    }
    if (right != 0)
    {
        right->mParent = parent;
        if (parent != 0)
        {
            // put the now single subtree in the correct parent subtree
            if (parent->mLeft == aNode)
            {
                // it was part of the left subtree
                parent->mLeft = right;
            }
            else
            {
                // it was part of the right subtree
                parent->mRight = right;
            }
        }
        else
        {
            // this was the root reset the root to a reasonable place.
            mRoot = right;
            balance_from_node(mRoot);
        }
    }
    else
    {
        // no subtrees
        if (parent != 0)
        {
            // update the parent to remove its subtree.
            if (parent->mLeft == aNode)
            {
                parent->mLeft = 0;
            }
            else
            {
                parent->mRight = 0;
            }
        }
        else
        {
            // it was the root, without subtrees, i.e. the last node, nuke accordingly
            mRoot = 0;
        }
    }
    if (parent != 0)
    {
        // now update the counts up to the root, while balancing
        do
        {
            parent->mCount -= 1;
            parent = balance_node(parent);
            if (parent->mParent == 0)
            {
                mRoot = parent;
            }
            parent = parent->mParent;
        } while (parent != 0);
    }
}

} p_com_redshift_software_libraries_base

#endif