libstdc++/stl/stl_tree.h

   1 /*
   2  *
   3  * Copyright (c) 1996,1997
   4  * Silicon Graphics Computer Systems, Inc.
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Silicon Graphics makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1994
  16  * Hewlett-Packard Company
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Hewlett-Packard Company makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  *
  26  *
  27  */
  28
  29 /* NOTE: This is an internal header file, included by other STL headers.
  30  *   You should not attempt to use it directly.
  31  */
  32
  33 #ifndef __SGI_STL_INTERNAL_TREE_H
  34 #define __SGI_STL_INTERNAL_TREE_H
  35
  36 /*
  37
  38 Red-black tree class, designed for use in implementing STL
  39 associative containers (set, multiset, map, and multimap). The
  40 insertion and deletion algorithms are based on those in Cormen,
  41 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
  42 except that
  43
  44 (1) the header cell is maintained with links not only to the root
  45 but also to the leftmost node of the tree, to enable constant time
  46 begin(), and to the rightmost node of the tree, to enable linear time
  47 performance when used with the generic set algorithms (set_union,
  48 etc.);
  49
  50 (2) when a node being deleted has two children its successor node is
  51 relinked into its place, rather than copied, so that the only
  52 iterators invalidated are those referring to the deleted node.
  53
  54 */
  55
  56 #include <stl_algobase.h>
  57 #include <stl_alloc.h>
  58 #include <stl_construct.h>
  59 #include <stl_function.h>
  60
  61 __STL_BEGIN_NAMESPACE
  62
  63 typedef bool __rb_tree_color_type;
  64 const __rb_tree_color_type __rb_tree_red = false;
  65 const __rb_tree_color_type __rb_tree_black = true;
  66
  67 struct __rb_tree_node_base
  68 {
  69   typedef __rb_tree_color_type color_type;
  70   typedef __rb_tree_node_base* base_ptr;
  71
  72   color_type color;
  73   base_ptr parent;
  74   base_ptr left;
  75   base_ptr right;
  76
  77   static base_ptr minimum(base_ptr x)
  78   {
  79     while (x->left != 0) x = x->left;
  80     return x;
  81   }
  82
  83   static base_ptr maximum(base_ptr x)
  84   {
  85     while (x->right != 0) x = x->right;
  86     return x;
  87   }
  88 };
  89
  90 template <class Value>
  91 struct __rb_tree_node : public __rb_tree_node_base
  92 {
  93   typedef __rb_tree_node<Value>* link_type;
  94   Value value_field;
  95 };
  96
  97
  98 struct __rb_tree_base_iterator
  99 {
 100   typedef __rb_tree_node_base::base_ptr base_ptr;
 101   typedef bidirectional_iterator_tag iterator_category;
 102   typedef ptrdiff_t difference_type;
 103   base_ptr node;
 104
 105   void increment()
 106   {
 107     if (node->right != 0) {
 108       node = node->right;
 109       while (node->left != 0)
 110         node = node->left;
 111     }
 112     else {
 113       base_ptr y = node->parent;
 114       while (node == y->right) {
 115         node = y;
 116         y = y->parent;
 117       }
 118       if (node->right != y)
 119         node = y;
 120     }
 121   }
 122
 123   void decrement()
 124   {
 125     if (node->color == __rb_tree_red &&
 126         node->parent->parent == node)
 127       node = node->right;
 128     else if (node->left != 0) {
 129       base_ptr y = node->left;
 130       while (y->right != 0)
 131         y = y->right;
 132       node = y;
 133     }
 134     else {
 135       base_ptr y = node->parent;
 136       while (node == y->left) {
 137         node = y;
 138         y = y->parent;
 139       }
 140       node = y;
 141     }
 142   }
 143 };
 144
 145 template <class Value, class Ref, class Ptr>
 146 struct __rb_tree_iterator : public __rb_tree_base_iterator
 147 {
 148   typedef Value value_type;
 149   typedef Ref reference;
 150   typedef Ptr pointer;
 151   typedef __rb_tree_iterator<Value, Value&, Value*>             iterator;
 152   typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
 153   typedef __rb_tree_iterator<Value, Ref, Ptr>                   self;
 154   typedef __rb_tree_node<Value>* link_type;
 155
 156   __rb_tree_iterator() {}
 157   __rb_tree_iterator(link_type x) { node = x; }
 158   __rb_tree_iterator(const iterator& it) { node = it.node; }
 159
 160   reference operator*() const { return link_type(node)->value_field; }
 161 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 162   pointer operator->() const { return &(operator*()); }
 163 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 164
 165   self& operator++() { increment(); return *this; }
 166   self operator++(int) {
 167     self tmp = *this;
 168     increment();
 169     return tmp;
 170   }
 171
 172   self& operator--() { decrement(); return *this; }
 173   self operator--(int) {
 174     self tmp = *this;
 175     decrement();
 176     return tmp;
 177   }
 178 };
 179
 180 inline bool operator==(const __rb_tree_base_iterator& x,
 181                        const __rb_tree_base_iterator& y) {
 182   return x.node == y.node;
 183 }
 184
 185 inline bool operator!=(const __rb_tree_base_iterator& x,
 186                        const __rb_tree_base_iterator& y) {
 187   return x.node != y.node;
 188 }
 189
 190 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 191
 192 inline bidirectional_iterator_tag
 193 iterator_category(const __rb_tree_base_iterator&) {
 194   return bidirectional_iterator_tag();
 195 }
 196
 197 inline __rb_tree_base_iterator::difference_type*
 198 distance_type(const __rb_tree_base_iterator&) {
 199   return (__rb_tree_base_iterator::difference_type*) 0;
 200 }
 201
 202 template <class Value, class Ref, class Ptr>
 203 inline Value* value_type(const __rb_tree_iterator<Value, Ref, Ptr>&) {
 204   return (Value*) 0;
 205 }
 206
 207 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 208
 209 inline void
 210 __rb_tree_rotate_left(__rb_tree_node_base* x, __rb_tree_node_base*& root)
 211 {
 212   __rb_tree_node_base* y = x->right;
 213   x->right = y->left;
 214   if (y->left !=0)
 215     y->left->parent = x;
 216   y->parent = x->parent;
 217
 218   if (x == root)
 219     root = y;
 220   else if (x == x->parent->left)
 221     x->parent->left = y;
 222   else
 223     x->parent->right = y;
 224   y->left = x;
 225   x->parent = y;
 226 }
 227
 228 inline void
 229 __rb_tree_rotate_right(__rb_tree_node_base* x, __rb_tree_node_base*& root)
 230 {
 231   __rb_tree_node_base* y = x->left;
 232   x->left = y->right;
 233   if (y->right != 0)
 234     y->right->parent = x;
 235   y->parent = x->parent;
 236
 237   if (x == root)
 238     root = y;
 239   else if (x == x->parent->right)
 240     x->parent->right = y;
 241   else
 242     x->parent->left = y;
 243   y->right = x;
 244   x->parent = y;
 245 }
 246
 247 inline void
 248 __rb_tree_rebalance(__rb_tree_node_base* x, __rb_tree_node_base*& root)
 249 {
 250   x->color = __rb_tree_red;
 251   while (x != root && x->parent->color == __rb_tree_red) {
 252     if (x->parent == x->parent->parent->left) {
 253       __rb_tree_node_base* y = x->parent->parent->right;
 254       if (y && y->color == __rb_tree_red) {
 255         x->parent->color = __rb_tree_black;
 256         y->color = __rb_tree_black;
 257         x->parent->parent->color = __rb_tree_red;
 258         x = x->parent->parent;
 259       }
 260       else {
 261         if (x == x->parent->right) {
 262           x = x->parent;
 263           __rb_tree_rotate_left(x, root);
 264         }
 265         x->parent->color = __rb_tree_black;
 266         x->parent->parent->color = __rb_tree_red;
 267         __rb_tree_rotate_right(x->parent->parent, root);
 268       }
 269     }
 270     else {
 271       __rb_tree_node_base* y = x->parent->parent->left;
 272       if (y && y->color == __rb_tree_red) {
 273         x->parent->color = __rb_tree_black;
 274         y->color = __rb_tree_black;
 275         x->parent->parent->color = __rb_tree_red;
 276         x = x->parent->parent;
 277       }
 278       else {
 279         if (x == x->parent->left) {
 280           x = x->parent;
 281           __rb_tree_rotate_right(x, root);
 282         }
 283         x->parent->color = __rb_tree_black;
 284         x->parent->parent->color = __rb_tree_red;
 285         __rb_tree_rotate_left(x->parent->parent, root);
 286       }
 287     }
 288   }
 289   root->color = __rb_tree_black;
 290 }
 291
 292 inline __rb_tree_node_base*
 293 __rb_tree_rebalance_for_erase(__rb_tree_node_base* z,
 294                               __rb_tree_node_base*& root,
 295                               __rb_tree_node_base*& leftmost,
 296                               __rb_tree_node_base*& rightmost)
 297 {
 298   __rb_tree_node_base* y = z;
 299   __rb_tree_node_base* x = 0;
 300   __rb_tree_node_base* x_parent = 0;
 301   if (y->left == 0)             // z has at most one non-null child. y == z.
 302     x = y->right;               // x might be null.
 303   else
 304     if (y->right == 0)          // z has exactly one non-null child.  y == z.
 305       x = y->left;              // x is not null.
 306     else {                      // z has two non-null children.  Set y to
 307       y = y->right;             //   z's successor.  x might be null.
 308       while (y->left != 0)
 309         y = y->left;
 310       x = y->right;
 311     }
 312   if (y != z) {                 // relink y in place of z.  y is z's successor
 313     z->left->parent = y;
 314     y->left = z->left;
 315     if (y != z->right) {
 316       x_parent = y->parent;
 317       if (x) x->parent = y->parent;
 318       y->parent->left = x;      // y must be a left child
 319       y->right = z->right;
 320       z->right->parent = y;
 321     }
 322     else
 323       x_parent = y;
 324     if (root == z)
 325       root = y;
 326     else if (z->parent->left == z)
 327       z->parent->left = y;
 328     else
 329       z->parent->right = y;
 330     y->parent = z->parent;
 331     __STD::swap(y->color, z->color);
 332     y = z;
 333     // y now points to node to be actually deleted
 334   }
 335   else {                        // y == z
 336     x_parent = y->parent;
 337     if (x) x->parent = y->parent;
 338     if (root == z)
 339       root = x;
 340     else
 341       if (z->parent->left == z)
 342         z->parent->left = x;
 343       else
 344         z->parent->right = x;
 345     if (leftmost == z)
 346       if (z->right == 0)        // z->left must be null also
 347         leftmost = z->parent;
 348     // makes leftmost == header if z == root
 349       else
 350         leftmost = __rb_tree_node_base::minimum(x);
 351     if (rightmost == z)
 352       if (z->left == 0)         // z->right must be null also
 353         rightmost = z->parent;
 354     // makes rightmost == header if z == root
 355       else                      // x == z->left
 356         rightmost = __rb_tree_node_base::maximum(x);
 357   }
 358   if (y->color != __rb_tree_red) {
 359     while (x != root && (x == 0 || x->color == __rb_tree_black))
 360       if (x == x_parent->left) {
 361         __rb_tree_node_base* w = x_parent->right;
 362         if (w->color == __rb_tree_red) {
 363           w->color = __rb_tree_black;
 364           x_parent->color = __rb_tree_red;
 365           __rb_tree_rotate_left(x_parent, root);
 366           w = x_parent->right;
 367         }
 368         if ((w->left == 0 || w->left->color == __rb_tree_black) &&
 369             (w->right == 0 || w->right->color == __rb_tree_black)) {
 370           w->color = __rb_tree_red;
 371           x = x_parent;
 372           x_parent = x_parent->parent;
 373         } else {
 374           if (w->right == 0 || w->right->color == __rb_tree_black) {
 375             if (w->left) w->left->color = __rb_tree_black;
 376             w->color = __rb_tree_red;
 377             __rb_tree_rotate_right(w, root);
 378             w = x_parent->right;
 379           }
 380           w->color = x_parent->color;
 381           x_parent->color = __rb_tree_black;
 382           if (w->right) w->right->color = __rb_tree_black;
 383           __rb_tree_rotate_left(x_parent, root);
 384           break;
 385         }
 386       } else {                  // same as above, with right <-> left.
 387         __rb_tree_node_base* w = x_parent->left;
 388         if (w->color == __rb_tree_red) {
 389           w->color = __rb_tree_black;
 390           x_parent->color = __rb_tree_red;
 391           __rb_tree_rotate_right(x_parent, root);
 392           w = x_parent->left;
 393         }
 394         if ((w->right == 0 || w->right->color == __rb_tree_black) &&
 395             (w->left == 0 || w->left->color == __rb_tree_black)) {
 396           w->color = __rb_tree_red;
 397           x = x_parent;
 398           x_parent = x_parent->parent;
 399         } else {
 400           if (w->left == 0 || w->left->color == __rb_tree_black) {
 401             if (w->right) w->right->color = __rb_tree_black;
 402             w->color = __rb_tree_red;
 403             __rb_tree_rotate_left(w, root);
 404             w = x_parent->left;
 405           }
 406           w->color = x_parent->color;
 407           x_parent->color = __rb_tree_black;
 408           if (w->left) w->left->color = __rb_tree_black;
 409           __rb_tree_rotate_right(x_parent, root);
 410           break;
 411         }
 412       }
 413     if (x) x->color = __rb_tree_black;
 414   }
 415   return y;
 416 }
 417
 418 template <class Key, class Value, class KeyOfValue, class Compare,
 419           class Alloc = alloc>
 420 class rb_tree {
 421 protected:
 422   typedef void* void_pointer;
 423   typedef __rb_tree_node_base* base_ptr;
 424   typedef __rb_tree_node<Value> rb_tree_node;
 425   typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
 426   typedef __rb_tree_color_type color_type;
 427 public:
 428   typedef Key key_type;
 429   typedef Value value_type;
 430   typedef value_type* pointer;
 431   typedef const value_type* const_pointer;
 432   typedef value_type& reference;
 433   typedef const value_type& const_reference;
 434   typedef rb_tree_node* link_type;
 435   typedef size_t size_type;
 436   typedef ptrdiff_t difference_type;
 437 protected:
 438   link_type get_node() { return rb_tree_node_allocator::allocate(); }
 439   void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); }
 440
 441   link_type create_node(const value_type& x) {
 442     link_type tmp = get_node();
 443     __STL_TRY {
 444       construct(&tmp->value_field, x);
 445     }
 446     __STL_UNWIND(put_node(tmp));
 447     return tmp;
 448   }
 449
 450   link_type clone_node(link_type x) {
 451     link_type tmp = create_node(x->value_field);
 452     tmp->color = x->color;
 453     tmp->left = 0;
 454     tmp->right = 0;
 455     return tmp;
 456   }
 457
 458   void destroy_node(link_type p) {
 459     destroy(&p->value_field);
 460     put_node(p);
 461   }
 462
 463 protected:
 464   size_type node_count; // keeps track of size of tree
 465   link_type header;
 466   Compare key_compare;
 467
 468   link_type& root() const { return (link_type&) header->parent; }
 469   link_type& leftmost() const { return (link_type&) header->left; }
 470   link_type& rightmost() const { return (link_type&) header->right; }
 471
 472   static link_type& left(link_type x) { return (link_type&)(x->left); }
 473   static link_type& right(link_type x) { return (link_type&)(x->right); }
 474   static link_type& parent(link_type x) { return (link_type&)(x->parent); }
 475   static reference value(link_type x) { return x->value_field; }
 476   static const Key& key(link_type x) { return KeyOfValue()(value(x)); }
 477   static color_type& color(link_type x) { return (color_type&)(x->color); }
 478
 479   static link_type& left(base_ptr x) { return (link_type&)(x->left); }
 480   static link_type& right(base_ptr x) { return (link_type&)(x->right); }
 481   static link_type& parent(base_ptr x) { return (link_type&)(x->parent); }
 482   static reference value(base_ptr x) { return ((link_type)x)->value_field; }
 483   static const Key& key(base_ptr x) { return KeyOfValue()(value(link_type(x)));}
 484   static color_type& color(base_ptr x) { return (color_type&)(link_type(x)->color); }
 485
 486   static link_type minimum(link_type x) {
 487     return (link_type)  __rb_tree_node_base::minimum(x);
 488   }
 489   static link_type maximum(link_type x) {
 490     return (link_type) __rb_tree_node_base::maximum(x);
 491   }
 492
 493 public:
 494   typedef __rb_tree_iterator<value_type, reference, pointer> iterator;
 495   typedef __rb_tree_iterator<value_type, const_reference, const_pointer>
 496           const_iterator;
 497
 498 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 499   typedef reverse_iterator<const_iterator> const_reverse_iterator;
 500   typedef reverse_iterator<iterator> reverse_iterator;
 501 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 502   typedef reverse_bidirectional_iterator<iterator, value_type, reference,
 503                                          difference_type>
 504           reverse_iterator;
 505   typedef reverse_bidirectional_iterator<const_iterator, value_type,
 506                                          const_reference, difference_type>
 507           const_reverse_iterator;
 508 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 509 private:
 510   iterator __insert(base_ptr x, base_ptr y, const value_type& v);
 511   link_type __copy(link_type x, link_type p);
 512   void __erase(link_type x);
 513   void init() {
 514     header = get_node();
 515     color(header) = __rb_tree_red; // used to distinguish header from
 516                                    // root, in iterator.operator++
 517     root() = 0;
 518     leftmost() = header;
 519     rightmost() = header;
 520   }
 521 public:
 522                                 // allocation/deallocation
 523   rb_tree(const Compare& comp = Compare())
 524     : node_count(0), key_compare(comp) { init(); }
 525
 526   rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x)
 527     : node_count(0), key_compare(x.key_compare)
 528   {
 529     header = get_node();
 530     color(header) = __rb_tree_red;
 531     if (x.root() == 0) {
 532       root() = 0;
 533       leftmost() = header;
 534       rightmost() = header;
 535     }
 536     else {
 537       __STL_TRY {
 538         root() = __copy(x.root(), header);
 539       }
 540       __STL_UNWIND(put_node(header));
 541       leftmost() = minimum(root());
 542       rightmost() = maximum(root());
 543     }
 544     node_count = x.node_count;
 545   }
 546   ~rb_tree() {
 547     clear();
 548     put_node(header);
 549   }
 550   rb_tree<Key, Value, KeyOfValue, Compare, Alloc>&
 551   operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x);
 552
 553 public:
 554                                 // accessors:
 555   Compare key_comp() const { return key_compare; }
 556   iterator begin() { return leftmost(); }
 557   const_iterator begin() const { return leftmost(); }
 558   iterator end() { return header; }
 559   const_iterator end() const { return header; }
 560   reverse_iterator rbegin() { return reverse_iterator(end()); }
 561   const_reverse_iterator rbegin() const {
 562     return const_reverse_iterator(end());
 563   }
 564   reverse_iterator rend() { return reverse_iterator(begin()); }
 565   const_reverse_iterator rend() const {
 566     return const_reverse_iterator(begin());
 567   }
 568   bool empty() const { return node_count == 0; }
 569   size_type size() const { return node_count; }
 570   size_type max_size() const { return size_type(-1); }
 571
 572   void swap(rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& t) {
 573     __STD::swap(header, t.header);
 574     __STD::swap(node_count, t.node_count);
 575     __STD::swap(key_compare, t.key_compare);
 576   }
 577
 578 public:
 579                                 // insert/erase
 580   pair<iterator,bool> insert_unique(const value_type& x);
 581   iterator insert_equal(const value_type& x);
 582
 583   iterator insert_unique(iterator position, const value_type& x);
 584   iterator insert_equal(iterator position, const value_type& x);
 585
 586 #ifdef __STL_MEMBER_TEMPLATES
 587   template <class InputIterator>
 588   void insert_unique(InputIterator first, InputIterator last);
 589   template <class InputIterator>
 590   void insert_equal(InputIterator first, InputIterator last);
 591 #else /* __STL_MEMBER_TEMPLATES */
 592   void insert_unique(const_iterator first, const_iterator last);
 593   void insert_unique(const value_type* first, const value_type* last);
 594   void insert_equal(const_iterator first, const_iterator last);
 595   void insert_equal(const value_type* first, const value_type* last);
 596 #endif /* __STL_MEMBER_TEMPLATES */
 597
 598   void erase(iterator position);
 599   size_type erase(const key_type& x);
 600   void erase(iterator first, iterator last);
 601   void erase(const key_type* first, const key_type* last);
 602   void clear() {
 603     if (node_count != 0) {
 604       __erase(root());
 605       leftmost() = header;
 606       root() = 0;
 607       rightmost() = header;
 608       node_count = 0;
 609     }
 610   }
 611
 612 public:
 613                                 // set operations:
 614   iterator find(const key_type& x);
 615   const_iterator find(const key_type& x) const;
 616   size_type count(const key_type& x) const;
 617   iterator lower_bound(const key_type& x);
 618   const_iterator lower_bound(const key_type& x) const;
 619   iterator upper_bound(const key_type& x);
 620   const_iterator upper_bound(const key_type& x) const;
 621   pair<iterator,iterator> equal_range(const key_type& x);
 622   pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
 623
 624 public:
 625                                 // Debugging.
 626   bool __rb_verify() const;
 627 };
 628
 629 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 630 inline bool operator==(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x,
 631                        const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
 632   return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
 633 }
 634
 635 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 636 inline bool operator<(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x,
 637                       const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
 638   return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
 639 }
 640
 641 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 642
 643 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 644 inline void swap(rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x,
 645                  rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
 646   x.swap(y);
 647 }
 648
 649 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 650
 651
 652 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 653 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>&
 654 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::
 655 operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) {
 656   if (this != &x) {
 657                                 // Note that Key may be a constant type.
 658     clear();
 659     node_count = 0;
 660     key_compare = x.key_compare;
 661     if (x.root() == 0) {
 662       root() = 0;
 663       leftmost() = header;
 664       rightmost() = header;
 665     }
 666     else {
 667       root() = __copy(x.root(), header);
 668       leftmost() = minimum(root());
 669       rightmost() = maximum(root());
 670       node_count = x.node_count;
 671     }
 672   }
 673   return *this;
 674 }
 675
 676 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 677 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
 678 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::
 679 __insert(base_ptr x_, base_ptr y_, const Value& v) {
 680   link_type x = (link_type) x_;
 681   link_type y = (link_type) y_;
 682   link_type z;
 683
 684   if (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y))) {
 685     z = create_node(v);
 686     left(y) = z;                // also makes leftmost() = z when y == header
 687     if (y == header) {
 688       root() = z;
 689       rightmost() = z;
 690     }
 691     else if (y == leftmost())
 692       leftmost() = z;           // maintain leftmost() pointing to min node
 693   }
 694   else {
 695     z = create_node(v);
 696     right(y) = z;
 697     if (y == rightmost())
 698       rightmost() = z;          // maintain rightmost() pointing to max node
 699   }
 700   parent(z) = y;
 701   left(z) = 0;
 702   right(z) = 0;
 703   __rb_tree_rebalance(z, header->parent);
 704   ++node_count;
 705   return iterator(z);
 706 }
 707
 708 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 709 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
 710 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const Value& v)
 711 {
 712   link_type y = header;
 713   link_type x = root();
 714   while (x != 0) {
 715     y = x;
 716     x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);
 717   }
 718   return __insert(x, y, v);
 719 }
 720
 721
 722 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 723 pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>
 724 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v)
 725 {
 726   link_type y = header;
 727   link_type x = root();
 728   bool comp = true;
 729   while (x != 0) {
 730     y = x;
 731     comp = key_compare(KeyOfValue()(v), key(x));
 732     x = comp ? left(x) : right(x);
 733   }
 734   iterator j = iterator(y);
 735   if (comp)
 736     if (j == begin())
 737       return pair<iterator,bool>(__insert(x, y, v), true);
 738     else
 739       --j;
 740   if (key_compare(key(j.node), KeyOfValue()(v)))
 741     return pair<iterator,bool>(__insert(x, y, v), true);
 742   return pair<iterator,bool>(j, false);
 743 }
 744
 745
 746 template <class Key, class Val, class KeyOfValue, class Compare, class Alloc>
 747 typename rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::iterator
 748 rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::insert_unique(iterator position,
 749                                                              const Val& v) {
 750   if (position.node == header->left) // begin()
 751     if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
 752       return __insert(position.node, position.node, v);
 753   // first argument just needs to be non-null
 754     else
 755       return insert_unique(v).first;
 756   else if (position.node == header) // end()
 757     if (key_compare(key(rightmost()), KeyOfValue()(v)))
 758       return __insert(0, rightmost(), v);
 759     else
 760       return insert_unique(v).first;
 761   else {
 762     iterator before = position;
 763     --before;
 764     if (key_compare(key(before.node), KeyOfValue()(v))
 765         && key_compare(KeyOfValue()(v), key(position.node)))
 766       if (right(before.node) == 0)
 767         return __insert(0, before.node, v);
 768       else
 769         return __insert(position.node, position.node, v);
 770     // first argument just needs to be non-null
 771     else
 772       return insert_unique(v).first;
 773   }
 774 }
 775
 776 template <class Key, class Val, class KeyOfValue, class Compare, class Alloc>
 777 typename rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::iterator
 778 rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::insert_equal(iterator position,
 779                                                             const Val& v) {
 780   if (position.node == header->left) // begin()
 781     if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
 782       return __insert(position.node, position.node, v);
 783   // first argument just needs to be non-null
 784     else
 785       return insert_equal(v);
 786   else if (position.node == header) // end()
 787     if (!key_compare(KeyOfValue()(v), key(rightmost())))
 788       return __insert(0, rightmost(), v);
 789     else
 790       return insert_equal(v);
 791   else {
 792     iterator before = position;
 793     --before;
 794     if (!key_compare(KeyOfValue()(v), key(before.node))
 795         && !key_compare(key(position.node), KeyOfValue()(v)))
 796       if (right(before.node) == 0)
 797         return __insert(0, before.node, v);
 798       else
 799         return __insert(position.node, position.node, v);
 800     // first argument just needs to be non-null
 801     else
 802       return insert_equal(v);
 803   }
 804 }
 805
 806 #ifdef __STL_MEMBER_TEMPLATES
 807
 808 template <class K, class V, class KoV, class Cmp, class Al> template<class II>
 809 void rb_tree<K, V, KoV, Cmp, Al>::insert_equal(II first, II last) {
 810   for ( ; first != last; ++first)
 811     insert_equal(*first);
 812 }
 813
 814 template <class K, class V, class KoV, class Cmp, class Al> template<class II>
 815 void rb_tree<K, V, KoV, Cmp, Al>::insert_unique(II first, II last) {
 816   for ( ; first != last; ++first)
 817     insert_unique(*first);
 818 }
 819
 820 #else /* __STL_MEMBER_TEMPLATES */
 821
 822 template <class K, class V, class KoV, class Cmp, class Al>
 823 void
 824 rb_tree<K, V, KoV, Cmp, Al>::insert_equal(const V* first, const V* last) {
 825   for ( ; first != last; ++first)
 826     insert_equal(*first);
 827 }
 828
 829 template <class K, class V, class KoV, class Cmp, class Al>
 830 void
 831 rb_tree<K, V, KoV, Cmp, Al>::insert_equal(const_iterator first,
 832                                           const_iterator last) {
 833   for ( ; first != last; ++first)
 834     insert_equal(*first);
 835 }
 836
 837 template <class K, class V, class KoV, class Cmp, class A>
 838 void
 839 rb_tree<K, V, KoV, Cmp, A>::insert_unique(const V* first, const V* last) {
 840   for ( ; first != last; ++first)
 841     insert_unique(*first);
 842 }
 843
 844 template <class K, class V, class KoV, class Cmp, class A>
 845 void
 846 rb_tree<K, V, KoV, Cmp, A>::insert_unique(const_iterator first,
 847                                           const_iterator last) {
 848   for ( ; first != last; ++first)
 849     insert_unique(*first);
 850 }
 851
 852 #endif /* __STL_MEMBER_TEMPLATES */
 853
 854 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 855 inline void
 856 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(iterator position) {
 857   link_type y = (link_type) __rb_tree_rebalance_for_erase(position.node,
 858                                                           header->parent,
 859                                                           header->left,
 860                                                           header->right);
 861   destroy_node(y);
 862   --node_count;
 863 }
 864
 865 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 866 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::size_type
 867 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const Key& x) {
 868   pair<iterator,iterator> p = equal_range(x);
 869   size_type n = 0;
 870   distance(p.first, p.second, n);
 871   erase(p.first, p.second);
 872   return n;
 873 }
 874
 875 template <class K, class V, class KeyOfValue, class Compare, class Alloc>
 876 typename rb_tree<K, V, KeyOfValue, Compare, Alloc>::link_type
 877 rb_tree<K, V, KeyOfValue, Compare, Alloc>::__copy(link_type x, link_type p) {
 878                                 // structural copy.  x and p must be non-null.
 879   link_type top = clone_node(x);
 880   top->parent = p;
 881
 882   __STL_TRY {
 883     if (x->right)
 884       top->right = __copy(right(x), top);
 885     p = top;
 886     x = left(x);
 887
 888     while (x != 0) {
 889       link_type y = clone_node(x);
 890       p->left = y;
 891       y->parent = p;
 892       if (x->right)
 893         y->right = __copy(right(x), y);
 894       p = y;
 895       x = left(x);
 896     }
 897   }
 898   __STL_UNWIND(__erase(top));
 899
 900   return top;
 901 }
 902
 903 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 904 void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__erase(link_type x) {
 905                                 // erase without rebalancing
 906   while (x != 0) {
 907     __erase(right(x));
 908     link_type y = left(x);
 909     destroy_node(x);
 910     x = y;
 911   }
 912 }
 913
 914 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 915 void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(iterator first,
 916                                                             iterator last) {
 917   if (first == begin() && last == end())
 918     clear();
 919   else
 920     while (first != last) erase(first++);
 921 }
 922
 923 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 924 void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const Key* first,
 925                                                             const Key* last) {
 926   while (first != last) erase(*first++);
 927 }
 928
 929 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 930 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
 931 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key& k) {
 932   link_type y = header;        // Last node which is not less than k.
 933   link_type x = root();        // Current node.
 934
 935   while (x != 0)
 936     if (!key_compare(key(x), k))
 937       y = x, x = left(x);
 938     else
 939       x = right(x);
 940
 941   iterator j = iterator(y);
 942   return (j == end() || key_compare(k, key(j.node))) ? end() : j;
 943 }
 944
 945 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 946 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator
 947 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key& k) const {
 948   link_type y = header; /* Last node which is not less than k. */
 949   link_type x = root(); /* Current node. */
 950
 951   while (x != 0) {
 952     if (!key_compare(key(x), k))
 953       y = x, x = left(x);
 954     else
 955       x = right(x);
 956   }
 957   const_iterator j = const_iterator(y);
 958   return (j == end() || key_compare(k, key(j.node))) ? end() : j;
 959 }
 960
 961 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 962 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::size_type
 963 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::count(const Key& k) const {
 964   pair<const_iterator, const_iterator> p = equal_range(k);
 965   size_type n = 0;
 966   distance(p.first, p.second, n);
 967   return n;
 968 }
 969
 970 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 971 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
 972 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const Key& k) {
 973   link_type y = header; /* Last node which is not less than k. */
 974   link_type x = root(); /* Current node. */
 975
 976   while (x != 0)
 977     if (!key_compare(key(x), k))
 978       y = x, x = left(x);
 979     else
 980       x = right(x);
 981
 982   return iterator(y);
 983 }
 984
 985 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
 986 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator
 987 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const Key& k) const {
 988   link_type y = header; /* Last node which is not less than k. */
 989   link_type x = root(); /* Current node. */
 990
 991   while (x != 0)
 992     if (!key_compare(key(x), k))
 993       y = x, x = left(x);
 994     else
 995       x = right(x);
 996
 997   return const_iterator(y);
 998 }
 999
1000 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
1001 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
1002 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const Key& k) {
1003   link_type y = header; /* Last node which is greater than k. */
1004   link_type x = root(); /* Current node. */
1005
1006    while (x != 0)
1007      if (key_compare(k, key(x)))
1008        y = x, x = left(x);
1009      else
1010        x = right(x);
1011
1012    return iterator(y);
1013 }
1014
1015 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
1016 typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator
1017 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const Key& k) const {
1018   link_type y = header; /* Last node which is greater than k. */
1019   link_type x = root(); /* Current node. */
1020
1021    while (x != 0)
1022      if (key_compare(k, key(x)))
1023        y = x, x = left(x);
1024      else
1025        x = right(x);
1026
1027    return const_iterator(y);
1028 }
1029
1030 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
1031 inline pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator,
1032             typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator>
1033 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::equal_range(const Key& k) {
1034   return pair<iterator, iterator>(lower_bound(k), upper_bound(k));
1035 }
1036
1037 template <class Key, class Value, class KoV, class Compare, class Alloc>
1038 inline pair<typename rb_tree<Key, Value, KoV, Compare, Alloc>::const_iterator,
1039             typename rb_tree<Key, Value, KoV, Compare, Alloc>::const_iterator>
1040 rb_tree<Key, Value, KoV, Compare, Alloc>::equal_range(const Key& k) const {
1041   return pair<const_iterator,const_iterator>(lower_bound(k), upper_bound(k));
1042 }
1043
1044 inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
1045 {
1046   if (node == 0)
1047     return 0;
1048   else {
1049     int bc = node->color == __rb_tree_black ? 1 : 0;
1050     if (node == root)
1051       return bc;
1052     else
1053       return bc + __black_count(node->parent, root);
1054   }
1055 }
1056
1057 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
1058 bool
1059 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__rb_verify() const
1060 {
1061   if (node_count == 0 || begin() == end())
1062     return node_count == 0 && begin() == end() &&
1063       header->left == header && header->right == header;
1064
1065   int len = __black_count(leftmost(), root());
1066   for (const_iterator it = begin(); it != end(); ++it) {
1067     link_type x = (link_type) it.node;
1068     link_type L = left(x);
1069     link_type R = right(x);
1070
1071     if (x->color == __rb_tree_red)
1072       if ((L && L->color == __rb_tree_red) ||
1073           (R && R->color == __rb_tree_red))
1074         return false;
1075
1076     if (L && key_compare(key(x), key(L)))
1077       return false;
1078     if (R && key_compare(key(R), key(x)))
1079       return false;
1080
1081     if (!L && !R && __black_count(x, root()) != len)
1082       return false;
1083   }
1084
1085   if (leftmost() != __rb_tree_node_base::minimum(root()))
1086     return false;
1087   if (rightmost() != __rb_tree_node_base::maximum(root()))
1088     return false;
1089
1090   return true;
1091 }
1092
1093 __STL_END_NAMESPACE
1094
1095 #endif /* __SGI_STL_INTERNAL_TREE_H */
1096
1097 // Local Variables:
1098 // mode:C++
1099 // End: