diff options
Diffstat (limited to 'ml/dlib/dlib/sequence')
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_compare_1.h | 102 | ||||
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_compare_abstract.h | 75 | ||||
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_kernel_1.h | 1340 | ||||
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_kernel_2.h | 682 | ||||
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_kernel_abstract.h | 199 | ||||
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_kernel_c.h | 253 | ||||
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_sort_1.h | 182 | ||||
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_sort_2.h | 65 | ||||
| -rw-r--r-- | ml/dlib/dlib/sequence/sequence_sort_abstract.h | 65 |
9 files changed, 2963 insertions, 0 deletions
diff --git a/ml/dlib/dlib/sequence/sequence_compare_1.h b/ml/dlib/dlib/sequence/sequence_compare_1.h new file mode 100644 index 000000000..9bc3c773d --- /dev/null +++ b/ml/dlib/dlib/sequence/sequence_compare_1.h @@ -0,0 +1,102 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_SEQUENCE_COMPARe_1_ +#define DLIB_SEQUENCE_COMPARe_1_ + +#include "sequence_compare_abstract.h" + +#include "../algs.h" + + +namespace dlib +{ + + template < + typename seq_base + > + class sequence_compare_1 : public seq_base + { + typedef typename seq_base::type T; + + public: + + bool operator< ( + const sequence_compare_1& rhs + ) const; + + bool operator== ( + const sequence_compare_1& rhs + ) const; + + }; + + + template < + typename seq_base + > + inline void swap ( + sequence_compare_1<seq_base>& a, + sequence_compare_1<seq_base>& b + ) { a.swap(b); } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- +// member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + bool sequence_compare_1<seq_base>:: + operator< ( + const sequence_compare_1<seq_base>& rhs + ) const + { + unsigned int length; + if (this->size() < rhs.size()) + length = this->size(); + else + length = rhs.size(); + + for (unsigned long i = 0; i < length; ++i) + { + if ((*this)[i] < rhs[i]) + return true; + else if ( !((*this)[i] == rhs[i]) ) + return false; + } + // they are equal so far + if (this->size() < rhs.size()) + return true; + else + return false; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + bool sequence_compare_1<seq_base>:: + operator== ( + const sequence_compare_1<seq_base>& rhs + ) const + { + if (this->size() != rhs.size()) + return false; + + for (unsigned long i = 0; i < this->size(); ++i) + { + if (!((*this)[i] == rhs[i])) + return false; + } + return true; + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_SEQUENCE_COMPARe_1_ + diff --git a/ml/dlib/dlib/sequence/sequence_compare_abstract.h b/ml/dlib/dlib/sequence/sequence_compare_abstract.h new file mode 100644 index 000000000..261703f45 --- /dev/null +++ b/ml/dlib/dlib/sequence/sequence_compare_abstract.h @@ -0,0 +1,75 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_SEQUENCE_COMPARe_ABSTRACT_ +#ifdef DLIB_SEQUENCE_COMPARe_ABSTRACT_ + +#include "sequence_kernel_abstract.h" + +#include "../algs.h" + + +namespace dlib +{ + + template < + typename seq_base + > + class sequence_compare : public seq_base + { + + /*! + REQUIREMENTS ON T + T must implement operator< for its type and + T must implement operator== for its type + + REQUIREMENTS ON SEQUENCE_BASE + must be an implementation of sequence/sequence_kernel_abstract.h + + + POINTERS AND REFERENCES TO INTERNAL DATA + operator== and operator< do not invalidate pointers or references to + data members + + WHAT THIS EXTENSION DOES FOR sequence + This gives a sequence the ability to compare itself to other + sequences using the < and == operators. + !*/ + + public: + + bool operator< ( + const sequence_compare& rhs + ) const; + /*! + ensures + - returns true if there exists an integer j such that 0 <= j < size() + and for all integers i such that 0 <= i < j where it is true that + (*this)[i] <= rhs[i] and (*this)[j] < rhs[j] + - returns false if there is no j that will satisfy the above conditions + !*/ + + bool operator== ( + const sequence_compare& rhs + ) const; + /*! + ensures + - returns true if for all i: (*this)[i] == rhs[i] else returns false + !*/ + + }; + + template < + typename seq_base + > + inline void swap ( + sequence_compare<seq_base>& a, + sequence_compare<seq_base>& b + ) { a.swap(b); } + /*! + provides a global swap function + !*/ + +} + +#endif // DLIB_SEQUENCE_COMPARe_ABSTRACT_ + 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_ + diff --git a/ml/dlib/dlib/sequence/sequence_kernel_2.h b/ml/dlib/dlib/sequence/sequence_kernel_2.h new file mode 100644 index 000000000..f15c50e93 --- /dev/null +++ b/ml/dlib/dlib/sequence/sequence_kernel_2.h @@ -0,0 +1,682 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_SEQUENCE_KERNEl_2_ +#define DLIB_SEQUENCE_KERNEl_2_ + +#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_2 : public enumerable<T>, + public remover<T> + { + /*! + INITIAL VALUE + sequence_size == 0 + at_start_ == true + current_enumeration_node == 0 + + CONVENTION + sequence_size == the number of elements in the sequence + + at_start_ == at_start() + (current_enumeration_node!=0) == current_element_valid() + if (current_enumeration_node!=0) then + current_enumeration_node->item == element() + current_enumeration_pos == the position of the node pointed to by + current_enumeration_node + + if ( sequence_size > 0 ) + { + current_node == pointer to a node in the linked list and + current_node->right->right->... eventually == current_node and + current_node->left->left->... eventually == current_node and + current_pos == the position in the sequence of + current_node->item + } + + !*/ + + struct node { + T item; + node* right; + node* left; + }; + + public: + + typedef T type; + typedef mem_manager mem_manager_type; + + sequence_kernel_2 ( + ) : + sequence_size(0), + at_start_(true), + current_enumeration_node(0) + {} + + virtual ~sequence_kernel_2 ( + ); + + inline void clear ( + ); + + void add ( + unsigned long pos, + T& item + ); + + void remove ( + unsigned long pos, + T& item + ); + + void cat ( + sequence_kernel_2& item + ); + + const T& operator[] ( + unsigned long pos + ) const; + + T& operator[] ( + unsigned long pos + ); + + void swap ( + sequence_kernel_2& 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* current_node, + unsigned long sequence_size + ); + /*! + requires + CONVENTION IS CORRECT + ensures + all memory associated with the ring of nodes has been freed + !*/ + + void move_to_pos ( + node*& current_node, + unsigned long& current_pos, + unsigned long pos, + unsigned long size + ) const; + /*! + requires + everything in the CONVENTION is correct and + there is a node corresponding to pos in the CONVENTION and + 0 <= pos < size + ensures + current_pos == pos and + current_node->item is the item in the sequence associated with + position pos + !*/ + + // data members + unsigned long sequence_size; + mutable node* current_node; + mutable unsigned long current_pos; + mutable bool at_start_; + mutable node* current_enumeration_node; + mutable unsigned long current_enumeration_pos; + + // restricted functions + sequence_kernel_2(sequence_kernel_2&); // copy constructor + sequence_kernel_2& operator=(sequence_kernel_2&); // assignment operator + + }; + + + template < + typename T, + typename mem_manager + > + inline void swap ( + sequence_kernel_2<T,mem_manager>& a, + sequence_kernel_2<T,mem_manager>& b + ) { a.swap(b); } + + template < + typename T, + typename mem_manager + > + void deserialize ( + sequence_kernel_2<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_2"); + } + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + sequence_kernel_2<T,mem_manager>:: + ~sequence_kernel_2 ( + ) + { + delete_nodes(current_node,sequence_size); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_2<T,mem_manager>:: + clear ( + ) + { + if (sequence_size != 0) + { + delete_nodes(current_node,sequence_size); + sequence_size = 0; + } + // reset the enumerator + reset(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_2<T,mem_manager>:: + add ( + unsigned long pos, + T& item + ) + { + // make new node and swap item into it + node* new_node = new node; + exchange(item,new_node->item); + + if (sequence_size > 0) + { + if (pos == sequence_size) + { + move_to_pos(current_node,current_pos,pos-1,sequence_size); + + node& n_node = *new_node; + node& c_node = *current_node; + + // make new node point to the nodes to its left and right + n_node.right = c_node.right; + n_node.left = current_node; + + // make the left node point back to new_node + c_node.right->left = new_node; + + // make the right node point back to new_node + c_node.right = new_node; + current_pos = pos; + + } + else + { + move_to_pos(current_node,current_pos,pos,sequence_size); + + node& n_node = *new_node; + node& c_node = *current_node; + + // make new node point to the nodes to its left and right + n_node.right = current_node; + n_node.left = c_node.left; + + // make the left node point back to new_node + c_node.left->right = new_node; + + // make the right node point back to new_node + c_node.left = new_node; + } + + } + else + { + current_pos = 0; + new_node->left = new_node; + new_node->right = new_node; + } + + // make the new node the current node + current_node = new_node; + + ++sequence_size; + // reset the enumerator + reset(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_2<T,mem_manager>:: + remove ( + unsigned long pos, + T& item + ) + { + move_to_pos(current_node,current_pos,pos,sequence_size); + node& c_node = *current_node; + exchange(c_node.item,item); + + node* temp = current_node; + + // close up gap left by remove + c_node.left->right = c_node.right; + c_node.right->left = c_node.left; + + current_node = c_node.right; + + --sequence_size; + + delete temp; + // reset the enumerator + reset(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + const T& sequence_kernel_2<T,mem_manager>:: + operator[] ( + unsigned long pos + ) const + { + move_to_pos(current_node,current_pos,pos,sequence_size); + return current_node->item; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_2<T,mem_manager>:: + cat ( + sequence_kernel_2<T,mem_manager>& item + ) + { + if (item.sequence_size > 0) + { + if (sequence_size > 0) + { + // move both sequences to a convenient location + move_to_pos(current_node,current_pos,0,sequence_size); + item.move_to_pos ( + item.current_node, + item.current_pos, + item.sequence_size-1, + item.sequence_size + ); + + // make copies of poitners + node& item_right = *item.current_node->right; + node& left = *current_node->left; + + + item.current_node->right = current_node; + current_node->left = item.current_node; + + left.right = &item_right; + item_right.left = &left; + + // set sizes + sequence_size += item.sequence_size; + item.sequence_size = 0; + } + else + { + // *this is empty so just swap + item.swap(*this); + } + } + item.clear(); + // reset the enumerator + reset(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + T& sequence_kernel_2<T,mem_manager>:: + operator[] ( + unsigned long pos + ) + { + move_to_pos(current_node,current_pos,pos,sequence_size); + return current_node->item; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + size_t sequence_kernel_2<T,mem_manager>:: + size ( + ) const + { + return sequence_size; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_2<T,mem_manager>:: + swap ( + sequence_kernel_2<T,mem_manager>& item + ) + { + unsigned long sequence_size_temp = item.sequence_size; + node* current_node_temp = item.current_node; + unsigned long current_pos_temp = item.current_pos; + bool at_start_temp = item.at_start_; + node* current_enumeration_node_temp = item.current_enumeration_node; + unsigned long current_enumeration_pos_temp = item.current_enumeration_pos; + + item.sequence_size = sequence_size; + item.current_node = current_node; + item.current_pos = current_pos; + item.at_start_ = at_start_; + item.current_enumeration_node = current_enumeration_node; + item.current_enumeration_pos = current_enumeration_pos; + + sequence_size = sequence_size_temp; + current_node = current_node_temp; + current_pos = current_pos_temp; + at_start_ = at_start_temp; + current_enumeration_node = current_enumeration_node_temp; + current_enumeration_pos = current_enumeration_pos_temp; + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // enumerable function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + bool sequence_kernel_2<T,mem_manager>:: + at_start ( + ) const + { + return at_start_; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_2<T,mem_manager>:: + reset ( + ) const + { + at_start_ = true; + current_enumeration_node = 0; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + bool sequence_kernel_2<T,mem_manager>:: + current_element_valid ( + ) const + { + return (current_enumeration_node!=0); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + const T& sequence_kernel_2<T,mem_manager>:: + element ( + ) const + { + return current_enumeration_node->item; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + T& sequence_kernel_2<T,mem_manager>:: + element ( + ) + { + return current_enumeration_node->item; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + bool sequence_kernel_2<T,mem_manager>:: + move_next ( + ) const + { + if (at_start_ && sequence_size>0) + { + move_to_pos(current_node,current_pos,0,sequence_size); + current_enumeration_node = current_node; + current_enumeration_pos = 0; + } + else if (current_enumeration_node!=0) + { + ++current_enumeration_pos; + if (current_enumeration_pos<sequence_size) + { + current_enumeration_node = current_enumeration_node->right; + } + else + { + // we have reached the end of the sequence + current_enumeration_node = 0; + } + } + + at_start_ = false; + return (current_enumeration_node!=0); + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // remover function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_2<T,mem_manager>:: + remove_any ( + T& item + ) + { + remove(0,item); + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // private member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_2<T,mem_manager>:: + delete_nodes ( + node* current_node, + unsigned long sequence_size + ) + { + node* temp; + while (sequence_size) + { + temp = current_node->right; + delete current_node; + current_node = temp; + --sequence_size; + } + } + +// ---------------------------------------------------------------------------------------- + + template < + typename T, + typename mem_manager + > + void sequence_kernel_2<T,mem_manager>:: + move_to_pos ( + node*& current_node, + unsigned long& current_pos, + unsigned long pos, + unsigned long size + ) const + { + if ( current_pos > pos) + { + // number of hops in each direction needed to reach pos + unsigned long right = size + pos - current_pos; + unsigned long left = current_pos - pos; + current_pos = pos; + + if (left < right) + { + // move left to position pos + for (; left > 0; --left) + current_node = current_node->left; + } + else + { + // move left to position pos + for (; right > 0; --right) + current_node = current_node->right; + } + } + else if (current_pos != pos) + { + // number of hops in each direction needed to reach pos + unsigned long right = pos - current_pos; + unsigned long left = size - pos + current_pos; + current_pos = pos; + + if (left < right) + { + // move left to position pos + for (; left > 0; --left) + current_node = current_node->left; + } + else + { + // move left to position pos + for (; right > 0; --right) + current_node = current_node->right; + } + } + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_SEQUENCE_KERNEl_2_ + diff --git a/ml/dlib/dlib/sequence/sequence_kernel_abstract.h b/ml/dlib/dlib/sequence/sequence_kernel_abstract.h new file mode 100644 index 000000000..8a0bdc5b3 --- /dev/null +++ b/ml/dlib/dlib/sequence/sequence_kernel_abstract.h @@ -0,0 +1,199 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_SEQUENCE_KERNEl_ABSTRACT_ +#ifdef DLIB_SEQUENCE_KERNEl_ABSTRACT_ + +#include "../interfaces/enumerable.h" +#include "../interfaces/remover.h" +#include "../serialize.h" +#include "../algs.h" + +namespace dlib +{ + template < + typename T, + typename mem_manager = default_memory_manager + > + class sequence : public enumerable<T>, + public remover<T> + { + + /*! + REQUIREMENTS ON T + T must be swappable by a global swap() and + T must have a default constructor + + REQUIREMENTS ON mem_manager + must be an implementation of memory_manager/memory_manager_kernel_abstract.h or + must be an implementation of memory_manager_global/memory_manager_global_kernel_abstract.h or + must be an implementation of memory_manager_stateless/memory_manager_stateless_kernel_abstract.h + mem_manager::type can be set to anything. + + POINTERS AND REFERENCES TO INTERNAL DATA + swap() and operator[] functions do not invalidate pointers or + references to internal data. + All other functions have no such guarantees. + + ENUMERATION ORDER + The enumerator will iterate over the elements in the sequence from + the 0th element to the (size()-1)th element. + + INITIAL VALUE + size() == 0 + + WHAT THIS OBJECT REPRESENTS + sequence contains items of type T + + This object represents an ordered sequence of items, each item is + associated with an integer value. + The items are numbered from 0 to size()-1 + + Also note that unless specified otherwise, no member functions + of this object throw exceptions. + !*/ + + public: + + typedef T type; + typedef mem_manager mem_manager_type; + + sequence ( + ); + /*! + ensures + - #*this is properly initialized + throws + - std::bad_alloc or any exception thrown by T's constructor + !*/ + + virtual ~sequence ( + ); + /*! + ensures + - all memory associated with *this has been released + !*/ + + void clear ( + ); + /*! + ensures + - #*this has its initial value + throws + - std::bad_alloc or any exception thrown by T's constructor + if this exception is thrown then *this is unusable + until clear() is called and succeeds + !*/ + + void add ( + unsigned long pos, + T& item + ); + /*! + requires + - pos <= size() + ensures + - #size() == size() + 1 + - #item has an initial value for its type + - #operator[](pos) == item + i.e. item has been inserted into *this between the elements which + were previously at position pos-1 and pos + - #at_start() == true + throws + - std::bad_alloc or any exception thrown by T's constructor + if add() throws then it has no effect + !*/ + + void remove ( + unsigned long pos, + T& item + ); + /*! + requires + - pos < size() + ensures + - #size() == size() - 1 + - the element at the position pos in *this has been removed and + swapped into #item + - #at_start() == true + !*/ + + void cat ( + sequence& item + ); + /*! + requires + - &item != this (i.e. you can't concatenate a sequence onto itself) + ensures + - item has been concatenated onto the end of *this + i.e. item[0] becomes (#*this)[size()], item[1] + becomes (#*this)[size()+1], etc. + - #size() == size() + item.size() + - #item has its initial value + - #at_start() == true + !*/ + + const T& operator[] ( + unsigned long pos + ) const; + /*! + requires + - pos < size() + ensures + - returns a const reference to the element at position pos + !*/ + + T& operator[] ( + unsigned long pos + ); + /*! + requires + - pos < size() + ensures + - returns a non-const reference to the element at position pos + !*/ + + void swap ( + sequence& item + ); + /*! + ensures + - swaps *this and item + !*/ + + + private: + + // restricted functions + sequence(sequence&); // copy constructor + sequence& operator=(sequence&); // assignment operator + + }; + + + template < + typename T, + typename mem_manager + > + inline void swap ( + sequence<T,mem_manager>& a, + sequence<T,mem_manager>& b + ) { a.swap(b); } + /*! + provides a global swap function + !*/ + + template < + typename T, + typename mem_manager + > + void deserialize ( + sequence<T,mem_manager>& item, + std::istream& in + ); + /*! + provides deserialization support + !*/ +} + +#endif // DLIB_SEQUENCE_KERNEl_ABSTRACT_ + diff --git a/ml/dlib/dlib/sequence/sequence_kernel_c.h b/ml/dlib/dlib/sequence/sequence_kernel_c.h new file mode 100644 index 000000000..c565b54f0 --- /dev/null +++ b/ml/dlib/dlib/sequence/sequence_kernel_c.h @@ -0,0 +1,253 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_SEQUENCE_KERNEl_C_ +#define DLIB_SEQUENCE_KERNEl_C_ + +#include "sequence_kernel_abstract.h" +#include "../algs.h" +#include "../assert.h" + +namespace dlib +{ + + template < + typename seq_base + > + class sequence_kernel_c : public seq_base + { + typedef typename seq_base::type T; + public: + + + void add ( + unsigned long pos, + T& item + ); + + void remove ( + unsigned long pos, + T& item + ); + + const T& operator[] ( + unsigned long pos + ) const; + + T& operator[] ( + unsigned long pos + ); + + void cat ( + sequence_kernel_c& item + ); + + const T& element ( + ) const; + + T& element ( + ); + + void remove_any ( + T& item + ); + + }; + + + template < + typename seq_base + > + inline void swap ( + sequence_kernel_c<seq_base>& a, + sequence_kernel_c<seq_base>& b + ) { a.swap(b); } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- +// member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + void sequence_kernel_c<seq_base>:: + add( + unsigned long pos, + T& item + ) + { + + // make sure requires clause is not broken + DLIB_CASSERT(( pos <= this->size() ), + "\tvoid sequence::add" + << "\n\tpos must be >= 0 and <= size()" + << "\n\tpos: " << pos + << "\n\tsize(): " << this->size() + << "\n\tthis: " << this + ); + + // call the real function + seq_base::add(pos,item); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + void sequence_kernel_c<seq_base>:: + cat ( + sequence_kernel_c<seq_base>& item + ) + { + // make sure requires clause is not broken + DLIB_CASSERT(&item != this, + "\tvoid sequence::cat" + << "\n\tyou can't concatenate a sequence onto itself" + << "\n\t&item: " << &item + << "\n\tthis: " << this + ); + + // call the real function + seq_base::cat(item); + + } + +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + void sequence_kernel_c<seq_base>:: + remove ( + unsigned long pos, + T& item + ) + { + // make sure requires clause is not broken + DLIB_CASSERT(( pos < this->size() ), + "\tvoid sequence::remove" + << "\n\tpos must be >= 0 and < size()" + << "\n\tpos: " << pos + << "\n\tsize(): " << this->size() + << "\n\tthis: " << this + ); + + // call the real function + seq_base::remove(pos,item); + + } + +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + const typename seq_base::type& sequence_kernel_c<seq_base>:: + operator[] ( + unsigned long pos + ) const + { + + // make sure requires clause is not broken + DLIB_CASSERT(( pos < this->size() ), + "\tconst T& sequence::operator[]" + << "\n\tpos must be >= 0 and < size()" + << "\n\tpos: " << pos + << "\n\tsize(): " << this->size() + << "\n\tthis: " << this + ); + + // call the real function + return seq_base::operator[](pos); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + typename seq_base::type& sequence_kernel_c<seq_base>:: + operator[] ( + unsigned long pos + ) + { + + // make sure requires clause is not broken + DLIB_CASSERT(( pos < this->size() ), + "\tT& sequence::operator[]" + << "\n\tpos must be >= 0 and < size()" + << "\n\tpos: " << pos + << "\n\tsize(): " << this->size() + << "\n\tthis: " << this + ); + + // call the real function + return seq_base::operator[](pos); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + const typename seq_base::type& sequence_kernel_c<seq_base>:: + element ( + ) const + { + DLIB_CASSERT(this->current_element_valid() == true, + "\tconst T& sequence::element() const" + << "\n\tyou can't access the current element if it doesn't exist" + << "\n\tthis: " << this + ); + + return seq_base::element(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + typename seq_base::type& sequence_kernel_c<seq_base>:: + element ( + ) + { + DLIB_CASSERT(this->current_element_valid() == true, + "\tT& sequence::element()" + << "\n\tyou can't access the current element if it doesn't exist" + << "\n\tthis: " << this + ); + + return seq_base::element(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + void sequence_kernel_c<seq_base>:: + remove_any ( + T& item + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( (this->size() > 0), + "\tvoid sequence::remove_any" + << "\n\tsize() must be greater than zero if something is going to be removed" + << "\n\tsize(): " << this->size() + << "\n\tthis: " << this + ); + + // call the real function + seq_base::remove_any(item); + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_SEQUENCE_KERNEl_C_ + diff --git a/ml/dlib/dlib/sequence/sequence_sort_1.h b/ml/dlib/dlib/sequence/sequence_sort_1.h new file mode 100644 index 000000000..2dd258e50 --- /dev/null +++ b/ml/dlib/dlib/sequence/sequence_sort_1.h @@ -0,0 +1,182 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_SEQUENCE_SORt_1_ +#define DLIB_SEQUENCE_SORt_1_ + +#include "sequence_sort_abstract.h" +#include "../algs.h" + +namespace dlib +{ + + template < + typename seq_base + > + class sequence_sort_1 : public seq_base + { + typedef typename seq_base::type T; + + public: + + /*! + this is a median of three version of the QuickSort algorithm and + it sorts sequences of less than 30 elements with a selection sort + !*/ + + void sort ( + ); + + private: + + void sort_this_sequence ( + seq_base& sequence + ); + /*! + ensures + - each element in the sequence is < the element behind it + !*/ + + void selection_sort ( + seq_base& sequence + ); + /*! + ensures + - sequence is sorted with a selection_sort + !*/ + + + }; + + + template < + typename seq_base + > + inline void swap ( + sequence_sort_1<seq_base>& a, + sequence_sort_1<seq_base>& b + ) { a.swap(b); } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- +// member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + void sequence_sort_1<seq_base>:: + sort ( + ) + { + if (this->size() > 1) + { + sort_this_sequence(*this); + } + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- +// private member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + void sequence_sort_1<seq_base>:: + sort_this_sequence ( + seq_base& sequence + ) + { + if (sequence.size() < 30) + { + selection_sort(sequence); + } + else + { + seq_base left, right; + T partition_element; + + sequence.remove(0,partition_element); + + dlib::median ( + partition_element, + sequence[sequence.size()-1], + sequence[(sequence.size()-1)/2] + ); + + // partition sequence into left and right + T temp; + while (sequence.size() > 0) + { + sequence.remove(0,temp); + if (temp < partition_element) + { + left.add(0,temp); + } + else + { + right.add(0,temp); + } + } + + sort_this_sequence(left); + sort_this_sequence(right); + + // combine left and right into sequence + left.swap(sequence); + sequence.add(sequence.size(),partition_element); + sequence.cat(right); + } + } + +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + void sequence_sort_1<seq_base>:: + selection_sort ( + seq_base& sequence + ) + { + if (sequence.size() > 2) + { + T temp[29]; + unsigned long ssize = sequence.size(); + + for (unsigned long i = 0; i < ssize; ++i) + sequence.remove(0,temp[i]); + + unsigned long smallest; + for (unsigned long i = 0; i < ssize - 1; ++i) + { + // find smallest element and swap into i + smallest = i; + for (unsigned long j = i+1; j < ssize; ++j) + { + if (temp[j] < temp[smallest]) + smallest = j; + } + exchange(temp[smallest],temp[i]); + } + + for (unsigned long i = 0; i < ssize; ++i) + sequence.add(i,temp[i]); + } + else if (sequence.size() == 2) + { + if (sequence[1] < sequence[0]) + { + exchange(sequence[0],sequence[1]); + } + } + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_SEQUENCE_SORt_1_ + diff --git a/ml/dlib/dlib/sequence/sequence_sort_2.h b/ml/dlib/dlib/sequence/sequence_sort_2.h new file mode 100644 index 000000000..558d4e0d5 --- /dev/null +++ b/ml/dlib/dlib/sequence/sequence_sort_2.h @@ -0,0 +1,65 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_SEQUENCE_SORt_2_ +#define DLIB_SEQUENCE_SORt_2_ + +#include "sequence_sort_abstract.h" +#include "../algs.h" +#include "../sort.h" + +namespace dlib +{ + + template < + typename seq_base + > + class sequence_sort_2 : public seq_base + { + typedef typename seq_base::type T; + + public: + + /*! + this is a version of the QuickSort algorithm + this uses the dlib::qsort_array function + !*/ + + void sort ( + ); + + + }; + + template < + typename seq_base + > + inline void swap ( + sequence_sort_2<seq_base>& a, + sequence_sort_2<seq_base>& b + ) { a.swap(b); } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- +// member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename seq_base + > + void sequence_sort_2<seq_base>:: + sort ( + ) + { + if (this->size() > 1) + { + dlib::qsort_array(*this,0,this->size()-1); + } + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_SEQUENCE_SORt_2_ + diff --git a/ml/dlib/dlib/sequence/sequence_sort_abstract.h b/ml/dlib/dlib/sequence/sequence_sort_abstract.h new file mode 100644 index 000000000..fe0a91220 --- /dev/null +++ b/ml/dlib/dlib/sequence/sequence_sort_abstract.h @@ -0,0 +1,65 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_SEQUENCE_SORt_ABSTRACT_ +#ifdef DLIB_SEQUENCE_SORt_ABSTRACT_ + +#include "sequence_kernel_abstract.h" + +namespace dlib +{ + + template < + typename seq_base + > + class sequence_sort : public seq_base + { + + /*! + REQUIREMENTS ON T + T must implement operator< for its type + + REQUIREMENTS ON seq_base + must be an implementation of sequence/sequence_kernel_abstract.h + + + + POINTERS AND REFERENCES TO INTERNAL DATA + sort() may invalidate pointers and references to data members. + + WHAT THIS EXTENSION DOES FOR sequence + this gives a sequence the ability to sort its contents by calling sort() + !*/ + + + public: + + void sort ( + ); + /*! + ensures + - for all elements in #*this the ith element is <= the i+1 element + - #at_start() == true + throws + - std::bad_alloc or any exception thrown by T's constructor + data may be lost if sort() throws + !*/ + + + }; + + + template < + typename seq_base + > + inline void swap ( + sequence_sort<seq_base>& a, + sequence_sort<seq_base>& b + ) { a.swap(b); } + /*! + provides a global swap function + !*/ + +} + +#endif // DLIB_SEQUENCE_SORt_ABSTRACT_ + |