libstdc++-v3/bits/stl_tree.h

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