Makefile.in (install): Some of HEADERS come from the stl dir now.

	* Makefile.in (install): Some of HEADERS come from the stl dir now.
	* algorithm, deque, functional, iterator, list, map, memory, numeric,
 	queue, set, stack, utility, vector: Now in stl dir.

stl/:
	* algo.h, algobase.h, alloc.h, bvector.h, defalloc.h, deque.h,
 	function.h, hash_map.h, hash_set.h, hashtable.h, heap.h, iterator.h,
 	list.h, map.h, multimap.h, multiset.h, pair.h, pthread_alloc.h,
 	rope.h, ropeimpl.h, set.h, slist.h, stack.h, stl_config.h, tempbuf.h,
 	tree.h, type_traits.h, vector.h: Update to October 27 SGI snapshot.
	* algorithm, deque, functional, hash_map, hash_set, iterator, list,
 	map, memory, numeric, pthread_alloc, queue, rope, set, slist, stack,
 	stl_algo.h, stl_algobase.h, stl_alloc.h, stl_bvector.h,
 	stl_construct.h, stl_deque.h, stl_function.h, stl_hash_fun.h,
 	stl_hash_map.h, stl_hash_set.h, stl_hashtable.h, stl_heap.h,
 	stl_iterator.h, stl_list.h, stl_map.h, stl_multimap.h, stl_multiset.h,
 	stl_numeric.h, stl_pair.h, stl_queue.h, stl_raw_storage_iter.h,
 	stl_relops.h, stl_rope.h, stl_set.h, stl_slist.h, stl_stack.h,
 	stl_tempbuf.h, stl_tree.h, stl_uninitialized.h, stl_vector.h,
 	utility, vector: New files in October 27 SGI snapshot.

From-SVN: r16277

1 files changed, 1099 insertions, 0 deletions

diff --git a/libstdc++/stl/stl_tree.h b/libstdc++/stl/stl_tree.h
new file mode 100644
index 0000000..55a6c0e
--- /dev/null
+++ b/libstdc++/stl/stl_tree.h
@@ -0,0 +1,1099 @@
+/*
+ *
+ * Copyright (c) 1996,1997
+ * Silicon Graphics Computer Systems, Inc.
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation.  Silicon Graphics makes no
+ * representations about the suitability of this software for any
+ * purpose.  It is provided "as is" without express or implied warranty.
+ *
+ *
+ * Copyright (c) 1994
+ * Hewlett-Packard Company
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation.  Hewlett-Packard Company makes no
+ * representations about the suitability of this software for any
+ * purpose.  It is provided "as is" without express or implied warranty.
+ *
+ *
+ */
+
+/* NOTE: This is an internal header file, included by other STL headers.
+ *   You should not attempt to use it directly.
+ */
+
+#ifndef __SGI_STL_INTERNAL_TREE_H
+#define __SGI_STL_INTERNAL_TREE_H
+
+/*
+
+Red-black tree class, designed for use in implementing STL
+associative containers (set, multiset, map, and multimap). The
+insertion and deletion algorithms are based on those in Cormen,
+Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
+except that
+
+(1) the header cell is maintained with links not only to the root
+but also to the leftmost node of the tree, to enable constant time
+begin(), and to the rightmost node of the tree, to enable linear time
+performance when used with the generic set algorithms (set_union,
+etc.);
+
+(2) when a node being deleted has two children its successor node is
+relinked into its place, rather than copied, so that the only
+iterators invalidated are those referring to the deleted node.
+
+*/
+
+#include <stl_algobase.h>
+#include <stl_alloc.h>
+#include <stl_construct.h>
+#include <stl_function.h>
+
+__STL_BEGIN_NAMESPACE 
+
+typedef bool __rb_tree_color_type;
+const __rb_tree_color_type __rb_tree_red = false;
+const __rb_tree_color_type __rb_tree_black = true;
+
+struct __rb_tree_node_base
+{
+  typedef __rb_tree_color_type color_type;
+  typedef __rb_tree_node_base* base_ptr;
+
+  color_type color; 
+  base_ptr parent;
+  base_ptr left;
+  base_ptr right;
+
+  static base_ptr minimum(base_ptr x)
+  {
+    while (x->left != 0) x = x->left;
+    return x;
+  }
+
+  static base_ptr maximum(base_ptr x)
+  {
+    while (x->right != 0) x = x->right;
+    return x;
+  }
+};
+
+template <class Value>
+struct __rb_tree_node : public __rb_tree_node_base
+{
+  typedef __rb_tree_node<Value>* link_type;
+  Value value_field;
+};
+
+
+struct __rb_tree_base_iterator
+{
+  typedef __rb_tree_node_base::base_ptr base_ptr;
+  typedef bidirectional_iterator_tag iterator_category;
+  typedef ptrdiff_t difference_type;
+  base_ptr node;
+
+  void increment()
+  {
+    if (node->right != 0) {
+      node = node->right;
+      while (node->left != 0)
+        node = node->left;
+    }
+    else {
+      base_ptr y = node->parent;
+      while (node == y->right) {
+        node = y;
+        y = y->parent;
+      }
+      if (node->right != y)
+        node = y;
+    }
+  }
+
+  void decrement()
+  {
+    if (node->color == __rb_tree_red &&
+        node->parent->parent == node)
+      node = node->right;
+    else if (node->left != 0) {
+      base_ptr y = node->left;
+      while (y->right != 0)
+        y = y->right;
+      node = y;
+    }
+    else {
+      base_ptr y = node->parent;
+      while (node == y->left) {
+        node = y;
+        y = y->parent;
+      }
+      node = y;
+    }
+  }
+};
+
+template <class Value, class Ref, class Ptr>
+struct __rb_tree_iterator : public __rb_tree_base_iterator
+{
+  typedef Value value_type;
+  typedef Ref reference;
+  typedef Ptr pointer;
+  typedef __rb_tree_iterator<Value, Value&, Value*>             iterator;
+  typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
+  typedef __rb_tree_iterator<Value, Ref, Ptr>                   self;
+  typedef __rb_tree_node<Value>* link_type;
+
+  __rb_tree_iterator() {}
+  __rb_tree_iterator(link_type x) { node = x; }
+  __rb_tree_iterator(const iterator& it) { node = it.node; }
+
+  reference operator*() const { return link_type(node)->value_field; }
+#ifndef __SGI_STL_NO_ARROW_OPERATOR
+  pointer operator->() const { return &(operator*()); }
+#endif /* __SGI_STL_NO_ARROW_OPERATOR */
+
+  self& operator++() { increment(); return *this; }
+  self operator++(int) {
+    self tmp = *this;
+    increment();
+    return tmp;
+  }
+    
+  self& operator--() { decrement(); return *this; }
+  self operator--(int) {
+    self tmp = *this;
+    decrement();
+    return tmp;
+  }
+};
+
+inline bool operator==(const __rb_tree_base_iterator& x,
+                       const __rb_tree_base_iterator& y) {
+  return x.node == y.node;
+}
+
+inline bool operator!=(const __rb_tree_base_iterator& x,
+                       const __rb_tree_base_iterator& y) {
+  return x.node != y.node;
+}
+
+#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
+
+inline bidirectional_iterator_tag
+iterator_category(const __rb_tree_base_iterator&) {
+  return bidirectional_iterator_tag();
+}
+
+inline __rb_tree_base_iterator::difference_type*
+distance_type(const __rb_tree_base_iterator&) {
+  return (__rb_tree_base_iterator::difference_type*) 0;
+}
+
+template <class Value, class Ref, class Ptr>
+inline Value* value_type(const __rb_tree_iterator<Value, Ref, Ptr>&) {
+  return (Value*) 0;
+}
+
+#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
+
+inline void 
+__rb_tree_rotate_left(__rb_tree_node_base* x, __rb_tree_node_base*& root)
+{
+  __rb_tree_node_base* y = x->right;
+  x->right = y->left;
+  if (y->left !=0)
+    y->left->parent = x;
+  y->parent = x->parent;
+
+  if (x == root)
+    root = y;
+  else if (x == x->parent->left)
+    x->parent->left = y;
+  else
+    x->parent->right = y;
+  y->left = x;
+  x->parent = y;
+}
+
+inline void 
+__rb_tree_rotate_right(__rb_tree_node_base* x, __rb_tree_node_base*& root)
+{
+  __rb_tree_node_base* y = x->left;
+  x->left = y->right;
+  if (y->right != 0)
+    y->right->parent = x;
+  y->parent = x->parent;
+
+  if (x == root)
+    root = y;
+  else if (x == x->parent->right)
+    x->parent->right = y;
+  else
+    x->parent->left = y;
+  y->right = x;
+  x->parent = y;
+}
+
+inline void 
+__rb_tree_rebalance(__rb_tree_node_base* x, __rb_tree_node_base*& root)
+{
+  x->color = __rb_tree_red;
+  while (x != root && x->parent->color == __rb_tree_red) {
+    if (x->parent == x->parent->parent->left) {
+      __rb_tree_node_base* y = x->parent->parent->right;
+      if (y && y->color == __rb_tree_red) {
+        x->parent->color = __rb_tree_black;
+        y->color = __rb_tree_black;
+        x->parent->parent->color = __rb_tree_red;
+        x = x->parent->parent;
+      }
+      else {
+        if (x == x->parent->right) {
+          x = x->parent;
+          __rb_tree_rotate_left(x, root);
+        }
+        x->parent->color = __rb_tree_black;
+        x->parent->parent->color = __rb_tree_red;
+        __rb_tree_rotate_right(x->parent->parent, root);
+      }
+    }
+    else {
+      __rb_tree_node_base* y = x->parent->parent->left;
+      if (y && y->color == __rb_tree_red) {
+        x->parent->color = __rb_tree_black;
+        y->color = __rb_tree_black;
+        x->parent->parent->color = __rb_tree_red;
+        x = x->parent->parent;
+      }
+      else {
+        if (x == x->parent->left) {
+          x = x->parent;
+          __rb_tree_rotate_right(x, root);
+        }
+        x->parent->color = __rb_tree_black;
+        x->parent->parent->color = __rb_tree_red;
+        __rb_tree_rotate_left(x->parent->parent, root);
+      }
+    }
+  }
+  root->color = __rb_tree_black;
+}
+
+inline __rb_tree_node_base*
+__rb_tree_rebalance_for_erase(__rb_tree_node_base* z,
+                              __rb_tree_node_base*& root,
+                              __rb_tree_node_base*& leftmost,
+                              __rb_tree_node_base*& rightmost)
+{
+  __rb_tree_node_base* y = z;
+  __rb_tree_node_base* x = 0;
+  __rb_tree_node_base* x_parent = 0;
+  if (y->left == 0)             // z has at most one non-null child. y == z.
+    x = y->right;               // x might be null.
+  else
+    if (y->right == 0)          // z has exactly one non-null child.  y == z.
+      x = y->left;              // x is not null.
+    else {                      // z has two non-null children.  Set y to
+      y = y->right;             //   z's successor.  x might be null.
+      while (y->left != 0)
+        y = y->left;
+      x = y->right;
+    }
+  if (y != z) {                 // relink y in place of z.  y is z's successor
+    z->left->parent = y; 
+    y->left = z->left;
+    if (y != z->right) {
+      x_parent = y->parent;
+      if (x) x->parent = y->parent;
+      y->parent->left = x;      // y must be a left child
+      y->right = z->right;
+      z->right->parent = y;
+    }
+    else
+      x_parent = y;  
+    if (root == z)
+      root = y;
+    else if (z->parent->left == z)
+      z->parent->left = y;
+    else 
+      z->parent->right = y;
+    y->parent = z->parent;
+    __STD::swap(y->color, z->color);
+    y = z;
+    // y now points to node to be actually deleted
+  }
+  else {                        // y == z
+    x_parent = y->parent;
+    if (x) x->parent = y->parent;   
+    if (root == z)
+      root = x;
+    else 
+      if (z->parent->left == z)
+        z->parent->left = x;
+      else
+        z->parent->right = x;
+    if (leftmost == z) 
+      if (z->right == 0)        // z->left must be null also
+        leftmost = z->parent;
+    // makes leftmost == header if z == root
+      else
+        leftmost = __rb_tree_node_base::minimum(x);
+    if (rightmost == z)  
+      if (z->left == 0)         // z->right must be null also
+        rightmost = z->parent;  
+    // makes rightmost == header if z == root
+      else                      // x == z->left
+        rightmost = __rb_tree_node_base::maximum(x);
+  }
+  if (y->color != __rb_tree_red) { 
+    while (x != root && (x == 0 || x->color == __rb_tree_black))
+      if (x == x_parent->left) {
+        __rb_tree_node_base* w = x_parent->right;
+        if (w->color == __rb_tree_red) {
+          w->color = __rb_tree_black;
+          x_parent->color = __rb_tree_red;
+          __rb_tree_rotate_left(x_parent, root);
+          w = x_parent->right;
+        }
+        if ((w->left == 0 || w->left->color == __rb_tree_black) &&
+            (w->right == 0 || w->right->color == __rb_tree_black)) {
+          w->color = __rb_tree_red;
+          x = x_parent;
+          x_parent = x_parent->parent;
+        } else {
+          if (w->right == 0 || w->right->color == __rb_tree_black) {
+            if (w->left) w->left->color = __rb_tree_black;
+            w->color = __rb_tree_red;
+            __rb_tree_rotate_right(w, root);
+            w = x_parent->right;
+          }
+          w->color = x_parent->color;
+          x_parent->color = __rb_tree_black;
+          if (w->right) w->right->color = __rb_tree_black;
+          __rb_tree_rotate_left(x_parent, root);
+          break;
+        }
+      } else {                  // same as above, with right <-> left.
+        __rb_tree_node_base* w = x_parent->left;
+        if (w->color == __rb_tree_red) {
+          w->color = __rb_tree_black;
+          x_parent->color = __rb_tree_red;
+          __rb_tree_rotate_right(x_parent, root);
+          w = x_parent->left;
+        }
+        if ((w->right == 0 || w->right->color == __rb_tree_black) &&
+            (w->left == 0 || w->left->color == __rb_tree_black)) {
+          w->color = __rb_tree_red;
+          x = x_parent;
+          x_parent = x_parent->parent;
+        } else {
+          if (w->left == 0 || w->left->color == __rb_tree_black) {
+            if (w->right) w->right->color = __rb_tree_black;
+            w->color = __rb_tree_red;
+            __rb_tree_rotate_left(w, root);
+            w = x_parent->left;
+          }
+          w->color = x_parent->color;
+          x_parent->color = __rb_tree_black;
+          if (w->left) w->left->color = __rb_tree_black;
+          __rb_tree_rotate_right(x_parent, root);
+          break;
+        }
+      }
+    if (x) x->color = __rb_tree_black;
+  }
+  return y;
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare,
+          class Alloc = alloc>
+class rb_tree {
+protected:
+  typedef void* void_pointer;
+  typedef __rb_tree_node_base* base_ptr;
+  typedef __rb_tree_node<Value> rb_tree_node;
+  typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
+  typedef __rb_tree_color_type color_type;
+public:
+  typedef Key key_type;
+  typedef Value value_type;
+  typedef value_type* pointer;
+  typedef const value_type* const_pointer;
+  typedef value_type& reference;
+  typedef const value_type& const_reference;
+  typedef rb_tree_node* link_type;
+  typedef size_t size_type;
+  typedef ptrdiff_t difference_type;
+protected:
+  link_type get_node() { return rb_tree_node_allocator::allocate(); }
+  void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); }
+
+  link_type create_node(const value_type& x) {
+    link_type tmp = get_node();
+    __STL_TRY {
+      construct(&tmp->value_field, x);
+    }
+    __STL_UNWIND(put_node(tmp));
+    return tmp;
+  }
+
+  link_type clone_node(link_type x) {
+    link_type tmp = create_node(x->value_field);
+    tmp->color = x->color;
+    tmp->left = 0;
+    tmp->right = 0;
+    return tmp;
+  }
+
+  void destroy_node(link_type p) {
+    destroy(&p->value_field);
+    put_node(p);
+  }
+
+protected:
+  size_type node_count; // keeps track of size of tree
+  link_type header;  
+  Compare key_compare;
+
+  link_type& root() const { return (link_type&) header->parent; }
+  link_type& leftmost() const { return (link_type&) header->left; }
+  link_type& rightmost() const { return (link_type&) header->right; }
+
+  static link_type& left(link_type x) { return (link_type&)(x->left); }
+  static link_type& right(link_type x) { return (link_type&)(x->right); }
+  static link_type& parent(link_type x) { return (link_type&)(x->parent); }
+  static reference value(link_type x) { return x->value_field; }
+  static const Key& key(link_type x) { return KeyOfValue()(value(x)); }
+  static color_type& color(link_type x) { return (color_type&)(x->color); }
+
+  static link_type& left(base_ptr x) { return (link_type&)(x->left); }
+  static link_type& right(base_ptr x) { return (link_type&)(x->right); }
+  static link_type& parent(base_ptr x) { return (link_type&)(x->parent); }
+  static reference value(base_ptr x) { return ((link_type)x)->value_field; }
+  static const Key& key(base_ptr x) { return KeyOfValue()(value(link_type(x)));} 
+  static color_type& color(base_ptr x) { return (color_type&)(link_type(x)->color); }
+
+  static link_type minimum(link_type x) { 
+    return (link_type)  __rb_tree_node_base::minimum(x);
+  }
+  static link_type maximum(link_type x) {
+    return (link_type) __rb_tree_node_base::maximum(x);
+  }
+
+public:
+  typedef __rb_tree_iterator<value_type, reference, pointer> iterator;
+  typedef __rb_tree_iterator<value_type, const_reference, const_pointer> 
+          const_iterator;
+
+#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
+  typedef reverse_iterator<const_iterator> const_reverse_iterator;
+  typedef reverse_iterator<iterator> reverse_iterator;
+#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
+  typedef reverse_bidirectional_iterator<iterator, value_type, reference,
+                                         difference_type>
+          reverse_iterator; 
+  typedef reverse_bidirectional_iterator<const_iterator, value_type,
+                                         const_reference, difference_type>
+          const_reverse_iterator;
+#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 
+private:
+  iterator __insert(base_ptr x, base_ptr y, const value_type& v);
+  link_type __copy(link_type x, link_type p);
+  void __erase(link_type x);
+  void init() {
+    header = get_node();
+    color(header) = __rb_tree_red; // used to distinguish header from 
+                                   // root, in iterator.operator++
+    root() = 0;
+    leftmost() = header;
+    rightmost() = header;
+  }
+public:
+                                // allocation/deallocation
+  rb_tree(const Compare& comp = Compare())
+    : node_count(0), key_compare(comp) { init(); }
+
+  rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) 
+    : node_count(0), key_compare(x.key_compare)
+  { 
+    header = get_node();
+    color(header) = __rb_tree_red;
+    if (x.root() == 0) {
+      root() = 0;
+      leftmost() = header;
+      rightmost() = header;
+    }
+    else {
+      __STL_TRY {
+        root() = __copy(x.root(), header);
+      }
+      __STL_UNWIND(put_node(header));
+      leftmost() = minimum(root());
+      rightmost() = maximum(root());
+    }
+    node_count = x.node_count;
+  }
+  ~rb_tree() {
+    clear();
+    put_node(header);
+  }
+  rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& 
+  operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x);
+
+public:    
+                                // accessors:
+  Compare key_comp() const { return key_compare; }
+  iterator begin() { return leftmost(); }
+  const_iterator begin() const { return leftmost(); }
+  iterator end() { return header; }
+  const_iterator end() const { return header; }
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  const_reverse_iterator rbegin() const { 
+    return const_reverse_iterator(end()); 
+  }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+  const_reverse_iterator rend() const { 
+    return const_reverse_iterator(begin());
+  } 
+  bool empty() const { return node_count == 0; }
+  size_type size() const { return node_count; }
+  size_type max_size() const { return size_type(-1); }
+
+  void swap(rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& t) {
+    __STD::swap(header, t.header);
+    __STD::swap(node_count, t.node_count);
+    __STD::swap(key_compare, t.key_compare);
+  }
+    
+public:
+                                // insert/erase
+  pair<iterator,bool> insert_unique(const value_type& x);
+  iterator insert_equal(const value_type& x);
+
+  iterator insert_unique(iterator position, const value_type& x);
+  iterator insert_equal(iterator position, const value_type& x);
+
+#ifdef __STL_MEMBER_TEMPLATES  
+  template <class InputIterator>
+  void insert_unique(InputIterator first, InputIterator last);
+  template <class InputIterator>
+  void insert_equal(InputIterator first, InputIterator last);
+#else /* __STL_MEMBER_TEMPLATES */
+  void insert_unique(const_iterator first, const_iterator last);
+  void insert_unique(const value_type* first, const value_type* last);
+  void insert_equal(const_iterator first, const_iterator last);
+  void insert_equal(const value_type* first, const value_type* last);
+#endif /* __STL_MEMBER_TEMPLATES */
+
+  void erase(iterator position);
+  size_type erase(const key_type& x);
+  void erase(iterator first, iterator last);
+  void erase(const key_type* first, const key_type* last);
+  void clear() {
+    if (node_count != 0) {
+      __erase(root());
+      leftmost() = header;
+      root() = 0;
+      rightmost() = header;
+      node_count = 0;
+    }
+  }      
+
+public:
+                                // set operations:
+  iterator find(const key_type& x);
+  const_iterator find(const key_type& x) const;
+  size_type count(const key_type& x) const;
+  iterator lower_bound(const key_type& x);
+  const_iterator lower_bound(const key_type& x) const;
+  iterator upper_bound(const key_type& x);
+  const_iterator upper_bound(const key_type& x) const;
+  pair<iterator,iterator> equal_range(const key_type& x);
+  pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
+
+public:
+                                // Debugging.
+  bool __rb_verify() const;
+};
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+inline bool operator==(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x, 
+                       const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
+  return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+inline bool operator<(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x, 
+                      const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
+  return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
+}
+
+#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+inline void swap(rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x, 
+                 rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
+  x.swap(y);
+}
+
+#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
+
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::
+operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) {
+  if (this != &x) {
+                                // Note that Key may be a constant type.
+    clear();
+    node_count = 0;
+    key_compare = x.key_compare;        
+    if (x.root() == 0) {
+      root() = 0;
+      leftmost() = header;
+      rightmost() = header;
+    }
+    else {
+      root() = __copy(x.root(), header);
+      leftmost() = minimum(root());
+      rightmost() = maximum(root());
+      node_count = x.node_count;
+    }
+  }
+  return *this;
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::
+__insert(base_ptr x_, base_ptr y_, const Value& v) {
+  link_type x = (link_type) x_;
+  link_type y = (link_type) y_;
+  link_type z;
+
+  if (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y))) {
+    z = create_node(v);
+    left(y) = z;                // also makes leftmost() = z when y == header
+    if (y == header) {
+      root() = z;
+      rightmost() = z;
+    }
+    else if (y == leftmost())
+      leftmost() = z;           // maintain leftmost() pointing to min node
+  }
+  else {
+    z = create_node(v);
+    right(y) = z;
+    if (y == rightmost())
+      rightmost() = z;          // maintain rightmost() pointing to max node
+  }
+  parent(z) = y;
+  left(z) = 0;
+  right(z) = 0;
+  __rb_tree_rebalance(z, header->parent);
+  ++node_count;
+  return iterator(z);
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const Value& v)
+{
+  link_type y = header;
+  link_type x = root();
+  while (x != 0) {
+    y = x;
+    x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);
+  }
+  return __insert(x, y, v);
+}
+
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v)
+{
+  link_type y = header;
+  link_type x = root();
+  bool comp = true;
+  while (x != 0) {
+    y = x;
+    comp = key_compare(KeyOfValue()(v), key(x));
+    x = comp ? left(x) : right(x);
+  }
+  iterator j = iterator(y);   
+  if (comp)
+    if (j == begin())     
+      return pair<iterator,bool>(__insert(x, y, v), true);
+    else
+      --j;
+  if (key_compare(key(j.node), KeyOfValue()(v)))
+    return pair<iterator,bool>(__insert(x, y, v), true);
+  return pair<iterator,bool>(j, false);
+}
+
+
+template <class Key, class Val, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::iterator 
+rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::insert_unique(iterator position,
+                                                             const Val& v) {
+  if (position.node == header->left) // begin()
+    if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
+      return __insert(position.node, position.node, v);
+  // first argument just needs to be non-null 
+    else
+      return insert_unique(v).first;
+  else if (position.node == header) // end()
+    if (key_compare(key(rightmost()), KeyOfValue()(v)))
+      return __insert(0, rightmost(), v);
+    else
+      return insert_unique(v).first;
+  else {
+    iterator before = position;
+    --before;
+    if (key_compare(key(before.node), KeyOfValue()(v))
+        && key_compare(KeyOfValue()(v), key(position.node)))
+      if (right(before.node) == 0)
+        return __insert(0, before.node, v); 
+      else
+        return __insert(position.node, position.node, v);
+    // first argument just needs to be non-null 
+    else
+      return insert_unique(v).first;
+  }
+}
+
+template <class Key, class Val, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::iterator 
+rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::insert_equal(iterator position,
+                                                            const Val& v) {
+  if (position.node == header->left) // begin()
+    if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
+      return __insert(position.node, position.node, v);
+  // first argument just needs to be non-null 
+    else
+      return insert_equal(v);
+  else if (position.node == header) // end()
+    if (!key_compare(KeyOfValue()(v), key(rightmost())))
+      return __insert(0, rightmost(), v);
+    else
+      return insert_equal(v);
+  else {
+    iterator before = position;
+    --before;
+    if (!key_compare(KeyOfValue()(v), key(before.node))
+        && !key_compare(key(position.node), KeyOfValue()(v)))
+      if (right(before.node) == 0)
+        return __insert(0, before.node, v); 
+      else
+        return __insert(position.node, position.node, v);
+    // first argument just needs to be non-null 
+    else
+      return insert_equal(v);
+  }
+}
+
+#ifdef __STL_MEMBER_TEMPLATES  
+
+template <class K, class V, class KoV, class Cmp, class Al> template<class II>
+void rb_tree<K, V, KoV, Cmp, Al>::insert_equal(II first, II last) {
+  for ( ; first != last; ++first)
+    insert_equal(*first);
+}
+
+template <class K, class V, class KoV, class Cmp, class Al> template<class II>
+void rb_tree<K, V, KoV, Cmp, Al>::insert_unique(II first, II last) {
+  for ( ; first != last; ++first)
+    insert_unique(*first);
+}
+
+#else /* __STL_MEMBER_TEMPLATES */
+
+template <class K, class V, class KoV, class Cmp, class Al>
+void
+rb_tree<K, V, KoV, Cmp, Al>::insert_equal(const V* first, const V* last) {
+  for ( ; first != last; ++first)
+    insert_equal(*first);
+}
+
+template <class K, class V, class KoV, class Cmp, class Al>
+void
+rb_tree<K, V, KoV, Cmp, Al>::insert_equal(const_iterator first,
+                                          const_iterator last) {
+  for ( ; first != last; ++first)
+    insert_equal(*first);
+}
+
+template <class K, class V, class KoV, class Cmp, class A>
+void 
+rb_tree<K, V, KoV, Cmp, A>::insert_unique(const V* first, const V* last) {
+  for ( ; first != last; ++first)
+    insert_unique(*first);
+}
+
+template <class K, class V, class KoV, class Cmp, class A>
+void 
+rb_tree<K, V, KoV, Cmp, A>::insert_unique(const_iterator first,
+                                          const_iterator last) {
+  for ( ; first != last; ++first)
+    insert_unique(*first);
+}
+
+#endif /* __STL_MEMBER_TEMPLATES */
+         
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+inline void
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(iterator position) {
+  link_type y = (link_type) __rb_tree_rebalance_for_erase(position.node,
+                                                          header->parent,
+                                                          header->left,
+                                                          header->right);
+  destroy_node(y);
+  --node_count;
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::size_type 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const Key& x) {
+  pair<iterator,iterator> p = equal_range(x);
+  size_type n = 0;
+  distance(p.first, p.second, n);
+  erase(p.first, p.second);
+  return n;
+}
+
+template <class K, class V, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<K, V, KeyOfValue, Compare, Alloc>::link_type 
+rb_tree<K, V, KeyOfValue, Compare, Alloc>::__copy(link_type x, link_type p) {
+                                // structural copy.  x and p must be non-null.
+  link_type top = clone_node(x);
+  top->parent = p;
+ 
+  __STL_TRY {
+    if (x->right)
+      top->right = __copy(right(x), top);
+    p = top;
+    x = left(x);
+
+    while (x != 0) {
+      link_type y = clone_node(x);
+      p->left = y;
+      y->parent = p;
+      if (x->right)
+        y->right = __copy(right(x), y);
+      p = y;
+      x = left(x);
+    }
+  }
+  __STL_UNWIND(__erase(top));
+
+  return top;
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__erase(link_type x) {
+                                // erase without rebalancing
+  while (x != 0) {
+    __erase(right(x));
+    link_type y = left(x);
+    destroy_node(x);
+    x = y;
+  }
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(iterator first, 
+                                                            iterator last) {
+  if (first == begin() && last == end())
+    clear();
+  else
+    while (first != last) erase(first++);
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const Key* first, 
+                                                            const Key* last) {
+  while (first != last) erase(*first++);
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key& k) {
+  link_type y = header;        // Last node which is not less than k. 
+  link_type x = root();        // Current node. 
+
+  while (x != 0) 
+    if (!key_compare(key(x), k))
+      y = x, x = left(x);
+    else
+      x = right(x);
+
+  iterator j = iterator(y);   
+  return (j == end() || key_compare(k, key(j.node))) ? end() : j;
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key& k) const {
+  link_type y = header; /* Last node which is not less than k. */
+  link_type x = root(); /* Current node. */
+
+  while (x != 0) {
+    if (!key_compare(key(x), k))
+      y = x, x = left(x);
+    else
+      x = right(x);
+  }
+  const_iterator j = const_iterator(y);   
+  return (j == end() || key_compare(k, key(j.node))) ? end() : j;
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::size_type 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::count(const Key& k) const {
+  pair<const_iterator, const_iterator> p = equal_range(k);
+  size_type n = 0;
+  distance(p.first, p.second, n);
+  return n;
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const Key& k) {
+  link_type y = header; /* Last node which is not less than k. */
+  link_type x = root(); /* Current node. */
+
+  while (x != 0) 
+    if (!key_compare(key(x), k))
+      y = x, x = left(x);
+    else
+      x = right(x);
+
+  return iterator(y);
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const Key& k) const {
+  link_type y = header; /* Last node which is not less than k. */
+  link_type x = root(); /* Current node. */
+
+  while (x != 0) 
+    if (!key_compare(key(x), k))
+      y = x, x = left(x);
+    else
+      x = right(x);
+
+  return const_iterator(y);
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const Key& k) {
+  link_type y = header; /* Last node which is greater than k. */
+  link_type x = root(); /* Current node. */
+
+   while (x != 0) 
+     if (key_compare(k, key(x)))
+       y = x, x = left(x);
+     else
+       x = right(x);
+
+   return iterator(y);
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const Key& k) const {
+  link_type y = header; /* Last node which is greater than k. */
+  link_type x = root(); /* Current node. */
+
+   while (x != 0) 
+     if (key_compare(k, key(x)))
+       y = x, x = left(x);
+     else
+       x = right(x);
+
+   return const_iterator(y);
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+inline pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator,
+            typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator>
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::equal_range(const Key& k) {
+  return pair<iterator, iterator>(lower_bound(k), upper_bound(k));
+}
+
+template <class Key, class Value, class KoV, class Compare, class Alloc>
+inline pair<typename rb_tree<Key, Value, KoV, Compare, Alloc>::const_iterator,
+            typename rb_tree<Key, Value, KoV, Compare, Alloc>::const_iterator>
+rb_tree<Key, Value, KoV, Compare, Alloc>::equal_range(const Key& k) const {
+  return pair<const_iterator,const_iterator>(lower_bound(k), upper_bound(k));
+}
+
+inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
+{
+  if (node == 0)
+    return 0;
+  else {
+    int bc = node->color == __rb_tree_black ? 1 : 0;
+    if (node == root)
+      return bc;
+    else
+      return bc + __black_count(node->parent, root);
+  }
+}
+
+template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
+bool 
+rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__rb_verify() const
+{
+  if (node_count == 0 || begin() == end())
+    return node_count == 0 && begin() == end() &&
+      header->left == header && header->right == header;
+  
+  int len = __black_count(leftmost(), root());
+  for (const_iterator it = begin(); it != end(); ++it) {
+    link_type x = (link_type) it.node;
+    link_type L = left(x);
+    link_type R = right(x);
+
+    if (x->color == __rb_tree_red)
+      if ((L && L->color == __rb_tree_red) ||
+          (R && R->color == __rb_tree_red))
+        return false;
+
+    if (L && key_compare(key(x), key(L)))
+      return false;
+    if (R && key_compare(key(R), key(x)))
+      return false;
+
+    if (!L && !R && __black_count(x, root()) != len)
+      return false;
+  }
+
+  if (leftmost() != __rb_tree_node_base::minimum(root()))
+    return false;
+  if (rightmost() != __rb_tree_node_base::maximum(root()))
+    return false;
+
+  return true;
+}
+
+__STL_END_NAMESPACE 
+
+#endif /* __SGI_STL_INTERNAL_TREE_H */
+
+// Local Variables:
+// mode:C++
+// End: