mstl_red_black_tree.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

protected:
    void destroy_tree( node_ptr x );
    node_ptr copy_tree( node_ptr source, node_ptr destination );
    iterator insert_node( base_ptr child, base_ptr parent, const value_type& v );
    void modify_key_aux( iterator position, const key_type& new_key );
    base_ptr find_node( const key_type& k ) const;
    base_ptr lower_bound_node( const key_type& k ) const;
    base_ptr upper_bound_node( const key_type& k ) const;

    void init_header( base_node_type& x )
    {
        x.parent = NULL_POINTER;
        x.left = &x;
        x.right = &x;
        x.color = red;
    }

    void rb_tree_swap( self& rhs )
    {
        data_swap( m_node_count, rhs.m_node_count );
        data_swap( m_comp, rhs.m_comp );
        data_swap( m_header.parent, rhs.m_header.parent );
        data_swap( m_header.left, rhs.m_header.left );
        data_swap( m_header.right, rhs.m_header.right );
        data_swap( m_alloc, rhs.m_alloc );
    }

    node_ptr create_node( const value_type& x )
    {
       node_ptr ptr = m_alloc.allocate( 1 );
       try
       {
       	   construct( &(ptr->data),x );
       }
       catch(...)
       {
       	   m_alloc.deallocate( ptr, 1 );
       	   throw;
       }
       return ptr;
    }

    node_ptr copy_node( node_ptr x )
    {
    	node_ptr ptr = create_node( x->data );
    	ptr->parent = NULL_POINTER;
    	ptr->left = NULL_POINTER;
    	ptr->right = NULL_POINTER;
    	ptr->color = x->color;
    	return ptr;
    }

    void destroy_node( node_ptr ptr )
    {
        destroy( &(ptr->data) );
        m_alloc.deallocate( ptr, 1 );
    }

    node_ptr root() const
        {  return  static_cast<node_ptr>( m_header.parent );  }
    node_ptr leftmost() const
        {  return  static_cast<node_ptr>( m_header.left );  }
    node_ptr rightmost() const
        {  return  static_cast<node_ptr>( m_header.right );  }

    static node_ptr min_node( node_ptr x )
        {  return  static_cast<node_ptr>( min_element(x) );  }
    static node_ptr max_node( node_ptr x )
        {  return  static_cast<node_ptr>( max_element(x) );  }

    static node_ptr _parent( node_ptr x )
        {  return  static_cast<node_ptr>( x->parent );  }
    static node_ptr _left( node_ptr x )
        {  return  static_cast<node_ptr>( x->left );  }
    static node_ptr _right( node_ptr x )
        {  return  static_cast<node_ptr>( x->right );  }
    static value_type& _value( node_ptr x )
        {  return  x->data;  }
    static const key_type& _key( node_ptr x )
        {  return  get_key()( _value(x) );  }

    static node_ptr _parent( base_ptr x )
        {  return  static_cast<node_ptr>( x->parent );  }
    static node_ptr _left( base_ptr x )
        {  return  static_cast<node_ptr>( x->left );  }
    static node_ptr _right( base_ptr x )
        {  return  static_cast<node_ptr>( x->right );  }
    static value_type& _value( base_ptr x )
        {  return  static_cast<node_ptr>( x )->data;  }
    static const key_type& _key( base_ptr x )
        {  return  get_key()( _value(x) );  }

};  //end class

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
void rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::swap( self& rhs )
{
    if( this != &rhs )
    {
        bool x = empty();
        bool y = rhs.empty();

        if( x )
        {
       	    if( y )
       	        return;
            rb_tree_swap( rhs );
            m_header.parent->parent = &m_header;  //将原rhs.root->parent指向header
            init_header( rhs.m_header );  //将rhs.header置空
        }
    	else
    	{
            rb_tree_swap( rhs );
            rhs.m_header.parent->parent = &(rhs.m_header);  //将原root指向rhs.m_header
            if( y )
                init_header( m_header );  //将header置空
            else
                m_header.parent->parent = &m_header;  //将原rhs.root->parent指向header
        }
    }
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
rb_tree( const self& rhs) : m_node_count(0), m_comp(rhs.m_comp)
{
    init_header( m_header );
    if( rhs.m_node_count > 0 )
    {
        m_header.parent = copy_tree( rhs.root(),
                                     static_cast<node_ptr>(&m_header) );
        m_header.left = min_node( root() );
        m_header.right = max_node( root() );
    }
    m_node_count = rhs.m_node_count;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>&
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
operator=( const self& rhs)
{
    if( this == &rhs )
        return *this;

    if( rhs.m_node_count > 0 )
    {
        self temp( rhs );
        swap( temp );
    }
    else
    {
        clear();
        m_comp = rhs.m_comp;
    }

    return *this;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
typename rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::node_ptr
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
copy_tree( node_ptr source, node_ptr destination )
{
    node_ptr top = copy_node( source );
    top->parent = destination;

    try
    {
        if( source->right )
            top->right = copy_tree( _right(source), top );
        destination = top;
        source = _left( source );

        while( source )
        {
            node_ptr temp = copy_node( source );
            destination->left = temp;
            temp->parent = destination;
            if( source->right )
    	        temp->right = copy_tree( _right(source), temp );
    	    destination = temp;
    	    source = _left( source );
        }
    }
    catch(...)
    {
        destroy_tree( top );
    }

    return top;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
void rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
destroy_tree( node_ptr x )
{
    while( x )
    {
    	destroy_tree( _right(x) );
    	node_ptr y = _left( x );
    	destroy_node( x );
    	x = y;
    }
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
typename rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::base_ptr
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
find_node( const key_type& k ) const
{
    base_ptr result = &m_header;
    node_ptr current = root();

    while( current )
    {
        if( !m_comp( _key(current), k ) )
        {
            result = current;
            current = _left( current );
        }
        else
            current = _right( current );
    }

    return ( result == &m_header || m_comp(k, _key(result)) ? &m_header : result );
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
typename rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::base_ptr
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
lower_bound_node( const key_type& k ) const
{
    base_ptr x = &m_header;
    node_ptr current = root();

    while( current )
    {
        if( !m_comp( _key(current), k ) )  // current >= k
        {
            x = current;
            current = _left( current );
        }
        else
            current = _right( current );
    }

    return x;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
typename rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::base_ptr
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
upper_bound_node( const key_type& k ) const
{
    base_ptr x = &m_header;
    node_ptr current = root();

    while( current )
    {
        if( m_comp( k, _key(current) ) )  // k < current
        {
            x = current;
            current = _left( current );
        }
        else
            current = _right( current );
    }

    return x;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
typename
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::pair_iterator_bool
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
insert_unique( const value_type& v )
{
    base_ptr y = &m_header;
    node_ptr current = root();
    bool bcompare = true;

    while( current )
    {
    	y = current;
    	bcompare = m_comp( get_key()(v), _key(current) );
    	current = bcompare ? _left( current ) : _right( current );
    }

    iterator result( y );
    if( bcompare )  //最后一次比较结果是: v < current
    {
    	if( result == begin() )
    	    return  pair_iterator_bool( insert_node(current, y, v), true );
    	else
    	    --result;
    }
    if( m_comp( _key(result.node), get_key()(v) ) )  // result < v
        return  pair_iterator_bool( insert_node(current, y, v), true );

    return  pair_iterator_bool( result, false );
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
typename rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::iterator
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
insert_unique( iterator position, const value_type& v )
{
    iterator result;

    if( position == begin() )
    {
    	if( size() > 0 && m_comp( get_key()(v), _key(position.node) ) )