libstdc++/stl/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 <stl_algobase.h>
  57 #include <stl_alloc.h>
  58 #include <stl_construct.h>
  59 #include <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 = __STL_DEFAULT_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 void
 784 swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
 785      _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
 786 {
 787   __x.swap(__y);
 788 }
 789
 790 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 791
 792
 793 template <class _Key, class _Value, class _KeyOfValue,
 794           class _Compare, class _Alloc>
 795 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>&
 796 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
 797   ::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
 798 {
 799   if (this != &__x) {
 800                                 // Note that _Key may be a constant type.
 801     clear();
 802     _M_node_count = 0;
 803     _M_key_compare = __x._M_key_compare;
 804     if (__x._M_root() == 0) {
 805       _M_root() = 0;
 806       _M_leftmost() = _M_header;
 807       _M_rightmost() = _M_header;
 808     }
 809     else {
 810       _M_root() = _M_copy(__x._M_root(), _M_header);
 811       _M_leftmost() = _S_minimum(_M_root());
 812       _M_rightmost() = _S_maximum(_M_root());
 813       _M_node_count = __x._M_node_count;
 814     }
 815   }
 816   return *this;
 817 }
 818
 819 template <class _Key, class _Value, class _KeyOfValue,
 820           class _Compare, class _Alloc>
 821 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
 822 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
 823   ::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
 824 {
 825   _Link_type __x = (_Link_type) __x_;
 826   _Link_type __y = (_Link_type) __y_;
 827   _Link_type __z;
 828
 829   if (__y == _M_header || __x != 0 ||
 830       _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) {
 831     __z = _M_create_node(__v);
 832     _S_left(__y) = __z;               // also makes _M_leftmost() = __z
 833                                       //    when __y == _M_header
 834     if (__y == _M_header) {
 835       _M_root() = __z;
 836       _M_rightmost() = __z;
 837     }
 838     else if (__y == _M_leftmost())
 839       _M_leftmost() = __z;   // maintain _M_leftmost() pointing to min node
 840   }
 841   else {
 842     __z = _M_create_node(__v);
 843     _S_right(__y) = __z;
 844     if (__y == _M_rightmost())
 845       _M_rightmost() = __z;  // maintain _M_rightmost() pointing to max node
 846   }
 847   _S_parent(__z) = __y;
 848   _S_left(__z) = 0;
 849   _S_right(__z) = 0;
 850   _Rb_tree_rebalance(__z, _M_header->_M_parent);
 851   ++_M_node_count;
 852   return iterator(__z);
 853 }
 854
 855 template <class _Key, class _Value, class _KeyOfValue,
 856           class _Compare, class _Alloc>
 857 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
 858 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
 859   ::insert_equal(const _Value& __v)
 860 {
 861   _Link_type __y = _M_header;
 862   _Link_type __x = _M_root();
 863   while (__x != 0) {
 864     __y = __x;
 865     __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
 866             _S_left(__x) : _S_right(__x);
 867   }
 868   return _M_insert(__x, __y, __v);
 869 }
 870
 871
 872 template <class _Key, class _Value, class _KeyOfValue,
 873           class _Compare, class _Alloc>
 874 pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
 875      bool>
 876 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
 877   ::insert_unique(const _Value& __v)
 878 {
 879   _Link_type __y = _M_header;
 880   _Link_type __x = _M_root();
 881   bool __comp = true;
 882   while (__x != 0) {
 883     __y = __x;
 884     __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
 885     __x = __comp ? _S_left(__x) : _S_right(__x);
 886   }
 887   iterator __j = iterator(__y);
 888   if (__comp)
 889     if (__j == begin())
 890       return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 891     else
 892       --__j;
 893   if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
 894     return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 895   return pair<iterator,bool>(__j, false);
 896 }
 897
 898
 899 template <class _Key, class _Val, class _KeyOfValue,
 900           class _Compare, class _Alloc>
 901 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 902 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>
 903   ::insert_unique(iterator __position, const _Val& __v)
 904 {
 905   if (__position._M_node == _M_header->_M_left) { // begin()
 906     if (size() > 0 &&
 907         _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
 908       return _M_insert(__position._M_node, __position._M_node, __v);
 909     // first argument just needs to be non-null
 910     else
 911       return insert_unique(__v).first;
 912   } else if (__position._M_node == _M_header) { // end()
 913     if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
 914       return _M_insert(0, _M_rightmost(), __v);
 915     else
 916       return insert_unique(__v).first;
 917   } else {
 918     iterator __before = __position;
 919     --__before;
 920     if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v))
 921         && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) {
 922       if (_S_right(__before._M_node) == 0)
 923         return _M_insert(0, __before._M_node, __v);
 924       else
 925         return _M_insert(__position._M_node, __position._M_node, __v);
 926     // first argument just needs to be non-null
 927     } else
 928       return insert_unique(__v).first;
 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_equal(iterator __position, const _Val& __v)
 937 {
 938   if (__position._M_node == _M_header->_M_left) { // begin()
 939     if (size() > 0 &&
 940         _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
 941       return _M_insert(__position._M_node, __position._M_node, __v);
 942     // first argument just needs to be non-null
 943     else
 944       return insert_equal(__v);
 945   } else if (__position._M_node == _M_header) {// end()
 946     if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
 947       return _M_insert(0, _M_rightmost(), __v);
 948     else
 949       return insert_equal(__v);
 950   } else {
 951     iterator __before = __position;
 952     --__before;
 953     if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
 954         && !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) {
 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_equal(__v);
 962   }
 963 }
 964
 965 #ifdef __STL_MEMBER_TEMPLATES
 966
 967 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
 968   template<class _II>
 969 void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
 970   ::insert_equal(_II __first, _II __last)
 971 {
 972   for ( ; __first != __last; ++__first)
 973     insert_equal(*__first);
 974 }
 975
 976 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
 977   template<class _II>
 978 void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
 979   ::insert_unique(_II __first, _II __last) {
 980   for ( ; __first != __last; ++__first)
 981     insert_unique(*__first);
 982 }
 983
 984 #else /* __STL_MEMBER_TEMPLATES */
 985
 986 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
 987 void
 988 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
 989   ::insert_equal(const _Val* __first, const _Val* __last)
 990 {
 991   for ( ; __first != __last; ++__first)
 992     insert_equal(*__first);
 993 }
 994
 995 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
 996 void
 997 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
 998   ::insert_equal(const_iterator __first, const_iterator __last)
 999 {
1000   for ( ; __first != __last; ++__first)
1001     insert_equal(*__first);
1002 }
1003
1004 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
1005 void
1006 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
1007   ::insert_unique(const _Val* __first, const _Val* __last)
1008 {
1009   for ( ; __first != __last; ++__first)
1010     insert_unique(*__first);
1011 }
1012
1013 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
1014 void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
1015   ::insert_unique(const_iterator __first, const_iterator __last)
1016 {
1017   for ( ; __first != __last; ++__first)
1018     insert_unique(*__first);
1019 }
1020
1021 #endif /* __STL_MEMBER_TEMPLATES */
1022
1023 template <class _Key, class _Value, class _KeyOfValue,
1024           class _Compare, class _Alloc>
1025 inline void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1026   ::erase(iterator __position)
1027 {
1028   _Link_type __y =
1029     (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
1030                                               _M_header->_M_parent,
1031                                               _M_header->_M_left,
1032                                               _M_header->_M_right);
1033   destroy_node(__y);
1034   --_M_node_count;
1035 }
1036
1037 template <class _Key, class _Value, class _KeyOfValue,
1038           class _Compare, class _Alloc>
1039 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
1040 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
1041 {
1042   pair<iterator,iterator> __p = equal_range(__x);
1043   size_type __n = 0;
1044   distance(__p.first, __p.second, __n);
1045   erase(__p.first, __p.second);
1046   return __n;
1047 }
1048
1049 template <class _Key, class _Val, class _KoV, class _Compare, class _Alloc>
1050 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1051 _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>
1052   ::_M_copy(_Link_type __x, _Link_type __p)
1053 {
1054                         // structural copy.  __x and __p must be non-null.
1055   _Link_type __top = _M_clone_node(__x);
1056   __top->_M_parent = __p;
1057
1058   __STL_TRY {
1059     if (__x->_M_right)
1060       __top->_M_right = _M_copy(_S_right(__x), __top);
1061     __p = __top;
1062     __x = _S_left(__x);
1063
1064     while (__x != 0) {
1065       _Link_type __y = _M_clone_node(__x);
1066       __p->_M_left = __y;
1067       __y->_M_parent = __p;
1068       if (__x->_M_right)
1069         __y->_M_right = _M_copy(_S_right(__x), __y);
1070       __p = __y;
1071       __x = _S_left(__x);
1072     }
1073   }
1074   __STL_UNWIND(_M_erase(__top));
1075
1076   return __top;
1077 }
1078
1079 template <class _Key, class _Value, class _KeyOfValue,
1080           class _Compare, class _Alloc>
1081 void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1082   ::_M_erase(_Link_type __x)
1083 {
1084                                 // erase without rebalancing
1085   while (__x != 0) {
1086     _M_erase(_S_right(__x));
1087     _Link_type __y = _S_left(__x);
1088     destroy_node(__x);
1089     __x = __y;
1090   }
1091 }
1092
1093 template <class _Key, class _Value, class _KeyOfValue,
1094           class _Compare, class _Alloc>
1095 void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1096   ::erase(iterator __first, iterator __last)
1097 {
1098   if (__first == begin() && __last == end())
1099     clear();
1100   else
1101     while (__first != __last) erase(__first++);
1102 }
1103
1104 template <class _Key, class _Value, class _KeyOfValue,
1105           class _Compare, class _Alloc>
1106 void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1107   ::erase(const _Key* __first, const _Key* __last)
1108 {
1109   while (__first != __last) erase(*__first++);
1110 }
1111
1112 template <class _Key, class _Value, class _KeyOfValue,
1113           class _Compare, class _Alloc>
1114 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
1115 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
1116 {
1117   _Link_type __y = _M_header;      // Last node which is not less than __k.
1118   _Link_type __x = _M_root();      // Current node.
1119
1120   while (__x != 0)
1121     if (!_M_key_compare(_S_key(__x), __k))
1122       __y = __x, __x = _S_left(__x);
1123     else
1124       __x = _S_right(__x);
1125
1126   iterator __j = iterator(__y);
1127   return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
1128      end() : __j;
1129 }
1130
1131 template <class _Key, class _Value, class _KeyOfValue,
1132           class _Compare, class _Alloc>
1133 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
1134 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) const
1135 {
1136   _Link_type __y = _M_header; /* Last node which is not less than __k. */
1137   _Link_type __x = _M_root(); /* Current node. */
1138
1139   while (__x != 0) {
1140     if (!_M_key_compare(_S_key(__x), __k))
1141       __y = __x, __x = _S_left(__x);
1142     else
1143       __x = _S_right(__x);
1144   }
1145   const_iterator __j = const_iterator(__y);
1146   return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
1147     end() : __j;
1148 }
1149
1150 template <class _Key, class _Value, class _KeyOfValue,
1151           class _Compare, class _Alloc>
1152 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
1153 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1154   ::count(const _Key& __k) const
1155 {
1156   pair<const_iterator, const_iterator> __p = equal_range(__k);
1157   size_type __n = 0;
1158   distance(__p.first, __p.second, __n);
1159   return __n;
1160 }
1161
1162 template <class _Key, class _Value, class _KeyOfValue,
1163           class _Compare, class _Alloc>
1164 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
1165 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1166   ::lower_bound(const _Key& __k)
1167 {
1168   _Link_type __y = _M_header; /* Last node which is not less than __k. */
1169   _Link_type __x = _M_root(); /* Current node. */
1170
1171   while (__x != 0)
1172     if (!_M_key_compare(_S_key(__x), __k))
1173       __y = __x, __x = _S_left(__x);
1174     else
1175       __x = _S_right(__x);
1176
1177   return iterator(__y);
1178 }
1179
1180 template <class _Key, class _Value, class _KeyOfValue,
1181           class _Compare, class _Alloc>
1182 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
1183 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1184   ::lower_bound(const _Key& __k) const
1185 {
1186   _Link_type __y = _M_header; /* Last node which is not less than __k. */
1187   _Link_type __x = _M_root(); /* Current node. */
1188
1189   while (__x != 0)
1190     if (!_M_key_compare(_S_key(__x), __k))
1191       __y = __x, __x = _S_left(__x);
1192     else
1193       __x = _S_right(__x);
1194
1195   return const_iterator(__y);
1196 }
1197
1198 template <class _Key, class _Value, class _KeyOfValue,
1199           class _Compare, class _Alloc>
1200 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
1201 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1202   ::upper_bound(const _Key& __k)
1203 {
1204   _Link_type __y = _M_header; /* Last node which is greater than __k. */
1205   _Link_type __x = _M_root(); /* Current node. */
1206
1207    while (__x != 0)
1208      if (_M_key_compare(__k, _S_key(__x)))
1209        __y = __x, __x = _S_left(__x);
1210      else
1211        __x = _S_right(__x);
1212
1213    return iterator(__y);
1214 }
1215
1216 template <class _Key, class _Value, class _KeyOfValue,
1217           class _Compare, class _Alloc>
1218 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
1219 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1220   ::upper_bound(const _Key& __k) const
1221 {
1222   _Link_type __y = _M_header; /* Last node which is greater than __k. */
1223   _Link_type __x = _M_root(); /* Current node. */
1224
1225    while (__x != 0)
1226      if (_M_key_compare(__k, _S_key(__x)))
1227        __y = __x, __x = _S_left(__x);
1228      else
1229        __x = _S_right(__x);
1230
1231    return const_iterator(__y);
1232 }
1233
1234 template <class _Key, class _Value, class _KeyOfValue,
1235           class _Compare, class _Alloc>
1236 inline
1237 pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
1238      typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator>
1239 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1240   ::equal_range(const _Key& __k)
1241 {
1242   return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k));
1243 }
1244
1245 template <class _Key, class _Value, class _KoV, class _Compare, class _Alloc>
1246 inline
1247 pair<typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator,
1248      typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator>
1249 _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>
1250   ::equal_range(const _Key& __k) const
1251 {
1252   return pair<const_iterator,const_iterator>(lower_bound(__k),
1253                                              upper_bound(__k));
1254 }
1255
1256 inline int
1257 __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
1258 {
1259   if (__node == 0)
1260     return 0;
1261   else {
1262     int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
1263     if (__node == __root)
1264       return __bc;
1265     else
1266       return __bc + __black_count(__node->_M_parent, __root);
1267   }
1268 }
1269
1270 template <class _Key, class _Value, class _KeyOfValue,
1271           class _Compare, class _Alloc>
1272 bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1273 {
1274   if (_M_node_count == 0 || begin() == end())
1275     return _M_node_count == 0 && begin() == end() &&
1276       _M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
1277
1278   int __len = __black_count(_M_leftmost(), _M_root());
1279   for (const_iterator __it = begin(); __it != end(); ++__it) {
1280     _Link_type __x = (_Link_type) __it._M_node;
1281     _Link_type __L = _S_left(__x);
1282     _Link_type __R = _S_right(__x);
1283
1284     if (__x->_M_color == _S_rb_tree_red)
1285       if ((__L && __L->_M_color == _S_rb_tree_red) ||
1286           (__R && __R->_M_color == _S_rb_tree_red))
1287         return false;
1288
1289     if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
1290       return false;
1291     if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
1292       return false;
1293
1294     if (!__L && !__R && __black_count(__x, _M_root()) != __len)
1295       return false;
1296   }
1297
1298   if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1299     return false;
1300   if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1301     return false;
1302
1303   return true;
1304 }
1305
1306 // Class rb_tree is not part of the C++ standard.  It is provided for
1307 // compatibility with the HP STL.
1308
1309 template <class _Key, class _Value, class _KeyOfValue, class _Compare,
1310           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
1311 struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>
1312 {
1313   typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
1314   typedef typename _Base::allocator_type allocator_type;
1315
1316   rb_tree(const _Compare& __comp = _Compare(),
1317           const allocator_type& __a = allocator_type())
1318     : _Base(__comp, __a) {}
1319
1320   ~rb_tree() {}
1321 };
1322
1323 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
1324 #pragma reset woff 1375
1325 #endif
1326
1327 __STL_END_NAMESPACE
1328
1329 #endif /* __SGI_STL_INTERNAL_TREE_H */
1330
1331 // Local Variables:
1332 // mode:C++
1333 // End: