You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

913 lines
28 KiB

/***************************************************************************
*
* _tree.h - Declarations for the Standard Library tree classes
*
* This is an internal header file used to implement the C++ Standard
* Library. It should never be #included directly by a program.
*
* $Id: _tree.h 172106 2011-11-02 17:04:12Z statham $
*
***************************************************************************
*
* 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.
*
***************************************************************************
*
* Copyright (c) 1994-2001 Rogue Wave Software, Inc. All Rights Reserved.
*
* This computer software is owned by Rogue Wave Software, Inc. and is
* protected by U.S. copyright laws and other laws and by international
* treaties. This computer software is furnished by Rogue Wave Software,
* Inc. pursuant to a written license agreement and may be used, copied,
* transmitted, and stored only in accordance with the terms of such
* license and with the inclusion of the above copyright notice. This
* computer software or any other copies thereof may not be provided or
* otherwise made available to any other person.
*
* U.S. Government Restricted Rights. This computer software is provided
* with Restricted Rights. Use, duplication, or disclosure by the
* Government is subject to restrictions as set forth in subparagraph (c)
* (1) (ii) of The Rights in Technical Data and Computer Software clause
* at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
* Commercial Computer Software--Restricted Rights at 48 CFR 52.227-19,
* as applicable. Manufacturer is Rogue Wave Software, Inc., 5500
* Flatiron Parkway, Boulder, Colorado 80301 USA.
*
**************************************************************************/
/*
**
** Red-black tree class, designed for use in implementing STL
** associative containers (set, multiset, map, and multimap). The
** insertion and deletion algorithms are based on those in Cormen,
** Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
** except that:
**
** (1) the header cell is maintained with links not only to the root
** but also to the leftmost node of the tree, to enable constant time
** begin(), and to the rightmost node of the tree, to enable linear time
** performance when used with the generic set algorithms (set_union,
** etc.);
**
** (2) when a node being deleted has two children its successor node is
** relinked into its place, rather than copied, so that the only
** iterators invalidated are those referring to the deleted node.
**
*/
#ifndef _RWSTD_TREE_H_INCLUDED
#define _RWSTD_TREE_H_INCLUDED
#include <rw/_algobase.h>
#include <rw/_iterator.h>
#include <rw/_defs.h>
_RWSTD_NAMESPACE_BEGIN (__rw)
template <class _Alloc, class _Val, class _Key, class _KeyOf>
struct __rw_rb_tree_node {
enum _C_color_t { _C_red, _C_black };
typedef _Val& reference;
typedef _Alloc allocator_type;
typedef _RWSTD_REBIND (allocator_type, __rw_rb_tree_node) _C_node_alloc_t;
typedef _RWSTD_REBIND (allocator_type, _Key) _C_key_alloc_t;
typedef _TYPENAME _C_node_alloc_t::pointer _C_link_t;
typedef _TYPENAME _C_key_alloc_t::const_reference _C_const_key_ref;
_C_color_t _C_color_field;
_C_link_t _C_parent_link;
_C_link_t _C_left_link;
_C_link_t _C_right_link;
_Val _C_value_field;
static _C_link_t _C_minimum (_C_link_t __x) {
_RWSTD_ASSERT (0 != (void*)__x);
while ((void*)__x->_C_left())
__x = __x->_C_left();
return __x;
}
static _C_link_t _C_maximum (_C_link_t __x) {
_RWSTD_ASSERT (0 != (void*)__x);
while ((void*)__x->_C_right())
__x = __x->_C_right();
return __x;
}
_C_link_t& _C_left() {
return _C_left_link;
}
_C_link_t& _C_right () {
return _C_right_link;
}
_C_link_t& _C_parent () {
return _C_parent_link;
}
reference _C_value () {
return _C_value_field;
}
_C_const_key_ref _C_key () {
return _KeyOf()(_C_value_field);
}
_C_color_t& _C_color () {
return _C_color_field;
}
};
template <class _TypeT, class _DiffT,
class _Pointer, class _Reference, class _Node>
class __rw_tree_iter
: public _STD::iterator <_STD::bidirectional_iterator_tag,
_TypeT, _DiffT, _Pointer, _Reference>
{
typedef _STD::iterator <_STD::bidirectional_iterator_tag,
_TypeT, _DiffT, _Pointer, _Reference> _C_iter_base;
public:
typedef _TYPENAME _C_iter_base::value_type value_type;
typedef _TYPENAME _C_iter_base::difference_type difference_type;
typedef _TYPENAME _C_iter_base::pointer pointer;
typedef _TYPENAME _C_iter_base::reference reference;
typedef _TYPENAME _C_iter_base::iterator_category iterator_category;
typedef _Node _C_node_t;
typedef _TYPENAME _C_node_t::allocator_type allocator_type;
typedef _TYPENAME _C_node_t::_C_link_t _C_link_t;
typedef const value_type* const_pointer;
typedef const value_type& const_reference;
typedef __rw_tree_iter<_TypeT, _DiffT, value_type*, value_type&, _C_node_t>
_C_iterator;
_C_link_t _C_node;
__rw_tree_iter () {}
// no copy ctor other than the one below is defined
// will use a compiler generated one if __rw_tree_iter != _C_iterator
__rw_tree_iter (const _C_iterator &__rhs)
: _C_node (__rhs._C_node) { }
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template <class _Ptr, class _Ref>
__rw_tree_iter (const __rw_tree_iter<_TypeT, _DiffT, _Ptr, _Ref, _Node>&
__rhs)
: _C_node (__rhs._C_node) { }
#endif // _RWSTD_NO_MEMBER_TEMPLATES
__rw_tree_iter (_C_link_t __x)
: _C_node(__x) {}
#ifdef SNI
difference_type operator- (const __rw_tree_iter&) const {
return 0;
}
#endif
__rw_tree_iter& operator++ () {
if ((void*)_C_node->_C_right()) {
_C_node = _C_node->_C_right();
while ((void*)_C_node->_C_left())
_C_node = _C_node->_C_left();
}
else {
_C_link_t __y = _C_node->_C_parent();
while (_C_node == __y->_C_right()) {
_C_node = __y; __y = __y->_C_parent();
}
if (_C_node->_C_right() != __y) // Necessary because of rightmost.
_C_node = __y;
}
return *this;
}
__rw_tree_iter& operator-- () {
if (_C_node->_C_color() == _C_node_t::_C_red
&& _C_node->_C_parent()->_C_parent() == _C_node)
//
// Check for header.
//
_C_node = _C_node->_C_right(); // Return rightmost.
else if ((void*)_C_node->_C_left()) {
_C_link_t __y = _C_node->_C_left();
while ((void*)__y->_C_right())
__y = __y->_C_right();
_C_node = __y;
}
else {
_C_link_t __y = _C_node->_C_parent();
while (_C_node == __y->_C_left()) {
_C_node = __y; __y = __y->_C_parent();
}
_C_node = __y;
}
return *this;
}
__rw_tree_iter operator++ (int) {
__rw_tree_iter __tmp = *this;
return ++*this, __tmp;
}
__rw_tree_iter operator-- (int) {
__rw_tree_iter __tmp = *this;
return --*this, __tmp;
}
reference operator* () const {
return _C_node->_C_value();
}
_RWSTD_OPERATOR_ARROW (pointer operator-> () const);
};
#define _RWSTD_TREE_ITER(n) \
__rw_tree_iter <_TypeT, _DiffT, _Ptr##n, _Ref##n, _Node>
template <class _TypeT, class _DiffT,
class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Node>
inline bool
operator== (const _RWSTD_TREE_ITER(1) &__x, const _RWSTD_TREE_ITER(2) &__y)
{
return __x._C_node == __y._C_node;
}
template <class _TypeT, class _DiffT,
class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Node>
inline bool
operator!= (const _RWSTD_TREE_ITER(1) &__x, const _RWSTD_TREE_ITER(2) &__y)
{
return !(__x == __y);
}
#undef _RWSTD_TREE_ITER
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
class __rb_tree : private _Alloc
{
protected:
typedef __rw_rb_tree_node<_Alloc,_Val,_Key,_KeyOf> _C_node_t;
typedef _RWSTD_ALLOC_TYPE (_Alloc,_Val) _C_val_alloc_t;
typedef _TYPENAME _C_node_t::_C_key_alloc_t _C_key_alloc_t;
typedef _TYPENAME _C_node_t::_C_node_alloc_t _C_node_alloc_t;
typedef _TYPENAME _C_node_t::_C_link_t _C_link_t;
public:
typedef _Key key_type;
typedef _Val value_type;
typedef _Alloc allocator_type;
typedef _TYPENAME _C_val_alloc_t::pointer pointer;
typedef _TYPENAME _C_val_alloc_t::const_pointer const_pointer;
typedef _TYPENAME _Alloc::size_type size_type;
typedef _TYPENAME _Alloc::difference_type difference_type;
typedef _TYPENAME _C_val_alloc_t::reference reference;
typedef _TYPENAME _C_val_alloc_t::const_reference const_reference;
protected:
struct _C_rb_tree_node_buffer;
friend struct _C_rb_tree_node_buffer;
// for brevity, long name preserved for ABI compatibility
typedef _C_rb_tree_node_buffer _C_node_buf;
typedef _RWSTD_REBIND(allocator_type,_C_node_buf) _C_buf_alloc_t;
typedef _TYPENAME _C_buf_alloc_t::pointer _C_buf_ptr_t;
typedef __rw_tree_iter<value_type, difference_type, pointer,
reference, _C_node_t> _C_tree_iter;
typedef __rw_tree_iter<value_type, difference_type, const_pointer,
const_reference, _C_node_t> _C_tree_citer;
public:
#ifndef _RWSTD_NO_DEBUG_ITER
typedef __rw_debug_iter <__rb_tree, _C_tree_iter, _C_tree_iter>
iterator;
typedef __rw_debug_iter <__rb_tree, _C_tree_citer, _C_tree_iter>
const_iterator;
iterator _C_make_iter (_C_link_t __node) {
return iterator (*this, _C_tree_iter (__node));
}
const_iterator _C_make_iter (const _C_link_t __node) const {
return const_iterator (*this, _C_tree_citer (__node));
}
#else // if defined (_RWSTD_NO_DEBUG_ITER)
typedef _C_tree_iter iterator;
typedef _C_tree_citer const_iterator;
iterator _C_make_iter (_C_link_t __node) {
return iterator (__node);
}
const_iterator _C_make_iter (const _C_link_t __node) const {
return const_iterator (__node);
}
#endif // _RWSTD_NO_DEBUG_ITER
protected:
struct _C_rb_tree_node_buffer {
_C_buf_ptr_t _C_next_buffer;
size_type size;
_C_link_t _C_buffer;
};
_C_buf_ptr_t _C_buf_list;
_C_link_t _C_free_list;
_C_link_t _C_next_avail;
_C_link_t _C_last;
void _C_add_new_buffer () {
_RWSTD_C::size_t __next_buffer_size = 0;
if ((void*)_C_buf_list) {
__next_buffer_size =
_RW::__rw_new_capacity(_C_buf_list->size,this);
}
else {
__next_buffer_size =
_RW::__rw_new_capacity(0,this);
}
_C_buf_ptr_t __tmp =
_C_buf_alloc_t(*this).
allocate(_RWSTD_STATIC_CAST(size_type,1), (void*)_C_buf_list);
#ifndef _RWSTD_NO_EXCEPTIONS
try {
__tmp->_C_buffer =
_C_node_alloc_t(*this).
allocate(__next_buffer_size, (void*)_C_last);
} catch(...) {
_C_buf_alloc_t(*this).deallocate(__tmp,1);
throw;
}
#else
__tmp->_C_buffer =
_C_node_alloc_t(*this).allocate(__next_buffer_size,_C_last);
#endif // _RWSTD_NO_EXCEPTIONS
__tmp->_C_next_buffer = _C_buf_list;
__tmp->size = __next_buffer_size;
_C_buf_list = __tmp;
_C_next_avail = _C_buf_list->_C_buffer;
_C_last = _C_next_avail + __next_buffer_size;
}
void _C_deallocate_buffers ();
//
// Return a node from the free list or new storage
//
_C_link_t _C_get_link() {
_C_link_t __tmp = _C_free_list;
_C_link_t __tmp2 = (void*)_C_free_list ?
(_C_free_list = _RWSTD_STATIC_CAST(_C_link_t,(_C_free_list->_C_right_link)), __tmp)
: (_C_next_avail == _C_last ? (_C_add_new_buffer(), _C_next_avail++)
: _C_next_avail++);
__tmp2->_C_parent_link = NULL;
__tmp2->_C_left_link = NULL;
__tmp2->_C_right_link = NULL;
__tmp2->_C_color_field = _C_node_t::_C_red;
return __tmp2;
}
//
// Return a node from the free list or new storage with
// the _Val __v constructed on it. Every call to _C_get_node
// must eventually be followed by a call to _C_put_node.
//
_C_link_t _C_get_node (const _Val& __v) {
_C_link_t __tmp2 = _C_get_link();
#ifndef _RWSTD_NO_EXCEPTIONS
try {
_RWSTD_VALUE_ALLOC
(_C_val_alloc_t,
construct(_RWSTD_VALUE_ALLOC (_C_val_alloc_t,
address(__tmp2->_C_value())),
__v));
} catch(...) {
_C_put_node(__tmp2,false);
throw;
}
#else
_RWSTD_VALUE_ALLOC
(_C_val_alloc_t,
construct(_RWSTD_VALUE_ALLOC (_C_val_alloc_t,
address(__tmp2->_C_value())), __v));
#endif // _RWSTD_NO_EXCEPTIONS
return __tmp2;
}
_C_link_t _C_get_node () {
return _C_get_link();
}
//
// Return a node to the free list and destroy the value in it.
//
void _C_put_node (_C_link_t __p, bool do_destroy = true) {
__p->_C_right_link = _C_free_list;
if (do_destroy) {
_RWSTD_VALUE_ALLOC (_C_val_alloc_t,
destroy (_RWSTD_VALUE_ALLOC (_C_val_alloc_t,
address (__p->_C_value()))));
}
_C_free_list = __p;
}
protected:
_C_link_t _C_header;
_C_link_t& _C_root () const { return _C_header->_C_parent (); }
_C_link_t& _C_leftmost () const { return _C_header->_C_left (); }
_C_link_t& _C_rightmost () const { return _C_header->_C_right(); }
size_type _C_node_count; // Keeps track of size of tree.
bool _C_insert_always; // Controls whether an element already in the
// tree is inserted again.
_Comp _C_key_comp;
public:
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC
typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator;
typedef _STD::reverse_iterator<iterator> reverse_iterator;
#else
typedef __reverse_bi_iterator<const_iterator,
_STD::bidirectional_iterator_tag, value_type,
const_reference, const_pointer, difference_type>
const_reverse_iterator;
typedef __reverse_bi_iterator<iterator,
_STD::bidirectional_iterator_tag, value_type,
reference, pointer, difference_type>
reverse_iterator;
#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC
private:
iterator _C_insert (_C_link_t __x, _C_link_t __y,
const value_type& __v);
_C_link_t _C_copy (_C_link_t __x, _C_link_t __p);
void _C_erase (_C_link_t __x);
inline void _C_erase_leaf (_C_link_t __x);
void _C_init ()
{
_C_buf_list = 0;
_C_free_list = _C_next_avail = _C_last = 0;
_C_header = _C_get_node();
_C_root() = 0;
_C_leftmost() = _C_header;
_C_rightmost() = _C_header;
}
public:
__rb_tree (const _Comp& _RWSTD_COMP = _Comp(),
bool __always = true,
const _Alloc& __alloc = _Alloc())
: allocator_type (__alloc),_C_buf_list(0), _C_header(0), _C_node_count(0),
_C_insert_always(__always), _C_key_comp(_RWSTD_COMP)
{
_C_init();
}
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template<class _InputIter>
__rb_tree (_InputIter __first, _InputIter __last,
const _Comp& __cmp = _Comp(), bool __always = true,
const _Alloc& __alloc = _Alloc())
: allocator_type(__alloc),_C_buf_list(0), _C_header(0), _C_node_count(0),
_C_insert_always(__always), _C_key_comp(__cmp)
{
_C_init();
#ifndef _RWSTD_NO_EXCEPTIONS
try {
insert(__first, __last);
} catch(...) {
_C_deallocate_buffers();
throw;
}
#else
insert(__first, __last);
#endif // _RWSTD_NO_EXCEPTIONS
}
#else
__rb_tree (const value_type* __first, const value_type* __last,
const _Comp& _RWSTD_COMP = _Comp(),
bool __always = true,
const _Alloc& __alloc = _Alloc())
: allocator_type(__alloc),_C_buf_list(0), _C_header(0), _C_node_count(0),
_C_insert_always(__always), _C_key_comp(_RWSTD_COMP)
{
_C_init();
#ifndef _RWSTD_NO_EXCEPTIONS
try {
insert(__first, __last);
} catch(...) {
_C_deallocate_buffers();
throw;
}
#else
insert(__first, __last);
#endif // _RWSTD_NO_EXCEPTIONS
}
__rb_tree (const_iterator __first, const_iterator __last,
const _Comp& _RWSTD_COMP = _Comp(),
bool __always = true,
const _Alloc& __alloc = _Alloc())
: allocator_type(__alloc), _C_buf_list(0), _C_header(0), _C_node_count(0),
_C_insert_always(__always), _C_key_comp(_RWSTD_COMP)
{
_C_init();
#ifndef _RWSTD_NO_EXCEPTIONS
try {
insert(__first, __last);
} catch(...) {
_C_deallocate_buffers();
throw;
}
#else
insert(__first, __last);
#endif // _RWSTD_NO_EXCEPTIONS
}
#endif
__rb_tree (const __rb_tree<_Key,_Val,_KeyOf,_Comp,_Alloc>& __x,
bool __always = true)
: allocator_type(__x.get_allocator()), _C_buf_list(0), _C_header(0),
_C_node_count(__x._C_node_count), _C_insert_always(__always),
_C_key_comp(__x._C_key_comp)
{
_C_free_list = _C_next_avail = _C_last = 0;
_C_header = _C_get_node();
_C_header->_C_color() = _C_node_t::_C_red;
_TRY {
_C_root() = _C_copy(__x._C_root(), _C_header);
}
_CATCH (...) {
_C_deallocate_buffers();
_RETHROW;
}
if (_C_root()) {
_C_leftmost() = _C_node_t::_C_minimum(_C_root());
_C_rightmost() = _C_node_t::_C_maximum(_C_root());
}
else {
_C_leftmost() = _C_header;
_C_rightmost() = _C_header;
}
}
~__rb_tree () {
if ((void*)_C_header) {
erase (begin(), end ());
_C_put_node (_C_header, false);
_C_deallocate_buffers ();
}
}
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>&
operator= (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __x);
_Comp key_comp () const { return _C_key_comp; }
_C_val_alloc_t get_allocator() const
{
return _C_val_alloc_t(*this);
}
iterator begin () {
return _C_make_iter (_C_leftmost ());
}
const_iterator begin () const {
return _C_make_iter (_C_leftmost ());
}
iterator end () {
return _C_make_iter (_C_header);
}
const_iterator end () const {
return _C_make_iter (_C_header);
}
reverse_iterator rbegin () {
return reverse_iterator(end());
}
reverse_iterator rend () {
return reverse_iterator (begin());
}
const_reverse_iterator rbegin () const {
return const_reverse_iterator (end());
}
const_reverse_iterator rend () const {
return const_reverse_iterator(begin());
}
bool empty () const {
return _C_node_count == 0;
}
size_type size () const {
return _C_node_count;
}
size_type max_size () const {
return _C_node_alloc_t(*this).max_size();
}
void swap (__rb_tree &__t) {
if(get_allocator() == __t.get_allocator()) {
_STD::swap (_C_buf_list, __t._C_buf_list);
_STD::swap (_C_free_list, __t._C_free_list);
_STD::swap (_C_next_avail, __t._C_next_avail);
_STD::swap (_C_last, __t._C_last);
_STD::swap (_C_header, __t._C_header);
_STD::swap (_C_node_count, __t._C_node_count);
_STD::swap (_C_insert_always, __t._C_insert_always);
_STD::swap (_C_key_comp, __t._C_key_comp);
}
else {
__rb_tree __x = *this;
*this = __t;
__t = __x;
}
}
_STD::pair<iterator, bool> insert (const value_type&);
iterator insert (iterator, const value_type&);
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template<class _Iterator>
void insert (_Iterator __first, _Iterator __last);
#else
void insert (const_iterator __first, const_iterator __last);
void insert (const value_type* __first, const value_type* __last);
#endif
iterator erase (iterator);
size_type erase (const key_type&);
iterator erase (iterator, iterator);
void erase (const key_type*, const key_type*);
iterator find (const key_type&);
const_iterator find (const key_type& __x) const {
return _RWSTD_CONST_CAST (__rb_tree*, this)->find (__x);
}
size_type count (const key_type& __x) const;
iterator lower_bound (const key_type& __x);
const_iterator lower_bound (const key_type& __x) const {
return _RWSTD_CONST_CAST (__rb_tree*, this)->lower_bound (__x);
}
iterator upper_bound (const key_type& __x);
const_iterator upper_bound (const key_type& __x) const {
return _RWSTD_CONST_CAST (__rb_tree*, this)->upper_bound (__x);
}
_STD::pair<iterator, iterator> equal_range (const key_type& __x);
_STD::pair<const_iterator, const_iterator>
equal_range (const key_type& __x) const {
_STD::pair<iterator, iterator> __tmp =
_RWSTD_CONST_CAST (__rb_tree*, this)->equal_range (__x);
return _STD::pair<const_iterator, const_iterator>
(__tmp.first, __tmp.second);
}
inline void __rotate_left (_C_link_t __x);
inline void __rotate_right (_C_link_t __x);
};
//
// Inline functions
//
template <class _Key, class _Val, class _KeyOf,
class _Comp, class _Alloc>
inline bool
operator== (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __x,
const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __y)
{
return __x.size () == __y.size ()
&& equal (__x.begin (), __x.end (), __y.begin ());
}
template <class _Key, class _Val, class _KeyOf,
class _Comp, class _Alloc>
inline bool
operator< (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __x,
const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __y)
{
return lexicographical_compare (__x.begin (), __x.end (),
__y.begin (), __y.end ());
}
template <class _Key,class _Val,class _KeyOf,class _Comp,class _Alloc>
inline void
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_C_erase_leaf (_C_link_t __x)
{
// Remove a leaf node from the tree
_C_link_t __y = __x->_C_parent();
if (__y == _C_header)
{
_C_leftmost() = _C_rightmost() = __y;
_C_root() = 0;
}
else if (__y->_C_left() == __x)
{
__y->_C_left() = 0;
if (_C_leftmost() == __x)
_C_leftmost() = __y;
}
else
{
__y->_C_right() = 0;
if (_C_rightmost() == __x)
_C_rightmost() = __y;
}
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__rotate_left (_C_link_t __x)
{
_RWSTD_ASSERT (0 != (void*)__x);
_C_link_t __y = __x->_C_right();
__x->_C_right() = __y->_C_left();
if ((void*)__y->_C_left ())
__y->_C_left()->_C_parent() = __x;
__y->_C_parent() = __x->_C_parent();
if (__x == _C_root())
_C_root() = __y;
else if (__x == __x->_C_parent()->_C_left())
__x->_C_parent()->_C_left() = __y;
else
__x->_C_parent()->_C_right() = __y;
__y->_C_left () = __x;
__x->_C_parent() = __y;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__rotate_right (_C_link_t __x)
{
_RWSTD_ASSERT (0 != (void*)__x);
_C_link_t __y = __x->_C_left();
__x->_C_left () = __y->_C_right();
if ((void*)__y->_C_right ())
__y->_C_right()->_C_parent() = __x;
__y->_C_parent() = __x->_C_parent();
if (__x == _C_root())
_C_root() = __y;
else if (__x == __x->_C_parent()->_C_right())
__x->_C_parent()->_C_right() = __y;
else
__x->_C_parent()->_C_left() = __y;
__y->_C_right () = __x;
__x->_C_parent () = __y;
}
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
template<class _Iterator>
inline void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
insert (_Iterator __first, _Iterator __last)
{
for (; __first != __last; ++__first)
insert(*__first);
}
#else
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
insert (const_iterator __first, const_iterator __last)
{
for (; __first != __last; ++__first)
insert(*__first);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
insert (const _Val* __first, const _Val* __last)
{
for (; __first != __last; ++__first)
insert(*__first);
}
#endif // _RWSTD_NO_MEMBER_TEMPLATES
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
erase (const _Key* __first, const _Key* __last)
{
for (; __first != __last; ++__first)
erase(*__first);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::count (const _Key& __k) const
{
_STD::pair<const_iterator, const_iterator> __p = equal_range(__k);
size_type __n = _DISTANCE (__p.first, __p.second, size_type);
return __n;
}
#define _RWSTD_RB_TREE_ITER _TYPENAME __rb_tree<_Key, _Val, _KeyOf, \
_Comp, _Alloc>::iterator
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline _STD::pair<_RWSTD_RB_TREE_ITER , _RWSTD_RB_TREE_ITER >
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::equal_range (const _Key& __k)
{
return _STD::pair<iterator, iterator>(lower_bound (__k), upper_bound (__k));
}
#undef _RWSTD_RB_TREE_ITER
_RWSTD_NAMESPACE_END // __rw
#ifdef _RWSTD_COMPILE_INSTANTIATE
# include <rw/_tree.cc>
#endif
#endif // _RWSTD_TREE_H_INCLUDED