ScrollingBuffer.hpp

Go to the documentation of this file.

// This file is part of INSTINCT, the INS Toolkit for Integrated
// Navigation Concepts and Training by the Institute of Navigation of
// the University of Stuttgart, Germany.
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
 
 
#pragma once
 
#include <vector>
#include <string>
#include <iostream>
#include <fmt/ostream.h>
 
namespace NAV
{
 
template<class T, size_t _Padding = 0>
class ScrollingBuffer
{
  public:
    // ###########################################################################################################
    //                                               Constructors
    // ###########################################################################################################
 
    explicit ScrollingBuffer(size_t maxSize = 0)
        : _infiniteBuffer(maxSize == 0), _maxSize(maxSize + _Padding), _dataStart(_Padding), _dataEnd(_infiniteBuffer ? 0 : _Padding)
    {
        _data.reserve(maxSize + _Padding);
        _data.resize(_Padding);
    }
 
    ScrollingBuffer(std::initializer_list<T> init)
        : _infiniteBuffer(init.size() == 0), _maxSize(init.size())
    {
        _data.reserve(init.size());
 
        for (auto& val : init)
        {
            push_back(val);
        }
    }
 
    // ###########################################################################################################
    //                                              Element access
    // ###########################################################################################################
 
    T& at(size_t pos)
    {
        // Cast the const away and reuse the implementation below
        return const_cast<T&>(static_cast<const ScrollingBuffer&>(*this).at(pos)); // NOLINT(cppcoreguidelines-pro-type-const-cast)
    }
 
    [[nodiscard]] const T& at(size_t pos) const
    {
        if (!(pos < size()))
        {
            throw std::out_of_range("ScrollingBuffer::at: pos (which is "
                                    + std::to_string(pos) + ") >= this->size() (which is " + std::to_string(size()) + ")");
        }
 
        //     start/end
        //     |
        // 8 9 3 4 5 6 7
        // at(0) = 3, at(4) = 7, at(5) = 8
        if (_dataStart + pos >= _maxSize)
        {
            return _data.at(_dataStart + pos - _maxSize);
        }
 
        return _data.at(_dataStart + pos);
    }
 
    T& front()
    {
        // Cast the const away and reuse the implementation below (don't repeat yourself)
        return const_cast<T&>(static_cast<const ScrollingBuffer&>(*this).front()); // NOLINT(cppcoreguidelines-pro-type-const-cast)
    }
 
    [[nodiscard]] const T& front() const
    {
        return _data.at(_dataStart);
    }
 
    T& back()
    {
        return const_cast<T&>(static_cast<const ScrollingBuffer&>(*this).back()); // NOLINT(cppcoreguidelines-pro-type-const-cast)
    }
 
    [[nodiscard]] const T& back() const
    {
        if (_data.size() < _maxSize || _dataEnd == 0)
        {
            return _data.back();
        }
 
        return _data.at(_dataEnd - 1);
    }
 
    // ###########################################################################################################
    //                                                Iterators
    // ###########################################################################################################
 
    class Iterator
    {
      public:
        using iterator_category = std::forward_iterator_tag; 
        using difference_type = std::ptrdiff_t;              
        using value_type = T;                                
        using pointer = T*;                                  
        using reference = T&;                                
 
        explicit Iterator(ScrollingBuffer& buffer, size_t index = 0)
            : buffer(buffer), index(index) {}
 
        reference operator*() const { return buffer.at(index); }
        pointer operator->() { return &buffer.at(index); }
 
        Iterator& operator++()
        {
            if (index == buffer.size()) { return *this; }
            index++;
            return *this;
        }
        Iterator operator++(int)
        {
            Iterator tmp = *this;
            operator++();
            return tmp;
        }
 
        friend bool operator==(const Iterator& lhs, const Iterator& rhs) { return &lhs.buffer == &rhs.buffer && lhs.index == rhs.index; };
        friend bool operator!=(const Iterator& lhs, const Iterator& rhs) { return !(lhs == rhs); };
 
      private:
        ScrollingBuffer& buffer; 
        size_t index;            
    };
 
    Iterator begin() { return Iterator(*this, 0); }
    Iterator end() { return Iterator(*this, size()); }
 
    class ConstIterator
    {
      public:
        using iterator_category = std::forward_iterator_tag; 
        using difference_type = std::ptrdiff_t;              
        using value_type = T;                                
        using pointer = const T*;                            
        using reference = const T&;                          
 
        explicit ConstIterator(const ScrollingBuffer& buffer, size_t index = 0)
            : buffer(buffer), index(index) {}
 
        reference operator*() const { return buffer.at(index); }
        pointer operator->() { return &buffer.at(index); }
 
        const ConstIterator& operator++()
        {
            if (index == buffer.size()) { return *this; }
            index++;
            return *this;
        }
        ConstIterator operator++(int)
        {
            ConstIterator tmp = *this;
            operator++();
            return tmp;
        }
 
        friend bool operator==(const ConstIterator& lhs, const ConstIterator& rhs) { return &lhs.buffer == &rhs.buffer && lhs.index == rhs.index; };
        friend bool operator!=(const ConstIterator& lhs, const ConstIterator& rhs) { return !(lhs == rhs); };
 
      private:
        const ScrollingBuffer& buffer; 
        size_t index;                  
    };
 
    [[nodiscard]] ConstIterator begin() const { return ConstIterator(*this, 0); }
    [[nodiscard]] ConstIterator end() const { return ConstIterator(*this, size()); }
    [[nodiscard]] ConstIterator cbegin() const { return ConstIterator(*this, 0); }
    [[nodiscard]] ConstIterator cend() const { return ConstIterator(*this, size()); }
 
    class ReverseIterator
    {
      public:
        using iterator_category = std::forward_iterator_tag; 
        using difference_type = std::ptrdiff_t;              
        using value_type = T;                                
        using pointer = T*;                                  
        using reference = T&;                                
 
        explicit ReverseIterator(ScrollingBuffer& buffer, int64_t index = 0)
            : buffer(buffer), index(index) {}
 
        reference operator*() const { return buffer.at(static_cast<size_t>(index)); }
        pointer operator->() { return &buffer.at(static_cast<size_t>(index)); }
 
        ReverseIterator& operator++()
        {
            if (index < 0) { return *this; }
            index--;
            return *this;
        }
        ReverseIterator operator++(int)
        {
            ReverseIterator tmp = *this;
            operator++();
            return tmp;
        }
 
        friend bool operator==(const ReverseIterator& lhs, const ReverseIterator& rhs) { return &lhs.buffer == &rhs.buffer && lhs.index == rhs.index; };
        friend bool operator!=(const ReverseIterator& lhs, const ReverseIterator& rhs) { return !(lhs == rhs); };
 
      private:
        ScrollingBuffer& buffer; 
        int64_t index;           
    };
 
    ReverseIterator rbegin() { return ReverseIterator(*this, static_cast<int64_t>(size()) - 1); }
    ReverseIterator rend() { return ReverseIterator(*this, -1); }
 
    class ConstReverseIterator
    {
      public:
        using iterator_category = std::forward_iterator_tag; 
        using difference_type = std::ptrdiff_t;              
        using value_type = T;                                
        using pointer = const T*;                            
        using reference = const T&;                          
 
        explicit ConstReverseIterator(const ScrollingBuffer& buffer, int64_t index = 0)
            : buffer(buffer), index(index) {}
 
        reference operator*() const { return buffer.at(static_cast<size_t>(index)); }
        pointer operator->() { return &buffer.at(static_cast<size_t>(index)); }
 
        const ConstReverseIterator& operator++()
        {
            if (index < 0) { return *this; }
            index--;
            return *this;
        }
        ConstReverseIterator operator++(int)
        {
            ConstReverseIterator tmp = *this;
            operator++();
            return tmp;
        }
 
        friend bool operator==(const ConstReverseIterator& lhs, const ConstReverseIterator& rhs) { return &lhs.buffer == &rhs.buffer && lhs.index == rhs.index; };
        friend bool operator!=(const ConstReverseIterator& lhs, const ConstReverseIterator& rhs) { return !(lhs == rhs); };
 
      private:
        const ScrollingBuffer& buffer; 
        int64_t index;                 
    };
 
    [[nodiscard]] ConstReverseIterator rbegin() const { return ConstReverseIterator(*this, static_cast<int64_t>(size()) - 1); }
    [[nodiscard]] ConstReverseIterator rend() const { return ConstReverseIterator(*this, -1); }
    [[nodiscard]] ConstReverseIterator crbegin() const { return ConstReverseIterator(*this, static_cast<int64_t>(size()) - 1); }
    [[nodiscard]] ConstReverseIterator crend() const { return ConstReverseIterator(*this, -1); }
 
    // ###########################################################################################################
    //                                                 Capacity
    // ###########################################################################################################
 
    [[nodiscard]] bool empty() const
    {
        return size() == 0;
    }
 
    [[nodiscard]] bool full() const
    {
        return !_infiniteBuffer && _maxSize - _Padding == size();
    }
 
    [[nodiscard]] size_t size() const
    {
        if (_dataStart == _Padding && _dataEnd == _Padding) // Buffer empty or full and not scrolled
        {
            return _data.size() - _Padding;
        }
        if (_dataStart < _dataEnd) // not scrolled buffer
        {
            return _dataEnd - _dataStart;
        }
 
        // scrolled buffer
        return _maxSize - (_dataStart - _dataEnd);
    }
 
    void reserve(size_t new_cap)
    {
        _data.reserve(new_cap);
    }
 
    [[nodiscard]] size_t capacity() const
    {
        return _infiniteBuffer ? 0 : (_maxSize - _Padding);
    }
 
    // ###########################################################################################################
    //                                                 Modifiers
    // ###########################################################################################################
 
    void clear()
    {
        _data.clear();
        _dataStart = _Padding;
        _dataEnd = _infiniteBuffer ? 0 : _Padding;
 
        for (size_t i = 0; i < _Padding; i++)
        {
            _data.push_back({});
        }
    }
 
    void push_back(const T& value)
    {
        if (_infiniteBuffer) // The buffer should grow when adding new values
        {
            _data.push_back(value);
            _maxSize = _data.size();
        }
        else if (_data.size() < _maxSize) // The real buffer is smaller than the allowed buffer size
        {
            _data.push_back(value);
            _dataEnd = (_dataEnd + 1) % _maxSize;
        }
        else // The real buffer as large as or bigger than the allowed buffer size, so we have to scroll the buffer
        {
            _data.at(_dataEnd) = value;
            if (size() >= capacity())
            {
                // "5, 6, _, _, 2, 3, 4"
                // "5, 6, 7, _, 2, 3, 4"
                _dataStart = (_dataStart + 1) % _maxSize;
            }
            _dataEnd = (_dataEnd + 1) % _maxSize;
        }
    }
 
    void pop_front()
    {
        if (empty())
        {
            return;
        }
        if (size() == 1)
        {
            clear();
            return;
        }
 
        if (_infiniteBuffer)
        {
            _data.erase(_data.begin());
            _maxSize = _data.size();
        }
        else
        {
            //       se                e     s                 e     s              s               e             se
            // 5, 6, 2, 3, 4  // 5, 6, _, _, 2, 3, 4  // 5, 6, X, X, 2, 3, 4  // X, 6, 7, 8, 9, 10, X // 5, 6, 7, 4
            //       e  s              e        s              e        s              s            e    s        e
            // 5, 6, _, 3, 4  // 5, 6, _, _, _, 3, 4  // 5, 6, _, X, X, 3, 4  // X, X, 7, 8, 9, 10, _ // 5, 6, 7, _
            _dataStart = (_dataStart + 1) % _maxSize;
        }
    }
 
    void resize(size_t targetSize)
    {
        if (targetSize == 0) // Buffer should grow indefinitely when adding new values
        {
            _infiniteBuffer = true;
 
            if (isScrolled()) // Buffer is scrolled and needs to be sorted in order of insertion
            {
                //       se                e     s                 e     s              s               e
                // 5, 6, 2, 3, 4  // 5, 6, _, _, 2, 3, 4  // 5, 6, X, X, 2, 3, 4  // X, 6, 7, 8, 9, 10, X
                // 2, 3, 4, 5, 6  // 2, 3, 4, 5, 6, _, _  // X, X, 2, 3, 4, 5, 6  // X, X, 6, 7, 8, 9, 10
                std::vector<T> to_vector;
 
                if (_dataEnd > _dataStart)
                {
                    std::copy(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)), _data.end(),
                              std::back_inserter(to_vector));
                    _maxSize = _dataEnd;
                }
 
                std::copy(std::next(_data.begin(), std::max(static_cast<int>(_dataStart - _Padding), 0)),
                          std::next(_data.begin(), static_cast<int64_t>(std::max(_dataEnd, _maxSize))),
                          std::back_inserter(to_vector));
 
                if (int64_t elementsFront = std::min(static_cast<int64_t>(_dataEnd), static_cast<int64_t>(_dataStart - _Padding));
                    elementsFront > 0)
                {
                    std::copy(_data.begin(), std::next(_data.begin(), elementsFront),
                              std::back_inserter(to_vector));
                }
                _data.swap(to_vector);
 
                _maxSize = _data.size();
 
                _dataStart = _Padding;
                _dataEnd = 0;
            }
        }
        else // Buffer should have scrolling behaviour when adding new values
        {
            _infiniteBuffer = false;
 
            if (_maxSize - _Padding > targetSize) // We make the buffer smaller
            {
                if (!isScrolled()) // Buffer is not scrolled, so shrinking removes the values from the front of the buffer
                {
                    size_t elementsToDelete = _maxSize - _Padding - targetSize;
 
                    if (size_t emptyAtTheBack = _maxSize - _dataEnd;
                        size_t emptyAtTheBackToDelete = std::min(emptyAtTheBack, elementsToDelete))
                    {
                        // 1, 2, 3, _, _,  // X, X, 1, 2, 3, _, _,
                        // 1, 2, 3, _,     // X, X, 1, 2, 3, _,
                        _maxSize -= emptyAtTheBackToDelete;
                        _dataEnd %= _maxSize; // NOLINT(clang-analyzer-core.DivideZero) // this lint is wrong, even when wrapped by `if(_maxSize != 0)` appearing
                        elementsToDelete -= emptyAtTheBackToDelete;
                        // 1, 2, 3,        // X, X, 1, 2, 3,
                    }
 
                    // 1, 2, 3,
                    // 2, 3,
                    if (elementsToDelete)
                    {
                        _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataStart)),
                                    std::next(_data.begin(), static_cast<int64_t>(_dataStart + elementsToDelete)));
                        _maxSize -= elementsToDelete;
                    }
                }
                else // Buffer is scrolled, so the correct values have to be erased from the buffer when shrinking
                {
                    // 5, 6, _, _, 2, 3, 4, // 5, 6, _, _, X, X, 2, 3, 4,
                    // 6,                   // 6, X, X
 
                    // 6, 7, 3, 4, 5,       // 5, 6, X, X, 2, 3, 4
                    // 6, 7, 4, 5,          // 5, 6, X, X, 3, 4
 
                    // X, 6, 7, 8, 9, 10, X
                    // X, 9, 10, X
 
                    size_t elementsToDelete = _maxSize - _Padding - targetSize;
 
                    if (size_t emptyInBetween = static_cast<size_t>(std::max(static_cast<int>(_dataStart - _Padding - _dataEnd), 0));
                        size_t emptyInBetweenToDelete = std::min(emptyInBetween, elementsToDelete))
                    {
                        // 5, 6, _, _, 2, 3, 4, // 5, 6, _, _, X, X, 2, 3, 4,
                        _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)),
                                    std::next(_data.begin(), static_cast<int64_t>(_dataEnd + emptyInBetweenToDelete)));
                        // 5, 6, _, 2, 3, 4,    // 5, 6, _, X, X, 2, 3, 4,
                        _dataStart -= emptyInBetweenToDelete;
                        _maxSize -= emptyInBetweenToDelete;
                        elementsToDelete -= emptyInBetweenToDelete;
                    }
 
                    //       s                   e
                    //  X  , 6, 7 ,   8 , 9, 10, X
                    // X(8), 9, 10, X(7)
                    if (size_t paddingAtTheEnd = static_cast<size_t>(std::max(static_cast<int>(_Padding - _dataStart), 0));
                        size_t paddingAtTheEndToDelete = std::min(paddingAtTheEnd, elementsToDelete))
                    {
                        _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)),
                                    std::next(_data.begin(), static_cast<int64_t>(_dataEnd + paddingAtTheEndToDelete)));
                        _maxSize -= paddingAtTheEndToDelete;
                        _dataStart += paddingAtTheEndToDelete;
                        _dataEnd %= _maxSize;
                        elementsToDelete -= paddingAtTheEndToDelete;
                    }
                    // e     s
                    // X, X, 6, 7 , 8 , 9, 10
                    // X, X, 7 , 8 , 9, 10
 
                    if (size_t elementsAtTheBack = _maxSize - _dataStart - (_dataEnd > _dataStart ? _maxSize - _dataEnd : 0);
                        size_t elementsAtTheBackToDelete = std::min(elementsAtTheBack, elementsToDelete))
                    {
                        // 5, 6, 2, 3, 4,       // 5, 6, X, X, 2, 3, 4,
                        _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataStart - _Padding)),
                                    std::next(_data.begin(), static_cast<int64_t>(_dataStart - _Padding + elementsAtTheBackToDelete)));
                        // 5, 6, 4,             // 5, 6, X, X, 4,
                        // 5, 6,                // 5, 6, X, X,
                        _maxSize -= elementsAtTheBackToDelete;
                        _dataStart %= _maxSize;
                        if (_dataEnd > _maxSize)
                        {
                            _dataEnd -= elementsToDelete;
                        }
                        _dataEnd %= _maxSize;
                        elementsToDelete -= elementsAtTheBackToDelete;
                    }
                    if (elementsToDelete)
                    {
                        // 5, 6,                // 5, 6, X, X,
                        _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataStart)),
                                    std::next(_data.begin(), static_cast<int64_t>(std::min(_dataStart + elementsToDelete, _maxSize - _Padding))));
                        // 6,                   // 6, X, X
                        _maxSize -= elementsToDelete;
                        if (_dataEnd >= elementsToDelete)
                        {
                            _dataEnd -= elementsToDelete;
                        }
                    }
                }
            }
            else if (_maxSize - _Padding < targetSize) // We make the buffer bigger
            {
                // 1, 2, 3, _, _,        // X, X, 0, 1, 2, 3, _, _
                // 1, 2, 3, _, _, _, _,  // X, X, 0, 1, 2, 3, _, _, _, _
                if (!isScrolled()) // Buffer not scrolled, so we can simply reserve more space
                {
                    _maxSize = targetSize + _Padding;
                    _data.reserve(_maxSize);
                }
                //      se                      e     s                 s               e
                // 6, 7, 3, 4, 5,      // 5, 6, X, X, 2, 3, 4     // X, 6, 7, 8, 9, 10, X
                // 6, 7, _, 3, 4, 5,   // 5, 6, _, X, X, 2, 3, 4  // X, 6, 7, 8, 9, 10, _, _, X
                else // (_dataStart != 0) // Buffer scrolled, so we need to copy the values to the correct positions
                {
                    _data.resize(targetSize + _Padding);
 
                    auto copy_backward = [](auto first, auto last, auto d_last) { // Needed, as MacOS with C++23 does not support std::copy_backward
                        while (first != last)
                        {
                            *(--d_last) = *(--last);
                        }
                    };
 
                    copy_backward(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)),
                                  std::next(_data.begin(), static_cast<int64_t>(_maxSize)),
                                  std::next(_data.begin(), static_cast<int64_t>(targetSize + _Padding)));
 
                    auto diff = targetSize + _Padding - _maxSize;
                    if (_dataStart >= _dataEnd)
                    {
                        _dataStart += diff;
                    }
 
                    _maxSize = targetSize + _Padding;
                }
            }
        }
    }
 
    // ###########################################################################################################
    //                                                   Other
    // ###########################################################################################################
 
    [[nodiscard]] T max() const
    {
        T currentMax = front();
        for (size_t i = 0; i < _data.size(); i++)
        {
            if (i >= _dataStart || i < _dataEnd)
            {
                currentMax = std::max(currentMax, _data.at(i));
            }
        }
        return currentMax;
    }
 
    [[nodiscard]] T min() const
    {
        T currentMin = front();
        for (size_t i = 0; i < _data.size(); i++)
        {
            if (i >= _dataStart || i < _dataEnd)
            {
                currentMin = std::min(currentMin, _data.at(i));
            }
        }
        return currentMin;
    }
 
    [[nodiscard]] int offset() const
    {
        return static_cast<int>(_dataStart);
    }
 
    [[nodiscard]] const T* data() const
    {
        return _data.data();
    }
 
    [[nodiscard]] T* data()
    {
        return _data.data();
    }
 
    [[nodiscard]] bool isInfiniteBuffer() const
    {
        return _infiniteBuffer;
    }
 
    [[nodiscard]] std::string getRawString() const
    {
        // Scrolled
        //       e        s
        // 5, 6, _, _, X, 2, 3, 4
 
        //      se
        // 5, 6, 2, 3, 4
 
        //    s  e
        // _, 6, _, _, _
 
        // Not scrolled
        //       s           e
        // X, X, 0, 1, 2, 3, _, _
 
        //    s               e
        // X, 6, 7, 8, 9, 10, _, _, X
 
        // s  e
        // 6, X, X,
 
        // s  e
        // 6, _, X, X,
 
        //       se
        // X, X, _, _, _,
 
        std::string out;
 
        for (int i = 0; static_cast<size_t>(i) < _maxSize; i++) // X, 6, 7, 8, 9, 10, _, _, X
        {
            if ((i >= static_cast<int>(_dataStart - _Padding) && static_cast<size_t>(i) < _dataStart)
                || (static_cast<size_t>(i) >= _dataStart + _maxSize - _Padding))
            {
                out += "X"; // padding
            }
            else if (bool scrolled = isScrolled();
                     (scrolled && static_cast<size_t>(i) >= _dataEnd && (static_cast<int>(_dataStart - _Padding) < 0 || i < static_cast<int>(_dataStart - _Padding)))
                     || (scrolled && _dataStart < _dataEnd && (static_cast<size_t>(i) < _dataStart || static_cast<size_t>(i) >= _dataEnd))
                     || (!scrolled && static_cast<size_t>(i) >= _dataEnd))
            {
                out += "_"; // empty
            }
            else
            {
                out += std::to_string(_data.at(static_cast<size_t>(i)));
            }
            if (static_cast<size_t>(i) != _maxSize - 1)
            {
                out += ", ";
            }
        }
        return out;
    }
 
    friend std::ostream& operator<<(std::ostream& os, const ScrollingBuffer<T, _Padding>& buffer)
    {
        os << fmt::format("{}", fmt::join(buffer, ", "));
        return os;
    }
 
  private:
    bool _infiniteBuffer{ false };
    size_t _maxSize;
    size_t _dataStart{ 0 };
    size_t _dataEnd{ 0 };
    std::vector<T> _data;
 
    [[nodiscard]] bool isScrolled() const
    {
        //       e        s
        // 5, 6, _, _, X, 2, 3, 4
 
        //                                se
        if (_dataEnd == 0 && !empty()) // 1, 2, 3, 4
        {
            return true;
        }
 
        return _dataEnd < _dataStart
               || (_dataStart != _Padding);
 
        //      se        //       se
        // 5, 6, 2, 3, 4  // X, X, _, _, _
 
        //    s           e
        // X, 0, 1, 2, 3, _, _, X // Scrolled
        //       s           e
        // X, X, 0, 1, 2, 3, _, _ // Not scrolled
    }
};
 
} // namespace NAV
 
#ifndef DOXYGEN_IGNORE
 
template<class T, size_t _Padding>
struct fmt::formatter<NAV::ScrollingBuffer<T, _Padding>> : ostream_formatter
{};
 
#endif