Program Listing for File RingBuffer.hpp

↰ Return to documentation for file (src/navtk/utils/RingBuffer.hpp)

#pragma once

#include <iterator>
#include <stdexcept>

#include <navtk/errors.hpp>

namespace navtk {
namespace utils {

template <typename T>
class RingBufferIterator;

template <typename T>
class RingBuffer {
public:
    using value_type = T;
    using iterator = RingBufferIterator<T>;
    using const_iterator = RingBufferIterator<const T>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    explicit RingBuffer(std::size_t capacity) : capacity(capacity) {
        if (capacity == 0) {
            throw std::invalid_argument("Buffer size cannot be 0.");
        }
        // Workaround for GCC bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87544
        // See issue navtk#895 for details.
        if (capacity >= std::size_t((std::numeric_limits<std::ptrdiff_t>::max)())) {
            throw std::invalid_argument(
                "Buffer size cannot be greater than or equal to "
                "std::size_t((std::numeric_limits<std::ptrdiff_t>::max)())");
        }
        buffer = new T[capacity];
    }

    ~RingBuffer() { delete[] buffer; }


    RingBuffer(const RingBuffer& other)
        : capacity(other.capacity), buffer(new T[other.capacity]()) {
        buffer_size = other.buffer_size;
        std::copy(other.begin(), other.end(), buffer);
    }

    RingBuffer& operator=(const RingBuffer& other) {
        if (this != &other) {
            // Free the existing resource.
            delete[] buffer;

            capacity    = other.capacity;
            buffer      = new T[capacity];
            buffer_size = other.buffer_size;
            std::copy(other.begin(), other.end(), buffer);
        }
        return *this;
    }

    RingBuffer(RingBuffer&& other) : capacity(0), buffer(nullptr) { *this = std::move(other); }

    RingBuffer& operator=(RingBuffer&& other) {
        if (this != &other) {
            // Free the existing resource.
            delete[] buffer;

            // Copy the data pointer and its length from the
            // source object.
            capacity    = other.capacity;
            buffer      = other.buffer;
            buffer_size = other.buffer_size;
            begin_index = other.begin_index;

            // Release the data pointer from the source object so that
            // the destructor does not free the memory multiple times.
            other.capacity    = 0;
            other.buffer      = nullptr;
            other.buffer_size = 0;
            other.begin_index = 0;
        }
        return *this;
    }

    std::size_t size() const { return buffer_size; }

    bool empty() const { return buffer_size == 0; }

    bool full() const { return buffer_size == capacity; }

    T& front() { return first_value(); }

    const T& front() const { return first_value(); }

    T& back() { return last_value(); }

    const T& back() const { return last_value(); }

    void pop_front() {
        if (buffer_size == 0) return;
        T t = std::move(first_value());
        (void)t;
        ++begin_index %= capacity;
        --buffer_size;
    }

    void pop_back() {
        if (buffer_size == 0) return;
        T t = std::move(last_value());
        (void)t;
        --buffer_size;
    }

    void push_front(const T& value) {
        if (buffer_size < capacity) {
            ++buffer_size;
        }
        begin_index   = (begin_index + capacity - 1) % capacity;
        first_value() = value;
    }

    void push_front(T&& value) {
        if (buffer_size < capacity) {
            ++buffer_size;
        }
        begin_index   = (begin_index + capacity - 1) % capacity;
        first_value() = std::move(value);
    }

    void push_back(const T& value) {
        if (buffer_size < capacity) {
            ++buffer_size;
        } else {
            ++begin_index %= capacity;
        }
        last_value() = value;
    }

    void push_back(T&& value) {
        if (buffer_size < capacity) {
            ++buffer_size;
        } else {
            ++begin_index %= capacity;
        }
        last_value() = std::move(value);
    }

    iterator erase(const_iterator first, const_iterator last) {
        auto number_of_elements_to_pop = last - first;
        iterator return_val            = end();
        if (first == cbegin()) {
            for (auto i = 0; i < number_of_elements_to_pop; i++) {
                pop_front();
                return_val = begin();
            }
        } else if (last == cend()) {
            for (auto i = 0; i < number_of_elements_to_pop; i++) {
                pop_back();
                return_val = end();
            }
        } else {
            log_or_throw("unimplemented operation erase from middle of RingBuffer");
        }
        return return_val;
    }

    iterator begin() { return iterator(buffer, begin_index, capacity); }

    const_iterator begin() const { return const_iterator(buffer, begin_index, capacity); }

    const_iterator cbegin() const { return begin(); }

    iterator end() { return iterator(buffer, begin_index + buffer_size, capacity); }

    const_iterator end() const {
        return const_iterator(buffer, begin_index + buffer_size, capacity);
    }

    const_iterator cend() const { return end(); }

    reverse_iterator rbegin() { return reverse_iterator(end()); }

    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }

    const_reverse_iterator crbegin() const { return rbegin(); }

    reverse_iterator rend() { return reverse_iterator(begin()); }

    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    const_reverse_iterator crend() const { return rend(); }

private:
    std::size_t capacity;
    T* buffer;
    std::size_t buffer_size = 0;
    std::size_t begin_index = 0;

    T& first_value() { return buffer[begin_index]; }
    const T& first_value() const { return buffer[begin_index]; }
    T& last_value() { return buffer[(begin_index + buffer_size - 1) % capacity]; }
    const T& last_value() const { return buffer[(begin_index + buffer_size - 1) % capacity]; }
};

template <typename T>
class RingBufferIterator {
public:
    using difference_type = ptrdiff_t;
    using value_type = T;
    using pointer = T*;
    using reference = T&;
    using iterator_category = std::random_access_iterator_tag;

    RingBufferIterator(T* buffer = new T[1](), std::size_t offset = 0, std::size_t capacity = 1)
        : capacity(capacity), buffer(buffer), offset(offset) {}

    bool operator==(const RingBufferIterator& rhs) {
        return rhs.buffer == buffer && rhs.offset == offset;
    }

    bool operator!=(const RingBufferIterator& rhs) { return !(*this == rhs); }

    RingBufferIterator& operator++() {
        ++offset;
        return *this;
    }

    RingBufferIterator operator++(int) {
        auto t = *this;
        ++offset;
        return t;
    }

    RingBufferIterator operator+(int amount) const {
        return RingBufferIterator(buffer, offset + amount, capacity);
    }

    RingBufferIterator operator-(int amount) const {
        return RingBufferIterator(buffer, offset - amount, capacity);
    }

    RingBufferIterator& operator--() {
        --offset;
        return *this;
    }

    RingBufferIterator operator--(int) {
        auto t = *this;
        --offset;
        return t;
    }

    std::ptrdiff_t operator-(RingBufferIterator const& rhs) const { return offset - rhs.offset; }

    RingBufferIterator& operator+=(int amount) {
        offset += amount;
        return *this;
    }

    RingBufferIterator& operator-=(int amount) {
        offset -= amount;
        return *this;
    }

    bool operator<(RingBufferIterator const& rhs) const { return offset < rhs.offset; }

    bool operator<=(RingBufferIterator const& rhs) const { return offset <= rhs.offset; }

    bool operator>(RingBufferIterator const& rhs) const { return offset > rhs.offset; }

    bool operator>=(RingBufferIterator const& rhs) const { return offset >= rhs.offset; }

    T& operator[](int index) const { return *(*this + index); }

    T& operator*() const { return buffer[offset % capacity]; }

    T* operator->() const { return &buffer[offset % capacity]; }

private:
    std::size_t capacity;
    T* buffer;
    std::size_t offset;
};

}  // namespace utils
}  // namespace navtk