Last active
August 3, 2019 23:26
-
-
Save marcobergamin/fa74a1274022d55c570127a13e6224b5 to your computer and use it in GitHub Desktop.
Circular buffer with random access const_iterator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iterator> | |
template<typename T, typename SIZE_TYPE = size_t> | |
class CircularBuffer | |
{ | |
public: | |
CircularBuffer(SIZE_TYPE capacity) | |
: _capacityPlusOne{ capacity + 1 } | |
, _buffer{ new T[_capacityPlusOne] } | |
, _head{ 0 } | |
, _tail{ 0 } | |
{} | |
~CircularBuffer() | |
{ | |
delete[] _buffer; | |
} | |
inline bool push(T elem) noexcept | |
{ | |
const auto nextHead = (_head + 1) % _capacityPlusOne; | |
if (nextHead == _tail) | |
{ | |
return false; | |
} | |
else | |
{ | |
_buffer[nextHead] = elem; | |
_head = nextHead; | |
return true; | |
} | |
} | |
inline bool pop(T &elem) noexcept | |
{ | |
if (_head == _tail) | |
return false; | |
_tail = (_tail + 1) % _capacityPlusOne; | |
elem = _buffer[_tail]; | |
return true; | |
} | |
inline SIZE_TYPE get_capacity() const | |
{ | |
return _capacityPlusOne - 1; | |
} | |
inline size_t get_size() const noexcept | |
{ | |
SIZE_TYPE size{ 0 }; | |
if (_head >= _tail) | |
size = _head - _tail; | |
else | |
size = _capacityPlusOne - _tail + _head; | |
return size; | |
} | |
private: | |
const SIZE_TYPE _capacityPlusOne; | |
T *_buffer; | |
SIZE_TYPE _head; | |
SIZE_TYPE _tail; | |
public: | |
class const_iterator | |
{ | |
public: | |
using iterator_category = std::random_access_iterator_tag; | |
using value_type = T; | |
using difference_type = SIZE_TYPE; | |
using pointer = const T *; | |
using reference = const T &; | |
const_iterator(const const_iterator &it) | |
: _index{ it._index } | |
, _buf{ it._buf } | |
, _capacityPlusOne{ it._capacityPlusOne } | |
{ | |
} | |
const_iterator(SIZE_TYPE index, const T *buf, SIZE_TYPE capacityPlusOne) | |
: _index{ index } | |
, _buf{ buf } | |
, _capacityPlusOne{ capacityPlusOne } | |
{ | |
} | |
bool operator==(const const_iterator &rhs) const | |
{ | |
return _index == rhs._index; | |
} | |
bool operator!=(const const_iterator &rhs) const | |
{ | |
return _index != rhs._index; | |
} | |
// post-increment | |
const_iterator operator++(int) | |
{ | |
const_iterator it(_index, _buf, _capacityPlusOne); | |
_index = (_index + 1) % _capacityPlusOne; | |
return it; | |
} | |
// pre-increment | |
const_iterator & operator++() | |
{ | |
_index = (_index + 1) % _capacityPlusOne; | |
return *this; | |
} | |
// post-decrement | |
const_iterator operator--(int) | |
{ | |
const_iterator it(_index, _buf, _capacityPlusOne); | |
_index = (_index - 1 + _capacityPlusOne) % _capacityPlusOne; | |
return it; | |
} | |
// pre-decrement | |
const_iterator & operator--() | |
{ | |
_index = (_index - 1 + _capacityPlusOne) % _capacityPlusOne; | |
return *this; | |
} | |
// dereference | |
const value_type & operator*() const | |
{ | |
return _buf[_index]; | |
} | |
// distance | |
difference_type operator-(const const_iterator & rhs) const | |
{ | |
difference_type distance; | |
if (_index >= rhs._index) | |
distance = _index - rhs._index; | |
else | |
distance = _capacityPlusOne - rhs._index + _index; | |
return distance; | |
} | |
// random access operator [] | |
const value_type &operator[](difference_type i) const | |
{ | |
return _buf[(_index + i + _capacityPlusOne) % _capacityPlusOne]; | |
} | |
private: | |
SIZE_TYPE _index; | |
const T *const _buf; | |
const SIZE_TYPE _capacityPlusOne; | |
}; | |
const_iterator cbegin() const | |
{ | |
return const_iterator((_tail + 1) % _capacityPlusOne, _buffer, _capacityPlusOne); | |
} | |
const_iterator cend() const | |
{ | |
return const_iterator((_head + 1) % _capacityPlusOne, _buffer, _capacityPlusOne); | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment