Program Listing for File tuple_vector.hpp

↰ Return to documentation for file (include/beluga/containers/tuple_vector.hpp)

// Copyright 2022-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_TUPLE_VECTOR_HPP
#define BELUGA_CONTAINERS_TUPLE_VECTOR_HPP

#include <tuple>
#include <vector>

#include <beluga/type_traits.hpp>
#include <beluga/views/zip.hpp>
#include <range/v3/algorithm/copy.hpp>
#include <range/v3/iterator/insert_iterators.hpp>
#include <range/v3/view/const.hpp>
#include <range/v3/view/take.hpp>

namespace beluga {

template <template <class> class InternalContainer, class T>
class TupleContainer;


template <template <class> class InternalContainer, class... Types>
class TupleContainer<InternalContainer, std::tuple<Types...>> {
 public:
  using value_type = std::tuple<Types...>;

  using reference_type = ranges::common_tuple<Types&...>;

  using size_type = std::size_t;

  using difference_type = std::ptrdiff_t;


  using allocator_type = void;

  constexpr TupleContainer() = default;


  explicit constexpr TupleContainer(size_type count) : sequences_{((void)sizeof(Types), count)...} {}

  template <typename I, typename S>
  constexpr TupleContainer(I first, S last) {
    assign(first, last);
  }

  constexpr TupleContainer(std::initializer_list<value_type> init) { assign(init.begin(), init.end()); }

  [[nodiscard]] constexpr bool empty() const noexcept { return std::get<0>(sequences_).empty(); }

  [[nodiscard]] constexpr size_type size() const noexcept { return std::get<0>(sequences_).size(); }

  [[nodiscard]] constexpr size_type capacity() const noexcept { return std::get<0>(sequences_).capacity(); }

  constexpr void clear() noexcept {
    std::apply([](auto&&... containers) { (containers.clear(), ...); }, sequences_);
  }


  template <typename I, typename S>
  constexpr void assign(I first, S last) {
    auto range = ranges::make_subrange(first, last);
    static_assert(ranges::input_range<decltype(range)>);
    if constexpr (ranges::sized_range<decltype(range)>) {
      resize(ranges::size(range));
      ranges::copy(range, begin());
    } else {
      // Optimization to copy as much as we can before we start back inserting.
      // Back insertion time is severely punished by having multiple containers.
      //
      // There are two bad cases for this implementation:
      // - The capacity is too large compared to the size of the input range, so
      //   we allocate and default construct unnecessarily.
      // - The capacity is too low compared to the size of the input range, so
      //   there will be a lot of back inserting.
      //
      // If common guidelines of calling reserve with the expected size are followed,
      // then this is quite fast, even when we don't know the exact size of the range
      // in advance.
      resize(capacity());
      // Copy elements until we reach current capacity.
      auto limited_range = range | ranges::views::take(size());
      auto [last_in, last_out] = ranges::copy(limited_range, begin());
      const auto copied_size = static_cast<size_type>(ranges::distance(begin(), last_out));
      if (size() == copied_size) {
        // Back insert the remaining elements if any.
        ranges::copy(last_in.base(), last, ranges::back_inserter(*this));
      } else {
        // Remove extra elements by resizing to the correct size.
        resize(copied_size);
      }
    }
  }

  template <typename R>
  constexpr void assign_range(R&& range) {
    assign(ranges::begin(range), ranges::end(range));
  }


  constexpr void reserve(size_type new_cap) {
    std::apply([new_cap](auto&&... containers) { (containers.reserve(new_cap), ...); }, sequences_);
  }


  constexpr void resize(size_type count) {
    std::apply([count](auto&&... containers) { (containers.resize(count), ...); }, sequences_);
  }


  constexpr void push_back(const value_type& value) {
    push_back_impl(value, std::make_index_sequence<sizeof...(Types)>());
  }

  constexpr void push_back(value_type&& value) {
    push_back_impl(std::move(value), std::make_index_sequence<sizeof...(Types)>());
  }

  [[nodiscard]] constexpr auto begin() const { return all().begin(); }

  [[nodiscard]] constexpr auto end() const { return all().end(); }

  [[nodiscard]] constexpr auto begin() { return all().begin(); }

  [[nodiscard]] constexpr auto end() { return all().end(); }

 private:
  std::tuple<InternalContainer<Types>...> sequences_;

  template <typename T, std::size_t... Ids>
  constexpr void push_back_impl(T value, std::index_sequence<Ids...>) {
    (std::get<Ids>(sequences_).push_back(std::get<Ids>(value)), ...);
  }

  [[nodiscard]] constexpr auto all() const {
    return std::apply([](auto&... containers) { return beluga::views::zip(containers...); }, sequences_);
  }

  [[nodiscard]] constexpr auto all() {
    return std::apply([](auto&... containers) { return beluga::views::zip(containers...); }, sequences_);
  }
};

template <class T>
using Vector = std::vector<T, std::allocator<T>>;


template <class T>
class TupleVector : public TupleContainer<Vector, T> {
  using TupleContainer<Vector, T>::TupleContainer;
};

template <class I, class S, typename = std::enable_if_t<ranges::input_iterator<I> && ranges::input_iterator<S>>>
TupleVector(I, S) -> TupleVector<decay_tuple_like_t<ranges::iter_value_t<I>>>;

}  // namespace beluga

#endif