Pothos  0.2.1-g9f04573d
The Pothos dataflow programming software suite
 All Classes Namespaces Files Functions Variables Typedefs Friends Macros
RingDeque.hpp
Go to the documentation of this file.
1 
11 #pragma once
12 #include <Pothos/Config.hpp>
13 #include <cstdlib> //size_t
14 #include <vector>
15 #include <cassert>
16 
17 namespace Pothos {
18 namespace Util {
19 
27 template <typename T>
28 class RingDeque
29 {
30 public:
32  RingDeque(void);
33 
35  RingDeque(const size_t capacity);
36 
38  const T &operator[](const size_t offset) const;
39 
41  T &operator[](const size_t offset);
42 
44  void push_front(const T &elem);
45 
47  void push_front(T &&elem);
48 
50  void pop_front(void);
51 
53  const T &front(void) const;
54 
56  T &front(void);
57 
59  void push_back(const T &elem);
60 
62  void push_back(T &&elem);
63 
65  void pop_back(void);
66 
68  const T &back(void) const;
69 
71  T &back(void);
72 
74  bool empty(void) const;
75 
77  bool full(void) const;
78 
80  size_t size(void) const;
81 
83  size_t capacity(void) const;
84 
86  void set_capacity(const size_t capacity);
87 
89  void clear(void);
90 
91 private:
92  size_t _frontIndex;
93  size_t _backIndex;
94  size_t _numElements;
95  std::vector<T> _container;
96 };
97 
98 template <typename T>
100  _frontIndex(0),
101  _backIndex(0),
102  _numElements(0),
103  _container(1)
104 {
105  return;
106 }
107 
108 template <typename T>
109 RingDeque<T>::RingDeque(const size_t capacity):
110  _frontIndex(0),
111  _backIndex(capacity-1),
112  _numElements(0),
113  _container(capacity)
114 {
115  assert(capacity > 0);
116 }
117 
118 template <typename T>
119 const T &RingDeque<T>::operator[](const size_t offset) const
120 {
121  return _container[(_frontIndex + offset) % _container.size()];
122 }
123 
124 template <typename T>
125 T &RingDeque<T>::operator[](const size_t offset)
126 {
127  return _container[(_frontIndex + offset) % _container.size()];
128 }
129 
130 template <typename T>
131 void RingDeque<T>::push_front(const T &elem)
132 {
133  assert(not this->full());
134  _frontIndex = size_t(_frontIndex + _container.size() - 1) % _container.size();
135  _container[_frontIndex] = elem;
136  _numElements++;
137 }
138 
139 template <typename T>
141 {
142  assert(not this->full());
143  _frontIndex = size_t(_frontIndex + _container.size() - 1) % _container.size();
144  _container[_frontIndex] = elem;
145  _numElements++;
146 }
147 
148 template <typename T>
150 {
151  assert(not this->empty());
152  assert(_frontIndex < _container.size());
153  T old; std::swap(_container[_frontIndex], old);
154  _frontIndex = size_t(_frontIndex + 1) % _container.size();
155  _numElements--;
156 }
157 
158 template <typename T>
159 const T &RingDeque<T>::front(void) const
160 {
161  assert(not this->empty());
162  assert(_frontIndex < _container.size());
163  return _container[_frontIndex];
164 }
165 
166 template <typename T>
168 {
169  assert(not this->empty());
170  assert(_frontIndex < _container.size());
171  return _container[_frontIndex];
172 }
173 
174 template <typename T>
175 void RingDeque<T>::push_back(const T &elem)
176 {
177  assert(not this->full());
178  _backIndex = size_t(_backIndex + 1) % _container.size();
179  _container[_backIndex] = elem;
180  _numElements++;
181 }
182 
183 template <typename T>
185 {
186  assert(not this->full());
187  _backIndex = size_t(_backIndex + 1) % _container.size();
188  _container[_backIndex] = elem;
189  _numElements++;
190 }
191 
192 template <typename T>
194 {
195  assert(not this->empty());
196  assert(_backIndex < _container.size());
197  T old; std::swap(_container[_backIndex], old);
198  _backIndex = size_t(_backIndex + _container.size() - 1) % _container.size();
199  _numElements--;
200 }
201 
202 template <typename T>
203 const T &RingDeque<T>::back(void) const
204 {
205  assert(not this->empty());
206  assert(_backIndex < _container.size());
207  return _container[_backIndex];
208 }
209 
210 template <typename T>
212 {
213  assert(not this->empty());
214  assert(_backIndex < _container.size());
215  return _container[_backIndex];
216 }
217 
218 template <typename T>
219 bool RingDeque<T>::empty(void) const
220 {
221  return _numElements == 0;
222 }
223 
224 template <typename T>
225 bool RingDeque<T>::full(void) const
226 {
227  return _numElements == _container.size();
228 }
229 
230 template <typename T>
231 size_t RingDeque<T>::size(void) const
232 {
233  return _numElements;
234 }
235 
236 template <typename T>
237 size_t RingDeque<T>::capacity(void) const
238 {
239  return _container.size();
240 }
241 
242 template <typename T>
243 void RingDeque<T>::set_capacity(const size_t capacity)
244 {
245  if (_numElements > capacity) return;
246  std::vector<T> _newContainer(capacity);
247  for (size_t i = 0; i < _numElements; i++)
248  {
249  _newContainer[i] = _container[(_frontIndex+i) % _container.size()];
250  }
251  _container = _newContainer;
252  _frontIndex = 0;
253  _backIndex = (_numElements + capacity - 1) % capacity;
254 }
255 
256 template <typename T>
258 {
259  while (not this->empty())
260  {
261  this->pop_front();
262  }
263 }
264 
265 } //namespace Util
266 } //namespace Pothos
const T & operator[](const size_t offset) const
Get a const ref at, where front == 0, back == size() - 1.
Definition: RingDeque.hpp:119
size_t capacity(void) const
How many elements can be stored?
Definition: RingDeque.hpp:237
void pop_back(void)
Pop and element from the back of the queue.
Definition: RingDeque.hpp:193
size_t size(void) const
How many elements are in the deque.
Definition: RingDeque.hpp:231
bool empty(void) const
Is the deque empty? – no elements.
Definition: RingDeque.hpp:219
void set_capacity(const size_t capacity)
Set the deque capacity if too small.
Definition: RingDeque.hpp:243
void clear(void)
Empty the contents of this queue.
Definition: RingDeque.hpp:257
RingDeque(void)
Construct a new ring deque.
Definition: RingDeque.hpp:99
void pop_front(void)
Pop and element from the front of the queue.
Definition: RingDeque.hpp:149
Definition: RingDeque.hpp:28
const T & front(void) const
Get a const reference to the front element.
Definition: RingDeque.hpp:159
bool full(void) const
Is the deque full? – num elements == capacity.
Definition: RingDeque.hpp:225
const T & back(void) const
Get a const reference to the back element.
Definition: RingDeque.hpp:203
void push_back(const T &elem)
Push an element onto the back of the queue.
Definition: RingDeque.hpp:175
void push_front(const T &elem)
Push an element onto the front of the queue.
Definition: RingDeque.hpp:131