tree.h

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C头文件 代码 · 共 952 行 · 第 1/3 页

    rb_tree(const Compare& comp = Compare(), bool always = true) 
           : node_count(0), key_compare(comp), insert_always(always) { 
        init();
    }
    rb_tree(const value_type* first, const value_type* last, 
            const Compare& comp = Compare(), bool always = true)
          : node_count(0), key_compare(comp), insert_always(always) { 
        init();
        insert(first, last);
    }
    rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare>& x, 
            bool always = true) : node_count(x.node_count), 
                 key_compare(x.key_compare), insert_always(always) { 
        ++number_of_trees;
        header = get_node();
        color(header) = red;
        root() = __copy(x.root(), header);
        if (root() == NIL) {
            leftmost() = header;
            rightmost() = header;
        } else {
            leftmost() = minimum(root());
            rightmost() = maximum(root());
        }
    }
    ~rb_tree() {
        erase(begin(), end());
        put_node(header);
        if (--number_of_trees == 0) {
            put_node(NIL);
            NIL = 0;
            deallocate_buffers();
            free_list = 0;    
            next_avail = 0;
            last = 0;
        }
    }
    rb_tree<Key, Value, KeyOfValue, Compare>& 
        operator=(const rb_tree<Key, Value, KeyOfValue, Compare>& x);
    
// 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 rb_tree_node_allocator.max_size(); 
    }
    void swap(rb_tree<Key, Value, KeyOfValue, Compare>& t) {
        ::swap(header, t.header);
        ::swap(node_count, t.node_count);
        ::swap(insert_always, t.insert_always);
        ::swap(key_compare, t.key_compare);
    }
    
// insert/erase

    typedef  pair<iterator, bool> pair_iterator_bool; 
    // typedef done to get around compiler bug
    pair_iterator_bool insert(const value_type& x);
    iterator insert(iterator position, const value_type& x);
    void insert(iterator first, iterator last);
    void insert(const value_type* first, const value_type* last);
    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);

// 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;
    typedef  pair<iterator, iterator> pair_iterator_iterator; 
    // typedef done to get around compiler bug
    pair_iterator_iterator equal_range(const key_type& x);
    typedef  pair<const_iterator, const_iterator> pair_citerator_citerator; 
    // typedef done to get around compiler bug
    pair_citerator_citerator equal_range(const key_type& x) const;
    inline void rotate_left(link_type x);
    inline void rotate_right(link_type x);
};

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::buffer_pointer 
        rb_tree<Key, Value, KeyOfValue, Compare>::buffer_list = 0;

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::link_type 
        rb_tree<Key, Value, KeyOfValue, Compare>::free_list = 0;

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::link_type 
        rb_tree<Key, Value, KeyOfValue, Compare>::next_avail = 0;

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::link_type 
        rb_tree<Key, Value, KeyOfValue, Compare>::last = 0;

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::size_type 
        rb_tree<Key, Value, KeyOfValue, Compare>::number_of_trees = 0;

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::rb_tree_node_allocator_type 
        rb_tree<Key, Value, KeyOfValue, Compare>::rb_tree_node_allocator;

template <class Key, class Value, class KeyOfValue, class Compare>
Allocator<Value> rb_tree<Key, Value, KeyOfValue, Compare>::value_allocator;

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::buffer_allocator_type 
        rb_tree<Key, Value, KeyOfValue, Compare>::buffer_allocator;

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::link_type 
        rb_tree<Key, Value, KeyOfValue, Compare>::NIL = 0;

template <class Key, class Value, class KeyOfValue, class Compare>
void rb_tree<Key, Value, KeyOfValue, Compare>::deallocate_buffers() {
    while (buffer_list) {
        buffer_pointer tmp = buffer_list;
        buffer_list = (buffer_pointer)(buffer_list->next_buffer);
        rb_tree_node_allocator.deallocate(tmp->buffer);
        buffer_allocator.deallocate(tmp);
    }
}

template <class Key, class Value, class KeyOfValue, class Compare>
inline bool operator==(const rb_tree<Key, Value, KeyOfValue, Compare>& x, 
                       const rb_tree<Key, Value, KeyOfValue, Compare>& y) {
    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

template <class Key, class Value, class KeyOfValue, class Compare>
inline bool operator<(const rb_tree<Key, Value, KeyOfValue, Compare>& x, 
                      const rb_tree<Key, Value, KeyOfValue, Compare>& y) {
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>& 
rb_tree<Key, Value, KeyOfValue, Compare>::
operator=(const rb_tree<Key, Value, KeyOfValue, Compare>& x) {
    if (this != &x) {
        // can't be done as in list because Key may be a constant type
        erase(begin(), end());
        root() = __copy(x.root(), header);
        if (root() == NIL) {
            leftmost() = header;
            rightmost() = header;
        } else {
            leftmost() = minimum(root());
            rightmost() = maximum(root());
        }
        node_count = x.node_count;
    }
    return *this;
}

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::iterator
rb_tree<Key, Value, KeyOfValue, Compare>::
__insert(link_type x, link_type y, const Value& v) {
    ++node_count;
    link_type z = get_node();
    construct(value_allocator.address(value(z)), v);
    if (y == header || x != NIL || key_compare(KeyOfValue()(v), key(y))) {
        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 minimum node
    } else {
        right(y) = z;
        if (y == rightmost())
            rightmost() = z;   // maintain rightmost() pointing to maximum node
    }
    parent(z) = y;
    left(z) = NIL;
    right(z) = NIL;
    x = z;  // recolor and rebalance the tree
    color(x) = red;
    while (x != root() && color(parent(x)) == red) 
        if (parent(x) == left(parent(parent(x)))) {
            y = right(parent(parent(x)));
            if (color(y) == red) {
                color(parent(x)) = black;
                color(y) = black;
                color(parent(parent(x))) = red;
                x = parent(parent(x));
            } else {
                if (x == right(parent(x))) {
                    x = parent(x);
                    rotate_left(x);
                }
                color(parent(x)) = black;
                color(parent(parent(x))) = red;
                rotate_right(parent(parent(x)));
            }
        } else {
            y = left(parent(parent(x)));
            if (color(y) == red) {
                color(parent(x)) = black;
                color(y) = black;
                color(parent(parent(x))) = red;
                x = parent(parent(x));
            } else {
                if (x == left(parent(x))) {
                    x = parent(x);
                    rotate_right(x);
                }
                color(parent(x)) = black;
                color(parent(parent(x))) = red;
                rotate_left(parent(parent(x)));
            }
        }
    color(root()) = black;
    return iterator(z);
}

template <class Key, class Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool
rb_tree<Key, Value, KeyOfValue, Compare>::insert(const Value& v) {
    link_type y = header;
    link_type x = root();
    bool comp = true;
    while (x != NIL) {
        y = x;
        comp = key_compare(KeyOfValue()(v), key(x));
        x = comp ? left(x) : right(x);
    }
    if (insert_always)
        return pair_iterator_bool(__insert(x, y, v), true);
    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 Value, class KeyOfValue, class Compare>
rb_tree<Key, Value, KeyOfValue, Compare>::iterator 
rb_tree<Key, Value, KeyOfValue, Compare>::insert(iterator position,
                                                 const Value& v) {
    if (position == iterator(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-NIL 
        else
            return insert(v).first;
    else if (position == iterator(end()))
        if (key_compare(key(rightmost()), KeyOfValue()(v)))
            return __insert(NIL, rightmost(), v);
        else
            return insert(v).first;
    else {
        iterator before = --position;
        if (key_compare(key(before.node), KeyOfValue()(v))
            && key_compare(KeyOfValue()(v), key(position.node)))
            if (right(before.node) == NIL)
                return __insert(NIL, before.node, v); 
            else
                return __insert(position.node, position.node, v);
                // first argument just needs to be non-NIL 
        else
            return insert(v).first;
    }
}

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

template <class Key, class Value, class KeyOfValue, class Compare>
void rb_tree<Key, Value, KeyOfValue, Compare>::insert(const Value* first, 
                                                      const Value* last) {
    while (first != last) insert(*first++);
}
         
template <class Key, class Value, class KeyOfValue, class Compare>
void rb_tree<Key, Value, KeyOfValue, Compare>::erase(iterator position) {
    link_type z = position.node;
    link_type y = z;
    link_type x;
    if (left(y) == NIL)
        x = right(y);
    else
        if (right(y) == NIL) 
            x = left(y);
        else {
            y = right(y);
            while (left(y) != NIL)
                y = left(y);
            x = right(y);