chain_range.h

#pragma once

#include "nanorange.hpp"
#include "utility.h"

namespace ublib {

template <typename... Iterables>
class chain_iterator {
  template <typename Iterable>
  struct range {
    nano::iterator_t<Iterable> first_;
    nano::iterator_t<Iterable> it;
    nano::sentinel_t<Iterable> last_;

    auto first() const { return first_; }
    auto last() const { return last_; }
  };

  std::size_t index_;
  std::tuple<range<Iterables>...> underlying_;

public:
  struct sentinel {};

  using iterator_category = std::common_type_t<
      nano::iterator_category_t<nano::iterator_t<Iterables>>...>;
  using value_type =
      std::common_type_t<nano::value_type_t<nano::iterator_t<Iterables>>...>;
  using reference =
      common_vctype_t<nano::reference_t<nano::iterator_t<Iterables>>...>;
  using difference_type = std::ptrdiff_t;
  using size_type = std::size_t;

  chain_iterator() = default;

  chain_iterator(Iterables &... its)
      : index_(0), underlying_(range<Iterables>{
                       nano::begin(its), nano::begin(its), nano::end(its)}...) {
  }

  chain_iterator &operator=(sentinel) {
    auto const set_to_end = [](auto &r) { nano::advance(r.it, r.last()); };
    for (; index_ < sizeof...(Iterables); ++index_) {
      call_nth(index_, set_to_end, underlying_);
    }
    return *this;
  }

  chain_iterator &operator++() {
    auto const lam = [](auto &rng) {
      ++rng.it;
      return rng.it == rng.last();
    };
    bool const should_increment = call_nth(index_, lam, underlying_);
    if (should_increment) {
      ++index_;
    }
    return *this;
  }
  chain_iterator operator++(int) {
    auto old = *this;
    operator++();
    return old;
  }

  chain_iterator &operator--() {
    auto const should_decrement = [](auto const &rng) {
      return rng.it == rng.first();
    };
    while (call_nth(index_, should_decrement, underlying_)) {
      --index_;
    }
    auto const decrement_internal = [](auto &rng) { --rng.it; };
    call_nth(index_, decrement_internal, underlying_);
    return *this;
  }
  chain_iterator operator--(int) {
    auto old = *this;
    operator--();
    return old;
  }

  chain_iterator &operator+=(difference_type d) {
    if (d < 0) {
      if (d == std::numeric_limits<difference_type>::lowest()) {
        throw 0;
      }
      return operator-=(-d);
    }

    auto const lam = [this](auto &rng, auto diff) {
      auto cur_diff = rng.last() - rng.it;
      if (cur_diff < diff) {
        rng.it += cur_diff; // set to end
        ++index_;
        return diff - cur_diff;
      } else {
        rng.it += diff;
        if (diff == cur_diff) {
          ++index_;
        }
        return difference_type(0);
      }
    };
    for (auto diff = d; diff != 0;) {
      diff = call_nth_or(
          index_, [=](auto &r) { return lam(r, diff); }, diff, underlying_);
    }
    return *this;
  }
  chain_iterator &operator-=(difference_type d) {
    if (d < 0) {
      if (d == std::numeric_limits<difference_type>::lowest()) {
        throw 0;
      }
      return operator+=(-d);
    }

    auto const lam = [this](auto &rng, auto diff) {
      auto cur_diff = rng.it - rng.first();
      if (cur_diff < diff) {
        rng.it -= cur_diff; // set to begin
        --index_;
        return diff - cur_diff;
      } else {
        rng.it -= diff;
        return difference_type(0);
      }
    };
    for (auto diff = d; diff != 0;) {
      diff = call_nth_or(
          index_, [=](auto &r) { return lam(r, diff); }, diff, underlying_);
    }
    return *this;
  }

  friend difference_type
  operator-(chain_iterator const &i1, chain_iterator const &i2) {
    auto const dist = [](auto const &r1, auto const &r2) {
      return r1.it - r2.it;
    };

    auto index = i1.index_;
    if (index < i2.index_) {
      difference_type total_dist = 0;
      while (index < i2.index_ and index < sizeof...(Iterables)) {
        total_dist += call_nth(index, dist, i1.underlying_, i2.underlying_);
        ++index;
      }
      return total_dist;
    } else if (index == i2.index_) {
      if (index == sizeof...(Iterables)) {
        return 0;
      } else {
        return call_nth(index, dist, i1.underlying_, i2.underlying_);
      }
    } else {
      difference_type total_dist = 0;
      if (index == sizeof...(Iterables)) {
        --index;
      }
      while (index > i2.index_) {
        total_dist += call_nth(index, dist, i1.underlying_, i2.underlying_);
        --index;
      }
      return total_dist;
    }
  }

  friend difference_type operator-(chain_iterator const &i, sentinel) {
    auto const dist = [](auto const &r) { return r.it - r.last(); };

    difference_type ret = 0;
    for (auto index = i.index_; index < sizeof...(Iterables); ++index) {
      ret += call_nth(index, dist, i.underlying_);
    }
    return ret;
  }

  reference operator*() const {
    auto const lam = [](auto &rng) -> decltype(auto) { return *rng.it; };
    return call_nth(index_, lam, underlying_);
  }
  reference operator[](difference_type dt) const {
    auto tmp = *this;
    tmp += dt;
    return *tmp;
  }

  friend bool operator==(chain_iterator const &i1, chain_iterator const &i2) {
    if (i1.index_ != i2.index_) {
      return false;
    }

    if (i1.index_ == sizeof...(Iterables)) {
      return true;
    }

    auto const lam = [](auto const &r1, auto const &r2) {
      return r1.it == r2.it;
    };
    return call_nth(i1.index_, lam, i1.underlying_, i2.underlying_);
  }
  friend bool operator==(chain_iterator const &i, sentinel) {
    return i.index_ == sizeof...(Iterables);
  }
  friend bool operator<(chain_iterator const &i1, chain_iterator const &i2) {
    if (i1.index_ < i2.index_) {
      return true;
    } else if (i2.index_ < i1.index_) {
      return false;
    } else {
      auto const lam = [](auto &r1, auto &r2) { return r1.it < r2.it; };
      return call_nth(i1.index_, lam, i1.underlying_, i2.underlying_);
    }
  }
  friend bool operator>(chain_iterator const &i1, chain_iterator const &i2) {
    if (i1.index_ > i2.index_) {
      return true;
    } else if (i2.index_ > i1.index_) {
      return false;
    } else {
      auto const lam = [](auto &r1, auto &r2) { return r1.it > r2.it; };
      return call_nth(i1.index_, lam, i1.underlying_, i2.underlying_);
    }
  }
};

template <typename... Iterables>
bool operator==(
    typename chain_iterator<Iterables...>::sentinel s,
    chain_iterator<Iterables...> const &i) {
  return i == s;
}

template <typename... Iterables>
bool operator!=(
    chain_iterator<Iterables...> const &i1,
    chain_iterator<Iterables...> const &i2) {
  return not(i1 == i2);
}
template <typename... Iterables>
bool operator!=(
    chain_iterator<Iterables...> const &i,
    typename chain_iterator<Iterables...>::sentinel s) {
  return not(i == s);
}
template <typename... Iterables>
bool operator!=(
    typename chain_iterator<Iterables...>::sentinel s,
    chain_iterator<Iterables...> const &i) {
  return i != s;
}

template <typename... Iterables>
bool operator<=(
    chain_iterator<Iterables...> const &i1,
    chain_iterator<Iterables...> const &i2) {
  return i2 > i1;
}
template <typename... Iterables>
bool operator>=(
    chain_iterator<Iterables...> const &i1,
    chain_iterator<Iterables...> const &i2) {
  return i2 < i1;
}

template <typename... Iterables>
bool operator<(
    chain_iterator<Iterables...> i,
    typename chain_iterator<Iterables...>::sentinel s) {
  return i != s;
}
template <typename... Iterables>
bool operator<(
    typename chain_iterator<Iterables...>::sentinel s,
    chain_iterator<Iterables...> i) {
  return false;
}
template <typename... Iterables>
bool operator>(
    chain_iterator<Iterables...> i,
    typename chain_iterator<Iterables...>::sentinel s) {
  return false;
}
template <typename... Iterables>
bool operator>(
    typename chain_iterator<Iterables...>::sentinel s,
    chain_iterator<Iterables...> i) {
  return i < s;
}
template <typename... Iterables>
bool operator<=(
    chain_iterator<Iterables...> i,
    typename chain_iterator<Iterables...>::sentinel s) {
  return true;
}
template <typename... Iterables>
bool operator<=(
    typename chain_iterator<Iterables...>::sentinel s,
    chain_iterator<Iterables...> i) {
  return i == s;
}
template <typename... Iterables>
bool operator>=(
    chain_iterator<Iterables...> i,
    typename chain_iterator<Iterables...>::sentinel s) {
  return i == s;
}
template <typename... Iterables>
bool operator>=(
    typename chain_iterator<Iterables...>::sentinel s,
    chain_iterator<Iterables...> i) {
  return true;
}

template <typename... Iterables>
chain_iterator<Iterables...> operator+(
    chain_iterator<Iterables...> const &i,
    typename chain_iterator<Iterables...>::difference_type dt) {
  return chain_iterator<Iterables...>(i) += dt;
}
template <typename... Iterables>
chain_iterator<Iterables...> operator+(
    typename chain_iterator<Iterables...>::difference_type dt,
    chain_iterator<Iterables...> const &i) {
  return dt + i;
}

template <typename... Iterables>
auto operator-(
    typename chain_iterator<Iterables...>::sentinel s,
    chain_iterator<Iterables...> i) {
  return -(i - s);
}

template <typename... Iterables>
chain_iterator<Iterables...> operator-(
    chain_iterator<Iterables...> const &i,
    typename chain_iterator<Iterables...>::difference_type dt) {
  return chain_iterator<Iterables...>(i) -= dt;
}

template <typename... Iterables>
class chain {
  std::tuple<Iterables &...> underlying_;

public:
  using iterator = chain_iterator<Iterables...>;
  using sentinel = typename iterator::sentinel;

  chain(Iterables &... iterables) : underlying_(iterables...) {}

  iterator begin() {
    auto const lam = [](auto &... its) { return iterator(its...); };
    return std::apply(lam, underlying_);
  }
  sentinel end() { return sentinel(); }
};

} // namespace ublib

main.cpp

#include "include/chain_range.h"
#include "include/nanorange.hpp"
#include "include/utility.h"

#include <array>
#include <iostream>
#include <tuple>
#include <type_traits>
#include <utility>

int main() {
  auto arr1 = std::array{4, 9, 7};
  auto arr2 = std::array{5, 2, 1, 10};
  auto arr3 = std::array{6, 8, 3};

  auto chn = ublib::chain(arr1, arr2, arr3);

  nano::sort(ublib::chain(arr1, arr2, arr3));

  nano::copy(
      ublib::chain(arr1, arr2, arr3),
      nano::ostream_iterator<int>(std::cout, "\n"));
  return 0;
}

utility.h

#pragma once

#include <tuple>
#include <type_traits>

namespace ublib {

template <typename T>
T declvc() noexcept;

template <typename... Ts>
struct common_vctype {};

template <typename... Ts>
using common_vctype_t = typename common_vctype<Ts...>::type;

template <typename T>
struct common_vctype<T> {
  using type = T;
};

template <typename T, typename... Ts>
struct common_vctype<T, Ts...> {
  using type = decltype(false ? declvc<T>() : declvc<common_vctype_t<Ts...>>());
};

template <typename... Ts>
struct all_same;

template <>
struct all_same<> : std::true_type {};
template <typename T>
struct all_same<T> : std::true_type {};
template <typename T, typename... Ts>
struct all_same<T, T, Ts...> : all_same<T, Ts...> {};
template <typename T, typename U, typename... Ts>
struct all_same<T, U, Ts...> : std::false_type {};

template <typename... Ts>
constexpr static bool all_same_v = all_same<Ts...>::value;

namespace impl {

  struct call_nth_t {
    template <std::size_t Idx, typename F, typename... Tups>
    struct ret_type_idx {
      using type =
          decltype(std::declval<F>()(std::get<Idx>(std::declval<Tups>())...));
    };

    template <typename... Tups>
    constexpr static std::size_t min_size =
        std::min({std::tuple_size_v<std::remove_reference_t<Tups>>...});

    template <typename F, typename... Tups>
    struct ret_type {
      template <typename T>
      struct expand_idx;
      template <std::size_t... Idxs>
      struct expand_idx<std::index_sequence<Idxs...>> {
        using type =
            common_vctype_t<typename ret_type_idx<Idxs, F, Tups...>::type...>;
      };

      using type = typename expand_idx<
          std::make_index_sequence<min_size<Tups...>>>::type;
    };

    template <typename F, typename... Tups>
    using ret_type_t = typename ret_type<F, Tups...>::type;

    template <std::size_t Idx, typename Function, typename... Tups>
    static auto helper(std::size_t n, Function &f, Tups &&... tups)
        -> ret_type_t<Function, Tups...> {
      if constexpr (min_size<Tups...> <= Idx) {
        throw 0;
      } else if (n == Idx) {
        return std::move(f)(std::get<Idx>(std::forward<Tups>(tups))...);
      } else {
        return helper<Idx + 1>(n, f, std::forward<Tups>(tups)...);
      }
    }
    struct otherwise {
      template <typename F, typename Otherwise, typename... Tups>
      decltype(auto)
      operator()(std::size_t n, F f, Otherwise &&o, Tups &&... tups) const {
        return (n == min_size<Tups...>)
                   ? std::forward<Otherwise>(o)
                   : call_nth_t::helper<0>(n, f, std::forward<Tups>(tups)...);
      }
    };
    template <typename F, typename... Tups>
    decltype(auto) operator()(std::size_t n, F f, Tups &&... tups) const {
      return call_nth_t::helper<0>(n, f, std::forward<Tups>(tups)...);
    }
  };
} // namespace impl

static constexpr impl::call_nth_t call_nth = impl::call_nth_t();
static constexpr impl::call_nth_t::otherwise call_nth_or =
    impl::call_nth_t::otherwise();

} // namespace ublib