Skip to content

Instantly share code, notes, and snippets.

@marcobergamin
Last active August 3, 2019 23:26
Show Gist options
  • Save marcobergamin/fa74a1274022d55c570127a13e6224b5 to your computer and use it in GitHub Desktop.
Save marcobergamin/fa74a1274022d55c570127a13e6224b5 to your computer and use it in GitHub Desktop.
Circular buffer with random access const_iterator
#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