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 _M_create_node(const value_type& __x)
 556   {
 557     _Link_type __tmp = _M_get_node();
 558     __STL_TRY {
 559       construct(&__tmp->_M_value_field, __x);
 560     }
 561     __STL_UNWIND(_M_put_node(__tmp));
 562     return __tmp;
 563   }
 564
 565   _Link_type _M_clone_node(_Link_type __x)
 566   {
 567     _Link_type __tmp = _M_create_node(__x->_M_value_field);
 568     __tmp->_M_color = __x->_M_color;
 569     __tmp->_M_left = 0;
 570     __tmp->_M_right = 0;
 571     return __tmp;
 572   }
 573
 574   void destroy_node(_Link_type __p)
 575   {
 576     destroy(&__p->_M_value_field);
 577     _M_put_node(__p);
 578   }
 579
 580 protected:
 581   size_type _M_node_count; // keeps track of size of tree
 582   _Compare _M_key_compare;
 583
 584   _Link_type& _M_root() const
 585     { return (_Link_type&) _M_header->_M_parent; }
 586   _Link_type& _M_leftmost() const
 587     { return (_Link_type&) _M_header->_M_left; }
 588   _Link_type& _M_rightmost() const
 589     { return (_Link_type&) _M_header->_M_right; }
 590
 591   static _Link_type& _S_left(_Link_type __x)
 592     { return (_Link_type&)(__x->_M_left); }
 593   static _Link_type& _S_right(_Link_type __x)
 594     { return (_Link_type&)(__x->_M_right); }
 595   static _Link_type& _S_parent(_Link_type __x)
 596     { return (_Link_type&)(__x->_M_parent); }
 597   static reference _S_value(_Link_type __x)
 598     { return __x->_M_value_field; }
 599   static const _Key& _S_key(_Link_type __x)
 600     { return _KeyOfValue()(_S_value(__x)); }
 601   static _Color_type& _S_color(_Link_type __x)
 602     { return (_Color_type&)(__x->_M_color); }
 603
 604   static _Link_type& _S_left(_Base_ptr __x)
 605     { return (_Link_type&)(__x->_M_left); }
 606   static _Link_type& _S_right(_Base_ptr __x)
 607     { return (_Link_type&)(__x->_M_right); }
 608   static _Link_type& _S_parent(_Base_ptr __x)
 609     { return (_Link_type&)(__x->_M_parent); }
 610   static reference _S_value(_Base_ptr __x)
 611     { return ((_Link_type)__x)->_M_value_field; }
 612   static const _Key& _S_key(_Base_ptr __x)
 613     { return _KeyOfValue()(_S_value(_Link_type(__x)));}
 614   static _Color_type& _S_color(_Base_ptr __x)
 615     { return (_Color_type&)(_Link_type(__x)->_M_color); }
 616
 617   static _Link_type _S_minimum(_Link_type __x)
 618     { return (_Link_type)  _Rb_tree_node_base::_S_minimum(__x); }
 619
 620   static _Link_type _S_maximum(_Link_type __x)
 621     { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
 622
 623 public:
 624   typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
 625   typedef _Rb_tree_iterator<value_type, const_reference, const_pointer>
 626           const_iterator;
 627
 628   typedef reverse_iterator<const_iterator> const_reverse_iterator;
 629   typedef reverse_iterator<iterator> reverse_iterator;
 630
 631 private:
 632   iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 633   _Link_type _M_copy(_Link_type __x, _Link_type __p);
 634   void _M_erase(_Link_type __x);
 635
 636 public:
 637                                 // allocation/deallocation
 638   _Rb_tree()
 639     : _Base(allocator_type()), _M_node_count(0), _M_key_compare()
 640     { _M_empty_initialize(); }
 641
 642   _Rb_tree(const _Compare& __comp)
 643     : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
 644     { _M_empty_initialize(); }
 645
 646   _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 647     : _Base(__a), _M_node_count(0), _M_key_compare(__comp)
 648     { _M_empty_initialize(); }
 649
 650   _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
 651     : _Base(__x.get_allocator()),
 652       _M_node_count(0), _M_key_compare(__x._M_key_compare)
 653   {
 654     if (__x._M_root() == 0)
 655       _M_empty_initialize();
 656     else {
 657       _S_color(_M_header) = _S_rb_tree_red;
 658       _M_root() = _M_copy(__x._M_root(), _M_header);
 659       _M_leftmost() = _S_minimum(_M_root());
 660       _M_rightmost() = _S_maximum(_M_root());
 661     }
 662     _M_node_count = __x._M_node_count;
 663   }
 664   ~_Rb_tree() { clear(); }
 665   _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>&
 666   operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);
 667
 668 private:
 669   void _M_empty_initialize() {
 670     _S_color(_M_header) = _S_rb_tree_red; // used to distinguish header from
 671                                           // __root, in iterator.operator++
 672     _M_root() = 0;
 673     _M_leftmost() = _M_header;
 674     _M_rightmost() = _M_header;
 675   }
 676
 677 public:
 678                                 // accessors:
 679   _Compare key_comp() const { return _M_key_compare; }
 680   iterator begin() { return _M_leftmost(); }
 681   const_iterator begin() const { return _M_leftmost(); }
 682   iterator end() { return _M_header; }
 683   const_iterator end() const { return _M_header; }
 684   reverse_iterator rbegin() { return reverse_iterator(end()); }
 685   const_reverse_iterator rbegin() const {
 686     return const_reverse_iterator(end());
 687   }
 688   reverse_iterator rend() { return reverse_iterator(begin()); }
 689   const_reverse_iterator rend() const {
 690     return const_reverse_iterator(begin());
 691   }
 692   bool empty() const { return _M_node_count == 0; }
 693   size_type size() const { return _M_node_count; }
 694   size_type max_size() const { return size_type(-1); }
 695
 696   void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) {
 697     std::swap(_M_header, __t._M_header);
 698     std::swap(_M_node_count, __t._M_node_count);
 699     std::swap(_M_key_compare, __t._M_key_compare);
 700   }
 701
 702 public:
 703                                 // insert/erase
 704   pair<iterator,bool> insert_unique(const value_type& __x);
 705   iterator insert_equal(const value_type& __x);
 706
 707   iterator insert_unique(iterator __position, const value_type& __x);
 708   iterator insert_equal(iterator __position, const value_type& __x);
 709
 710   template <class _InputIterator>
 711   void insert_unique(_InputIterator __first, _InputIterator __last);
 712   template <class _InputIterator>
 713   void insert_equal(_InputIterator __first, _InputIterator __last);
 714
 715   void erase(iterator __position);
 716   size_type erase(const key_type& __x);
 717   void erase(iterator __first, iterator __last);
 718   void erase(const key_type* __first, const key_type* __last);
 719   void clear() {
 720     if (_M_node_count != 0) {
 721       _M_erase(_M_root());
 722       _M_leftmost() = _M_header;
 723       _M_root() = 0;
 724       _M_rightmost() = _M_header;
 725       _M_node_count = 0;
 726     }
 727   }
 728
 729 public:
 730                                 // set operations:
 731   iterator find(const key_type& __x);
 732   const_iterator find(const key_type& __x) const;
 733   size_type count(const key_type& __x) const;
 734   iterator lower_bound(const key_type& __x);
 735   const_iterator lower_bound(const key_type& __x) const;
 736   iterator upper_bound(const key_type& __x);
 737   const_iterator upper_bound(const key_type& __x) const;
 738   pair<iterator,iterator> equal_range(const key_type& __x);
 739   pair<const_iterator, const_iterator> equal_range(const key_type& __x) const;
 740
 741 public:
 742                                 // Debugging.
 743   bool __rb_verify() const;
 744 };
 745
 746 template <class _Key, class _Value, class _KeyOfValue,
 747           class _Compare, class _Alloc>
 748 inline bool
 749 operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
 750            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
 751 {
 752   return __x.size() == __y.size() &&
 753          equal(__x.begin(), __x.end(), __y.begin());
 754 }
 755
 756 template <class _Key, class _Value, class _KeyOfValue,
 757           class _Compare, class _Alloc>
 758 inline bool
 759 operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
 760           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
 761 {
 762   return lexicographical_compare(__x.begin(), __x.end(),
 763                                  __y.begin(), __y.end());
 764 }
 765
 766 template <class _Key, class _Value, class _KeyOfValue,
 767           class _Compare, class _Alloc>
 768 inline bool
 769 operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
 770            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
 771   return !(__x == __y);
 772 }
 773
 774 template <class _Key, class _Value, class _KeyOfValue,
 775           class _Compare, class _Alloc>
 776 inline bool
 777 operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
 778           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
 779   return __y < __x;
 780 }
 781
 782 template <class _Key, class _Value, class _KeyOfValue,
 783           class _Compare, class _Alloc>
 784 inline bool
 785 operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
 786            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
 787   return !(__y < __x);
 788 }
 789
 790 template <class _Key, class _Value, class _KeyOfValue,
 791           class _Compare, class _Alloc>
 792 inline bool
 793 operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
 794            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
 795   return !(__x < __y);
 796 }
 797
 798
 799 template <class _Key, class _Value, class _KeyOfValue,
 800           class _Compare, class _Alloc>
 801 inline void
 802 swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
 803      _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
 804 {
 805   __x.swap(__y);
 806 }
 807
 808
 809 template <class _Key, class _Value, class _KeyOfValue,
 810           class _Compare, class _Alloc>
 811 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>&
 812 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
 813   ::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
 814 {
 815   if (this != &__x) {
 816                                 // Note that _Key may be a constant type.
 817     clear();
 818     _M_node_count = 0;
 819     _M_key_compare = __x._M_key_compare;
 820     if (__x._M_root() == 0) {
 821       _M_root() = 0;
 822       _M_leftmost() = _M_header;
 823       _M_rightmost() = _M_header;
 824     }
 825     else {
 826       _M_root() = _M_copy(__x._M_root(), _M_header);
 827       _M_leftmost() = _S_minimum(_M_root());
 828       _M_rightmost() = _S_maximum(_M_root());
 829       _M_node_count = __x._M_node_count;
 830     }
 831   }
 832   return *this;
 833 }
 834
 835 template <class _Key, class _Value, class _KeyOfValue,
 836           class _Compare, class _Alloc>
 837 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
 838 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
 839   ::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
 840 {
 841   _Link_type __x = (_Link_type) __x_;
 842   _Link_type __y = (_Link_type) __y_;
 843   _Link_type __z;
 844
 845   if (__y == _M_header || __x != 0 ||
 846       _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) {
 847     __z = _M_create_node(__v);
 848     _S_left(__y) = __z;               // also makes _M_leftmost() = __z
 849                                       //    when __y == _M_header
 850     if (__y == _M_header) {
 851       _M_root() = __z;
 852       _M_rightmost() = __z;
 853     }
 854     else if (__y == _M_leftmost())
 855       _M_leftmost() = __z;   // maintain _M_leftmost() pointing to min node
 856   }
 857   else {
 858     __z = _M_create_node(__v);
 859     _S_right(__y) = __z;
 860     if (__y == _M_rightmost())
 861       _M_rightmost() = __z;  // maintain _M_rightmost() pointing to max node
 862   }
 863   _S_parent(__z) = __y;
 864   _S_left(__z) = 0;
 865   _S_right(__z) = 0;
 866   _Rb_tree_rebalance(__z, _M_header->_M_parent);
 867   ++_M_node_count;
 868   return iterator(__z);
 869 }
 870
 871 template <class _Key, class _Value, class _KeyOfValue,
 872           class _Compare, class _Alloc>
 873 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
 874 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
 875   ::insert_equal(const _Value& __v)
 876 {
 877   _Link_type __y = _M_header;
 878   _Link_type __x = _M_root();
 879   while (__x != 0) {
 880     __y = __x;
 881     __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
 882             _S_left(__x) : _S_right(__x);
 883   }
 884   return _M_insert(__x, __y, __v);
 885 }
 886
 887
 888 template <class _Key, class _Value, class _KeyOfValue,
 889           class _Compare, class _Alloc>
 890 pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
 891      bool>
 892 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
 893   ::insert_unique(const _Value& __v)
 894 {
 895   _Link_type __y = _M_header;
 896   _Link_type __x = _M_root();
 897   bool __comp = true;
 898   while (__x != 0) {
 899     __y = __x;
 900     __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
 901     __x = __comp ? _S_left(__x) : _S_right(__x);
 902   }
 903   iterator __j = iterator(__y);
 904   if (__comp)
 905     if (__j == begin())
 906       return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 907     else
 908       --__j;
 909   if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
 910     return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 911   return pair<iterator,bool>(__j, false);
 912 }
 913
 914
 915 template <class _Key, class _Val, class _KeyOfValue,
 916           class _Compare, class _Alloc>
 917 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 918 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>
 919   ::insert_unique(iterator __position, const _Val& __v)
 920 {
 921   if (__position._M_node == _M_header->_M_left) { // begin()
 922     if (size() > 0 &&
 923        _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
 924       return _M_insert(__position._M_node, __position._M_node, __v);
 925     // first argument just needs to be non-null
 926     else
 927       return insert_unique(__v).first;
 928   } else if (__position._M_node == _M_header) { // end()
 929     if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
 930       return _M_insert(0, _M_rightmost(), __v);
 931     else
 932       return insert_unique(__v).first;
 933   } else {
 934     iterator __before = __position;
 935     --__before;
 936     if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v))
 937         && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) {
 938       if (_S_right(__before._M_node) == 0)
 939         return _M_insert(0, __before._M_node, __v);
 940       else
 941         return _M_insert(__position._M_node, __position._M_node, __v);
 942     // first argument just needs to be non-null
 943     } else
 944       return insert_unique(__v).first;
 945   }
 946 }
 947
 948 template <class _Key, class _Val, class _KeyOfValue,
 949           class _Compare, class _Alloc>
 950 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
 951 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>
 952   ::insert_equal(iterator __position, const _Val& __v)
 953 {
 954   if (__position._M_node == _M_header->_M_left) { // begin()
 955     if (size() > 0 &&
 956         !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
 957       return _M_insert(__position._M_node, __position._M_node, __v);
 958     // first argument just needs to be non-null
 959     else
 960       return insert_equal(__v);
 961   } else if (__position._M_node == _M_header) {// end()
 962     if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
 963       return _M_insert(0, _M_rightmost(), __v);
 964     else
 965       return insert_equal(__v);
 966   } else {
 967     iterator __before = __position;
 968     --__before;
 969     if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
 970         && !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) {
 971       if (_S_right(__before._M_node) == 0)
 972         return _M_insert(0, __before._M_node, __v);
 973       else
 974         return _M_insert(__position._M_node, __position._M_node, __v);
 975     // first argument just needs to be non-null
 976     } else
 977       return insert_equal(__v);
 978   }
 979 }
 980
 981 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
 982   template<class _II>
 983 void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
 984   ::insert_equal(_II __first, _II __last)
 985 {
 986   for ( ; __first != __last; ++__first)
 987     insert_equal(*__first);
 988 }
 989
 990 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
 991   template<class _II>
 992 void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
 993   ::insert_unique(_II __first, _II __last) {
 994   for ( ; __first != __last; ++__first)
 995     insert_unique(*__first);
 996 }
 997
 998 template <class _Key, class _Value, class _KeyOfValue,
 999           class _Compare, class _Alloc>
1000 inline void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1001   ::erase(iterator __position)
1002 {
1003   _Link_type __y =
1004     (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
1005                                               _M_header->_M_parent,
1006                                               _M_header->_M_left,
1007                                               _M_header->_M_right);
1008   destroy_node(__y);
1009   --_M_node_count;
1010 }
1011
1012 template <class _Key, class _Value, class _KeyOfValue,
1013           class _Compare, class _Alloc>
1014 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
1015 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
1016 {
1017   pair<iterator,iterator> __p = equal_range(__x);
1018   size_type __n = 0;
1019   distance(__p.first, __p.second, __n);
1020   erase(__p.first, __p.second);
1021   return __n;
1022 }
1023
1024 template <class _Key, class _Val, class _KoV, class _Compare, class _Alloc>
1025 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1026 _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>
1027   ::_M_copy(_Link_type __x, _Link_type __p)
1028 {
1029                         // structural copy.  __x and __p must be non-null.
1030   _Link_type __top = _M_clone_node(__x);
1031   __top->_M_parent = __p;
1032
1033   __STL_TRY {
1034     if (__x->_M_right)
1035       __top->_M_right = _M_copy(_S_right(__x), __top);
1036     __p = __top;
1037     __x = _S_left(__x);
1038
1039     while (__x != 0) {
1040       _Link_type __y = _M_clone_node(__x);
1041       __p->_M_left = __y;
1042       __y->_M_parent = __p;
1043       if (__x->_M_right)
1044         __y->_M_right = _M_copy(_S_right(__x), __y);
1045       __p = __y;
1046       __x = _S_left(__x);
1047     }
1048   }
1049   __STL_UNWIND(_M_erase(__top));
1050
1051   return __top;
1052 }
1053
1054 template <class _Key, class _Value, class _KeyOfValue,
1055           class _Compare, class _Alloc>
1056 void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1057   ::_M_erase(_Link_type __x)
1058 {
1059                                 // erase without rebalancing
1060   while (__x != 0) {
1061     _M_erase(_S_right(__x));
1062     _Link_type __y = _S_left(__x);
1063     destroy_node(__x);
1064     __x = __y;
1065   }
1066 }
1067
1068 template <class _Key, class _Value, class _KeyOfValue,
1069           class _Compare, class _Alloc>
1070 void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1071   ::erase(iterator __first, iterator __last)
1072 {
1073   if (__first == begin() && __last == end())
1074     clear();
1075   else
1076     while (__first != __last) erase(__first++);
1077 }
1078
1079 template <class _Key, class _Value, class _KeyOfValue,
1080           class _Compare, class _Alloc>
1081 void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1082   ::erase(const _Key* __first, const _Key* __last)
1083 {
1084   while (__first != __last) erase(*__first++);
1085 }
1086
1087 template <class _Key, class _Value, class _KeyOfValue,
1088           class _Compare, class _Alloc>
1089 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
1090 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
1091 {
1092   _Link_type __y = _M_header;      // Last node which is not less than __k.
1093   _Link_type __x = _M_root();      // Current node.
1094
1095   while (__x != 0)
1096     if (!_M_key_compare(_S_key(__x), __k))
1097       __y = __x, __x = _S_left(__x);
1098     else
1099       __x = _S_right(__x);
1100
1101   iterator __j = iterator(__y);
1102   return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
1103      end() : __j;
1104 }
1105
1106 template <class _Key, class _Value, class _KeyOfValue,
1107           class _Compare, class _Alloc>
1108 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
1109 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) const
1110 {
1111   _Link_type __y = _M_header; /* Last node which is not less than __k. */
1112   _Link_type __x = _M_root(); /* Current node. */
1113
1114   while (__x != 0) {
1115     if (!_M_key_compare(_S_key(__x), __k))
1116       __y = __x, __x = _S_left(__x);
1117     else
1118       __x = _S_right(__x);
1119   }
1120   const_iterator __j = const_iterator(__y);
1121   return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
1122     end() : __j;
1123 }
1124
1125 template <class _Key, class _Value, class _KeyOfValue,
1126           class _Compare, class _Alloc>
1127 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
1128 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1129   ::count(const _Key& __k) const
1130 {
1131   pair<const_iterator, const_iterator> __p = equal_range(__k);
1132   size_type __n = 0;
1133   distance(__p.first, __p.second, __n);
1134   return __n;
1135 }
1136
1137 template <class _Key, class _Value, class _KeyOfValue,
1138           class _Compare, class _Alloc>
1139 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
1140 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1141   ::lower_bound(const _Key& __k)
1142 {
1143   _Link_type __y = _M_header; /* Last node which is not less than __k. */
1144   _Link_type __x = _M_root(); /* Current node. */
1145
1146   while (__x != 0)
1147     if (!_M_key_compare(_S_key(__x), __k))
1148       __y = __x, __x = _S_left(__x);
1149     else
1150       __x = _S_right(__x);
1151
1152   return iterator(__y);
1153 }
1154
1155 template <class _Key, class _Value, class _KeyOfValue,
1156           class _Compare, class _Alloc>
1157 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
1158 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1159   ::lower_bound(const _Key& __k) const
1160 {
1161   _Link_type __y = _M_header; /* Last node which is not less than __k. */
1162   _Link_type __x = _M_root(); /* Current node. */
1163
1164   while (__x != 0)
1165     if (!_M_key_compare(_S_key(__x), __k))
1166       __y = __x, __x = _S_left(__x);
1167     else
1168       __x = _S_right(__x);
1169
1170   return const_iterator(__y);
1171 }
1172
1173 template <class _Key, class _Value, class _KeyOfValue,
1174           class _Compare, class _Alloc>
1175 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
1176 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1177   ::upper_bound(const _Key& __k)
1178 {
1179   _Link_type __y = _M_header; /* Last node which is greater than __k. */
1180   _Link_type __x = _M_root(); /* Current node. */
1181
1182    while (__x != 0)
1183      if (_M_key_compare(__k, _S_key(__x)))
1184        __y = __x, __x = _S_left(__x);
1185      else
1186        __x = _S_right(__x);
1187
1188    return iterator(__y);
1189 }
1190
1191 template <class _Key, class _Value, class _KeyOfValue,
1192           class _Compare, class _Alloc>
1193 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
1194 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1195   ::upper_bound(const _Key& __k) const
1196 {
1197   _Link_type __y = _M_header; /* Last node which is greater than __k. */
1198   _Link_type __x = _M_root(); /* Current node. */
1199
1200    while (__x != 0)
1201      if (_M_key_compare(__k, _S_key(__x)))
1202        __y = __x, __x = _S_left(__x);
1203      else
1204        __x = _S_right(__x);
1205
1206    return const_iterator(__y);
1207 }
1208
1209 template <class _Key, class _Value, class _KeyOfValue,
1210           class _Compare, class _Alloc>
1211 inline
1212 pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
1213      typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator>
1214 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
1215   ::equal_range(const _Key& __k)
1216 {
1217   return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k));
1218 }
1219
1220 template <class _Key, class _Value, class _KoV, class _Compare, class _Alloc>
1221 inline
1222 pair<typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator,
1223      typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator>
1224 _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>
1225   ::equal_range(const _Key& __k) const
1226 {
1227   return pair<const_iterator,const_iterator>(lower_bound(__k),
1228                                              upper_bound(__k));
1229 }
1230
1231 inline int
1232 __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
1233 {
1234   if (__node == 0)
1235     return 0;
1236   int __sum = 0;
1237   do {
1238     if (__node->_M_color == _S_rb_tree_black)
1239       ++__sum;
1240     if (__node == __root)
1241       break;
1242     __node = __node->_M_parent;
1243   } while (1);
1244   return __sum;
1245 }
1246
1247 template <class _Key, class _Value, class _KeyOfValue,
1248           class _Compare, class _Alloc>
1249 bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1250 {
1251   if (_M_node_count == 0 || begin() == end())
1252     return _M_node_count == 0 && begin() == end() &&
1253       _M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
1254
1255   int __len = __black_count(_M_leftmost(), _M_root());
1256   for (const_iterator __it = begin(); __it != end(); ++__it) {
1257     _Link_type __x = (_Link_type) __it._M_node;
1258     _Link_type __L = _S_left(__x);
1259     _Link_type __R = _S_right(__x);
1260
1261     if (__x->_M_color == _S_rb_tree_red)
1262       if ((__L && __L->_M_color == _S_rb_tree_red) ||
1263           (__R && __R->_M_color == _S_rb_tree_red))
1264         return false;
1265
1266     if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
1267       return false;
1268     if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
1269       return false;
1270
1271     if (!__L && !__R && __black_count(__x, _M_root()) != __len)
1272       return false;
1273   }
1274
1275   if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1276     return false;
1277   if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1278     return false;
1279
1280   return true;
1281 }
1282
1283 // Class rb_tree is not part of the C++ standard.  It is provided for
1284 // compatibility with the HP STL.
1285
1286 template <class _Key, class _Value, class _KeyOfValue, class _Compare,
1287           class _Alloc = allocator<_Value> >
1288 struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>
1289 {
1290   typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
1291   typedef typename _Base::allocator_type allocator_type;
1292
1293   rb_tree(const _Compare& __comp = _Compare(),
1294           const allocator_type& __a = allocator_type())
1295     : _Base(__comp, __a) {}
1296
1297   ~rb_tree() {}
1298 };
1299
1300 } // namespace std
1301
1302 #endif /* __SGI_STL_INTERNAL_TREE_H */
1303
1304 // Local Variables:
1305 // mode:C++
1306 // End: