| /*************************************************************************** |
| * |
| * _tree.cc - Non-inline tree definitions for the Standard Library |
| * |
| * $Id$ |
| * |
| *************************************************************************** |
| * |
| * 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. |
| * |
| *************************************************************************** |
| * |
| * 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. |
| * |
| **************************************************************************/ |
| |
| |
| _RWSTD_NAMESPACE (__rw) { |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| __rb_tree (const key_compare &__cmp /* = key_compare () */, |
| const allocator_type &__alloc /* = allocator_type () */) |
| : allocator_type (__alloc), |
| _C_buf_list (0), |
| _C_end (0), |
| _C_size (0), |
| _C_cmp (__cmp) |
| { |
| _C_init (); |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| operator= (const __rb_tree &__x) |
| { |
| if (this != &__x) { |
| erase (begin (), end ()); |
| |
| // set the root of the tree |
| _C_end->_C_parent = _C_copy (__x._C_end->_C_parent, _C_end); |
| |
| if (_C_link_t () == _C_end->_C_parent) { |
| // set the child pointers of an empty tree to point to the header |
| _C_end->_C_child [0] = |
| _C_end->_C_child [1] = _C_end; |
| } |
| else { |
| // set the leftmost and the rightmost nodes |
| _C_end->_C_child [0] = _C_node_t::_C_min (_C_end->_C_parent); |
| _C_end->_C_child [1] = _C_node_t::_C_max (_C_end->_C_parent); |
| } |
| _C_size = __x._C_size; |
| _C_cmp = __x._C_cmp; |
| } |
| return *this; |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| __rb_tree (const __rb_tree &__lnk) |
| : allocator_type (__lnk.get_allocator ()), _C_buf_list (0), _C_end (0), |
| _C_size (__lnk._C_size), |
| _C_cmp (__lnk._C_cmp) |
| { |
| _C_free_list = _C_next_avail = _C_last = 0; |
| _C_end = _C_get_node (); |
| _C_end->_C_color = _C_node_t::_C_red; |
| _TRY { |
| _C_end->_C_parent = _C_copy (__lnk._C_end->_C_parent, _C_end); |
| } |
| _CATCH (...) { |
| _C_deallocate_buffers (); |
| _RETHROW; |
| } |
| if (_C_link_t () == _C_end->_C_parent) { |
| _C_end->_C_child [0] = |
| _C_end->_C_child [1] = _C_end; |
| } |
| else { |
| _C_end->_C_child [0] = _C_node_t::_C_min (_C_end->_C_parent); |
| _C_end->_C_child [1] = _C_node_t::_C_max (_C_end->_C_parent); |
| } |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| ~__rb_tree () |
| { |
| if (_C_link_t () != _C_end) { |
| erase (begin (), end ()); |
| _C_put_node (_C_end, false); |
| _C_deallocate_buffers (); |
| } |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| _C_add_new_buffer () |
| { |
| const size_type __bufsize = |
| _C_buf_ptr_t () == _C_buf_list ? 0 : _C_buf_list->size; |
| |
| size_type __newsize = _RWSTD_NEW_CAPACITY (__rb_tree, this, __bufsize); |
| if (__newsize <= __bufsize) |
| __newsize = __bufsize + 1; |
| |
| _C_buf_ptr_t __buf = |
| _C_buf_alloc_t (*this).allocate (size_type (1), (void*)_C_buf_list); |
| |
| _TRY { |
| __buf->_C_buffer = |
| _C_node_alloc_t (*this).allocate (__newsize, (void*)_C_last); |
| } |
| _CATCH (...) { |
| _C_buf_alloc_t (*this).deallocate (__buf, 1); |
| _RETHROW; |
| } |
| __buf->_C_next_buffer = _C_buf_list; |
| __buf->size = __newsize; |
| _C_buf_list = __buf; |
| _C_next_avail = _C_buf_list->_C_buffer; |
| _C_last = _C_next_avail + __newsize; |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| _C_deallocate_buffers () |
| { |
| while ((void*)_C_buf_list) { |
| _C_buf_ptr_t __tmp = _C_buf_list; |
| _C_buf_list = (_C_buf_ptr_t)(_C_buf_list->_C_next_buffer); |
| _C_node_alloc_t(*this).deallocate(__tmp->_C_buffer,__tmp->size); |
| _C_buf_alloc_t(*this).deallocate(__tmp,1); |
| } |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| _C_insert (_C_link_t __x, _C_link_t __y, const value_type &__v) |
| { |
| _C_link_t __z = _C_get_node (__v); |
| ++_C_size; |
| |
| // for notational convenience |
| const typename _C_node_t::_C_color_t _Red = _C_node_t::_C_red; |
| const typename _C_node_t::_C_color_t _Black = _C_node_t::_C_black; |
| const _C_link_t _Null = _C_link_t (); |
| |
| if ( __y == _C_end || _Null != __x |
| || _C_cmp (_KeyOf()(__v), __y->_C_key ())) { |
| |
| __y->_C_child [0] = __z; |
| if (__y == _C_end) { |
| |
| // set the root node and the rightmost node |
| _C_end->_C_parent = __z; |
| _C_end->_C_child [1] = __z; |
| } |
| else if (__y == _C_end->_C_child [0]) { |
| // set the leftmost node |
| _C_end->_C_child [0] = __z; |
| } |
| } |
| else { |
| __y->_C_child [1] = __z; |
| if (__y == _C_end->_C_child [1]) { |
| // set the rightmost node |
| _C_end->_C_child [1] = __z; |
| } |
| } |
| |
| __z->_C_parent = __y; |
| __x = __z; // recolor and rebalance the tree |
| |
| while ( __x != _C_end->_C_parent |
| && __x->_C_parent->_C_color == _Red) { |
| |
| #ifndef _RWSTD_NO_OPTIMIZE_SPEED |
| |
| if (__x->_C_parent == __x->_C_parent->_C_parent->_C_child [0]) { |
| |
| __y = __x->_C_parent->_C_parent->_C_child [1]; |
| |
| if (_Null != __y && __y->_C_color == _Red) { |
| __x->_C_parent->_C_color = _Black; |
| __y->_C_color = _Black; |
| __x->_C_parent->_C_parent->_C_color = _Red; |
| __x = __x->_C_parent->_C_parent; |
| } |
| else { |
| if (__x == __x->_C_parent->_C_child [1]) { |
| __x = __x->_C_parent; |
| _C_rol (__x); |
| } |
| __x->_C_parent->_C_color = _Black; |
| __x->_C_parent->_C_parent->_C_color = _Red; |
| _C_ror (__x->_C_parent->_C_parent); |
| } |
| } |
| else { |
| __y = __x->_C_parent->_C_parent->_C_child [0]; |
| |
| if (_Null != __y && __y->_C_color == _Red) { |
| __x->_C_parent->_C_color = _Black; |
| __y->_C_color = _Black; |
| __x->_C_parent->_C_parent->_C_color = _Red; |
| __x = __x->_C_parent->_C_parent; |
| } |
| else { |
| if (__x == __x->_C_parent->_C_child [0]) { |
| __x = __x->_C_parent; |
| _C_ror (__x); |
| } |
| __x->_C_parent->_C_color = _Black; |
| __x->_C_parent->_C_parent->_C_color = _Red; |
| _C_rol (__x->_C_parent->_C_parent); |
| } |
| } |
| |
| #else // if defined (_RWSTD_NO_OPTIMIZE_SPEED) |
| |
| const bool __left = |
| __x->_C_parent == __x->_C_parent->_C_parent->_C_child [0]; |
| const bool __right = !__left; |
| |
| __y = __x->_C_parent->_C_parent->_C_child [__left]; |
| |
| if (_Null != __y && _Red == __y->_C_color) { |
| __y->_C_color = |
| __x->_C_parent->_C_color = _Black; |
| __x->_C_parent->_C_parent->_C_color = _Red; |
| __x = __x->_C_parent->_C_parent; |
| } |
| else { |
| if (__x == __x->_C_parent->_C_child [__left]) { |
| __x = __x->_C_parent; |
| _C_rotate (__x, __right); |
| } |
| __x->_C_parent->_C_color = _Black; |
| __x->_C_parent->_C_parent->_C_color = _Red; |
| _C_rotate (__x->_C_parent->_C_parent, __left); |
| } |
| |
| #endif // _RWSTD_NO_OPTIMIZE_SPEED |
| |
| } |
| |
| // set the color of the root node |
| _C_end->_C_parent->_C_color = _Black; |
| |
| return _C_make_iter (__z); |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| _C_insert (const value_type &__v, _STD::pair<iterator, bool> &__ret, |
| bool __dup) |
| { |
| _C_link_t __y = _C_end; // end |
| _C_link_t __x = _C_end->_C_parent; // root node |
| |
| bool __right = true; |
| |
| while (_C_link_t () != __x) { |
| __y = __x; |
| __right = _C_cmp (_KeyOf ()(__v), __x->_C_key ()); |
| __x = __x->_C_child [!__right]; |
| } |
| |
| typedef _STD::pair<iterator, bool> _IterPair; |
| |
| if (__dup) { |
| // allow insertion of duplicate keys |
| __ret = _IterPair (_C_insert (__x, __y, __v), true); |
| return; |
| } |
| |
| iterator __j = _C_make_iter (__y); |
| if (__right) { |
| if (__j == begin ()) { |
| __ret = _IterPair (_C_insert (__x, __y, __v), true); |
| return; |
| } |
| --__j; |
| } |
| |
| if (_C_cmp (_ITER_NODE (__j)->_C_key (), _KeyOf ()(__v))) |
| __ret = _IterPair (_C_insert (__x, __y, __v), true); |
| else |
| __ret = _IterPair (__j, false); |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| insert (iterator __it, const value_type &__v, bool __dup) |
| { |
| _RWSTD_ASSERT_RANGE (begin (), __it); |
| |
| #ifdef _RWSTDDEBUG |
| |
| { // verify the consistency of the tree |
| size_type __two_logN = 0; |
| for (size_type __i = size () + 1; __i >>= 1; ++__two_logN); |
| |
| __two_logN *= 2; |
| |
| const size_type __depth = _C_depth (); |
| _RWSTD_ASSERT (__depth <= __two_logN); |
| } |
| |
| #endif // _RWSTDDEBUG |
| |
| const _C_link_t __hint = _ITER_NODE (__it); |
| |
| // if __hint is the right most child, or tree is empty |
| if (__hint == _C_end->_C_child [1]) { |
| |
| // if tree is not empty and __key is greater |
| // then insert on the right |
| if (_C_size && _C_cmp (__hint->_C_key (), _KeyOf ()(__v))) |
| return _C_insert (0, __hint, __v); |
| |
| // otherwise just insert |
| return insert (__v, __dup).first; |
| } |
| |
| // if __hint is past the end and __key is greater, |
| // then insert on the right |
| if (__hint == _C_end) { |
| if (_C_cmp (__hint->_C_child [1]->_C_key(), _KeyOf ()(__v))) |
| return _C_insert (0, __hint->_C_child [1], __v); |
| return insert (__v, __dup).first; |
| } |
| |
| // if __hint is the left most child and __key is less |
| // then insert on the left |
| if (__hint == _C_end->_C_child [0]) { |
| if (_C_cmp (_KeyOf ()(__v), __hint->_C_key ())) |
| return _C_insert (__hint, __hint, __v); |
| return insert (__v, __dup).first; |
| } |
| |
| const iterator __prev = __it++; |
| |
| // if __v falls between __prev and __it, then insert it there |
| if ( _C_cmp (_ITER_NODE (__prev)->_C_key (), _KeyOf ()(__v)) |
| && _C_cmp (_KeyOf ()(__v), _ITER_NODE (__it)->_C_key ())) { |
| |
| // if there is no right child of __prev, then __prev is the |
| // left child of __it and we insert to right of __prev |
| if (_C_link_t () == _ITER_NODE (__prev)->_C_child [1]) |
| return _C_insert (0, _ITER_NODE (__prev), __v); |
| |
| // otherwise we insert on the left of __it |
| return _C_insert (_ITER_NODE (__it), _ITER_NODE (__it), __v); |
| } |
| |
| // otherwise, do a full traversal |
| return insert (__v, __dup).first; |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (iterator __it) |
| { |
| _RWSTD_ASSERT_RANGE (begin (), __it); |
| |
| #ifdef _RWSTDDEBUG |
| |
| { // verify the consistency of the tree |
| size_type __two_logN = 0; |
| for (size_type __i = size () + 1; __i >>= 1; ++__two_logN); |
| |
| __two_logN *= 2; |
| |
| const size_type __depth = _C_depth (); |
| _RWSTD_ASSERT (__depth <= __two_logN); |
| } |
| |
| #endif // _RWSTDDEBUG |
| |
| if (__it == end ()) |
| return end (); |
| |
| // for notational convenience |
| const typename _C_node_t::_C_color_t _Red = _C_node_t::_C_red; |
| const typename _C_node_t::_C_color_t _Black = _C_node_t::_C_black; |
| const _C_link_t _Null = _C_link_t (); |
| |
| // returned iterator pointing to the element just past `it' |
| const iterator __next = ++iterator (__it); |
| |
| _C_link_t __z (_ITER_NODE (__it)); // `it's node |
| _C_link_t __y (__z); // node to be erased |
| _C_link_t __x; |
| |
| _C_link_t __x_parent = 0; |
| |
| |
| _RWSTD_ASSERT (_Null != __z); |
| |
| if (_Null == __y->_C_child [0]) { |
| // __z might have one non-null child. x |
| // holds that child (might be null though). |
| __x = __y->_C_child [1]; |
| } |
| else if (_Null == __y->_C_child [1]) { |
| // __z HAS one non-null child and __x points to it now. |
| __x = __y->_C_child [0]; |
| } |
| else { |
| // __z has two non-null children; make __y point to its immediate |
| // predecessor; __x will point to that predecessor's immediate |
| // predecessor. |
| __y = _C_node_t::_C_min (__y->_C_child [1]); |
| __x = __y->_C_child [1]; |
| } |
| |
| |
| if (__y != __z) { |
| // __y != __z ( means __y is in __z's left subtree ) |
| |
| // __y REPLACES __z |
| |
| // relink `y' in place of `z' (at this point __y |
| // is __z's immediate predecessor) |
| __z->_C_child [0]->_C_parent = __y; |
| __y->_C_child [0] = __z->_C_child [0]; |
| |
| if (__y != __z->_C_child [1]) { |
| // __y is predecessor but is not __z's direct child (right) |
| |
| // save y's former parent |
| __x_parent = __y->_C_parent; |
| |
| if (_Null != __x) |
| // if __x exists, __x's parent becomes __y's parent |
| __x->_C_parent = __y->_C_parent; |
| |
| // __y's former parent becomes __x's parent |
| __y->_C_parent->_C_child [0] = __x; |
| |
| // __y's right child gets __z's former right child |
| __y->_C_child [1] = __z->_C_child [1]; |
| |
| // __z's former right child gets __y as parent |
| __z->_C_child [1]->_C_parent = __y; |
| } |
| else { |
| |
| // in the case when __y is a direct child of __z, |
| // save __y value as __x's parent |
| __x_parent = __y; |
| |
| } |
| |
| if (_C_end->_C_parent == __z) { |
| // when deleted (__z) is root/end, then __y replaces root/end |
| _C_end->_C_parent = __y; |
| } |
| else { |
| // nice shot; |
| // when __z is not root/end, then its parent's |
| // child on __z's side becomes __y |
| __z->_C_parent->_C_child [__z->_C_parent->_C_child [0] != __z] |
| = __y; |
| } |
| |
| // Finally, y's parent changes to be z's parent; |
| // y is completely severed from its place |
| __y->_C_parent = __z->_C_parent; |
| |
| // swap y and z colors |
| _STD::swap (__y->_C_color, __z->_C_color); |
| |
| // __y now points to the deleted node |
| __y = __z; |
| } |
| else { |
| // (__y == __z) ( __z has had only one child (or maybe none) ) |
| |
| // __x REPLACES __z |
| |
| // save __y's/__z's parent (will later become x's parent) |
| __x_parent = __y->_C_parent; |
| |
| if (_Null != __x) { |
| // for a non-null __x, set its parent to point to __y's parent |
| __x->_C_parent = __y->_C_parent; |
| } |
| |
| if (_C_end->_C_parent == __z) { |
| // if __z was root, __x becomes new root... |
| _C_end->_C_parent = __x; |
| } |
| else |
| // ... otherwise, __x simply replaces __z and as such, |
| // __z's parent gets __x as right *or* left child |
| __z->_C_parent->_C_child [__z->_C_parent->_C_child [0] != __z] |
| = __x; |
| |
| // ADJUST TREE'S CORNERS |
| if (_C_end->_C_child [0] == __z) { |
| // __z is the left corner of the tree (smallest element) |
| |
| if (_Null == __z->_C_child [1]) |
| // when __z leaves the tree, leftmost will be invalidated; |
| // adjust left corner to point to __z's parent |
| _C_end->_C_child [0] = __z->_C_parent; |
| else { |
| // finding the successor of __z when __z's right subtree |
| // is not null; leftmost becomes that minimum/sucessor |
| _C_end->_C_child [0] = _C_node_t::_C_min (__x); |
| } |
| } |
| |
| if (_C_end->_C_child [1] == __z) { |
| // __z is in the right corner of the tree |
| |
| if (_Null == __z->_C_child [0]) |
| // when __z leaves the tree, right corner will be invalidated; |
| // adjust right corner to point to __z's parent |
| _C_end->_C_child [1] = __z->_C_parent; |
| else { |
| // otherwise, find z's predecessor in z's |
| // left subtree; that becomes the new rightmost element |
| _C_end->_C_child [1] = _C_node_t::_C_max (__x); |
| } |
| } |
| } |
| |
| |
| // COLOR SWAPPING |
| // (At this point __y has replaced __z and __z has been removed.) |
| |
| if (__y->_C_color != _Red) { |
| |
| // __y's color is not red; had it been red, we would have been |
| // done because it would not have altered the "blackness" |
| |
| |
| // At the loop's beginning, __x can be one of the two: |
| // 1. either the strict predecessor of __z's strict predecessor |
| // and in this case is down the subtree on z's left |
| // 2. is the node that replaced __z when __z has had only one |
| // child; that child has replaced __z and its changes |
| // will be propagated upward |
| |
| |
| while ( __x != _C_end->_C_parent |
| && (_Null == __x || __x->_C_color == _Black)) { |
| |
| #ifndef _RWSTD_NO_OPTIMIZE_SPEED |
| |
| if (__x == __x_parent->_C_child [0]) { |
| |
| // X ON THE LEFT SIDE OF ITS PARENT |
| |
| // __w is __x's brother/sibling |
| _C_link_t __w = __x_parent->_C_child [1]; |
| |
| if (_Red == __w->_C_color) { |
| __w->_C_color = _Black; |
| __x_parent->_C_color = _Red; |
| |
| _C_rol (__x_parent); |
| |
| __w = __x_parent->_C_child [1]; |
| } |
| |
| if ((_Null == __w->_C_child [0] || |
| _Black == __w->_C_child [0]->_C_color) && |
| (_Null == __w->_C_child [1] || |
| _Black == __w->_C_child [1]->_C_color)) { |
| // __x's sibling (__w) has black children (or null); |
| // color __x's sibling as RED and move up in the tree |
| __w->_C_color = _Red; |
| __x = __x_parent; |
| __x_parent = __x_parent->_C_parent; |
| } |
| else { |
| // __w (__x's sibling) has a child which is RED |
| |
| if (_Null == __w->_C_child [1] || |
| _Black == __w->_C_child [1]->_C_color) { |
| |
| // __w's left is RED |
| |
| if (_Null != __w->_C_child [0]) |
| // the left RED child becomes BLACK |
| __w->_C_child [0]->_C_color = _Black; |
| |
| // __w (x's sibling) becomes RED - color propagates up |
| __w->_C_color = _Red; |
| |
| _C_ror (__w); |
| |
| __w = __x_parent->_C_child [1]; |
| } |
| |
| __w->_C_color = __x_parent->_C_color; |
| __x_parent->_C_color = _Black; |
| |
| if (_Null != __w->_C_child [1]) |
| __w->_C_child [1]->_C_color = _Black; |
| |
| _C_rol (__x_parent); |
| |
| break; |
| } |
| } |
| else { |
| |
| // same as the if clause with "right" and "left" exchanged |
| |
| _C_link_t __w = __x_parent->_C_child [0]; |
| |
| if (_Red == __w->_C_color) { |
| __w->_C_color = _Black; |
| __x_parent->_C_color = _Red; |
| |
| _C_ror (__x_parent); |
| |
| __w = __x_parent->_C_child [0]; |
| } |
| |
| if ((_Null == __w->_C_child [1] || |
| _Black == __w->_C_child [1]->_C_color) && |
| (_Null == __w->_C_child [0] || |
| _Black == __w->_C_child [0]->_C_color)) { |
| __w->_C_color = _Red; |
| __x = __x_parent; |
| __x_parent = __x_parent->_C_parent; |
| } |
| else { |
| if (_Null == __w->_C_child [0] || |
| _Black == __w->_C_child [0]->_C_color) { |
| if (_Null != __w->_C_child [1]) |
| __w->_C_child [1]->_C_color = _Black; |
| |
| __w->_C_color = _Red; |
| |
| _C_rol (__w); |
| |
| __w = __x_parent->_C_child [0]; |
| } |
| |
| __w->_C_color = __x_parent->_C_color; |
| __x_parent->_C_color = _Black; |
| |
| if (_Null != __w->_C_child [0]) |
| __w->_C_child [0]->_C_color = _Black; |
| |
| _C_ror (__x_parent); |
| |
| break; |
| } |
| } |
| |
| #else // if defined (_RWSTD_NO_OPTIMIZE_SPEED) |
| |
| const bool __left = (__x == __x_parent->_C_child [0]); |
| const bool __right = !__left; |
| |
| _C_link_t __w = __x_parent->_C_child [__left]; |
| |
| if (_Red == __w->_C_color) { |
| __w->_C_color = _Black; |
| __x_parent->_C_color = _Red; |
| |
| // rotate right if `x' is a right child, otherwise right |
| _C_rotate (__x_parent, __right); |
| __w = __x_parent->_C_child [__left]; |
| } |
| |
| if ((_Null == __w->_C_child [__right] || |
| _Black == __w->_C_child [__right]->_C_color) && |
| (_Null == __w->_C_child [__left ] || |
| _Black == __w->_C_child [__left ]->_C_color)) { |
| __w->_C_color = _Red; |
| __x = __x_parent; |
| __x_parent = __x->_C_parent; |
| } |
| else { |
| if (_Null == __w->_C_child [__left] || |
| _Black == __w->_C_child [__left]->_C_color) { |
| |
| if (_Null != __w->_C_child [__right]) |
| __w->_C_child [__right]->_C_color = _Black; |
| |
| __w->_C_color = _Red; |
| _C_rotate (__w, __left); |
| __w = __x_parent->_C_child [__left]; |
| } |
| |
| if (_Null != __w) { |
| __w->_C_color = __x_parent->_C_color; |
| __x_parent->_C_color = _Black; |
| |
| if (_Null != __w->_C_child [__left]) |
| __w->_C_child [__left]->_C_color = _Black; |
| |
| _C_rotate (__x_parent, __right); |
| } |
| break; |
| } |
| |
| #endif // _RWSTD_NO_OPTIMIZE_SPEED |
| |
| } |
| |
| if (_Null != __x) |
| __x->_C_color = _Black; |
| |
| } |
| |
| _C_put_node (__y); |
| |
| --_C_size; |
| |
| return __next; |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| erase (const key_type &__x) |
| { |
| const _STD::pair<iterator, iterator> __p = equal_range(__x); |
| |
| const size_type __n = _DISTANCE (__p.first, __p.second, size_type); |
| |
| erase (__p.first, __p.second); |
| |
| return __n; |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_C_link_t |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| _C_copy (_C_link_t __x, _C_link_t __p) |
| { |
| // recursive structural copy |
| _C_link_t __res = __x; |
| |
| while (_C_link_t () != __x) { |
| const _C_link_t __y = _C_get_node (__x->_C_value); |
| if (__res == __x) |
| __res = __y; // save for return value |
| |
| __y->_C_color = __x->_C_color; |
| __y->_C_parent = __p; |
| __p->_C_child [0] = __y; |
| __y->_C_child [1] = _C_copy (__x->_C_child [1], __y); |
| __p = __y; |
| __x = __x->_C_child [0]; |
| } |
| __p->_C_child [0] = 0; |
| |
| return __res; |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| _C_erase (_C_link_t __x) |
| { |
| // recursively erase without rebalancing |
| |
| while (_C_link_t () != __x) { |
| _C_erase (__x->_C_child [1]); |
| _C_link_t __y = __x->_C_child [0]; |
| _C_put_node (__x); |
| __x = __y; |
| } |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| erase (iterator __first, iterator __last) |
| { |
| _RWSTD_ASSERT_RANGE (begin (), __first); |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| iterator __tmp; |
| |
| if (__first == begin () && __last == end () && _C_size) { |
| // erase the root node |
| _C_erase (_C_end->_C_parent); |
| |
| // set the parent pointer of an empty tree to null |
| _C_end->_C_parent = 0; |
| |
| // set the child pointers of an empty tree to end() |
| _C_end->_C_child [0] = |
| _C_end->_C_child [1] = _C_end; |
| |
| // set the size of the tree to 0 |
| _C_size = 0; |
| |
| // return end() |
| __tmp = end (); |
| } else |
| for (__tmp = end (); !(__first == __last); __tmp = erase (__first++)); |
| |
| return __tmp; |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| find (const key_type &__k) |
| { |
| const iterator __j = lower_bound (__k); |
| |
| return __j == end () || _C_cmp (__k, _ITER_NODE (__j)->_C_key ()) ? |
| end () : __j; |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| lower_bound (const key_type &__k) |
| { |
| _C_link_t __y = _C_end; |
| |
| for (_C_link_t __x = __y->_C_parent; _C_link_t () != __x; ) { |
| if (_C_cmp (__x->_C_key (), __k)) { |
| __x = __x->_C_child [1]; |
| } |
| else { |
| __y = __x; |
| __x = __x->_C_child [0]; |
| } |
| } |
| |
| return _C_make_iter (__y); |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| upper_bound (const key_type &__k) |
| { |
| _C_link_t __y = _C_end; |
| |
| for (_C_link_t __x = __y->_C_parent; _C_link_t () != __x; ) { |
| if (_C_cmp (__k, __x->_C_key ())) { |
| __y = __x; |
| __x = __x->_C_child [0]; |
| } |
| else |
| __x = __x->_C_child [1]; |
| } |
| |
| return _C_make_iter (__y); |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| _C_depth (const_iterator __it, size_type *__rank /* = 0 */) const |
| { |
| // for notational convenience |
| const typename _C_node_t::_C_color_t _Black = _C_node_t::_C_black; |
| const _C_link_t _Null = _C_link_t (); |
| |
| const _C_link_t __node = _ITER_NODE (__it); |
| |
| if (_Null == __node) |
| return 0; |
| |
| #ifdef _RWSTDDEBUG |
| |
| const typename _C_node_t::_C_color_t _Red = _C_node_t::_C_red; |
| |
| if (_Red == __node->_C_color) { |
| |
| // both children of every red node must be black |
| |
| const bool __left_child_black = |
| _Null == __node->_C_child [0] |
| || _Black == __node->_C_child [0]->_C_color; |
| |
| const bool __right_child_black = |
| _Null == __node->_C_child [1] |
| || _Black == __node->_C_child [1]->_C_color; |
| |
| _RWSTD_ASSERT (__left_child_black); |
| _RWSTD_ASSERT (__right_child_black); |
| } |
| |
| #endif // _RWDSDEBUG |
| |
| // every simple path from every node must contain the same number |
| // of black nodes; that means that every black node must either |
| // have zero or two children (of either color), or a single red |
| // child |
| |
| size_type __ranks [2]; |
| |
| if ( _Null == __node->_C_child [0] |
| || _Black == __node->_C_child [0]->_C_color) |
| __ranks [0] = 1; |
| else |
| __ranks [0] = 0; |
| |
| if ( _Null == __node->_C_child [1] |
| || _Black == __node->_C_child [1]->_C_color) |
| __ranks [1] = 1; |
| else |
| __ranks [1] = 0; |
| |
| const size_type __depth [] = { |
| _Null == __node->_C_child [0] ? |
| 0 : 1 + _C_depth (_C_make_iter (__node->_C_child [0]), __ranks + 0), |
| _Null == __node->_C_child [1] ? |
| 0 : 1 + _C_depth (_C_make_iter (__node->_C_child [1]), __ranks + 1) |
| }; |
| |
| _RWSTD_ASSERT (__ranks [0] == __ranks [1]); |
| |
| if (__rank) |
| *__rank += __ranks [0]; |
| |
| return __depth [__depth [0] < __depth [1]]; |
| } |
| |
| |
| template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc> |
| typename __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type |
| __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>:: |
| _C_level (const_iterator __it) const |
| { |
| if (_ITER_NODE (__it) == _C_end->_C_parent) |
| return 0; |
| |
| return 1 + _C_level (_C_make_iter (_ITER_NODE (__it)->_C_parent)); |
| } |
| |
| |
| } // namespace __rw |
