libboxes
boxes is a set of specialised containers built on top of STL
All Classes Files Functions Pages Concepts
ring_buffer.hpp
Go to the documentation of this file.
1
11#ifndef __BOXES_RING_BUFFER_HPP__
12#define __BOXES_RING_BUFFER_HPP__
13
14#include "compiler.hpp"
15
16#include <array>
17#include <stdexcept>
18
19namespace boxes {
20
31template <typename T, std::size_t SizeV> class RingBuffer {
32public:
33 using value_type = T;
34 using reference = T &;
35 using const_reference = const T &;
36 using size_type = std::size_t;
37 using difference_type = std::ptrdiff_t;
38
39 static constexpr size_type Size = SizeV;
40
41 class iterator {
42 public:
43 using value_type = T;
44 using reference = T &;
45 using pointer = T *;
46 using difference_type = std::ptrdiff_t;
47 using iterator_category = std::random_access_iterator_tag;
48
49 iterator(RingBuffer<T, SizeV> *cnt, size_type pos) : cnt{cnt}, pos{pos} {}
50
51 iterator &operator++() {
52 if (pos != cnt->head) {
54 }
55 return *this;
56 }
57
58 iterator operator++(int) {
59 iterator tmp{*this};
60 ++(*this);
61 return tmp;
62 }
63
64 iterator &operator--() {
65 if (pos != cnt->tail) {
67 }
68 return *this;
69 }
70
71 iterator operator--(int) {
72 iterator tmp{*this};
73 --(*this);
74 return tmp;
75 }
76
77 reference operator*() { return cnt->buffer[pos]; }
78
79 pointer operator->() { return &cnt->buffer[pos]; }
80
81 bool operator==(const iterator &other) const {
82 return cnt == other.cnt && pos == other.pos;
83 }
84
85 bool operator!=(const iterator &other) const { return !(*this == other); }
86
87 private:
89 size_type pos;
90 };
91
92 RingBuffer() : head{0}, tail{0} {}
93
100 : head{other.head}, tail{other.tail}, buffer{other.buffer} {}
101
108 : head{other.head}, tail{other.tail}, buffer{std::move(other.buffer)} {
109 other.head = 0;
110 other.tail = 0;
111 }
112
120 if (this != &other) {
121 RingBuffer<T, SizeV> tmp{other};
122 swap(tmp);
123 }
124 return *this;
125 }
126
134 if (this != &other) {
135 RingBuffer<T, SizeV> tmp{std::move(other)};
136 swap(tmp);
137 }
138 return *this;
139 }
140
149 iterator begin() { return iterator(this, tail); }
150
156 iterator end() { return iterator(this, head); }
157
163 iterator cbegin() const { return begin(); }
164
170 iterator cend() const { return end(); }
171
177 bool empty() const BOXES_NOTHROW { return head == tail; }
178
184 bool full() const BOXES_NOTHROW { return nextHead() == tail; }
185
194 T &back() {
195 if (empty()) {
196 throw std::out_of_range("RingBuffer::front");
197 }
198 return buffer[prevHead()];
199 }
200
209 T &front() {
210 if (empty()) {
211 throw std::out_of_range("RingBuffer::back");
212 }
213 return buffer[tail];
214 }
215
221 const T &front() const { return const_cast<RingBuffer *>(this)->front(); }
222
228 const T &back() const { return const_cast<RingBuffer *>(this)->back(); }
229
243 T &operator[](size_type pos) { return buffer[(tail + pos) % BuffSize]; }
244
251 const T &operator[](size_type pos) const {
252 return const_cast<RingBuffer *>(this)->operator[](pos);
253 }
254
265 T &at(size_type pos) {
266 if (pos >= size()) {
267 throw std::out_of_range("RingBuffer::at");
268 }
269 return (*this)[pos];
270 }
271
278 const T &at(size_type pos) const {
279 return const_cast<RingBuffer *>(this)->at(pos);
280 }
281
290 bool operator==(const RingBuffer<T, SizeV> &other) const {
291 if (size() != other.size()) {
292 return false;
293 }
294
295 for (size_type i = 0; i < size(); ++i) {
296 if ((*this)[i] != other[i]) {
297 return false;
298 }
299 }
300
301 return true;
302 }
303
313 bool operator!=(const RingBuffer<T, SizeV> &other) const {
314 return !(*this == other);
315 }
316
325 std::swap(head, other.head);
326 std::swap(tail, other.tail);
327 buffer.swap(other.buffer);
328 }
329
340 template <typename Arg> bool push_back(Arg &&value) {
341 const size_type next = nextHead();
342 if (next != tail) {
343 buffer[head] = std::forward<Arg>(value);
344 head = next;
345 return true;
346 }
347 return false;
348 }
349
360 template <typename Arg> bool push_front(Arg &&value) {
361 const size_type next = prevTail();
362 if (next != head) {
363 tail = next;
364 buffer[tail] = std::forward<Arg>(value);
365 return true;
366 }
367 return false;
368 }
369
379 bool pop_back() {
380 if (empty()) {
381 return false;
382 }
383 head = prevHead();
384 buffer[head] = std::move(T{});
385 return true;
386 }
387
397 bool pop_front() {
398 if (empty()) {
399 return false;
400 }
401 buffer[tail] = std::move(T{});
402 tail = nextTail();
403 return true;
404 }
405
411 size_type size() const BOXES_NOTHROW {
412 if (head >= tail) {
413 return head - tail;
414 }
415 return BuffSize - tail + head;
416 }
417
424 void clear() {
425 while (pop_front()) {
426 }
427 head = 0;
428 tail = 0;
429 }
430
431protected:
432 static constexpr size_type BuffSize = Size + 1;
433 size_type head;
434 size_type tail;
435 std::array<T, BuffSize> buffer;
436
437 constexpr static size_type nextPos(size_type pos) BOXES_NOTHROW {
438 return (pos + 1) % BuffSize;
439 }
440
441 constexpr static size_type prevPos(size_type pos) BOXES_NOTHROW {
442 return (pos + BuffSize - 1) % BuffSize;
443 }
444
445 constexpr size_type prevHead() const BOXES_NOTHROW { return prevPos(head); }
446 constexpr size_type nextHead() const BOXES_NOTHROW { return nextPos(head); }
447 constexpr size_type nextTail() const BOXES_NOTHROW { return nextPos(tail); }
448 constexpr size_type prevTail() const BOXES_NOTHROW { return prevPos(tail); }
449};
450
451} // namespace boxes
452
453#endif // __BOXES_RING_BUFFER_HPP__
Implements a fixed-size double ended queue.
Definition: ring_buffer.hpp:31
bool pop_front()
Removes the first element from the RingBuffer.
RingBuffer< T, SizeV > & operator=(const RingBuffer< T, SizeV > &other)
Copy the contents of another RingBuffer into this one.
iterator cend() const
Returns a const iterator to the end of the RingBuffer.
void swap(RingBuffer< T, SizeV > &other)
Swaps the contents of this RingBuffer with another.
iterator cbegin() const
Returns a const iterator to the first element in the RingBuffer.
bool push_back(Arg &&value)
Inserts a new element at the end of the RingBuffer.
bool full() const BOXES_NOTHROW
Returns true if the RingBuffer is full.
const T & at(size_type pos) const
Const version of at
RingBuffer(const RingBuffer< T, SizeV > &other)
Copy constructs a RingBuffer from another.
Definition: ring_buffer.hpp:99
bool pop_back()
Removes the last element from the RingBuffer.
T & front()
Returns the first element in the queue.
void clear()
Clears the contents of the RingBuffer.
const T & back() const
Version of back that can be used with const RingBuffers.
bool operator==(const RingBuffer< T, SizeV > &other) const
Returns true if the contents of this RingBuffer are equal to another.
const T & operator[](size_type pos) const
Returns a const reference to the element at position pos
T & operator[](size_type pos)
Allows for random access to the elements in the RingBuffer.
RingBuffer(RingBuffer< T, SizeV > &&other)
Move constructs a RingBuffer from another.
T & back()
Returns the last element in the queue.
size_type size() const BOXES_NOTHROW
Returns the number of elements in the RingBuffer.
iterator end()
Returns an iterator to the end of the RingBuffer.
bool empty() const BOXES_NOTHROW
Returns true if the RingBuffer is empty.
iterator begin()
Returns an iterator to the first element in the RingBuffer.
RingBuffer< T, SizeV > & operator=(RingBuffer< T, SizeV > &&other)
Moves the contents of another RingBuffer into this one.
T & at(size_type pos)
Allows for random access to the elements in the RingBuffer.
bool operator!=(const RingBuffer< T, SizeV > &other) const
Returns true if the contents of this RingBuffer are not equal to another.
const T & front() const
Version of front that can be used with const RingBuffers.
bool push_front(Arg &&value)
Inserts a new element at the front of the RingBuffer.