| /* |
| * |
| * Copyright (c) 1996 |
| * 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. |
| * |
| * |
| */ |
| |
| #ifndef __SGI_STL_TREE_H |
| #define __SGI_STL_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 <stddef.h> |
| #include <algobase.h> |
| #include <iterator.h> |
| #include <alloc.h> |
| |
| |
| 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> |
| struct __rb_tree_iterator : public __rb_tree_base_iterator |
| { |
| typedef Value value_type; |
| typedef Value& reference; |
| typedef const Value& const_reference; |
| typedef Value* pointer; |
| typedef __rb_tree_iterator<Value, reference> iterator; |
| typedef __rb_tree_iterator<Value, const_reference> const_iterator; |
| typedef __rb_tree_iterator<Value, Ref> 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; } |
| |
| Ref operator*() const { return link_type(node)->value_field; } |
| |
| 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; |
| } |
| |
| 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> |
| inline Value* value_type(const __rb_tree_iterator<Value, Ref>&) { |
| return (Value*) 0; |
| } |
| |
| 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; |
| ::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(); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| construct(&tmp->value_field, x); |
| return tmp; |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| put_node(tmp); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| 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> iterator; |
| typedef __rb_tree_iterator<value_type, const_reference> const_iterator; |
| |
| 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; |
| 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()) |
| : key_compare(comp), node_count(0) { init(); } |
| |
| rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) |
| : key_compare(x.key_compare), node_count(0) { |
| header = get_node(); |
| color(header) = __rb_tree_red; |
| if (x.root() == 0) { |
| root() = 0; |
| leftmost() = header; |
| rightmost() = header; |
| } |
| else { |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| root() = __copy(x.root(), header); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| put_node(header); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| 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) { |
| ::swap(header, t.header); |
| ::swap(node_count, t.node_count); |
| ::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()); |
| } |
| |
| 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> |
| 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> |
| 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<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> |
| 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> |
| 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> |
| 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> |
| 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; |
| |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| 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); |
| } |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| __erase(top); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| |
| 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> |
| 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> |
| 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> |
| 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> |
| 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> |
| 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> |
| 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> |
| 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<rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, |
| 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 KeyOfValue, class Compare, class Alloc> |
| inline pair<rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator, |
| rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator> |
| rb_tree<Key, Value, KeyOfValue, 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; |
| } |
| |
| #endif /* __SGI_STL_TREE_H */ |
