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

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