SlidingBuffer.h

Go to the documentation of this file.

 
#ifndef GUL14_SLIDINGBUFFER_H_
#define GUL14_SLIDINGBUFFER_H_
 
#include <algorithm>
#include <array>
#include <ostream>
#include <vector>
#include "gul14/cat.h"
#include "gul14/internal.h"
 
namespace gul14 {
 
enum class ShrinkBehavior { keep_front_elements, keep_back_elements };
 
template<typename ElementT, std::size_t fixed_capacity = 0u,
    typename Container = typename std::conditional_t<(fixed_capacity >= 1u),
        std::array<ElementT, fixed_capacity>,
        std::vector<ElementT>>
    >
class SlidingBuffer {
public:
    template <typename>
    class SlidingBufferIterator;
    using container_type = Container;
    using value_type = ElementT;
    using size_type = typename Container::size_type;
    using difference_type = typename Container::difference_type;
    using reference = typename Container::reference;
    using const_reference = typename Container::const_reference;
    using pointer = typename Container::pointer;
    using const_pointer = typename Container::const_pointer;
    using iterator = SlidingBufferIterator<SlidingBuffer<ElementT, fixed_capacity, Container>*>;
    using const_iterator = SlidingBufferIterator<SlidingBuffer<ElementT, fixed_capacity, Container> const*>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
    SlidingBuffer() = default;
    SlidingBuffer(SlidingBuffer const&) = default;
    SlidingBuffer(SlidingBuffer&&) noexcept(std::is_nothrow_move_constructible<container_type>::value) = default;
    SlidingBuffer& operator=(SlidingBuffer const&) = default;
    SlidingBuffer& operator=(SlidingBuffer &&) noexcept(std::is_nothrow_move_assignable<container_type>::value) = default;
    virtual ~SlidingBuffer() = default;
 
    SlidingBuffer(size_type count) : storage_(count) {}
 
protected:
 
    size_type idx_begin_{ 0u };
    size_type idx_end_{ 0u };
    bool full_{ false };
    Container storage_{ };
 
public:
    auto pop_back() -> void
    {
        decrease_idx(idx_end_);
        full_ = false;
    }
 
    auto pop_front() -> void
    {
        increase_idx(idx_begin_);
        full_ = false;
    }
 
    auto push_back(const value_type& in) -> void
    {
        storage_[idx_end_] = in;
 
        increase_idx(idx_end_);
        if (full_)
            increase_idx(idx_begin_);
        else if (idx_end_ == idx_begin_)
            full_ = true;
    }
 
    auto push_back(value_type&& in) -> void
    {
        storage_[idx_end_] = std::move(in);
 
        increase_idx(idx_end_);
        if (full_)
            increase_idx(idx_begin_);
        else if (idx_end_ == idx_begin_)
            full_ = true;
    }
 
    auto push_front(const value_type& in) -> void
    {
        decrease_idx(idx_begin_);
 
        if (full_)
            decrease_idx(idx_end_);
        else if (idx_end_ == idx_begin_)
            full_ = true;
 
        storage_[idx_begin_] = in;
    }
 
    auto push_front(value_type&& in) -> void
    {
        decrease_idx(idx_begin_);
 
        if (full_)
            decrease_idx(idx_end_);
        else if (idx_end_ == idx_begin_)
            full_ = true;
 
        storage_[idx_begin_] = std::move(in);
    }
 
    auto operator[](size_type idx) noexcept -> reference
    {
        idx += idx_begin_;
 
        return (idx >= capacity()) ? storage_[idx - capacity()] : storage_[idx];
    }
 
    auto operator[](size_type idx) const noexcept -> const_reference
    {
        idx += idx_begin_;
 
        return (idx >= capacity()) ? storage_[idx - capacity()] : storage_[idx];
    }
 
    auto at(const size_type idx) noexcept(false) -> reference
    {
        auto const s = size();
        if (idx >= s) {
            throw std::out_of_range(gul14::cat("SlidingBuffer::", __func__,
                ": idx (which is ", idx, ") >= this->size() (which is ", s, ")"));
        }
        return operator[](idx);
    }
 
    auto at(const size_type idx) const noexcept(false) -> const_reference
    {
        auto const s = size();
        if (idx >= s) {
            throw std::out_of_range(gul14::cat("SlidingBuffer::", __func__,
                ": idx (which is ", idx, ") >= this->size() (which is ", s, ")"));
        }
        return operator[](idx);
    }
 
    auto front() noexcept -> reference
    {
        return storage_[idx_begin_];
    }
 
    auto front() const noexcept -> const_reference
    {
        return storage_[idx_begin_];
    }
 
    auto back() noexcept -> reference
    {
        if (idx_end_ == 0)
            return storage_[capacity() - 1];
        else
            return storage_[idx_end_ - 1];
    }
 
    auto back() const noexcept -> const_reference
    {
        if (idx_end_ == 0)
            return storage_[capacity() - 1];
        else
            return storage_[idx_end_ - 1];
    }
 
    auto size() const noexcept -> size_type
    {
        if (full_)
            return capacity();
 
        if (idx_end_ >= idx_begin_)
            return idx_end_ - idx_begin_;
        else
            return idx_end_ + capacity() - idx_begin_;
    }
 
    auto constexpr capacity() const noexcept -> size_type
    {
        return (fixed_capacity > 0) ? fixed_capacity : storage_.size();
    }
 
    auto filled() const noexcept -> bool
    {
        return full_;
    }
 
    auto clear() -> void
    {
        full_ = false;
        idx_begin_ = 0u;
        idx_end_ = 0u;
 
        // Fill with new empty elements to possibly trigger RAII in the elements
        std::fill(storage_.begin(), storage_.end(), value_type{});
    }
 
    auto resize(size_type new_capacity, ShrinkBehavior shrink_behavior = ShrinkBehavior::keep_front_elements) -> void
    {
        static_assert(fixed_capacity == 0u,
            "resize() only possible if the underlying container is resizable");
        change_capacity(new_capacity, shrink_behavior);
    }
 
    auto reserve(size_type size, ShrinkBehavior shrink_behavior = ShrinkBehavior::keep_front_elements) -> void
    {
        static_assert(fixed_capacity == 0u,
            "reserve() only possible if the underlying container is resizable");
        change_capacity(size, shrink_behavior);
    }
 
    auto empty() const noexcept -> bool
    {
        return (not full_) and (idx_begin_ == idx_end_);
    }
 
    auto friend operator<< (std::ostream& s,
            const SlidingBuffer<value_type, fixed_capacity, container_type>& buffer) -> std::ostream&
    {
        auto const size = buffer.size();
        // We can not use range-for here, because of SlidingBufferExposed<>'s un-wrapped iterators
        for (auto i = size_type{ 0 }; i < size; ++i)
            s << buffer[i] << "  ";
        return s << '\n';
    }
 
    template <typename BufferPointer>
    class SlidingBufferIterator
    {
    protected:
        size_type position_{ 0 };
    private:
        BufferPointer buffer_;
 
    public:
        // Set of 5 member types that are needed by std::iterator_traits:
 
        using iterator_category = std::random_access_iterator_tag;
        using value_type = ElementT;
        using difference_type = std::ptrdiff_t;
        using pointer = value_type*;
        using reference = value_type&;
 
        explicit SlidingBufferIterator(BufferPointer buff, size_type num = 0) noexcept
            : position_{ num }
            , buffer_{ buff }
        {
        }
 
        auto operator++() noexcept -> SlidingBufferIterator&
        {
            ++position_;
            return *this;
        }
 
        auto operator++(int) noexcept -> SlidingBufferIterator
        {
            auto previous = *this;
            ++(*this);
            return previous;
        }
 
        auto operator+=(difference_type d) noexcept -> SlidingBufferIterator&
        {
            position_ += d;
            return *this;
        }
 
        friend auto
        operator+(const SlidingBufferIterator &it, difference_type d) noexcept
        -> SlidingBufferIterator
        {
            return SlidingBufferIterator{ it.buffer_, it.position_ + d };
        }
 
        friend auto
        operator+(difference_type d, const SlidingBufferIterator &it) noexcept
        -> SlidingBufferIterator
        {
            return SlidingBufferIterator{ it.buffer_, it.position_ + d };
        }
 
        auto operator--() noexcept -> SlidingBufferIterator&
        {
            --position_;
            return *this;
        }
 
        auto operator--(int) noexcept -> SlidingBufferIterator
        {
            auto previous = *this;
            --(*this);
            return previous;
        }
 
        auto operator-=(difference_type d) noexcept -> SlidingBufferIterator&
        {
            position_ -= d;
            return *this;
        }
 
        friend auto
        operator-(const SlidingBufferIterator &it, difference_type d) noexcept
        -> SlidingBufferIterator
        {
            return SlidingBufferIterator{ it.buffer_, it.position_ - d };
        }
 
        friend auto
        operator-(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept
        -> difference_type
        {
            return lhs.position_ - rhs.position_;
        }
 
        auto operator*() const noexcept -> typename std::conditional_t<
            std::is_const<std::remove_pointer_t<BufferPointer>>::value,
            const_reference, reference>
        {
            return (*buffer_)[position_];
        }
 
        auto operator->() const noexcept -> typename std::conditional_t<
            std::is_const<std::remove_pointer_t<BufferPointer>>::value,
            const_pointer, pointer>
        {
            return &(*buffer_)[position_];
        }
 
        auto operator[](difference_type offs) noexcept -> typename std::conditional_t<
            std::is_const<std::remove_pointer_t<BufferPointer>>::value,
            const_reference, reference>
        {
            return *(*this + offs);
        }
 
        friend auto
        operator==(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept
        -> bool
        {
            return lhs.position_ == rhs.position_;
        }
 
        friend auto
        operator!=(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept
        -> bool
        {
            return not(lhs == rhs);
        }
 
        friend auto
        operator>(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept
        -> bool
        {
            return lhs.position_ > rhs.position_;
        }
 
        friend auto
        operator<(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept
        -> bool
        {
            return lhs.position_ < rhs.position_;
        }
 
        friend auto
        operator>=(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept
        -> bool
        {
            return lhs.position_ >= rhs.position_;
        }
 
        friend auto
        operator<=(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept
        -> bool
        {
            return lhs.position_ <= rhs.position_;
        }
    };
 
    auto begin() noexcept -> iterator
    {
        return iterator{ this, 0 };
    }
 
    auto begin() const noexcept -> const_iterator
    {
        return const_iterator{ this, 0 };
    }
 
    auto rbegin() noexcept -> reverse_iterator
    {
        return std::make_reverse_iterator(end());
    }
 
    auto end() noexcept -> iterator
    {
        return iterator{ this, size() };
    }
 
    auto end() const noexcept -> const_iterator
    {
        return const_iterator{ this, size() };
    }
 
    auto rend() noexcept -> reverse_iterator
    {
        return std::make_reverse_iterator(begin());
    }
 
    auto cbegin() const noexcept -> const_iterator
    {
        return const_iterator{ this, 0 };
    }
 
    auto crbegin() const noexcept -> const_reverse_iterator
    {
        return std::make_reverse_iterator(cend());
    }
 
    auto cend() const noexcept -> const_iterator
    {
        return const_iterator{ this, size() };
    }
 
    auto crend() const noexcept -> const_reverse_iterator
    {
        return std::make_reverse_iterator(cbegin());
    }
 
private:
    void decrease_idx(size_t &idx) noexcept
    {
        if (idx == 0)
            idx = capacity() - 1;
        else
            --idx;
    }
 
    void increase_idx(size_t &idx) noexcept
    {
        ++idx;
 
        if (idx >= capacity())
            idx = 0;
    }
 
protected:
    auto change_capacity(size_type new_capacity, ShrinkBehavior shrink_behavior = ShrinkBehavior::keep_front_elements) -> void
    {
        auto const old_capacity = capacity();
        auto const old_size = size();
 
        // No change
        if (new_capacity == old_capacity)
            return;
 
        // Vanishing
        if (new_capacity == 0) {
            storage_.resize(0);
            idx_begin_ = 0;
            idx_end_ = 0;
            full_ = false;
            return;
        }
 
 
        // Growing
        if (new_capacity > old_capacity) {
            // Make SlidingBuffer indices equal to those of the underlying container
            std::rotate(storage_.begin(), storage_.begin() + idx_begin_, storage_.end());
            storage_.resize(new_capacity);
            idx_begin_ = 0;
            idx_end_ = old_size;
            full_ = false;
            return;
        }
 
        // Shrinking
        if (old_size < new_capacity) {
            // All data fits into new capacity, just move it there
            std::rotate(storage_.begin(), storage_.begin() + idx_begin_, storage_.end());
            storage_.resize(new_capacity);
            idx_begin_ = 0;
            idx_end_ = old_size;
            full_ = false;
        }
        else {
            auto new_front = idx_begin_;
            if (shrink_behavior == ShrinkBehavior::keep_back_elements)
                new_front = (idx_end_ + old_capacity - new_capacity) % old_capacity;
 
            std::rotate(storage_.begin(), storage_.begin() + new_front, storage_.end());
            storage_.resize(new_capacity);
            full_ = true;
            idx_begin_ = 0;
            idx_end_ = 0;
        }
    }
};
 
template<typename ElementT, std::size_t fixed_capacity = 0u,
    typename Container = typename std::conditional_t<(fixed_capacity >= 1u),
        std::array<ElementT, fixed_capacity>,
        std::vector<ElementT>>
    >
class SlidingBufferExposed : public SlidingBuffer<ElementT, fixed_capacity, Container> {
public:
    using iterator = typename Container::iterator;
    using const_iterator = typename Container::const_iterator;
    using reverse_iterator = typename Container::reverse_iterator;
    using const_reverse_iterator = typename Container::const_reverse_iterator;
 
    // Inherit member types
    using typename SlidingBuffer<ElementT, fixed_capacity, Container>::container_type;
    using typename SlidingBuffer<ElementT, fixed_capacity, Container>::value_type;
    using typename SlidingBuffer<ElementT, fixed_capacity, Container>::size_type;
    using typename SlidingBuffer<ElementT, fixed_capacity, Container>::difference_type;
    using typename SlidingBuffer<ElementT, fixed_capacity, Container>::reference;
    using typename SlidingBuffer<ElementT, fixed_capacity, Container>::const_reference;
    using typename SlidingBuffer<ElementT, fixed_capacity, Container>::pointer;
    using typename SlidingBuffer<ElementT, fixed_capacity, Container>::const_pointer;
 
    // Inherit constructors
    using SlidingBuffer<ElementT, fixed_capacity, Container>::SlidingBuffer;
 
    // Inherit members for access without "this->"
    using SlidingBuffer<ElementT, fixed_capacity, Container>::storage_;
    using SlidingBuffer<ElementT, fixed_capacity, Container>::idx_begin_;
    using SlidingBuffer<ElementT, fixed_capacity, Container>::idx_end_;
    using SlidingBuffer<ElementT, fixed_capacity, Container>::full_;
    using SlidingBuffer<ElementT, fixed_capacity, Container>::capacity;
 
    auto begin() noexcept -> iterator
    {
        if (not full_ and (idx_end_ == 0 or idx_end_ >= idx_begin_))
            return storage_.begin() + idx_begin_;
 
        return storage_.begin();
    }
 
    auto begin() const noexcept -> const_iterator
    {
        return cbegin();
    }
 
    auto cbegin() const noexcept -> const_iterator
    {
        if (not full_ and (idx_end_ == 0 or idx_end_ >= idx_begin_))
            return storage_.cbegin() + idx_begin_;
 
        return storage_.cbegin();
    }
 
    auto end() noexcept -> iterator
    {
        if (full_ or idx_begin_ != 0)
            return storage_.end();
 
        return storage_.begin() + idx_end_;
    }
 
    auto end() const noexcept -> const_iterator
    {
        return cend();
    }
 
    auto cend() const noexcept -> const_iterator
    {
        if (full_ or idx_begin_ != 0)
            return storage_.cend();
 
        return storage_.cbegin() + idx_end_;
    }
 
    auto rbegin() noexcept -> reverse_iterator
    {
        return std::make_reverse_iterator(end());
    }
 
    auto crbegin() const noexcept -> const_reverse_iterator
    {
        return std::make_reverse_iterator(cend());
    }
 
    auto rend() noexcept -> reverse_iterator
    {
        return std::make_reverse_iterator(begin());
    }
 
    auto crend() const noexcept -> const_reverse_iterator
    {
        return std::make_reverse_iterator(cbegin());
    }
 
    auto resize(size_type new_capacity, ShrinkBehavior shrink_behavior = ShrinkBehavior::keep_front_elements) -> void
    {
        static_assert(fixed_capacity == 0u,
            "resize() only possible if the underlying container is resizable");
 
        // We handle just one special case here: A pure right aligned un-full buffer
        //
        // I.e. only push_front() (not push_back()) has been used until now, and
        // the buffer is not yet filled completely. Then the data will only occupy
        // the 'right hand side' of the underlying container.
        //
        // In order to fulfill begin()'s and end()'s guarantee to include only
        // filled elements we need to right-align the data in the new container.
 
        auto const old_capacity = capacity();
 
        auto const right_align =
            (shrink_behavior == ShrinkBehavior::keep_front_elements)
            and (new_capacity > 0)
            and (new_capacity != old_capacity)
            and (not full_)
            and (idx_end_ == 0)
            and (idx_begin_ != 0);
 
        if (not right_align)
            return this->change_capacity(new_capacity, shrink_behavior);
 
        // Growing
        if (new_capacity > old_capacity) {
            storage_.resize(new_capacity);
            std::move_backward(storage_.begin() + idx_begin_,
                               storage_.begin() + old_capacity, storage_.end());
            idx_begin_ += new_capacity - old_capacity;
            return;
        }
 
        // Shrinking
        full_ = (this->size() >= new_capacity);
        auto const required_shift = std::min(old_capacity - new_capacity, idx_begin_);
        std::rotate(storage_.begin(), storage_.begin() + required_shift, storage_.end());
        idx_begin_ -= required_shift;
        storage_.resize(new_capacity);
    }
 
    auto reserve(size_type size, ShrinkBehavior shrink_behavior = ShrinkBehavior::keep_front_elements) -> void
    {
        static_assert(fixed_capacity == 0u,
            "reserve() only possible if the underlying container is resizable");
        resize(size, shrink_behavior);
    }
};
 
} // namespace gul14
 
#endif
 
// vi:ts=4:sw=4:sts=4:et