文件位置：young/tree/y_binary_search_tree_base.hpp
/*
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.
*/
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_BINARY_SEARCH_TREE_BASE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_BINARY_SEARCH_TREE_BASE_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "../y_define.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_YOUNG_LIBRARY_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
struct bs_tree_node_base
{
bs_tree_node_base* parent;
bs_tree_node_base* left;
bs_tree_node_base* right;
};
typedef bs_tree_node_base* bs_tree_node_base_ptr;
inline bs_tree_node_base* min_element( bs_tree_node_base* p )
{
if( p )
{
while( p->left )
p = p->left;
}
return p;
}
inline bs_tree_node_base* max_element( bs_tree_node_base* p )
{
if( p )
{
while( p->right )
p = p->right;
}
return p;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
inline
void bs_tree_iterator_increment( bs_tree_node_base_ptr& node )
{
if( node->right )
{
node = node->right;
while( node->left )
node = node->left;
}
else
{
bs_tree_node_base* temp = node->parent;
while( node == temp->right )
{
node = temp;
temp = temp->parent;
}
if( node->right != temp )
node = temp;
}
}
inline
void bs_tree_iterator_decrement( bs_tree_node_base_ptr& node )
{
bs_tree_node_base* temp;
if( node->left )
{
temp = node->left;
while( temp->right )
temp = temp->right;
node = temp;
}
else
{
temp = node->parent;
while( node == temp->left )
{
node = temp;
temp = temp->parent;
}
node = temp;
}
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
inline
def_size_t bs_tree_node_height( const bs_tree_node_base* node,
const bs_tree_node_base* root )
{
if( !node || !root )
return 0;
def_size_t height = 0;
while( node != root )
{
node = node->parent;
++height;
}
return height;
}
inline
void bs_tree_rotate_left( bs_tree_node_base_ptr position,
bs_tree_node_base_ptr& root )
{
bs_tree_node_base_ptr rchild = position->right;
position->right = rchild->left;
if( rchild->left )
rchild->left->parent = position;
rchild->parent = position->parent;
if( position == root )
root = rchild;
else if( position == position->parent->left )
position->parent->left = rchild;
else
position->parent->right = rchild;
rchild->left = position;
position->parent = rchild;
}
inline
void bs_tree_rotate_right( bs_tree_node_base_ptr position,
bs_tree_node_base_ptr& root )
{
bs_tree_node_base_ptr lchild = position->left;
position->left = lchild->right;
if( lchild->right )
lchild->right->parent = position;
lchild->parent = position->parent;
if( position == root )
root = lchild;
else if( position == position->parent->right )
position->parent->right = lchild;
else
position->parent->left = lchild;
lchild->right = position;
position->parent = lchild;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
inline bs_tree_node_base_ptr
bs_tree_erase_adjust( bs_tree_node_base_ptr erase_node,
bs_tree_node_base_ptr& successor,
bs_tree_node_base_ptr& succ_parent,
bs_tree_node_base_ptr& root,
bs_tree_node_base_ptr& leftmost,
bs_tree_node_base_ptr& rightmost )
{
bs_tree_node_base_ptr position = erase_node; //position将指向新节点
successor = NULL_POINTER;
succ_parent = NULL_POINTER;
//查找
if( !(position->left) ) //position有右子树或者没有子树
successor = position->right; //successor可能为空
else
{
if( !(position->right) ) //只有左子树
successor = position->left;
else //有左、右子树
{
position = position->right;
while( position->left )
position = position->left;
successor = position->right;
}
}
//替换
if( position != erase_node )
{
erase_node->left->parent = position;
position->left = erase_node->left;
if( position != erase_node->right )
{
if( successor )
successor->parent = position->parent;
succ_parent = position->parent;
position->parent->left = successor;
position->right = erase_node->right;
erase_node->right->parent = position;
}
else
succ_parent = position;
if( root == erase_node )
root = position;
if( erase_node->parent->left == erase_node )
erase_node->parent->left = position;
else
erase_node->parent->right = position;
position->parent = erase_node->parent;
}
else //position == erase_node
{
succ_parent = position->parent;
if( successor )
successor->parent = succ_parent;
if( root == erase_node )
root = successor;
else if( erase_node->parent->left == erase_node )
erase_node->parent->left = successor;
else
erase_node->parent->right = successor;
if( leftmost == erase_node )
{
if( !(erase_node->right) ) //leftmost左子树必为空
leftmost = erase_node->parent;
else
leftmost = min_element( successor );
}
if( rightmost == erase_node )
{
if( !(erase_node->left) ) //rightmost右子树必为空
rightmost = erase_node->parent;
else
rightmost = max_element( successor );
}
} //end else
return position;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_YOUNG_LIBRARY_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
文件位置：young/tree/y_red_black_tree.hpp
/*
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.
*/
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_RED_BLACK_TREE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_RED_BLACK_TREE_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "../y_allocator.hpp"
#include "../y_construct.hpp"
#include "../y_pair.hpp"
#include "../algorithm/y_algorithm_base.hpp"
#include "y_bs_tree_base.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_YOUNG_LIBRARY_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
typedef bool rb_tree_color;
const rb_tree_color red = false;
const rb_tree_color black = true;
struct rb_tree_node_base : public bs_tree_node_base
{
rb_tree_color color;
};
typedef rb_tree_node_base* rb_tree_node_base_ptr;
template< typename Value >
struct rb_tree_node : public rb_tree_node_base
{
Value data;
};
def_size_t black_count( const rb_tree_node_base* node,
const rb_tree_node_base* root )
{
if( !node )
return 0;
def_size_t count = ( node->color == black ) ? 1 : 0;
if( node == root )
return count;
else
return ( count
+ black_count( static_cast<rb_tree_node_base*>( node->parent ),
root ) );
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
inline rb_tree_node_base_ptr& parent( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->parent );
}
inline rb_tree_node_base_ptr& left( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->left );
}
inline rb_tree_node_base_ptr& right( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->right );
}
inline rb_tree_color& color( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x )->color;
}
inline rb_tree_node_base_ptr& granddad( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->parent->parent );
}
inline rb_tree_node_base_ptr& parent( rb_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->parent );
}
inline rb_tree_node_base_ptr& left( rb_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->left );
}
inline rb_tree_node_base_ptr& right( rb_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->right );
}
inline rb_tree_color& color( rb_tree_node_base_ptr x )
{
return x->color;
}
inline rb_tree_node_base_ptr& granddad( rb_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->parent->parent );
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void rb_tree_insert_rebalance( rb_tree_node_base_ptr position,
rb_tree_node_base_ptr& root )
{
color( position ) = red;
while( position != root && color( parent(position) ) == red )
{
//position->parent is left child
if( parent( position ) == left( granddad(position) ) )
{
rb_tree_node_base_ptr runcle = right( granddad(position) );
//处理第1种情况:只用更改颜色
if( runcle && color( runcle ) == red )
{
color( runcle ) = black;
color( parent(position) ) = black;
color( granddad(position) ) = red;
position = granddad( position );
}
else //right uncle == 0 or right uncle->color == black
{
if( position == right( parent(position) ) ) //处理第2种情况:
{
position = parent( position );
bs_tree_rotate_left( position,
static_cast<bs_tree_node_base_ptr>(root) );
}
color( parent(position) ) = black; //处理第3种情况:将终止循环
color( granddad(position) ) = red;
bs_tree_rotate_right( position->parent->parent,
static_cast<bs_tree_node_base_ptr>(root) );
}
}
else //position->parent is right child
{
rb_tree_node_base_ptr luncle = left( granddad(position) );
//处理第1种情况:只用更改颜色
if( luncle && color( luncle ) == red )
{
color( luncle ) = black;
color( parent(position) ) = black;
color( granddad(position) ) = red;
position = granddad( position );
}
else //left uncle == 0 or left uncle->color == black
{
if( position == left( parent(position) ) ) //处理第2种情况:
{
position = parent( position );
bs_tree_rotate_right( position,
static_cast<bs_tree_node_base_ptr>(root) );
}
color( parent(position) ) = black; //处理第3种情况:将终止循环
color( granddad(position) ) = red;
bs_tree_rotate_left( position->parent->parent,
static_cast<bs_tree_node_base_ptr>(root) );
}
}
} //end while
color( root ) = black;
}
void rb_tree_erase_rebalance( rb_tree_node_base_ptr erase_node,
rb_tree_node_base_ptr& root,
rb_tree_node_base_ptr& leftmost,
rb_tree_node_base_ptr& rightmost )
{
rb_tree_node_base_ptr successor, succ_parent;
bs_tree_node_base_ptr position;
//调整节点
position = bs_tree_erase_adjust(
static_cast<bs_tree_node_base_ptr>( erase_node ),
static_cast<bs_tree_node_base_ptr>( successor ),
static_cast<bs_tree_node_base_ptr>( succ_parent ),
static_cast<bs_tree_node_base_ptr>( root ),
static_cast<bs_tree_node_base_ptr>( leftmost ),
static_cast<bs_tree_node_base_ptr>( rightmost ) );
//调整颜色
if( position != erase_node )
data_swap( color( position ), color( erase_node ) );
position; //避免编译器提出警告
if( erase_node->color != red )
{
while( ( successor != root )
&& ( !successor || color( successor ) == black ) )
{
//successor is left child
if( successor == left( succ_parent ) )
{
rb_tree_node_base_ptr succ_rbrother = right( succ_parent );
//第1种情况:succ_rbrother->color is red
if( color( succ_rbrother ) == red )
{
color( succ_rbrother ) = black;
color( succ_parent ) = red;
bs_tree_rotate_left( succ_parent,
static_cast<bs_tree_node_base_ptr>(root) );
succ_rbrother = right( succ_parent );
}
//第2种情况: succ_rbrother->children->color are black
if( ( !left( succ_rbrother )
|| left( succ_rbrother )->color == black )
&& ( !right( succ_rbrother )
|| right( succ_rbrother )->color == black ) )
{
color( succ_rbrother ) = red;
successor = succ_parent;
succ_parent = parent( succ_parent );
}
else
{
//第3种情况:succ_rbrother->right->color is black
if( !right( succ_rbrother )
|| right( succ_rbrother )->color == black )
{
left( succ_rbrother )->color = black;
color( succ_rbrother ) = red;
bs_tree_rotate_right( succ_rbrother,
static_cast<bs_tree_node_base_ptr>(root) );
succ_rbrother = right( succ_parent );
}
//第4种情况:succ_rbrother->right->color is red
color( succ_rbrother ) = color( succ_parent );
color( succ_parent ) = black;
right( succ_rbrother )->color = black;
bs_tree_rotate_left( succ_parent,
static_cast<bs_tree_node_base_ptr>(root) );
break;
}
} //end if : successor is left child
//successor is right child
else
{
rb_tree_node_base_ptr succ_lbrother = left( succ_parent );
//第1种情况:succ_lbrother->color is red
if( color( succ_lbrother ) == red )
{
color( succ_lbrother ) = black;
color( succ_parent ) = red;
bs_tree_rotate_right( succ_parent,
static_cast<bs_tree_node_base_ptr>(root) );
succ_lbrother = left( succ_parent );
}
//第2种情况:succ_lbrother->children->color are black
if( ( !right( succ_lbrother )
|| right( succ_lbrother )->color == black )
&& ( !left( succ_lbrother )
|| left( succ_lbrother )->color == black ) )
{
color( succ_lbrother ) = red;
successor = succ_parent;
succ_parent = parent( succ_parent );
}
else
{
//第3种情况:succ_lbrother->left->color is black
if( !left( succ_lbrother )
|| left( succ_lbrother )->color == black )
{
left( succ_lbrother )->color = black;
color( succ_lbrother ) = red;
bs_tree_rotate_left( succ_lbrother,
static_cast<bs_tree_node_base_ptr>(root) );
succ_lbrother = left( succ_parent );
}
//第4种情况:succ_lbrother->left->color is red
color( succ_lbrother ) = color( succ_parent );
color( succ_parent ) = black;
left( succ_lbrother )->color = black;
bs_tree_rotate_right( succ_parent,
static_cast<bs_tree_node_base_ptr>(root) );
break;
}
} //end else : successor is right child
} //end while
if( successor )
color( successor ) = black;
} //end if
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
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 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
bs_tree_iterator_increment( static_cast<bs_ptr>( node ) );
return *this;
}
self& operator--()
{
if( node->color == red && node->parent->parent == node ) //is header
node = static_cast<base_ptr>( node->right );
else
bs_tree_iterator_decrement( static_cast<bs_ptr>( 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;
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( root() );
}
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 uint_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;
}
}
protected:
void destroy_tree( node_ptr x );
node_ptr copy_tree( node_ptr source, node_ptr destination );
iterator insert_node( base_ptr ch, base_ptr pa, 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 color_type& color( node_ptr x )
{ return x->color; }
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) ); }
static color_type& color( base_ptr x )
{ return static_cast<node_ptr>( x )->color; }
}; //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 );
root()->parent = &m_header; //将原rhs.root()->parent指向header
init_header( rhs.m_header ); //将rhs.header置空
}
else
{
rb_tree_swap( rhs );
rhs.root()->parent = &(rhs.m_header); //将原root()指向rhs.m_header
if( y )
init_header( m_header ); //将header置空
else
root()->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 )
{
root() = copy_tree( rhs.root(), static_cast<node_ptr>(&m_header) );
leftmost() = min_node( root() );
rightmost() = 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_header.parent = NULL_POINTER;
m_header.left = &m_header;
m_header.right = &m_header;
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 );
parent( top ) = destination;
try
{
if( source->right )
right( top ) = copy_tree( right(source), top );
destination = top;
source = left( source );
while( source )
{
node_ptr temp = copy_node( source );
left( destination ) = temp;
parent( temp ) = destination;
if( source->right )
right( temp ) = 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 pa = &m_header;
node_ptr current = root();
while( current )
{
if( !m_comp( key(current), k ) )
{
pa = current;
current = left( current );
}
else
current = right( current );
}
return pa;
}
//-----------------------------------------------------------------------------
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) ) )
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,
static_cast<base_ptr>( m_header.parent ),
static_cast<base_ptr>( m_header.left ),
static_cast<base_ptr>( m_header.right ) );
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 ch, base_ptr pa, const value_type& v )
{
node_ptr p = create_node( v );
// v < parent
if( pa == &m_header || ch || m_comp( get_key()(v), key(pa) ) )
{
left( pa ) = p;
if( pa == &m_header )
{
root() = p;
rightmost() = p;
}
else if( pa == leftmost() )
leftmost() = p;
}
else // v >= parent
{
right( pa ) = p;
if( rightmost() == pa )
rightmost() = p;
}
p->parent = pa;
left( p ) = NULL_POINTER;
right( p ) = NULL_POINTER;
rb_tree_insert_rebalance( static_cast<base_ptr>( p ),
static_cast<base_ptr>( m_header.parent ) );
++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.firt;
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,
static_cast<base_ptr>( m_header.parent ),
static_cast<base_ptr>( m_header.left ),
static_cast<base_ptr>( m_header.right ) );
try
{
get_key()( value(x) ) = new_key;
}
catch(...)
{
destroy_node( static_cast<node_ptr>( x ) );
--m_node_count;
throw;
}
//寻找节点重新插入的位置
base_ptr pa = &m_header;
node_ptr current = root();
while( current )
{
pa = current;
current = m_comp( new_key, key(current) )
? left( current ) : right( current );
}
if( m_comp( new_key, key(pa) ) )
{
pa->left = x;
if( leftmost() == static_cast<node_ptr>( pa ) )
leftmost() = static_cast<node_ptr>( x );
}
else
{
pa->right = x;
if( rightmost() == static_cast<node_ptr>( pa ) )
rightmost() = static_cast<node_ptr>( x );
}
x->parent = pa;
x->left = NULL_POINTER;
x->right = NULL_POINTER;
rb_tree_insert_rebalance( x, static_cast<base_ptr>( m_header.parent ) );
}
//-----------------------------------------------------------------------------
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_YOUNG_LIBRARY_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
文件位置：young/tree/old_y_red_black_tree.hpp
这个文件其实是我最初实现的红黑树，后来我改进了一些，就把这个最初的实现文件改了一个名字，大家有兴趣的话可以比较一下两者的不同。
/*
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.
*/
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_OLD_RED_BLACK_TREE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_OLD_RED_BLACK_TREE_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "../y_allocator.hpp"
#include "../y_construct.hpp"
#include "../y_pair.hpp"
#include "../algorithm/y_algorithm_base.hpp"
#include "y_binary_search_tree_base.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_YOUNG_LIBRARY_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
typedef bool rb_tree_color;
const rb_tree_color red = false;
const rb_tree_color black = true;
struct rb_tree_node_base : public bs_tree_node_base
{
rb_tree_color color;
};
typedef rb_tree_node_base* rb_tree_node_base_ptr;
template< typename Value >
struct rb_tree_node : public rb_tree_node_base
{
Value data;
};
def_size_t black_count( const rb_tree_node_base* node,
const rb_tree_node_base* root )
{
if( !node )
return 0;
def_size_t count = ( node->color == black ) ? 1 : 0;
if( node == root )
return count;
else
return ( count + black_count( static_cast<rb_tree_node_base*>(node->parent),
root) );
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
inline rb_tree_node_base_ptr& parent( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->parent );
}
inline rb_tree_node_base_ptr& left( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->left );
}
inline rb_tree_node_base_ptr& right( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->right );
}
inline rb_tree_color& color( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x )->color;
}
inline rb_tree_node_base_ptr& granddad( bs_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->parent->parent );
}
inline rb_tree_node_base_ptr& parent( rb_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->parent );
}
inline rb_tree_node_base_ptr& left( rb_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->left );
}
inline rb_tree_node_base_ptr& right( rb_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->right );
}
inline rb_tree_color& color( rb_tree_node_base_ptr x )
{
return x->color;
}
inline rb_tree_node_base_ptr& granddad( rb_tree_node_base_ptr x )
{
return static_cast<rb_tree_node_base_ptr>( x->parent->parent );
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void rb_tree_insert_rebalance( rb_tree_node_base_ptr position,
rb_tree_node_base_ptr& root )
{
color( position ) = red;
while( position != root && color( parent(position) ) == red )
{
//position->parent is left child
if( parent( position ) == left( granddad(position) ) )
{
rb_tree_node_base_ptr runcle = right( granddad(position) );
//处理第1种情况:只用更改颜色
if( runcle && color( runcle ) == red )
{
color( runcle ) = black;
color( parent(position) ) = black;
color( granddad(position) ) = red;
position = granddad( position );
}
else //right uncle == 0 or right uncle->color == black
{
if( position == right( parent(position) ) ) //处理第2种情况:
{
position = parent( position );
bs_tree_rotate_left( position,
static_cast<bs_tree_node_base_ptr>(root) );
}
color( parent(position) ) = black; //处理第3种情况:将终止循环
color( granddad(position) ) = red;
bs_tree_rotate_right( position->parent->parent,
static_cast<bs_tree_node_base_ptr>(root) );
}
}
else //position->parent is right child
{
rb_tree_node_base_ptr luncle = left( granddad(position) );
//处理第1种情况:只用更改颜色
if( luncle && color( luncle ) == red )
{
color( luncle ) = black;
color( parent(position) ) = black;
color( granddad(position) ) = red;
position = granddad( position );
}
else //left uncle == 0 or left uncle->color == black
{
if( position == left( parent(position) ) ) //处理第2种情况:
{
position = parent( position );
bs_tree_rotate_right( position,
static_cast<bs_tree_node_base_ptr>(root) );
}
color( parent(position) ) = black; //处理第3种情况:将终止循环
color( granddad(position) ) = red;
bs_tree_rotate_left( position->parent->parent,
static_cast<bs_tree_node_base_ptr>(root) );
}
}
} //end while
color( root ) = black;
}
void rb_tree_erase_rebalance( rb_tree_node_base_ptr erase_node,
rb_tree_node_base_ptr& root,
rb_tree_node_base_ptr& leftmost,
rb_tree_node_base_ptr& rightmost )
{
rb_tree_node_base_ptr successor, succ_parent;
bs_tree_node_base_ptr position;
//调整节点
position = bs_tree_erase_adjust(
static_cast<bs_tree_node_base_ptr>( erase_node ),
static_cast<bs_tree_node_base_ptr>( successor ),
static_cast<bs_tree_node_base_ptr>( succ_parent ),
static_cast<bs_tree_node_base_ptr>( root ),
static_cast<bs_tree_node_base_ptr>( leftmost ),
static_cast<bs_tree_node_base_ptr>( rightmost ) );
//调整颜色
if( position != erase_node )
data_swap( color( position ), color( erase_node ) );
position; //避免编译器提出警告
if( erase_node->color != red )
{
while( ( successor != root )
&& ( !successor || color( successor ) == black ) )
{
//successor is left child
if( successor == left( succ_parent ) )
{
rb_tree_node_base_ptr succ_rbrother = right( succ_parent );
//第1种情况:succ_rbrother->color is red
if( color( succ_rbrother ) == red )
{
color( succ_rbrother ) = black;
color( succ_parent ) = red;
bs_tree_rotate_left( succ_parent,
static_cast<bs_tree_node_base_ptr>(root) );
succ_rbrother = right( succ_parent );
}
//第2种情况: succ_rbrother->children->color are black
if( ( !left( succ_rbrother )
|| left( succ_rbrother )->color == black )
&& ( !right( succ_rbrother )
|| right( succ_rbrother )->color == black ) )
{
color( succ_rbrother ) = red;
successor = succ_parent;
succ_parent = parent( succ_parent );
}
else
{
//第3种情况:succ_rbrother->right->color is black
if( !right( succ_rbrother )
|| right( succ_rbrother )->color == black )
{
left( succ_rbrother )->color = black;
color( succ_rbrother ) = red;
bs_tree_rotate_right( succ_rbrother,
static_cast<bs_tree_node_base_ptr>(root) );
succ_rbrother = right( succ_parent );
}
//第4种情况:succ_rbrother->right->color is red
color( succ_rbrother ) = color( succ_parent );
color( succ_parent ) = black;
right( succ_rbrother )->color = black;
bs_tree_rotate_left( succ_parent,
static_cast<bs_tree_node_base_ptr>(root) );
break;
}
} //end if : successor is left child
//successor is right child
else
{
rb_tree_node_base_ptr succ_lbrother = left( succ_parent );
//第1种情况:succ_lbrother->color is red
if( color( succ_lbrother ) == red )
{
color( succ_lbrother ) = black;
color( succ_parent ) = red;
bs_tree_rotate_right( succ_parent,
static_cast<bs_tree_node_base_ptr>(root) );
succ_lbrother = left( succ_parent );
}
//第2种情况:succ_lbrother->children->color are black
if( ( !right( succ_lbrother )
|| right( succ_lbrother )->color == black )
&& ( !left( succ_lbrother )
|| left( succ_lbrother )->color == black ) )
{
color( succ_lbrother ) = red;
successor = succ_parent;
succ_parent = parent( succ_parent );
}
else
{
//第3种情况:succ_lbrother->left->color is black
if( !left( succ_lbrother )
|| left( succ_lbrother )->color == black )
{
left( succ_lbrother )->color = black;
color( succ_lbrother ) = red;
bs_tree_rotate_left( succ_lbrother,
static_cast<bs_tree_node_base_ptr>(root) );
succ_lbrother = left( succ_parent );
}
//第4种情况:succ_lbrother->left->color is red
color( succ_lbrother ) = color( succ_parent );
color( succ_parent ) = black;
left( succ_lbrother )->color = black;
bs_tree_rotate_right( succ_parent,
static_cast<bs_tree_node_base_ptr>(root) );
break;
}
} //end else : successor is right child
} //end while
if( successor )
color( successor ) = black;
} //end if
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
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 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
bs_tree_iterator_increment( static_cast<bs_ptr>( node ) );
return *this;
}
self& operator--()
{
if( node->color == red && node->parent->parent == node ) //is header
node = static_cast<base_ptr>( node->right );
else
bs_tree_iterator_decrement( static_cast<bs_ptr>( 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
{
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 typename Allocator::rebind<base_node_type>::other base_node_Alloc;
// typedef allocator<base_node_type> base_node_Alloc;
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*> iterator;
typedef rb_tree_iterator<Value, const Value&, const Value*> 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:
size_type m_node_count;
key_compare m_comp;
allocator_type m_alloc;
base_ptr m_header;
void init_header()
{
alloc_header();
m_header->parent = NULL_POINTER;
m_header->left = m_header;
m_header->right = m_header;
m_header->color = red;
}
void alloc_header()
{
m_header = base_node_Alloc().allocate( 1 );
}
void dealloc_header()
{
base_node_Alloc().deallocate( m_header, 1 );
}
public:
explicit rb_tree( const key_compare& compare = key_compare() )
: m_node_count(0), m_comp(compare)
{
init_header();
}
rb_tree( const self& rhs );
self& operator=( const self& rhs );
~rb_tree()
{
if( m_node_count > 0 )
destroy_tree( root() );
dealloc_header();
}
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 uint_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 );
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;
}
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;
}
bool verify_rb_tree() const;
size_type node_height( iterator position )
{ return bs_tree_node_height( position.node, root() ); }
size_type count( const key_type& k ) const
{
pair_const_iterator pItr = equal_range(k);
return distance( pItr.first, pItr.second );
}
void clear()
{
if( m_node_count > 0 )
{
destroy_tree( root() );
m_header->parent = NULL_POINTER;
m_header->left = m_header->right = m_header;
m_node_count = 0;
}
}
void swap( self& rhs )
{
if( this != &rhs )
{
data_swap( m_alloc, rhs.m_alloc );
data_swap( m_node_count, rhs.m_node_count );
data_swap( m_comp, rhs.m_comp );
data_swap( m_header, rhs.m_header );
}
}
protected:
void destroy_tree( node_ptr x );
node_ptr copy_tree( node_ptr source, node_ptr destination );
iterator insert_node( base_ptr ch, base_ptr pa, 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;
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 color_type& color( node_ptr x )
{ return x->color; }
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) ); }
static color_type& color( base_ptr x )
{ return static_cast<node_ptr>( x )->color; }
}; //end class
//-----------------------------------------------------------------------------
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();
if( rhs.m_node_count > 0 )
{
try
{
root() = copy_tree( rhs.root(), (node_ptr)m_header );
}
catch(...)
{
dealloc_header();
throw;
}
leftmost() = min_node( root() );
rightmost() = 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( rhs );
}
else
{
clear();
m_header->parent = NULL_POINTER;
m_header->left = m_header->right = m_header;
m_node_count = 0;
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 );
parent(top) = destination;
try
{
if( source->right )
right(top) = copy_tree( right(source), top );
destination = top;
source = left(source);
while( source )
{
node_ptr temp = copy_node(source);
left(destination) = temp;
parent(temp) = destination;
if( source->right )
right(temp) = 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 pa = m_header;
node_ptr current = parent(m_header);
while( current )
{
if( !m_comp(key(current), k) )
{
pa = current;
current = left(current);
}
else
current = right(current);
}
return pa;
}
//-----------------------------------------------------------------------------
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) ) )
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, (base_ptr&)root(),
(base_ptr&)leftmost(), (base_ptr&)rightmost() );
destroy_node( (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 pItr = equal_range(k);
size_type n = distance( pItr.first, pItr.second );
erase( pItr.first, pItr.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 ch, base_ptr pa, const value_type& v )
{
node_ptr p = create_node( v );
// v < parent
if( pa == m_header || ch || m_comp( get_key()(v), key(pa) ) )
{
left(pa) = p;
if( pa == m_header )
{
root() = p;
rightmost() = p;
}
else if( pa == leftmost() )
leftmost() = p;
}
else // v >= parent
{
right(pa) = p;
if( rightmost() == pa )
rightmost() = p;
}
p->parent = pa;
left(p) = NULL_POINTER;
right(p) = NULL_POINTER;
rb_tree_insert_rebalance( (base_ptr)p, (base_ptr&)root() );
++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 pItr = equal_range(k);
iterator first = pItr.firt;
iterator last = pItr.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, (base_ptr&)root(),
(base_ptr&)leftmost(), (base_ptr&)rightmost() );
try
{
get_key()( value(x) ) = new_key;
}
catch(...)
{
destroy_node( static_cast<node_ptr>( x ) );
--m_node_count;
throw;
}
base_ptr pa = m_header;
node_ptr current = root();
while( current )
{
pa = current;
current = m_comp( new_key, key(current) )
? left(current) : right(current);
}
if( m_comp(new_key, key(pa)) )
{
pa->left = x;
if( leftmost() == (node_ptr)pa )
leftmost() = (node_ptr)x;
}
else
{
pa->right = x;
if( rightmost() == (node_ptr)pa )
rightmost() = (node_ptr)x;
}
x->parent = pa;
x->left = NULL_POINTER;
x->right = NULL_POINTER;
rb_tree_insert_rebalance( x, (base_ptr&)root() );
}
//-----------------------------------------------------------------------------
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 = (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_YOUNG_LIBRARY_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
