diff options
Diffstat (limited to 'ml/dlib/dlib/queue/queue_kernel_2.h')
| -rw-r--r-- | ml/dlib/dlib/queue/queue_kernel_2.h | 600 |
1 files changed, 600 insertions, 0 deletions
diff --git a/ml/dlib/dlib/queue/queue_kernel_2.h b/ml/dlib/dlib/queue/queue_kernel_2.h new file mode 100644 index 000000000..8e4536ae9 --- /dev/null +++ b/ml/dlib/dlib/queue/queue_kernel_2.h @@ -0,0 +1,600 @@ +// 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_ + |