contrib/gcc-3.4/libstdc++-v3/include/bits/stl_tree.h

   1 // RB tree implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1996,1997
  33  * Silicon Graphics Computer Systems, Inc.
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Silicon Graphics makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1994
  45  * Hewlett-Packard Company
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Hewlett-Packard Company makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  *
  55  *
  56  */
  57
  58 /** @file stl_tree.h
  59  *  This is an internal header file, included by other library headers.
  60  *  You should not attempt to use it directly.
  61  */
  62
  63 #ifndef _TREE_H
  64 #define _TREE_H 1
  65
  66 #include <bits/stl_algobase.h>
  67 #include <bits/allocator.h>
  68 #include <bits/stl_construct.h>
  69 #include <bits/stl_function.h>
  70 #include <bits/cpp_type_traits.h>
  71
  72 namespace std
  73 {
  74   // Red-black tree class, designed for use in implementing STL
  75   // associative containers (set, multiset, map, and multimap). The
  76   // insertion and deletion algorithms are based on those in Cormen,
  77   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
  78   // 1990), except that
  79   //
  80   // (1) the header cell is maintained with links not only to the root
  81   // but also to the leftmost node of the tree, to enable constant
  82   // time begin(), and to the rightmost node of the tree, to enable
  83   // linear time performance when used with the generic set algorithms
  84   // (set_union, etc.)
  85   //
  86   // (2) when a node being deleted has two children its successor node
  87   // is relinked into its place, rather than copied, so that the only
  88   // iterators invalidated are those referring to the deleted node.
  89
  90   enum _Rb_tree_color { _S_red = false, _S_black = true };
  91
  92   struct _Rb_tree_node_base
  93   {
  94     typedef _Rb_tree_node_base* _Base_ptr;
  95     typedef const _Rb_tree_node_base* _Const_Base_ptr;
  96
  97     _Rb_tree_color      _M_color;
  98     _Base_ptr           _M_parent;
  99     _Base_ptr           _M_left;
 100     _Base_ptr           _M_right;
 101
 102     static _Base_ptr
 103     _S_minimum(_Base_ptr __x)
 104     {
 105       while (__x->_M_left != 0) __x = __x->_M_left;
 106       return __x;
 107     }
 108
 109     static _Const_Base_ptr
 110     _S_minimum(_Const_Base_ptr __x)
 111     {
 112       while (__x->_M_left != 0) __x = __x->_M_left;
 113       return __x;
 114     }
 115
 116     static _Base_ptr
 117     _S_maximum(_Base_ptr __x)
 118     {
 119       while (__x->_M_right != 0) __x = __x->_M_right;
 120       return __x;
 121     }
 122
 123     static _Const_Base_ptr
 124     _S_maximum(_Const_Base_ptr __x)
 125     {
 126       while (__x->_M_right != 0) __x = __x->_M_right;
 127       return __x;
 128     }
 129   };
 130
 131   template<typename _Val>
 132     struct _Rb_tree_node : public _Rb_tree_node_base
 133     {
 134       typedef _Rb_tree_node<_Val>* _Link_type;
 135       _Val _M_value_field;
 136     };
 137
 138   _Rb_tree_node_base*
 139   _Rb_tree_increment(_Rb_tree_node_base* __x);
 140
 141   const _Rb_tree_node_base*
 142   _Rb_tree_increment(const _Rb_tree_node_base* __x);
 143
 144   _Rb_tree_node_base*
 145   _Rb_tree_decrement(_Rb_tree_node_base* __x);
 146
 147   const _Rb_tree_node_base*
 148   _Rb_tree_decrement(const _Rb_tree_node_base* __x);
 149
 150   template<typename _Tp>
 151     struct _Rb_tree_iterator
 152     {
 153       typedef _Tp  value_type;
 154       typedef _Tp& reference;
 155       typedef _Tp* pointer;
 156
 157       typedef bidirectional_iterator_tag iterator_category;
 158       typedef ptrdiff_t                  difference_type;
 159
 160       typedef _Rb_tree_iterator<_Tp>        _Self;
 161       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
 162       typedef _Rb_tree_node<_Tp>*           _Link_type;
 163
 164       _Rb_tree_iterator() { }
 165
 166       _Rb_tree_iterator(_Link_type __x)
 167       : _M_node(__x) { }
 168
 169       reference
 170       operator*() const
 171       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 172
 173       pointer
 174       operator->() const
 175       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 176
 177       _Self&
 178       operator++()
 179       {
 180         _M_node = _Rb_tree_increment(_M_node);
 181         return *this;
 182       }
 183
 184       _Self
 185       operator++(int)
 186       {
 187         _Self __tmp = *this;
 188         _M_node = _Rb_tree_increment(_M_node);
 189         return __tmp;
 190       }
 191
 192       _Self&
 193       operator--()
 194       {
 195         _M_node = _Rb_tree_decrement(_M_node);
 196         return *this;
 197       }
 198
 199       _Self
 200       operator--(int)
 201       {
 202         _Self __tmp = *this;
 203         _M_node = _Rb_tree_decrement(_M_node);
 204         return __tmp;
 205       }
 206
 207       bool
 208       operator==(const _Self& __x) const
 209       { return _M_node == __x._M_node; }
 210
 211       bool
 212       operator!=(const _Self& __x) const
 213       { return _M_node != __x._M_node; }
 214
 215       _Base_ptr _M_node;
 216   };
 217
 218   template<typename _Tp>
 219     struct _Rb_tree_const_iterator
 220     {
 221       typedef _Tp        value_type;
 222       typedef const _Tp& reference;
 223       typedef const _Tp* pointer;
 224
 225       typedef _Rb_tree_iterator<_Tp> iterator;
 226
 227       typedef bidirectional_iterator_tag iterator_category;
 228       typedef ptrdiff_t                  difference_type;
 229
 230       typedef _Rb_tree_const_iterator<_Tp>        _Self;
 231       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
 232       typedef const _Rb_tree_node<_Tp>*           _Link_type;
 233
 234       _Rb_tree_const_iterator() { }
 235
 236       _Rb_tree_const_iterator(_Link_type __x)
 237       : _M_node(__x) { }
 238
 239       _Rb_tree_const_iterator(const iterator& __it)
 240       : _M_node(__it._M_node) { }
 241
 242       reference
 243       operator*() const
 244       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 245
 246       pointer
 247       operator->() const
 248       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 249
 250       _Self&
 251       operator++()
 252       {
 253         _M_node = _Rb_tree_increment(_M_node);
 254         return *this;
 255       }
 256
 257       _Self
 258       operator++(int)
 259       {
 260         _Self __tmp = *this;
 261         _M_node = _Rb_tree_increment(_M_node);
 262         return __tmp;
 263       }
 264
 265       _Self&
 266       operator--()
 267       {
 268         _M_node = _Rb_tree_decrement(_M_node);
 269         return *this;
 270       }
 271
 272       _Self
 273       operator--(int)
 274       {
 275         _Self __tmp = *this;
 276         _M_node = _Rb_tree_decrement(_M_node);
 277         return __tmp;
 278       }
 279
 280       bool
 281       operator==(const _Self& __x) const
 282       { return _M_node == __x._M_node; }
 283
 284       bool
 285       operator!=(const _Self& __x) const
 286       { return _M_node != __x._M_node; }
 287
 288       _Base_ptr _M_node;
 289     };
 290
 291   template<typename _Val>
 292     inline bool
 293     operator==(const _Rb_tree_iterator<_Val>& __x,
 294                const _Rb_tree_const_iterator<_Val>& __y)
 295     { return __x._M_node == __y._M_node; }
 296
 297   template<typename _Val>
 298     inline bool
 299     operator!=(const _Rb_tree_iterator<_Val>& __x,
 300                const _Rb_tree_const_iterator<_Val>& __y)
 301     { return __x._M_node != __y._M_node; }
 302
 303   void
 304   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
 305                        _Rb_tree_node_base*& __root);
 306
 307   void
 308   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
 309                         _Rb_tree_node_base*& __root);
 310
 311   void
 312   _Rb_tree_insert_and_rebalance(const bool __insert_left,
 313                                 _Rb_tree_node_base* __x,
 314                                 _Rb_tree_node_base* __p,
 315                                 _Rb_tree_node_base& __header);
 316
 317   _Rb_tree_node_base*
 318   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 319                                _Rb_tree_node_base& __header);
 320
 321
 322   template<typename _Key, typename _Val, typename _KeyOfValue,
 323            typename _Compare, typename _Alloc = allocator<_Val> >
 324     class _Rb_tree
 325     {
 326       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
 327               _Node_allocator;
 328
 329     protected:
 330       typedef _Rb_tree_node_base* _Base_ptr;
 331       typedef const _Rb_tree_node_base* _Const_Base_ptr;
 332       typedef _Rb_tree_node<_Val> _Rb_tree_node;
 333
 334     public:
 335       typedef _Key key_type;
 336       typedef _Val value_type;
 337       typedef value_type* pointer;
 338       typedef const value_type* const_pointer;
 339       typedef value_type& reference;
 340       typedef const value_type& const_reference;
 341       typedef _Rb_tree_node* _Link_type;
 342       typedef const _Rb_tree_node* _Const_Link_type;
 343       typedef size_t size_type;
 344       typedef ptrdiff_t difference_type;
 345       typedef _Alloc allocator_type;
 346
 347       allocator_type
 348       get_allocator() const
 349       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
 350
 351     protected:
 352       _Rb_tree_node*
 353       _M_get_node()
 354       { return _M_impl._Node_allocator::allocate(1); }
 355
 356       void
 357       _M_put_node(_Rb_tree_node* __p)
 358       { _M_impl._Node_allocator::deallocate(__p, 1); }
 359
 360       _Link_type
 361       _M_create_node(const value_type& __x)
 362       {
 363         _Link_type __tmp = _M_get_node();
 364         try
 365           { std::_Construct(&__tmp->_M_value_field, __x); }
 366         catch(...)
 367           {
 368             _M_put_node(__tmp);
 369             __throw_exception_again;
 370           }
 371         return __tmp;
 372       }
 373
 374       _Link_type
 375       _M_clone_node(_Const_Link_type __x)
 376       {
 377         _Link_type __tmp = _M_create_node(__x->_M_value_field);
 378         __tmp->_M_color = __x->_M_color;
 379         __tmp->_M_left = 0;
 380         __tmp->_M_right = 0;
 381         return __tmp;
 382       }
 383
 384       void
 385       destroy_node(_Link_type __p)
 386       {
 387         std::_Destroy(&__p->_M_value_field);
 388         _M_put_node(__p);
 389       }
 390
 391     protected:
 392       template<typename _Key_compare,
 393                bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type>
 394         struct _Rb_tree_impl : public _Node_allocator
 395         {
 396           _Key_compare          _M_key_compare;
 397           _Rb_tree_node_base    _M_header;
 398           size_type             _M_node_count; // Keeps track of size of tree.
 399
 400           _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
 401                         const _Key_compare& __comp = _Key_compare())
 402           : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
 403           {
 404             this->_M_header._M_color = _S_red;
 405             this->_M_header._M_parent = 0;
 406             this->_M_header._M_left = &this->_M_header;
 407             this->_M_header._M_right = &this->_M_header;
 408           }
 409         };
 410
 411       // Specialization for _Comparison types that are not capable of
 412       // being base classes / super classes.
 413       template<typename _Key_compare>
 414         struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
 415         {
 416           _Key_compare          _M_key_compare;
 417           _Rb_tree_node_base    _M_header;
 418           size_type             _M_node_count; // Keeps track of size of tree.
 419
 420           _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
 421                         const _Key_compare& __comp = _Key_compare())
 422           : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
 423           {
 424             this->_M_header._M_color = _S_red;
 425             this->_M_header._M_parent = 0;
 426             this->_M_header._M_left = &this->_M_header;
 427             this->_M_header._M_right = &this->_M_header;
 428           }
 429         };
 430
 431       _Rb_tree_impl<_Compare> _M_impl;
 432
 433     protected:
 434       _Base_ptr&
 435       _M_root()
 436       { return this->_M_impl._M_header._M_parent; }
 437
 438       _Const_Base_ptr
 439       _M_root() const
 440       { return this->_M_impl._M_header._M_parent; }
 441
 442       _Base_ptr&
 443       _M_leftmost()
 444       { return this->_M_impl._M_header._M_left; }
 445
 446       _Const_Base_ptr
 447       _M_leftmost() const
 448       { return this->_M_impl._M_header._M_left; }
 449
 450       _Base_ptr&
 451       _M_rightmost()
 452       { return this->_M_impl._M_header._M_right; }
 453
 454       _Const_Base_ptr
 455       _M_rightmost() const
 456       { return this->_M_impl._M_header._M_right; }
 457
 458       _Link_type
 459       _M_begin()
 460       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 461
 462       _Const_Link_type
 463       _M_begin() const
 464       { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_parent); }
 465
 466       _Link_type
 467       _M_end()
 468       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 469
 470       _Const_Link_type
 471       _M_end() const
 472       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 473
 474       static const_reference
 475       _S_value(_Const_Link_type __x)
 476       { return __x->_M_value_field; }
 477
 478       static const _Key&
 479       _S_key(_Const_Link_type __x)
 480       { return _KeyOfValue()(_S_value(__x)); }
 481
 482       static _Link_type
 483       _S_left(_Base_ptr __x)
 484       { return static_cast<_Link_type>(__x->_M_left); }
 485
 486       static _Const_Link_type
 487       _S_left(_Const_Base_ptr __x)
 488       { return static_cast<_Const_Link_type>(__x->_M_left); }
 489
 490       static _Link_type
 491       _S_right(_Base_ptr __x)
 492       { return static_cast<_Link_type>(__x->_M_right); }
 493
 494       static _Const_Link_type
 495       _S_right(_Const_Base_ptr __x)
 496       { return static_cast<_Const_Link_type>(__x->_M_right); }
 497
 498       static const_reference
 499       _S_value(_Const_Base_ptr __x)
 500       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 501
 502       static const _Key&
 503       _S_key(_Const_Base_ptr __x)
 504       { return _KeyOfValue()(_S_value(__x)); }
 505
 506       static _Base_ptr
 507       _S_minimum(_Base_ptr __x)
 508       { return _Rb_tree_node_base::_S_minimum(__x); }
 509
 510       static _Const_Base_ptr
 511       _S_minimum(_Const_Base_ptr __x)
 512       { return _Rb_tree_node_base::_S_minimum(__x); }
 513
 514       static _Base_ptr
 515       _S_maximum(_Base_ptr __x)
 516       { return _Rb_tree_node_base::_S_maximum(__x); }
 517
 518       static _Const_Base_ptr
 519       _S_maximum(_Const_Base_ptr __x)
 520       { return _Rb_tree_node_base::_S_maximum(__x); }
 521
 522     public:
 523       typedef _Rb_tree_iterator<value_type>       iterator;
 524       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 525
 526       typedef std::reverse_iterator<iterator>       reverse_iterator;
 527       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 528
 529     private:
 530       iterator
 531       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 532
 533       _Link_type
 534       _M_copy(_Const_Link_type __x, _Link_type __p);
 535
 536       void
 537       _M_erase(_Link_type __x);
 538
 539     public:
 540       // allocation/deallocation
 541       _Rb_tree()
 542       { }
 543
 544       _Rb_tree(const _Compare& __comp)
 545       : _M_impl(allocator_type(), __comp)
 546       { }
 547
 548       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 549       : _M_impl(__a, __comp)
 550       { }
 551
 552       _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
 553       : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
 554       {
 555         if (__x._M_root() != 0)
 556           {
 557             _M_root() = _M_copy(__x._M_begin(), _M_end());
 558             _M_leftmost() = _S_minimum(_M_root());
 559             _M_rightmost() = _S_maximum(_M_root());
 560             _M_impl._M_node_count = __x._M_impl._M_node_count;
 561           }
 562       }
 563
 564       ~_Rb_tree()
 565       { _M_erase(_M_begin()); }
 566
 567       _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
 568       operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
 569
 570       // Accessors.
 571       _Compare
 572       key_comp() const
 573       { return _M_impl._M_key_compare; }
 574
 575       iterator
 576       begin()
 577       { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
 578
 579       const_iterator
 580       begin() const
 581       { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); }
 582
 583       iterator
 584       end()
 585       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 586
 587       const_iterator
 588       end() const
 589       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 590
 591       reverse_iterator
 592       rbegin()
 593       { return reverse_iterator(end()); }
 594
 595       const_reverse_iterator
 596       rbegin() const
 597       { return const_reverse_iterator(end()); }
 598
 599       reverse_iterator
 600       rend()
 601       { return reverse_iterator(begin()); }
 602
 603       const_reverse_iterator
 604       rend() const
 605       { return const_reverse_iterator(begin()); }
 606
 607       bool
 608       empty() const
 609       { return _M_impl._M_node_count == 0; }
 610
 611       size_type
 612       size() const
 613       { return _M_impl._M_node_count; }
 614
 615       size_type
 616       max_size() const
 617       { return size_type(-1); }
 618
 619       void
 620       swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t);
 621
 622       // Insert/erase.
 623       pair<iterator,bool>
 624       insert_unique(const value_type& __x);
 625
 626       iterator
 627       insert_equal(const value_type& __x);
 628
 629       iterator
 630       insert_unique(iterator __position, const value_type& __x);
 631
 632       iterator
 633       insert_equal(iterator __position, const value_type& __x);
 634
 635       template<typename _InputIterator>
 636       void
 637       insert_unique(_InputIterator __first, _InputIterator __last);
 638
 639       template<typename _InputIterator>
 640       void
 641       insert_equal(_InputIterator __first, _InputIterator __last);
 642
 643       void
 644       erase(iterator __position);
 645
 646       size_type
 647       erase(const key_type& __x);
 648
 649       void
 650       erase(iterator __first, iterator __last);
 651
 652       void
 653       erase(const key_type* __first, const key_type* __last);
 654
 655       void
 656       clear()
 657       {
 658         _M_erase(_M_begin());
 659         _M_leftmost() = _M_end();
 660         _M_root() = 0;
 661         _M_rightmost() = _M_end();
 662         _M_impl._M_node_count = 0;
 663       }
 664
 665       // Set operations.
 666       iterator
 667       find(const key_type& __x);
 668
 669       const_iterator
 670       find(const key_type& __x) const;
 671
 672       size_type
 673       count(const key_type& __x) const;
 674
 675       iterator
 676       lower_bound(const key_type& __x);
 677
 678       const_iterator
 679       lower_bound(const key_type& __x) const;
 680
 681       iterator
 682       upper_bound(const key_type& __x);
 683
 684       const_iterator
 685       upper_bound(const key_type& __x) const;
 686
 687       pair<iterator,iterator>
 688       equal_range(const key_type& __x);
 689
 690       pair<const_iterator, const_iterator>
 691       equal_range(const key_type& __x) const;
 692
 693       // Debugging.
 694       bool
 695       __rb_verify() const;
 696     };
 697
 698   template<typename _Key, typename _Val, typename _KeyOfValue,
 699            typename _Compare, typename _Alloc>
 700     inline bool
 701     operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 702                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 703     {
 704       return __x.size() == __y.size()
 705              && equal(__x.begin(), __x.end(), __y.begin());
 706     }
 707
 708   template<typename _Key, typename _Val, typename _KeyOfValue,
 709            typename _Compare, typename _Alloc>
 710     inline bool
 711     operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 712               const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 713     {
 714       return lexicographical_compare(__x.begin(), __x.end(),
 715                                      __y.begin(), __y.end());
 716     }
 717
 718   template<typename _Key, typename _Val, typename _KeyOfValue,
 719            typename _Compare, typename _Alloc>
 720     inline bool
 721     operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 722                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 723     { return !(__x == __y); }
 724
 725   template<typename _Key, typename _Val, typename _KeyOfValue,
 726            typename _Compare, typename _Alloc>
 727     inline bool
 728     operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 729               const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 730     { return __y < __x; }
 731
 732   template<typename _Key, typename _Val, typename _KeyOfValue,
 733            typename _Compare, typename _Alloc>
 734     inline bool
 735     operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 736                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 737     { return !(__y < __x); }
 738
 739   template<typename _Key, typename _Val, typename _KeyOfValue,
 740            typename _Compare, typename _Alloc>
 741     inline bool
 742     operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 743                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 744     { return !(__x < __y); }
 745
 746   template<typename _Key, typename _Val, typename _KeyOfValue,
 747            typename _Compare, typename _Alloc>
 748     inline void
 749     swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 750          _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 751     { __x.swap(__y); }
 752
 753   template<typename _Key, typename _Val, typename _KeyOfValue,
 754            typename _Compare, typename _Alloc>
 755     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
 756     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 757     operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
 758     {
 759       if (this != &__x)
 760         {
 761           // Note that _Key may be a constant type.
 762           clear();
 763           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 764           if (__x._M_root() != 0)
 765             {
 766               _M_root() = _M_copy(__x._M_begin(), _M_end());
 767               _M_leftmost() = _S_minimum(_M_root());
 768               _M_rightmost() = _S_maximum(_M_root());
 769               _M_impl._M_node_count = __x._M_impl._M_node_count;
 770             }
 771         }
 772       return *this;
 773     }
 774
 775   template<typename _Key, typename _Val, typename _KeyOfValue,
 776            typename _Compare, typename _Alloc>
 777     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
 778     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 779     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 780     {
 781       _Link_type __z = _M_create_node(__v);
 782       bool __insert_left;
 783
 784       __insert_left = __x != 0 || __p == _M_end()
 785                       || _M_impl._M_key_compare(_KeyOfValue()(__v),
 786                                                 _S_key(__p));
 787
 788       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 789                                     this->_M_impl._M_header);
 790       ++_M_impl._M_node_count;
 791       return iterator(__z);
 792     }
 793
 794   template<typename _Key, typename _Val, typename _KeyOfValue,
 795            typename _Compare, typename _Alloc>
 796     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
 797     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 798     insert_equal(const _Val& __v)
 799     {
 800       _Link_type __x = _M_begin();
 801       _Link_type __y = _M_end();
 802       while (__x != 0)
 803         {
 804           __y = __x;
 805           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
 806                 _S_left(__x) : _S_right(__x);
 807         }
 808       return _M_insert(__x, __y, __v);
 809     }
 810
 811   template<typename _Key, typename _Val, typename _KeyOfValue,
 812            typename _Compare, typename _Alloc>
 813     void
 814     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 815     swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
 816     {
 817       if (_M_root() == 0)
 818       {
 819         if (__t._M_root() != 0)
 820         {
 821           _M_root() = __t._M_root();
 822           _M_leftmost() = __t._M_leftmost();
 823           _M_rightmost() = __t._M_rightmost();
 824           _M_root()->_M_parent = _M_end();
 825
 826           __t._M_root() = 0;
 827           __t._M_leftmost() = __t._M_end();
 828           __t._M_rightmost() = __t._M_end();
 829         }
 830       }
 831       else if (__t._M_root() == 0)
 832       {
 833         __t._M_root() = _M_root();
 834         __t._M_leftmost() = _M_leftmost();
 835         __t._M_rightmost() = _M_rightmost();
 836         __t._M_root()->_M_parent = __t._M_end();
 837
 838         _M_root() = 0;
 839         _M_leftmost() = _M_end();
 840         _M_rightmost() = _M_end();
 841       }
 842       else
 843       {
 844         std::swap(_M_root(),__t._M_root());
 845         std::swap(_M_leftmost(),__t._M_leftmost());
 846         std::swap(_M_rightmost(),__t._M_rightmost());
 847
 848         _M_root()->_M_parent = _M_end();
 849         __t._M_root()->_M_parent = __t._M_end();
 850       }
 851       // No need to swap header's color as it does not change.
 852       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
 853       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
 854     }
 855
 856   template<typename _Key, typename _Val, typename _KeyOfValue,
 857            typename _Compare, typename _Alloc>
 858     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
 859     bool>
 860     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 861     insert_unique(const _Val& __v)
 862     {
 863       _Link_type __x = _M_begin();
 864       _Link_type __y = _M_end();
 865       bool __comp = true;
 866       while (__x != 0)
 867         {
 868           __y = __x;
 869           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
 870           __x = __comp ? _S_left(__x) : _S_right(__x);
 871         }
 872       iterator __j = iterator(__y);
 873       if (__comp)
 874         if (__j == begin())
 875           return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 876         else
 877           --__j;
 878       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
 879         return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 880       return pair<iterator,bool>(__j, false);
 881     }
 882
 883   template<typename _Key, typename _Val, typename _KeyOfValue,
 884            typename _Compare, typename _Alloc>
 885     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 886     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 887     insert_unique(iterator __position, const _Val& __v)
 888     {
 889       if (__position._M_node == _M_leftmost())
 890         {
 891           // begin()
 892           if (size() > 0
 893               && _M_impl._M_key_compare(_KeyOfValue()(__v),
 894                                         _S_key(__position._M_node)))
 895             return _M_insert(__position._M_node, __position._M_node, __v);
 896           // First argument just needs to be non-null.
 897           else
 898             return insert_unique(__v).first;
 899         }
 900       else if (__position._M_node == _M_end())
 901         {
 902           // end()
 903           if (_M_impl._M_key_compare(_S_key(_M_rightmost()),
 904                                      _KeyOfValue()(__v)))
 905             return _M_insert(0, _M_rightmost(), __v);
 906           else
 907             return insert_unique(__v).first;
 908         }
 909       else
 910         {
 911           iterator __before = __position;
 912           --__before;
 913           if (_M_impl._M_key_compare(_S_key(__before._M_node),
 914                                      _KeyOfValue()(__v))
 915               && _M_impl._M_key_compare(_KeyOfValue()(__v),
 916                                         _S_key(__position._M_node)))
 917             {
 918               if (_S_right(__before._M_node) == 0)
 919                 return _M_insert(0, __before._M_node, __v);
 920               else
 921                 return _M_insert(__position._M_node, __position._M_node, __v);
 922               // First argument just needs to be non-null.
 923             }
 924           else
 925             return insert_unique(__v).first;
 926         }
 927     }
 928
 929   template<typename _Key, typename _Val, typename _KeyOfValue,
 930            typename _Compare, typename _Alloc>
 931     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
 932     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 933     insert_equal(iterator __position, const _Val& __v)
 934     {
 935       if (__position._M_node == _M_leftmost())
 936         {
 937           // begin()
 938           if (size() > 0
 939               && !_M_impl._M_key_compare(_S_key(__position._M_node),
 940                                          _KeyOfValue()(__v)))
 941             return _M_insert(__position._M_node, __position._M_node, __v);
 942           // first argument just needs to be non-null
 943           else
 944             return insert_equal(__v);
 945         }
 946       else if (__position._M_node == _M_end())
 947         {
 948           // end()
 949           if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
 950                                       _S_key(_M_rightmost())))
 951             return _M_insert(0, _M_rightmost(), __v);
 952           else
 953             return insert_equal(__v);
 954         }
 955       else
 956         {
 957           iterator __before = __position;
 958           --__before;
 959           if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
 960                                       _S_key(__before._M_node))
 961               && !_M_impl._M_key_compare(_S_key(__position._M_node),
 962                                          _KeyOfValue()(__v)))
 963             {
 964               if (_S_right(__before._M_node) == 0)
 965                 return _M_insert(0, __before._M_node, __v);
 966               else
 967                 return _M_insert(__position._M_node, __position._M_node, __v);
 968               // First argument just needs to be non-null.
 969             }
 970           else
 971             return insert_equal(__v);
 972         }
 973     }
 974
 975   template<typename _Key, typename _Val, typename _KoV,
 976            typename _Cmp, typename _Alloc>
 977     template<class _II>
 978       void
 979       _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
 980       insert_equal(_II __first, _II __last)
 981       {
 982         for ( ; __first != __last; ++__first)
 983           insert_equal(*__first);
 984       }
 985
 986   template<typename _Key, typename _Val, typename _KoV,
 987            typename _Cmp, typename _Alloc>
 988     template<class _II>
 989     void
 990     _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
 991     insert_unique(_II __first, _II __last)
 992     {
 993       for ( ; __first != __last; ++__first)
 994         insert_unique(*__first);
 995     }
 996
 997   template<typename _Key, typename _Val, typename _KeyOfValue,
 998            typename _Compare, typename _Alloc>
 999     inline void
1000     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
1001     {
1002       _Link_type __y =
1003         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
1004                                                              this->_M_impl._M_header));
1005       destroy_node(__y);
1006       --_M_impl._M_node_count;
1007     }
1008
1009   template<typename _Key, typename _Val, typename _KeyOfValue,
1010            typename _Compare, typename _Alloc>
1011     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
1012     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
1013     {
1014       pair<iterator,iterator> __p = equal_range(__x);
1015       size_type __n = std::distance(__p.first, __p.second);
1016       erase(__p.first, __p.second);
1017       return __n;
1018     }
1019
1020   template<typename _Key, typename _Val, typename _KoV,
1021            typename _Compare, typename _Alloc>
1022     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1023     _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
1024     _M_copy(_Const_Link_type __x, _Link_type __p)
1025     {
1026       // Structural copy.  __x and __p must be non-null.
1027       _Link_type __top = _M_clone_node(__x);
1028       __top->_M_parent = __p;
1029
1030       try
1031         {
1032           if (__x->_M_right)
1033             __top->_M_right = _M_copy(_S_right(__x), __top);
1034           __p = __top;
1035           __x = _S_left(__x);
1036
1037           while (__x != 0)
1038             {
1039               _Link_type __y = _M_clone_node(__x);
1040               __p->_M_left = __y;
1041               __y->_M_parent = __p;
1042               if (__x->_M_right)
1043                 __y->_M_right = _M_copy(_S_right(__x), __y);
1044               __p = __y;
1045               __x = _S_left(__x);
1046             }
1047         }
1048       catch(...)
1049         {
1050           _M_erase(__top);
1051           __throw_exception_again;
1052         }
1053       return __top;
1054     }
1055
1056   template<typename _Key, typename _Val, typename _KeyOfValue,
1057            typename _Compare, typename _Alloc>
1058     void
1059     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
1060     {
1061       // Erase without rebalancing.
1062       while (__x != 0)
1063         {
1064           _M_erase(_S_right(__x));
1065           _Link_type __y = _S_left(__x);
1066           destroy_node(__x);
1067           __x = __y;
1068         }
1069     }
1070
1071   template<typename _Key, typename _Val, typename _KeyOfValue,
1072            typename _Compare, typename _Alloc>
1073     void
1074     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1075     erase(iterator __first, iterator __last)
1076     {
1077       if (__first == begin() && __last == end())
1078         clear();
1079       else
1080         while (__first != __last) erase(__first++);
1081     }
1082
1083   template<typename _Key, typename _Val, typename _KeyOfValue,
1084            typename _Compare, typename _Alloc>
1085     void
1086     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1087     erase(const _Key* __first, const _Key* __last)
1088     {
1089       while (__first != __last)
1090         erase(*__first++);
1091     }
1092
1093   template<typename _Key, typename _Val, typename _KeyOfValue,
1094            typename _Compare, typename _Alloc>
1095     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1096     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
1097     {
1098       _Link_type __x = _M_begin(); // Current node.
1099       _Link_type __y = _M_end(); // Last node which is not less than __k.
1100
1101       while (__x != 0)
1102         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1103           __y = __x, __x = _S_left(__x);
1104         else
1105           __x = _S_right(__x);
1106
1107       iterator __j = iterator(__y);
1108       return (__j == end()
1109           || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
1110     }
1111
1112   template<typename _Key, typename _Val, typename _KeyOfValue,
1113            typename _Compare, typename _Alloc>
1114     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1115     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1116     find(const _Key& __k) const
1117     {
1118       _Const_Link_type __x = _M_begin(); // Current node.
1119       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1120
1121      while (__x != 0)
1122        {
1123          if (!_M_impl._M_key_compare(_S_key(__x), __k))
1124            __y = __x, __x = _S_left(__x);
1125          else
1126            __x = _S_right(__x);
1127        }
1128      const_iterator __j = const_iterator(__y);
1129      return (__j == end()
1130           || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
1131     }
1132
1133   template<typename _Key, typename _Val, typename _KeyOfValue,
1134            typename _Compare, typename _Alloc>
1135     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
1136     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1137     count(const _Key& __k) const
1138     {
1139       pair<const_iterator, const_iterator> __p = equal_range(__k);
1140       const size_type __n = std::distance(__p.first, __p.second);
1141       return __n;
1142     }
1143
1144   template<typename _Key, typename _Val, typename _KeyOfValue,
1145            typename _Compare, typename _Alloc>
1146     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1147     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1148     lower_bound(const _Key& __k)
1149     {
1150       _Link_type __x = _M_begin(); // Current node.
1151       _Link_type __y = _M_end(); // Last node which is not less than __k.
1152
1153       while (__x != 0)
1154         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1155           __y = __x, __x = _S_left(__x);
1156         else
1157           __x = _S_right(__x);
1158
1159       return iterator(__y);
1160     }
1161
1162   template<typename _Key, typename _Val, typename _KeyOfValue,
1163            typename _Compare, typename _Alloc>
1164     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1165     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1166     lower_bound(const _Key& __k) const
1167     {
1168       _Const_Link_type __x = _M_begin(); // Current node.
1169       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1170
1171       while (__x != 0)
1172         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1173           __y = __x, __x = _S_left(__x);
1174         else
1175           __x = _S_right(__x);
1176
1177       return const_iterator(__y);
1178     }
1179
1180   template<typename _Key, typename _Val, typename _KeyOfValue,
1181            typename _Compare, typename _Alloc>
1182     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1183     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1184     upper_bound(const _Key& __k)
1185     {
1186       _Link_type __x = _M_begin(); // Current node.
1187       _Link_type __y = _M_end(); // Last node which is greater than __k.
1188
1189       while (__x != 0)
1190         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1191           __y = __x, __x = _S_left(__x);
1192         else
1193           __x = _S_right(__x);
1194
1195       return iterator(__y);
1196     }
1197
1198   template<typename _Key, typename _Val, typename _KeyOfValue,
1199            typename _Compare, typename _Alloc>
1200     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1201     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1202     upper_bound(const _Key& __k) const
1203     {
1204       _Const_Link_type __x = _M_begin(); // Current node.
1205       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1206
1207       while (__x != 0)
1208         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1209           __y = __x, __x = _S_left(__x);
1210         else
1211           __x = _S_right(__x);
1212
1213       return const_iterator(__y);
1214     }
1215
1216   template<typename _Key, typename _Val, typename _KeyOfValue,
1217            typename _Compare, typename _Alloc>
1218     inline
1219     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,
1220                            _Compare,_Alloc>::iterator,
1221          typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
1222     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1223     equal_range(const _Key& __k)
1224     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1225
1226   template<typename _Key, typename _Val, typename _KoV,
1227            typename _Compare, typename _Alloc>
1228     inline
1229     pair<typename _Rb_tree<_Key, _Val, _KoV,
1230                            _Compare, _Alloc>::const_iterator,
1231          typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1232     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1233     equal_range(const _Key& __k) const
1234     { return pair<const_iterator, const_iterator>(lower_bound(__k),
1235                                                   upper_bound(__k)); }
1236
1237   unsigned int
1238   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1239                        const _Rb_tree_node_base* __root);
1240
1241   template<typename _Key, typename _Val, typename _KeyOfValue,
1242            typename _Compare, typename _Alloc>
1243     bool
1244     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1245     {
1246       if (_M_impl._M_node_count == 0 || begin() == end())
1247         return _M_impl._M_node_count == 0 && begin() == end()
1248                && this->_M_impl._M_header._M_left == _M_end()
1249                && this->_M_impl._M_header._M_right == _M_end();
1250
1251       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1252       for (const_iterator __it = begin(); __it != end(); ++__it)
1253         {
1254           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1255           _Const_Link_type __L = _S_left(__x);
1256           _Const_Link_type __R = _S_right(__x);
1257
1258           if (__x->_M_color == _S_red)
1259             if ((__L && __L->_M_color == _S_red)
1260                 || (__R && __R->_M_color == _S_red))
1261               return false;
1262
1263           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1264             return false;
1265           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1266             return false;
1267
1268           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1269             return false;
1270         }
1271
1272       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1273         return false;
1274       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1275         return false;
1276       return true;
1277     }
1278 } // namespace std
1279
1280 #endif
1281