stl_tree.h
资源名称:Vc_STL.rar [点击查看]
上传用户:sichengcw
上传日期:2009-02-17
资源大小:202k
文件大小:35k
源码类别:
STL
开发平台:
Visual C++
- /*
- *
- * 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: