Pothos  0.4.0-gd11861cd
The Pothos dataflow programming software suite
 All Classes Namespaces Files Functions Variables Typedefs Friends Macros Pages
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 <utility> //forward
15 #include <vector>
16 #include <cassert>
17 
18 namespace Pothos {
19 namespace Util {
20 
28 template <typename T>
29 class RingDeque
30 {
31 public:
33  RingDeque(void);
34 
36  RingDeque(const size_t capacity);
37 
39  const T &operator[](const size_t offset) const;
40 
42  T &operator[](const size_t offset);
43 
45  template <typename U>
46  void push_front(U &&elem);
47 
49  template <typename... Args>
50  T &emplace_front(Args&&... args);
51 
53  void pop_front(void);
54 
56  const T &front(void) const;
57 
59  T &front(void);
60 
62  template <typename U>
63  void push_back(U &&elem);
64 
66  template <typename... Args>
67  T &emplace_back(Args&&... args);
68 
70  void pop_back(void);
71 
73  const T &back(void) const;
74 
76  T &back(void);
77 
79  bool empty(void) const;
80 
82  bool full(void) const;
83 
85  size_t size(void) const;
86 
88  size_t capacity(void) const;
89 
91  void set_capacity(const size_t capacity);
92 
94  void clear(void);
95 
96 private:
97  size_t _frontIndex;
98  size_t _backIndex;
99  size_t _numElements;
100  std::vector<T> _container;
101 };
102 
103 template <typename T>
105  _frontIndex(0),
106  _backIndex(0),
107  _numElements(0),
108  _container(1)
109 {
110  return;
111 }
112 
113 template <typename T>
114 RingDeque<T>::RingDeque(const size_t capacity):
115  _frontIndex(0),
116  _backIndex(capacity-1),
117  _numElements(0),
118  _container(capacity)
119 {
120  assert(capacity > 0);
121 }
122 
123 template <typename T>
124 const T &RingDeque<T>::operator[](const size_t offset) const
125 {
126  return _container[(_frontIndex + offset) % _container.size()];
127 }
128 
129 template <typename T>
130 T &RingDeque<T>::operator[](const size_t offset)
131 {
132  return _container[(_frontIndex + offset) % _container.size()];
133 }
134 
135 template <typename T>
136 template <typename U>
138 {
139  assert(not this->full());
140  _frontIndex = size_t(_frontIndex + _container.size() - 1) % _container.size();
141  _container[_frontIndex] = std::forward<U>(elem);
142  _numElements++;
143 }
144 
145 template <typename T>
146 template <typename... Args>
147 T &RingDeque<T>::emplace_front(Args&&... args)
148 {
149  assert(not this->full());
150  _frontIndex = size_t(_frontIndex + _container.size() - 1) % _container.size();
151  _container[_frontIndex] = T(std::forward<Args>(args)...);
152  _numElements++;
153  return _container[_frontIndex];
154 }
155 
156 template <typename T>
158 {
159  assert(not this->empty());
160  assert(_frontIndex < _container.size());
161  _container[_frontIndex] = T();
162  _frontIndex = size_t(_frontIndex + 1) % _container.size();
163  _numElements--;
164 }
165 
166 template <typename T>
167 const T &RingDeque<T>::front(void) const
168 {
169  assert(not this->empty());
170  assert(_frontIndex < _container.size());
171  return _container[_frontIndex];
172 }
173 
174 template <typename T>
176 {
177  assert(not this->empty());
178  assert(_frontIndex < _container.size());
179  return _container[_frontIndex];
180 }
181 
182 template <typename T>
183 template <typename U>
185 {
186  assert(not this->full());
187  _backIndex = size_t(_backIndex + 1) % _container.size();
188  _container[_backIndex] = std::forward<U>(elem);
189  _numElements++;
190 }
191 
192 template <typename T>
193 template <typename... Args>
194 T &RingDeque<T>::emplace_back(Args&&... args)
195 {
196  assert(not this->full());
197  _backIndex = size_t(_backIndex + 1) % _container.size();
198  _container[_backIndex] = T(std::forward<Args>(args)...);
199  _numElements++;
200  return _container[_backIndex];
201 }
202 
203 template <typename T>
205 {
206  assert(not this->empty());
207  assert(_backIndex < _container.size());
208  _container[_backIndex] = T();
209  _backIndex = size_t(_backIndex + _container.size() - 1) % _container.size();
210  _numElements--;
211 }
212 
213 template <typename T>
214 const T &RingDeque<T>::back(void) const
215 {
216  assert(not this->empty());
217  assert(_backIndex < _container.size());
218  return _container[_backIndex];
219 }
220 
221 template <typename T>
223 {
224  assert(not this->empty());
225  assert(_backIndex < _container.size());
226  return _container[_backIndex];
227 }
228 
229 template <typename T>
230 bool RingDeque<T>::empty(void) const
231 {
232  return _numElements == 0;
233 }
234 
235 template <typename T>
236 bool RingDeque<T>::full(void) const
237 {
238  return _numElements == _container.size();
239 }
240 
241 template <typename T>
242 size_t RingDeque<T>::size(void) const
243 {
244  return _numElements;
245 }
246 
247 template <typename T>
248 size_t RingDeque<T>::capacity(void) const
249 {
250  return _container.size();
251 }
252 
253 template <typename T>
254 void RingDeque<T>::set_capacity(const size_t capacity)
255 {
256  if (_numElements > capacity) return;
257  std::vector<T> _newContainer(capacity);
258  for (size_t i = 0; i < _numElements; i++)
259  {
260  _newContainer[i] = _container[(_frontIndex+i) % _container.size()];
261  }
262  _container = _newContainer;
263  _frontIndex = 0;
264  _backIndex = (_numElements + capacity - 1) % capacity;
265 }
266 
267 template <typename T>
269 {
270  while (not this->empty())
271  {
272  this->pop_front();
273  }
274 }
275 
276 } //namespace Util
277 } //namespace Pothos
const T & operator[](const size_t offset) const
Get a const ref at, where front == 0, back == size() - 1.
Definition: RingDeque.hpp:124
size_t capacity(void) const
How many elements can be stored?
Definition: RingDeque.hpp:248
void pop_back(void)
Pop and element from the back of the queue.
Definition: RingDeque.hpp:204
T & emplace_front(Args &&...args)
Emplace an element onto the front of the queue.
Definition: RingDeque.hpp:147
size_t size(void) const
How many elements are in the deque.
Definition: RingDeque.hpp:242
bool empty(void) const
Is the deque empty? – no elements.
Definition: RingDeque.hpp:230
void push_front(U &&elem)
Push an element onto the front of the queue.
Definition: RingDeque.hpp:137
void set_capacity(const size_t capacity)
Set the deque capacity if too small.
Definition: RingDeque.hpp:254
void clear(void)
Empty the contents of this queue.
Definition: RingDeque.hpp:268
RingDeque(void)
Construct a new ring deque.
Definition: RingDeque.hpp:104
void pop_front(void)
Pop and element from the front of the queue.
Definition: RingDeque.hpp:157
Definition: RingDeque.hpp:29
T & emplace_back(Args &&...args)
Emplace an element onto the back of the queue.
Definition: RingDeque.hpp:194
const T & front(void) const
Get a const reference to the front element.
Definition: RingDeque.hpp:167
bool full(void) const
Is the deque full? – num elements == capacity.
Definition: RingDeque.hpp:236
const T & back(void) const
Get a const reference to the back element.
Definition: RingDeque.hpp:214
void push_back(U &&elem)
Push an element onto the back of the queue.
Definition: RingDeque.hpp:184