Write a CircularBuffer
为什么要写一个 CircularBuffer :
- Template-able
CircularBuffer. - 可变和不可变容量(
recapacity)的 buffer. - 可以
forwardormove(改变有效数据范围) 的 buffer. - 可以
resize有效数据 size 的 buffer. - 可以连续访问未使用区域的 buffer (
restBeginandrestEnd).
例如可以用于:
- A copy less
ROS/navigation/costmap_2d/ cost mapimplementation!
实现
The CircularBuffer class brief:
/**
* Var capacity circular buffer.
* NOTE:
* - Like CircularQueue, but if full, then overwrite!
* - And like CircularQueue, but NOT use front and rear, but use next index
* and size(front index just for faster computing).
* - When use in multi-threads, should add lock or some other to sync.
* @tparam T data type.
* @sa CircularQueue
*/
template<typename T>
class CircularBuffer {
public:
/// The iterator type.
class Iterator;
/// The const iterator type.
class ConstIterator;
/// Box type: { boxMinXIdx, boxMinYIdx, boxWidth, boxHeight }
using Box = Eigen::Vector4i;
/**
* Ctor.
* @param capacity the buffer capacity, should >= 1.
* @throw std::logic_error when capacity invalid.
*/
CircularBuffer(int32_t capacity = 1, const T& initValue = T{});
/// Move ctor
CircularBuffer(CircularBuffer<T>&& rhs) noexcept;
/// Copy ctor
CircularBuffer(const CircularBuffer<T>& rhs) noexcept;
/// Dtor
~CircularBuffer() noexcept;
/// Move assign
CircularBuffer<T>& operator=(CircularBuffer<T>&& rhs) noexcept;
/// Copy assign
CircularBuffer<T>& operator=(const CircularBuffer<T>& rhs) noexcept;
/// @return internal alloced buffer capacity.
inline int32_t getAllocedCapacity() const noexcept;
/// @return buffer capacity.
inline int32_t capacity() const noexcept;
/**
* Set buffer capacity.
* @param capacity the new capacity to set, should > 0.
* @param initValue the initValue to set when reset capacity.
* @return true when success, otherwise false.
*/
bool recapacity(int32_t capacity, const T& initValue = T{}) noexcept;
/// Fit internal buffer's capacity to this->capacity().
void shrink_to_fit() noexcept;
/**
* Forward the buffer to frontIdx(real is nextIdx) by step.
* @param step the steps to forward, if < 0, then backward.
* @return forwarded buffer.
*/
inline CircularBuffer<T>& forward(int32_t step) noexcept;
/**
* Move box to right and down.
*
* 0 1 2 3
* 0. - - - > right (x, width)
* 1|
* 2|
* V
* down (y, height)
*
* @param box the box to move.
* @param width the full(capacity) buffer width (i.e. sizeX).
* @param height the full(capacity) buffer height (i.e. sizeY).
* @param xStep x increasing direction steps,
* if < 0 then to descending direction.
* @param yStep y increasing direction steps,
* if < 0 then to descending direction.
* @param initValue NOTE: if some regions will out of bounds then fill
* these regions with initValue first, then these regions with initValue
* will be moved circularly!
* @return the moved buffer.
* @sa
* - fillBox
* - fillBoxOutside
*/
CircularBuffer<T>& moveBox(
const Box& box,
int32_t width,
int32_t height,
int32_t xStep,
int32_t yStep,
const T& initValue = T{}) noexcept;
/**
* Resize in-use datas count.
* @note NO re-init.
* @param newCount the new count to resize, should >= 0.
* @return resized buffer.
* @throw std::logic_error when @a newCount invalid.
*/
CircularBuffer<T>& resize(int32_t newCount);
/**
* Resize in-use datas count.
* @param newCount the new count to resize, should >= 0.
* @param initValue set new or unused buffer to initValue.
* @return resized buffer.
* @throw std::logic_error when @a newCount invalid.
*/
CircularBuffer<T>& resize(int32_t newCount, const T& initValue);
/**
* Push a value.
* @param value to push.
*/
void push_back(T&& value) noexcept;
void push_back(const T& value) noexcept;
bool pop_back(const bool reset = false) noexcept;
bool pop_back(T& removed, const bool reset = false) noexcept;
bool pop_front(const bool reset = false) noexcept;
bool pop_front(T& removed, const bool reset = false) noexcept;
/**
* Get first data when buffer not empty.
* @return first data when buffer not empty.
* @throw std::logic_error when buffer empty.
*/
const T& front() const;
T& front();
/**
* Get last data when buffer not empty.
* @return last data when buffer not empty.
* @throw std::logic_error when buffer empty.
*/
const T& back() const;
T& back();
/// @return internal buffer.data().
inline T* data() noexcept;
/// @return internal buffer.data().
inline const T* data() const noexcept;
/// @return whether buffer empty.
inline bool empty() const noexcept;
/// @return whether buffer full.
inline bool full() const noexcept;
/// @return data size.
inline int32_t size() const noexcept;
/// Clear in-use datas count to 0.
inline CircularBuffer<T>& clear() noexcept;
/// Clear buffer and reset to initValue.
inline CircularBuffer<T>& clear(const T& initValue) noexcept;
/// Set count to capacity, NOTE: NOT set rest buffer region to a value.
inline CircularBuffer<T>& beFull() noexcept;
/// Set count to capacity, and set rest buffer region to a value.
inline CircularBuffer<T>& beFull(const T& value) noexcept;
/**
* Fill all (in-use and rest buffer regions) to gave value, but NOT
* change buffer's size.
*/
inline CircularBuffer<T>& fillNoResize(const T& value) noexcept;
/**
* Fill to gave starting from frontIdx + offset and count is @a count,
* but NOT change buffer size.
* @param offset the offset from frontIdx.
* @param count the data count to fill.
* @param value the value to fill.
*/
inline CircularBuffer<T>& fillNoResize(
const int64_t offset, const int32_t count, const T& value) noexcept;
/**
* Set count to capacity and set in-use and rest buffer regions to
* gave value.
*/
inline CircularBuffer<T>& fill(const T& value) noexcept;
/// Fill in-use buffer region to gave value.
inline CircularBuffer<T>& fillInUse(const T& value) noexcept;
/// Fill rest buffer region to gave value.
CircularBuffer<T>& fillRest(const T& value) noexcept;
/**
* Fill out of a inner box (sub-window) with gave value.
* @param box the box to move.
* @param width the full(capacity) buffer width (i.e. sizeX).
* @param height the full(capacity) buffer height (i.e. sizeY).
* @param value the value to fill.
* @return filled buffer.
* @note
* - Size of buffer should be width * height!
* - Parameters should valid and range!
*/
CircularBuffer<T>& fillBoxOutside(
const Box& box,
int32_t width,
int32_t height,
const T& value) noexcept;
CircularBuffer<T>& fillBox(
const Box& box, int32_t width, const T& value) noexcept;
/// Get buffer begin and end to watch all valid datas.
Iterator begin() noexcept;
Iterator end() noexcept;
ConstIterator begin() const noexcept;
ConstIterator end() const noexcept;
/// Get buffer's rest region begin and end.
Iterator restBegin() noexcept;
Iterator restEnd() noexcept;
/**
* Access buffer from front to last,
* @param idx data index, [0, size).
* @return the data of index when success.
* @throw std::logic_error when buffer empty when @a idx out of range.
*/
const T& operator[](const int64_t idx) const;
T& operator[](const int64_t idx);
/**
* Get ordered vector of the valid datas.
* @return ordered vector buffer of all valid datas.
* @note Result's size maybe < capacity.
*/
std::vector<T> getOrdered() const noexcept;
/// Check whether buffer equals @a datas
bool operator==(const std::initializer_list<T>& datas) const noexcept;
private:
/**
* Compute front data index, NOTE: buffer NOT empty, otherwise index
* invalid.
*/
inline int64_t computeFrontIdx() const noexcept;
std::vector<T> buffer;///< The buffer.
int32_t capa{ 1 };///< The buffer capacity, > 0.
int64_t nextIdx{ 0 };///< Next buffer data index.
/**
* Cache to fast related method, NOTE: sometimes invalid, need external
* empty check!
*/
int64_t frontIdx{ 0 };
int32_t count{ 0 };///< Current valid data count.
};
Detailed implementations see: