// Copyright (C) 2003 Davis E. King (davis@dlib.net) // License: Boost Software License See LICENSE.txt for the full license. #ifndef DLIB_BINARY_SEARCH_TREE_KERNEl_1_ #define DLIB_BINARY_SEARCH_TREE_KERNEl_1_ #include "binary_search_tree_kernel_abstract.h" #include "../algs.h" #include "../interfaces/map_pair.h" #include "../interfaces/enumerable.h" #include "../interfaces/remover.h" #include "../serialize.h" #include <cstdlib> #include <functional> namespace dlib { template < typename domain, typename range, typename mem_manager, typename compare = std::less<domain> > class binary_search_tree_kernel_1 : public enumerable<map_pair<domain,range> >, public asc_pair_remover<domain,range,compare> { /*! INITIAL VALUE tree_size == 0 tree_root == 0 tree_height == 0 at_start_ == true current_element == 0 stack == array of 50 node pointers stack_pos == 0 CONVENTION tree_size == size() tree_height == height() stack[stack_pos-1] == pop() current_element_valid() == (current_element != 0) if (current_element_valid()) then element() == current_element->d and current_element->r at_start_ == at_start() if (current_element != 0 && current_element != tree_root) then stack[stack_pos-1] == the parent of the node pointed to by current_element if (tree_size != 0) tree_root == pointer to the root node of the binary search tree else tree_root == 0 for all nodes: { left points to the left subtree or 0 if there is no left subtree and right points to the right subtree or 0 if there is no right subtree and all elements in a left subtree are <= the root and all elements in a right subtree are >= the root and d is the item in the domain of *this contained in the node r is the item in the range of *this contained in the node balance: balance == 0 if both subtrees have the same height balance == -1 if the left subtree has a height that is greater than the height of the right subtree by 1 balance == 1 if the right subtree has a height that is greater than the height of the left subtree by 1 for all trees: the height of the left and right subtrees differ by at most one } !*/ class node { public: node* left; node* right; domain d; range r; signed char balance; }; class mpair : public map_pair<domain,range> { public: const domain* d; range* r; const domain& key( ) const { return *d; } const range& value( ) const { return *r; } range& value( ) { return *r; } }; public: typedef domain domain_type; typedef range range_type; typedef compare compare_type; typedef mem_manager mem_manager_type; binary_search_tree_kernel_1( ) : tree_size(0), tree_root(0), current_element(0), tree_height(0), at_start_(true), stack_pos(0), stack(ppool.allocate_array(50)) { } virtual ~binary_search_tree_kernel_1( ); inline void clear( ); inline short height ( ) const; inline unsigned long count ( const domain& item ) const; inline void add ( domain& d, range& r ); void remove ( const domain& d, domain& d_copy, range& r ); void destroy ( const domain& item ); inline const range* operator[] ( const domain& item ) const; inline range* operator[] ( const domain& item ); inline void swap ( binary_search_tree_kernel_1& item ); // function from the asc_pair_remover interface void remove_any ( domain& d, range& r ); // functions from the enumerable interface inline unsigned long size ( ) const; bool at_start ( ) const; inline void reset ( ) const; bool current_element_valid ( ) const; const map_pair<domain,range>& element ( ) const; map_pair<domain,range>& element ( ); bool move_next ( ) const; void remove_last_in_order ( domain& d, range& r ); void remove_current_element ( domain& d, range& r ); void position_enumerator ( const domain& d ) const; private: inline void rotate_left ( node*& t ); /*! requires - t->balance == 2 - t->right->balance == 0 or 1 - t == reference to the pointer in t's parent node that points to t ensures - #t is still a binary search tree - #t->balance is between 1 and -1 - #t now has a height smaller by 1 if #t->balance == 0 !*/ inline void rotate_right ( node*& t ); /*! requires - t->balance == -2 - t->left->balance == 0 or -1 - t == reference to the pointer in t's parent node that points to t ensures - #t is still a binary search tree - #t->balance is between 1 and -1 - #t now has a height smaller by 1 if #t->balance == 0 !*/ inline void double_rotate_right ( node*& t ); /*! requires - t->balance == -2 - t->left->balance == 1 - t == reference to the pointer in t's parent node that points to t ensures - #t is still a binary search tree - #t now has a balance of 0 - #t now has a height smaller by 1 !*/ inline void double_rotate_left ( node*& t ); /*! requires - t->balance == 2 - t->right->balance == -1 - t == reference to the pointer in t's parent node that points to t ensures - #t is still a binary search tree - #t now has a balance of 0 - #t now has a height smaller by 1 !*/ bool remove_biggest_element_in_tree ( node*& t, domain& d, range& r ); /*! requires - t != 0 (i.e. there must be something in the tree to remove) - t == reference to the pointer in t's parent node that points to t ensures - the biggest node in t has been removed - the biggest node domain element in t has been put into #d - the biggest node range element in t has been put into #r - #t is still a binary search tree - returns false if the height of the tree has not changed - returns true if the height of the tree has shrunk by one !*/ bool remove_least_element_in_tree ( node*& t, domain& d, range& r ); /*! requires - t != 0 (i.e. there must be something in the tree to remove) - t == reference to the pointer in t's parent node that points to t ensures - the least node in t has been removed - the least node domain element in t has been put into #d - the least node range element in t has been put into #r - #t is still a binary search tree - returns false if the height of the tree has not changed - returns true if the height of the tree has shrunk by one !*/ bool add_to_tree ( node*& t, domain& d, range& r ); /*! requires - t == reference to the pointer in t's parent node that points to t ensures - the mapping (d --> r) has been added to #t - #d and #r have initial values for their types - #t is still a binary search tree - returns false if the height of the tree has not changed - returns true if the height of the tree has grown by one !*/ bool remove_from_tree ( node*& t, const domain& d, domain& d_copy, range& r ); /*! requires - return_reference(t,d) != 0 - t == reference to the pointer in t's parent node that points to t ensures - #d_copy is equivalent to d - an element in t equivalent to d has been removed and swapped into #d_copy and its associated range object has been swapped into #r - #t is still a binary search tree - returns false if the height of the tree has not changed - returns true if the height of the tree has shrunk by one !*/ bool remove_from_tree ( node*& t, const domain& item ); /*! requires - return_reference(t,item) != 0 - t == reference to the pointer in t's parent node that points to t ensures - an element in t equivalent to item has been removed - #t is still a binary search tree - returns false if the height of the tree has not changed - returns true if the height of the tree has shrunk by one !*/ const range* return_reference ( const node* t, const domain& d ) const; /*! ensures - if (there is a domain element equivalent to d in t) then - returns a pointer to the element in the range equivalent to d - else - returns 0 !*/ range* return_reference ( node* t, const domain& d ); /*! ensures - if (there is a domain element equivalent to d in t) then - returns a pointer to the element in the range equivalent to d - else - returns 0 !*/ inline bool keep_node_balanced ( node*& t ); /*! requires - t != 0 - t == reference to the pointer in t's parent node that points to t ensures - if (t->balance is < 1 or > 1) then - keep_node_balanced() will ensure that #t->balance == 0, -1, or 1 - #t is still a binary search tree - returns true if it made the tree one height shorter - returns false if it didn't change the height !*/ unsigned long get_count ( const domain& item, node* tree_root ) const; /*! requires - tree_root == the root of a binary search tree or 0 ensures - if (tree_root == 0) then - returns 0 - else - returns the number of elements in tree_root that are equivalent to item !*/ void delete_tree ( node* t ); /*! requires - t != 0 ensures - deallocates the node pointed to by t and all of t's left and right children !*/ void push ( node* n ) const { stack[stack_pos] = n; ++stack_pos; } /*! ensures - pushes n onto the stack !*/ node* pop ( ) const { --stack_pos; return stack[stack_pos]; } /*! ensures - pops the top of the stack and returns it !*/ bool fix_stack ( node* t, unsigned char depth = 0 ); /*! requires - current_element != 0 - depth == 0 - t == tree_root ensures - makes the stack contain the correct set of parent pointers. also adjusts stack_pos so it is correct. - #t is still a binary search tree !*/ bool remove_current_element_from_tree ( node*& t, domain& d, range& r, unsigned long cur_stack_pos = 1 ); /*! requires - t == tree_root - cur_stack_pos == 1 - current_element != 0 ensures - removes the data in the node given by current_element and swaps it into #d and #r. - #t is still a binary search tree - the enumerator is advances on to the next element but its stack is potentially corrupted. so you must call fix_stack(tree_root) to fix it. - returns false if the height of the tree has not changed - returns true if the height of the tree has shrunk by one !*/ // data members mutable mpair p; unsigned long tree_size; node* tree_root; mutable node* current_element; typename mem_manager::template rebind<node>::other pool; typename mem_manager::template rebind<node*>::other ppool; short tree_height; mutable bool at_start_; mutable unsigned char stack_pos; mutable node** stack; compare comp; // restricted functions binary_search_tree_kernel_1(binary_search_tree_kernel_1&); binary_search_tree_kernel_1& operator=(binary_search_tree_kernel_1&); }; template < typename domain, typename range, typename mem_manager, typename compare > inline void swap ( binary_search_tree_kernel_1<domain,range,mem_manager,compare>& a, binary_search_tree_kernel_1<domain,range,mem_manager,compare>& b ) { a.swap(b); } template < typename domain, typename range, typename mem_manager, typename compare > void deserialize ( binary_search_tree_kernel_1<domain,range,mem_manager,compare>& item, std::istream& in ) { try { item.clear(); unsigned long size; deserialize(size,in); domain d; range r; for (unsigned long i = 0; i < size; ++i) { deserialize(d,in); deserialize(r,in); item.add(d,r); } } catch (serialization_error e) { item.clear(); throw serialization_error(e.info + "\n while deserializing object of type binary_search_tree_kernel_1"); } } // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- // member function definitions // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: ~binary_search_tree_kernel_1 ( ) { ppool.deallocate_array(stack); if (tree_size != 0) { delete_tree(tree_root); } } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: clear ( ) { if (tree_size > 0) { delete_tree(tree_root); tree_root = 0; tree_size = 0; tree_height = 0; } // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > unsigned long binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: size ( ) const { return tree_size; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > short binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: height ( ) const { return tree_height; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > unsigned long binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: count ( const domain& item ) const { return get_count(item,tree_root); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: add ( domain& d, range& r ) { tree_height += add_to_tree(tree_root,d,r); ++tree_size; // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: remove ( const domain& d, domain& d_copy, range& r ) { tree_height -= remove_from_tree(tree_root,d,d_copy,r); --tree_size; // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: destroy ( const domain& item ) { tree_height -= remove_from_tree(tree_root,item); --tree_size; // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: remove_any ( domain& d, range& r ) { tree_height -= remove_least_element_in_tree(tree_root,d,r); --tree_size; // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > range* binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: operator[] ( const domain& item ) { return return_reference(tree_root,item); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > const range* binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: operator[] ( const domain& item ) const { return return_reference(tree_root,item); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: swap ( binary_search_tree_kernel_1<domain,range,mem_manager,compare>& item ) { pool.swap(item.pool); ppool.swap(item.ppool); exchange(p,item.p); exchange(stack,item.stack); exchange(stack_pos,item.stack_pos); exchange(comp,item.comp); node* tree_root_temp = item.tree_root; unsigned long tree_size_temp = item.tree_size; short tree_height_temp = item.tree_height; node* current_element_temp = item.current_element; bool at_start_temp = item.at_start_; item.tree_root = tree_root; item.tree_size = tree_size; item.tree_height = tree_height; item.current_element = current_element; item.at_start_ = at_start_; tree_root = tree_root_temp; tree_size = tree_size_temp; tree_height = tree_height_temp; current_element = current_element_temp; at_start_ = at_start_temp; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: remove_last_in_order ( domain& d, range& r ) { tree_height -= remove_biggest_element_in_tree(tree_root,d,r); --tree_size; // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: remove_current_element ( domain& d, range& r ) { tree_height -= remove_current_element_from_tree(tree_root,d,r); --tree_size; // fix the enumerator stack if we need to if (current_element) fix_stack(tree_root); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: position_enumerator ( const domain& d ) const { // clear the enumerator state and make sure the stack is empty reset(); at_start_ = false; node* t = tree_root; bool went_left = false; while (t != 0) { if ( comp(d , t->d) ) { push(t); // if item is on the left then look in left t = t->left; went_left = true; } else if (comp(t->d , d)) { push(t); // if item is on the right then look in right t = t->right; went_left = false; } else { current_element = t; return; } } // if we didn't find any matches but there might be something after the // d in this tree. if (stack_pos > 0) { current_element = pop(); // if we went left from this node then this node is the next // biggest. if (went_left) { return; } else { move_next(); } } } // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- // enumerable function definitions // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: at_start ( ) const { return at_start_; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: reset ( ) const { at_start_ = true; current_element = 0; stack_pos = 0; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: current_element_valid ( ) const { return (current_element != 0); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > const map_pair<domain,range>& binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: element ( ) const { p.d = &(current_element->d); p.r = &(current_element->r); return p; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > map_pair<domain,range>& binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: element ( ) { p.d = &(current_element->d); p.r = &(current_element->r); return p; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: move_next ( ) const { // if we haven't started iterating yet if (at_start_) { at_start_ = false; if (tree_size == 0) { return false; } else { // find the first element in the tree current_element = tree_root; node* temp = current_element->left; while (temp != 0) { push(current_element); current_element = temp; temp = current_element->left; } return true; } } else { if (current_element == 0) { return false; } else { node* temp; bool went_up; // true if we went up the tree from a child node to parent bool from_left = false; // true if we went up and were coming from a left child node // find the next element in the tree if (current_element->right != 0) { // go right and down temp = current_element; push(current_element); current_element = temp->right; went_up = false; } else { // go up to the parent if we can if (current_element == tree_root) { // in this case we have iterated over all the element of the tree current_element = 0; return false; } went_up = true; node* parent = pop(); from_left = (parent->left == current_element); // go up to parent current_element = parent; } while (true) { if (went_up) { if (from_left) { // in this case we have found the next node break; } else { if (current_element == tree_root) { // in this case we have iterated over all the elements // in the tree current_element = 0; return false; } // we should go up node* parent = pop(); from_left = (parent->left == current_element); current_element = parent; } } else { // we just went down to a child node if (current_element->left != 0) { // go left went_up = false; temp = current_element; push(current_element); current_element = temp->left; } else { // if there is no left child then we have found the next node break; } } } return true; } } } // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- // private member function definitions // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: delete_tree ( node* t ) { if (t->left != 0) delete_tree(t->left); if (t->right != 0) delete_tree(t->right); pool.deallocate(t); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: rotate_left ( node*& t ) { // set the new balance numbers if (t->right->balance == 1) { t->balance = 0; t->right->balance = 0; } else { t->balance = 1; t->right->balance = -1; } // perform the rotation node* temp = t->right; t->right = temp->left; temp->left = t; t = temp; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: rotate_right ( node*& t ) { // set the new balance numbers if (t->left->balance == -1) { t->balance = 0; t->left->balance = 0; } else { t->balance = -1; t->left->balance = 1; } // preform the rotation node* temp = t->left; t->left = temp->right; temp->right = t; t = temp; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: double_rotate_right ( node*& t ) { node* temp = t; t = t->left->right; temp->left->right = t->left; t->left = temp->left; temp->left = t->right; t->right = temp; if (t->balance < 0) { t->left->balance = 0; t->right->balance = 1; } else if (t->balance > 0) { t->left->balance = -1; t->right->balance = 0; } else { t->left->balance = 0; t->right->balance = 0; } t->balance = 0; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > void binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: double_rotate_left ( node*& t ) { node* temp = t; t = t->right->left; temp->right->left = t->right; t->right = temp->right; temp->right = t->left; t->left = temp; if (t->balance < 0) { t->left->balance = 0; t->right->balance = 1; } else if (t->balance > 0) { t->left->balance = -1; t->right->balance = 0; } else { t->left->balance = 0; t->right->balance = 0; } t->balance = 0; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: remove_biggest_element_in_tree ( node*& t, domain& d, range& r ) { // make a reference to the current node so we don't have to dereference a // pointer a bunch of times node& tree = *t; // if the right tree is an empty tree if ( tree.right == 0) { // swap nodes domain and range elements into d and r exchange(d,tree.d); exchange(r,tree.r); // plug hole left by removing this node t = tree.left; // delete the node that was just removed pool.deallocate(&tree); // return that the height of this part of the tree has decreased return true; } else { // keep going right // if remove made the tree one height shorter if ( remove_biggest_element_in_tree(tree.right,d,r) ) { // if this caused the current tree to strink then report that if ( tree.balance == 1) { --tree.balance; return true; } else { --tree.balance; return keep_node_balanced(t); } } return false; } } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: remove_least_element_in_tree ( node*& t, domain& d, range& r ) { // make a reference to the current node so we don't have to dereference a // pointer a bunch of times node& tree = *t; // if the left tree is an empty tree if ( tree.left == 0) { // swap nodes domain and range elements into d and r exchange(d,tree.d); exchange(r,tree.r); // plug hole left by removing this node t = tree.right; // delete the node that was just removed pool.deallocate(&tree); // return that the height of this part of the tree has decreased return true; } else { // keep going left // if remove made the tree one height shorter if ( remove_least_element_in_tree(tree.left,d,r) ) { // if this caused the current tree to strink then report that if ( tree.balance == -1) { ++tree.balance; return true; } else { ++tree.balance; return keep_node_balanced(t); } } return false; } } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: add_to_tree ( node*& t, domain& d, range& r ) { // if found place to add if (t == 0) { // create a node to add new item into t = pool.allocate(); // make a reference to the current node so we don't have to dereference a // pointer a bunch of times node& tree = *t; // set left and right pointers to NULL to indicate that there are no // left or right subtrees tree.left = 0; tree.right = 0; tree.balance = 0; // put d and r into t exchange(tree.d,d); exchange(tree.r,r); // indicate that the height of this tree has increased return true; } else // keep looking for a place to add the new item { // make a reference to the current node so we don't have to dereference // a pointer a bunch of times node& tree = *t; signed char old_balance = tree.balance; // add the new item to whatever subtree it should go into if (comp( d , tree.d) ) tree.balance -= add_to_tree(tree.left,d,r); else tree.balance += add_to_tree(tree.right,d,r); // if the tree was balanced to start with if (old_balance == 0) { // if its not balanced anymore then it grew in height if (tree.balance != 0) return true; else return false; } else { // if the tree is now balanced then it didn't grow if (tree.balance == 0) { return false; } else { // if the tree needs to be balanced if (tree.balance != old_balance) { return !keep_node_balanced(t); } // if there has been no change in the heights else { return false; } } } } } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: fix_stack ( node* t, unsigned char depth ) { // if we found the node we were looking for if (t == current_element) { stack_pos = depth; return true; } else if (t == 0) { return false; } if (!( comp(t->d , current_element->d))) { // go left if (fix_stack(t->left,depth+1)) { stack[depth] = t; return true; } } if (!(comp(current_element->d , t->d))) { // go right if (fix_stack(t->right,depth+1)) { stack[depth] = t; return true; } } return false; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: remove_current_element_from_tree ( node*& t, domain& d, range& r, unsigned long cur_stack_pos ) { // make a reference to the current node so we don't have to dereference // a pointer a bunch of times node& tree = *t; // if we found the node we were looking for if (t == current_element) { // swap nodes domain and range elements into d_copy and r exchange(d,tree.d); exchange(r,tree.r); // if there is no left node if (tree.left == 0) { // move the enumerator on to the next element before we mess with the // tree move_next(); // plug hole left by removing this node and free memory t = tree.right; // plug hole with right subtree // delete old node pool.deallocate(&tree); // indicate that the height has changed return true; } // if there is no right node else if (tree.right == 0) { // move the enumerator on to the next element before we mess with the // tree move_next(); // plug hole left by removing this node and free memory t = tree.left; // plug hole with left subtree // delete old node pool.deallocate(&tree); // indicate that the height of this tree has changed return true; } // if there are both a left and right sub node else { // in this case the next current element is going to get swapped back // into this t node. current_element = t; // get an element that can replace the one being removed and do this // if it made the right subtree shrink by one if (remove_least_element_in_tree(tree.right,tree.d,tree.r)) { // adjust the tree height --tree.balance; // if the height of the current tree has dropped by one if (tree.balance == 0) { return true; } else { return keep_node_balanced(t); } } // else this remove did not effect the height of this tree else { return false; } } } else if ( (cur_stack_pos < stack_pos && stack[cur_stack_pos] == tree.left) || tree.left == current_element ) { // go left if (tree.balance == -1) { int balance = tree.balance; balance += remove_current_element_from_tree(tree.left,d,r,cur_stack_pos+1); tree.balance = balance; return !tree.balance; } else { int balance = tree.balance; balance += remove_current_element_from_tree(tree.left,d,r,cur_stack_pos+1); tree.balance = balance; return keep_node_balanced(t); } } else if ( (cur_stack_pos < stack_pos && stack[cur_stack_pos] == tree.right) || tree.right == current_element ) { // go right if (tree.balance == 1) { int balance = tree.balance; balance -= remove_current_element_from_tree(tree.right,d,r,cur_stack_pos+1); tree.balance = balance; return !tree.balance; } else { int balance = tree.balance; balance -= remove_current_element_from_tree(tree.right,d,r,cur_stack_pos+1); tree.balance = balance; return keep_node_balanced(t); } } // this return should never happen but do it anyway to suppress compiler warnings return false; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: remove_from_tree ( node*& t, const domain& d, domain& d_copy, range& r ) { // make a reference to the current node so we don't have to dereference // a pointer a bunch of times node& tree = *t; // if item is on the left if (comp(d , tree.d)) { // if the left side of the tree has the greatest height if (tree.balance == -1) { int balance = tree.balance; balance += remove_from_tree(tree.left,d,d_copy,r); tree.balance = balance; return !tree.balance; } else { int balance = tree.balance; balance += remove_from_tree(tree.left,d,d_copy,r); tree.balance = balance; return keep_node_balanced(t); } } // if item is on the right else if (comp(tree.d , d)) { // if the right side of the tree has the greatest height if (tree.balance == 1) { int balance = tree.balance; balance -= remove_from_tree(tree.right,d,d_copy,r); tree.balance = balance; return !tree.balance; } else { int balance = tree.balance; balance -= remove_from_tree(tree.right,d,d_copy,r); tree.balance = balance; return keep_node_balanced(t); } } // if item is found else { // swap nodes domain and range elements into d_copy and r exchange(d_copy,tree.d); exchange(r,tree.r); // if there is no left node if (tree.left == 0) { // plug hole left by removing this node and free memory t = tree.right; // plug hole with right subtree // delete old node pool.deallocate(&tree); // indicate that the height has changed return true; } // if there is no right node else if (tree.right == 0) { // plug hole left by removing this node and free memory t = tree.left; // plug hole with left subtree // delete old node pool.deallocate(&tree); // indicate that the height of this tree has changed return true; } // if there are both a left and right sub node else { // get an element that can replace the one being removed and do this // if it made the right subtree shrink by one if (remove_least_element_in_tree(tree.right,tree.d,tree.r)) { // adjust the tree height --tree.balance; // if the height of the current tree has dropped by one if (tree.balance == 0) { return true; } else { return keep_node_balanced(t); } } // else this remove did not effect the height of this tree else { return false; } } } } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: remove_from_tree ( node*& t, const domain& d ) { // make a reference to the current node so we don't have to dereference // a pointer a bunch of times node& tree = *t; // if item is on the left if (comp(d , tree.d)) { // if the left side of the tree has the greatest height if (tree.balance == -1) { int balance = tree.balance; balance += remove_from_tree(tree.left,d); tree.balance = balance; return !tree.balance; } else { int balance = tree.balance; balance += remove_from_tree(tree.left,d); tree.balance = balance; return keep_node_balanced(t); } } // if item is on the right else if (comp(tree.d , d)) { // if the right side of the tree has the greatest height if (tree.balance == 1) { int balance = tree.balance; balance -= remove_from_tree(tree.right,d); tree.balance = balance; return !tree.balance; } else { int balance = tree.balance; balance -= remove_from_tree(tree.right,d); tree.balance = balance; return keep_node_balanced(t); } } // if item is found else { // if there is no left node if (tree.left == 0) { // plug hole left by removing this node and free memory t = tree.right; // plug hole with right subtree // delete old node pool.deallocate(&tree); // indicate that the height has changed return true; } // if there is no right node else if (tree.right == 0) { // plug hole left by removing this node and free memory t = tree.left; // plug hole with left subtree // delete old node pool.deallocate(&tree); // indicate that the height of this tree has changed return true; } // if there are both a left and right sub node else { // get an element that can replace the one being removed and do this // if it made the right subtree shrink by one if (remove_least_element_in_tree(tree.right,tree.d,tree.r)) { // adjust the tree height --tree.balance; // if the height of the current tree has dropped by one if (tree.balance == 0) { return true; } else { return keep_node_balanced(t); } } // else this remove did not effect the height of this tree else { return false; } } } } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > range* binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: return_reference ( node* t, const domain& d ) { while (t != 0) { if ( comp(d , t->d )) { // if item is on the left then look in left t = t->left; } else if (comp(t->d , d)) { // if item is on the right then look in right t = t->right; } else { // if it's found then return a reference to it return &(t->r); } } return 0; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > const range* binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: return_reference ( const node* t, const domain& d ) const { while (t != 0) { if ( comp(d , t->d) ) { // if item is on the left then look in left t = t->left; } else if (comp(t->d , d)) { // if item is on the right then look in right t = t->right; } else { // if it's found then return a reference to it return &(t->r); } } return 0; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: keep_node_balanced ( node*& t ) { // make a reference to the current node so we don't have to dereference // a pointer a bunch of times node& tree = *t; // if tree does not need to be balanced then return false if (tree.balance == 0) return false; // if tree needs to be rotated left if (tree.balance == 2) { if (tree.right->balance >= 0) rotate_left(t); else double_rotate_left(t); } // else if the tree needs to be rotated right else if (tree.balance == -2) { if (tree.left->balance <= 0) rotate_right(t); else double_rotate_right(t); } if (t->balance == 0) return true; else return false; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename mem_manager, typename compare > unsigned long binary_search_tree_kernel_1<domain,range,mem_manager,compare>:: get_count ( const domain& d, node* tree_root ) const { if (tree_root != 0) { if (comp(d , tree_root->d)) { // go left return get_count(d,tree_root->left); } else if (comp(tree_root->d , d)) { // go right return get_count(d,tree_root->right); } else { // go left and right to look for more matches return get_count(d,tree_root->left) + get_count(d,tree_root->right) + 1; } } return 0; } // ---------------------------------------------------------------------------------------- } #endif // DLIB_BINARY_SEARCH_TREE_KERNEl_1_