blob: fbf31a7df1cdfb54c337281f91d17d0749b21de8 [file] [log] [blame]
/***************************************************************************
*
* _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$
*
***************************************************************************
*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed
* with this work for additional information regarding copyright
* ownership. The ASF licenses this file to you under the Apache
* License, Version 2.0 (the "License"); you may not use this file
* except in compliance with the License. You may obtain a copy of
* the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
* implied. See the License for the specific language governing
* permissions and limitations under the License.
*
* Copyright 1994-2006 Rogue Wave Software.
*
***************************************************************************
*
* 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.
*
**************************************************************************/
/***************************************************************************
*
* Red-black tree class, designed for use in implementing 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_RW_TREE_H_INCLUDED
#define _RWSTD_RW_TREE_H_INCLUDED
#ifndef _RWSTD_RW_ALGOBASE_H_INCLUDED
# include <rw/_algobase.h>
#endif // _RWSTD_RW_ALGOBASE_H_INCLUDED
#ifndef _RWSTD_RW_ITERATOR_H_INCLUDED
# include <rw/_iterator.h>
#endif // _RWSTD_RW_ITERATOR_H_INCLUDED
_RWSTD_NAMESPACE (__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;
_C_link_t _C_parent;
_C_link_t _C_child [2]; // left (0) and right (1) children
_Val _C_value;
static _C_link_t _C_minmax (_C_link_t __lnk, bool __do_max) {
_RWSTD_ASSERT (_C_link_t () != __lnk);
while (_C_link_t () != __lnk->_C_child [__do_max])
__lnk = __lnk->_C_child [__do_max];
return __lnk;
}
static _C_link_t _C_min (_C_link_t __lnk) {
return _C_minmax (__lnk, false);
}
static _C_link_t _C_max (_C_link_t __lnk) {
return _C_minmax (__lnk, true);
}
_C_const_key_ref _C_key () const {
return _KeyOf ()(_C_value);
}
};
// iterator implements inorder traversal; i.e., nodes are visited
// recursively in this order: left subtree, root, right subtree
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 () { /* empty */ }
// 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) { }
template <class _Ptr, class _Ref>
__rw_tree_iter (const __rw_tree_iter<_TypeT, _DiffT, _Ptr, _Ref, _Node>&
__rhs)
: _C_node (__rhs._C_node) { }
__rw_tree_iter (_C_link_t __lnk)
: _C_node (__lnk) {}
#ifdef SNI
difference_type operator- (const __rw_tree_iter&) const {
return 0;
}
#endif
__rw_tree_iter& operator++ () {
if (_C_link_t () != _C_node->_C_child [1]) {
_C_node = _C_node_t::_C_min (_C_node->_C_child [1]);
}
else {
_C_link_t __tmp = _C_node->_C_parent;
while (_C_node == __tmp->_C_child [1]) {
_C_node = __tmp;
__tmp = __tmp->_C_parent;
}
if (_C_node->_C_child [1] != __tmp)
_C_node = __tmp;
}
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_child [1]; // Return rightmost.
else if (_C_link_t () != _C_node->_C_child [0]) {
_C_node = _C_node_t::_C_max (_C_node->_C_child [0]);
}
else {
_C_link_t __tmp = _C_node->_C_parent;
while (_C_node == __tmp->_C_child [0]) {
_C_node = __tmp;
__tmp = __tmp->_C_parent;
}
_C_node = __tmp;
}
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) &__lhs,
const _RWSTD_TREE_ITER (2) &__rhs)
{
return __lhs._C_node == __rhs._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) &__lhs,
const _RWSTD_TREE_ITER (2) &__rhs)
{
return !(__lhs == __rhs);
}
#undef _RWSTD_TREE_ITER
// for convenience
#undef _ITER_NODE
#define _ITER_NODE(it) (_ITER_BASE (it)._C_node)
_EXPORT
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
class __rb_tree : private _Alloc
{
private:
typedef __rw_rb_tree_node<_Alloc,_Val,_Key,_KeyOf> _C_node_t;
typedef _RWSTD_ALLOC_TYPE (_Alloc,_Val) _C_val_alloc_t;
typedef _RWSTD_REBIND (_Alloc, _Key) _C_key_alloc_t;
typedef _RWSTD_REBIND (_Alloc, _C_node_t) _C_node_alloc_t;
typedef typename _C_node_alloc_t::pointer _C_link_t;
public:
typedef _Key key_type;
typedef _Val value_type;
typedef _Comp key_compare;
typedef _Alloc allocator_type;
typedef typename _C_val_alloc_t::pointer pointer;
typedef typename _C_val_alloc_t::const_pointer const_pointer;
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
typedef typename _C_val_alloc_t::reference reference;
typedef typename _C_val_alloc_t::const_reference const_reference;
private:
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 (_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 (_C_link_t __node) const {
return const_iterator (__node);
}
#endif // _RWSTD_NO_DEBUG_ITER
private:
#ifdef _RWSTD_NO_NESTED_CLASS_ACCESS
// allow _C_node_buf access to __rb_tree's private type(s)
// if the resolution of cwg issue 45 is not yet implemented
struct _C_node_buf;
friend struct _C_node_buf;
#endif // _RWSTD_NO_NESTED_CLASS_ACCESS
struct _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;
_C_buf_ptr_t _C_next_buffer;
size_type size;
_C_link_t _C_buffer;
};
typedef typename _C_node_buf::_C_buf_alloc_t _C_buf_alloc_t;
typedef typename _C_node_buf::_C_buf_ptr_t _C_buf_ptr_t;
_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 ();
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_child [1])), __tmp)
: (_C_next_avail == _C_last ? (_C_add_new_buffer (), _C_next_avail++)
: _C_next_avail++);
__tmp2->_C_parent = 0;
__tmp2->_C_child [0] = 0;
__tmp2->_C_child [1] = 0;
__tmp2->_C_color = _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_reference __v) {
_C_link_t __tmp2 = _C_get_link ();
_TRY {
_RWSTD_VALUE_ALLOC (_C_val_alloc_t, *this,
construct (_RWSTD_VALUE_ALLOC (_C_val_alloc_t, *this,
address (__tmp2->_C_value)),
__v));
}
_CATCH (...) {
_C_put_node (__tmp2, false);
_RETHROW;
}
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 __destroy = true) {
__p->_C_child [1] = _C_free_list;
if (__destroy) {
_RWSTD_VALUE_ALLOC (_C_val_alloc_t, *this,
destroy (_RWSTD_VALUE_ALLOC (_C_val_alloc_t, *this,
address (__p->_C_value))));
}
_C_free_list = __p;
}
private:
// _C_end is end()
// tree root is _C_end->_C_parent
// the leftmost node, i.e., begin(), is _C_end->_C_child [0]
// the rightmost node, i.e., end() - 1, is _C_end->_C_child [1]
// all three pointers are null (0) when the tree is empty
// both child pointers of each leaf node are null (0)
// the parent pointer of the root node points to *_C_end
_C_link_t _C_end;
size_type _C_size; // number of nodes
key_compare _C_cmp; // comparison object
public:
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC
typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator;
typedef _STD::reverse_iterator<iterator> reverse_iterator;
#else // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)
typedef std::reverse_iterator<const_iterator,
_STD::bidirectional_iterator_tag, value_type,
const_reference, const_pointer, difference_type>
const_reverse_iterator;
typedef std::reverse_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, _C_link_t, const value_type&);
_C_link_t _C_copy (_C_link_t, _C_link_t);
void _C_erase (_C_link_t);
void _C_erase_leaf (_C_link_t);
void _C_init () {
_C_buf_list = 0;
_C_free_list =
_C_next_avail =
_C_last = 0;
_C_end = _C_get_node ();
_C_end->_C_parent = 0;
_C_end->_C_child [0] =
_C_end->_C_child [1] = _C_end;
}
public:
__rb_tree (const key_compare& = key_compare (),
const allocator_type& = allocator_type ());
template<class _InputIter>
__rb_tree (_InputIter __first, _InputIter __last,
const key_compare &__cmp,
const allocator_type &__alloc, bool __dup)
: allocator_type (__alloc), _C_buf_list (0),
_C_end (0), _C_size (0),
_C_cmp (__cmp) {
_C_init ();
_TRY {
insert (__first, __last, __dup);
}
_CATCH (...) {
_C_deallocate_buffers ();
_RETHROW;
}
}
__rb_tree (const __rb_tree&);
~__rb_tree ();
__rb_tree& operator= (const __rb_tree&);
key_compare key_comp () const {
return _C_cmp;
}
_C_val_alloc_t get_allocator () const {
return _C_val_alloc_t (*this);
}
iterator begin () {
return _C_make_iter (_C_end->_C_child [0]);
}
const_iterator begin () const {
return _C_make_iter (_C_end->_C_child [0]);
}
iterator end () {
return _C_make_iter (_C_end);
}
const_iterator end () const {
return _C_make_iter (_C_end);
}
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 0 == _C_size;
}
size_type size () const {
return _C_size;
}
size_type max_size () const {
return _C_node_alloc_t (*this).max_size ();
}
void swap (__rb_tree &__rhs) {
if (get_allocator () == __rhs.get_allocator ()) {
_STD::swap (_C_buf_list, __rhs._C_buf_list);
_STD::swap (_C_free_list, __rhs._C_free_list);
_STD::swap (_C_next_avail, __rhs._C_next_avail);
_STD::swap (_C_last, __rhs._C_last);
_STD::swap (_C_end, __rhs._C_end);
_STD::swap (_C_size, __rhs._C_size);
_STD::swap (_C_cmp, __rhs._C_cmp);
}
else {
__rb_tree __tmp = *this;
*this = __rhs;
__rhs = __tmp;
}
}
void _C_insert (const value_type&, _STD::pair<iterator, bool>&, bool);
_STD::pair<iterator, bool>
insert (const value_type &__val, bool __dup) {
_STD::pair<iterator, bool> __ret;
return _C_insert (__val, __ret, __dup), __ret;
}
iterator insert (iterator, const value_type&, bool);
template<class _Iterator>
void insert (_Iterator __first, _Iterator __last, bool __dup) {
for (; __first != __last; ++__first)
insert (*__first, __dup);
}
iterator erase (iterator);
size_type erase (const key_type&);
iterator erase (iterator, iterator);
// MSVC 6.0 thinks S<const T*> is the same as S<T*>...
#if !defined (_MSC_VER) || _MSC_VER > 1300
// map and set's iterator may be defined to be tree::const_iterator
iterator insert (const_iterator __it, const value_type &__x, bool __dup) {
return insert (_C_make_iter (_ITER_NODE (__it)), __x, __dup);
}
// map and set's iterator may be defined to be tree::const_iterator
iterator erase (const_iterator __it) {
return erase (_C_make_iter (_ITER_NODE (__it)));
}
// map and set's iterator may be defined to be tree::const_iterator
iterator erase (const_iterator __first, const_iterator __last) {
return erase (_C_make_iter (_ITER_NODE (__first)),
_C_make_iter (_ITER_NODE (__last)));
}
#endif // _MSC_VER <= 1300
void erase (const key_type*, const key_type*);
void clear () {
erase (begin (), end ());
}
iterator find (const key_type&);
const_iterator find (const key_type& __key) const {
return _RWSTD_CONST_CAST (__rb_tree*, this)->find (__key);
}
size_type count (const key_type&) const;
iterator lower_bound (const key_type&);
const_iterator lower_bound (const key_type& __key) const {
return _RWSTD_CONST_CAST (__rb_tree*, this)->lower_bound (__key);
}
iterator upper_bound (const key_type&);
const_iterator upper_bound (const key_type& __key) const {
return _RWSTD_CONST_CAST (__rb_tree*, this)->upper_bound (__key);
}
_STD::pair<iterator, iterator> equal_range (const key_type&);
_STD::pair<const_iterator, const_iterator>
equal_range (const key_type& __key) const {
_STD::pair<iterator, iterator> __tmp =
_RWSTD_CONST_CAST (__rb_tree*, this)->equal_range (__key);
return _STD::pair<const_iterator, const_iterator>
(__tmp.first, __tmp.second);
}
#ifndef _RWSTD_NO_OPTIMIZE_SPEED
void _C_rol (_C_link_t);
void _C_ror (_C_link_t);
#else // if defined (_RWSTD_NO_OPTIMIZE_SPEED)
void _C_rotate (_C_link_t, bool);
#endif // _RWSTD_NO_OPTIMIZE_SPEED
size_type _C_level (const_iterator) const;
// depth guaranteed to be <= 2 * log2(size() + 1)
size_type _C_depth (const_iterator, size_type* = 0) const;
size_type _C_depth () const {
return _C_depth (_C_make_iter (_C_end->_C_parent));
}
};
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline bool
operator== (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __lhs,
const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __rhs)
{
return __lhs.size () == __rhs.size ()
&& _STD::equal (__lhs.begin (), __lhs.end (), __rhs.begin ());
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline bool
operator< (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __lhs,
const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __rhs)
{
return _STD::lexicographical_compare (__lhs.begin (), __lhs.end (),
__rhs.begin (), __rhs.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 __lnk)
{
// remove a leaf node from the tree
const _C_link_t __parent = __lnk->_C_parent;
if (__parent == _C_end) {
_C_end->_C_parent = 0;
_C_end->_C_child [0] =
_C_end->_C_child [1] = __parent;
}
#ifndef _RWSTD_NO_OPTIMIZE_SPEED
else if (__parent->_C_child [0] == __lnk) {
__parent->_C_child [0] = 0;
if (_C_end->_C_child [0] == __lnk)
_C_end->_C_child [0] = __parent;
}
else {
__parent->_C_child [1] = 0;
if (_C_end->_C_child [1] == __lnk)
_C_end->_C_child [1] = __parent;
}
#else // if !defined (_RWSTD_NO_OPTIMIZE_SPEED)
else {
const bool __right = __parent->_C_child [0] != __lnk;
__parent->_C_child [__right] = 0;
if (_C_end->_C_child [__right] == __lnk)
_C_end->_C_child [__right] = __parent;
}
#endif // _RWSTD_NO_OPTIMIZE_SPEED
}
#ifndef _RWSTD_NO_OPTIMIZE_SPEED
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
_C_rol (_C_link_t __lnk)
{
_RWSTD_ASSERT (_C_link_t () != __lnk);
_C_link_t __tmp = __lnk->_C_child [1];
__lnk->_C_child [1] = __tmp->_C_child [0];
if (_C_link_t () != __tmp->_C_child [0])
__tmp->_C_child [0]->_C_parent = __lnk;
__tmp->_C_parent = __lnk->_C_parent;
if (__lnk == _C_end->_C_parent)
_C_end->_C_parent = __tmp;
else if (__lnk == __lnk->_C_parent->_C_child [0])
__lnk->_C_parent->_C_child [0] = __tmp;
else
__lnk->_C_parent->_C_child [1] = __tmp;
__tmp->_C_child [0] = __lnk;
__lnk->_C_parent = __tmp;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
_C_ror (_C_link_t __lnk)
{
_RWSTD_ASSERT (_C_link_t () != __lnk);
_C_link_t __tmp = __lnk->_C_child [0];
__lnk->_C_child [0] = __tmp->_C_child [1];
if (_C_link_t () != __tmp->_C_child [1])
__tmp->_C_child [1]->_C_parent = __lnk;
__tmp->_C_parent = __lnk->_C_parent;
if (__lnk == _C_end->_C_parent)
_C_end->_C_parent = __tmp;
else if (__lnk == __lnk->_C_parent->_C_child [1])
__lnk->_C_parent->_C_child [1] = __tmp;
else
__lnk->_C_parent->_C_child [0] = __tmp;
__tmp->_C_child [1] = __lnk;
__lnk->_C_parent = __tmp;
}
#else // if defined (_RWSTD_NO_OPTIMIZE_SPEED)
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
_C_rotate (_C_link_t __lnk, bool __right)
{
_RWSTD_ASSERT (_C_link_t () != __lnk);
_C_link_t __tmp = __lnk->_C_child [!__right];
__lnk->_C_child [!__right] = __tmp->_C_child [__right];
if (_C_link_t () != __tmp->_C_child [__right])
__tmp->_C_child [__right]->_C_parent = __lnk;
__tmp->_C_parent = __lnk->_C_parent;
if (__lnk == _C_end->_C_parent)
_C_end->_C_parent = __tmp;
else {
const bool __rt = __lnk == __lnk->_C_parent->_C_child [1];
__lnk->_C_parent->_C_child [__rt] = __tmp;
}
__tmp->_C_child [__right] = __lnk;
__lnk->_C_parent = __tmp;
}
#endif // _RWSTD_NO_OPTIMIZE_SPEED
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline 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
} // namespace __rw
#ifdef _RWSTD_NO_IMPLICIT_INCLUSION
# include <rw/_tree.cc>
#endif
#endif // _RWSTD_RW_TREE_H_INCLUDED