libstdc++-v3/include/bits/stl_tree.h

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