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, 0 insertions, 2963 deletions
diff --git a/ml/dlib/dlib/sequence/sequence_compare_1.h b/ml/dlib/dlib/sequence/sequence_compare_1.h deleted file mode 100644 index 9bc3c773d..000000000 --- a/ml/dlib/dlib/sequence/sequence_compare_1.h +++ /dev/null @@ -1,102 +0,0 @@ -// 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 deleted file mode 100644 index 261703f45..000000000 --- a/ml/dlib/dlib/sequence/sequence_compare_abstract.h +++ /dev/null @@ -1,75 +0,0 @@ -// 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 deleted file mode 100644 index 9e1e26f1b..000000000 --- a/ml/dlib/dlib/sequence/sequence_kernel_1.h +++ /dev/null @@ -1,1340 +0,0 @@ -// 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 deleted file mode 100644 index f15c50e93..000000000 --- a/ml/dlib/dlib/sequence/sequence_kernel_2.h +++ /dev/null @@ -1,682 +0,0 @@ -// 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 deleted file mode 100644 index 8a0bdc5b3..000000000 --- a/ml/dlib/dlib/sequence/sequence_kernel_abstract.h +++ /dev/null @@ -1,199 +0,0 @@ -// 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 deleted file mode 100644 index c565b54f0..000000000 --- a/ml/dlib/dlib/sequence/sequence_kernel_c.h +++ /dev/null @@ -1,253 +0,0 @@ -// 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 deleted file mode 100644 index 2dd258e50..000000000 --- a/ml/dlib/dlib/sequence/sequence_sort_1.h +++ /dev/null @@ -1,182 +0,0 @@ -// 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 deleted file mode 100644 index 558d4e0d5..000000000 --- a/ml/dlib/dlib/sequence/sequence_sort_2.h +++ /dev/null @@ -1,65 +0,0 @@ -// 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 deleted file mode 100644 index fe0a91220..000000000 --- a/ml/dlib/dlib/sequence/sequence_sort_abstract.h +++ /dev/null @@ -1,65 +0,0 @@ -// 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_ - |