_rbtree.mh

来自「开放源码的编译器open watcom 1.6.0版的源代码」· MH 代码 · 共 1,712 行 · 第 1/5 页

///////////////////////////////////////////////////////////////////////////
// FILE: _rbtree (std::_OW::RedBlackTree definition)
//
:keep CPP_HDR
:include crwatcnt.sp
//
// 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
:include readonly.sp

#ifndef __cplusplus
#error The header _rbtree.h requires C++
#endif

//#line 22 "_rbtree.mh"

#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;}
    //static Key const& getKey(value_type const & v){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;}
    //static Key const& getKey(value_type const & v){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); }
    };
    Allocator::rebind< Node >::other mem;       // !!! moved up here until compiler bug fixed !!!
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 const & i ) : iterator_base( i ) {}
        iterator() : iterator_base() {}
        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 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 & );
    template< class InputIterator > // compiler only understands inline syntax
    void insert( InputIterator f, InputIterator l )
        {   // presume data sorted; use last insert point as hint
            iterator hint;
            if( f != l ) hint = insert( *f ).first;
            for( ++f ; f != l ; ++f ) hint = insert( hint, *f ).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;
    
    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;


// ---=== !!MOVE ME OUTTA HERE!! ===---
/* ------------------------------------------------------------------
 * 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 Allocator, class ValueWrapper>
std::pair< 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);
}

public:
/* ------------------------------------------------------------------
 * !!MOVE ME OUTSIDE CLASS!!
 * 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 Allocator, class ValueWrapper>
std::pair< 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;
}
/* ------------------------------------------------------------------
 * !!MOVE ME OUTSIDE CLASS!!
 * 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 Allocator, class ValueWrapper>
std::pair< 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;