You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
601 lines
15 KiB
C++
601 lines
15 KiB
C++
// 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_
|
|
|