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