stl_tree.h revision 146897
197403Sobrien// RB tree implementation -*- C++ -*- 297403Sobrien 3146897Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 1897403Sobrien// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * 3297403Sobrien * Copyright (c) 1996,1997 3397403Sobrien * Silicon Graphics Computer Systems, Inc. 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Silicon Graphics makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien * 4397403Sobrien * 4497403Sobrien * Copyright (c) 1994 4597403Sobrien * Hewlett-Packard Company 4697403Sobrien * 4797403Sobrien * Permission to use, copy, modify, distribute and sell this software 4897403Sobrien * and its documentation for any purpose is hereby granted without fee, 4997403Sobrien * provided that the above copyright notice appear in all copies and 5097403Sobrien * that both that copyright notice and this permission notice appear 5197403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 5297403Sobrien * representations about the suitability of this software for any 5397403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5497403Sobrien * 5597403Sobrien * 5697403Sobrien */ 5797403Sobrien 5897403Sobrien/** @file stl_tree.h 5997403Sobrien * This is an internal header file, included by other library headers. 6097403Sobrien * You should not attempt to use it directly. 6197403Sobrien */ 6297403Sobrien 63132720Skan#ifndef _TREE_H 64132720Skan#define _TREE_H 1 6597403Sobrien 6697403Sobrien#include <bits/stl_algobase.h> 67132720Skan#include <bits/allocator.h> 6897403Sobrien#include <bits/stl_construct.h> 6997403Sobrien#include <bits/stl_function.h> 70132720Skan#include <bits/cpp_type_traits.h> 7197403Sobrien 7297403Sobriennamespace std 73132720Skan{ 74132720Skan // Red-black tree class, designed for use in implementing STL 75132720Skan // associative containers (set, multiset, map, and multimap). The 76132720Skan // insertion and deletion algorithms are based on those in Cormen, 77132720Skan // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 78132720Skan // 1990), except that 79132720Skan // 80132720Skan // (1) the header cell is maintained with links not only to the root 81132720Skan // but also to the leftmost node of the tree, to enable constant 82132720Skan // time begin(), and to the rightmost node of the tree, to enable 83132720Skan // linear time performance when used with the generic set algorithms 84132720Skan // (set_union, etc.) 85132720Skan // 86132720Skan // (2) when a node being deleted has two children its successor node 87132720Skan // is relinked into its place, rather than copied, so that the only 88132720Skan // iterators invalidated are those referring to the deleted node. 8997403Sobrien 90132720Skan enum _Rb_tree_color { _S_red = false, _S_black = true }; 91132720Skan 9297403Sobrien struct _Rb_tree_node_base 9397403Sobrien { 9497403Sobrien typedef _Rb_tree_node_base* _Base_ptr; 95132720Skan typedef const _Rb_tree_node_base* _Const_Base_ptr; 96132720Skan 97132720Skan _Rb_tree_color _M_color; 98132720Skan _Base_ptr _M_parent; 99132720Skan _Base_ptr _M_left; 100132720Skan _Base_ptr _M_right; 101132720Skan 102132720Skan static _Base_ptr 10397403Sobrien _S_minimum(_Base_ptr __x) 10497403Sobrien { 10597403Sobrien while (__x->_M_left != 0) __x = __x->_M_left; 10697403Sobrien return __x; 10797403Sobrien } 10897403Sobrien 109132720Skan static _Const_Base_ptr 110132720Skan _S_minimum(_Const_Base_ptr __x) 111132720Skan { 112132720Skan while (__x->_M_left != 0) __x = __x->_M_left; 113132720Skan return __x; 114132720Skan } 115132720Skan 116132720Skan static _Base_ptr 11797403Sobrien _S_maximum(_Base_ptr __x) 11897403Sobrien { 11997403Sobrien while (__x->_M_right != 0) __x = __x->_M_right; 12097403Sobrien return __x; 12197403Sobrien } 122132720Skan 123132720Skan static _Const_Base_ptr 124132720Skan _S_maximum(_Const_Base_ptr __x) 125132720Skan { 126132720Skan while (__x->_M_right != 0) __x = __x->_M_right; 127132720Skan return __x; 128132720Skan } 12997403Sobrien }; 13097403Sobrien 13197403Sobrien template<typename _Val> 13297403Sobrien struct _Rb_tree_node : public _Rb_tree_node_base 13397403Sobrien { 13497403Sobrien typedef _Rb_tree_node<_Val>* _Link_type; 13597403Sobrien _Val _M_value_field; 13697403Sobrien }; 13797403Sobrien 138132720Skan _Rb_tree_node_base* 139132720Skan _Rb_tree_increment(_Rb_tree_node_base* __x); 14097403Sobrien 141132720Skan const _Rb_tree_node_base* 142132720Skan _Rb_tree_increment(const _Rb_tree_node_base* __x); 14397403Sobrien 144132720Skan _Rb_tree_node_base* 145132720Skan _Rb_tree_decrement(_Rb_tree_node_base* __x); 14697403Sobrien 147132720Skan const _Rb_tree_node_base* 148132720Skan _Rb_tree_decrement(const _Rb_tree_node_base* __x); 149132720Skan 150132720Skan template<typename _Tp> 151132720Skan struct _Rb_tree_iterator 15297403Sobrien { 153132720Skan typedef _Tp value_type; 154132720Skan typedef _Tp& reference; 155132720Skan typedef _Tp* pointer; 15697403Sobrien 157132720Skan typedef bidirectional_iterator_tag iterator_category; 158132720Skan typedef ptrdiff_t difference_type; 15997403Sobrien 160132720Skan typedef _Rb_tree_iterator<_Tp> _Self; 161132720Skan typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 162132720Skan typedef _Rb_tree_node<_Tp>* _Link_type; 16397403Sobrien 164146897Skan _Rb_tree_iterator() 165146897Skan : _M_node() { } 166132720Skan 167132720Skan _Rb_tree_iterator(_Link_type __x) 168132720Skan : _M_node(__x) { } 169132720Skan 170132720Skan reference 171132720Skan operator*() const 172132720Skan { return static_cast<_Link_type>(_M_node)->_M_value_field; } 173132720Skan 174132720Skan pointer 175132720Skan operator->() const 176132720Skan { return &static_cast<_Link_type>(_M_node)->_M_value_field; } 177132720Skan 178132720Skan _Self& 179132720Skan operator++() 180132720Skan { 181132720Skan _M_node = _Rb_tree_increment(_M_node); 182132720Skan return *this; 18397403Sobrien } 18497403Sobrien 185132720Skan _Self 186132720Skan operator++(int) 18797403Sobrien { 18897403Sobrien _Self __tmp = *this; 189132720Skan _M_node = _Rb_tree_increment(_M_node); 19097403Sobrien return __tmp; 19197403Sobrien } 19297403Sobrien 193132720Skan _Self& 194132720Skan operator--() 19597403Sobrien { 196132720Skan _M_node = _Rb_tree_decrement(_M_node); 197132720Skan return *this; 198132720Skan } 199132720Skan 200132720Skan _Self 201132720Skan operator--(int) 202132720Skan { 20397403Sobrien _Self __tmp = *this; 204132720Skan _M_node = _Rb_tree_decrement(_M_node); 20597403Sobrien return __tmp; 20697403Sobrien } 207132720Skan 208132720Skan bool 209132720Skan operator==(const _Self& __x) const 210132720Skan { return _M_node == __x._M_node; } 211132720Skan 212132720Skan bool 213132720Skan operator!=(const _Self& __x) const 214132720Skan { return _M_node != __x._M_node; } 215132720Skan 216132720Skan _Base_ptr _M_node; 21797403Sobrien }; 21897403Sobrien 219132720Skan template<typename _Tp> 220132720Skan struct _Rb_tree_const_iterator 221132720Skan { 222132720Skan typedef _Tp value_type; 223132720Skan typedef const _Tp& reference; 224132720Skan typedef const _Tp* pointer; 22597403Sobrien 226132720Skan typedef _Rb_tree_iterator<_Tp> iterator; 22797403Sobrien 228132720Skan typedef bidirectional_iterator_tag iterator_category; 229132720Skan typedef ptrdiff_t difference_type; 23097403Sobrien 231132720Skan typedef _Rb_tree_const_iterator<_Tp> _Self; 232132720Skan typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 233132720Skan typedef const _Rb_tree_node<_Tp>* _Link_type; 23497403Sobrien 235146897Skan _Rb_tree_const_iterator() 236146897Skan : _M_node() { } 23797403Sobrien 238132720Skan _Rb_tree_const_iterator(_Link_type __x) 239132720Skan : _M_node(__x) { } 24097403Sobrien 241132720Skan _Rb_tree_const_iterator(const iterator& __it) 242132720Skan : _M_node(__it._M_node) { } 24397403Sobrien 244132720Skan reference 245132720Skan operator*() const 246132720Skan { return static_cast<_Link_type>(_M_node)->_M_value_field; } 24797403Sobrien 248132720Skan pointer 249132720Skan operator->() const 250132720Skan { return &static_cast<_Link_type>(_M_node)->_M_value_field; } 25197403Sobrien 252132720Skan _Self& 253132720Skan operator++() 25497403Sobrien { 255132720Skan _M_node = _Rb_tree_increment(_M_node); 256132720Skan return *this; 25797403Sobrien } 25897403Sobrien 259132720Skan _Self 260132720Skan operator++(int) 26197403Sobrien { 262132720Skan _Self __tmp = *this; 263132720Skan _M_node = _Rb_tree_increment(_M_node); 264132720Skan return __tmp; 26597403Sobrien } 266132720Skan 267132720Skan _Self& 268132720Skan operator--() 269132720Skan { 270132720Skan _M_node = _Rb_tree_decrement(_M_node); 271132720Skan return *this; 27297403Sobrien } 273132720Skan 274132720Skan _Self 275132720Skan operator--(int) 276132720Skan { 277132720Skan _Self __tmp = *this; 278132720Skan _M_node = _Rb_tree_decrement(_M_node); 279132720Skan return __tmp; 28097403Sobrien } 28197403Sobrien 282132720Skan bool 283132720Skan operator==(const _Self& __x) const 284132720Skan { return _M_node == __x._M_node; } 28597403Sobrien 286132720Skan bool 287132720Skan operator!=(const _Self& __x) const 288132720Skan { return _M_node != __x._M_node; } 28997403Sobrien 290132720Skan _Base_ptr _M_node; 291132720Skan }; 29297403Sobrien 293132720Skan template<typename _Val> 294132720Skan inline bool 295132720Skan operator==(const _Rb_tree_iterator<_Val>& __x, 296132720Skan const _Rb_tree_const_iterator<_Val>& __y) 297132720Skan { return __x._M_node == __y._M_node; } 29897403Sobrien 299132720Skan template<typename _Val> 300132720Skan inline bool 301132720Skan operator!=(const _Rb_tree_iterator<_Val>& __x, 302132720Skan const _Rb_tree_const_iterator<_Val>& __y) 303132720Skan { return __x._M_node != __y._M_node; } 30497403Sobrien 305132720Skan void 306132720Skan _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 307132720Skan _Rb_tree_node_base*& __root); 30897403Sobrien 309132720Skan void 310132720Skan _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 311132720Skan _Rb_tree_node_base*& __root); 31297403Sobrien 313132720Skan void 314132720Skan _Rb_tree_insert_and_rebalance(const bool __insert_left, 315132720Skan _Rb_tree_node_base* __x, 316132720Skan _Rb_tree_node_base* __p, 317132720Skan _Rb_tree_node_base& __header); 31897403Sobrien 319132720Skan _Rb_tree_node_base* 320132720Skan _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 321132720Skan _Rb_tree_node_base& __header); 32297403Sobrien 32397403Sobrien 324132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 325132720Skan typename _Compare, typename _Alloc = allocator<_Val> > 326132720Skan class _Rb_tree 32797403Sobrien { 328132720Skan typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other 329132720Skan _Node_allocator; 33097403Sobrien 33197403Sobrien protected: 33297403Sobrien typedef _Rb_tree_node_base* _Base_ptr; 333132720Skan typedef const _Rb_tree_node_base* _Const_Base_ptr; 33497403Sobrien typedef _Rb_tree_node<_Val> _Rb_tree_node; 335132720Skan 33697403Sobrien public: 33797403Sobrien typedef _Key key_type; 33897403Sobrien typedef _Val value_type; 33997403Sobrien typedef value_type* pointer; 34097403Sobrien typedef const value_type* const_pointer; 34197403Sobrien typedef value_type& reference; 34297403Sobrien typedef const value_type& const_reference; 34397403Sobrien typedef _Rb_tree_node* _Link_type; 344132720Skan typedef const _Rb_tree_node* _Const_Link_type; 34597403Sobrien typedef size_t size_type; 34697403Sobrien typedef ptrdiff_t difference_type; 347132720Skan typedef _Alloc allocator_type; 348132720Skan 349132720Skan allocator_type 350132720Skan get_allocator() const 351132720Skan { return *static_cast<const _Node_allocator*>(&this->_M_impl); } 352132720Skan 35397403Sobrien protected: 354132720Skan _Rb_tree_node* 355132720Skan _M_get_node() 356132720Skan { return _M_impl._Node_allocator::allocate(1); } 357132720Skan 358132720Skan void 359132720Skan _M_put_node(_Rb_tree_node* __p) 360132720Skan { _M_impl._Node_allocator::deallocate(__p, 1); } 361132720Skan 36297403Sobrien _Link_type 36397403Sobrien _M_create_node(const value_type& __x) 36497403Sobrien { 36597403Sobrien _Link_type __tmp = _M_get_node(); 366132720Skan try 367132720Skan { std::_Construct(&__tmp->_M_value_field, __x); } 36897403Sobrien catch(...) 36997403Sobrien { 370132720Skan _M_put_node(__tmp); 371132720Skan __throw_exception_again; 37297403Sobrien } 37397403Sobrien return __tmp; 37497403Sobrien } 375132720Skan 376132720Skan _Link_type 377132720Skan _M_clone_node(_Const_Link_type __x) 37897403Sobrien { 37997403Sobrien _Link_type __tmp = _M_create_node(__x->_M_value_field); 38097403Sobrien __tmp->_M_color = __x->_M_color; 38197403Sobrien __tmp->_M_left = 0; 38297403Sobrien __tmp->_M_right = 0; 38397403Sobrien return __tmp; 38497403Sobrien } 38597403Sobrien 38697403Sobrien void 38797403Sobrien destroy_node(_Link_type __p) 38897403Sobrien { 389132720Skan std::_Destroy(&__p->_M_value_field); 39097403Sobrien _M_put_node(__p); 39197403Sobrien } 39297403Sobrien 393132720Skan protected: 394132720Skan template<typename _Key_compare, 395132720Skan bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type> 396132720Skan struct _Rb_tree_impl : public _Node_allocator 397132720Skan { 398132720Skan _Key_compare _M_key_compare; 399132720Skan _Rb_tree_node_base _M_header; 400132720Skan size_type _M_node_count; // Keeps track of size of tree. 40197403Sobrien 402132720Skan _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), 403132720Skan const _Key_compare& __comp = _Key_compare()) 404132720Skan : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0) 405132720Skan { 406132720Skan this->_M_header._M_color = _S_red; 407132720Skan this->_M_header._M_parent = 0; 408132720Skan this->_M_header._M_left = &this->_M_header; 409132720Skan this->_M_header._M_right = &this->_M_header; 410132720Skan } 411132720Skan }; 41297403Sobrien 413132720Skan // Specialization for _Comparison types that are not capable of 414132720Skan // being base classes / super classes. 415132720Skan template<typename _Key_compare> 416132720Skan struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator 417132720Skan { 418132720Skan _Key_compare _M_key_compare; 419132720Skan _Rb_tree_node_base _M_header; 420132720Skan size_type _M_node_count; // Keeps track of size of tree. 42197403Sobrien 422132720Skan _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), 423132720Skan const _Key_compare& __comp = _Key_compare()) 424132720Skan : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0) 425132720Skan { 426132720Skan this->_M_header._M_color = _S_red; 427132720Skan this->_M_header._M_parent = 0; 428132720Skan this->_M_header._M_left = &this->_M_header; 429132720Skan this->_M_header._M_right = &this->_M_header; 430132720Skan } 431132720Skan }; 43297403Sobrien 433132720Skan _Rb_tree_impl<_Compare> _M_impl; 43497403Sobrien 435132720Skan protected: 436132720Skan _Base_ptr& 437132720Skan _M_root() 438132720Skan { return this->_M_impl._M_header._M_parent; } 43997403Sobrien 440132720Skan _Const_Base_ptr 441132720Skan _M_root() const 442132720Skan { return this->_M_impl._M_header._M_parent; } 44397403Sobrien 444132720Skan _Base_ptr& 445132720Skan _M_leftmost() 446132720Skan { return this->_M_impl._M_header._M_left; } 44797403Sobrien 448132720Skan _Const_Base_ptr 449132720Skan _M_leftmost() const 450132720Skan { return this->_M_impl._M_header._M_left; } 45197403Sobrien 452132720Skan _Base_ptr& 453132720Skan _M_rightmost() 454132720Skan { return this->_M_impl._M_header._M_right; } 45597403Sobrien 456132720Skan _Const_Base_ptr 457132720Skan _M_rightmost() const 458132720Skan { return this->_M_impl._M_header._M_right; } 45997403Sobrien 460132720Skan _Link_type 461132720Skan _M_begin() 462132720Skan { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 46397403Sobrien 464132720Skan _Const_Link_type 465132720Skan _M_begin() const 466132720Skan { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_parent); } 46797403Sobrien 468132720Skan _Link_type 469132720Skan _M_end() 470132720Skan { return static_cast<_Link_type>(&this->_M_impl._M_header); } 47197403Sobrien 472132720Skan _Const_Link_type 473132720Skan _M_end() const 474132720Skan { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 47597403Sobrien 476132720Skan static const_reference 477132720Skan _S_value(_Const_Link_type __x) 478132720Skan { return __x->_M_value_field; } 47997403Sobrien 480132720Skan static const _Key& 481132720Skan _S_key(_Const_Link_type __x) 482132720Skan { return _KeyOfValue()(_S_value(__x)); } 48397403Sobrien 484132720Skan static _Link_type 485132720Skan _S_left(_Base_ptr __x) 486132720Skan { return static_cast<_Link_type>(__x->_M_left); } 48797403Sobrien 488132720Skan static _Const_Link_type 489132720Skan _S_left(_Const_Base_ptr __x) 490132720Skan { return static_cast<_Const_Link_type>(__x->_M_left); } 491132720Skan 492132720Skan static _Link_type 493132720Skan _S_right(_Base_ptr __x) 494132720Skan { return static_cast<_Link_type>(__x->_M_right); } 495132720Skan 496132720Skan static _Const_Link_type 497132720Skan _S_right(_Const_Base_ptr __x) 498132720Skan { return static_cast<_Const_Link_type>(__x->_M_right); } 499132720Skan 500132720Skan static const_reference 501132720Skan _S_value(_Const_Base_ptr __x) 502132720Skan { return static_cast<_Const_Link_type>(__x)->_M_value_field; } 503132720Skan 504132720Skan static const _Key& 505132720Skan _S_key(_Const_Base_ptr __x) 506132720Skan { return _KeyOfValue()(_S_value(__x)); } 507132720Skan 508132720Skan static _Base_ptr 509132720Skan _S_minimum(_Base_ptr __x) 510132720Skan { return _Rb_tree_node_base::_S_minimum(__x); } 511132720Skan 512132720Skan static _Const_Base_ptr 513132720Skan _S_minimum(_Const_Base_ptr __x) 514132720Skan { return _Rb_tree_node_base::_S_minimum(__x); } 515132720Skan 516132720Skan static _Base_ptr 517132720Skan _S_maximum(_Base_ptr __x) 518132720Skan { return _Rb_tree_node_base::_S_maximum(__x); } 519132720Skan 520132720Skan static _Const_Base_ptr 521132720Skan _S_maximum(_Const_Base_ptr __x) 522132720Skan { return _Rb_tree_node_base::_S_maximum(__x); } 523132720Skan 52497403Sobrien public: 525132720Skan typedef _Rb_tree_iterator<value_type> iterator; 526132720Skan typedef _Rb_tree_const_iterator<value_type> const_iterator; 52797403Sobrien 528132720Skan typedef std::reverse_iterator<iterator> reverse_iterator; 529117397Skan typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 53097403Sobrien 53197403Sobrien private: 532132720Skan iterator 53397403Sobrien _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 53497403Sobrien 535132720Skan _Link_type 536132720Skan _M_copy(_Const_Link_type __x, _Link_type __p); 53797403Sobrien 538132720Skan void 53997403Sobrien _M_erase(_Link_type __x); 54097403Sobrien 54197403Sobrien public: 54297403Sobrien // allocation/deallocation 54397403Sobrien _Rb_tree() 544132720Skan { } 54597403Sobrien 54697403Sobrien _Rb_tree(const _Compare& __comp) 547132720Skan : _M_impl(allocator_type(), __comp) 548132720Skan { } 54997403Sobrien 55097403Sobrien _Rb_tree(const _Compare& __comp, const allocator_type& __a) 551132720Skan : _M_impl(__a, __comp) 552132720Skan { } 55397403Sobrien 554132720Skan _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) 555132720Skan : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare) 556132720Skan { 557132720Skan if (__x._M_root() != 0) 55897403Sobrien { 559132720Skan _M_root() = _M_copy(__x._M_begin(), _M_end()); 56097403Sobrien _M_leftmost() = _S_minimum(_M_root()); 56197403Sobrien _M_rightmost() = _S_maximum(_M_root()); 562132720Skan _M_impl._M_node_count = __x._M_impl._M_node_count; 56397403Sobrien } 56497403Sobrien } 56597403Sobrien 566132720Skan ~_Rb_tree() 567132720Skan { _M_erase(_M_begin()); } 56897403Sobrien 569132720Skan _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 57097403Sobrien operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x); 57197403Sobrien 57297403Sobrien // Accessors. 573132720Skan _Compare 574132720Skan key_comp() const 575132720Skan { return _M_impl._M_key_compare; } 57697403Sobrien 577132720Skan iterator 578132720Skan begin() 579132720Skan { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); } 58097403Sobrien 581132720Skan const_iterator 582132720Skan begin() const 583132720Skan { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); } 58497403Sobrien 585132720Skan iterator 586132720Skan end() 587132720Skan { return static_cast<_Link_type>(&this->_M_impl._M_header); } 58897403Sobrien 589132720Skan const_iterator 590132720Skan end() const 591132720Skan { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 59297403Sobrien 593132720Skan reverse_iterator 594132720Skan rbegin() 595132720Skan { return reverse_iterator(end()); } 59697403Sobrien 597132720Skan const_reverse_iterator 598132720Skan rbegin() const 599132720Skan { return const_reverse_iterator(end()); } 60097403Sobrien 601132720Skan reverse_iterator 602132720Skan rend() 603132720Skan { return reverse_iterator(begin()); } 60497403Sobrien 605132720Skan const_reverse_iterator 606132720Skan rend() const 607132720Skan { return const_reverse_iterator(begin()); } 60897403Sobrien 609132720Skan bool 610132720Skan empty() const 611132720Skan { return _M_impl._M_node_count == 0; } 61297403Sobrien 613132720Skan size_type 614132720Skan size() const 615132720Skan { return _M_impl._M_node_count; } 61697403Sobrien 617132720Skan size_type 618132720Skan max_size() const 619132720Skan { return size_type(-1); } 620132720Skan 621132720Skan void 622132720Skan swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t); 623132720Skan 62497403Sobrien // Insert/erase. 625132720Skan pair<iterator,bool> 62697403Sobrien insert_unique(const value_type& __x); 62797403Sobrien 628132720Skan iterator 62997403Sobrien insert_equal(const value_type& __x); 63097403Sobrien 631132720Skan iterator 63297403Sobrien insert_unique(iterator __position, const value_type& __x); 63397403Sobrien 634132720Skan iterator 63597403Sobrien insert_equal(iterator __position, const value_type& __x); 63697403Sobrien 63797403Sobrien template<typename _InputIterator> 638132720Skan void 63997403Sobrien insert_unique(_InputIterator __first, _InputIterator __last); 64097403Sobrien 64197403Sobrien template<typename _InputIterator> 642132720Skan void 64397403Sobrien insert_equal(_InputIterator __first, _InputIterator __last); 64497403Sobrien 645132720Skan void 64697403Sobrien erase(iterator __position); 64797403Sobrien 648132720Skan size_type 64997403Sobrien erase(const key_type& __x); 65097403Sobrien 651132720Skan void 65297403Sobrien erase(iterator __first, iterator __last); 65397403Sobrien 654132720Skan void 65597403Sobrien erase(const key_type* __first, const key_type* __last); 65697403Sobrien 657132720Skan void 658132720Skan clear() 65997403Sobrien { 660132720Skan _M_erase(_M_begin()); 661132720Skan _M_leftmost() = _M_end(); 662132720Skan _M_root() = 0; 663132720Skan _M_rightmost() = _M_end(); 664132720Skan _M_impl._M_node_count = 0; 665132720Skan } 66697403Sobrien 66797403Sobrien // Set operations. 668132720Skan iterator 66997403Sobrien find(const key_type& __x); 67097403Sobrien 671132720Skan const_iterator 67297403Sobrien find(const key_type& __x) const; 67397403Sobrien 674132720Skan size_type 67597403Sobrien count(const key_type& __x) const; 67697403Sobrien 677132720Skan iterator 67897403Sobrien lower_bound(const key_type& __x); 67997403Sobrien 680132720Skan const_iterator 68197403Sobrien lower_bound(const key_type& __x) const; 68297403Sobrien 683132720Skan iterator 68497403Sobrien upper_bound(const key_type& __x); 68597403Sobrien 686132720Skan const_iterator 68797403Sobrien upper_bound(const key_type& __x) const; 68897403Sobrien 689132720Skan pair<iterator,iterator> 69097403Sobrien equal_range(const key_type& __x); 69197403Sobrien 692132720Skan pair<const_iterator, const_iterator> 69397403Sobrien equal_range(const key_type& __x) const; 69497403Sobrien 69597403Sobrien // Debugging. 696132720Skan bool 69797403Sobrien __rb_verify() const; 69897403Sobrien }; 69997403Sobrien 700132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 70197403Sobrien typename _Compare, typename _Alloc> 702132720Skan inline bool 703132720Skan operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 70497403Sobrien const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 70597403Sobrien { 706132720Skan return __x.size() == __y.size() 707146897Skan && std::equal(__x.begin(), __x.end(), __y.begin()); 70897403Sobrien } 70997403Sobrien 710132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 71197403Sobrien typename _Compare, typename _Alloc> 712132720Skan inline bool 713132720Skan operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 71497403Sobrien const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 71597403Sobrien { 716146897Skan return std::lexicographical_compare(__x.begin(), __x.end(), 717146897Skan __y.begin(), __y.end()); 71897403Sobrien } 71997403Sobrien 720132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 72197403Sobrien typename _Compare, typename _Alloc> 722132720Skan inline bool 723132720Skan operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 724132720Skan const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 72597403Sobrien { return !(__x == __y); } 72697403Sobrien 727132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 72897403Sobrien typename _Compare, typename _Alloc> 729132720Skan inline bool 730132720Skan operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 731132720Skan const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 73297403Sobrien { return __y < __x; } 73397403Sobrien 734132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 73597403Sobrien typename _Compare, typename _Alloc> 736132720Skan inline bool 737132720Skan operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 738132720Skan const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 739132720Skan { return !(__y < __x); } 74097403Sobrien 741132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 74297403Sobrien typename _Compare, typename _Alloc> 743132720Skan inline bool 744132720Skan operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 745132720Skan const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 746132720Skan { return !(__x < __y); } 74797403Sobrien 748132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 74997403Sobrien typename _Compare, typename _Alloc> 750132720Skan inline void 751132720Skan swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 75297403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 75397403Sobrien { __x.swap(__y); } 75497403Sobrien 755132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 75697403Sobrien typename _Compare, typename _Alloc> 757132720Skan _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 75897403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 75997403Sobrien operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) 76097403Sobrien { 761132720Skan if (this != &__x) 76297403Sobrien { 76397403Sobrien // Note that _Key may be a constant type. 76497403Sobrien clear(); 765132720Skan _M_impl._M_key_compare = __x._M_impl._M_key_compare; 766132720Skan if (__x._M_root() != 0) 76797403Sobrien { 768132720Skan _M_root() = _M_copy(__x._M_begin(), _M_end()); 76997403Sobrien _M_leftmost() = _S_minimum(_M_root()); 77097403Sobrien _M_rightmost() = _S_maximum(_M_root()); 771132720Skan _M_impl._M_node_count = __x._M_impl._M_node_count; 77297403Sobrien } 77397403Sobrien } 77497403Sobrien return *this; 77597403Sobrien } 77697403Sobrien 777132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 77897403Sobrien typename _Compare, typename _Alloc> 77997403Sobrien typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 78097403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 781132720Skan _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 78297403Sobrien { 783132720Skan _Link_type __z = _M_create_node(__v); 784132720Skan bool __insert_left; 785132720Skan 786132720Skan __insert_left = __x != 0 || __p == _M_end() 787132720Skan || _M_impl._M_key_compare(_KeyOfValue()(__v), 788132720Skan _S_key(__p)); 789132720Skan 790132720Skan _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 791132720Skan this->_M_impl._M_header); 792132720Skan ++_M_impl._M_node_count; 79397403Sobrien return iterator(__z); 79497403Sobrien } 79597403Sobrien 796132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 79797403Sobrien typename _Compare, typename _Alloc> 79897403Sobrien typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 79997403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 80097403Sobrien insert_equal(const _Val& __v) 80197403Sobrien { 802132720Skan _Link_type __x = _M_begin(); 803132720Skan _Link_type __y = _M_end(); 804132720Skan while (__x != 0) 80597403Sobrien { 80697403Sobrien __y = __x; 807132720Skan __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 808132720Skan _S_left(__x) : _S_right(__x); 80997403Sobrien } 81097403Sobrien return _M_insert(__x, __y, __v); 81197403Sobrien } 81297403Sobrien 813132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 81497403Sobrien typename _Compare, typename _Alloc> 815132720Skan void 816132720Skan _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 817132720Skan swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) 818132720Skan { 819132720Skan if (_M_root() == 0) 820132720Skan { 821132720Skan if (__t._M_root() != 0) 822132720Skan { 823132720Skan _M_root() = __t._M_root(); 824132720Skan _M_leftmost() = __t._M_leftmost(); 825132720Skan _M_rightmost() = __t._M_rightmost(); 826132720Skan _M_root()->_M_parent = _M_end(); 827132720Skan 828132720Skan __t._M_root() = 0; 829132720Skan __t._M_leftmost() = __t._M_end(); 830132720Skan __t._M_rightmost() = __t._M_end(); 831132720Skan } 832132720Skan } 833132720Skan else if (__t._M_root() == 0) 834132720Skan { 835132720Skan __t._M_root() = _M_root(); 836132720Skan __t._M_leftmost() = _M_leftmost(); 837132720Skan __t._M_rightmost() = _M_rightmost(); 838132720Skan __t._M_root()->_M_parent = __t._M_end(); 839132720Skan 840132720Skan _M_root() = 0; 841132720Skan _M_leftmost() = _M_end(); 842132720Skan _M_rightmost() = _M_end(); 843132720Skan } 844132720Skan else 845132720Skan { 846132720Skan std::swap(_M_root(),__t._M_root()); 847132720Skan std::swap(_M_leftmost(),__t._M_leftmost()); 848132720Skan std::swap(_M_rightmost(),__t._M_rightmost()); 849132720Skan 850132720Skan _M_root()->_M_parent = _M_end(); 851132720Skan __t._M_root()->_M_parent = __t._M_end(); 852132720Skan } 853132720Skan // No need to swap header's color as it does not change. 854132720Skan std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 855132720Skan std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 856132720Skan } 857132720Skan 858132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 859132720Skan typename _Compare, typename _Alloc> 860132720Skan pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, 86197403Sobrien bool> 86297403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 86397403Sobrien insert_unique(const _Val& __v) 86497403Sobrien { 865132720Skan _Link_type __x = _M_begin(); 866132720Skan _Link_type __y = _M_end(); 86797403Sobrien bool __comp = true; 868132720Skan while (__x != 0) 86997403Sobrien { 87097403Sobrien __y = __x; 871132720Skan __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 87297403Sobrien __x = __comp ? _S_left(__x) : _S_right(__x); 87397403Sobrien } 874132720Skan iterator __j = iterator(__y); 87597403Sobrien if (__comp) 876132720Skan if (__j == begin()) 87797403Sobrien return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 87897403Sobrien else 87997403Sobrien --__j; 880132720Skan if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 88197403Sobrien return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 88297403Sobrien return pair<iterator,bool>(__j, false); 88397403Sobrien } 88497403Sobrien 885132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 88697403Sobrien typename _Compare, typename _Alloc> 887132720Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 88897403Sobrien _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 88997403Sobrien insert_unique(iterator __position, const _Val& __v) 89097403Sobrien { 891132720Skan if (__position._M_node == _M_leftmost()) 892132720Skan { 89397403Sobrien // begin() 894132720Skan if (size() > 0 895132720Skan && _M_impl._M_key_compare(_KeyOfValue()(__v), 896132720Skan _S_key(__position._M_node))) 89797403Sobrien return _M_insert(__position._M_node, __position._M_node, __v); 898132720Skan // First argument just needs to be non-null. 89997403Sobrien else 90097403Sobrien return insert_unique(__v).first; 901132720Skan } 902132720Skan else if (__position._M_node == _M_end()) 903132720Skan { 90497403Sobrien // end() 905132720Skan if (_M_impl._M_key_compare(_S_key(_M_rightmost()), 906132720Skan _KeyOfValue()(__v))) 90797403Sobrien return _M_insert(0, _M_rightmost(), __v); 90897403Sobrien else 90997403Sobrien return insert_unique(__v).first; 910132720Skan } 911132720Skan else 91297403Sobrien { 91397403Sobrien iterator __before = __position; 91497403Sobrien --__before; 915132720Skan if (_M_impl._M_key_compare(_S_key(__before._M_node), 916132720Skan _KeyOfValue()(__v)) 917132720Skan && _M_impl._M_key_compare(_KeyOfValue()(__v), 918132720Skan _S_key(__position._M_node))) 91997403Sobrien { 92097403Sobrien if (_S_right(__before._M_node) == 0) 921132720Skan return _M_insert(0, __before._M_node, __v); 92297403Sobrien else 92397403Sobrien return _M_insert(__position._M_node, __position._M_node, __v); 924132720Skan // First argument just needs to be non-null. 925132720Skan } 92697403Sobrien else 92797403Sobrien return insert_unique(__v).first; 92897403Sobrien } 92997403Sobrien } 93097403Sobrien 931132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 93297403Sobrien typename _Compare, typename _Alloc> 933132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 93497403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 93597403Sobrien insert_equal(iterator __position, const _Val& __v) 93697403Sobrien { 937132720Skan if (__position._M_node == _M_leftmost()) 938132720Skan { 93997403Sobrien // begin() 940132720Skan if (size() > 0 941132720Skan && !_M_impl._M_key_compare(_S_key(__position._M_node), 942132720Skan _KeyOfValue()(__v))) 94397403Sobrien return _M_insert(__position._M_node, __position._M_node, __v); 944132720Skan // first argument just needs to be non-null 94597403Sobrien else 94697403Sobrien return insert_equal(__v); 947132720Skan } 948132720Skan else if (__position._M_node == _M_end()) 94997403Sobrien { 95097403Sobrien // end() 951132720Skan if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 952132720Skan _S_key(_M_rightmost()))) 95397403Sobrien return _M_insert(0, _M_rightmost(), __v); 95497403Sobrien else 95597403Sobrien return insert_equal(__v); 956132720Skan } 957132720Skan else 95897403Sobrien { 95997403Sobrien iterator __before = __position; 96097403Sobrien --__before; 961132720Skan if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 962132720Skan _S_key(__before._M_node)) 963132720Skan && !_M_impl._M_key_compare(_S_key(__position._M_node), 964132720Skan _KeyOfValue()(__v))) 96597403Sobrien { 96697403Sobrien if (_S_right(__before._M_node) == 0) 967132720Skan return _M_insert(0, __before._M_node, __v); 96897403Sobrien else 96997403Sobrien return _M_insert(__position._M_node, __position._M_node, __v); 970132720Skan // First argument just needs to be non-null. 971132720Skan } 97297403Sobrien else 97397403Sobrien return insert_equal(__v); 97497403Sobrien } 97597403Sobrien } 97697403Sobrien 977132720Skan template<typename _Key, typename _Val, typename _KoV, 97897403Sobrien typename _Cmp, typename _Alloc> 97997403Sobrien template<class _II> 980132720Skan void 98197403Sobrien _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: 98297403Sobrien insert_equal(_II __first, _II __last) 98397403Sobrien { 98497403Sobrien for ( ; __first != __last; ++__first) 98597403Sobrien insert_equal(*__first); 98697403Sobrien } 98797403Sobrien 988132720Skan template<typename _Key, typename _Val, typename _KoV, 989132720Skan typename _Cmp, typename _Alloc> 99097403Sobrien template<class _II> 991132720Skan void 99297403Sobrien _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: 993132720Skan insert_unique(_II __first, _II __last) 99497403Sobrien { 99597403Sobrien for ( ; __first != __last; ++__first) 99697403Sobrien insert_unique(*__first); 99797403Sobrien } 99897403Sobrien 999132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 100097403Sobrien typename _Compare, typename _Alloc> 1001132720Skan inline void 100297403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position) 100397403Sobrien { 1004132720Skan _Link_type __y = 1005132720Skan static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node, 1006132720Skan this->_M_impl._M_header)); 100797403Sobrien destroy_node(__y); 1008132720Skan --_M_impl._M_node_count; 100997403Sobrien } 101097403Sobrien 1011132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 101297403Sobrien typename _Compare, typename _Alloc> 1013132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 101497403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x) 101597403Sobrien { 101697403Sobrien pair<iterator,iterator> __p = equal_range(__x); 1017132720Skan size_type __n = std::distance(__p.first, __p.second); 101897403Sobrien erase(__p.first, __p.second); 101997403Sobrien return __n; 102097403Sobrien } 102197403Sobrien 1022132720Skan template<typename _Key, typename _Val, typename _KoV, 102397403Sobrien typename _Compare, typename _Alloc> 1024132720Skan typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 102597403Sobrien _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>:: 1026132720Skan _M_copy(_Const_Link_type __x, _Link_type __p) 102797403Sobrien { 102897403Sobrien // Structural copy. __x and __p must be non-null. 102997403Sobrien _Link_type __top = _M_clone_node(__x); 103097403Sobrien __top->_M_parent = __p; 1031132720Skan 1032132720Skan try 103397403Sobrien { 103497403Sobrien if (__x->_M_right) 103597403Sobrien __top->_M_right = _M_copy(_S_right(__x), __top); 103697403Sobrien __p = __top; 103797403Sobrien __x = _S_left(__x); 1038132720Skan 1039132720Skan while (__x != 0) 104097403Sobrien { 104197403Sobrien _Link_type __y = _M_clone_node(__x); 104297403Sobrien __p->_M_left = __y; 104397403Sobrien __y->_M_parent = __p; 104497403Sobrien if (__x->_M_right) 104597403Sobrien __y->_M_right = _M_copy(_S_right(__x), __y); 104697403Sobrien __p = __y; 104797403Sobrien __x = _S_left(__x); 104897403Sobrien } 104997403Sobrien } 105097403Sobrien catch(...) 105197403Sobrien { 105297403Sobrien _M_erase(__top); 1053132720Skan __throw_exception_again; 105497403Sobrien } 105597403Sobrien return __top; 105697403Sobrien } 105797403Sobrien 1058132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 105997403Sobrien typename _Compare, typename _Alloc> 1060132720Skan void 106197403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x) 106297403Sobrien { 106397403Sobrien // Erase without rebalancing. 1064132720Skan while (__x != 0) 106597403Sobrien { 106697403Sobrien _M_erase(_S_right(__x)); 106797403Sobrien _Link_type __y = _S_left(__x); 106897403Sobrien destroy_node(__x); 106997403Sobrien __x = __y; 107097403Sobrien } 107197403Sobrien } 107297403Sobrien 1073132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 107497403Sobrien typename _Compare, typename _Alloc> 1075132720Skan void 107697403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 107797403Sobrien erase(iterator __first, iterator __last) 107897403Sobrien { 107997403Sobrien if (__first == begin() && __last == end()) 108097403Sobrien clear(); 108197403Sobrien else 108297403Sobrien while (__first != __last) erase(__first++); 108397403Sobrien } 108497403Sobrien 1085132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 108697403Sobrien typename _Compare, typename _Alloc> 1087132720Skan void 108897403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1089132720Skan erase(const _Key* __first, const _Key* __last) 1090132720Skan { 1091132720Skan while (__first != __last) 1092132720Skan erase(*__first++); 109397403Sobrien } 109497403Sobrien 1095132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 109697403Sobrien typename _Compare, typename _Alloc> 1097132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 109897403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) 109997403Sobrien { 1100132720Skan _Link_type __x = _M_begin(); // Current node. 1101132720Skan _Link_type __y = _M_end(); // Last node which is not less than __k. 1102132720Skan 1103132720Skan while (__x != 0) 1104132720Skan if (!_M_impl._M_key_compare(_S_key(__x), __k)) 110597403Sobrien __y = __x, __x = _S_left(__x); 110697403Sobrien else 110797403Sobrien __x = _S_right(__x); 1108132720Skan 1109132720Skan iterator __j = iterator(__y); 1110132720Skan return (__j == end() 1111132720Skan || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; 111297403Sobrien } 1113132720Skan 1114132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 111597403Sobrien typename _Compare, typename _Alloc> 1116132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 111797403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 111897403Sobrien find(const _Key& __k) const 111997403Sobrien { 1120132720Skan _Const_Link_type __x = _M_begin(); // Current node. 1121132720Skan _Const_Link_type __y = _M_end(); // Last node which is not less than __k. 1122132720Skan 1123132720Skan while (__x != 0) 112497403Sobrien { 1125132720Skan if (!_M_impl._M_key_compare(_S_key(__x), __k)) 112697403Sobrien __y = __x, __x = _S_left(__x); 112797403Sobrien else 112897403Sobrien __x = _S_right(__x); 1129132720Skan } 1130132720Skan const_iterator __j = const_iterator(__y); 1131132720Skan return (__j == end() 1132132720Skan || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; 113397403Sobrien } 113497403Sobrien 1135132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 113697403Sobrien typename _Compare, typename _Alloc> 1137132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 113897403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 113997403Sobrien count(const _Key& __k) const 114097403Sobrien { 114197403Sobrien pair<const_iterator, const_iterator> __p = equal_range(__k); 1142132720Skan const size_type __n = std::distance(__p.first, __p.second); 114397403Sobrien return __n; 114497403Sobrien } 114597403Sobrien 1146132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 114797403Sobrien typename _Compare, typename _Alloc> 1148132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 114997403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 115097403Sobrien lower_bound(const _Key& __k) 115197403Sobrien { 1152132720Skan _Link_type __x = _M_begin(); // Current node. 1153132720Skan _Link_type __y = _M_end(); // Last node which is not less than __k. 1154132720Skan 1155132720Skan while (__x != 0) 1156132720Skan if (!_M_impl._M_key_compare(_S_key(__x), __k)) 115797403Sobrien __y = __x, __x = _S_left(__x); 115897403Sobrien else 115997403Sobrien __x = _S_right(__x); 1160132720Skan 116197403Sobrien return iterator(__y); 116297403Sobrien } 116397403Sobrien 1164132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 116597403Sobrien typename _Compare, typename _Alloc> 1166132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 116797403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 116897403Sobrien lower_bound(const _Key& __k) const 116997403Sobrien { 1170132720Skan _Const_Link_type __x = _M_begin(); // Current node. 1171132720Skan _Const_Link_type __y = _M_end(); // Last node which is not less than __k. 1172132720Skan 1173132720Skan while (__x != 0) 1174132720Skan if (!_M_impl._M_key_compare(_S_key(__x), __k)) 117597403Sobrien __y = __x, __x = _S_left(__x); 117697403Sobrien else 117797403Sobrien __x = _S_right(__x); 1178132720Skan 117997403Sobrien return const_iterator(__y); 118097403Sobrien } 118197403Sobrien 1182132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 118397403Sobrien typename _Compare, typename _Alloc> 1184132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 118597403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 118697403Sobrien upper_bound(const _Key& __k) 118797403Sobrien { 1188132720Skan _Link_type __x = _M_begin(); // Current node. 1189132720Skan _Link_type __y = _M_end(); // Last node which is greater than __k. 1190132720Skan 1191132720Skan while (__x != 0) 1192132720Skan if (_M_impl._M_key_compare(__k, _S_key(__x))) 119397403Sobrien __y = __x, __x = _S_left(__x); 119497403Sobrien else 119597403Sobrien __x = _S_right(__x); 1196132720Skan 119797403Sobrien return iterator(__y); 119897403Sobrien } 119997403Sobrien 1200132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 120197403Sobrien typename _Compare, typename _Alloc> 1202132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 120397403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 120497403Sobrien upper_bound(const _Key& __k) const 120597403Sobrien { 1206132720Skan _Const_Link_type __x = _M_begin(); // Current node. 1207132720Skan _Const_Link_type __y = _M_end(); // Last node which is greater than __k. 1208132720Skan 1209132720Skan while (__x != 0) 1210132720Skan if (_M_impl._M_key_compare(__k, _S_key(__x))) 121197403Sobrien __y = __x, __x = _S_left(__x); 121297403Sobrien else 121397403Sobrien __x = _S_right(__x); 1214132720Skan 121597403Sobrien return const_iterator(__y); 121697403Sobrien } 121797403Sobrien 1218132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 121997403Sobrien typename _Compare, typename _Alloc> 1220132720Skan inline 1221132720Skan pair<typename _Rb_tree<_Key,_Val,_KeyOfValue, 1222132720Skan _Compare,_Alloc>::iterator, 1223132720Skan typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator> 122497403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 122597403Sobrien equal_range(const _Key& __k) 122697403Sobrien { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); } 122797403Sobrien 1228132720Skan template<typename _Key, typename _Val, typename _KoV, 122997403Sobrien typename _Compare, typename _Alloc> 1230132720Skan inline 1231132720Skan pair<typename _Rb_tree<_Key, _Val, _KoV, 1232132720Skan _Compare, _Alloc>::const_iterator, 1233132720Skan typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator> 1234132720Skan _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 1235132720Skan equal_range(const _Key& __k) const 1236132720Skan { return pair<const_iterator, const_iterator>(lower_bound(__k), 1237132720Skan upper_bound(__k)); } 123897403Sobrien 1239132720Skan unsigned int 1240132720Skan _Rb_tree_black_count(const _Rb_tree_node_base* __node, 1241132720Skan const _Rb_tree_node_base* __root); 124297403Sobrien 1243132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 124497403Sobrien typename _Compare, typename _Alloc> 1245132720Skan bool 124697403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 124797403Sobrien { 1248132720Skan if (_M_impl._M_node_count == 0 || begin() == end()) 1249132720Skan return _M_impl._M_node_count == 0 && begin() == end() 1250132720Skan && this->_M_impl._M_header._M_left == _M_end() 1251132720Skan && this->_M_impl._M_header._M_right == _M_end(); 1252132720Skan 1253132720Skan unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 1254132720Skan for (const_iterator __it = begin(); __it != end(); ++__it) 1255132720Skan { 1256132720Skan _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 1257132720Skan _Const_Link_type __L = _S_left(__x); 1258132720Skan _Const_Link_type __R = _S_right(__x); 1259132720Skan 1260132720Skan if (__x->_M_color == _S_red) 1261132720Skan if ((__L && __L->_M_color == _S_red) 1262132720Skan || (__R && __R->_M_color == _S_red)) 1263132720Skan return false; 1264132720Skan 1265132720Skan if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 126697403Sobrien return false; 1267132720Skan if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 1268132720Skan return false; 126997403Sobrien 1270132720Skan if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 1271132720Skan return false; 1272132720Skan } 1273132720Skan 1274132720Skan if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 1275132720Skan return false; 1276132720Skan if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 1277132720Skan return false; 1278132720Skan return true; 127997403Sobrien } 1280132720Skan} // namespace std 128197403Sobrien 1282132720Skan#endif 1283132720Skan 1284