diff options
Diffstat (limited to 'STL/tree.h')
| -rw-r--r-- | STL/tree.h | 1088 |
1 files changed, 0 insertions, 1088 deletions
diff --git a/STL/tree.h b/STL/tree.h deleted file mode 100644 index dc91484b535..00000000000 --- a/STL/tree.h +++ /dev/null @@ -1,1088 +0,0 @@ -/* - * - * 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 and Microsoft - * Corporation make no representations about the suitability of this - * software for any purpose. It is provided "as is" without express or - * implied warranty. - * - */ - -#ifndef TREE_H -#define 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 <algobase.h> -#include <iterator.h> -#include <function.h> -#include <bool.h> -#include <projectn.h> - -#ifndef rb_tree -#define rb_tree rb_tree -#endif - -/* - *Added by d:\\convert.pl --begin-- - */ -namespace std { -/* - *Added by d:\\convert.pl --end-- - */ - -template <class Key, class Value, class KeyOfValue, class Compare> -class rb_tree { -protected: - enum color_type {red, black}; - typedef Allocator<void>::pointer void_pointer; - struct rb_tree_node; - friend rb_tree_node; - struct rb_tree_node { - color_type color_field; - void_pointer parent_link; - void_pointer left_link; - void_pointer right_link; - Value value_field; - }; - static Allocator<rb_tree_node> rb_tree_node_allocator; - static Allocator<Value> value_allocator; -public: - typedef Key key_type; - typedef Value value_type; - typedef Allocator<Value>::pointer pointer; - typedef Allocator<Value>::reference reference; - typedef Allocator<Value>::const_reference const_reference; - typedef Allocator<rb_tree_node> rb_tree_node_allocator_type; - typedef Allocator<rb_tree_node>::pointer link_type; - typedef Allocator<rb_tree_node>::size_type size_type; - typedef Allocator<rb_tree_node>::difference_type difference_type; -protected: - size_type buffer_size() { - return rb_tree_node_allocator.init_page_size(); - } - struct rb_tree_node_buffer; - friend rb_tree_node_buffer; - struct rb_tree_node_buffer { - void_pointer next_buffer; - link_type buffer; - }; -public: - typedef Allocator<rb_tree_node_buffer> buffer_allocator_type; - typedef Allocator<rb_tree_node_buffer>::pointer buffer_pointer; -protected: - static Allocator<rb_tree_node_buffer> buffer_allocator; -/* - * Changed by Terris - */ - /*static*/ buffer_pointer buffer_list; - /*static*/ link_type free_list; - /*static*/ link_type next_avail; - /*static*/ link_type last; - void add_new_buffer() { - buffer_pointer tmp = buffer_allocator.allocate((size_type)1); - tmp->buffer = rb_tree_node_allocator.allocate(buffer_size()); - tmp->next_buffer = buffer_list; - buffer_list = tmp; - next_avail = buffer_list->buffer; - last = next_avail + buffer_size(); - } -/* - * Changed by Terris - */ - /*static*/ size_type number_of_trees; - void deallocate_buffers(); - link_type get_node() { - link_type tmp = free_list; - return free_list ? - (free_list = (link_type)(free_list->right_link), tmp) - : (next_avail == last ? (add_new_buffer(), next_avail++) - : next_avail++); - // ugly code for inlining - avoids multiple returns - } - void put_node(link_type p) { - p->right_link = free_list; - free_list = p; - } -protected: - link_type header; - link_type& root() { return parent(header); } - link_type& root() const { return parent(header); } - link_type& leftmost() { return left(header); } - link_type& leftmost() const { return left(header); } - link_type& rightmost() { return right(header); } - link_type& rightmost() const { return right(header); } - size_type node_count; // keeps track of size of tree - bool insert_always; // controls whether an element already in the - // tree is inserted again -//public: - Compare key_compare; -/* - * Changed by Terris - */ - /*static*/ link_type NIL; - - static link_type& left(link_type x) { - return (link_type&)((*x).left_link); - } - static link_type& right(link_type x) { - return (link_type&)((*x).right_link); - } - static link_type& parent(link_type x) { - return (link_type&)((*x).parent_link); - } - static reference value(link_type x) { return (*x).value_field; } - static Allocator<Key>::const_reference key(link_type x) { - return KeyOfValue()(value(x)); - } - static color_type& color(link_type x) { - return (color_type&)(*x).color_field; } -/* - * Changed by Terris - * Doesn't need to take "NIL" parameter because everyone who calls this - * uses links only from "this" - */ - /*static*/ link_type minimum(link_type x) { - while (left(x) != NIL) - x = left(x); - return x; - } -/* - * Changed by Terris - */ - /*static*/ link_type maximum(link_type x) { - while (right(x) != NIL) - x = right(x); - return x; - } -public: - class iterator; - friend iterator; - class const_iterator; - friend const_iterator; -/* - * Terris comment: Here is where the iterator class starts. - */ - class iterator : public bidirectional_iterator<Value, difference_type> { - friend class rb_tree<Key, Value, KeyOfValue, Compare>; - friend class const_iterator; -/* - * Added by Terris - */ - link_type NIL; - -/* - friend bool operator==(const iterator& x, const iterator& y) { - return x.node == y.node; - } -*/ - protected: - link_type node; - iterator(link_type x, link_type NIL) : node(x), NIL(NIL) {} - public: -/* - * Changed by Terris - */ - iterator() { NIL = NULL; } - bool operator==(const iterator& y) const { return node == y.node; } - reference operator*() const { return value(node); } - iterator& operator++() { - if (right(node) != NIL) { - node = right(node); - while (left(node) != NIL) - node = left(node); - } else { - link_type y = parent(node); - while (node == right(y)) { - node = y; - y = parent(y); - } - if (right(node) != y) // necessary because of rightmost - node = y; - } - return *this; - } - iterator operator++(int) { - iterator tmp = *this; - ++*this; - return tmp; - } - iterator& operator--() { - if (color(node) == red && parent(parent(node)) == node) - // check for header - node = right(node); // return rightmost - else if (left(node) != NIL) { - link_type y = left(node); - while (right(y) != NIL) - y = right(y); - node = y; - } else { - link_type y = parent(node); - while (node == left(y)) { - node = y; - y = parent(y); - } - node = y; - } - return *this; - } - iterator operator--(int) { - iterator tmp = *this; - --*this; - return tmp; - } - }; -/* - * Terris comment: Iterator class ends here - * Terris comment: Const Iterator class starts here - */ - class const_iterator - : public bidirectional_iterator<Value,difference_type> { - friend class rb_tree<Key, Value, KeyOfValue, Compare>; - friend class iterator; -/* - friend bool operator==(const const_iterator& x, const const_iterator& y) { - return x.node == y.node; - } -*/ -/* - * Added by Terris - */ - link_type NIL; - - protected: - link_type node; - const_iterator(link_type x, link_type NIL) : node(x), NIL(NIL) {} - public: -/* - * Changed by Terris - */ - const_iterator() { NIL = NULL; } -/* - * Changed by Terris - */ - const_iterator(const iterator& x) : node(x.node), NIL(x.NIL) {} - bool operator==(const const_iterator& y) const { - return node == y.node; - } - bool operator!=(const const_iterator& y) const { - return node != y.node; - } - const_reference operator*() const { return value(node); } - const_iterator& operator++() { - if (right(node) != NIL) { - node = right(node); - while (left(node) != NIL) - node = left(node); - } else { - link_type y = parent(node); - while (node == right(y)) { - node = y; - y = parent(y); - } - if (right(node) != y) // necessary because of rightmost - node = y; - } - return *this; - } - const_iterator operator++(int) { - const_iterator tmp = *this; - ++*this; - return tmp; - } - const_iterator& operator--() { - if (color(node) == red && parent(parent(node)) == node) - // check for header - node = right(node); // return rightmost - else if (left(node) != NIL) { - link_type y = left(node); - while (right(y) != NIL) - y = right(y); - node = y; - } else { - link_type y = parent(node); - while (node == left(y)) { - node = y; - y = parent(y); - } - node = y; - } - return *this; - } - const_iterator operator--(int) { - const_iterator tmp = *this; - --*this; - return tmp; - } - }; -/* - * Terris comment: const_iterator ends here - */ - 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(link_type x, link_type y, const value_type& v); -/* - * Changed by Terris - */ - link_type __copy(link_type x, link_type p, link_type nil); - void __erase(link_type x); - void init() { - ++number_of_trees; - if ( NIL == 0 ) { - NIL = get_node(); - color(NIL) = black; - parent(NIL) = 0; - left(NIL) = 0; - right(NIL) = 0; - } - header = get_node(); - color(header) = red; // used to distinguish header from root, - // in iterator.operator++ - root() = NIL; - leftmost() = header; - rightmost() = header; - } -public: - -// allocation/deallocation - -/* - * Changed by Terris - */ - rb_tree(const Compare& comp = Compare(), bool always = true) - : node_count(0), key_compare(comp), insert_always(always), free_list(0), buffer_list(0), next_avail(0), - last(0), number_of_trees(0), NIL(0) { - init(); - } -/* - * Changed by Terris - */ - 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), free_list(0), - buffer_list(0), next_avail(0), last(0), number_of_trees(0), NIL(0) { - init(); - insert(first, last); - } -/* - * Changed by Terris - */ - 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), free_list(0), - buffer_list(0), next_avail(0), last(0), number_of_trees(0), - NIL( 0 ) { -/* - * Added by Terris - */ - init(); -/* - * Changed by Terris - */ - // ++number_of_trees; - // header = get_node(); - // color(header) = red; -/* - * Changed by Terris - */ - root() = __copy(x.root(), header, x.NIL); - 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; } -/* - * Changed by Terris - */ - iterator begin() { return iterator(leftmost(), NIL); } -/* - * Changed by Terris - */ - const_iterator begin() const { return const_iterator(leftmost(), NIL); } -/* - * Changed by Terris - */ - iterator end() { return iterator(header, NIL); } -/* - * Changed by Terris - */ - const_iterator end() const { return const_iterator(header, NIL); } - 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) { - std::swap(header, t.header); - std::swap(node_count, t.node_count); - std::swap(insert_always, t.insert_always); - std::swap(key_compare, t.key_compare); - /* - * Added By Terris - */ - std::swap(NIL, t.NIL); - std::swap(buffer_list, t.buffer_list); - std::swap(free_list, t.free_list); - std::swap(next_avail, t.next_avail); - std::swap(last, t.last); - /* - * Added By Terris - */ - } - -// 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); -}; - -/* - * Added by Terris - */ -#if 0 -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; -/* - * Added by Terris - */ -#endif - -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; - -/* Added by Terris - */ -#if 0 -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; -#endif - -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()); -/* - * Changed by Terris - */ - root() = __copy(x.root(), header, x.NIL); - 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, NIL); -} - -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, NIL); - 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); - } - 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); - std::swap(color(y), color(z)); - std::swap(y, z); - // y points to node to be actually deleted, - // z points to old z's former successor - } 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 -/* - * Changed by Terris - */ -rb_tree<Key, Value, KeyOfValue, Compare>::__copy(link_type x, link_type p, link_type xNIL) { - // structural copy - link_type r = x; - while (x != xNIL) { - 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); -/* - * Changed by Terris - */ - right(y) = __copy(right(x), y, xNIL); - p = y; - x = left(x); - } - left(p) = NIL; -/* - * Changed by Terris - */ - return r == xNIL ? NIL : 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; - link_type x = root(); - bool comp = false; - while (x != NIL) { - y = x; - comp = key_compare(key(x), k); - x = comp ? right(x) : left(x); - } - iterator j = iterator(y, NIL); - if (comp) ++j; - 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; - link_type x = root(); - bool comp = false; - while (x != NIL) { - y = x; - comp = key_compare(key(x), k); - x = comp ? right(x) : left(x); - } - const_iterator j = const_iterator(y, NIL); - if (comp) ++j; - 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; - link_type x = root(); - bool comp = false; - while (x != NIL) { - y = x; - comp = key_compare(key(x), k); - x = comp ? right(x) : left(x); - } - iterator j = iterator(y, NIL); - return comp ? ++j : j; -} - -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; - link_type x = root(); - bool comp = false; - while (x != NIL) { - y = x; - comp = key_compare(key(x), k); - x = comp ? right(x) : left(x); - } - const_iterator j = const_iterator(y, NIL); - return comp ? ++j : j; -} - -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; - link_type x = root(); - bool comp = true; - while (x != NIL) { - y = x; - comp = key_compare(k, key(x)); - x = comp ? left(x) : right(x); - } - iterator j = iterator(y, NIL); - return comp ? j : ++j; -} - -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; - link_type x = root(); - bool comp = true; - while (x != NIL) { - y = x; - comp = key_compare(k, key(x)); - x = comp ? left(x) : right(x); - } - const_iterator j = const_iterator(y, NIL); - return comp ? j : ++j; -} - - -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; -} - - -/* - *Added by d:\\convert.pl --begin-- - */ -} -/* - *Added by d:\\convert.pl --end-- - */ - -#endif |