Files

585 lines
17 KiB
C++

/**
* @file include/ActivMiddleware/Misc/CircularBuffer.h
*
* @brief Growable circular buffer.
*/
#if (!defined ACTIV_MISC_CIRCULAR_BUFFER_H)
#define ACTIV_MISC_CIRCULAR_BUFFER_H
#include "ActivMiddleware/ActivMiddleware.h"
#include ACTIV_BOOST_INCLUDE(circular_buffer.hpp)
//! Activ namespace.
namespace Activ
{
/**
* @brief Circular buffer class. Similar to Boost::circular_buffer, except insertions will grow the buffer as required.
*
* See the Boost::circular_buffer documentation for methods not documented below.
*/
template<typename T, typename ALLOCATOR = std::allocator<T> >
class CircularBuffer
{
private:
typedef Boost::circular_buffer<T, ALLOCATOR> BoostCircularBuffer;
public:
typedef typename BoostCircularBuffer::value_type value_type;
typedef typename BoostCircularBuffer::pointer pointer;
typedef typename BoostCircularBuffer::const_pointer const_pointer;
typedef typename BoostCircularBuffer::reference reference;
typedef typename BoostCircularBuffer::const_reference const_reference;
typedef typename BoostCircularBuffer::size_type size_type;
typedef typename BoostCircularBuffer::difference_type difference_type;
typedef typename BoostCircularBuffer::allocator_type allocator_type;
typedef typename BoostCircularBuffer::const_iterator const_iterator;
typedef typename BoostCircularBuffer::iterator iterator;
typedef typename BoostCircularBuffer::const_reverse_iterator const_reverse_iterator;
typedef typename BoostCircularBuffer::reverse_iterator reverse_iterator;
typedef typename BoostCircularBuffer::array_range array_range;
typedef typename BoostCircularBuffer::const_array_range const_array_range;
typedef typename BoostCircularBuffer::param_value_type param_value_type;
typedef typename BoostCircularBuffer::return_value_type return_value_type;
typedef typename BoostCircularBuffer::capacity_type capacity_type;
explicit CircularBuffer(const allocator_type &alloc = allocator_type()) :
m_circularBuffer(alloc)
{
}
explicit CircularBuffer(capacity_type capacity, const allocator_type &alloc = allocator_type()) :
m_circularBuffer(capacity, alloc)
{
}
CircularBuffer(size_type n, const_reference item, const allocator_type &alloc = allocator_type()) :
m_circularBuffer(n, item, alloc)
{
}
CircularBuffer(const CircularBuffer<T, ALLOCATOR> &cb) :
m_circularBuffer(cb)
{
}
template <typename ITERATOR>
CircularBuffer(ITERATOR first, ITERATOR last, const allocator_type &alloc = allocator_type()) :
m_circularBuffer(first, last, alloc)
{
}
template <typename ITERATOR>
CircularBuffer(capacity_type capacity, ITERATOR first, ITERATOR last, const allocator_type &alloc = allocator_type()) :
m_circularBuffer(capacity, first, last, alloc)
{
}
iterator begin()
{
return m_circularBuffer.begin();
}
iterator end()
{
return m_circularBuffer.end();
}
const_iterator begin() const
{
return m_circularBuffer.begin();
}
const_iterator end() const
{
return m_circularBuffer.end();
}
reverse_iterator rbegin()
{
return m_circularBuffer.rbegin();
}
reverse_iterator rend()
{
return m_circularBuffer.rend();
}
const_reverse_iterator rbegin() const
{
return m_circularBuffer.rbegin();
}
const_reverse_iterator rend() const
{
return m_circularBuffer.rend();
}
reference operator[](size_type index)
{
return m_circularBuffer[index];
}
const_reference operator[](size_type index) const
{
return m_circularBuffer[index];
}
reference at(size_type index)
{
return m_circularBuffer.at(index);
}
const_reference at(size_type index) const
{
return m_circularBuffer.at(index);
}
reference front()
{
return m_circularBuffer.front();
}
reference back()
{
return m_circularBuffer.back();
}
const_reference front() const
{
return m_circularBuffer.front();
}
const_reference back() const
{
return m_circularBuffer.back();
}
array_range array_one()
{
return m_circularBuffer.array_one();
}
array_range array_two()
{
return m_circularBuffer.array_two();
}
const_array_range array_one() const
{
return m_circularBuffer.array_one();
}
const_array_range array_two() const
{
return m_circularBuffer.array_two();
}
pointer linearize()
{
return m_circularBuffer.linearize();
}
bool is_linearized() const
{
return m_circularBuffer.is_linearized();
}
void rotate(const_iterator newBegin)
{
return m_circularBuffer.rotate(newBegin);
}
size_type size() const
{
return m_circularBuffer.size();
}
size_type max_size() const
{
return m_circularBuffer.max_size();
}
bool empty() const
{
return m_circularBuffer.empty();
}
bool full() const
{
return m_circularBuffer.full();
}
size_type reserve() const
{
return m_circularBuffer.reserve();
}
capacity_type capacity() const
{
return m_circularBuffer.capacity();
}
void set_capacity(capacity_type newCapacity)
{
m_circularBuffer.set_capacity(newCapacity);
}
void resize(size_type newSize, const_reference item = value_type())
{
m_circularBuffer.resize(newSize, item);
}
void rset_capacity(capacity_type newCapacity)
{
m_circularBuffer.rset_capacity(newCapacity);
}
void rresize(size_type newSize, const_reference item = value_type())
{
m_circularBuffer.rresize(newSize, item);
}
CircularBuffer<T, ALLOCATOR> &operator=(const CircularBuffer<T, ALLOCATOR> &circularBuffer)
{
return m_circularBuffer.operator=(circularBuffer.m_circularBuffer);
}
void assign(size_type n, const_reference item)
{
m_circularBuffer.assign(n, item);
}
void assign(capacity_type capacity, size_type n, const_reference item)
{
return m_circularBuffer.assign(capacity, n, item);
}
template <class ITERATOR>
void assign(ITERATOR first, ITERATOR last)
{
return m_circularBuffer.assign(first, last);
}
template <typename ITERATOR>
void assign(capacity_type capacity, ITERATOR first, ITERATOR last)
{
return m_circularBuffer.assign(capacity, first, last);
}
void swap(CircularBuffer<T, ALLOCATOR> &circularBuffer)
{
m_circularBuffer.swap(circularBuffer.m_circularBuffer);
}
/**
* @brief Insert a new element at the end of the buffer.
*
* If the buffer is full, its capacity is increased such that it can hold a new item.
* Invalidates all iterators pointing to the buffer (except iterators equal to end())
* if the capacity is changed.
*
* @param item the item to append.
*
* @throw An allocation error if memory is exhausted (std::bad_alloc if the standard allocator is used).
* @throw Whatever T::T(const T&) throws.
* @throw Whatever T::operator=(const T&) throws.
*/
void push_back(const_reference item = value_type())
{
if (ACTIV_UNLIKELY(m_circularBuffer.full()))
InternalResize(m_circularBuffer.capacity() + 1);
m_circularBuffer.push_back(item);
}
/**
* @brief Insert a new element at the beginning of the buffer.
*
* If the buffer is full, its capacity is increased such that it can hold a new item.
* Invalidates all iterators pointing to the buffer (except iterators equal to end())
* if the capacity is changed.
*
* @param item the item to prepend.
*
* @throw An allocation error if memory is exhausted (std::bad_alloc if the standard allocator is used).
* @throw Whatever T::T(const T&) throws.
* @throw Whatever T::operator=(const T&) throws.
*/
void push_front(const_reference item = value_type())
{
if (ACTIV_UNLIKELY(m_circularBuffer.full()))
InternalResize(m_circularBuffer.capacity() + 1);
m_circularBuffer.push_front(item);
}
void pop_back()
{
return m_circularBuffer.pop_back();
}
void pop_front()
{
return m_circularBuffer.pop_front();
}
/**
* @brief Insert an element at the specified position.
*
* If the buffer is full, its capacity is increased such that it can hold a new item.
* Invalidates all iterators pointing to the buffer (except iterators equal to end())
* if the capacity is changed. Otherwise, invalidates iterators pointing to the elements before the
* insertion point (towards the beginning and excluding pos).
*
* @param pos an iterator specifying the position where the item will be inserted.
* @param item the item to insert.
*
* @throw An allocation error if memory is exhausted (std::bad_alloc if the standard allocator is used).
* @throw Whatever T::T(const T&) throws.
* @throw Whatever T::operator=(const T&) throws.
*/
iterator insert(iterator pos, const_reference item = value_type())
{
if (ACTIV_UNLIKELY(m_circularBuffer.full()))
InternalResize(m_circularBuffer.capacity() + 1);
return m_circularBuffer.insert(pos, item);
}
/**
* @brief Insert n copies of the item at the specified position.
*
* If the buffer is full, its capacity is increased such that it can hold the new items.
* Invalidates all iterators pointing to the buffer (except iterators equal to end())
* if the capacity is changed. Otherwise, invalidates iterators pointing to the elements at the
* insertion point (including pos) and iterators behind the insertion point
* (towards the end; except iterators equal to end()).
*
* @param pos an iterator specifying the position where the items will be inserted.
* @param n the number of items the to be inserted.
* @param item the element whose copies will be inserted.
*
* @throw An allocation error if memory is exhausted (std::bad_alloc if the standard allocator is used).
* @throw Whatever T::T(const T&) throws.
* @throw Whatever T::operator=(const T&) throws.
*/
void insert(iterator pos, size_type n, const_reference item)
{
const size_type currentCapacity = m_circularBuffer.capacity();
const size_type newSize = m_circularBuffer.size() + n;
if (ACTIV_UNLIKELY(newSize > currentCapacity))
InternalResize(newSize);
m_circularBuffer.insert(pos, n, item);
}
/**
* @brief Insert the range [first, last) at the specified position.
*
* If the buffer is full, its capacity is increased such that it can hold the new items.
* Invalidates all iterators pointing to the buffer (except iterators equal to end())
* if the capacity is changed. Otherwise, Invalidates iterators pointing to the elements at the
* insertion point (including pos) and iterators behind the insertion point
* (towards the end; except iterators equal to end()).
*
* @param pos an iterator specifying the position where the items will be inserted.
* @param first the beginning of the range to be inserted.
* @param last the end of the range to be inserted.
*
* @throw An allocation error if memory is exhausted (std::bad_alloc if the standard allocator is used).
* @throw Whatever T::T(const T&) throws.
* @throw Whatever T::operator=(const T&) throws.
*/
template <class ITERATOR>
void insert(iterator pos, ITERATOR first, ITERATOR last)
{
const size_type numberOfItemsToInsert = last - first;
const size_type currentCapacity = m_circularBuffer.capacity();
const size_type newSize = m_circularBuffer.size() + numberOfItemsToInsert;
if (ACTIV_UNLIKELY(newSize > currentCapacity))
InternalResize(newSize);
m_circularBuffer.insert(pos, first, last);
}
/**
* @brief Insert an element before the specified position.
*
* If the buffer is full, its capacity is increased such that it can hold a new item.
* Invalidates all iterators pointing to the buffer (except iterators equal to end())
* if the capacity is changed. Otherwise, invalidates iterators pointing to the elements before
* the insertion point (towards the beginning and excluding pos).
*
* @param pos an iterator specifying the position where the item will be inserted.
* @param item the item to insert.
*
* @throw An allocation error if memory is exhausted (std::bad_alloc if the standard allocator is used).
* @throw Whatever T::T(const T&) throws.
* @throw Whatever T::operator=(const T&) throws.
*/
iterator rinsert(iterator pos, const_reference item = value_type())
{
if (ACTIV_UNLIKELY(m_circularBuffer.full()))
InternalResize(m_circularBuffer.capacity() + 1);
return m_circularBuffer.rinsert(pos, item);
}
/**
* @brief Insert n copies of the item before the specified position.
*
* If the buffer is full, its capacity is increased such that it can hold the new items.
* Invalidates all iterators pointing to the buffer (except iterators equal to end())
* if the capacity is changed. Otherwise, tnvalidates iterators pointing to the elements before
* the insertion point (towards the beginning and excluding pos).
*
* @param pos an iterator specifying the position where the items will be inserted.
* @param n the number of items the to be inserted.
* @param item the element whose copies will be inserted.
*
* @throw An allocation error if memory is exhausted (std::bad_alloc if the standard allocator is used).
* @throw Whatever T::T(const T&) throws.
* @throw Whatever T::operator=(const T&) throws.
*/
void rinsert(iterator pos, size_type n, const_reference item)
{
const size_type currentCapacity = m_circularBuffer.capacity();
const size_type newSize = m_circularBuffer.size() + n;
if (ACTIV_UNLIKELY(newSize > currentCapacity))
InternalResize(newSize);
m_circularBuffer.rinsert(pos, n, item);
}
/**
* @brief Insert the range [first, last) before the specified position.
*
* If the buffer is full, its capacity is increased such that it can hold the new items.
* Invalidates all iterators pointing to the buffer (except iterators equal to end())
* if the capacity is changed. Otherwise, invalidates iterators pointing to the elements before
* the insertion point (towards the beginning and excluding pos).
*
* @param pos an iterator specifying the position where the items will be inserted.
* @param first the beginning of the range to be inserted.
* @param last the end of the range to be inserted.
*
* @throw An allocation error if memory is exhausted (std::bad_alloc if the standard allocator is used).
* @throw Whatever T::T(const T&) throws.
* @throw Whatever T::operator=(const T&) throws.
*/
template <class ITERATOR>
void rinsert(iterator pos, ITERATOR first, ITERATOR last)
{
const size_type numberOfItemsToInsert = last - first;
const size_type currentCapacity = m_circularBuffer.capacity();
const size_type newSize = m_circularBuffer.size() + numberOfItemsToInsert;
if (ACTIV_UNLIKELY(newSize > currentCapacity))
InternalResize(newSize);
m_circularBuffer.rinsert(pos, first, last);
}
iterator erase(iterator pos)
{
return m_circularBuffer.erase(pos);
}
iterator erase(iterator first, iterator last)
{
return m_circularBuffer.eraser(first, last);
}
iterator rerase(iterator pos)
{
return m_circularBuffer.rerase(pos);
}
iterator rerase(iterator first, iterator last)
{
return m_circularBuffer.rerase(first, last);
}
void clear()
{
m_circularBuffer.clear();
}
private:
void InternalResize(const size_type newCapacity)
{
const size_t currentCapacity = m_circularBuffer.capacity();
m_circularBuffer.set_capacity(GetMaximum<size_t>(newCapacity, (currentCapacity + (currentCapacity / 2))));
}
BoostCircularBuffer m_circularBuffer;
};
// ---------------------------------------------------------------------------------------------------------------------------------
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename T, typename ALLOCATOR>
inline bool operator==(const CircularBuffer<T, ALLOCATOR> &lhs, const CircularBuffer<T, ALLOCATOR> &rhs)
{
return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename T, typename ALLOCATOR>
inline bool operator!=(const CircularBuffer<T, ALLOCATOR> &lhs, const CircularBuffer<T, ALLOCATOR> &rhs)
{
return !(lhs == rhs);
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename T, typename ALLOCATOR>
inline bool operator<(const CircularBuffer<T, ALLOCATOR> &lhs, const CircularBuffer<T, ALLOCATOR> &rhs)
{
return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename T, typename ALLOCATOR>
inline bool operator>(const CircularBuffer<T, ALLOCATOR> &lhs, const CircularBuffer<T, ALLOCATOR> &rhs)
{
return rhs < lhs;
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename T, typename ALLOCATOR>
inline bool operator<=(const CircularBuffer<T, ALLOCATOR> &lhs, const CircularBuffer<T, ALLOCATOR> &rhs)
{
return !(rhs < lhs);
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename T, typename ALLOCATOR>
inline bool operator>=(const CircularBuffer<T, ALLOCATOR> &lhs, const CircularBuffer<T, ALLOCATOR> &rhs)
{
return !(lhs < rhs);
}
// ---------------------------------------------------------------------------------------------------------------------------------
template <typename T, typename ALLOCATOR>
inline void swap(CircularBuffer<T, ALLOCATOR> &lhs, CircularBuffer<T, ALLOCATOR> &rhs)
{
lhs.swap(rhs);
}
} // namespace Activ
#endif // (!defined ACTIV_MISC_CIRCULAR_BUFFER_H)