Write a CircularBuffer

为什么要写一个 CircularBuffer :

• Template-able CircularBuffer.
• 可变和不可变容量(recapacity)的 buffer.
• 可以 forward or move (改变有效数据范围) 的 buffer.
• 可以 resize 有效数据 size 的 buffer.
• 可以连续访问未使用区域的 buffer (restBegin and restEnd).

例如可以用于:

• A copy less ROS/navigation/costmap_2d/ cost map implementation!

---

实现

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:

• circularbuffer.hpp
• test/base/circularbuffer.cpp
• FastCircularBuffer
• Fixed size buffer: CircularArrayBuffer