Program Listing for File circular_array.hpp
↰ Return to documentation for file (include/beluga/containers/circular_array.hpp
)
// Copyright 2024 Ekumen, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef BELUGA_CONTAINERS_CIRCULAR_ARRAY_HPP
#define BELUGA_CONTAINERS_CIRCULAR_ARRAY_HPP
#include <array>
#include <cstdint>
#include <iterator>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <beluga/utility/indexing_iterator.hpp>
namespace beluga {
enum class CircularArrayFeatureFlags : std::int8_t {
kNone = 0x00,
kRolloverOnWrite = 0x01,
kExtrapolateOnRead = 0x02,
kLayoutReversal = 0x04
};
constexpr CircularArrayFeatureFlags operator|(CircularArrayFeatureFlags lflag, CircularArrayFeatureFlags rflag) {
return static_cast<CircularArrayFeatureFlags>( // NOLINT(lang-analyzer-optin.core.EnumCastOutOfRange)
static_cast<std::underlying_type_t<CircularArrayFeatureFlags>>(lflag) |
static_cast<std::underlying_type_t<CircularArrayFeatureFlags>>(rflag));
}
constexpr bool operator&(CircularArrayFeatureFlags mask, CircularArrayFeatureFlags flag) {
return static_cast<bool>(
static_cast<std::underlying_type_t<CircularArrayFeatureFlags>>(mask) &
static_cast<std::underlying_type_t<CircularArrayFeatureFlags>>(flag));
}
template <typename T, std::size_t N, CircularArrayFeatureFlags F = CircularArrayFeatureFlags::kNone>
class CircularArray {
public:
using value_type = T;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using reference = value_type&;
using const_reference = const value_type&;
using pointer = value_type*;
using const_pointer = const value_type*;
using allocator_type = void;
using iterator = IndexingIterator<CircularArray<T, N, F>>;
using const_iterator = IndexingIterator<const CircularArray<T, N, F>>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
CircularArray() = default;
template <
typename Iterator,
typename Sentinel,
typename = std::enable_if_t<std::is_same_v<T, typename std::iterator_traits<Iterator>::value_type>>>
CircularArray(Iterator first, Sentinel last) { // NOLINT(readability-non-const-parameter)
if constexpr (F & CircularArrayFeatureFlags::kLayoutReversal) {
tail_index_ = N - 1;
for (size_ = 0; size_ < N && first != last; ++size_, ++first) {
data_[tail_index_ - size_] = *first;
}
if constexpr (!(F & CircularArrayFeatureFlags::kRolloverOnWrite)) {
if (first != last) {
throw std::length_error{"Range does not fit in circular array"};
}
}
} else {
const auto n = static_cast<size_type>(std::distance(first, last));
if (n > N) {
if constexpr (!(F & CircularArrayFeatureFlags::kRolloverOnWrite)) {
throw std::length_error{"Range does not fit in circular array"};
} else {
std::advance(first, n - N);
}
}
for (size_ = 0; size_ < N && first != last; ++size_, ++first) {
data_[size_] = *first;
}
tail_index_ = size_ - 1;
}
}
template <std::size_t M, typename = std::enable_if_t<M >= 1 && M <= N>>
explicit CircularArray(T (&&data)[M]) : tail_index_(M - 1), size_(M) { // NOLINT(modernize-avoid-c-arrays)
if constexpr (F & CircularArrayFeatureFlags::kLayoutReversal) {
for (std::size_t i = 0; i < M; ++i)
data_[i] = data[M - i - 1];
} else {
for (std::size_t i = 0; i < M; ++i)
data_[i] = data[i];
}
}
[[nodiscard]] constexpr iterator begin() noexcept { return iterator(this); }
[[nodiscard]] constexpr const_iterator begin() const noexcept { return const_iterator(this); }
[[nodiscard]] constexpr const_iterator cbegin() const noexcept { return const_iterator(this); }
[[nodiscard]] constexpr iterator end() noexcept { return iterator(this, size()); }
[[nodiscard]] constexpr const_iterator end() const noexcept { return const_iterator(this, effective_size()); }
[[nodiscard]] constexpr const_iterator cend() const noexcept { return const_iterator(this, effective_size()); }
[[nodiscard]] constexpr reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
[[nodiscard]] constexpr const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
[[nodiscard]] constexpr const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(cend()); }
[[nodiscard]] constexpr reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
[[nodiscard]] constexpr const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
[[nodiscard]] constexpr const_reverse_iterator crend() const noexcept { return const_reverse_iterator(cbegin()); }
template <bool Enabled = !(F & CircularArrayFeatureFlags::kLayoutReversal)>
std::enable_if_t<Enabled> push_back(value_type value) {
static_assert(
!(F & CircularArrayFeatureFlags::kLayoutReversal),
"Cannot push_back() when the layout reversal feature is enabled.");
if constexpr (!(F & CircularArrayFeatureFlags::kRolloverOnWrite)) {
if (size_ == N) {
throw std::length_error{"Circular array reached its maximum size"};
}
}
if (++tail_index_ == N)
tail_index_ = 0;
data_[tail_index_] = std::move(value);
size_ = std::min(size_ + 1, N);
}
template <bool Enabled = (F & CircularArrayFeatureFlags::kLayoutReversal)>
std::enable_if_t<Enabled> push_front(value_type value) {
static_assert(
F & CircularArrayFeatureFlags::kLayoutReversal,
"Cannot push_front() when the layout reversal feature is not enabled.");
if constexpr (!(F & CircularArrayFeatureFlags::kRolloverOnWrite)) {
if (size_ == N) {
throw std::length_error{"Circular array reached its maximum size"};
}
}
if (++tail_index_ == N)
tail_index_ = 0;
data_[tail_index_] = std::move(value);
size_ = std::min(size_ + 1, N);
}
template <bool Enabled = (F & CircularArrayFeatureFlags::kLayoutReversal)>
std::enable_if_t<Enabled> pop_back() noexcept {
--size_;
}
template <bool Enabled = !(F & CircularArrayFeatureFlags::kLayoutReversal)>
std::enable_if_t<Enabled> pop_front() noexcept {
--size_;
}
[[nodiscard]] constexpr reference back() noexcept {
if constexpr (F & CircularArrayFeatureFlags::kLayoutReversal) {
return data_[head_index()];
} else {
return data_[tail_index_];
}
}
[[nodiscard]] constexpr const_reference back() const noexcept {
if constexpr (F & CircularArrayFeatureFlags::kLayoutReversal) {
return data_[head_index()];
} else {
return data_[tail_index_];
}
}
[[nodiscard]] constexpr reference front() noexcept {
if constexpr (F & CircularArrayFeatureFlags::kLayoutReversal) {
return data_[tail_index_];
} else {
return data_[head_index()];
}
}
[[nodiscard]] constexpr const_reference front() const noexcept {
if constexpr (F & CircularArrayFeatureFlags::kLayoutReversal) {
return data_[tail_index_];
} else {
return data_[head_index()];
}
}
[[nodiscard]] constexpr reference at(size_type index) {
if (index >= effective_size()) {
throw std::out_of_range{"Index out of circular array range"};
}
return (*this)[index];
}
[[nodiscard]] constexpr const_reference at(size_type index) const {
if (index >= effective_size()) {
throw std::out_of_range{"Index out of circular array range"};
}
return (*this)[index];
}
[[nodiscard]] constexpr reference operator[](size_type index) noexcept {
if constexpr (F & CircularArrayFeatureFlags::kLayoutReversal) {
return data_[static_cast<size_type>(index > tail_index_) * N + tail_index_ - index];
} else {
return data_[static_cast<size_type>(size_ - index > tail_index_ + 1) * N + tail_index_ - (size_ - index - 1)];
}
}
[[nodiscard]] constexpr const_reference operator[](size_type index) const noexcept {
if constexpr (F & CircularArrayFeatureFlags::kExtrapolateOnRead) {
index = std::min(index, size_ - 1);
}
if constexpr (F & CircularArrayFeatureFlags::kLayoutReversal) {
return data_[static_cast<size_type>(index > tail_index_) * N + tail_index_ - index];
} else {
return data_[static_cast<size_type>(size_ - index > tail_index_ + 1) * N + tail_index_ - (size_ - index - 1)];
}
}
void fill(const T& value) {
while (size_ < N) {
tail_index_ = (tail_index_ + 1) % N;
data_[tail_index_] = value;
++size_;
}
}
void clear() noexcept { size_ = 0; }
template <CircularArrayFeatureFlags G>
void swap(CircularArray<T, N, G>& other) noexcept(std::is_nothrow_swappable_v<T>) {
using std::swap;
swap(data_, other.data_);
swap(size_, other.size_);
swap(tail_index_, other.tail_index_);
}
template <typename U, std::size_t M, CircularArrayFeatureFlags G>
friend class CircularArray;
[[nodiscard]] constexpr T* data() noexcept { return data_.data(); }
[[nodiscard]] constexpr const T* data() const noexcept { return data_.data(); }
[[nodiscard]] constexpr bool full() const noexcept { return size_ == N; }
[[nodiscard]] constexpr bool empty() const noexcept { return size_ == 0U; }
[[nodiscard]] constexpr size_type size() const noexcept { return size_; }
[[nodiscard]] constexpr size_type max_size() const noexcept { return N; }
[[nodiscard]] constexpr size_type effective_size() const noexcept {
if constexpr (F & CircularArrayFeatureFlags::kExtrapolateOnRead) {
return static_cast<size_type>(size_ > 0) * N;
} else {
return size_;
}
}
private:
// Computes the head index of the array.
[[nodiscard]] constexpr size_type head_index() const noexcept {
return static_cast<size_type>(size_ > tail_index_ + 1) * N + tail_index_ - size_ + 1;
}
std::array<T, N> data_;
size_type tail_index_{0U};
size_type size_{0U};
};
template <typename T, std::size_t N>
using RollingWindow = CircularArray<
T,
N,
CircularArrayFeatureFlags::kRolloverOnWrite | CircularArrayFeatureFlags::kExtrapolateOnRead |
CircularArrayFeatureFlags::kLayoutReversal>;
template <typename T, std::size_t N, CircularArrayFeatureFlags F>
CircularArray<T, N, F>& operator<<(CircularArray<T, N, F>& array, T value) {
if constexpr (F & CircularArrayFeatureFlags::kLayoutReversal) {
array.push_front(std::move(value));
} else {
array.push_back(std::move(value));
}
return array;
}
template <std::size_t I, class T, std::size_t N, CircularArrayFeatureFlags F>
constexpr T& get(CircularArray<T, N, F>& array) noexcept {
return array[I];
}
template <std::size_t I, class T, std::size_t N, CircularArrayFeatureFlags F>
constexpr T&& get(CircularArray<T, N, F>&& array) noexcept {
return array[I];
}
template <std::size_t I, class T, std::size_t N, CircularArrayFeatureFlags F>
constexpr const T& get(const CircularArray<T, N, F>& array) noexcept {
return array[I];
}
template <std::size_t I, class T, std::size_t N, CircularArrayFeatureFlags F>
constexpr const T&& get(const CircularArray<T, N, F>&& array) noexcept {
return array[I];
}
template <typename T, std::size_t N, CircularArrayFeatureFlags F, CircularArrayFeatureFlags G>
constexpr void swap(CircularArray<T, N, F>& a, CircularArray<T, N, G>& b) {
a.swap(b);
}
} // namespace beluga
namespace std {
template <typename T, std::size_t N, beluga::CircularArrayFeatureFlags F>
struct tuple_size<beluga::CircularArray<T, N, F>> : std::integral_constant<std::size_t, N> {};
template <std::size_t I, typename T, std::size_t N, beluga::CircularArrayFeatureFlags F>
struct tuple_element<I, beluga::CircularArray<T, N, F>> {
using type = T;
};
} // namespace std
#endif