-
Notifications
You must be signed in to change notification settings - Fork 24
/
internal_queue.h
123 lines (107 loc) · 5.78 KB
/
internal_queue.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// -*- mode: c++; tab-width: 4; indent-tabs-mode: t; c-file-style: "stroustrup"; -*-
// vi:set ts=4 sts=4 sw=4 noet cino+=(0 :
// Copyright 2010, 2011, The TPIE development team
//
// This file is part of TPIE.
//
// TPIE is free software: you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License as published by the
// Free Software Foundation, either version 3 of the License, or (at your
// option) any later version.
//
// TPIE is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
// License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with TPIE. If not, see <http://www.gnu.org/licenses/>
#ifndef __TPIE_INTERNAL_QUEUE_H__
#define __TPIE_INTERNAL_QUEUE_H__
///////////////////////////////////////////////////////////////////////////////
/// \file internal_queue.h
/// Generic internal queue with known memory requirements.
///////////////////////////////////////////////////////////////////////////////
#include <tpie/array.h>
#include <tpie/util.h>
#include <tpie/tpie_assert.h>
namespace tpie {
///////////////////////////////////////////////////////////////////////////////
/// \brief A generic internal circular queue
///
/// The queue supports a fixed number of unpopped elements between
/// calls to clear. The number of elements is given as an argument
/// to the constructor or to resize.
///
/// \tparam T The type of items stored in the queue
///////////////////////////////////////////////////////////////////////////////
template <typename T>
class internal_queue: public linear_memory_base<internal_queue<T> > {
array<T> m_elements;
size_t m_first, m_last;
public:
///////////////////////////////////////////////////////////////////////////
/// \copybrief linear_memory_structure_doc::memory_coefficient()
/// \copydetails linear_memory_structure_doc::memory_coefficient()
///////////////////////////////////////////////////////////////////////////
static double memory_coefficient() {return array<T>::memory_coefficient();}
///////////////////////////////////////////////////////////////////////////
/// \copybrief linear_memory_structure_doc::memory_overhead()
/// \copydetails linear_memory_structure_doc::memory_overhead()
///////////////////////////////////////////////////////////////////////////
static double memory_overhead() {return array<T>::memory_overhead() - sizeof(array<T>) + sizeof(internal_queue);}
///////////////////////////////////////////////////////////////////////////
/// \brief Construct a queue.
///
/// \param size The number of pushes supported between calls to clear and
/// resize.
///////////////////////////////////////////////////////////////////////////
internal_queue(size_t size=0): m_first(0), m_last(0) {m_elements.resize(size);}
///////////////////////////////////////////////////////////////////////////
/// \brief Resize the queue; all data is lost.
///
/// \param size The number of elements to contain.
///////////////////////////////////////////////////////////////////////////
void resize(size_t size=0) {m_elements.resize(size); m_first = m_last = 0;}
///////////////////////////////////////////////////////////////////////////
/// \brief Return the item that has been in the queue for the longest time.
///////////////////////////////////////////////////////////////////////////
const T & front() const {tp_assert(!empty(), "front() on empty queue"); return m_elements[m_first % m_elements.size()];}
///////////////////////////////////////////////////////////////////////////
/// \brief Return the last item pushed to the queue.
///////////////////////////////////////////////////////////////////////////
const T & back() const {return m_elements[(m_last-1) % m_elements.size()];}
///////////////////////////////////////////////////////////////////////////
/// \brief Add an element to the front of the queue.
///
/// \param val The element to add.
///////////////////////////////////////////////////////////////////////////
inline void push(T val){m_elements[m_last++ % m_elements.size()] = val;}
///////////////////////////////////////////////////////////////////////////
/// \brief Remove an element from the back of the queue.
///////////////////////////////////////////////////////////////////////////
inline void pop(){++m_first;}
///////////////////////////////////////////////////////////////////////////
/// \brief Check if the queue is empty.
/// \return true if the queue is empty, otherwise false.
///////////////////////////////////////////////////////////////////////////
inline bool empty() const {return m_first == m_last;}
///////////////////////////////////////////////////////////////////////////
/// \brief Check if the queue is empty.
/// \return true if the queue is empty, otherwise false.
///////////////////////////////////////////////////////////////////////////
inline bool full() const {return m_last - m_first == m_elements.size();}
///////////////////////////////////////////////////////////////////////////
/// \brief Return the number of elements in the queue.
/// \return The number of elements in the queue.
///////////////////////////////////////////////////////////////////////////
inline size_t size() const { return m_last - m_first;}
///////////////////////////////////////////////////////////////////////////
/// \brief Clear the queue of all elements.
/// After this call, the queue again supports the number of pushes passed
/// to the constructor or resize.
///////////////////////////////////////////////////////////////////////////
inline void clear(){m_first = m_last =0;}
}; // class internal_queue
} // namespace tpie
#endif //__TPIE_INTERNAL_QUEUE_H__