mstl_red_black_tree.hpp

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

    	    result = insert_node( position.node, position.node, v );
    	else
    	    result = insert_unique( v ).first;
    }
    else if( position == end() )
    {
    	if( size() > 0 && m_comp( _key(rightmost()), get_key()(v) ) )
    	    result = insert_node( NULL_POINTER, rightmost(), v );
    	else
    	    result = insert_unique( v ).first;
    }
    else
    {
    	iterator before = position;
    	--before;
    	if( m_comp( _key(before.node), get_key()(v) )
    	    && m_comp( get_key()(v), _key(position.node) ) )  // b < v < p
    	{
    	    if( !(position.node->right) )
    	        result = insert_node( NULL_POINTER, before.node, v );
    	    else
    	        result = insert_node( position.node, position.node, v );
    	}
    	else
    	    result = insert_unique( v ).first;
    }

    return result;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
template< typename InputIterator >
void rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
insert_unique( InputIterator first, InputIterator last )
{
    while( first != last )
        insert_unique( *first++ );
}
//-----------------------------------------------------------------------------

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_equal( const value_type& v )
{
    base_ptr y = &m_header;
    node_ptr current = root();

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

    return insert_node( current, y, v );
}
//-----------------------------------------------------------------------------

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_equal( iterator position, const value_type& v )
{
    iterator result;

    if( position == begin() )
    {
    	if( size() > 0 && m_comp( get_key()(v), _key(position.node) ) )  //v < p
    	    result = insert_node( position.node, position.node, v );
    	else
    	    result = insert_equal( v );
    }
    else if( position == end() )
    {
    	if( size() > 0 && !m_comp( get_key()(v), _key(rightmost()) ) )  //v >= rightmost()
    	    result = insert_node( NULL_POINTER, rightmost(), v );
    	else
    	    result = insert_equal( v );
    }
    else
    {
    	iterator before = position;
    	--before;
    	if( !m_comp( get_key()(v), _key(before.node) )
    	    && !m_comp( _key(position.node), get_key()(v) ) )  // p >= v >= b
    	{
    	    if( !(position.node->right) )
    	        result = insert_node( NULL_POINTER, before.node, v );
    	    else
    	        result = insert_node( position.node, position.node, v );
    	}
    	else
    	    result = insert_equal( v );
    }

    return result;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
template< typename InputIterator >
void rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
insert_equal( InputIterator first, InputIterator last )
{
    while( first != last )
        insert_equal( *first++ );
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
inline void rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
erase( iterator position )
{
    if( position != end() )
    {
        rb_tree_erase_rebalance( position.node, m_header );
        destroy_node( static_cast<node_ptr>( position.node ) );
        --m_node_count;
    }
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
inline
typename rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::size_type
rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
erase( const key_type& k )
{
    pair_iterator pair_iter = equal_range(k);
    size_type n = distance( pair_iter.first, pair_iter.second );
    erase( pair_iter.first, pair_iter.second );
    return n;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
void rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
erase( iterator first, iterator last )
{
    if( first == begin() && last == end() )
        clear();
    else
    {
        while( first != last )
    	    erase( first++ );
    }
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
void rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
erase( const key_type* first, const key_type* last )
{
    while( first != last )
        erase( *first++ );
}
//-----------------------------------------------------------------------------

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_node( base_ptr child, base_ptr parent, const value_type& v )
{
    node_ptr p = create_node( v );

    // v < parent
    if( parent == &m_header || child || m_comp( get_key()(v), _key(parent) ) )
    {
        parent->left = p;
        if( parent == &m_header )
        {
            m_header.parent = p;
            m_header.right = p;
        }
        else if( parent == leftmost() )
            m_header.left = p;
    }
    else  // v >= parent
    {
        parent->right = p;
        if( rightmost() == parent )
            m_header.right = p;
    }
    p->parent = parent;
    p->left = NULL_POINTER;
    p->right = NULL_POINTER;

    rb_tree_insert_rebalance( p, m_header );
    ++m_node_count;
    return iterator( p );
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
void rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
modify_key_equal( const key_type& k, const key_type& new_key )
{
    pair_iterator pair_iter = equal_range( k );
    iterator first = pair_iter.first;
    iterator last = pair_iter.second;

    while( first != last )
    {
        modify_key_equal( first, new_key );
        ++first;
    }
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
void rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
modify_key_aux( iterator position, const key_type& new_key )
{
    base_ptr x = position.node;
    rb_tree_erase_rebalance( x, m_header );

    try
    {
        const_cast<key_type&>( get_key()(_value(x)) ) = new_key;
    }
    catch(...)
    {
        destroy_node( static_cast<node_ptr>( x ) );
        --m_node_count;
        throw;
    }

    //寻找节点重新插入的位置
    base_ptr parent = &m_header;
    node_ptr current = root();
    while( current )
    {
        parent = current;
        current = m_comp( new_key, _key(current) )
                  ? _left( current ) : _right( current );
    }

    if( m_comp( new_key, _key(parent) ) )
    {
        parent->left = x;
        if( leftmost() == static_cast<node_ptr>( parent ) )
            m_header.left = x;
    }
    else
    {
        parent->right = x;
        if( rightmost() == static_cast<node_ptr>( parent ) )
            m_header.right = x;
    }
    x->parent = parent;
    x->left = NULL_POINTER;
    x->right = NULL_POINTER;

    rb_tree_insert_rebalance( x, m_header );
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
bool rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>::
verify_rb_tree() const
{
    if( m_node_count == 0 || begin() == end() )
        return ( m_node_count == 0 && begin() == end()
    	         && m_header.left == &m_header && m_header.right == &m_header );

    def_size_t black_num = black_count( leftmost(), root() );

    const_iterator first = begin();
    const_iterator last = end();
    for( ; first != last; ++first )
    {
    	node_ptr current = static_cast<node_ptr>( first.node );
    	node_ptr lchild = _left( current );
    	node_ptr rchild = _right( current );

        if( current->color == red )
        {
            if( lchild && (lchild->color == red) )
                return false;
            if( rchild && (rchild->color == red) )
                return false;
        }

        if( lchild && m_comp( _key(current), _key(lchild) ) )
            return false;
        if( rchild && m_comp( _key(rchild), _key(current) ) )
            return false;

        if( !lchild && !rchild && (black_count(current, root()) != black_num) )
            return false;
    }

    if( leftmost() != min_element(root())
        || rightmost() != max_element(root()) )
        return false;

    return true;
}

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

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
inline
void swap( rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>& lhs,
           rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>& rhs )
{
    lhs.swap( rhs );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------