tree.h

C++标准库源代码_C++ STL Source Code 请不要修改任何文件

                y = left(y);
            x = right(y);
        }
    if (y != z) { // relink y in place of z
        parent(left(z)) = y; 
        left(y) = left(z);
        if (y != right(z)) {
            parent(x) = parent(y); // possibly x == NIL
            left(parent(y)) = x;   // y must be a left child
            right(y) = right(z);
            parent(right(z)) = y;
        } else
            parent(x) = y;  // needed in case x == NIL
        if (root() == z)
            root() = y;
        else if (left(parent(z)) == z)
            left(parent(z)) = y;
        else 
            right(parent(z)) = y;
        parent(y) = parent(z);
        ::swap(color(y), color(z));
        y = z;
                       // y points to node to be actually deleted
    } else {  // y == z
        parent(x) = parent(y);   // possibly x == NIL
        if (root() == z)
            root() = x;
        else 
            if (left(parent(z)) == z)
                left(parent(z)) = x;
            else
                right(parent(z)) = x;
        if (leftmost() == z) 
            if (right(z) == NIL)  // left(z) must be NIL also
                leftmost() = parent(z);
                // makes leftmost() == header if z == root()
        else
            leftmost() = minimum(x);
        if (rightmost() == z)  
            if (left(z) == NIL) // right(z) must be NIL also
                rightmost() = parent(z);  
                // makes rightmost() == header if z == root()
        else  // x == left(z)
            rightmost() = maximum(x);
    }
    if (color(y) != red) { 
        while (x != root() && color(x) == black)
            if (x == left(parent(x))) {
                link_type w = right(parent(x));
                if (color(w) == red) {
                    color(w) = black;
                    color(parent(x)) = red;
                    rotate_left(parent(x));
                    w = right(parent(x));
                }
                if (color(left(w)) == black && color(right(w)) == black) {
                    color(w) = red;
                    x = parent(x);
                } else {
                    if (color(right(w)) == black) {
                        color(left(w)) = black;
                        color(w) = red;
                        rotate_right(w);
                        w = right(parent(x));
                    }
                    color(w) = color(parent(x));
                    color(parent(x)) = black;
                    color(right(w)) = black;
                    rotate_left(parent(x));
                    break;
                }
            } else {  // same as then clause with "right" and "left" exchanged
                link_type w = left(parent(x));
                if (color(w) == red) {
                    color(w) = black;
                    color(parent(x)) = red;
                    rotate_right(parent(x));
                    w = left(parent(x));
                }
                if (color(right(w)) == black && color(left(w)) == black) {
                    color(w) = red;
                    x = parent(x);
                } else {
                    if (color(left(w)) == black) {
                        color(right(w)) = black;
                        color(w) = red;
                        rotate_left(w);
                        w = left(parent(x));
                    }
                    color(w) = color(parent(x));
                    color(parent(x)) = black;
                    color(left(w)) = black;
                    rotate_right(parent(x));
                    break;
                }
            }
        color(x) = black;
    }
    destroy(value_allocator.address(value(y)));
    put_node(y);
    --node_count;
}

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::size_type 
rb_tree<Key, Value, KeyOfValue, Compare>::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 Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::link_type 
rb_tree<Key, Value, KeyOfValue, Compare>::__copy(link_type x, link_type p) {
   // structural copy
   link_type r = x;
   while (x != NIL) {
      link_type y = get_node();
      if (r == x) r = y;  // save for return value
      construct(value_allocator.address(value(y)), value(x));
      left(p) = y;
      parent(y) = p;
      color(y) = color(x);
      right(y) = __copy(right(x), y);
      p = y;
      x = left(x);
   }
   left(p) = NIL;
   return r;
}

template <class Key, class Value, class KeyOfValue, class Compare>
void rb_tree<Key, Value, KeyOfValue, Compare>::__erase(link_type x) {
    // erase without rebalancing
    while (x != NIL) {
       __erase(right(x));
       link_type y = left(x);
       destroy(value_allocator.address(value(x)));
       put_node(x);
       x = y;
    }
}

template <class Key, class Value, class KeyOfValue, class Compare>
void rb_tree<Key, Value, KeyOfValue, Compare>::erase(iterator first, 
                                                     iterator last) {
    if (first == begin() && last == end() && node_count != 0) {
        __erase(root());
        leftmost() = header;
        root() = NIL;
        rightmost() = header;
        node_count = 0;
    } else
        while (first != last) erase(first++);
}

template <class Key, class Value, class KeyOfValue, class Compare>
void rb_tree<Key, Value, KeyOfValue, Compare>::erase(const Key* first, 
                                                     const Key* last) {
    while (first != last) erase(*first++);
}

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::iterator 
rb_tree<Key, Value, KeyOfValue, Compare>::find(const Key& k) {
   link_type y = header; /* Last node which is not less than k. */
   link_type x = root(); /* Current node. */

   while (x != NIL) 
     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>
rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator 
rb_tree<Key, Value, KeyOfValue, Compare>::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 != NIL) {
     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>
rb_tree<Key, Value, KeyOfValue, Compare>::size_type 
rb_tree<Key, Value, KeyOfValue, Compare>::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>
rb_tree<Key, Value, KeyOfValue, Compare>::iterator 
rb_tree<Key, Value, KeyOfValue, Compare>::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 != NIL) 
     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>
rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator 
rb_tree<Key, Value, KeyOfValue, Compare>::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 != NIL) 
     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>
rb_tree<Key, Value, KeyOfValue, Compare>::iterator 
rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound(const Key& k) {
  link_type y = header; /* Last node which is greater than k. */
  link_type x = root(); /* Current node. */

   while (x != NIL) 
     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>
rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator 
rb_tree<Key, Value, KeyOfValue, Compare>::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 != NIL) 
     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>
rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_iterator 
rb_tree<Key, Value, KeyOfValue, Compare>::equal_range(const Key& k) {
    return pair_iterator_iterator(lower_bound(k), upper_bound(k));
}

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::pair_citerator_citerator 
rb_tree<Key, Value, KeyOfValue, Compare>::equal_range(const Key& k) const {
    return pair_citerator_citerator(lower_bound(k), upper_bound(k));
}

template <class Key, class Value, class KeyOfValue, class Compare>
inline void 
rb_tree<Key, Value, KeyOfValue, Compare>::rotate_left(link_type x) {
    link_type y = right(x);
    right(x) = left(y);
    if (left(y) != NIL)
        parent(left(y)) = x;
    parent(y) = parent(x);
    if (x == root())
        root() = y;
    else if (x == left(parent(x)))
        left(parent(x)) = y;
    else
        right(parent(x)) = y;
    left(y) = x;
    parent(x) = y;
}

template <class Key, class Value, class KeyOfValue, class Compare>
inline void 
rb_tree<Key, Value, KeyOfValue, Compare>::rotate_right(link_type x) {
    link_type y = left(x);
    left(x) = right(y);
    if (right(y) != NIL)
        parent(right(y)) = x;
    parent(y) = parent(x);
    if (x == root())
        root() = y;
    else if (x == right(parent(x)))
        right(parent(x)) = y;
    else
        left(parent(x)) = y;
    right(y) = x;
    parent(x) = y;
}

#endif