mstl_red_black_tree.hpp

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

/*
The young Library
Copyright (c) 2005 by 杨桓

Permission to use, copy, modify, distribute and sell this software for any
purpose is hereby granted without fee, provided that the above copyright
notice appear in all copies and that both that copyright notice and this
permission notice appear in supporting documentation.
The author make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_RED_BLACK_TREE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_RED_BLACK_TREE_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "../mstl_allocator.hpp"
#include "../mstl_construct.hpp"
#include "../mstl_pair.hpp"
#include "../algorithm/mstl_algorithm_base.hpp"
#include "mstl_red_black_tree_base.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename T, typename Ref, typename Ptr, typename Key,
          typename ExtractKey, typename KeyCompare, typename Alloc >
class rb_tree_iterator;

template< typename Key, typename Value, typename ExtractKey,
          typename KeyCompare, typename Allocator >
class rb_tree;

template< typename T, typename Key, typename ExtractKey, typename KeyCompare,
          typename Alloc >
inline rb_tree_iterator<T, T&, T*, Key, ExtractKey, KeyCompare, Alloc>
const_iter_cast( const rb_tree_iterator<T, const T&, const T*, Key,
                           ExtractKey, KeyCompare, Alloc>& citer );



template< typename T, typename Ref, typename Ptr, typename Key,
          typename ExtractKey, typename KeyCompare, typename Alloc >
class rb_tree_iterator
{
public:
    typedef  bidirectional_iterator_tag  iterator_category;
    typedef  def_size_t                  size_type;
    typedef  def_ptrdiff_t               difference_type;
    typedef  T                           value_type;
    typedef  Ref                         reference;
    typedef  Ptr                         pointer;

    typedef  rb_tree_iterator<T, Ref, Ptr, Key, ExtractKey,
                              KeyCompare, Alloc>  self;
    typedef  rb_tree_iterator<T, T&, T*, Key, ExtractKey,
                              KeyCompare, Alloc>  iterator;
    typedef  rb_tree_iterator<T, const T&, const T*, Key, ExtractKey,
                              KeyCompare, Alloc>  const_iterator;

private:
    typedef  bs_tree_node_base*  bs_ptr;
    typedef  rb_tree_node_base*  base_ptr;
    typedef  rb_tree_node<T>*    node_ptr;

    typedef  typename primal_type<Ref>::contrary_const_ref  Ref_t;
    typedef  typename primal_type<Ptr>::contrary_const_ptr  Ptr_t;

    friend class rb_tree<Key, T, ExtractKey, KeyCompare, Alloc>;
    friend class rb_tree_iterator<T, Ref_t, Ptr_t, Key, ExtractKey,
                                  KeyCompare, Alloc>;
    friend iterator const_iter_cast <> ( const const_iterator& );


    base_ptr node;

public:
    rb_tree_iterator() : node(NULL_POINTER)  {}
    rb_tree_iterator( base_ptr p ) : node(p)  {}
    rb_tree_iterator( node_ptr p ) : node(p)  {}
    rb_tree_iterator( const iterator& x ) : node(x.node)  {}

    self& operator=( def_nullptr_t n )
    {
        if( n == NULL_POINTER )
            node = NULL_POINTER;
        return *this;
    }

    bool operator!() const  {  return !node;  }

    bool operator==( const self& rhs ) const  {  return node == rhs.node;  }
    bool operator!=( const self& rhs ) const  {  return node != rhs.node;  }

    reference operator*() const
        {  return static_cast<node_ptr>( node )->data;  }
    pointer operator->() const
        {  return &( operator*() );  }

    self& operator++()
    {
        if( node->color == red && node->parent->parent == node ) //is header
            node = static_cast<base_ptr>( node->left );
        else
    	    node = static_cast<base_ptr>( bs_tree_iterator_increase(node) );
    	return *this;
    }

    self& operator--()
    {
        if( node->color == red && node->parent->parent == node ) //is header
            node = static_cast<base_ptr>( node->right );
        else
    	    node = static_cast<base_ptr>( bs_tree_iterator_decrease(node) );
    	return *this;
    }

    self operator++(int)  {  self old = *this;  ++( *this );  return old;  }
    self operator--(int)  {  self old = *this;  --( *this );  return old;  }
};  //end iterator



template< typename T, typename Key, typename ExtractKey, typename KeyCompare,
          typename Alloc >
inline rb_tree_iterator<T, T&, T*, Key, ExtractKey, KeyCompare, Alloc>
const_iter_cast( const rb_tree_iterator<T, const T&, const T*, Key,
                           ExtractKey, KeyCompare, Alloc>& citer )
{
    return rb_tree_iterator<T, T&, T*, Key, ExtractKey,
                            KeyCompare, Alloc>( citer.node );
}

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

template< typename Key, typename Value, typename ExtractKey, typename KeyCompare,
          typename Allocator = allocator< rb_tree_node<Value> > >
class rb_tree
{
public:
    typedef  rb_tree<Key, Value, ExtractKey, KeyCompare, Allocator>  self;

    typedef  rb_tree_color  color_type;
    typedef  Key            key_type;
    typedef  ExtractKey     get_key;
    typedef  KeyCompare     key_compare;
    typedef  Allocator      allocator_type;

    typedef  Value              value_type;
    typedef  value_type&        reference;
    typedef  const value_type&  const_reference;
    typedef  value_type*        pointer;
    typedef  const value_type*  const_pointer;
    typedef  def_size_t         size_type;
    typedef  def_ptrdiff_t      difference_type;

    typedef  rb_tree_iterator<Value, Value&, Value*, Key, ExtractKey,
                              KeyCompare, Allocator>  iterator;
    typedef  rb_tree_iterator<Value, const Value&, const Value*, Key, ExtractKey,
                              KeyCompare, Allocator>  const_iterator;

    typedef  Reverse_Iterator<iterator>            reverse_iterator;
    typedef  Reverse_Iterator<const_iterator>      const_reverse_iterator;

    typedef  pair<iterator, iterator>              pair_iterator;
    typedef  pair<const_iterator, const_iterator>  pair_const_iterator;
    typedef  pair<iterator, bool>                  pair_iterator_bool;

protected:
    typedef  bs_tree_node_base    bs_tree_node_type;
    typedef  rb_tree_node_base    base_node_type;
    typedef  rb_tree_node<Value>  rb_tree_node_type;
    typedef  bs_tree_node_type*   bs_tree_ptr;
    typedef  base_node_type*      base_ptr;
    typedef  rb_tree_node_type*   node_ptr;
    typedef  const base_node_type*     const_base_ptr;
    typedef  const rb_tree_node_type*  const_node_ptr;

    size_type       m_node_count;
    key_compare     m_comp;
    mutable base_node_type  m_header;
    allocator_type  m_alloc;

public:
    explicit rb_tree( const key_compare& compare = key_compare() )
    : m_node_count(0), m_comp(compare)
    {
        init_header( m_header );
    }

    rb_tree( const self& rhs );

    self& operator=( const self& rhs );

    ~rb_tree()
    {
        if( m_node_count > 0 )
            destroy_tree( static_cast<node_ptr>(m_header.parent) );
    }

    key_compare key_comp() const  {  return m_comp;  }
    size_type size() const        {  return m_node_count;  }
    bool empty() const            {  return ( m_node_count == 0 );  }
    size_type max_size() const    {  return size_t_max;  }

    iterator begin()              {  return leftmost();  }
    iterator end()                {  return &m_header;  }
    const_iterator begin() const  {  return leftmost();  }
    const_iterator end() const    {  return &m_header;  }

    reverse_iterator rbegin()              {  return end();  }
    reverse_iterator rend()                {  return begin();  }
    const_reverse_iterator rbegin() const  {  return end();  }
    const_reverse_iterator rend() const    {  return begin();  }

    value_type& front()              {  return *begin();  }
    value_type& back()               {  return *(--end());  }
    const value_type& front() const  {  return *begin();  }
    const value_type& back() const   {  return *(--end());  }

    pair_iterator_bool insert_unique( const value_type& v );
    iterator insert_unique( iterator position, const value_type& v );
    template< typename InputIterator >
    void insert_unique( InputIterator first, InputIterator last );

    iterator insert_equal( const value_type& v );
    iterator insert_equal( iterator position, const value_type& v );
    template< typename InputIterator >
    void insert_equal( InputIterator first, InputIterator last );

    iterator lower_bound( const key_type& k )
        {  return iterator( lower_bound_node(k) );  }
    const_iterator lower_bound( const key_type& k ) const
        {  return const_iterator( lower_bound_node(k) );  }

    iterator upper_bound( const key_type& k )
        {  return iterator( upper_bound_node(k) );  }
    const_iterator upper_bound( const key_type& k ) const
        {  return const_iterator( upper_bound_node(k) );  }

    pair_iterator equal_range( const key_type& k )
        {  return pair_iterator( lower_bound(k), upper_bound(k) );  }
    pair_const_iterator equal_range( const key_type& k ) const
        {  return pair_const_iterator( lower_bound(k), upper_bound(k) );  }

    void erase( iterator position );
    size_type erase( const key_type& k );
    void erase( iterator first, iterator last );
    void erase( const key_type* first, const key_type* last );

    void modify_key_equal( const key_type& k, const key_type& new_key );
    void modify_key_equal( iterator position, const key_type& new_key )
    {
        if( position != end() )
            modify_key_aux( position, new_key );
    }
    iterator modify_key_unique( const key_type& k, const key_type& new_key )
    {
        iterator result = find( k );
        if( result != end() && find(new_key) == end() )
            modify_key_aux( result, new_key );
        return result;
    }
    bool modify_key_unique( iterator position, const key_type& new_key )
    {
        if( position == end() || find(new_key) != end() )
            return false;
        modify_key_aux( position, new_key );
        return true;
    }

    iterator find( const key_type& k )
    {
        base_ptr x = find_node( k );
        if( x == &m_header || m_comp( k, _key(x) ) )
            return end();
        else
            return x;
    }
    const_iterator find( const key_type& k ) const
    {
        base_ptr x = find_node( k );
        if( x == &m_header || m_comp( k, _key(x) ) )
            return end();
        else
            return x;
    }

    bool verify_rb_tree() const;
    void swap( self& rhs );

    size_type node_height( iterator position ) const
    {
        return bs_tree_node_height( position.node, root() );
    }

    size_type count( const key_type& k ) const
    {
    	pair_const_iterator pair_c_iter = equal_range( k );
    	return distance( pair_c_iter.first, pair_c_iter.second );
    }

    void clear()
    {
        if( m_node_count > 0 )
        {
            destroy_tree( root() );
            m_header.parent = NULL_POINTER;
            m_header.left = &m_header;
            m_header.right = &m_header;
            m_node_count = 0;
        }
    }