diff options
| -rw-r--r-- | libs/kstd/kstd/ring_buffer.hpp | 144 | ||||
| -rw-r--r-- | libs/kstd/kstd/ring_buffer.tests.cpp | 21 |
2 files changed, 165 insertions, 0 deletions
diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 3e85baae..8328655d 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -5,8 +5,11 @@ #include <kstd/os/error.hpp> #include <algorithm> +#include <compare> #include <cstddef> +#include <iterator> #include <ranges> +#include <type_traits> namespace kstd { @@ -18,12 +21,153 @@ namespace kstd template<typename ValueType, std::size_t Capacity> struct ring_buffer { + template<bool Const> + struct ring_buffer_iterator; + using value_type = ValueType; using pointer = value_type *; using const_pointer = value_type const *; using reference = value_type &; using const_reference = value_type const &; using size_type = std::size_t; + using iterator = ring_buffer_iterator<false>; + using const_iterator = ring_buffer_iterator<true>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + + template<bool Const> + struct ring_buffer_iterator + { + using iterator_category = std::random_access_iterator_tag; + using iterator_concept = std::random_access_iterator_tag; + using value_type = ring_buffer::value_type; + using difference_type = std::ptrdiff_t; + using pointer = std::conditional_t<Const, ring_buffer::const_pointer, ring_buffer::pointer>; + using reference = std::conditional_t<Const, ring_buffer::const_reference, ring_buffer::reference>; + + constexpr ring_buffer_iterator() = default; + + constexpr ring_buffer_iterator(ring_buffer_iterator const &) = default; + + constexpr ring_buffer_iterator(ring_buffer_iterator<!Const> it) + requires Const + : m_buffer{it.m_buffer} + , m_index{it.m_index} + {} + + template<bool OtherConst> + [[nodiscard]] constexpr auto friend operator<=>(ring_buffer_iterator const & lhs, + ring_buffer_iterator<OtherConst> const & rhs) noexcept + -> std::strong_ordering + { + return lhs.m_index <=> rhs.m_index; + } + + template<bool OtherConst> + [[nodiscard]] constexpr auto friend operator==(ring_buffer_iterator const & lhs, + ring_buffer_iterator<OtherConst> const & rhs) noexcept -> bool + { + return lhs.m_buffer == rhs.m_buffer && lhs.m_index == rhs.m_index; + } + + [[nodiscard]] constexpr auto friend operator==(ring_buffer_iterator const & lhs, std::default_sentinel_t) noexcept + -> bool + { + return lhs.m_buffer == nullptr || lhs.m_index >= lhs.m_buffer->size(); + } + + template<bool OtherConst> + [[nodiscard]] constexpr auto operator-(ring_buffer_iterator<OtherConst> const & other) const noexcept + -> difference_type + { + return static_cast<difference_type>(m_index) - static_cast<difference_type>(other.m_index); + } + + constexpr auto operator+=(difference_type offset) noexcept -> ring_buffer_iterator & + { + m_index += offset; + return *this; + } + + [[nodiscard]] constexpr auto friend operator+(ring_buffer_iterator it, difference_type offset) noexcept + -> ring_buffer_iterator + { + return it += offset; + } + + [[nodiscard]] constexpr auto friend operator+(difference_type offset, ring_buffer_iterator it) noexcept + -> ring_buffer_iterator + { + return it += offset; + } + + constexpr auto operator-=(difference_type offset) noexcept -> ring_buffer_iterator & + { + m_index -= offset; + return *this; + } + + [[nodiscard]] constexpr auto friend operator-(ring_buffer_iterator it, difference_type offset) noexcept + -> ring_buffer_iterator + { + return it -= offset; + } + + constexpr auto operator++() noexcept -> ring_buffer_iterator & + { + ++m_index; + return *this; + } + + constexpr auto operator++(int) noexcept -> ring_buffer_iterator + { + auto copy = *this; + ++(*this); + return copy; + } + + constexpr auto operator--() noexcept -> ring_buffer_iterator & + { + --m_index; + return *this; + } + + constexpr auto operator--(int) noexcept -> ring_buffer_iterator + { + auto copy = *this; + --(*this); + return copy; + } + + [[nodiscard]] constexpr auto operator[](difference_type offset) const noexcept -> reference + { + return (*m_buffer)[m_index + static_cast<size_type>(offset)]; + } + + [[nodiscard]] constexpr auto operator*() const noexcept -> reference + { + return *m_buffer->element_at(m_index); + } + + [[nodiscard]] constexpr auto operator->() const noexcept -> pointer + { + return m_buffer->element_at(m_index); + } + + private: + friend struct ring_buffer; + friend struct ring_buffer_iterator<!Const>; + + using buffer_type = std::conditional_t<Const, ring_buffer const, ring_buffer>; + + constexpr ring_buffer_iterator(buffer_type * buffer, size_type index) + : m_buffer{buffer} + , m_index{index} + {} + + buffer_type * m_buffer{}; + size_type m_index{}; + }; //! @name Special Member Functions //! @{ diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 43ddafae..91535e04 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -7,6 +7,7 @@ #include <catch2/matchers/catch_matchers_exception.hpp> #include <cstddef> +#include <iterator> #include <type_traits> #include <utility> @@ -46,6 +47,26 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") STATIC_REQUIRE(std::is_same_v<float const *, buffer::const_pointer>); } + THEN("iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator<buffer::iterator>); + } + + THEN("const_iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator<buffer::const_iterator>); + } + + THEN("reverse_iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator<buffer::reverse_iterator>); + } + + THEN("const_reverse_iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator<buffer::const_reverse_iterator>); + } + THEN("the return type of at() is 'reference' on a non-const buffer") { STATIC_REQUIRE(std::is_same_v<buffer::reference, decltype(std::declval<buffer &>().at(0))>); |