197403Sobrien// RB tree implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * 3397403Sobrien * Copyright (c) 1996,1997 3497403Sobrien * Silicon Graphics Computer Systems, Inc. 3597403Sobrien * 3697403Sobrien * Permission to use, copy, modify, distribute and sell this software 3797403Sobrien * and its documentation for any purpose is hereby granted without fee, 3897403Sobrien * provided that the above copyright notice appear in all copies and 3997403Sobrien * that both that copyright notice and this permission notice appear 4097403Sobrien * in supporting documentation. Silicon Graphics makes no 4197403Sobrien * representations about the suitability of this software for any 4297403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4397403Sobrien * 4497403Sobrien * 4597403Sobrien * Copyright (c) 1994 4697403Sobrien * Hewlett-Packard Company 4797403Sobrien * 4897403Sobrien * Permission to use, copy, modify, distribute and sell this software 4997403Sobrien * and its documentation for any purpose is hereby granted without fee, 5097403Sobrien * provided that the above copyright notice appear in all copies and 5197403Sobrien * that both that copyright notice and this permission notice appear 5297403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 5397403Sobrien * representations about the suitability of this software for any 5497403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5597403Sobrien * 5697403Sobrien * 5797403Sobrien */ 5897403Sobrien 5997403Sobrien/** @file stl_tree.h 6097403Sobrien * This is an internal header file, included by other library headers. 6197403Sobrien * You should not attempt to use it directly. 6297403Sobrien */ 6397403Sobrien 64132720Skan#ifndef _TREE_H 65132720Skan#define _TREE_H 1 6697403Sobrien 67258429Spfg#pragma GCC system_header 68258429Spfg 6997403Sobrien#include <bits/stl_algobase.h> 70132720Skan#include <bits/allocator.h> 7197403Sobrien#include <bits/stl_construct.h> 7297403Sobrien#include <bits/stl_function.h> 73132720Skan#include <bits/cpp_type_traits.h> 7497403Sobrien 75169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 76169691Skan 77132720Skan // Red-black tree class, designed for use in implementing STL 78132720Skan // associative containers (set, multiset, map, and multimap). The 79132720Skan // insertion and deletion algorithms are based on those in Cormen, 80132720Skan // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 81132720Skan // 1990), except that 82132720Skan // 83132720Skan // (1) the header cell is maintained with links not only to the root 84132720Skan // but also to the leftmost node of the tree, to enable constant 85132720Skan // time begin(), and to the rightmost node of the tree, to enable 86132720Skan // linear time performance when used with the generic set algorithms 87132720Skan // (set_union, etc.) 88132720Skan // 89132720Skan // (2) when a node being deleted has two children its successor node 90132720Skan // is relinked into its place, rather than copied, so that the only 91132720Skan // iterators invalidated are those referring to the deleted node. 9297403Sobrien 93132720Skan enum _Rb_tree_color { _S_red = false, _S_black = true }; 94132720Skan 9597403Sobrien struct _Rb_tree_node_base 9697403Sobrien { 9797403Sobrien typedef _Rb_tree_node_base* _Base_ptr; 98132720Skan typedef const _Rb_tree_node_base* _Const_Base_ptr; 99132720Skan 100132720Skan _Rb_tree_color _M_color; 101132720Skan _Base_ptr _M_parent; 102132720Skan _Base_ptr _M_left; 103132720Skan _Base_ptr _M_right; 104132720Skan 105132720Skan static _Base_ptr 10697403Sobrien _S_minimum(_Base_ptr __x) 10797403Sobrien { 10897403Sobrien while (__x->_M_left != 0) __x = __x->_M_left; 10997403Sobrien return __x; 11097403Sobrien } 11197403Sobrien 112132720Skan static _Const_Base_ptr 113132720Skan _S_minimum(_Const_Base_ptr __x) 114132720Skan { 115132720Skan while (__x->_M_left != 0) __x = __x->_M_left; 116132720Skan return __x; 117132720Skan } 118132720Skan 119132720Skan static _Base_ptr 12097403Sobrien _S_maximum(_Base_ptr __x) 12197403Sobrien { 12297403Sobrien while (__x->_M_right != 0) __x = __x->_M_right; 12397403Sobrien return __x; 12497403Sobrien } 125132720Skan 126132720Skan static _Const_Base_ptr 127132720Skan _S_maximum(_Const_Base_ptr __x) 128132720Skan { 129132720Skan while (__x->_M_right != 0) __x = __x->_M_right; 130132720Skan return __x; 131132720Skan } 13297403Sobrien }; 13397403Sobrien 13497403Sobrien template<typename _Val> 13597403Sobrien struct _Rb_tree_node : public _Rb_tree_node_base 13697403Sobrien { 13797403Sobrien typedef _Rb_tree_node<_Val>* _Link_type; 13897403Sobrien _Val _M_value_field; 13997403Sobrien }; 14097403Sobrien 141132720Skan _Rb_tree_node_base* 142132720Skan _Rb_tree_increment(_Rb_tree_node_base* __x); 14397403Sobrien 144132720Skan const _Rb_tree_node_base* 145132720Skan _Rb_tree_increment(const _Rb_tree_node_base* __x); 14697403Sobrien 147132720Skan _Rb_tree_node_base* 148132720Skan _Rb_tree_decrement(_Rb_tree_node_base* __x); 14997403Sobrien 150132720Skan const _Rb_tree_node_base* 151132720Skan _Rb_tree_decrement(const _Rb_tree_node_base* __x); 152132720Skan 153132720Skan template<typename _Tp> 154132720Skan struct _Rb_tree_iterator 15597403Sobrien { 156132720Skan typedef _Tp value_type; 157132720Skan typedef _Tp& reference; 158132720Skan typedef _Tp* pointer; 15997403Sobrien 160132720Skan typedef bidirectional_iterator_tag iterator_category; 161132720Skan typedef ptrdiff_t difference_type; 16297403Sobrien 163132720Skan typedef _Rb_tree_iterator<_Tp> _Self; 164132720Skan typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 165132720Skan typedef _Rb_tree_node<_Tp>* _Link_type; 16697403Sobrien 167146897Skan _Rb_tree_iterator() 168146897Skan : _M_node() { } 169132720Skan 170169691Skan explicit 171132720Skan _Rb_tree_iterator(_Link_type __x) 172132720Skan : _M_node(__x) { } 173132720Skan 174132720Skan reference 175132720Skan operator*() const 176132720Skan { return static_cast<_Link_type>(_M_node)->_M_value_field; } 177132720Skan 178132720Skan pointer 179132720Skan operator->() const 180132720Skan { return &static_cast<_Link_type>(_M_node)->_M_value_field; } 181132720Skan 182132720Skan _Self& 183132720Skan operator++() 184132720Skan { 185132720Skan _M_node = _Rb_tree_increment(_M_node); 186132720Skan return *this; 18797403Sobrien } 18897403Sobrien 189132720Skan _Self 190132720Skan operator++(int) 19197403Sobrien { 19297403Sobrien _Self __tmp = *this; 193132720Skan _M_node = _Rb_tree_increment(_M_node); 19497403Sobrien return __tmp; 19597403Sobrien } 19697403Sobrien 197132720Skan _Self& 198132720Skan operator--() 19997403Sobrien { 200132720Skan _M_node = _Rb_tree_decrement(_M_node); 201132720Skan return *this; 202132720Skan } 203132720Skan 204132720Skan _Self 205132720Skan operator--(int) 206132720Skan { 20797403Sobrien _Self __tmp = *this; 208132720Skan _M_node = _Rb_tree_decrement(_M_node); 20997403Sobrien return __tmp; 21097403Sobrien } 211132720Skan 212132720Skan bool 213132720Skan operator==(const _Self& __x) const 214132720Skan { return _M_node == __x._M_node; } 215132720Skan 216132720Skan bool 217132720Skan operator!=(const _Self& __x) const 218132720Skan { return _M_node != __x._M_node; } 219132720Skan 220132720Skan _Base_ptr _M_node; 22197403Sobrien }; 22297403Sobrien 223132720Skan template<typename _Tp> 224132720Skan struct _Rb_tree_const_iterator 225132720Skan { 226132720Skan typedef _Tp value_type; 227132720Skan typedef const _Tp& reference; 228132720Skan typedef const _Tp* pointer; 22997403Sobrien 230132720Skan typedef _Rb_tree_iterator<_Tp> iterator; 23197403Sobrien 232132720Skan typedef bidirectional_iterator_tag iterator_category; 233132720Skan typedef ptrdiff_t difference_type; 23497403Sobrien 235132720Skan typedef _Rb_tree_const_iterator<_Tp> _Self; 236132720Skan typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 237132720Skan typedef const _Rb_tree_node<_Tp>* _Link_type; 23897403Sobrien 239146897Skan _Rb_tree_const_iterator() 240146897Skan : _M_node() { } 24197403Sobrien 242169691Skan explicit 243132720Skan _Rb_tree_const_iterator(_Link_type __x) 244132720Skan : _M_node(__x) { } 24597403Sobrien 246132720Skan _Rb_tree_const_iterator(const iterator& __it) 247132720Skan : _M_node(__it._M_node) { } 24897403Sobrien 249132720Skan reference 250132720Skan operator*() const 251132720Skan { return static_cast<_Link_type>(_M_node)->_M_value_field; } 25297403Sobrien 253132720Skan pointer 254132720Skan operator->() const 255132720Skan { return &static_cast<_Link_type>(_M_node)->_M_value_field; } 25697403Sobrien 257132720Skan _Self& 258132720Skan operator++() 25997403Sobrien { 260132720Skan _M_node = _Rb_tree_increment(_M_node); 261132720Skan return *this; 26297403Sobrien } 26397403Sobrien 264132720Skan _Self 265132720Skan operator++(int) 26697403Sobrien { 267132720Skan _Self __tmp = *this; 268132720Skan _M_node = _Rb_tree_increment(_M_node); 269132720Skan return __tmp; 27097403Sobrien } 271132720Skan 272132720Skan _Self& 273132720Skan operator--() 274132720Skan { 275132720Skan _M_node = _Rb_tree_decrement(_M_node); 276132720Skan return *this; 27797403Sobrien } 278132720Skan 279132720Skan _Self 280132720Skan operator--(int) 281132720Skan { 282132720Skan _Self __tmp = *this; 283132720Skan _M_node = _Rb_tree_decrement(_M_node); 284132720Skan return __tmp; 28597403Sobrien } 28697403Sobrien 287132720Skan bool 288132720Skan operator==(const _Self& __x) const 289132720Skan { return _M_node == __x._M_node; } 29097403Sobrien 291132720Skan bool 292132720Skan operator!=(const _Self& __x) const 293132720Skan { return _M_node != __x._M_node; } 29497403Sobrien 295132720Skan _Base_ptr _M_node; 296132720Skan }; 29797403Sobrien 298132720Skan template<typename _Val> 299132720Skan inline bool 300132720Skan operator==(const _Rb_tree_iterator<_Val>& __x, 301132720Skan const _Rb_tree_const_iterator<_Val>& __y) 302132720Skan { return __x._M_node == __y._M_node; } 30397403Sobrien 304132720Skan template<typename _Val> 305132720Skan inline bool 306132720Skan operator!=(const _Rb_tree_iterator<_Val>& __x, 307132720Skan const _Rb_tree_const_iterator<_Val>& __y) 308132720Skan { return __x._M_node != __y._M_node; } 30997403Sobrien 310132720Skan void 311132720Skan _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 312132720Skan _Rb_tree_node_base*& __root); 31397403Sobrien 314132720Skan void 315132720Skan _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 316132720Skan _Rb_tree_node_base*& __root); 31797403Sobrien 318132720Skan void 319132720Skan _Rb_tree_insert_and_rebalance(const bool __insert_left, 320132720Skan _Rb_tree_node_base* __x, 321132720Skan _Rb_tree_node_base* __p, 322132720Skan _Rb_tree_node_base& __header); 32397403Sobrien 324132720Skan _Rb_tree_node_base* 325132720Skan _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 326132720Skan _Rb_tree_node_base& __header); 32797403Sobrien 32897403Sobrien 329132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 330132720Skan typename _Compare, typename _Alloc = allocator<_Val> > 331132720Skan class _Rb_tree 33297403Sobrien { 333132720Skan typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other 334132720Skan _Node_allocator; 33597403Sobrien 33697403Sobrien protected: 33797403Sobrien typedef _Rb_tree_node_base* _Base_ptr; 338132720Skan typedef const _Rb_tree_node_base* _Const_Base_ptr; 33997403Sobrien typedef _Rb_tree_node<_Val> _Rb_tree_node; 340132720Skan 34197403Sobrien public: 34297403Sobrien typedef _Key key_type; 34397403Sobrien typedef _Val value_type; 34497403Sobrien typedef value_type* pointer; 34597403Sobrien typedef const value_type* const_pointer; 34697403Sobrien typedef value_type& reference; 34797403Sobrien typedef const value_type& const_reference; 34897403Sobrien typedef _Rb_tree_node* _Link_type; 349132720Skan typedef const _Rb_tree_node* _Const_Link_type; 35097403Sobrien typedef size_t size_type; 35197403Sobrien typedef ptrdiff_t difference_type; 352132720Skan typedef _Alloc allocator_type; 353132720Skan 354169691Skan _Node_allocator& 355169691Skan _M_get_Node_allocator() 356169691Skan { return *static_cast<_Node_allocator*>(&this->_M_impl); } 357169691Skan 358169691Skan const _Node_allocator& 359169691Skan _M_get_Node_allocator() const 360132720Skan { return *static_cast<const _Node_allocator*>(&this->_M_impl); } 361132720Skan 362169691Skan allocator_type 363169691Skan get_allocator() const 364169691Skan { return allocator_type(_M_get_Node_allocator()); } 365169691Skan 36697403Sobrien protected: 367132720Skan _Rb_tree_node* 368132720Skan _M_get_node() 369132720Skan { return _M_impl._Node_allocator::allocate(1); } 370132720Skan 371132720Skan void 372132720Skan _M_put_node(_Rb_tree_node* __p) 373132720Skan { _M_impl._Node_allocator::deallocate(__p, 1); } 374132720Skan 37597403Sobrien _Link_type 37697403Sobrien _M_create_node(const value_type& __x) 37797403Sobrien { 37897403Sobrien _Link_type __tmp = _M_get_node(); 379132720Skan try 380169691Skan { get_allocator().construct(&__tmp->_M_value_field, __x); } 38197403Sobrien catch(...) 38297403Sobrien { 383132720Skan _M_put_node(__tmp); 384132720Skan __throw_exception_again; 38597403Sobrien } 38697403Sobrien return __tmp; 38797403Sobrien } 388132720Skan 389132720Skan _Link_type 390132720Skan _M_clone_node(_Const_Link_type __x) 39197403Sobrien { 39297403Sobrien _Link_type __tmp = _M_create_node(__x->_M_value_field); 39397403Sobrien __tmp->_M_color = __x->_M_color; 39497403Sobrien __tmp->_M_left = 0; 39597403Sobrien __tmp->_M_right = 0; 39697403Sobrien return __tmp; 39797403Sobrien } 39897403Sobrien 39997403Sobrien void 400169691Skan _M_destroy_node(_Link_type __p) 40197403Sobrien { 402169691Skan get_allocator().destroy(&__p->_M_value_field); 40397403Sobrien _M_put_node(__p); 40497403Sobrien } 40597403Sobrien 406132720Skan protected: 407132720Skan template<typename _Key_compare, 408169691Skan bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value> 409132720Skan struct _Rb_tree_impl : public _Node_allocator 410132720Skan { 411132720Skan _Key_compare _M_key_compare; 412132720Skan _Rb_tree_node_base _M_header; 413132720Skan size_type _M_node_count; // Keeps track of size of tree. 41497403Sobrien 415236829Spfg _Rb_tree_impl() 416236829Spfg : _Node_allocator(), _M_key_compare(), _M_header(), 417169691Skan _M_node_count(0) 418236829Spfg { _M_initialize(); } 419236829Spfg 420236829Spfg _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 421236829Spfg : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), 422236829Spfg _M_node_count(0) 423236829Spfg { _M_initialize(); } 424236829Spfg 425236829Spfg private: 426236829Spfg void 427236829Spfg _M_initialize() 428132720Skan { 429132720Skan this->_M_header._M_color = _S_red; 430132720Skan this->_M_header._M_parent = 0; 431132720Skan this->_M_header._M_left = &this->_M_header; 432132720Skan this->_M_header._M_right = &this->_M_header; 433132720Skan } 434132720Skan }; 43597403Sobrien 436132720Skan // Specialization for _Comparison types that are not capable of 437132720Skan // being base classes / super classes. 438132720Skan template<typename _Key_compare> 439132720Skan struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator 440132720Skan { 441132720Skan _Key_compare _M_key_compare; 442132720Skan _Rb_tree_node_base _M_header; 443132720Skan size_type _M_node_count; // Keeps track of size of tree. 44497403Sobrien 445236829Spfg _Rb_tree_impl() 446236829Spfg : _Node_allocator(), _M_key_compare(), _M_header(), 447236829Spfg _M_node_count(0) 448236829Spfg { _M_initialize(); } 449236829Spfg 450236829Spfg _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 451169691Skan : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), 452169691Skan _M_node_count(0) 453236829Spfg { _M_initialize(); } 454236829Spfg 455236829Spfg private: 456236829Spfg void 457236829Spfg _M_initialize() 458236829Spfg { 459132720Skan this->_M_header._M_color = _S_red; 460132720Skan this->_M_header._M_parent = 0; 461132720Skan this->_M_header._M_left = &this->_M_header; 462132720Skan this->_M_header._M_right = &this->_M_header; 463132720Skan } 464132720Skan }; 46597403Sobrien 466132720Skan _Rb_tree_impl<_Compare> _M_impl; 46797403Sobrien 468132720Skan protected: 469132720Skan _Base_ptr& 470132720Skan _M_root() 471132720Skan { return this->_M_impl._M_header._M_parent; } 47297403Sobrien 473132720Skan _Const_Base_ptr 474132720Skan _M_root() const 475132720Skan { return this->_M_impl._M_header._M_parent; } 47697403Sobrien 477132720Skan _Base_ptr& 478132720Skan _M_leftmost() 479132720Skan { return this->_M_impl._M_header._M_left; } 48097403Sobrien 481132720Skan _Const_Base_ptr 482132720Skan _M_leftmost() const 483132720Skan { return this->_M_impl._M_header._M_left; } 48497403Sobrien 485132720Skan _Base_ptr& 486132720Skan _M_rightmost() 487132720Skan { return this->_M_impl._M_header._M_right; } 48897403Sobrien 489132720Skan _Const_Base_ptr 490132720Skan _M_rightmost() const 491132720Skan { return this->_M_impl._M_header._M_right; } 49297403Sobrien 493132720Skan _Link_type 494132720Skan _M_begin() 495132720Skan { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 49697403Sobrien 497132720Skan _Const_Link_type 498132720Skan _M_begin() const 499169691Skan { 500169691Skan return static_cast<_Const_Link_type> 501169691Skan (this->_M_impl._M_header._M_parent); 502169691Skan } 50397403Sobrien 504132720Skan _Link_type 505132720Skan _M_end() 506132720Skan { return static_cast<_Link_type>(&this->_M_impl._M_header); } 50797403Sobrien 508132720Skan _Const_Link_type 509132720Skan _M_end() const 510132720Skan { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 51197403Sobrien 512132720Skan static const_reference 513132720Skan _S_value(_Const_Link_type __x) 514132720Skan { return __x->_M_value_field; } 51597403Sobrien 516132720Skan static const _Key& 517132720Skan _S_key(_Const_Link_type __x) 518132720Skan { return _KeyOfValue()(_S_value(__x)); } 51997403Sobrien 520132720Skan static _Link_type 521132720Skan _S_left(_Base_ptr __x) 522132720Skan { return static_cast<_Link_type>(__x->_M_left); } 52397403Sobrien 524132720Skan static _Const_Link_type 525132720Skan _S_left(_Const_Base_ptr __x) 526132720Skan { return static_cast<_Const_Link_type>(__x->_M_left); } 527132720Skan 528132720Skan static _Link_type 529132720Skan _S_right(_Base_ptr __x) 530132720Skan { return static_cast<_Link_type>(__x->_M_right); } 531132720Skan 532132720Skan static _Const_Link_type 533132720Skan _S_right(_Const_Base_ptr __x) 534132720Skan { return static_cast<_Const_Link_type>(__x->_M_right); } 535132720Skan 536132720Skan static const_reference 537132720Skan _S_value(_Const_Base_ptr __x) 538132720Skan { return static_cast<_Const_Link_type>(__x)->_M_value_field; } 539132720Skan 540132720Skan static const _Key& 541132720Skan _S_key(_Const_Base_ptr __x) 542132720Skan { return _KeyOfValue()(_S_value(__x)); } 543132720Skan 544132720Skan static _Base_ptr 545132720Skan _S_minimum(_Base_ptr __x) 546132720Skan { return _Rb_tree_node_base::_S_minimum(__x); } 547132720Skan 548132720Skan static _Const_Base_ptr 549132720Skan _S_minimum(_Const_Base_ptr __x) 550132720Skan { return _Rb_tree_node_base::_S_minimum(__x); } 551132720Skan 552132720Skan static _Base_ptr 553132720Skan _S_maximum(_Base_ptr __x) 554132720Skan { return _Rb_tree_node_base::_S_maximum(__x); } 555132720Skan 556132720Skan static _Const_Base_ptr 557132720Skan _S_maximum(_Const_Base_ptr __x) 558132720Skan { return _Rb_tree_node_base::_S_maximum(__x); } 559132720Skan 56097403Sobrien public: 561132720Skan typedef _Rb_tree_iterator<value_type> iterator; 562132720Skan typedef _Rb_tree_const_iterator<value_type> const_iterator; 56397403Sobrien 564132720Skan typedef std::reverse_iterator<iterator> reverse_iterator; 565117397Skan typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 56697403Sobrien 56797403Sobrien private: 568132720Skan iterator 56997403Sobrien _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 57097403Sobrien 571169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 572169691Skan // 233. Insertion hints in associative containers. 573169691Skan iterator 574169691Skan _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 575169691Skan 576169691Skan const_iterator 577169691Skan _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y, 578169691Skan const value_type& __v); 579169691Skan 580132720Skan _Link_type 581132720Skan _M_copy(_Const_Link_type __x, _Link_type __p); 58297403Sobrien 583132720Skan void 58497403Sobrien _M_erase(_Link_type __x); 58597403Sobrien 58697403Sobrien public: 58797403Sobrien // allocation/deallocation 58897403Sobrien _Rb_tree() 589132720Skan { } 59097403Sobrien 591236829Spfg _Rb_tree(const _Compare& __comp, 592236829Spfg const allocator_type& __a = allocator_type()) 593236829Spfg : _M_impl(__comp, __a) 594132720Skan { } 59597403Sobrien 596236829Spfg _Rb_tree(const _Rb_tree& __x) 597236829Spfg : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) 598132720Skan { 599132720Skan if (__x._M_root() != 0) 60097403Sobrien { 601132720Skan _M_root() = _M_copy(__x._M_begin(), _M_end()); 60297403Sobrien _M_leftmost() = _S_minimum(_M_root()); 60397403Sobrien _M_rightmost() = _S_maximum(_M_root()); 604132720Skan _M_impl._M_node_count = __x._M_impl._M_node_count; 60597403Sobrien } 60697403Sobrien } 60797403Sobrien 608132720Skan ~_Rb_tree() 609132720Skan { _M_erase(_M_begin()); } 61097403Sobrien 611236829Spfg _Rb_tree& 612236829Spfg operator=(const _Rb_tree& __x); 61397403Sobrien 61497403Sobrien // Accessors. 615132720Skan _Compare 616132720Skan key_comp() const 617132720Skan { return _M_impl._M_key_compare; } 61897403Sobrien 619132720Skan iterator 620132720Skan begin() 621169691Skan { 622169691Skan return iterator(static_cast<_Link_type> 623169691Skan (this->_M_impl._M_header._M_left)); 624169691Skan } 62597403Sobrien 626132720Skan const_iterator 627132720Skan begin() const 628169691Skan { 629169691Skan return const_iterator(static_cast<_Const_Link_type> 630169691Skan (this->_M_impl._M_header._M_left)); 631169691Skan } 63297403Sobrien 633132720Skan iterator 634132720Skan end() 635169691Skan { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); } 63697403Sobrien 637132720Skan const_iterator 638132720Skan end() const 639169691Skan { 640169691Skan return const_iterator(static_cast<_Const_Link_type> 641169691Skan (&this->_M_impl._M_header)); 642169691Skan } 64397403Sobrien 644132720Skan reverse_iterator 645132720Skan rbegin() 646132720Skan { return reverse_iterator(end()); } 64797403Sobrien 648132720Skan const_reverse_iterator 649132720Skan rbegin() const 650132720Skan { return const_reverse_iterator(end()); } 65197403Sobrien 652132720Skan reverse_iterator 653132720Skan rend() 654132720Skan { return reverse_iterator(begin()); } 65597403Sobrien 656132720Skan const_reverse_iterator 657132720Skan rend() const 658132720Skan { return const_reverse_iterator(begin()); } 65997403Sobrien 660132720Skan bool 661132720Skan empty() const 662132720Skan { return _M_impl._M_node_count == 0; } 66397403Sobrien 664132720Skan size_type 665132720Skan size() const 666132720Skan { return _M_impl._M_node_count; } 66797403Sobrien 668132720Skan size_type 669132720Skan max_size() const 670169691Skan { return get_allocator().max_size(); } 671132720Skan 672132720Skan void 673236829Spfg swap(_Rb_tree& __t); 674132720Skan 67597403Sobrien // Insert/erase. 676169691Skan pair<iterator, bool> 677169691Skan _M_insert_unique(const value_type& __x); 67897403Sobrien 679132720Skan iterator 680169691Skan _M_insert_equal(const value_type& __x); 68197403Sobrien 682169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 683169691Skan // 233. Insertion hints in associative containers. 684132720Skan iterator 685169691Skan _M_insert_equal_lower(const value_type& __x); 68697403Sobrien 687132720Skan iterator 688169691Skan _M_insert_unique(iterator __position, const value_type& __x); 68997403Sobrien 690169691Skan const_iterator 691169691Skan _M_insert_unique(const_iterator __position, const value_type& __x); 692169691Skan 693169691Skan iterator 694169691Skan _M_insert_equal(iterator __position, const value_type& __x); 695169691Skan 696169691Skan const_iterator 697169691Skan _M_insert_equal(const_iterator __position, const value_type& __x); 698169691Skan 69997403Sobrien template<typename _InputIterator> 700169691Skan void 701169691Skan _M_insert_unique(_InputIterator __first, _InputIterator __last); 70297403Sobrien 70397403Sobrien template<typename _InputIterator> 704169691Skan void 705169691Skan _M_insert_equal(_InputIterator __first, _InputIterator __last); 70697403Sobrien 707132720Skan void 70897403Sobrien erase(iterator __position); 70997403Sobrien 710169691Skan void 711169691Skan erase(const_iterator __position); 712169691Skan 713132720Skan size_type 71497403Sobrien erase(const key_type& __x); 71597403Sobrien 716132720Skan void 71797403Sobrien erase(iterator __first, iterator __last); 71897403Sobrien 719132720Skan void 720169691Skan erase(const_iterator __first, const_iterator __last); 721169691Skan 722169691Skan void 72397403Sobrien erase(const key_type* __first, const key_type* __last); 72497403Sobrien 725132720Skan void 726132720Skan clear() 72797403Sobrien { 728132720Skan _M_erase(_M_begin()); 729132720Skan _M_leftmost() = _M_end(); 730132720Skan _M_root() = 0; 731132720Skan _M_rightmost() = _M_end(); 732132720Skan _M_impl._M_node_count = 0; 733132720Skan } 73497403Sobrien 73597403Sobrien // Set operations. 736132720Skan iterator 73797403Sobrien find(const key_type& __x); 73897403Sobrien 739132720Skan const_iterator 74097403Sobrien find(const key_type& __x) const; 74197403Sobrien 742132720Skan size_type 74397403Sobrien count(const key_type& __x) const; 74497403Sobrien 745132720Skan iterator 74697403Sobrien lower_bound(const key_type& __x); 74797403Sobrien 748132720Skan const_iterator 74997403Sobrien lower_bound(const key_type& __x) const; 75097403Sobrien 751132720Skan iterator 75297403Sobrien upper_bound(const key_type& __x); 75397403Sobrien 754132720Skan const_iterator 75597403Sobrien upper_bound(const key_type& __x) const; 75697403Sobrien 757132720Skan pair<iterator,iterator> 75897403Sobrien equal_range(const key_type& __x); 75997403Sobrien 760132720Skan pair<const_iterator, const_iterator> 76197403Sobrien equal_range(const key_type& __x) const; 76297403Sobrien 76397403Sobrien // Debugging. 764132720Skan bool 76597403Sobrien __rb_verify() const; 76697403Sobrien }; 76797403Sobrien 768132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 76997403Sobrien typename _Compare, typename _Alloc> 770132720Skan inline bool 771169691Skan operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 772169691Skan const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 77397403Sobrien { 774132720Skan return __x.size() == __y.size() 775146897Skan && std::equal(__x.begin(), __x.end(), __y.begin()); 77697403Sobrien } 77797403Sobrien 778132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 77997403Sobrien typename _Compare, typename _Alloc> 780132720Skan inline bool 781169691Skan operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 782169691Skan const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 78397403Sobrien { 784146897Skan return std::lexicographical_compare(__x.begin(), __x.end(), 785146897Skan __y.begin(), __y.end()); 78697403Sobrien } 78797403Sobrien 788132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 78997403Sobrien typename _Compare, typename _Alloc> 790132720Skan inline bool 791169691Skan operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 792169691Skan const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 79397403Sobrien { return !(__x == __y); } 79497403Sobrien 795132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 79697403Sobrien typename _Compare, typename _Alloc> 797132720Skan inline bool 798169691Skan operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 799169691Skan const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 80097403Sobrien { return __y < __x; } 80197403Sobrien 802132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 80397403Sobrien typename _Compare, typename _Alloc> 804132720Skan inline bool 805169691Skan operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 806169691Skan const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 807132720Skan { return !(__y < __x); } 80897403Sobrien 809132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 81097403Sobrien typename _Compare, typename _Alloc> 811132720Skan inline bool 812169691Skan operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 813169691Skan const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 814132720Skan { return !(__x < __y); } 81597403Sobrien 816132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 81797403Sobrien typename _Compare, typename _Alloc> 818132720Skan inline void 819169691Skan swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 820169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 82197403Sobrien { __x.swap(__y); } 82297403Sobrien 823132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 82497403Sobrien typename _Compare, typename _Alloc> 825169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 826169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 827169691Skan operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) 82897403Sobrien { 829132720Skan if (this != &__x) 83097403Sobrien { 83197403Sobrien // Note that _Key may be a constant type. 83297403Sobrien clear(); 833132720Skan _M_impl._M_key_compare = __x._M_impl._M_key_compare; 834132720Skan if (__x._M_root() != 0) 83597403Sobrien { 836132720Skan _M_root() = _M_copy(__x._M_begin(), _M_end()); 83797403Sobrien _M_leftmost() = _S_minimum(_M_root()); 83897403Sobrien _M_rightmost() = _S_maximum(_M_root()); 839132720Skan _M_impl._M_node_count = __x._M_impl._M_node_count; 84097403Sobrien } 84197403Sobrien } 84297403Sobrien return *this; 84397403Sobrien } 84497403Sobrien 845132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 84697403Sobrien typename _Compare, typename _Alloc> 847169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 848169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 849132720Skan _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 85097403Sobrien { 851169691Skan bool __insert_left = (__x != 0 || __p == _M_end() 852169691Skan || _M_impl._M_key_compare(_KeyOfValue()(__v), 853169691Skan _S_key(__p))); 854169691Skan 855132720Skan _Link_type __z = _M_create_node(__v); 856132720Skan 857169691Skan _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 858169691Skan this->_M_impl._M_header); 859169691Skan ++_M_impl._M_node_count; 860169691Skan return iterator(__z); 861169691Skan } 862132720Skan 863169691Skan template<typename _Key, typename _Val, typename _KeyOfValue, 864169691Skan typename _Compare, typename _Alloc> 865169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 866169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 867169691Skan _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 868169691Skan { 869169691Skan bool __insert_left = (__x != 0 || __p == _M_end() 870169691Skan || !_M_impl._M_key_compare(_S_key(__p), 871169691Skan _KeyOfValue()(__v))); 872169691Skan 873169691Skan _Link_type __z = _M_create_node(__v); 874169691Skan 875132720Skan _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 876132720Skan this->_M_impl._M_header); 877132720Skan ++_M_impl._M_node_count; 87897403Sobrien return iterator(__z); 87997403Sobrien } 88097403Sobrien 881132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 88297403Sobrien typename _Compare, typename _Alloc> 883169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator 884169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 885169691Skan _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) 88697403Sobrien { 887169691Skan bool __insert_left = (__x != 0 || __p == _M_end() 888169691Skan || _M_impl._M_key_compare(_KeyOfValue()(__v), 889169691Skan _S_key(__p))); 890169691Skan 891169691Skan _Link_type __z = _M_create_node(__v); 892169691Skan 893169691Skan _Rb_tree_insert_and_rebalance(__insert_left, __z, 894169691Skan const_cast<_Base_ptr>(__p), 895169691Skan this->_M_impl._M_header); 896169691Skan ++_M_impl._M_node_count; 897169691Skan return const_iterator(__z); 898169691Skan } 899169691Skan 900169691Skan template<typename _Key, typename _Val, typename _KeyOfValue, 901169691Skan typename _Compare, typename _Alloc> 902169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 903169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 904169691Skan _M_insert_equal(const _Val& __v) 905169691Skan { 906132720Skan _Link_type __x = _M_begin(); 907132720Skan _Link_type __y = _M_end(); 908132720Skan while (__x != 0) 90997403Sobrien { 91097403Sobrien __y = __x; 911132720Skan __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 912132720Skan _S_left(__x) : _S_right(__x); 91397403Sobrien } 91497403Sobrien return _M_insert(__x, __y, __v); 91597403Sobrien } 91697403Sobrien 917132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 91897403Sobrien typename _Compare, typename _Alloc> 919169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 920169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 921169691Skan _M_insert_equal_lower(const _Val& __v) 922169691Skan { 923169691Skan _Link_type __x = _M_begin(); 924169691Skan _Link_type __y = _M_end(); 925169691Skan while (__x != 0) 926169691Skan { 927169691Skan __y = __x; 928169691Skan __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 929169691Skan _S_left(__x) : _S_right(__x); 930169691Skan } 931169691Skan return _M_insert_lower(__x, __y, __v); 932169691Skan } 933169691Skan 934169691Skan template<typename _Key, typename _Val, typename _KeyOfValue, 935169691Skan typename _Compare, typename _Alloc> 936132720Skan void 937169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 938169691Skan swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 939132720Skan { 940132720Skan if (_M_root() == 0) 941132720Skan { 942169691Skan if (__t._M_root() != 0) 943169691Skan { 944169691Skan _M_root() = __t._M_root(); 945169691Skan _M_leftmost() = __t._M_leftmost(); 946169691Skan _M_rightmost() = __t._M_rightmost(); 947169691Skan _M_root()->_M_parent = _M_end(); 948169691Skan 949169691Skan __t._M_root() = 0; 950169691Skan __t._M_leftmost() = __t._M_end(); 951169691Skan __t._M_rightmost() = __t._M_end(); 952169691Skan } 953132720Skan } 954132720Skan else if (__t._M_root() == 0) 955169691Skan { 956169691Skan __t._M_root() = _M_root(); 957169691Skan __t._M_leftmost() = _M_leftmost(); 958169691Skan __t._M_rightmost() = _M_rightmost(); 959169691Skan __t._M_root()->_M_parent = __t._M_end(); 960169691Skan 961169691Skan _M_root() = 0; 962169691Skan _M_leftmost() = _M_end(); 963169691Skan _M_rightmost() = _M_end(); 964169691Skan } 965132720Skan else 966169691Skan { 967169691Skan std::swap(_M_root(),__t._M_root()); 968169691Skan std::swap(_M_leftmost(),__t._M_leftmost()); 969169691Skan std::swap(_M_rightmost(),__t._M_rightmost()); 970169691Skan 971169691Skan _M_root()->_M_parent = _M_end(); 972169691Skan __t._M_root()->_M_parent = __t._M_end(); 973169691Skan } 974132720Skan // No need to swap header's color as it does not change. 975132720Skan std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 976132720Skan std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 977169691Skan 978169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 979169691Skan // 431. Swapping containers with unequal allocators. 980169691Skan std::__alloc_swap<_Node_allocator>:: 981169691Skan _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); 982132720Skan } 983132720Skan 984132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 985132720Skan typename _Compare, typename _Alloc> 986169691Skan pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 987169691Skan _Compare, _Alloc>::iterator, bool> 988169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 989169691Skan _M_insert_unique(const _Val& __v) 99097403Sobrien { 991132720Skan _Link_type __x = _M_begin(); 992132720Skan _Link_type __y = _M_end(); 99397403Sobrien bool __comp = true; 994132720Skan while (__x != 0) 99597403Sobrien { 99697403Sobrien __y = __x; 997132720Skan __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 99897403Sobrien __x = __comp ? _S_left(__x) : _S_right(__x); 99997403Sobrien } 1000132720Skan iterator __j = iterator(__y); 100197403Sobrien if (__comp) 1002233193Sdim { 1003233193Sdim if (__j == begin()) 1004233193Sdim return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 1005233193Sdim else 1006233193Sdim --__j; 1007233193Sdim } 1008132720Skan if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 1009169691Skan return pair<iterator, bool>(_M_insert(__x, __y, __v), true); 1010169691Skan return pair<iterator, bool>(__j, false); 101197403Sobrien } 101297403Sobrien 1013132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 101497403Sobrien typename _Compare, typename _Alloc> 1015132720Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 101697403Sobrien _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1017169691Skan _M_insert_unique(iterator __position, const _Val& __v) 101897403Sobrien { 1019169691Skan // end() 1020169691Skan if (__position._M_node == _M_end()) 1021132720Skan { 1022132720Skan if (size() > 0 1023169691Skan && _M_impl._M_key_compare(_S_key(_M_rightmost()), 1024169691Skan _KeyOfValue()(__v))) 1025169691Skan return _M_insert(0, _M_rightmost(), __v); 102697403Sobrien else 1027169691Skan return _M_insert_unique(__v).first; 1028132720Skan } 1029169691Skan else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1030169691Skan _S_key(__position._M_node))) 1031132720Skan { 1032169691Skan // First, try before... 1033169691Skan iterator __before = __position; 1034169691Skan if (__position._M_node == _M_leftmost()) // begin() 1035169691Skan return _M_insert(_M_leftmost(), _M_leftmost(), __v); 1036169691Skan else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 1037169691Skan _KeyOfValue()(__v))) 1038169691Skan { 1039169691Skan if (_S_right(__before._M_node) == 0) 1040169691Skan return _M_insert(0, __before._M_node, __v); 1041169691Skan else 1042169691Skan return _M_insert(__position._M_node, 1043169691Skan __position._M_node, __v); 1044169691Skan } 1045169691Skan else 1046169691Skan return _M_insert_unique(__v).first; 1047169691Skan } 1048169691Skan else if (_M_impl._M_key_compare(_S_key(__position._M_node), 1049169691Skan _KeyOfValue()(__v))) 1050169691Skan { 1051169691Skan // ... then try after. 1052169691Skan iterator __after = __position; 1053169691Skan if (__position._M_node == _M_rightmost()) 105497403Sobrien return _M_insert(0, _M_rightmost(), __v); 1055169691Skan else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1056169691Skan _S_key((++__after)._M_node))) 1057169691Skan { 1058169691Skan if (_S_right(__position._M_node) == 0) 1059169691Skan return _M_insert(0, __position._M_node, __v); 1060169691Skan else 1061169691Skan return _M_insert(__after._M_node, __after._M_node, __v); 1062169691Skan } 106397403Sobrien else 1064169691Skan return _M_insert_unique(__v).first; 1065132720Skan } 1066132720Skan else 1067169691Skan return __position; // Equivalent keys. 1068169691Skan } 1069169691Skan 1070169691Skan template<typename _Key, typename _Val, typename _KeyOfValue, 1071169691Skan typename _Compare, typename _Alloc> 1072169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator 1073169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1074169691Skan _M_insert_unique(const_iterator __position, const _Val& __v) 1075169691Skan { 1076169691Skan // end() 1077169691Skan if (__position._M_node == _M_end()) 107897403Sobrien { 1079169691Skan if (size() > 0 1080169691Skan && _M_impl._M_key_compare(_S_key(_M_rightmost()), 1081169691Skan _KeyOfValue()(__v))) 1082169691Skan return _M_insert(0, _M_rightmost(), __v); 1083169691Skan else 1084169691Skan return const_iterator(_M_insert_unique(__v).first); 1085169691Skan } 1086169691Skan else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1087169691Skan _S_key(__position._M_node))) 1088169691Skan { 1089169691Skan // First, try before... 1090169691Skan const_iterator __before = __position; 1091169691Skan if (__position._M_node == _M_leftmost()) // begin() 1092169691Skan return _M_insert(_M_leftmost(), _M_leftmost(), __v); 1093169691Skan else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 1094169691Skan _KeyOfValue()(__v))) 109597403Sobrien { 109697403Sobrien if (_S_right(__before._M_node) == 0) 1097132720Skan return _M_insert(0, __before._M_node, __v); 109897403Sobrien else 1099169691Skan return _M_insert(__position._M_node, 1100169691Skan __position._M_node, __v); 1101132720Skan } 110297403Sobrien else 1103169691Skan return const_iterator(_M_insert_unique(__v).first); 110497403Sobrien } 1105169691Skan else if (_M_impl._M_key_compare(_S_key(__position._M_node), 1106169691Skan _KeyOfValue()(__v))) 1107169691Skan { 1108169691Skan // ... then try after. 1109169691Skan const_iterator __after = __position; 1110169691Skan if (__position._M_node == _M_rightmost()) 1111169691Skan return _M_insert(0, _M_rightmost(), __v); 1112169691Skan else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1113169691Skan _S_key((++__after)._M_node))) 1114169691Skan { 1115169691Skan if (_S_right(__position._M_node) == 0) 1116169691Skan return _M_insert(0, __position._M_node, __v); 1117169691Skan else 1118169691Skan return _M_insert(__after._M_node, __after._M_node, __v); 1119169691Skan } 1120169691Skan else 1121169691Skan return const_iterator(_M_insert_unique(__v).first); 1122169691Skan } 1123169691Skan else 1124169691Skan return __position; // Equivalent keys. 112597403Sobrien } 112697403Sobrien 1127132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 112897403Sobrien typename _Compare, typename _Alloc> 1129169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1130169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1131169691Skan _M_insert_equal(iterator __position, const _Val& __v) 113297403Sobrien { 1133169691Skan // end() 1134169691Skan if (__position._M_node == _M_end()) 1135132720Skan { 1136132720Skan if (size() > 0 1137169691Skan && !_M_impl._M_key_compare(_KeyOfValue()(__v), 1138169691Skan _S_key(_M_rightmost()))) 1139169691Skan return _M_insert(0, _M_rightmost(), __v); 114097403Sobrien else 1141169691Skan return _M_insert_equal(__v); 1142132720Skan } 1143169691Skan else if (!_M_impl._M_key_compare(_S_key(__position._M_node), 1144169691Skan _KeyOfValue()(__v))) 114597403Sobrien { 1146169691Skan // First, try before... 1147169691Skan iterator __before = __position; 1148169691Skan if (__position._M_node == _M_leftmost()) // begin() 1149169691Skan return _M_insert(_M_leftmost(), _M_leftmost(), __v); 1150169691Skan else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 1151169691Skan _S_key((--__before)._M_node))) 1152169691Skan { 1153169691Skan if (_S_right(__before._M_node) == 0) 1154169691Skan return _M_insert(0, __before._M_node, __v); 1155169691Skan else 1156169691Skan return _M_insert(__position._M_node, 1157169691Skan __position._M_node, __v); 1158169691Skan } 115997403Sobrien else 1160169691Skan return _M_insert_equal(__v); 1161132720Skan } 1162132720Skan else 116397403Sobrien { 1164169691Skan // ... then try after. 1165169691Skan iterator __after = __position; 1166169691Skan if (__position._M_node == _M_rightmost()) 1167169691Skan return _M_insert(0, _M_rightmost(), __v); 1168169691Skan else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), 1169169691Skan _KeyOfValue()(__v))) 117097403Sobrien { 1171169691Skan if (_S_right(__position._M_node) == 0) 1172169691Skan return _M_insert(0, __position._M_node, __v); 1173169691Skan else 1174169691Skan return _M_insert(__after._M_node, __after._M_node, __v); 1175169691Skan } 1176169691Skan else 1177169691Skan return _M_insert_equal_lower(__v); 1178169691Skan } 1179169691Skan } 1180169691Skan 1181169691Skan template<typename _Key, typename _Val, typename _KeyOfValue, 1182169691Skan typename _Compare, typename _Alloc> 1183169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator 1184169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1185169691Skan _M_insert_equal(const_iterator __position, const _Val& __v) 1186169691Skan { 1187169691Skan // end() 1188169691Skan if (__position._M_node == _M_end()) 1189169691Skan { 1190169691Skan if (size() > 0 1191169691Skan && !_M_impl._M_key_compare(_KeyOfValue()(__v), 1192169691Skan _S_key(_M_rightmost()))) 1193169691Skan return _M_insert(0, _M_rightmost(), __v); 1194169691Skan else 1195169691Skan return const_iterator(_M_insert_equal(__v)); 1196169691Skan } 1197169691Skan else if (!_M_impl._M_key_compare(_S_key(__position._M_node), 1198169691Skan _KeyOfValue()(__v))) 1199169691Skan { 1200169691Skan // First, try before... 1201169691Skan const_iterator __before = __position; 1202169691Skan if (__position._M_node == _M_leftmost()) // begin() 1203169691Skan return _M_insert(_M_leftmost(), _M_leftmost(), __v); 1204169691Skan else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 1205169691Skan _S_key((--__before)._M_node))) 1206169691Skan { 120797403Sobrien if (_S_right(__before._M_node) == 0) 1208132720Skan return _M_insert(0, __before._M_node, __v); 120997403Sobrien else 1210169691Skan return _M_insert(__position._M_node, 1211169691Skan __position._M_node, __v); 1212132720Skan } 121397403Sobrien else 1214169691Skan return const_iterator(_M_insert_equal(__v)); 121597403Sobrien } 1216169691Skan else 1217169691Skan { 1218169691Skan // ... then try after. 1219169691Skan const_iterator __after = __position; 1220169691Skan if (__position._M_node == _M_rightmost()) 1221169691Skan return _M_insert(0, _M_rightmost(), __v); 1222169691Skan else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), 1223169691Skan _KeyOfValue()(__v))) 1224169691Skan { 1225169691Skan if (_S_right(__position._M_node) == 0) 1226169691Skan return _M_insert(0, __position._M_node, __v); 1227169691Skan else 1228169691Skan return _M_insert(__after._M_node, __after._M_node, __v); 1229169691Skan } 1230169691Skan else 1231169691Skan return const_iterator(_M_insert_equal_lower(__v)); 1232169691Skan } 123397403Sobrien } 123497403Sobrien 1235132720Skan template<typename _Key, typename _Val, typename _KoV, 123697403Sobrien typename _Cmp, typename _Alloc> 123797403Sobrien template<class _II> 1238132720Skan void 1239169691Skan _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1240169691Skan _M_insert_equal(_II __first, _II __last) 124197403Sobrien { 1242169691Skan for (; __first != __last; ++__first) 1243169691Skan _M_insert_equal(end(), *__first); 124497403Sobrien } 124597403Sobrien 1246132720Skan template<typename _Key, typename _Val, typename _KoV, 1247132720Skan typename _Cmp, typename _Alloc> 124897403Sobrien template<class _II> 1249169691Skan void 1250169691Skan _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1251169691Skan _M_insert_unique(_II __first, _II __last) 1252169691Skan { 1253169691Skan for (; __first != __last; ++__first) 1254169691Skan _M_insert_unique(end(), *__first); 1255169691Skan } 1256169691Skan 1257169691Skan template<typename _Key, typename _Val, typename _KeyOfValue, 1258169691Skan typename _Compare, typename _Alloc> 1259169691Skan inline void 1260169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1261169691Skan erase(iterator __position) 126297403Sobrien { 1263169691Skan _Link_type __y = 1264169691Skan static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1265169691Skan (__position._M_node, 1266169691Skan this->_M_impl._M_header)); 1267169691Skan _M_destroy_node(__y); 1268169691Skan --_M_impl._M_node_count; 126997403Sobrien } 127097403Sobrien 1271132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 127297403Sobrien typename _Compare, typename _Alloc> 1273132720Skan inline void 1274169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1275169691Skan erase(const_iterator __position) 127697403Sobrien { 1277132720Skan _Link_type __y = 1278169691Skan static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1279169691Skan (const_cast<_Base_ptr>(__position._M_node), 1280169691Skan this->_M_impl._M_header)); 1281169691Skan _M_destroy_node(__y); 1282132720Skan --_M_impl._M_node_count; 128397403Sobrien } 128497403Sobrien 1285132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 128697403Sobrien typename _Compare, typename _Alloc> 1287169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1288169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1289169691Skan erase(const _Key& __x) 129097403Sobrien { 1291169691Skan pair<iterator, iterator> __p = equal_range(__x); 1292169691Skan const size_type __old_size = size(); 129397403Sobrien erase(__p.first, __p.second); 1294169691Skan return __old_size - size(); 129597403Sobrien } 129697403Sobrien 1297132720Skan template<typename _Key, typename _Val, typename _KoV, 129897403Sobrien typename _Compare, typename _Alloc> 1299132720Skan typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 1300169691Skan _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 1301132720Skan _M_copy(_Const_Link_type __x, _Link_type __p) 130297403Sobrien { 130397403Sobrien // Structural copy. __x and __p must be non-null. 130497403Sobrien _Link_type __top = _M_clone_node(__x); 130597403Sobrien __top->_M_parent = __p; 1306132720Skan 1307132720Skan try 130897403Sobrien { 130997403Sobrien if (__x->_M_right) 131097403Sobrien __top->_M_right = _M_copy(_S_right(__x), __top); 131197403Sobrien __p = __top; 131297403Sobrien __x = _S_left(__x); 1313132720Skan 1314132720Skan while (__x != 0) 131597403Sobrien { 131697403Sobrien _Link_type __y = _M_clone_node(__x); 131797403Sobrien __p->_M_left = __y; 131897403Sobrien __y->_M_parent = __p; 131997403Sobrien if (__x->_M_right) 132097403Sobrien __y->_M_right = _M_copy(_S_right(__x), __y); 132197403Sobrien __p = __y; 132297403Sobrien __x = _S_left(__x); 132397403Sobrien } 132497403Sobrien } 132597403Sobrien catch(...) 132697403Sobrien { 132797403Sobrien _M_erase(__top); 1328132720Skan __throw_exception_again; 132997403Sobrien } 133097403Sobrien return __top; 133197403Sobrien } 133297403Sobrien 1333132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 133497403Sobrien typename _Compare, typename _Alloc> 1335132720Skan void 1336169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1337169691Skan _M_erase(_Link_type __x) 133897403Sobrien { 133997403Sobrien // Erase without rebalancing. 1340132720Skan while (__x != 0) 134197403Sobrien { 134297403Sobrien _M_erase(_S_right(__x)); 134397403Sobrien _Link_type __y = _S_left(__x); 1344169691Skan _M_destroy_node(__x); 134597403Sobrien __x = __y; 134697403Sobrien } 134797403Sobrien } 134897403Sobrien 1349132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 135097403Sobrien typename _Compare, typename _Alloc> 1351132720Skan void 1352169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 135397403Sobrien erase(iterator __first, iterator __last) 135497403Sobrien { 135597403Sobrien if (__first == begin() && __last == end()) 135697403Sobrien clear(); 135797403Sobrien else 1358169691Skan while (__first != __last) 1359169691Skan erase(__first++); 136097403Sobrien } 136197403Sobrien 1362132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 136397403Sobrien typename _Compare, typename _Alloc> 1364132720Skan void 1365169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1366169691Skan erase(const_iterator __first, const_iterator __last) 1367169691Skan { 1368169691Skan if (__first == begin() && __last == end()) 1369169691Skan clear(); 1370169691Skan else 1371169691Skan while (__first != __last) 1372169691Skan erase(__first++); 1373169691Skan } 1374169691Skan 1375169691Skan template<typename _Key, typename _Val, typename _KeyOfValue, 1376169691Skan typename _Compare, typename _Alloc> 1377169691Skan void 1378169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1379132720Skan erase(const _Key* __first, const _Key* __last) 1380132720Skan { 1381132720Skan while (__first != __last) 1382132720Skan erase(*__first++); 138397403Sobrien } 138497403Sobrien 1385132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 138697403Sobrien typename _Compare, typename _Alloc> 1387169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1388169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1389169691Skan find(const _Key& __k) 139097403Sobrien { 1391132720Skan _Link_type __x = _M_begin(); // Current node. 1392132720Skan _Link_type __y = _M_end(); // Last node which is not less than __k. 1393132720Skan 1394132720Skan while (__x != 0) 1395132720Skan if (!_M_impl._M_key_compare(_S_key(__x), __k)) 139697403Sobrien __y = __x, __x = _S_left(__x); 139797403Sobrien else 139897403Sobrien __x = _S_right(__x); 1399132720Skan 1400132720Skan iterator __j = iterator(__y); 1401169691Skan return (__j == end() 1402169691Skan || _M_impl._M_key_compare(__k, 1403169691Skan _S_key(__j._M_node))) ? end() : __j; 140497403Sobrien } 1405132720Skan 1406132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 140797403Sobrien typename _Compare, typename _Alloc> 1408169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator 1409169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 141097403Sobrien find(const _Key& __k) const 141197403Sobrien { 1412132720Skan _Const_Link_type __x = _M_begin(); // Current node. 1413132720Skan _Const_Link_type __y = _M_end(); // Last node which is not less than __k. 1414132720Skan 1415132720Skan while (__x != 0) 141697403Sobrien { 1417132720Skan if (!_M_impl._M_key_compare(_S_key(__x), __k)) 141897403Sobrien __y = __x, __x = _S_left(__x); 141997403Sobrien else 142097403Sobrien __x = _S_right(__x); 1421132720Skan } 1422132720Skan const_iterator __j = const_iterator(__y); 1423169691Skan return (__j == end() 1424169691Skan || _M_impl._M_key_compare(__k, 1425169691Skan _S_key(__j._M_node))) ? end() : __j; 142697403Sobrien } 142797403Sobrien 1428132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 142997403Sobrien typename _Compare, typename _Alloc> 1430169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1431169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 143297403Sobrien count(const _Key& __k) const 143397403Sobrien { 143497403Sobrien pair<const_iterator, const_iterator> __p = equal_range(__k); 1435132720Skan const size_type __n = std::distance(__p.first, __p.second); 143697403Sobrien return __n; 143797403Sobrien } 143897403Sobrien 1439132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 144097403Sobrien typename _Compare, typename _Alloc> 1441169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1442169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 144397403Sobrien lower_bound(const _Key& __k) 144497403Sobrien { 1445132720Skan _Link_type __x = _M_begin(); // Current node. 1446132720Skan _Link_type __y = _M_end(); // Last node which is not less than __k. 1447132720Skan 1448132720Skan while (__x != 0) 1449132720Skan if (!_M_impl._M_key_compare(_S_key(__x), __k)) 145097403Sobrien __y = __x, __x = _S_left(__x); 145197403Sobrien else 145297403Sobrien __x = _S_right(__x); 1453132720Skan 145497403Sobrien return iterator(__y); 145597403Sobrien } 145697403Sobrien 1457132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 145897403Sobrien typename _Compare, typename _Alloc> 1459169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator 1460169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 146197403Sobrien lower_bound(const _Key& __k) const 146297403Sobrien { 1463132720Skan _Const_Link_type __x = _M_begin(); // Current node. 1464132720Skan _Const_Link_type __y = _M_end(); // Last node which is not less than __k. 1465132720Skan 1466132720Skan while (__x != 0) 1467132720Skan if (!_M_impl._M_key_compare(_S_key(__x), __k)) 146897403Sobrien __y = __x, __x = _S_left(__x); 146997403Sobrien else 147097403Sobrien __x = _S_right(__x); 1471132720Skan 147297403Sobrien return const_iterator(__y); 147397403Sobrien } 147497403Sobrien 1475132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 147697403Sobrien typename _Compare, typename _Alloc> 1477169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1478169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 147997403Sobrien upper_bound(const _Key& __k) 148097403Sobrien { 1481132720Skan _Link_type __x = _M_begin(); // Current node. 1482132720Skan _Link_type __y = _M_end(); // Last node which is greater than __k. 1483132720Skan 1484132720Skan while (__x != 0) 1485132720Skan if (_M_impl._M_key_compare(__k, _S_key(__x))) 148697403Sobrien __y = __x, __x = _S_left(__x); 148797403Sobrien else 148897403Sobrien __x = _S_right(__x); 1489132720Skan 149097403Sobrien return iterator(__y); 149197403Sobrien } 149297403Sobrien 1493132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 149497403Sobrien typename _Compare, typename _Alloc> 1495169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator 1496169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 149797403Sobrien upper_bound(const _Key& __k) const 149897403Sobrien { 1499132720Skan _Const_Link_type __x = _M_begin(); // Current node. 1500132720Skan _Const_Link_type __y = _M_end(); // Last node which is greater than __k. 1501132720Skan 1502132720Skan while (__x != 0) 1503132720Skan if (_M_impl._M_key_compare(__k, _S_key(__x))) 150497403Sobrien __y = __x, __x = _S_left(__x); 150597403Sobrien else 150697403Sobrien __x = _S_right(__x); 1507132720Skan 150897403Sobrien return const_iterator(__y); 150997403Sobrien } 151097403Sobrien 1511132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 151297403Sobrien typename _Compare, typename _Alloc> 1513132720Skan inline 1514169691Skan pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1515169691Skan _Compare, _Alloc>::iterator, 1516169691Skan typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator> 1517169691Skan _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 151897403Sobrien equal_range(const _Key& __k) 151997403Sobrien { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); } 152097403Sobrien 1521132720Skan template<typename _Key, typename _Val, typename _KoV, 152297403Sobrien typename _Compare, typename _Alloc> 1523132720Skan inline 1524132720Skan pair<typename _Rb_tree<_Key, _Val, _KoV, 1525132720Skan _Compare, _Alloc>::const_iterator, 1526132720Skan typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator> 1527132720Skan _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 1528132720Skan equal_range(const _Key& __k) const 1529132720Skan { return pair<const_iterator, const_iterator>(lower_bound(__k), 1530132720Skan upper_bound(__k)); } 153197403Sobrien 1532132720Skan unsigned int 1533132720Skan _Rb_tree_black_count(const _Rb_tree_node_base* __node, 1534132720Skan const _Rb_tree_node_base* __root); 153597403Sobrien 1536132720Skan template<typename _Key, typename _Val, typename _KeyOfValue, 153797403Sobrien typename _Compare, typename _Alloc> 1538132720Skan bool 153997403Sobrien _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 154097403Sobrien { 1541132720Skan if (_M_impl._M_node_count == 0 || begin() == end()) 1542132720Skan return _M_impl._M_node_count == 0 && begin() == end() 1543132720Skan && this->_M_impl._M_header._M_left == _M_end() 1544132720Skan && this->_M_impl._M_header._M_right == _M_end(); 1545132720Skan 1546132720Skan unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 1547132720Skan for (const_iterator __it = begin(); __it != end(); ++__it) 1548132720Skan { 1549132720Skan _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 1550132720Skan _Const_Link_type __L = _S_left(__x); 1551132720Skan _Const_Link_type __R = _S_right(__x); 1552132720Skan 1553132720Skan if (__x->_M_color == _S_red) 1554132720Skan if ((__L && __L->_M_color == _S_red) 1555132720Skan || (__R && __R->_M_color == _S_red)) 1556132720Skan return false; 1557132720Skan 1558132720Skan if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 155997403Sobrien return false; 1560132720Skan if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 1561132720Skan return false; 156297403Sobrien 1563132720Skan if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 1564132720Skan return false; 1565132720Skan } 1566132720Skan 1567132720Skan if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 1568132720Skan return false; 1569132720Skan if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 1570132720Skan return false; 1571132720Skan return true; 157297403Sobrien } 157397403Sobrien 1574169691Skan_GLIBCXX_END_NAMESPACE 1575169691Skan 1576132720Skan#endif 1577