Polaris: BaseMapRoot.cc Source File

BaseMapRoot.cc Go to the documentation of this file. /// /// #ifdef POLARIS_GNU_PRAGMAS #pragma implementation "BaseMapRoot.h" #pragma implementation "BaseMapNode.h" #endif /// #include "RefList.h" #include "Iterator.h" #include "Wrapper.h" #include "BaseMapNode.h" #include "BaseMapRoot.h" #include "../macros.h" #include "../p-assert.h" template class TypedCollection<BMNode>; template class RefList<BMNode>; template class Iterator<BMNode>; template class Assign<BMNode>; template ostream & operator << (ostream &, const RefList<BMNode> &); BMNode::~BMNode() { #ifdef CLASS_INSTANCE_REGISTRY unregister_instance(BM_NODE, this); #endif } BMNode::BMNode() { #ifdef CLASS_INSTANCE_REGISTRY register_instance(BM_NODE, sizeof(BMNode), this); #endif } Listable * BMNode::listable_clone() const { p_assert(0, "ERROR"); return 0; } void BMNode::print(ostream & o) const { p_assert(0, "ERROR"); o << "<ERROR>"; } /// These two functions should always be overriden. void * BaseMapRoot::_list_remove(Wrapper * NOTUSED(rem_wrap)) { p_abort( "BaseMapRoot::_list_remove: should not be invoked!" ); return 0; } void BaseMapRoot::_list_delete(Wrapper * NOTUSED(del_wrap)) { p_abort( "BaseMapRoot::_list_delete: should not be invoked!" ); } void BaseMapRoot::_kill_key(BMKey & NOTUSED(key)) { p_abort( "BaseMapRoot::_kill_key: should not be invoked!" ); } void BaseMapRoot::_kill_data(void * NOTUSED(data)) { p_abort( "BaseMapRoot::_kill_data: should not be invoked!" ); } /// BaseMapRoot constructor BaseMapRoot::BaseMapRoot() { #ifdef MEMORY_LEAK_PRINT cout << "BaseMapRoot ctor: " << this << " : size=" << sizeof(BaseMapRoot) << endl; #endif /// ... Create sentinel and point to it as the root _sentinel = new BMNode; _sentinel->_type = NONROOT; _sentinel->_parent = 0; _sentinel->_left = 0; _sentinel->_right = 0; _sentinel->_data = 0; _sentinel->_color = BLACK; _sentinel->_key._keyval = 0; _root = _sentinel; /// ... Initially, no entries _entries = 0; } /// Print a map (for debugging purposes only) ostream & operator << (ostream & o, const BaseMapRoot & map) { RefList<BMNode> *new_tree_list_ptr = new RefList<BMNode>; o << "BaseMapRoot output:\n"; int level = 0; if (map.entries()>0) new_tree_list_ptr->ins_first(*map._root); while (new_tree_list_ptr->entries()>0) { ++level; o << "\nLevel " << level << ":\n"; RefList<BMNode> tree_list(*new_tree_list_ptr); delete new_tree_list_ptr; new_tree_list_ptr = new RefList<BMNode>; Iterator<BMNode> tree_iter(tree_list); while (tree_iter.valid()) { BMNode &tree_node = tree_iter.current(); map._print_node(o, tree_node); if (!map._leaf(tree_node._left)) new_tree_list_ptr->ins_last(*tree_node._left); if (!map._leaf(tree_node._right)) new_tree_list_ptr->ins_last(*tree_node._right); ++tree_iter; } } return o << "\nEnd of BaseMapRoot output.\n"; } /// Insert an entry /// This routine is derived from algorithms given in pseudocode form in /// Chapters 13 and 14 of "Introduction to Algorithms" by Cormen, Leiserson /// and Rivest. int BaseMapRoot::ins(BMKey &new_key, Listable *new_data) { BMNode *y; /// ... Create new node BMNode *z = new BMNode; /// ... Node is initially red and has leaves for children z->_map = this; z->_left = _sentinel; z->_right = _sentinel; z->_key = new_key; z->_color = RED; _list_insert(z, new_data); #ifdef DEBUG cout << "Insert node with key "; _print(cout, new_key); cout << ".\n"; #endif /// ... Find position to insert new node BMPosition pos; _position(new_key, pos); /// ... Insert node if (pos._type == TOP) { #ifdef DEBUG cout << "Insert node as root.\n"; #endif _root = z; z->_type = ROOT; z->_map = this; } else { if (pos._type == MATCH) { #ifdef DEBUG cout << "Node with matching key node present: no insert.\n"; #endif delete z; p_abort( "Internal Error: BaseMapRoot::ins(...): " "A node with the same key already exists. " "(This is an internal error because all of the " "derived classes of BaseMapRoot are required " "to first delete any element in the BaseMapRoot " "which has the same key as a new element to be " "inserted, BEFORE that new element is actually " "inserted. Obviously, this criteria was not " "met in some derived class of BaseMapRoot."); return 0; } z->_type = NONROOT; z->_parent = pos._ptr; if (pos._type == LEFT) { #ifdef DEBUG cout << "Insert node as left child.\n"; #endif pos._ptr->_left = z; } else { #ifdef DEBUG cout << "Insert node as right child.\n"; #endif pos._ptr->_right = z; } } /// ... Increment the count of entries _entries++; #ifdef DEBUG cout << "Tree before insert rebalancing.\n" << (*this); #endif /// ... Rebalance tree while ((z->_type == NONROOT) && (z->_parent->_color == RED)) { /// ... z's parent is red, so it is not the root and so it also has /// ... a valid parent pointer if ((z->_parent) == (z->_parent->_parent->_left)) { /// ... z's parent is a left child, so set y to z's uncle y = z->_parent->_parent->_right; if (y->_color == RED) { /// ... Handle Case 1L - Both z's parent and uncle are red. // /// ... Make both of them black, point to z's grandparent /// ... as the new z and make the new z red (it must have /// ... been black). z->_parent->_color = BLACK; y->_color = BLACK; z = z->_parent->_parent; z->_color = RED; #ifdef DEBUG cout << "Tree encounters Case 1L.\n"; #endif } else { if (z == z->_parent->_right) { /// ... Handle Case 2L - z's uncle is red and z is a right /// ... child of its black parent. // /// ... Point to z's parent as the new z and do a left /// ... rotation about the new z: this leads to Case 3L /// ... at the new z. z = z->_parent; _left_rotate(z); #ifdef DEBUG cout << "Tree encounters Case 2L.\n"; #endif } /// ... Handle Case 3L - z's uncle is red and z is a left child /// ... of its black parent. // /// ... Make z's parent black, make z's grandparent red, /// ... and do a right rotation around z's grandparent. z->_parent->_color = BLACK; z->_parent->_parent->_color = RED; _right_rotate(z->_parent->_parent); #ifdef DEBUG cout << "Tree encounters Case 3L.\n"; #endif } } else { /// ... z's parent is a right child, set y to z's uncle y = z->_parent->_parent->_left; if (y->_color == RED) { /// ... Handle Case 1R - Both z's parent and uncle are red. // /// ... Make both of them black, point to z's grandparent /// ... as the new z and make the new z red (it must have /// ... been black). z->_parent->_color = BLACK; y->_color = BLACK; z->_parent->_parent->_color = RED; z = z->_parent->_parent; #ifdef DEBUG cout << "Tree encounters Case 1R.\n"; #endif } else { if (z == z->_parent->_left) { /// ... Handle Case 2R - z's uncle is red and z is a left /// ... child of its black parent. /// ... Point to z's parent as the new z and do a right /// ... rotation about the new z: this leads to Case 3R /// ... at the new z. z = z->_parent; _right_rotate(z); #ifdef DEBUG cout << "Tree encounters Case 2R.\n"; #endif } /// ... Handle Case 3R - z's uncle is red and z is a right /// ... child of its black parent. // /// ... Make z's parent black, make z's grandparent red, /// ... and do a left rotation around z's grandparent. z->_parent->_color = BLACK; z->_parent->_parent->_color = RED; _left_rotate(z->_parent->_parent); #ifdef DEBUG cout << "Tree encounters Case 3R.\n"; #endif } } } /// ... Ensure that the root (which might be a different node) is a black /// ... node which points to the map. _root->_color = BLACK; _root->_type = ROOT; _root->_map = this; #ifdef DEBUG cout << "Tree after insert rebalancing.\n" << (*this); #endif return 1; } /// Delete an entry /// This routine is derived from algorithms given in pseudocode form in /// Chapters 13 and 14 of "Introduction to Algorithms" by Cormen, Leiserson /// and Rivest. void * BaseMapRoot::remove(BMKey &del_key) { /// ... Note that this algorithm may define and then use the parent pointer /// ... of the sentinel: this is OK because only one delete is going on at /// ... once and because it always defines the pointer before using it BMNode *x; BMNode *y; #ifdef DEBUG cout << "Delete node with key "; _print(cout, del_key); cout << ".\n"; #endif /// ... Find node z to delete BMPosition pos; _position(del_key, pos); /// ... If it isn't there, don't delete anything if (pos._type != MATCH) { #ifdef DEBUG cout << "Node with matching key not present: no delete.\n"; #endif return 0; } BMNode *z = pos._ptr; /// ... Decrement the count of entries _entries--; void *ret_data; if (z->_data->valid()) ret_data = z->_data->object(); else ret_data = 0; Wrapper *del_wrap = z->_data; /// ... Find node y to be spliced out if (_leaf(z->_left) || _leaf(z->_right)) y = z; else y = _successor(z); #ifdef DEBUG cout << "Node to be spliced out: " << (*y) << "\n"; #endif if (!_leaf(y->_left)) x = y->_left; else x = y->_right; if (y->_type == ROOT) { x->_type = ROOT; x->_map = y->_map; _root = x; } else { x->_type = NONROOT; x->_parent = y->_parent; if (y == y->_parent->_left) y->_parent->_left = x; else y->_parent->_right = x; } /// ... If needed, transfer data from node y to node z if (y != z) { z->_key = y->_key; z->_data = y->_data; } #ifdef DEBUG cout << "Tree before delete rebalancing.\n" << (*this); #endif if (y->_color == BLACK) { BMNode *w; /// ... Rebalance tree while ((x->_type == NONROOT) && (x->_color == BLACK)) { if (x == x->_parent->_left) { /// ... x is a left child, set w to x's brother w = x->_parent->_right; if (w->_color == RED) { /// ... Handle Case 1L - w is red. // /// ... Make w black, make x's parent red, left rotate /// ... around x's parent and set w to x's new brother: /// ... this leads to Case 2L, 3L or 4L at the new w. w->_color = BLACK; x->_parent->_color = RED; _left_rotate(x->_parent); w = x->_parent->_right; #ifdef DEBUG cout << "Tree encounters Case 1L.\n"; #endif } if ((w->_left->_color == BLACK) && (w->_right->_color == BLACK)) { /// ... Handle Case 2L - w is black and has two black children. // /// ... Make w red and point to x's parent as the new x. w->_color = RED; x = x->_parent; #ifdef DEBUG cout << "Tree encounters Case 2L.\n"; #endif } else { if (w->_right->_color == BLACK) { /// ... Handle Case 3L - w is black, w's left child is /// ... red and w's right child is black. // /// ... Make w's left child black, make w red, /// ... right-rotate around w, and set w to x's /// ... new brother: /// ... this leads to case 4L at the new w. w->_left->_color = BLACK; w->_color = RED; _right_rotate(w); w = x->_parent->_right; #ifdef DEBUG cout << "Tree encounters Case 3L.\n"; #endif } /// ... Handle Case 4L - w is black, w's left child is /// ... black, and w's right child is red. // /// ... Make w the same color as x's parent, make x's parent /// ... black, make w's right child black, left-rotate around /// ... x's parent and terminate the loop by setting x to the /// ... root. w->_color = x->_parent->_color; x->_parent->_color = BLACK; w->_right->_color = BLACK; _left_rotate(x->_parent); x = _root; #ifdef DEBUG cout << "Tree encounters Case 4L.\n"; #endif } } else { /// ... x is a right child, set w to x's brother w = x->_parent->_left; if (w->_color == RED) { /// ... Handle Case 1R - w is red. // /// ... Make w black, make x's parent red, right rotate /// ... around x's parent and set w to x's new brother: /// ... this leads to Case 2R, 3R or 4R at the new w. w->_color = BLACK; x->_parent->_color = RED; _right_rotate(x->_parent); w = x->_parent->_left; #ifdef DEBUG cout << "Tree encounters Case 1R.\n"; #endif } if ((w->_right->_color == BLACK) && (w->_left->_color == BLACK)) { /// ... Handle Case 2R - w is black and has two black children. // /// ... Make w red and point to x's parent as the new x. w->_color = RED; x = x->_parent; #ifdef DEBUG cout << "Tree encounters Case 2R.\n"; #endif } else { if (w->_left->_color == BLACK) { /// ... Handle Case 3R - w is black, w's right child is /// ... red and w's left child is black. // /// ... Make w's right child black, make w red, /// ... left-rotate around w, and set w to x's new /// ... brother: this leads to case 4R at the new w. w->_right->_color = BLACK; w->_color = RED; _left_rotate(w); w = x->_parent->_left; #ifdef DEBUG cout << "Tree encounters Case 3R.\n"; #endif } /// ... Handle Case 4R - w is black, w's right child is /// ... black, and w's left child is red. // /// ... Make w the same color as x's parent, make x's /// ... parent black, make w's left child black, /// ... right-rotate around x's parent and terminate /// ... the loop by setting x to the root. w->_color = x->_parent->_color; x->_parent->_color = BLACK; w->_left->_color = BLACK; _right_rotate(x->_parent); x = _root; #ifdef DEBUG cout << "Tree encounters Case 4R.\n"; #endif } } } x->_color = BLACK; } /// ... Delete spliced-out node and return to caller. (void) _list_remove(del_wrap); delete y; #ifdef DEBUG cout << "Tree after delete rebalancing.\n" << (*this); #endif return ret_data; } /// Find an entry Listable * BaseMapRoot::find_ref(const BMKey &find_key) const { /// ... Find position node is in, if any BMPosition pos; _position(find_key, pos); if (pos._type != MATCH) return 0; BMNode *z = pos._ptr; return (z->_data->valid() ? z->_data->object() : 0); } /// Check if key is member Boolean BaseMapRoot::member(const BMKey &mem_key) const { BMPosition pos; _position(mem_key, pos); return (pos._type == MATCH); } /// Check BaseMapRoot structure int BaseMapRoot::structures_OK() const { /// ... Check for empty tree if (_leaf(_root)) return 1; /// ... Check root node if ((_root->_type != ROOT) || (_root->_map != this) || (_root->_color != BLACK)) return 0; /// ... Find black height down leftmost path int black_height = 2; BMNode *ptr = _root; while (!_leaf(ptr->_left)) { ptr = ptr->_left; if (ptr->_color == BLACK) black_height++; } /// ... Root is always black, so decrement black height black_height--; return ((_check_node(_root->_left, _root, black_height)) && (_check_node(_root->_right, _root, black_height))); } /// BaseMapRoot destructor BaseMapRoot::~BaseMapRoot() { #ifdef MEMORY_LEAK_PRINT cout << "BaseMapRoot dtor: " << this << " : size=" << sizeof(BaseMapRoot) << endl; #endif /// ... Clear out map p_assert( entries() == 0, "The tree should already be empty." ); /// ... Delete sentinel delete _sentinel; } /// Print a node (for debugging purposes only) /// If possible, use _print_node member function of BaseMapRoot instead ostream & operator << (ostream & o, const BMNode & node) { /// ... Find the pointer to the map in the root node const BMNode *root_node = &node; while (root_node->_type != ROOT) root_node = root_node->_parent; /// ... Print the node with that information root_node->_map->_print_node(o, node); return o; } /// Check node and children Boolean BaseMapRoot::_check_node(const BMNode * node, const BMNode * parent_node, int black_height) const { /// ... If leaf node, residual black height had better be one. if (_leaf(node)) return (black_height == 1); /// ... Check parent pointer and for no consecutive red nodes if ((node->_type != NONROOT) || (node->_parent != parent_node) || ((node->_color == RED) && (parent_node->_color == RED))) return 0; /// ... Check key relative to parent if (((node == parent_node->_left) && (_less(parent_node->_key, node->_key))) || ((node == parent_node->_right) && (_less(node->_key, parent_node->_key)))) return 0; /// ... If this node is black, decrement black height if (node->_color == BLACK) black_height--; /// ... Check child nodes return ((_check_node(node->_left, node, black_height)) && (_check_node(node->_right, node, black_height))); } /// Set position of first node void BaseMapRoot::_first(BMPosition & first) const { first._ptr = _minimum(_root); if (_leaf(first._ptr)) first._type = TOP; else first._type = MATCH; } /// Set position of last node void BaseMapRoot::_last(BMPosition & last) const { last._ptr = _maximum(_root); if (_leaf(last._ptr)) last._type = TOP; else last._type = MATCH; } /// Kill node and children void BaseMapRoot::_kill_node(BMNode * node) { /// void *data; if (!_leaf(node)) { _kill_node(node->_left); _kill_node(node->_right); _entries--; /// ... delete the key (if needed) _kill_key(node->_key); /// ... remove the data from list, and delete the data (if needed) /// data = _list_remove(node->_data); /// _kill_data( data ); _list_delete(node->_data); delete node; } } /// Perform left rotation around a node void BaseMapRoot::_left_rotate(BMNode * x) { BMNode *y = x->_right; /// ... Rotate y into x's current position x->_right = y->_left; if (!_leaf(y->_left)) y->_left->_parent = x; if (x->_type == ROOT) { y->_type = ROOT; y->_map = x->_map; _root = y; } else { y->_type = NONROOT; y->_parent = x->_parent; if (x == x->_parent->_left) x->_parent->_left = y; else x->_parent->_right = y; } y->_left = x; x->_type = NONROOT; x->_parent = y; } /// Find the minimum node at or below a node BMNode * BaseMapRoot::_minimum(const BMNode * z) const { if (!_leaf(z)) while (!_leaf(z->_left)) z = z->_left; return (BMNode *) z; } /// Find the maximum node at or below a node BMNode * BaseMapRoot::_maximum(const BMNode * z) const { if (!_leaf(z)) while (!_leaf(z->_right)) z = z->_right; return (BMNode *) z; } /// Set position to node with key pos_key void BaseMapRoot::_position(const BMKey &pos_key, BMPosition &pos) const { BMNode *x = _root; /// ... BMNode *y = _sentinel; pos._type = TOP; while (!_leaf(x)) { pos._ptr = x; if (_less(pos_key, x->_key)) { x = x->_left; pos._type = LEFT; } else { if (_equal(pos_key, x->_key)) { pos._type = MATCH; return; } x = x->_right; pos._type = RIGHT; } } } /// Print a node (preferred method) void BaseMapRoot::_print_node(ostream & o, const BMNode & node) const { _print(o, node._key); if (node._color == RED) o << " RED "; else o << " BLACK "; } /// Perform right rotation around a node void BaseMapRoot::_right_rotate(BMNode * x) { BMNode *y = x->_left; /// ... Rotate y into x's current position x->_left = y->_right; if (!_leaf(y->_right)) y->_right->_parent = x; if (x->_type == ROOT) { y->_type = ROOT; y->_map = x->_map; _root = y; } else { y->_type = NONROOT; y->_parent = x->_parent; if (x == x->_parent->_right) x->_parent->_right = y; else x->_parent->_left = y; } y->_right = x; x->_type = NONROOT; x->_parent = y; } /// Find the successor of a node BMNode * BaseMapRoot::_successor(const BMNode * z) const { /// ... If z has a right subtree, its successor is the minimum of the nodes /// ... in its right subtree. if (!_leaf(z->_right)) return _minimum(z->_right); /// ... If z is the root and has no right subtree, it has no successor if (z->_type == ROOT) return _sentinel; /// ... Find z's successor by going up the tree. BMNode *y = z->_parent; while ((y->_type == NONROOT) && (z == y->_right)) { z = y; y = y->_parent; } if ((y->_type == ROOT) && (z == y->_right)) return _sentinel; return y; } void * BaseMapRoot::key_ref( Listable *data ) const { p_assert( data, "BaseMapRoot::key_ref: data is null" ); Wrapper *w = data->wrapper(); return (w ? w->key_node() : 0); }

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:05:40 2005