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