| /*************************************************************************** |
| * |
| * _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 |