home *** CD-ROM | disk | FTP | other *** search
/ PC World 2000 January / PCWorld_2000-01_cd.bin / Software / Servis / Devc / _SETUP.4 / Group3 / stl_tree.h < prev    next >
C/C++ Source or Header  |  1998-03-08  |  35KB  |  1,100 lines
  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:
  1100.