diff options
Diffstat (limited to 'ml/dlib/dlib/queue')
| -rw-r--r-- | ml/dlib/dlib/queue/queue_kernel_1.h | 554 | ||||
| -rw-r--r-- | ml/dlib/dlib/queue/queue_kernel_2.h | 600 | ||||
| -rw-r--r-- | ml/dlib/dlib/queue/queue_kernel_abstract.h | 196 | ||||
| -rw-r--r-- | ml/dlib/dlib/queue/queue_kernel_c.h | 187 | ||||
| -rw-r--r-- | ml/dlib/dlib/queue/queue_sort_1.h | 165 | ||||
| -rw-r--r-- | ml/dlib/dlib/queue/queue_sort_abstract.h | 74 |
6 files changed, 0 insertions, 1776 deletions
diff --git a/ml/dlib/dlib/queue/queue_kernel_1.h b/ml/dlib/dlib/queue/queue_kernel_1.h deleted file mode 100644 index e59bf2659..000000000 --- a/ml/dlib/dlib/queue/queue_kernel_1.h +++ /dev/null @@ -1,554 +0,0 @@ -// Copyright (C) 2003 Davis E. King (davis@dlib.net) -// License: Boost Software License See LICENSE.txt for the full license. -#ifndef DLIB_QUEUE_KERNEl_1_ -#define DLIB_QUEUE_KERNEl_1_ - -#include "queue_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 queue_kernel_1 : public enumerable<T>, - public remover<T> - { - - /*! - INITIAL VALUE - queue_size == 0 - current_element == 0 - at_start_ == true - - CONVENTION - queue_size == the number of elements in the queue - at_start() == at_start_ - current_element_valid() == (current_element != 0) - element() == current_element->item - - if (queue_size > 0) - { - in points to the last element to be inserted into the queue - out points to the next element to be dequeued - - each node points to the node inserted after it except for the most - recently inserted node - - current_element == 0 - } - - !*/ - - - struct node - { - node* last; - - T item; - }; - - - public: - - typedef T type; - typedef mem_manager mem_manager_type; - - queue_kernel_1 ( - ) : - in(0), - out(0), - queue_size(0), - current_element(0), - at_start_(true) - { - } - - virtual ~queue_kernel_1 ( - ); - - inline void clear( - ); - - void enqueue ( - T& item - ); - - void dequeue ( - T& item - ); - - void cat ( - queue_kernel_1& item - ); - - T& current ( - ); - - const T& current ( - ) const; - - void swap ( - queue_kernel_1& item - ); - - // functions from the remover interface - inline void remove_any ( - T& item - ); - - // functions from the enumerable interface - inline size_t size ( - ) const; - - inline bool at_start ( - ) const; - - inline void reset ( - ) const; - - bool current_element_valid ( - ) const; - - inline const T& element ( - ) const; - - inline T& element ( - ); - - bool move_next ( - ) const; - - private: - - void delete_nodes ( - node* start, - unsigned long length - ); - /*! - requires - - start points to a node in a singly linked list - - start->last points to the next node in the list - - there are at least length nodes in the list begining with start - ensures - - length nodes have been deleted starting with the node pointed - to by start - !*/ - - // data members - - node* in; - node* out; - unsigned long queue_size; - mutable node* current_element; - mutable bool at_start_; - - // restricted functions - queue_kernel_1(queue_kernel_1&); // copy constructor - queue_kernel_1& operator=(queue_kernel_1&); // assignment operator - - }; - - template < - typename T, - typename mem_manager - > - inline void swap ( - queue_kernel_1<T,mem_manager>& a, - queue_kernel_1<T,mem_manager>& b - ) { a.swap(b); } - - template < - typename T, - typename mem_manager - > - void deserialize ( - queue_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.enqueue(temp); - } - } - catch (serialization_error e) - { - item.clear(); - throw serialization_error(e.info + "\n while deserializing object of type queue_kernel_1"); - } - } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // member function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - queue_kernel_1<T,mem_manager>:: - ~queue_kernel_1 ( - ) - { - delete_nodes(out,queue_size); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - void queue_kernel_1<T,mem_manager>:: - clear ( - ) - { - delete_nodes(out,queue_size); - queue_size = 0; - - // put the enumerator at the start - reset(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - void queue_kernel_1<T,mem_manager>:: - enqueue ( - T& item - ) - { - // make new node - node* temp = new node; - - // swap item into new node - exchange(item,temp->item); - - if (queue_size == 0) - out = temp; - else - in->last = temp; - - // make in point to the new node - in = temp; - - ++queue_size; - - // put the enumerator at the start - reset(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - void queue_kernel_1<T,mem_manager>:: - dequeue ( - T& item - ) - { - // swap out into item - exchange(item,out->item); - - --queue_size; - - if (queue_size == 0) - { - delete out; - } - else - { - node* temp = out; - - // move out pointer to the next element in the queue - out = out->last; - - // delete old node - delete temp; - } - - // put the enumerator at the start - reset(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - void queue_kernel_1<T,mem_manager>:: - cat ( - queue_kernel_1<T,mem_manager>& item - ) - { - if (item.queue_size > 0) - { - if (queue_size > 0) - { - in->last = item.out; - } - else - { - out = item.out; - } - - - in = item.in; - queue_size += item.queue_size; - item.queue_size = 0; - } - - // put the enumerator at the start - reset(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - T& queue_kernel_1<T,mem_manager>:: - current ( - ) - { - return out->item; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - const T& queue_kernel_1<T,mem_manager>:: - current ( - ) const - { - return out->item; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - void queue_kernel_1<T,mem_manager>:: - swap ( - queue_kernel_1<T,mem_manager>& item - ) - { - node* in_temp = in; - node* out_temp = out; - unsigned long queue_size_temp = queue_size; - node* current_element_temp = current_element; - bool at_start_temp = at_start_; - - in = item.in; - out = item.out; - queue_size = item.queue_size; - current_element = item.current_element; - at_start_ = item.at_start_; - - item.in = in_temp; - item.out = out_temp; - item.queue_size = queue_size_temp; - item.current_element = current_element_temp; - item.at_start_ = at_start_temp; - } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // enumerable function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - bool queue_kernel_1<T,mem_manager>:: - at_start ( - ) const - { - return at_start_; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - size_t queue_kernel_1<T,mem_manager>:: - size ( - ) const - { - return queue_size; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - void queue_kernel_1<T,mem_manager>:: - reset ( - ) const - { - at_start_ = true; - current_element = 0; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - bool queue_kernel_1<T,mem_manager>:: - current_element_valid ( - ) const - { - return (current_element != 0); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - const T& queue_kernel_1<T,mem_manager>:: - element ( - ) const - { - return current_element->item; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - T& queue_kernel_1<T,mem_manager>:: - element ( - ) - { - return current_element->item; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - bool queue_kernel_1<T,mem_manager>:: - move_next ( - ) const - { - if (at_start_) - { - at_start_ = false; - // if the queue is empty then there is nothing to do - if (queue_size == 0) - { - return false; - } - else - { - current_element = out; - return true; - } - } - else - { - // if we are at the last element then the enumeration has finished - if (current_element == in || current_element == 0) - { - current_element = 0; - return false; - } - else - { - current_element = current_element->last; - return true; - } - } - } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // remover function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - void queue_kernel_1<T,mem_manager>:: - remove_any ( - T& item - ) - { - dequeue(item); - } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // private member function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename T, - typename mem_manager - > - void queue_kernel_1<T,mem_manager>:: - delete_nodes ( - node* start, - unsigned long length - ) - { - node* temp; - while (length) - { - temp = start->last; - delete start; - start = temp; - --length; - } - } - -// ---------------------------------------------------------------------------------------- - -} - -#endif // DLIB_QUEUE_KERNEl_1_ - diff --git a/ml/dlib/dlib/queue/queue_kernel_2.h b/ml/dlib/dlib/queue/queue_kernel_2.h deleted file mode 100644 index 8e4536ae9..000000000 --- a/ml/dlib/dlib/queue/queue_kernel_2.h +++ /dev/null @@ -1,600 +0,0 @@ -// Copyright (C) 2004 Davis E. King (davis@dlib.net) -// License: Boost Software License See LICENSE.txt for the full license. -#ifndef DLIB_QUEUE_KERNEl_2_ -#define DLIB_QUEUE_KERNEl_2_ - -#include "queue_kernel_abstract.h" -#include "../algs.h" -#include "../assert.h" -#include "../interfaces/enumerable.h" -#include "../interfaces/remover.h" -#include "../serialize.h" - -namespace dlib -{ - - template < - typename T, - unsigned long block_size, - typename mem_manager = default_memory_manager - > - class queue_kernel_2 : public enumerable<T>, - public remover<T> - { - - /*! - REQUIREMENTS ON block_size - 0 < block_size < 2000000000 - - INITIAL VALUE - queue_size == 0 - current_element == 0 - at_start_ == true - - CONVENTION - queue_size == the number of elements in the queue - at_start() == at_start_ - current_element_valid() == (current_element != 0) - if (current_element_valid()) then - element() == current_element->item[current_element_pos] - - if (queue_size > 0) - { - in->item[in_pos] == the spot where we will put the next item added - into the queue - out->item[out_pos] == current() - - when enqueuing elements inside each node item[0] is filled first, then - item[1], then item[2], etc. - - - each node points to the node inserted after it except for the most - recently inserted node. - } - - !*/ - - - struct node - { - node* next; - - T item[block_size]; - }; - - - public: - - typedef T type; - typedef mem_manager mem_manager_type; - - queue_kernel_2 ( - ) : - in(0), - out(0), - queue_size(0), - current_element(0), - at_start_(true) - { - } - - virtual ~queue_kernel_2 ( - ); - - inline void clear( - ); - - void enqueue ( - T& item - ); - - void dequeue ( - T& item - ); - - void cat ( - queue_kernel_2& item - ); - - T& current ( - ); - - const T& current ( - ) const; - - void swap ( - queue_kernel_2& item - ); - - // functions from the remover interface - inline void remove_any ( - T& item - ); - - // functions from the enumerable interface - inline size_t size ( - ) const; - - inline bool at_start ( - ) const; - - inline void reset ( - ) const; - - bool current_element_valid ( - ) const; - - inline const T& element ( - ) const; - - inline T& element ( - ); - - bool move_next ( - ) const; - - private: - - void delete_nodes ( - node* start, - node* end - ); - /*! - requires - - start points to a node in a singly linked list - - start->next points to the next node in the list - - by following the next pointers you eventually hit the node pointed - to by end - ensures - - calls delete on the start node, the end node, and all nodes in between - !*/ - - // data members - - typename mem_manager::template rebind<node>::other pool; - - node* in; - node* out; - size_t queue_size; - size_t in_pos; - size_t out_pos; - - - mutable node* current_element; - mutable size_t current_element_pos; - mutable bool at_start_; - - // restricted functions - queue_kernel_2(queue_kernel_2&); // copy constructor - queue_kernel_2& operator=(queue_kernel_2&); // assignment operator - - }; - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - inline void swap ( - queue_kernel_2<T,block_size,mem_manager>& a, - queue_kernel_2<T,block_size,mem_manager>& b - ) { a.swap(b); } - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - void deserialize ( - queue_kernel_2<T,block_size,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.enqueue(temp); - } - } - catch (serialization_error e) - { - item.clear(); - throw serialization_error(e.info + "\n while deserializing object of type queue_kernel_2"); - } - } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // member function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - queue_kernel_2<T,block_size,mem_manager>:: - ~queue_kernel_2 ( - ) - { - COMPILE_TIME_ASSERT(0 < block_size && block_size < (unsigned long)(2000000000)); - - if (queue_size > 0) - delete_nodes(out,in); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - void queue_kernel_2<T,block_size,mem_manager>:: - clear ( - ) - { - if (queue_size > 0) - { - delete_nodes(out,in); - queue_size = 0; - } - - // put the enumerator at the start - reset(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - void queue_kernel_2<T,block_size,mem_manager>:: - enqueue ( - T& item - ) - { - if (queue_size == 0) - { - out = in = pool.allocate(); - in_pos = 0; - out_pos = 0; - } - else if (in_pos >= block_size) - { - in->next = pool.allocate(); - in_pos = 0; - in = in->next; - } - - exchange(item,in->item[in_pos]); - ++in_pos; - - ++queue_size; - - // put the enumerator at the start - reset(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - void queue_kernel_2<T,block_size,mem_manager>:: - dequeue ( - T& item - ) - { - // swap out into item - exchange(item,out->item[out_pos]); - - ++out_pos; - --queue_size; - - // if this was the last element in this node then remove this node - if (out_pos == block_size) - { - out_pos = 0; - node* temp = out; - out = out->next; - pool.deallocate(temp); - } - else if (queue_size == 0) - { - pool.deallocate(out); - } - - // put the enumerator at the start - reset(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - void queue_kernel_2<T,block_size,mem_manager>:: - cat ( - queue_kernel_2<T,block_size,mem_manager>& item - ) - { - if (queue_size > 0) - { - T temp; - assign_zero_if_built_in_scalar_type(temp); - while (item.size() > 0) - { - item.dequeue(temp); - enqueue(temp); - } - } - else - { - in = item.in; - out = item.out; - out_pos = item.out_pos; - in_pos = item.in_pos; - - queue_size = item.queue_size; - item.queue_size = 0; - - // put the enumerator at the start - reset(); - } - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - T& queue_kernel_2<T,block_size,mem_manager>:: - current ( - ) - { - return out->item[out_pos]; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - const T& queue_kernel_2<T,block_size,mem_manager>:: - current ( - ) const - { - return out->item[out_pos]; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - void queue_kernel_2<T,block_size,mem_manager>:: - swap ( - queue_kernel_2<T,block_size,mem_manager>& item - ) - { - exchange(in,item.in); - exchange(out,item.out); - exchange(queue_size,item.queue_size); - exchange(in_pos,item.in_pos); - exchange(out_pos,item.out_pos); - exchange(current_element,item.current_element); - exchange(current_element_pos,item.current_element_pos); - exchange(at_start_,item.at_start_); - pool.swap(item.pool); - } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // enumerable function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - size_t queue_kernel_2<T,block_size,mem_manager>:: - size ( - ) const - { - return queue_size; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - bool queue_kernel_2<T,block_size,mem_manager>:: - at_start ( - ) const - { - return at_start_; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - void queue_kernel_2<T,block_size,mem_manager>:: - reset ( - ) const - { - at_start_ = true; - current_element = 0; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - bool queue_kernel_2<T,block_size,mem_manager>:: - current_element_valid ( - ) const - { - return (current_element != 0); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - const T& queue_kernel_2<T,block_size,mem_manager>:: - element ( - ) const - { - return current_element->item[current_element_pos]; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - T& queue_kernel_2<T,block_size,mem_manager>:: - element ( - ) - { - return current_element->item[current_element_pos]; - } - -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - bool queue_kernel_2<T,block_size,mem_manager>:: - move_next ( - ) const - { - if (at_start_) - { - at_start_ = false; - // if the queue is empty then there is nothing to do - if (queue_size == 0) - { - return false; - } - else - { - current_element = out; - current_element_pos = out_pos; - return true; - } - } - else if (current_element == 0) - { - return false; - } - else - { - ++current_element_pos; - // if we are at the last element then the enumeration has finished - if (current_element == in && current_element_pos == in_pos ) - { - current_element = 0; - return false; - } - else if (current_element_pos == block_size) - { - current_element_pos = 0; - current_element = current_element->next; - } - - return true; - } - } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // remover function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - void queue_kernel_2<T,block_size,mem_manager>:: - remove_any ( - T& item - ) - { - dequeue(item); - } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // private member function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename T, - unsigned long block_size, - typename mem_manager - > - void queue_kernel_2<T,block_size,mem_manager>:: - delete_nodes ( - node* start, - node* end - ) - { - node* temp; - while (start != end) - { - temp = start; - start = start->next; - pool.deallocate(temp); - } - pool.deallocate(start); - } - -// ---------------------------------------------------------------------------------------- - -} - -#endif // DLIB_QUEUE_KERNEl_2_ - diff --git a/ml/dlib/dlib/queue/queue_kernel_abstract.h b/ml/dlib/dlib/queue/queue_kernel_abstract.h deleted file mode 100644 index 4fd4c7dd1..000000000 --- a/ml/dlib/dlib/queue/queue_kernel_abstract.h +++ /dev/null @@ -1,196 +0,0 @@ -// Copyright (C) 2003 Davis E. King (davis@dlib.net) -// License: Boost Software License See LICENSE.txt for the full license. -#undef DLIB_QUEUE_KERNEl_ABSTRACT_ -#ifdef DLIB_QUEUE_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 queue : public enumerable<T>, - public remover<T> - { - - /*! - REQUIREMENTS ON T - T must be swappable by a global swap() - 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 current() functions do not invalidate pointers or - references to internal data. - All other functions have no such guarantee. - - INITIAL VALUE - size() == 0 - - ENUMERATION ORDER - The enumerator will iterate over the elements in the queue in the - same order they would be removed by repeated calls to dequeue(). - (e.g. current() would be the first element enumerated) - - WHAT THIS OBJECT REPRESENTS - This is a first in first out queue containing items of type T - - e.g. if the queue is {b,c,d,e} and then 'a' is enqueued - the queue becomes {a,b,c,d,e} and then calling dequeue takes e out - making the queue {a,b,c,d} - - Also note that unless specified otherwise, no member functions - of this object throw exceptions. - !*/ - - public: - - typedef T type; - typedef mem_manager mem_manager_type; - - queue ( - ); - /*! - ensures - - #*this is properly initialized - throws - - std::bad_alloc or any exception thrown by T's constructor - !*/ - - virtual ~queue ( - ); - /*! - 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 enqueue ( - T& item - ); - /*! - ensures - - item is now at the left end of #*this - - #item has an initial value for its type - - #size() == size() + 1 - - #at_start() == true - throws - - std::bad_alloc or any exception thrown by T's constructor - if enqueue() throws then it has no effect - !*/ - - void dequeue ( - T& item - ); - /*! - requires - - size() != 0 - ensures - - #size() == size() - 1 - - the far right element of *this has been removed and swapped - into #item - - #at_start() == true - !*/ - - void cat ( - queue& item - ); - /*! - ensures - - item has been concatenated onto the left end of *this. - i.e. item.current() is attached onto the left end of *this and - the left most element in item will also be the left most item - in #*this - - #size() == size() + item.size() - - #item has its initial value - - #at_start() == true - throws - - std::bad_alloc or any exception thrown by T's constructor - if cat() throws then the state of #item and *this is undefined - until clear() is successfully called on them. - !*/ - - T& current ( - ); - /*! - requires - - size() != 0 - ensures - - returns a const reference to the next element to be dequeued. - i.e. the right most element. - !*/ - - const T& current ( - ) const; - /*! - requires - - size() != 0 - ensures - - returns a non-const reference to the next element to be dequeued. - i.e. the right most element. - !*/ - - void swap ( - queue& item - ); - /*! - ensures - - swaps *this and item - !*/ - - private: - - // restricted functions - queue(queue&); // copy constructor - queue& operator=(queue&); // assignment operator - - }; - - template < - typename T, - typename mem_manager - > - inline void swap ( - queue<T,mem_manager>& a, - queue<T,mem_manager>& b - ) { a.swap(b); } - /*! - provides a global swap function - !*/ - - template < - typename T, - typename mem_manager - > - void deserialize ( - queue<T,mem_manager>& item, - std::istream& in - ); - /*! - provides deserialization support - !*/ -} - -#endif // DLIB_QUEUE_KERNEl_ABSTRACT_ - diff --git a/ml/dlib/dlib/queue/queue_kernel_c.h b/ml/dlib/dlib/queue/queue_kernel_c.h deleted file mode 100644 index 554c9aecd..000000000 --- a/ml/dlib/dlib/queue/queue_kernel_c.h +++ /dev/null @@ -1,187 +0,0 @@ -// Copyright (C) 2003 Davis E. King (davis@dlib.net) -// License: Boost Software License See LICENSE.txt for the full license. -#ifndef DLIB_QUEUE_KERNEl_C_ -#define DLIB_QUEUE_KERNEl_C_ - -#include "queue_kernel_abstract.h" -#include "../algs.h" -#include "../assert.h" - -namespace dlib -{ - - - template < - typename queue_base // is an implementation of queue_kernel_abstract.h - > - class queue_kernel_c : public queue_base - { - typedef typename queue_base::type T; - - public: - - void dequeue ( - T& item - ); - - T& current ( - ); - - const T& current ( - ) const; - - const T& element ( - ) const; - - T& element ( - ); - - void remove_any ( - T& item - ); - - }; - - template < - typename queue_base - > - inline void swap ( - queue_kernel_c<queue_base>& a, - queue_kernel_c<queue_base>& b - ) { a.swap(b); } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // member function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename queue_base - > - void queue_kernel_c<queue_base>:: - dequeue ( - T& item - ) - { - - // make sure requires clause is not broken - DLIB_CASSERT(this->size() != 0, - "\tvoid queue::dequeue" - << "\n\tsize of queue should not be zero" - << "\n\tthis: " << this - ); - - // call the real function - queue_base::dequeue(item); - - } - -// ---------------------------------------------------------------------------------------- - - template < - typename queue_base - > - const typename queue_base::type& queue_kernel_c<queue_base>:: - current ( - ) const - { - // make sure requires clause is not broken - DLIB_CASSERT(this->size() != 0, - "\tconst T& queue::current" - << "\n\tsize of queue should not be zero" - << "\n\tthis: " << this - ); - - // call the real function - return queue_base::current(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename queue_base - > - typename queue_base::type& queue_kernel_c<queue_base>:: - current ( - ) - { - // make sure requires clause is not broken - DLIB_CASSERT(this->size() != 0, - "\tT& queue::current" - << "\n\tsize of queue should not be zero" - << "\n\tthis: " << this - ); - - // call the real function - return queue_base::current(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename queue_base - > - const typename queue_base::type& queue_kernel_c<queue_base>:: - element ( - ) const - { - // make sure requires clause is not broken - DLIB_CASSERT(this->current_element_valid() == true, - "\tconst T& queue::element" - << "\n\tyou can't access the current element if it doesn't exist" - << "\n\tthis: " << this - ); - - // call the real function - return queue_base::element(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename queue_base - > - typename queue_base::type& queue_kernel_c<queue_base>:: - element ( - ) - { - // make sure requires clause is not broken - DLIB_CASSERT(this->current_element_valid() == true, - "\tT& queue::element" - << "\n\tyou can't access the current element if it doesn't exist" - << "\n\tthis: " << this - ); - - // call the real function - return queue_base::element(); - } - -// ---------------------------------------------------------------------------------------- - - template < - typename queue_base - > - void queue_kernel_c<queue_base>:: - remove_any ( - T& item - ) - { - // make sure requires clause is not broken - DLIB_CASSERT( (this->size() > 0), - "\tvoid queue::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 - queue_base::remove_any(item); - } - -// ---------------------------------------------------------------------------------------- - -} - -#endif // DLIB_QUEUE_KERNEl_C_ - diff --git a/ml/dlib/dlib/queue/queue_sort_1.h b/ml/dlib/dlib/queue/queue_sort_1.h deleted file mode 100644 index bc20dcb82..000000000 --- a/ml/dlib/dlib/queue/queue_sort_1.h +++ /dev/null @@ -1,165 +0,0 @@ -// Copyright (C) 2003 Davis E. King (davis@dlib.net) -// License: Boost Software License See LICENSE.txt for the full license. -#ifndef DLIB_QUEUE_SORt_1_ -#define DLIB_QUEUE_SORt_1_ - -#include "queue_sort_abstract.h" -#include "../algs.h" -#include <vector> -#include "../sort.h" - -namespace dlib -{ - - template < - typename queue_base - > - class queue_sort_1 : public queue_base - { - typedef typename queue_base::type T; - - public: - - /*! - This implementation uses the QuickSort algorithm and - when the quicksort depth goes too high it uses the dlib::qsort_array() - function on the data. - !*/ - - void sort ( - ); - - template <typename compare_type> - void sort ( - const compare_type& compare - ) - { - if (this->size() > 1) - { - sort_this_queue(*this,0,compare); - } - } - - private: - - template <typename compare_type> - void sort_this_queue ( - queue_base& queue, - long depth, - const compare_type& compare - ) - /*! - ensures - each element in the queue is < the element behind it according - to compare - !*/ - { - if (queue.size() <= 1) - { - // already sorted - } - else if (queue.size() <= 29) - { - T vect[29]; - const unsigned long size = queue.size(); - for (unsigned long i = 0; i < size; ++i) - { - queue.dequeue(vect[i]); - } - isort_array(vect,0,size-1,compare); - for (unsigned long i = 0; i < size; ++i) - { - queue.enqueue(vect[i]); - } - } - else if (depth > 50) - { - std::vector<T> vect(queue.size()); - for (unsigned long i = 0; i < vect.size(); ++i) - { - queue.dequeue(vect[i]); - } - hsort_array(vect,0,vect.size()-1,compare); - for (unsigned long i = 0; i < vect.size(); ++i) - { - queue.enqueue(vect[i]); - } - } - else - { - queue_base left, right; - T partition_element; - T temp; - // do this just to avoid a compiler warning - assign_zero_if_built_in_scalar_type(temp); - assign_zero_if_built_in_scalar_type(partition_element); - - queue.dequeue(partition_element); - - // partition queue into left and right - while (queue.size() > 0) - { - queue.dequeue(temp); - if (compare(temp , partition_element)) - { - left.enqueue(temp); - } - else - { - right.enqueue(temp); - } - } - - - long ratio; - if (left.size() > right.size()) - ratio = left.size()/(right.size()+1); // add 1 so we can't divide by zero - else - ratio = right.size()/(left.size()+1); - - sort_this_queue(left,ratio+depth,compare); - sort_this_queue(right,ratio+depth,compare); - - // combine the two queues - left.swap(queue); - queue.enqueue(partition_element); - queue.cat(right); - } - } - - - }; - - template < - typename queue_base - > - inline void swap ( - queue_sort_1<queue_base>& a, - queue_sort_1<queue_base>& b - ) { a.swap(b); } - -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - // member function definitions -// ---------------------------------------------------------------------------------------- -// ---------------------------------------------------------------------------------------- - - template < - typename queue_base - > - void queue_sort_1<queue_base>:: - sort ( - ) - { - if (this->size() > 1) - { - sort_this_queue(*this,0,std::less<typename queue_base::type>()); - } - } - -// ---------------------------------------------------------------------------------------- - -} - -#endif // DLIB_QUEUE_SORt_1_ - diff --git a/ml/dlib/dlib/queue/queue_sort_abstract.h b/ml/dlib/dlib/queue/queue_sort_abstract.h deleted file mode 100644 index 54c06f430..000000000 --- a/ml/dlib/dlib/queue/queue_sort_abstract.h +++ /dev/null @@ -1,74 +0,0 @@ -// Copyright (C) 2003 Davis E. King (davis@dlib.net) -// License: Boost Software License See LICENSE.txt for the full license. -#undef DLIB_QUEUE_SORt_ABSTRACT_ -#ifdef DLIB_QUEUE_SORt_ABSTRACT_ - - -#include "queue_kernel_abstract.h" - -namespace dlib -{ - - template < - typename queue_base - > - class queue_sort : public queue_base - { - - /*! - REQUIREMENTS ON QUEUE_BASE - - is an implementation of queue/queue_kernel_abstract.h - - queue_base::type must be a type with that is comparable via operator< - - POINTERS AND REFERENCES TO INTERNAL DATA - sort() may invalidate pointers and references to internal data. - - WHAT THIS EXTENSION DOES FOR QUEUE - This gives a queue 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 compare_type> - void sort ( - const compare_type& compare - ); - /*! - ensures - - for all elements in #*this the ith element is <= the i+1 element - - uses compare(a,b) as the < operator. So if compare(a,b) == true - then a comes before b in the resulting ordering. - - #at_start() == true - throws - - std::bad_alloc or any exception thrown by T's constructor - data may be lost if sort() throws - !*/ - }; - - template < - template queue_base - > - inline void swap ( - queue_sort<queue_base>& a, - queue_sort<queue_base>& b - ) { a.swap(b); } - /*! - provides a global swap function - !*/ - -} - -#endif // DLIB_QUEUE_SORt_ABSTRACT_ - |