circular_array.hpp

Go to the documentation of this file.

// 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