diff options
Diffstat (limited to 'ml/dlib/dlib/sequence/sequence_kernel_1.h')
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_kernel_1.h | 1340 |
1 files changed, 1340 insertions, 0 deletions
diff --git a/ml/dlib/dlib/sequence/sequence_kernel_1.h b/ml/dlib/dlib/sequence/sequence_kernel_1.h new file mode 100644 index 000000000..9e1e26f1b --- /dev/null +++ b/ml/dlib/dlib/sequence/sequence_kernel_1.h @@ -0,0 +1,1340 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_SEQUENCE_KERNEl_1_ +#define DLIB_SEQUENCE_KERNEl_1_ + +#include "sequence_kernel_abstract.h" +#include "../algs.h" +#include "../interfaces/enumerable.h" +#include "../interfaces/remover.h" +#include "../serialize.h" + +namespace dlib +{ + + template < + typename T, + typename mem_manager = default_memory_manager + > + class sequence_kernel_1 : public enumerable<T>, + public remover<T> + { + + /*! + INITIAL VALUE + - tree_root == 0 + - tree_size == 0 + - at_start_ == true + - current_element == 0 + - stack == array of 50 node pointers + - stack_pos == 0 + + CONVENTION + + - if (tree_size > 0) + - tree_root == pointer to the root node of the binary search tree + - else + - tree_root == 0 + + + + - stack[stack_pos-1] == pop() + + - current_element_valid() == (current_element != 0) + + - 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 (current_element_valid()) then + - element() == current_element->item + + + + - tree_size == size() + - (*this)[i] == return_reference(i) + + + - for all nodes: + - left_size == the number of elements in the left subtree. + - left points to the left subtree or 0 if there is no left subtree. + - right points to the right subtree or 0 if there is no right subtree. + + - all elements in a left subtree have a position in the sequence < that + of the root of the current tree. + + - all elements in a right subtree have a position in the + sequence > that of the root of the current tree. + + - item is the sequence element for that 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 subtrees: + - the height of the left and right subtrees differ by at most one + + !*/ + + + class node + { + public: + node* left; + node* right; + unsigned long left_size; + T item; + signed char balance; + }; + + + + public: + + typedef T type; + typedef mem_manager mem_manager_type; + + sequence_kernel_1 ( + ) : + tree_root(0), + tree_size(0), + stack(ppool.allocate_array(50)), + current_element(0), + at_start_(true), + stack_pos(0) + {} + + virtual ~sequence_kernel_1 ( + ); + + inline void clear ( + ); + + void add ( + unsigned long pos, + T& item + ); + + void remove ( + unsigned long pos, + T& item + ); + + void cat ( + sequence_kernel_1& item + ); + + const T& operator[] ( + unsigned long pos + ) const; + + T& operator[] ( + unsigned long pos + ); + + inline void swap ( + sequence_kernel_1& item + ); + + // functions from the remover interface + inline void remove_any ( + T& item + ); + + // functions from the enumerable interface + inline size_t size ( + ) const; + + bool at_start ( + ) const; + + inline void reset ( + ) const; + + bool current_element_valid ( + ) const; + + const T& element ( + ) const; + + T& element ( + ); + + bool move_next ( + ) const; + + + private: + + void delete_nodes ( + node* t + ); + /*! + requires + - t == a pointer to a valid node + ensures + - deletes t and all its sub nodes. + !*/ + + inline void rotate_left ( + node*& t + ); + /*! + requires + - t->balance == 2 + - t->right->balance == 0 or 1 + 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 + 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 + 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 + ensures + - #t is still a binary search tree + - #t now has a balance of 0 and + - #t now has a height smaller by 1 + !*/ + + bool remove_least_element_in_tree ( + node*& t, + T& item + ); + /*! + requires + - t != 0 (i.e. there must be something in the tree to remove) + ensures + - the least node in t has been removed + - the least node element in t has been put into #item + - #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, + unsigned long pos, + T& item + ); + /*! + requires + - pos <= the number of items in the tree + ensures + - item has been added to #t + - #return_reference(pos) == item + - the convention is still satisfied + - #item has an initial value for its type + - 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, + unsigned long pos, + T& item + ); + /*! + requires + - there is an item in the tree associated with pos + ensures + - the element in the tree associated with pos has been removed + and put into #item + - the convention is still satisfied + - returns false if the height of the tree has not changed + - returns true if the height of the tree has shrunk by one + !*/ + + const T& return_reference ( + const node* t, + unsigned long pos + ) const; + /*! + requires + - there is an item in the tree associated with pos + ensures + - returns a const reference to the item in the tree associated with pos + !*/ + + T& return_reference ( + node* t, + unsigned long pos + ); + /*! + requires + - there is an item in the tree associated with pos + ensures + - returns a non-const reference to the item in the tree associated + with pos + !*/ + + inline bool keep_node_balanced ( + node*& t + ); + /*! + requires + - t != 0 + ensures + - if (t->balance is < 1 or > 1) then + - keep_node_balanced() will ensure that t->balance == 0, -1, or 1 + - returns true if it made the tree one height shorter + - returns false if it didn't change the height + !*/ + + 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 + !*/ + + // data members + typename mem_manager::template rebind<node>::other pool; + typename mem_manager::template rebind<node*>::other ppool; + + node* tree_root; + unsigned long tree_size; + + mutable node** stack; + mutable node* current_element; + mutable bool at_start_; + mutable unsigned char stack_pos; + + // restricted functions + sequence_kernel_1(sequence_kernel_1&); // copy constructor + sequence_kernel_1& operator=(sequence_kernel_1&); // assignment operator + + }; + + template < + typename T, + typename mem_manager + > + inline void swap ( + sequence_kernel_1<T,mem_manager>& a, + sequence_kernel_1<T,mem_manager>& b + ) { a.swap(b); } + + template < + typename T, + typename mem_manager + > + void deserialize ( + sequence_kernel_1<T,mem_manager>& item, + std::istream& in + ) + { + try + { + item.clear(); + unsigned long size; + deserialize(size,in); + T temp; + for (unsigned long i = 0; i < size; ++i) + { + deserialize(temp,in); + item.add(i,temp); + } + } + catch (serialization_error e) + { + item.clear(); + throw serialization_error(e.info + "\n while deserializing object of type sequence_kernel_1"); + } + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + sequence_kernel_1<T,mem_manager>:: + ~sequence_kernel_1 ( + ) + { + ppool.deallocate_array(stack); + if (tree_size > 0) + { + delete_nodes(tree_root); + } + } + +// ---------------------------------------------------------------------------------------- + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + swap ( + sequence_kernel_1<T,mem_manager>& item + ) + { + exchange(stack,item.stack); + exchange(stack_pos,item.stack_pos); + + pool.swap(item.pool); + ppool.swap(item.ppool); + + node* tree_root_temp = item.tree_root; + unsigned long tree_size_temp = item.tree_size; + 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.current_element = current_element; + item.at_start_ = at_start_; + + tree_root = tree_root_temp; + tree_size = tree_size_temp; + current_element = current_element_temp; + at_start_ = at_start_temp; + + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + size_t sequence_kernel_1<T,mem_manager>:: + size ( + ) const + { + return tree_size; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + const T& sequence_kernel_1<T,mem_manager>:: + operator[] ( + unsigned long pos + ) const + { + return return_reference(tree_root,pos); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + T& sequence_kernel_1<T,mem_manager>:: + operator[] ( + unsigned long pos + ) + { + return return_reference(tree_root,pos); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + add ( + unsigned long pos, + T& item + ) + { + add_to_tree(tree_root,pos,item); + ++tree_size; + // reset the enumerator + reset(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + remove ( + unsigned long pos, + T& item + ) + { + remove_from_tree(tree_root,pos,item); + --tree_size; + // reset the enumerator + reset(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + cat ( + sequence_kernel_1<T,mem_manager>& item + ) + { + for (unsigned long i = 0; i < item.tree_size; ++i) + { + add_to_tree( + tree_root, + tree_size, + return_reference(item.tree_root,i) + ); + + ++tree_size; + } + + item.clear(); + // reset the enumerator + reset(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + clear ( + ) + { + if (tree_size > 0) + { + delete_nodes(tree_root); + tree_root = 0; + tree_size = 0; + } + // reset the enumerator + reset(); + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // enumerable function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + bool sequence_kernel_1<T,mem_manager>:: + at_start ( + ) const + { + return at_start_; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + reset ( + ) const + { + at_start_ = true; + current_element = 0; + stack_pos = 0; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + bool sequence_kernel_1<T,mem_manager>:: + current_element_valid ( + ) const + { + return (current_element != 0); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + const T& sequence_kernel_1<T,mem_manager>:: + element ( + ) const + { + return current_element->item; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + T& sequence_kernel_1<T,mem_manager>:: + element ( + ) + { + return current_element->item; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + bool sequence_kernel_1<T,mem_manager>:: + 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; + } + } + + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // remover function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + remove_any ( + T& item + ) + { + remove(0,item); + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // private member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + 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; + + + // set left_size to its correct value + t->left_size += t->left->left_size + 1; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + 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; + + + // set left_size to its correct value + t->right->left_size -= t->left_size + 1; + + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + 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; + + + // set left_size to its correct value + t->left_size += t->left->left_size + 1; + t->right->left_size -= t->left_size + 1; + + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + 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; + + // set left_size to its correct value + t->right->left_size -= t->left_size + 1; + t->left_size += t->left->left_size + 1; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + bool sequence_kernel_1<T,mem_manager>:: + remove_least_element_in_tree ( + node*& t, + T& item + ) + { + // 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 element into item + exchange(tree.item,item); + + // plug hole left by removing this node + t = tree.right; + + // delete the node that was just removed + tree.right = 0; + delete_nodes(&tree); + + // return that the height of this part of the tree has decreased + return true; + } + else + { + // subtract one from the left size + --tree.left_size; + + // keep going left + + // if remove made the tree one height shorter + if ( remove_least_element_in_tree(tree.left,item) ) + { + // 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 T, + typename mem_manager + > + bool sequence_kernel_1<T,mem_manager>:: + add_to_tree ( + node*& t, + unsigned long pos, + T& item + ) + { + // 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 0 to indicate that there are no + // left or right subtrees + tree.left = 0; + tree.right = 0; + tree.balance = 0; + tree.left_size = 0; + + // put item into t + exchange(item,tree.item); + + // 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 ( pos < tree.left_size + 1 ) + { + tree.balance -= add_to_tree(tree.left,pos,item); + ++tree.left_size; + } + else + tree.balance += add_to_tree(tree.right,pos - tree.left_size - 1,item); + + + // 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 T, + typename mem_manager + > + bool sequence_kernel_1<T,mem_manager>:: + remove_from_tree ( + node*& t, + unsigned long pos, + T& item + ) + { + + // 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 (pos < tree.left_size) + { + // adjust the left size + --tree.left_size; + + // if the left side of the tree has the greatest height + if (tree.balance == -1) + { + tree.balance += remove_from_tree(tree.left,pos,item); + return !tree.balance; + } + else + { + tree.balance += remove_from_tree(tree.left,pos,item); + return keep_node_balanced(t); + } + + } + // if item is found + else if (pos == tree.left_size) + { + // if there is no left node + if (tree.left == 0) + { + // swap nodes element into item + exchange(tree.item,item); + + // plug hole left by removing this node and free memory + t = tree.right; // plug hole with right subtree + + // delete old node + tree.right = 0; + delete_nodes(&tree); + + // indicate that the height has changed + return true; + } + // if there is no right node + else if (tree.right == 0) + { + // swap nodes element into item + exchange(tree.item,item); + + // plug hole left by removing this node and free memory + t = tree.left; // plug hole with left subtree + + // delete old node + tree.left = 0; + delete_nodes(&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,item)) + { + // adjust the tree height + --tree.balance; + + // put the element into item copy and also plug the + // hole with the smallest element from the right. + exchange(item,tree.item); + + // 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 + { + // put the element into item copy and also plug the + // hole with the smallest element from the right. + exchange(item,tree.item); + + return false; + } + + } + } + // if item is on the right + else + { + + // if the right side of the tree has the greatest height + if (tree.balance == 1) + { + tree.balance -= remove_from_tree(tree.right,pos - tree.left_size - 1,item); + return !tree.balance; + } + else + { + tree.balance -= remove_from_tree(tree.right,pos - tree.left_size - 1,item); + return keep_node_balanced(t); + } + } + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + T& sequence_kernel_1<T,mem_manager>:: + return_reference ( + node* t, + unsigned long pos + ) + { + while (true) + { + // if we have found the node + if (pos == t->left_size) + return t->item; + + if (pos < t->left_size) + { + // go left + t = t->left; + } + else + { + // go right + pos -= t->left_size+1; + t = t->right; + } + } + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + const T& sequence_kernel_1<T,mem_manager>:: + return_reference ( + const node* t, + unsigned long pos + ) const + { + while (true) + { + // if we have found the node + if (pos == t->left_size) + return t->item; + + if (pos < t->left_size) + { + // go left + t = t->left; + } + else + { + // go right + pos -= t->left_size+1; + t = t->right; + } + } + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + bool sequence_kernel_1<T,mem_manager>:: + 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 T, + typename mem_manager + > + void sequence_kernel_1<T,mem_manager>:: + delete_nodes ( + node* t + ) + { + if (t->left) + delete_nodes(t->left); + if (t->right) + delete_nodes(t->right); + pool.deallocate(t); + } + +// ---------------------------------------------------------------------------------------- +} + +#endif // DLIB_SEQUENCE_KERNEl_1_ + |