///////////////////////////////////////////////////////////////////////////
// FILE: _rbtree (std::_OW::RedBlackTree definition)
//
// =========================================================================
//
//                          Open Watcom Project
//
// Copyright (c) 2004-2010 The Open Watcom Contributors. All Rights Reserved.
//
//    This file is automatically generated. Do not edit directly.
//
// =========================================================================
//
// Description: This header is an OpenWatcom red black tree container
//              implementation. Although it not part of the 14882 C++ standard
//              library it is written with a similar interface. It is used by
//              the OpenWatcom implementation of the C++ standard library
//              (map, set, multimap, multiset)
///////////////////////////////////////////////////////////////////////////
#ifndef __RBTREE_H_INCLUDED
#define __RBTREE_H_INCLUDED

#ifndef _ENABLE_AUTODEPEND
 #pragma read_only_file;
#endif

#ifndef __cplusplus
 #error This header file requires C++
#endif

#ifndef _UTILITY_INCLUDED
 #include <utility>
#endif

#ifndef _ITERATOR_INCLUDED
 #include <iterator>
#endif

#ifndef _FUNCTIONAL_INCLUDED
 #include <function>
#endif

#ifndef _MEMORY_INCLUDED
 #include <memory>
#endif

namespace std {
namespace _ow {

/* ==================================================================
 * value wrappers
 * Two classes/functors for set and map that allow single keys and 
 * pairs to be used so memory is not wasted.  Provides a common 
 * interface for getting the key value so the same tree code can be used.
 */

template< class Key >
struct TreeKeyWrapper{
    typedef Key const value_type;
    Key const& operator()( value_type const & v ) const
        { return( v ); }
};

template< class Key, class Type >
struct TreePairWrapper{
    typedef pair< Key const, Type > value_type;
    Key const& operator()( value_type const & v ) const
        { return( v.first ); }
};

/* ==================================================================
 * Red-Black Tree container interface
 * To do: 
 *  * find out what supposed to do with allocator alloc/construct exceptions
 *  * rebind and copy allocator
 *  * finish off all functions so has 14882 style interface
 *  * check const is used where ever it can/needed
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
class RedBlackTree{
public:
    typedef ValueWrapper::value_type    value_type;
    typedef Key                         key_type;
    typedef unsigned int                size_type;

protected:
    struct Node{
        enum Chroma { red = 0, black = 1 };
        value_type value;
        Node* left;
        Node* right;
    private:
        Node* parent;

    #if 0
        // simple implementation
        Chroma colour;
    public:
        void   setParent( Node* const p )   { parent = p; }
        Node*  getParent()                  { return( parent ); }
        void   setRed()                     { colour = red; }
        void   setBlack()                   { colour = black; }
        Chroma getColour()                  { return( colour ); }
        void   setColour( Chroma c )        { colour = c; }
        bool   isRed()                      { return( colour == red ); }
        bool   isBlack()                    { return( colour == black ); }

    #else
        // colour hidden in parent
    public:
        void   setParent( Node* const p )
        {   // debug assert parent really has lsb clear ?
            parent = (Node*)( (long)p | ((long)parent & 1) );
        }

        Node* getParent()
            { return( (Node*)( (long)parent & -2 ) ); }

        void setRed()
            { parent = (Node*)( (long)parent & -2 ) ; }

        void setBlack()
            { parent = (Node*)( (long)parent | 1 ) ; }

        Chroma getColour()
            { return( (Chroma)( (long)parent & 1 ) ); }

        void setColour( Chroma c )
        {
            parent = (Node*)( (long)parent & -2 );
            parent = (Node*)( (long)parent |  c );
        }

        bool isRed()
            { return( !( (long)parent & 1 ) ); }

        bool isBlack()
            { return( (bool)( (long)parent & 1 ) ); }
    #endif

        Node( const value_type& v, Node* const p = 0, Chroma c = red )
            : value( v ), left( 0 ), right( 0 )
        {
            setParent(p);
            setColour(c);
        }
    };

    // !!! moved up here until compiler bug fixed !!!
    Allocator::rebind< Node >::other mem;

public:
    class iterator;

    //ctors and dtor
    explicit RedBlackTree( Compare c, Allocator a )
        : mRoot(0), mFirst(0), mLast(0), mSize(0), mError(0), cmp(c), mem(a)
    { }

    template< class InputIterator >
    RedBlackTree(
        InputIterator f,
        InputIterator l,
        Compare const &c,
        Allocator const &a )
        : mRoot(0), mFirst(0), mLast(0), mSize(0), mError(0), cmp(c), mem(a)
    {
        // presume init data sorted, hint ignored when tree empty
        iterator hint;
        for( ; f != l ; ++f ) hint = insert( hint, *f ).first; 
    }

    RedBlackTree( RedBlackTree const & );
    RedBlackTree& operator=( RedBlackTree const & );
   ~RedBlackTree();
    Allocator get_allocator() const 
        { Allocator a( mem ); return( a ); }


    /* ------------------------------------------------------------------
     * iterators
     */
    class iterator_base :
        public std::iterator< std::bidirectional_iterator_tag, value_type> {

        friend class RedBlackTree;
        typedef RedBlackTree<Key, Compare, Allocator, ValueWrapper> rbt_type;

    public:
        bool operator==( iterator_base i )
            { return( self==i.self ); }

        bool operator!=( iterator_base i )
            { return( self!=i.self ); }

        iterator_base& operator++()
        {
            self = rbt->walkRight( self );
            return *this;
        }

        iterator_base& operator--()
        {
            self ? self = rbt->walkLeft( self ) : self = rbt->mLast;
            return *this;
        }

    protected:
        iterator_base( iterator_base const & i ) : self( i.self ), rbt( i.rbt )
            { }

        iterator_base() : self( 0 ), rbt( 0 )
            { }

        iterator_base( rbt_type const * rb, Node* n ) : self(n), rbt(rb)
            { }

        Node* getNodePtr()
            { return( self ); }

        Node* self;
        rbt_type const *rbt;
    };

    class iterator : public iterator_base{
    public:
        iterator() : iterator_base() { }
        iterator( iterator_base const & i ) : iterator_base( i ) { }
        iterator( rbt_type const * rb, Node* n )
            : iterator_base( rb, n )
        { }

        RedBlackTree::value_type& operator*()
            { return( self->value ); }

        RedBlackTree::value_type* operator->()
            { return &(self->value); }

        iterator& operator++()
            { return( (iterator&)iterator_base::operator++( ) ); }

        iterator operator++( int )
            { iterator i = *this; operator++(); return i; }

        iterator& operator--()
            { return( (iterator&)iterator_base::operator--( ) ); }
 
        iterator operator--( int )
            { iterator i = *this; operator--(); return i; }
    };

    class const_iterator : public iterator_base{
    public:
        const_iterator( iterator_base const & i ) : iterator_base( i ) { }
        const_iterator() : iterator_base() { }
        const_iterator( rbt_type const* rb, Node* n )
            : iterator_base( rb, n )
        { }

        RedBlackTree::value_type const& operator*()
            { return self->value; }

        RedBlackTree::value_type const* operator->()
            { return &(self->value); }

        const_iterator& operator++()
            { return( (const_iterator&)iterator_base::operator++()); }

        const_iterator operator++( int )
            { const_iterator i = *this; operator++(); return i; }

        const_iterator& operator--()
            { return( (const_iterator&)iterator_base::operator--()); }

        const_iterator operator--( int )
            { const_iterator i = *this; operator--(); return i; }
    };

    friend class iterator_base;
    friend class iterator;
    friend class const_iterator;
    /*
     * end of iterators
     * ------------------------------------------------------------------ */
    
    iterator end()
        { return iterator( this, (Node*) 0 ); }

    iterator begin()
        { return iterator( this, mFirst ); }

    const_iterator end() const
        { return const_iterator( this, (Node*)0 ); }

    const_iterator begin() const
        { return const_iterator( this, mFirst ); }
    
    //pair< iterator, bool > insert( value_type const & );

    // TODO: Move to out-of-line when compiler supports syntax.
    template< class InputIterator >
    void RedBlackTree< Key, Compare, Allocator, ValueWrapper>::insert(
        InputIterator first_it, InputIterator last_it )
    {
        // presume data sorted; use last insert point as hint
        iterator hint;
        if( first_it != last_it ) hint = insert( *first_it ).first;
        for( ++first_it ; first_it != last_it ; ++first_it )
            hint = insert( hint, *first_it ).first; 
    }

    void            erase( iterator );
    size_type       erase( key_type const & );
    //void erase(iterator first, iterator last);
    void            clear();
    iterator        find( key_type const & );
    bool            empty() const { return( mSize == 0 ); }
    size_type       size() const  { return( mSize ); }
    size_type       max_size() const;
    iterator        upper_bound( key_type const & );
    const_iterator  upper_bound( key_type const & x) const;
    iterator        lower_bound( key_type const & );
    const_iterator  lower_bound( key_type const & x) const;

    std::pair< iterator, iterator >
        equal_range( key_type const & x )
            { return( make_pair( lower_bound(x), upper_bound(x) ) ); }

    std::pair< const_iterator, const_iterator >
        equal_range( key_type const & x ) const
            { return( make_pair( lower_bound(x), upper_bound(x) ) ); }
    
    bool _Sane();
    int mError;

protected:
    void    doubleBlackTransform( Node* parent, bool lefty );
    void    insBalTransform( Node* inserted );
    // std::pair< iterator, bool > unbalancedInsert( value_type const & );
    int     blackHeight( iterator );
    int     height( iterator );
    Node*   walkRight( Node* ) const;
    Node*   walkLeft( Node* ) const;
    int     mSize;
    Node*   mRoot;
    Node*   mFirst;
    Node*   mLast;
    Compare cmp;
    ValueWrapper keyGetter;

    std::pair< RedBlackTree::iterator, bool >
        unbalancedInsert( value_type const & v );

public:
    std::pair< RedBlackTree::iterator, bool >
        insert( value_type const & v );

    std::pair< RedBlackTree::iterator, bool >
        insert( iterator hint, value_type const & v );

}; //class RedBlackTree


/* ==================================================================
 * Red-Black Tree Functions
 */

/* ------------------------------------------------------------------
 * Copy Ctor
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::RedBlackTree(
    RedBlackTree< Key, Compare, Allocator, ValueWrapper > const & that )
    : mem(that.mem)
{
    //copy comparator ? 
    //other bits?
    mSize = that.mSize;
    //copy nodes
    //special case node
    if( !that.mRoot ) {
        // no root, therefore first and last don't exist either
        mFirst = 0;
        mLast = 0;
        mRoot = 0;
        return;
    }
    mRoot = mem.allocate( 1 );
    try {
        mem.construct( mRoot,
                       Node( that.mRoot->value, 0, that.mRoot->getColour() ) );
    } catch( ... ) {
        mem.deallocate( mRoot, 1 );
        mRoot = 0;
        throw;
    }
        
    Node* n;
    Node* o;
    
    o = that.mRoot;
    n = mRoot;
    for( ;; ) {
        //check to see if reached first/last and fix up
        if( o == that.mFirst ) {
            mFirst = n;
        }
        if( o == that.mLast ) {
            mLast = n;
        }
        //logic for tree traverse and copy
        if( o->left && !n->left ) {
            //copy left node if we can/haven't already
            o = o->left;
            try {
                n->left = mem.allocate( 1 );
                try {
                    mem.construct( n->left,
                                   Node( o->value, n, o->getColour() ) );
                } catch( ... ) {
                    mem.deallocate( n->left, 1 );
                    throw;
                }
            } catch( ... ) {
                n->left = 0;
                clear();
                throw;
            }
            n = n->left;
        } else if( o->right && !n->right ) {
            //or copy right node if we can/haven't already
            o = o->right;
            try {
                n->right = mem.allocate( 1 );
                try {
                    mem.construct( n->right,
                                   Node( o->value, n, o->getColour() ) );
                } catch( ... ) {
                    mem.deallocate( n->right, 1 );
                    throw;
                }
            } catch( ... ) {
                n->right = 0;
                clear();
                throw;
            }
            n = n->right;
        } else if( o->getParent() ) {
            //no children nodes left to copy, move back up
            o = o->getParent();
            n = n->getParent();
        } else {
            //no children nodes left to copy and we are root therefore
            //finished
            return;
        }
    } //end for( ;; )
}

/* ------------------------------------------------------------------
 * operator=
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >&
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::operator=(
    RedBlackTree< Key, Compare, Allocator, ValueWrapper > const & that )
{
    clear();
    new ( this ) RedBlackTree( that );  //call copy ctor to do the copy
    return( *this );
}

/* ------------------------------------------------------------------
 * Dtor
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::~RedBlackTree()
{
    clear();
}

/* ------------------------------------------------------------------
 * clear()
 *
 * erase all elements. Should be quicker than iterating through each one as we
 * don't have to walk and rebalance
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
void RedBlackTree< Key, Compare, Allocator, ValueWrapper >::clear( )
{
    //note copy constructor clean up assumes clear() need any members set
    //correctly except mRoot
    Node* n = mRoot;
    while( n ) {
        if( n->left ) n = n->left;
        else if( n->right ) n = n->right;
        else {
            //delete it when all children gone
            if( !n->getParent() ) {
                //if no parent then root, therefore finished
                mem.destroy( n );
                mem.deallocate( n, 1 );
                mSize = 0;
                mRoot = 0;
                mFirst = 0;
                mLast = 0;
                return; 
            }
            if( n == n->getParent()->left ) n->getParent()->left = 0;
            else n->getParent()->right = 0;
            Node* delme = n;
            n = n->getParent();
            mem.destroy( delme );
            mem.deallocate( delme, 1 );
        }
    }
}

/* ------------------------------------------------------------------
 * Find( )
 * Climb the tree until we get to the key :)
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::iterator 
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::find(Key const& findMe)
{
    Node* n=mRoot;
    Node* notLT=0;
    
    while( n ) {
        if( cmp(findMe, keyGetter(n->value) ) ) n = n->left;
        else {
            notLT=n;
            n=n->right;
        }
    }
    // the last node the key is not less than (if any) may be equal, in which
    // case it was found
    if( notLT && !(cmp(keyGetter(notLT->value), findMe) ) ) // !(a<b) & !(b<a) then a==b
        return iterator(this, notLT);
    else
        return end();
}

/* ------------------------------------------------------------------
 * lower_bound( key_type )
 *
 * find first[lowest/most left] node that !(node.key < k) [equivalent to
 * node.key >= k]
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::iterator
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::lower_bound(
    key_type const & findMe )
{
    Node* n = mRoot;
    Node* nodeNotLTkey = 0;
    
    while( n ) {
        if( cmp( keyGetter(n->value), findMe ) ) n = n->right;
        else {
            nodeNotLTkey = n;
            n = n->left;
        }
    }
    // if there are no nodes >= findMe then nodeNotLTkey will still be 0 thus
    // the end() iterator will be created as expected
    return( iterator(this, nodeNotLTkey) );
}

/* ------------------------------------------------------------------
 * lower_bound( key_type ) const
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::const_iterator
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::lower_bound(
    key_type const & k ) const
{
    return( const_cast<RedBlackTree*>(this)->lower_bound( k ) );
}

/* ------------------------------------------------------------------
 * upper_bound( key_type )
 * find first[lowest/most left] node that node.key > k
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::iterator
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::upper_bound(
    key_type const & findMe )
{
    Node* n = mRoot;
    Node* nodeGTkey = 0;
    
    while( n ) {
        if( cmp( findMe, keyGetter(n->value) ) ) {
            nodeGTkey = n;
            n = n->left;
        } else {
            n = n->right;
        }
    }
    // if there are no node > findMe then nodeNotGTkey will still be 0 thus
    // the end() iterator will be created as expected
    return( iterator(this, nodeGTkey) );
}


/* ------------------------------------------------------------------
 * upper_bound( key_type ) const
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::const_iterator
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::upper_bound(
    key_type const & k ) const
{
    return( const_cast<RedBlackTree*>(this)->upper_bound( k ) );
}

/* ------------------------------------------------------------------
 * walkRight( Node* )
 *
 * iterate to next greater node 
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::Node*
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::walkRight(
    Node* n ) const
{
    if( n->right) {
        n = n->right;
        while( n->left ) n = n->left;
    } else {
        while( n->getParent() && (n == n->getParent()->right) ) {
            n = n->getParent();
        }
        n = n->getParent();
    }
    return n;
}

/* ------------------------------------------------------------------
 * walkLeft( Node* )
 * iterate to next node with lower key
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::Node*
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::walkLeft(
    Node* n ) const
{
    if( n->left ) {
        n = n->left;
        while( n->right ) n = n->right;
    } else {
        while( n->getParent() && (n == n->getParent()->left) ) {
            n = n->getParent();
        }
        n = n->getParent();
    }
    return n;
}

/* ------------------------------------------------------------------
 * blackHeight( iterator )
 * calculate black height of node
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
int RedBlackTree< Key, Compare, Allocator, ValueWrapper >::blackHeight(
    iterator i)
{
    Node* n = i.getNodePtr();
    int c = 0;
    while(n) {
        if( n->isBlack() ) c++;
        n = n->getParent();
    }
    return c;
}

/* ------------------------------------------------------------------
 * height( iterator )
 * calculate height of node
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
int RedBlackTree< Key, Compare, Allocator, ValueWrapper >::height( iterator i )
{
    Node* n = i.getNodePtr();
    int c = 0;
    while(n) {
        c++;
        n = n->getParent();
    }
    return c;
}

/* ------------------------------------------------------------------
 * insBalTransform
 *
 * Ref: Chris Okasaki paper (2005?) proposing simple transform for insert
 * ballance and Lyn Turbak CS231 handout #21 (2001)
 * 
 * if uncle is red we just do a colour change, if uncle is black we do a
 * transform in summary 4 cases transform to this:
 *
 *        y(b)          
 *      /     \         
 *    x(r)    z(r)      
 *  /   \     /   \     
 * a(b) b(b) c(b) d(b)  
 *
 * case 1:          case 2:        case 3:         case 4:
 * (insert x)      (insert y)     (insert z)      (insert y)
 *       z             z             x                x
 *      / \           / \           / \              / \
 *     y   d         x   d         a   y            a   z
 *    / \           / \               / \              / \
 *   x   c         a   y             b   z            y   d
 *  / \               / \               / \          / \
 * a   b             b   c             c   d        b   c
 */
template<class Key, class Compare, class Allocator, class ValueWrapper>
void RedBlackTree<Key, Compare, Allocator, ValueWrapper>::insBalTransform(
    Node* inserted)
{
    // at this point inserted->colour == red;
    for( ;; ) { 
        /* terminating case
         * 1. we have moved up the tree and are now the root
         * 2. our parent is the root (therefore must be black)
         * 3. our parent is black (no red-red problem any more)
         */
        if( inserted->getParent() == 0 ||
            inserted->getParent()->getParent() == 0 ||
            inserted->getParent()->isBlack() )
            return;

        /* so at this point parent must also be red, and grandparent must be
         * black therefore our sibling must be black (our children are black
         * by definition) leaving two main cases : our uncle can black or red
         */
        Node* parent = inserted->getParent();
        Node* grandparent = inserted->getParent()->getParent();
        Node* uncle;
        //find uncle
        if( parent == grandparent->left ) uncle = grandparent->right;
        else uncle = grandparent->left;

        if( uncle && (uncle->isRed()) ) {    // main case a: red uncle
            // now we propergate grandparents blackness between parent and
            // uncle (without need to rotate)
            grandparent->setRed();
            parent->setBlack();
            uncle->setBlack();
            mRoot->setBlack();      // just in case grandparent was root
            inserted = grandparent; // prepare to propergate red-red up tree
            // the execusion flow now jumps back to the for loop instead of
            // recursive insBalTransform( inserted );
        } else { // main case b:  black uncle
            Node *x,*y,*z,*b,*c;
            // case 1
            if( (inserted == parent->left) && (parent == grandparent->left) ) {
                x = inserted;
                y = parent;
                z = grandparent;
                b = x->right;
                c = y->right;
            }
            //case 2 
            else if( (inserted == parent->right) && (parent == grandparent->left) ){
                x = parent;
                y = inserted;
                z = grandparent;
                b = y->left;
                c = y->right;
            }
            //case 3
            else if( (inserted == parent->right) && (parent == grandparent->right) ){
                x = grandparent;
                y = parent;
                z = inserted;
                b = y->left;
                c = z->left;
            }
            //case4
            else if( (inserted == parent->left) && (parent == grandparent->right) ){
                x = grandparent;
                y = inserted;
                z = parent;
                b = y->left;
                c = y->right;
            }
            
            //recolour - can use this order becase all leafs a,b,c,d must be
            //black (uncle is black) this will stop red-red violation from
            //propergating
            y->setBlack();
            x->setRed();
            z->setRed();
            
            //transform to balanced structure
            if( grandparent == mRoot ) {
                mRoot = y;
                y->setParent( 0 );
            } else {
                if (grandparent->getParent()->left == grandparent){
                    grandparent->getParent()->left = y;
                } else { //grandparent is righty
                    grandparent->getParent()->right = y;
                }
                y->setParent( grandparent->getParent() );
            }
            
            y->left = x;
            y->right = z;
            x->setParent( y );
            z->setParent( y );
            x->right = b;
            z->left = c;
            if( b ) b->setParent( x );
            if( c ) c->setParent( z );
            // a and d are always already linked to the right parent in this
            // case we have fixed the red-red violation so finish
            return;
        } //end main case uncle black
    } //end for( ever )
}

/* ------------------------------------------------------------------
 * _Sane( )
 *
 * test the implementation for errors and test the container hasn't been
 * corrupt return true if everything is ok
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
bool RedBlackTree< Key, Compare, Allocator, ValueWrapper >::_Sane()
{
    if( !mRoot ) {
        //no element in tree
        if( mSize != 0 ) {
            mError = 10;
            return false;
        } else {
            //nothing else in tree to check
            return true;
        }
    }
    iterator it = begin();
    Node* n = it.getNodePtr();
    Node* highN = n;
    Node* lowN = n;
    Key const * lowkey = &keyGetter(n->value);
    Key const * highkey = &keyGetter(n->value);
    int count = 0;
    int maxheight = height(it);
    int bheight = -1;
    
    if( n->left ) {             //begining element cant have a left node
        mError = 20;
        return false;
    }
    if( mRoot->isRed() ) {
        mError = 25;
        return false;           //root should always be black
    }
    
    do {
        if( ++count > size()  ){
            mError = 30;                // we could have got trapped in
            return false;               // a loop, cant be more iterations
        }                               // than size
        Node* n_old = n;
        n = it.getNodePtr();
        if( (it != begin()) && (n_old == n) ) {
            mError = 40;                //circular links:
            return false;               //iterating didn't advance
        }
        if( n->isRed() &&
            n->getParent() &&
            n->getParent()->isRed() ) {
            mError = 50;
            return false;               //red-red error
        }
        if( n->getParent() &&
            (n->getParent()->left != n) &&
            (n->getParent()->right != n) ) {
            mError = 60;
            return false;               //links broken
        }
        if( !n->getParent() && (mRoot != n) ) {
            mError = 70;
            return false;              //links broken
        }
        if( (n->left == n) || (n->right == n) ) {
            mError = 80;
            return false;               //simple circular loop detection
            //? not sure this works as iterating will get stuck before
            //detection ?
        }
        if( !n->getParent() && n!=mRoot) {
            mError = 90;
            return false;               //no parent but not root
        }
        //keep track of the lowest key we come across
        if( cmp( keyGetter(n->value), *lowkey) ) {
            lowkey = &keyGetter(n->value);
            lowN = n;
        }
        //keep track of the highest key we come across
        if( cmp(*highkey, keyGetter(n->value)) ) {
            highkey = &keyGetter(n->value);
            highN = n;
        }
        if( !n->left || !n->right ) {   //null child is a leaf
            int bh = blackHeight(it);
            if( bheight == -1 ) bheight = bh;
            else if(bheight != bh) {
                mError = 100;
                return false;           //black height to leaves not same
            }
        }
        int h = height(it);             //keep track of deepest node depth
        if( h > maxheight ) maxheight = h;
        
    } while( ++it != end() );
    
    if( count != size() ) {
        mError = 110;
        return false;
    }        
    if( n->right ) { // end element cant have a right node
        mError = 120;
        return false;
    }
    if( (highN != (--end()).getNodePtr()) ||
        (lowN != begin().getNodePtr()) ) {
        mError = 130;
        return false;
    }
    return true;
}

/* ------------------------------------------------------------------
 * Erase( key )
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::size_type
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::erase( const Key& k )
{
    iterator it = find(k);
    if(it == end()) return 0;
    else{
        erase(it);
        return 1;
    }
}

/* ------------------------------------------------------------------
 * Erase( iterator )
 * Maybe to do: this isn't the most easy to understand, is there a nicer
 * way of writing it?
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
void RedBlackTree< Key, Compare, Allocator, ValueWrapper >::erase(
    iterator it )
{
    Node* delme = it.getNodePtr();
    Node* child;    //(re)moved endnode child
    Node* parent;   // parent of (re)moved endnode 
    bool  lefty;    //true if (re)moved endnode was left child
    Node::Chroma colour;    //(re)moved endnode colour
    
    mSize--;
    
    if( delme == mFirst ) {
        if( delme == mLast ) {
            //special case, deleted == only element in tree
            mFirst = 0;
            mLast = 0;
        } else 
            mFirst = walkRight(delme);
    } else if( delme == mLast) mLast = walkLeft(delme);
    
    //if not end node swap for predecessor
    if( delme->left && delme->right) {
        Node* predecessor = walkLeft(delme);
        colour = predecessor->getColour();
        child = predecessor->left;  //predecessor can't have a right child
        if( predecessor == predecessor->getParent()->left ) lefty = true;
        else lefty = false;
        //fix up parent's link 
        if( delme == mRoot )
            mRoot = predecessor;
        else if( delme == delme->getParent()->left ) {
            delme->getParent()->left = predecessor;
        } else {
            delme->getParent()->right = predecessor;
        }
        //if delme is one level above predecessor we have to be
        //careful linking left as it could create a circular link
        //and a link to the deleted item
        if( predecessor != delme->left ) {
            //fix up chidren's link
            delme->left->setParent( predecessor );
            //fix predecessors link
            predecessor->left = delme->left;
            parent = predecessor->getParent();
        } else { //predecessor is erased node's child
            parent = predecessor;
            //leave old left child links intact
        }
        //common bits
        //fix childrens links
        delme->right->setParent( predecessor );
        //fix predecessor's links
        predecessor->setColour( delme->getColour() );
        predecessor->setParent( delme->getParent() );
        predecessor->right = delme->right;
    }
    else { //end node
        if( delme->left ) child = delme->left;
        else child = delme->right;
        parent = delme->getParent();
        colour = delme->getColour();
        if( parent && (delme == parent->left) ) lefty = true;
        else lefty = false;
    }
    
    //delete delme;
    mem.destroy( delme );
    mem.deallocate( delme, 1 );
    //handle simple cases
    if( !parent ) {
        //root with up to 1 child
        if( child ) {
            mRoot = child;
            mRoot->setParent( 0 );
            mRoot->setBlack();
        } else {
            mRoot = 0;
        }
    } else if( colour == Node::red ) {
        //red end node cant have a single child node or it would have violated
        //red-red rule or black height rule removing it doesn't change black
        //height so we are done
        if( lefty ) parent->left = 0;
        else parent->right = 0;
    } else if( child ) {
        //black end node may have a single child, in which case it has to be
        //red and we can fix up the black height easily
        if( lefty ) {
            parent->left = child;
        } else { //righty
            parent->right = child;
        }
        child->setParent( parent );
        child->setBlack();
    } else {
        //black node with no children, 
        if( lefty ) parent->left = 0;
        else parent->right = 0;
        //(re)moving this will cause black height problem do some operations
        //to keep rb tree valid
        doubleBlackTransform( parent,lefty );
    }
    
    return;
}

/* ------------------------------------------------------------------
 * DoubleBlackTransform
 * Fix double-black node to rebalance the tree after delete
 * 
 * references: backs of lots of matchboxes :)
 *
 * (this doesn't touch key or type, can the compiler figure out it can use one
 * block of code for all template instantiations or does it need to be coded
 * in a non template base class?)
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
void
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::doubleBlackTransform(
    Node* parent, bool lefty )
{
    for( ;; ) {
        Node* sibling;
        Node *x,*y,*z,*b,*c;
        if( lefty ) {
            sibling = parent->right;
        } else { //righty
            sibling = parent->left;
        }
        
        if( sibling->isBlack() ) {
            if( ( sibling->right && sibling->right->isRed() ) ||
                ( sibling->left && sibling->left->isRed() ) ) {
        //main case 1 sibling black, at least one nephew red we can fix this
        //case
    /*
     *     case a               case b        case c              case d    
     *      Z(*)                 Z(*)          X(*)                X(*)     
     *     /   \\               /   \\       //    \             //    \    
     *   X(b)   d(bb)         Y(b)   d(bb)  a(bb)   Y(b)       a(bb)   Z(b) 
     *  /    \               /    \                 /  \              /  \  
     * a(*)   Y(r)          X(r)  c(*)            b(*) Z(r)         Y(r) d(*)
     *       /   \         /   \                       /   \       /   \    
     *     b(b)   c(b)   a(b)  b(b)                   c(b) d(b)   b(b) c(b) 
     *
     * Transform to this:
     *       Y(*)
     *      /     \
     *   X(b)      Z(b)
     *  /   \     /   \
     * a(*) b(*) c(*) d(*)
     *
     * where double black goes black & new root takes old root colour note
     * nodes a,b,c may be null (leafs)
     */
                if( sibling->right && sibling->right->isRed() ) {
                    if( lefty ) {       // case 1 c
                        x = parent;
                        y = sibling;
                        z = sibling->right;
                        b = y->left;
                        c = z->left;
                    } else {            // case 1 a
                        z = parent;
                        x = sibling;
                        y = sibling->right;
                        b = y->left;
                        c = y->right;
                    }
                } else { // sibling->left && sibling->left->colour == red 
                    if( lefty ) {       // case 1 d
                        x = parent;
                        z = sibling;
                        y = sibling->left;
                        b = y->left;
                        c = y->right;
                    } else {            // case 1 b
                        z = parent;
                        y = sibling;
                        x = sibling->left;
                        b = x->right;
                        c = y->right;
                    }
                }
                // finish off case 1 by relinking to correct sturcture
                y->setParent( parent->getParent() );
                if( parent == mRoot ) mRoot = y;
                else{    //link grandparent back to y;
                    if( parent == parent->getParent()->left ) 
                        parent->getParent()->left = y;
                    else parent->getParent()->right = y;
                }
                y->setColour( parent->getColour() );
                y->left = x;
                y->right = z;
                x->setParent( y );
                x->setBlack();
                x->right = b;       // x->left is unchanged as a
                if( b ) b->setParent( x );
                z->setParent( y );
                z->setBlack();
                z->left = c;        // z->right is unchanged as d
                if( c ) c->setParent( z );
                return;
            } else {  //nephews both black
                if( parent->isRed() ){
        //main case 2: sibling black, two black nephews, parent red we can fix
        //this case
        /*
         *      case a           case b         
         *       Z(r)             X(r)          
         *      /   \\           //   \         
         *    X(b)   d(bb)     a(bb)  Z(b)      
         *   /    \                  /    \     
         *  a(b)   b(b)             b(b)  d(b)  
         * 
         * Recolour to this:
         *        Z(b)              X(b)        
         *       /    \            /    \       
         *    X(r)    d(b)       a(b)   Z(r)    
         *   /   \                     /    \   
         *  a(b) b(b)                b(b)   d(b)
         *
         */
                    parent->setBlack();
                    sibling->setRed();
                    return;
                } else { //parent black
        //main case 3: sibling black, two black nephews, parent black
        /*
         *        case a           case b       
         *         Z(b)             X(b)        
         *        /   \\           //   \       
         *      X(b)   d(bb)     a(bb)  Z(b)    
         *     /    \                  /    \   
         *    a(b)   b(b)             b(b)  d(b)
         * 
         * Recolour to propergate double black:
         *        ||                ||          
         *       Z(bb)             X(bb)        
         *      /     \           /    \        
         *   X(r)      d(b)     a(b)   Z(r)     
         *  /   \                     /    \    
         * a(b) b(b)                b(b)   d(b) 
         *
         * Not much we can do - propergate double black If double black has
         * properaged to to root just set it black as we have acheived balance
         * (higher order special cases may be possible eg node a has two red
         * children but probably not worth the extra code to check?)
         */
                    sibling->setRed();
                    if( parent == mRoot ) {
                        parent->setBlack();
                        return;
                    }
                    Node* grandparent = parent->getParent();
                    if( parent == grandparent->left) lefty = true;
                    else lefty = false;
                    //loop to top of doubleBlackTransform with new parent
                    //(replaces recursion) doubleBlackTransform(grandparent,
                    //lefty); return;
                    parent = grandparent;
                }
            } //end main case 2/3
        } else {
        //main case 4: red sibling
        /*
         *        case a           case b       
         *         Z(b)             X(b)        
         *        /   \\           //   \       
         *      X(r)   d(bb)     a(bb)  Z(r)    
         *     /    \                  /    \   
         *    a(b)   b(b)             c(b)  d(b)
         * 
         * Recolour to propergate double black:
         *       X(b)                   Z(b)    
         *      /    \                 /    \   
         *   a(b)     Z(r)           X(r)   d(b)
         *           /   \\         //  \       
         *         b(b)  d(bb)   a(bb)  c(b)    
         *
         * This is an annoying one! Note, a and b must have children (ie a/b
         * can't be null/leaves) or the black height doesn't add up. Double
         * black stays with the same node but restructure so we can use one of
         * the previous cases (1 or 2) where the sibling is black.
         */
            //common bits
            if( parent == mRoot ) {
                mRoot = sibling;
                sibling->setParent( 0 );
            } else if ( parent == parent->getParent()->left ) {
                parent->getParent()->left = sibling;
                sibling->setParent( parent->getParent() );
            } else {//parent is a righty
                parent->getParent()->right = sibling;
                sibling->setParent( parent->getParent() );
            }
            parent->setRed();
            sibling->setBlack();
            
            if( lefty ) {
                //case b
                x = parent;
                c = sibling->left;
                z = sibling;
                x->right = c;      
                c->setParent( x );
                x->setParent( z );
                z->left = x;
                //a & d stay linked to the same nodes
            } else {  //righty
                //case a
                z = parent;
                b = sibling->right;
                x = sibling;
                z->left = b;
                b->setParent( z );
                z->setParent( x );
                x->right = z;
                //a & d stay linked to the same nodes
            }
            //now try again and case will be 1, 2, or 3 note old parent is
            //still parent of double black and left/right position of double
            //black hasn't changed recursion has been replaced with the for
            //loop doubleBlackTransform(parent,lefty); return;
        }
    }//end for( ever )
}


/* ------------------------------------------------------------------
 * unbalancedInsert( value_type const & )
 *
 * like find but create new node after last node visited if cant find an
 * existing key
 */
template< class Key, class Compare, class Allocator, class ValueWrapper>
std::pair< typename RedBlackTree< Key,
                                  Compare,
                                  Allocator,
                                  ValueWrapper >::iterator, bool >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::unbalancedInsert(
  value_type const & v)
{
    if( mRoot==0 ) {                 //special case nothing exists yet
        mRoot = mem.allocate( 1 );
        try{
            mem.construct( mRoot, Node( v, 0, Node::black ) );
        } catch( ... ) {
            mem.deallocate( mRoot, 1 );
            mRoot = 0;
            throw;
        }
        mFirst = mRoot;
        mLast = mRoot;
        mSize++;
        return( std::pair<iterator, bool>( iterator(this, mRoot), true ) );
    }
    
    Node* n = mRoot;
    Node* notLT = 0;
    Node* last = n;
    bool LtLast;
    
    while( n ) {
        if( cmp(keyGetter( v ), keyGetter( n->value ) ) ) {
            last = n;
            LtLast = true;
            n = n->left;
        } else {
            last = n;
            LtLast = false;
            notLT = n;
            n = n->right;
        }
    }

    // the last node the key is not less than (if any) may be equal, in which
    // case it was found
    if( notLT && 
        !( cmp( keyGetter( notLT->value ), keyGetter( v ) ) ) ) {
        // !(a<b) & !(b<a) then a==b
        return( std::pair<iterator,bool>( iterator(this, notLT), false ) );
    }
    // else insert the new node with parent as last node travelled to
    Node* newnode = mem.allocate( 1 );
    try {
        mem.construct( newnode, Node( v, last, Node::red ) );
    } catch( ... ) {
        mem.deallocate( newnode, 1 );
        throw;
        }
    mSize++;
    if( LtLast ) {
        last->left = newnode;
        if( last == mFirst ) mFirst = newnode;
    } else {
        last->right = newnode;
        if( last == mLast ) mLast = newnode;
    }
    
    return( std::pair<iterator,bool>( iterator(this, newnode), true ) );
}


/* ------------------------------------------------------------------
 * insert( value_type const & )
 *
 * inserts v into the tree if it doesn't exist already and maintains balance
 * returns a pair containing iterator with key equivelent to that of v and a
 * bool that is true if v was inserted or false if the key already existed
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
std::pair< typename RedBlackTree< Key,
                                  Compare,
                                  Allocator,
                                  ValueWrapper >::iterator, bool >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::insert(
    value_type const & v)
{
    pair< iterator, bool > inserted = unbalancedInsert( v );
    if( inserted.second ) { 
        Node* n = inserted.first.getNodePtr();
        if( n != mRoot ) {
            //do some operations to keep rb tree valid
            insBalTransform( n );
        }
        // else if n==mRoot it has been inserted as single black node and
        // there is nothing else to do
    }
    return inserted;
}


/* ------------------------------------------------------------------
 * insert( iterator hint, value_type const &)
 *
 * inserts v into the tree if it doesn't exist already and maintains ballance
 * returns a pair containing iterator with key equivelent to that of v and a
 * bool that is true if v was inserted or false if the key already existed
 * Written in the spirit of N1780 (not strictly standard compliant?)
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
std::pair< typename RedBlackTree< Key,
                                  Compare,
                                  Allocator,
                                  ValueWrapper >::iterator, bool >
RedBlackTree< Key, Compare, Allocator, ValueWrapper >::insert(
    iterator hint, value_type const & v )
{
    pair< iterator, bool > inserted;
    iterator b4hint;
    if( mSize &&
        ( hint == end() || cmp( keyGetter(v), keyGetter(*hint) ) ) ) {

        //at this point tree isn't empty and key is before hint
        b4hint = hint;
        if( hint == begin() ||
            cmp( keyGetter( *(--b4hint) ), keyGetter( v ) ) ) {

            //at this point key is also before begin or after (hint-1) so hint
            //is good now, either hint->left or (hint-1)->right must have a
            //unused leaf node where the new node belongs
            Node* parent;
            bool lefty = true;

            if( hint != end() && hint.getNodePtr()->left == 0 ) {
                parent = hint.getNodePtr();
            } else {
                parent = b4hint.getNodePtr();
                lefty = false;
            }
            //create the new node
            Node* newnode = mem.allocate( 1 );
            try {
                mem.construct( newnode, Node(v, parent, Node::red) );
            } catch( ... ) {
                mem.deallocate( newnode, 1 );
                throw;
            }
            mSize++;
            //fix up pointers
            if( lefty ) {
                parent->left = newnode;
                if( parent == mFirst ) mFirst = newnode;
            } else {
                parent->right = newnode;
                if( parent == mLast ) mLast = newnode;
            }
            inserted = make_pair( iterator(this, newnode), true );
        } else inserted = unbalancedInsert( v ); //hint bad (or key already exists)
    } else inserted = unbalancedInsert( v ); //hint is bad or tree is empty
    
    if( inserted.second ) { 
        Node* n = inserted.first.getNodePtr();
        if( n != mRoot ) {
            //do some operations to keep rb tree valid
            insBalTransform(n);
        }
        // else if n==mRoot it has been inserted as single black node and
        // there is nothing else to do
    }
    return inserted;
}


/* ================================================================== */




/* ==================================================================
 * MLRBTNode 
 * sub-node type that forms a linked list and is stored in the 
 * rbtree node to create the MultiListRBTree
 */
template< class ValueType >
struct MLRBTNode{
    MLRBTNode* fwd;
    MLRBTNode* bwd;
    ValueType value;
    MLRBTNode() {}
    MLRBTNode( ValueType v ) : value( v ) { }
};

/* ==================================================================
 * ValueWrappers for MultiListRBTree
 *
 * pairs for multimap, plain Keys for multiset wraps up the rbtree type
 * (pointer to the list) and knows how to get a key out of it
 */
template< class Key, class Type >
struct ListTreePairWrapper{
    //this is the value_type actually contained in the container
    typedef pair< Key const, Type > value_type;
    Key const& operator()( value_type const & v ) const
        { return( v.first ); }
    
    struct TreeWrapper{
        //this is the rbtree value_type (pointer to list)
        typedef MLRBTNode< pair< Key const, Type > >* value_type;
        Key const& operator()( value_type const & v ) const
            { return( v->value.first ); }
    };
};

template< class Key >
struct ListTreeKeyWrapper{
    //this is the value_type actually contained in the container
    typedef Key value_type;
    Key const& operator()( value_type const & v ) const
        { return( v ); }
    
    struct TreeWrapper{
        //this is the rbtree value_type (pointer to list)
        typedef MLRBTNode< Key >* value_type;
        Key const& operator()( value_type const & v ) const
            { return( v->value); }
    };
};

/* ==================================================================
 * MultiListRBTree 
 *
 * Adds linked list to redblack tree to build a multimap/set. handles the list
 * operations in this class rather than using a full blown (or even a cut down
 * one) list object in tree node. This should save a little memory. Note for a
 * low number of repetitions of each key this alogorithm will use more memory
 * than holding the repeated nodes directly in tree for this algorithm p = 4 +
 * 2n ; c = 1 for tree only algo p = 3n ; c = n where p is num of pointers, c
 * is num of colour enums, n is num of key repetitions so if c uses same space
 * as p (likely due to alignment?) this algo is better if n >=3 This algo
 * should have slightly faster find (+ insert/delete) operations
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
class MultiListRBTree{
public:
    typedef ValueWrapper::value_type        value_type;
    typedef unsigned int                    size_type;
    typedef Key                             key_type;

private:
    typedef RedBlackTree< Key, Compare, Allocator, ValueWrapper::TreeWrapper > tree_type;
    typedef MLRBTNode< value_type > node_type;
    
    Allocator::rebind< node_type >::other mem; //moved up here to stop crash

public:
    MultiListRBTree(Compare c, Allocator a)
        : mSize( 0 ), mTree( tree_type( c, a ) ), mem( a )
    { }

    MultiListRBTree( MultiListRBTree const & );
    ~MultiListRBTree();

    Allocator get_allocator() const 
        { Allocator a(mem); return( a ); }

    MultiListRBTree& operator=( MultiListRBTree const & );
    
    /* ------------------------------------------------------------------
     * iterators
     */
    class iterator_base;
    friend class iterator_base;

    class iterator_base{
    public:
        iterator_base& operator++() 
        { 
            if( self == (*tit)->bwd ) {  //if last element in list
                ++tit;
                if( tit != mlt->mTree.end() ) self = *tit;  //move on to first list node in next tree node
                else self = 0;          //signals end iterator
            } else {
                self = self->fwd;
            }
            return( *this );
        }

        iterator_base& operator--()
        {
            if( self == 0 || self == (*tit) ) {
                                      //if first element in list or end of list
                --tit;                //move back to last list node in 
                self = (*tit)->bwd;   //previous tree node
            } else {
                self = self->bwd;
            }
            return( *this );
        }

        value_type& operator*()
            { return( self->value ); }

        value_type* operator->()
            { return( &(self->value) ); }

        bool operator==( iterator_base const & that )
            { return( self == that.self ); }

        bool operator!=( iterator_base const & that )
            { return( self != that.self ); }

        iterator_base const & operator=( iterator_base const & that ) 
        {
            tit = that.tit;
            mlt = that.mlt;
            self = that.self;
            return( *this );
        }

    protected:
        friend class MultiListRBTree;
        iterator_base()
        { }

        iterator_base( iterator_base const & x )
            : tit( x.tit ), mlt( x.mlt ), self( x.self )
        { }

        iterator_base( MultiListRBTree const* m, tree_type::iterator const &i ) 
            : mlt( m ), tit( i )
            { ( tit != (mlt->mTree).end() ) ? self = (*tit) : self = 0; }

        iterator_base( MultiListRBTree const* m,
                       tree_type::iterator const & i,
                       node_type* n )
            : mlt( m ), tit( i ), self( n )
        { }

        tree_type::iterator tit;
        MultiListRBTree const* mlt;
        node_type* self;
    };

    class iterator : public iterator_base{
    public:
        iterator() : iterator_base() {}
        iterator( iterator const & i ) : iterator_base(i) {}
        iterator( MultiListRBTree const* m, tree_type::iterator const & i) 
            : iterator_base( m, i )
        { }

        iterator( MultiListRBTree const* m,
                  tree_type::iterator const & i,
                  node_type* n )
            : iterator_base( m, i, n )
        { }

        iterator& operator++()
            { return( (iterator&)iterator_base::operator++() ); }

        iterator& operator--()
           { return( (iterator&)iterator_base::operator--() ); }

        iterator& operator++( int )
           { iterator i(*this); operator++(); return( i ); }

        iterator& operator--( int )
           { iterator i(*this); operator--(); return( i ); }
    };

    class const_iterator : public iterator_base{
        public:
        const_iterator() : iterator_base() {}
        const_iterator( const_iterator const & i ) : iterator_base(i) {}
        const_iterator( iterator const & i ) : iterator_base(i) {}
        const_iterator( MultiListRBTree const* m, tree_type::iterator const & i) 
            : iterator_base( m, i )
        { }

        const_iterator( MultiListRBTree const* m,
                        tree_type::iterator const & i,
                        node_type* n )
            : iterator_base( m, i, n )
        { }

        const_iterator& operator++()
            { return( (const_iterator&)iterator_base::operator++() ); }

        const_iterator& operator--()
            { return( (const_iterator&)iterator_base::operator--() ); }

        const_iterator& operator++( int )
            { const_iterator i(*this); operator++(); return( i ); }

        const_iterator& operator--( int )
            { const_iterator i(*this); operator--(); return( i ); }
    };

    iterator begin()
        { return( iterator( this, mTree.begin() ) ); }

    iterator end()
        { return( iterator( this, mTree.end() ) ); }

    // note use const_cast<> so calls version of mTree.end()/begin() that
    // return an iterator not a const_iterator for interal use within the
    // iterator of this class. mTree still doesn't get modified.
    const_iterator begin() const
        { return( const_iterator( this, const_cast<tree_type*>(&mTree)->begin() ) ); }

    const_iterator end() const
        { return( const_iterator( this, const_cast<tree_type*>(&mTree)->end() ) ); }

    //capacity
    size_type   size() { return( mSize ); }
    bool        empty() { return( !mSize ); }
    //modifiers
    iterator    insert( value_type const & );
    iterator    insert( iterator, value_type const & );
    void        erase( iterator );
    size_type   erase( key_type const & );
    void        clear();
    //operations
    iterator        find( key_type const & );
    size_type       count( key_type const & );
    iterator        upper_bound( key_type const & );
    const_iterator  upper_bound( key_type const & x) const;
    iterator        lower_bound( key_type const & );
    const_iterator  lower_bound( key_type const & x) const;

    std::pair< iterator, iterator > equal_range( key_type const & x )
        { return( make_pair( lower_bound(x), upper_bound(x) ) ); }

    std::pair< const_iterator, const_iterator > equal_range( key_type const & x ) const
        { return( make_pair( lower_bound(x), upper_bound(x) ) ); }
    
    //owstl extentions
    bool _Sane();
private:
    size_type mSize;
    tree_type mTree;            //this is the tree that holds the lists
    Compare cmp;
    ValueWrapper keyGetter;
};

/* ------------------------------------------------------------------
 * copy ctor
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::MultiListRBTree( 
    MultiListRBTree< Key, Compare, Allocator, ValueWrapper > const & that )
    : mTree( that.mTree ), mem( that.mem )
{
    // pointer to old list elements is copied by rbtree copy ctor and the
    // pointers will still link back to the old list elements so now make
    // copies of new list elments and fixup pointers
    tree_type::iterator it;
    tree_type::const_iterator it2;
    try {
        for( it = mTree.begin(), it2 = that.mTree.begin();
             it != mTree.end();
             ++it, ++it2 ) {
            //special case, copy the first element in the list
            try {
                *it = mem.allocate( 1 );
                try {
                    mem.construct( *it, **it2 );
                } catch( ... ) {
                    mem.deallocate( *it, 1 );
                    throw;
                }
            } catch( ... ) {
                //signal no first element to rewind logic
                *it = 0;
                throw;
            }
            //copy the rest of the list (if they exist)
            node_type* start = *it2;
            node_type* o = start->fwd;
            node_type* n = *it;
            while( o != start ) {
                try {
                    //allocate the next node
                    n->fwd = mem.allocate( 1 );
                    try {
                        //o already points to the next node
                        mem.construct( n->fwd, *o );
                    } catch( ... ) {
                        mem.deallocate( n->fwd, 1 );
                        throw;
                    }
                } catch( ... ) {
                    //finish off the links so can do a generic rewind
                    n->fwd = *it;
                    (*it)->bwd = n;
                    throw;
                }
                n->fwd->bwd = n;
                n = n->fwd;
                o = o->fwd;
            }
            n->fwd = *it;
            (*it)->bwd = n;
        }
    } catch( ... ) {
        //the copy either completely succeeds or completely fails so rewind
        //the nodes added so far:
        for( ; it != mTree.begin(); --it ) {
            if( *it == 0 ) continue;
            node_type* n = *it;
            node_type* delme;
            node_type* end = n;
            do {
                delme = n;
                n = n->fwd;
                mem.destroy( delme );
                mem.deallocate( delme, 1 );
            } while( n != end );
        }
        mTree.clear();
        throw;
    }
    
    //success
    mSize = that.mSize;
}

/* ------------------------------------------------------------------
 * operator=( that )
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >&
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::operator=(
    MultiListRBTree const & that )
{
    clear();
    new ( this ) MultiListRBTree(that);
    return( *this );
}

/* ------------------------------------------------------------------
 * insert( value_type const & )
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::iterator
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::insert(
    value_type const & x )
{
    node_type* n;
    pair< tree_type::iterator, bool > ans;
    n = mem.allocate( 1 );
    try {
        mem.construct( n, node_type(x) );
    } catch( ... ) {
        mem.deallocate( n, 1 );
        throw;
    }
    try {
        ans = mTree.insert( n );
    } catch( ... ) {
        mem.destroy( n );
        mem.deallocate( n, 1 );
        throw;
    }
    if( ans.second ) {  //insert happened
        n->fwd = n;
        n->bwd = n;
    } else {            //already inserted
        node_type* o = *ans.first;  //get pointer to already inserted node
        n->bwd = o->bwd;            //fix up links so as to add new node
        n->fwd = o;                 //to end of list
        o->bwd->fwd = n;
        o->bwd = n;
    }
    mSize++;
    return iterator( this, ans.first, n );
}

/* ------------------------------------------------------------------
 * insert( iterator hint, value_type const & )
 * Insert as close to as before hint as possible. In the spirit of
 * N1780 (Comments on LWG issue 233, Howard E. Hinnant, 23/04/2005)
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::iterator
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::insert(
    iterator hint, value_type const & v )
{
    //!!!!I'm not happy with this function and it needs redesigning when I
    //have time...!!!

    //To insert x at p:
    //   if p == end || x <= *p
    //      if p == begin || x >= *(p-1)
    //         insert x before p
    //      else
    //         insert x before upper_bound(x)
    //   else
    //      insert x before lower_bound(x)

    iterator pos;
    if( mSize == 0 ) {
        //cout<<"pos = end\n";
        pos = end();
    } else {
        if( hint == end() || !cmp( keyGetter( *hint ), keyGetter( v ) ) ) {
            // !(hint < v)  ==  v <= hint
            iterator b4hint = hint; 
            if( hint == begin() || !cmp( keyGetter( v ), keyGetter( *(--b4hint) ) ) ) {
                // !(v < hint)  ==  v >= hint
                //insert before hint
                //cout<<"pos = hint\n";
                pos = hint;
            } else {
                //insert before upper_bound
                //cout<<"pos = upper\n";
                pos = upper_bound( keyGetter(v) );
            }
        } else {
            //insert before lower_bound
            //cout<<"pos = lower "<<keyGetter( *hint )<<"\n";
            pos = lower_bound( keyGetter(v) );
        }
    }
    node_type* n;
    pair< tree_type::iterator, bool> ans;
    n = mem.allocate( 1 );
    try {
        mem.construct( n, node_type(v) );
    } catch( ... ) {
        mem.deallocate( n, 1 );
        throw;
    }
    try {
        //insert into tree. to do: rewrite rbtree hint insert so it doesn't
        //need to recheck the hint pos
        ans = mTree.insert( pos.tit, n );
    } catch( ... ) {
        mem.destroy( n );
        mem.deallocate( n, 1 );
        throw;
    }
    //insert node
    if( ans.second ) {
        //only node in list
        //cout<<"only node in list\n";
        n->fwd = n;
        n->bwd = n;
    } else {
        if( pos == end() || cmp( keyGetter( v ), keyGetter( *pos ) ) ) {
            //insert at end of previous list
            //cout<<"insert at end\n";
            --pos;
            n->bwd = pos.self;
            n->fwd = pos.self->fwd;
            pos.self->fwd->bwd = n;
            pos.self->fwd = n;
        } else {
            //cout<<"insert before hint\n";
            //insert in list before hint
            if( *(pos.tit) == pos.self ) *(pos.tit) = n;
            n->bwd = pos.self->bwd;
            n->fwd = pos.self;
            pos.self->bwd->fwd = n;
            pos.self->bwd = n;
        }
    }
    ++mSize;
    return( iterator(this, ans.first, n) );
}

/* ------------------------------------------------------------------
 * dtor
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::~MultiListRBTree( )
{
    clear();
}

/* ------------------------------------------------------------------
 * clear()
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
void MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::clear( )
{
    for( tree_type::iterator i = mTree.begin(); i != mTree.end(); ++i ) {
        node_type* n = *i;
        node_type* delme;
        node_type* end = n;
        do {
            delme = n;
            n = n->fwd;
            mem.destroy( delme );
            mem.deallocate( delme, 1 );
        } while( n != end );
    }
    mTree.clear();
    mSize = 0;
}

/* ------------------------------------------------------------------
 * _Sane()
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
bool MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::_Sane( )
{
    if( !mTree._Sane() ) return false;
    //do more tests here
    return true;
}

/* ------------------------------------------------------------------
 * find()
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::iterator
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::find(
    key_type const & k )
{
    return iterator( this, mTree.find( k ) );
}

/* ------------------------------------------------------------------
 * count( key_type )
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::size_type
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::count(
    key_type const & k )
{
    tree_type::iterator tit = mTree.find( k );
    if( tit == mTree.end() ) return 0;
    node_type* start = *tit;
    node_type* n = start;
    size_type c = 0;
    do {
        n = n->fwd;
        ++c;
    } while( n != start );
    
    return( c );
}

/* ------------------------------------------------------------------
 * erase( iterator )
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
void MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::erase(
    iterator it )
{
    node_type* n = it.self;
    if( n == n->fwd ) {           //if only element in list 
        mTree.erase( it.tit );
    } else if( *(it.tit) == n ) { //if master element in list & >1 element
        n->bwd->fwd = n->fwd;     //relink to remove n
        n->fwd->bwd = n->bwd;
        *(it.tit) = n->fwd;       //set tree to hold new master element
    } else {                      //if not master element & >1 element
        n->bwd->fwd = n->fwd;     //relink to remove n
        n->fwd->bwd = n->bwd;
    }
    mem.destroy( n );
    mem.deallocate( n, 1 );
    --mSize;
}

/* ------------------------------------------------------------------
 * erase( key_type )
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::size_type
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::erase(
    key_type const & k )
{
    iterator it = find( k );
    node_type* n = it.self;
    node_type* delme;
    node_type* end = n;
    size_type c = 0;
    do {
        delme = n;
        n = n->fwd;
        mem.destroy( delme );
        mem.deallocate( delme, 1 );
        ++c;
        --mSize;
    } while( n != end );
    mTree.erase( it.tit );
    return( c );
}

/* ------------------------------------------------------------------
 * lower_bound( key_type )
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::iterator
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::lower_bound(
    key_type const & k )
{
    tree_type::iterator tit = mTree.lower_bound( k );
    node_type* n = (tit == mTree.end()) ? 0 : *tit;
    return( iterator( this, tit, n ) );
}

/* ------------------------------------------------------------------
 * lower_bound( key_type ) const
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::const_iterator
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::lower_bound(
    key_type const & k ) const
{
    return( const_cast<MultiListRBTree*>(this)->lower_bound( k ) );
}

/* ------------------------------------------------------------------
 * upper_bound( key_type )
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::iterator
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::upper_bound(
    key_type const & k )
{
    tree_type::iterator tit = mTree.upper_bound( k );
    node_type* n = (tit == mTree.end()) ? 0 : *tit;
    return( iterator( this, tit, n ) );
}

/* ------------------------------------------------------------------
 * upper_bound( key_type ) const
 */
template< class Key, class Compare, class Allocator, class ValueWrapper >
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::const_iterator
MultiListRBTree< Key, Compare, Allocator, ValueWrapper >::upper_bound(
    key_type const & k ) const
{
    return( const_cast<MultiListRBTree*>(this)->upper_bound( k ) );
}


} // namespace _ow
} // namespace std

#endif