iterators.h

Go to the documentation of this file.

/* *****************************************************************************
 * kblib is a general utility library for C++14 and C++17, intended to provide
 * performant high-level abstractions and more expressive ways to do simple
 * things.
 *
 * Copyright (c) 2021 killerbee
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 * ****************************************************************************/
 
#ifndef KBLIB_ITERATORS_H
#define KBLIB_ITERATORS_H
 
#include "enumerate-contrib-cry.h"
#include "enumerate-contrib-tw.h"
#include "fakestd.h"
#include "traits.h"
 
#include <cassert>
#include <iterator>
#include <vector>
 
#if KBLIB_USE_CXX17
#  include <optional>
#endif
 
namespace kblib {
 
template <typename ptr>
struct to_pointer_impl {
   constexpr auto operator()(ptr&& p) const noexcept -> auto {
      return to_pointer_impl<decltype(p.operator->())>{}(p.operator->());
   }
   constexpr auto operator()(const ptr& p) const noexcept -> auto {
      return to_pointer_impl<decltype(p.operator->())>{}(p.operator->());
   }
};
 
template <typename T>
struct to_pointer_impl<T*> {
   constexpr auto operator()(T* p) const noexcept -> T* { return p; }
};
 
template <typename P>
constexpr auto to_pointer(P&& p) noexcept -> auto* {
   return to_pointer_impl<std::decay_t<P>>{}(p);
}
 
template <typename Container,
          typename Comp = std::less<value_type_linear_t<Container>>>
auto max_element(Container& c, Comp comp) -> value_type_linear_t<Container>* {
   auto it = max_element(std::begin(c), std::end(c), comp);
   if (it != std::end(c)) {
      return to_pointer(it);
   } else {
      return nullptr;
   }
}
template <typename T, typename E, typename = void>
struct is_output_iterator_for : std::false_type {};
 
template <typename T, typename E>
struct is_output_iterator_for<
    T, E, void_t<decltype(*std::declval<T&>()++ = std::declval<const E&>())>>
    : std::true_type {};
 
template <typename Container>
class counting_back_insert_iterator {
 public:
   using value_type = void;
   using difference_type = std::ptrdiff_t;
   using pointer = void;
   using reference = void;
   using iterator_category = std::output_iterator_tag;
 
   counting_back_insert_iterator() noexcept = default;
   explicit counting_back_insert_iterator(Container& c, std::size_t n = 0)
       : container(std::addressof(c))
       , count(n) {}
   explicit counting_back_insert_iterator(std::size_t n)
       : count(n) {}
 
   struct proxy_iterator {
      using value_type = typename Container::value_type;
 
      auto operator=(const value_type& value) & -> proxy_iterator& {
         assert(container);
         // Multiple assignments for a single dereference are not allowed
         assert(*dirty);
         *dirty = false;
         container->push_back(value);
         return *this;
      }
 
      auto operator=(value_type&& value) & -> proxy_iterator& {
         assert(container);
         // Multiple assignments for a single dereference are not allowed
         assert(*dirty);
         *dirty = false;
         container->push_back(std::move(value));
         return *this;
      }
 
      Container* container;
      bool* dirty;
   };
 
   auto operator*() noexcept -> proxy_iterator {
      assert(dirty);
      return {container, &dirty};
   }
 
   auto operator++() & noexcept -> counting_back_insert_iterator& {
      assert(not dirty);
      ++count;
      dirty = true;
      return *this;
   }
   auto operator++(int) noexcept -> counting_back_insert_iterator = delete;
 
   friend auto operator==(const counting_back_insert_iterator& a,
                          const counting_back_insert_iterator& b) noexcept
       -> bool {
      return a.count == b.count;
   }
   friend auto operator!=(const counting_back_insert_iterator& a,
                          const counting_back_insert_iterator& b) noexcept
       -> bool {
      return a.count != b.count;
   }
   friend auto operator<(const counting_back_insert_iterator& a,
                         const counting_back_insert_iterator& b) noexcept
       -> bool {
      return a.count < b.count;
   }
   friend auto operator<=(const counting_back_insert_iterator& a,
                          const counting_back_insert_iterator& b) noexcept
       -> bool {
      return a.count <= b.count;
   }
   friend auto operator>(const counting_back_insert_iterator& a,
                         const counting_back_insert_iterator& b) noexcept
       -> bool {
      return a.count > b.count;
   }
   friend auto operator>=(const counting_back_insert_iterator& a,
                          const counting_back_insert_iterator& b) noexcept
       -> bool {
      return a.count >= b.count;
   }
   friend auto operator-(const counting_back_insert_iterator& a,
                         const counting_back_insert_iterator& b) noexcept
       -> std::ptrdiff_t {
      return std::ptrdiff_t(a.count) - ptrdiff_t(b.count);
   }
 
 protected:
   Container* container = nullptr;
   std::size_t count = 0;
   bool dirty = true;
};
 
template <typename C>
KBLIB_NODISCARD counting_back_insert_iterator<C> counting_back_inserter(
    C& c, std::size_t count = 0) {
   return counting_back_insert_iterator<C>{c, count};
}
 
template <typename Value, typename Delta>
class range_t {
 private:
   Value min, max;
   Delta step;
 
   constexpr static bool nothrow_copyable
       = std::is_nothrow_copy_constructible<Value>::value;
   constexpr static bool nothrow_steppable = noexcept(min + step);
 
 public:
   constexpr range_t(Value min_, Value max_, Delta step_ = 1)
       : min(min_)
       , max(max_)
       , step(step_) {
      normalize();
   }
   constexpr range_t(Value max_)
       : range_t(Value{}, max_, (max_ >= Value{}) ? 1 : -1) {}
 
   struct iterator {
      Value val;
      Delta step;
 
      using difference_type = std::ptrdiff_t;
      using value_type = Value;
      using pointer = const Value*;
      using reference = Value;
      using iterator_category = std::input_iterator_tag;
 
      constexpr auto operator*() const noexcept(nothrow_copyable) -> Value {
         return val;
      }
      constexpr auto operator->() const noexcept -> pointer { return &val; }
      constexpr auto operator++() & noexcept(nothrow_steppable) -> iterator& {
         val = static_cast<Value>(val + step);
         return *this;
      }
      constexpr auto operator++(int) noexcept(nothrow_steppable) -> iterator {
         auto ret = *this;
         val = val + step;
         return ret;
      }
      constexpr friend auto operator==(iterator l, iterator r) noexcept
          -> bool {
         return l.val == r.val and l.step == r.step;
      }
      constexpr friend auto operator!=(iterator l, iterator r) noexcept
          -> bool {
         return l.val != r.val or l.step != r.step;
      }
      constexpr friend auto operator<(iterator l, iterator r) noexcept -> bool {
         if (l.step > 0)
            return l.val < r.val;
         else
            return l.val > r.val;
      }
      constexpr friend auto operator<=(iterator l, iterator r) noexcept
          -> bool {
         return not (r < l);
      }
      constexpr friend auto operator>(iterator l, iterator r) noexcept -> bool {
         return r < l;
      }
      constexpr friend auto operator>=(iterator l, iterator r) noexcept
          -> bool {
         return not (l < r);
      }
      constexpr auto operator[](std::ptrdiff_t x) const noexcept -> Value {
         return static_cast<Value>(val + x * step);
      }
      template <typename Integral>
      constexpr auto operator[](Integral x) const noexcept -> Value {
         return static_cast<Value>(val + std::ptrdiff_t(x) * step);
      }
   };
 
   constexpr auto begin() const noexcept -> iterator { return {min, step}; }
   constexpr auto end() const noexcept -> iterator { return {max, step}; }
 
   constexpr auto size() const noexcept -> std::size_t {
      return static_cast<std::size_t>(std::abs(max - min) / step);
   }
 
   friend constexpr auto begin(const range_t& r) noexcept -> iterator {
      return {r.min, r.step};
   }
   friend constexpr auto end(const range_t& r) noexcept -> iterator {
      return {r.max, r.step};
   }
 
   friend constexpr auto size(const range_t& r) noexcept -> std::size_t {
      return (r.max - r.min) / r.step;
   }
 
   constexpr auto empty() const noexcept -> bool { return size() == 0; }
 
   template <typename Integral>
   constexpr auto operator[](Integral x) const noexcept
       -> decltype(begin()[x]) {
      return begin()[x];
   }
 
   constexpr auto lesser() const noexcept(nothrow_copyable) -> Value {
      return (step > 0) ? max : min;
   }
 
   constexpr auto greater() const noexcept(nothrow_copyable) -> Value {
      return (step > 0) ? min : max;
   }
 
   template <
       typename Container,
       enable_if_t<
           is_linear_container_v<
               Container> and std::is_constructible<Container, iterator, iterator>::value>* = nullptr>
   explicit operator Container() const
       noexcept(noexcept(Container(std::declval<iterator>(),
                                   std::declval<iterator>()))) {
      return Container(begin(), end());
   }
 
   template <
       typename Container,
       enable_if_t<
           is_setlike_v<
               Container> and std::is_constructible<Container, iterator, iterator>::value>* = nullptr>
   explicit operator Container() const
       noexcept(noexcept(Container(std::declval<iterator>(),
                                   std::declval<iterator>()))) {
      return Container(begin(), end());
   }
 
   constexpr friend auto operator==(range_t l, range_t r) noexcept -> bool {
      return (l.empty() and r.empty())
             or ((l.begin() == r.begin()) and (l.end() == r.end())
                 and (l.step == r.step));
   }
   constexpr friend auto operator!=(range_t l, range_t r) noexcept -> bool {
      return not (l == r);
   }
 
 private:
   template <typename T>
   static constexpr enable_if_t<not std::is_signed<T>::value, std::true_type>
   positive(const T&) {
      return {};
   }
   template <typename T>
   static constexpr enable_if_t<std::is_signed<T>::value, bool> positive(T v) {
      return v >= 0;
   }
   template <typename R, typename T,
             enable_if_t<std::is_integral<R>::value
                         and std::is_integral<T>::value>* = nullptr>
   static constexpr auto signed_cast(T v) {
      return kblib::signed_cast<R>(v);
   }
   template <typename R, typename T,
             enable_if_t<not (std::is_integral<R>::value
                              and std::is_integral<T>::value)>* = nullptr>
   static constexpr auto signed_cast(T v) {
      return v;
   }
 
   constexpr auto normalize() noexcept(nothrow_steppable) -> void {
      if (min == max) {
      } else if (step == 0) {
         if (min != std::numeric_limits<Value>::max()) {
            max = min + 1;
         } else {
            max = min - 1;
         }
      } else {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wsign-conversion"
#pragma GCC diagnostic ignored "-Wconversion"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wimplicit-int-conversion"
#pragma GCC diagnostic ignored "-Wshorten-64-to-32"
         auto difference = max - min;
         std::ptrdiff_t sign = (step > 0) ? 1 : -1;
         if ((sign * to_signed(difference)) <= (sign * step)) {
            step = sign;
            max = min + step;
         } else {
            auto remainder = difference % step;
            if (remainder != 0) {
               max = max - remainder;
               assert(not (positive(max)
                           and (signed_cast<Delta>(
                                    std::numeric_limits<Value>::max() - max)
                                < step)));
               max = max + step;
            }
         }
#pragma GCC diagnostic pop
      }
   }
};
 
namespace detail_iterators {
   template <typename T, typename U, typename = void>
   struct is_addable : std::false_type {};
 
   template <typename T, typename U>
   struct is_addable<T, U,
                     void_t<decltype(std::declval<T&>() + std::declval<U&>())>>
       : std::true_type {};
} // namespace detail_iterators
 
struct adjuster {
   std::ptrdiff_t adj;
   constexpr adjuster(std::ptrdiff_t adj_) noexcept
       : adj(adj_) {}
   constexpr operator std::ptrdiff_t() const noexcept { return adj; }
};
 
template <typename T>
constexpr auto operator+(T val, adjuster a) noexcept
    -> enable_if_t<not detail_iterators::is_addable<T, std::ptrdiff_t>::value,
                   decltype(std::advance(val, a.adj))> {
   return std::advance(val, a.adj);
}
 
struct incrementer {
   constexpr incrementer() noexcept = default;
   constexpr incrementer(int) noexcept {}
   constexpr operator int() const noexcept { return 1; }
   friend constexpr auto operator*(std::ptrdiff_t x, incrementer) {
      return adjuster{x};
   }
 
   template <typename T>
   constexpr auto operator()(T& t) -> T& {
      return ++t;
   }
};
 
template <typename T>
constexpr auto operator+(T val, incrementer) -> T {
   return ++val;
}
 
struct decrementer {
   constexpr decrementer() noexcept = default;
   constexpr decrementer(int) noexcept {}
   constexpr operator int() const noexcept { return -1; }
   friend constexpr auto operator*(std::ptrdiff_t x, decrementer) {
      return adjuster{-x};
   }
   template <typename T>
   constexpr auto operator()(T& t) -> T& {
      return --t;
   }
};
 
template <typename T>
constexpr auto operator+(T val, decrementer) -> T {
   return --val;
}
 
template <typename Value, typename Delta = int>
constexpr auto range(Value min, Value max, Delta step = 0)
    -> range_t<Value, Delta> {
   if (step == 0) {
      if (min <= max) {
         return {min, max, 1};
      } else {
         return {min, max, -1};
      }
   } else {
      return {min, max, step};
   }
}
 
template <typename Value>
constexpr auto range(Value max) -> range_t<Value, incrementer> {
   return {max};
}
 
#if KBLIB_USE_CXX17
 
template <typename Value, typename Delta>
class irange_t {
 public:
   Value min, max;
   Delta step;
 
   constexpr static bool nothrow_copyable
       = std::is_nothrow_copy_constructible<Value>::value;
   constexpr static bool nothrow_steppable = noexcept(min + step);
};
 
template <typename Value, typename Delta = int>
constexpr auto irange(Value, Value, Delta = 0) {}
 
template <typename T>
class enumerator_iterator;
 
namespace detail_enumerate {
 
   template <typename T1, typename T2>
   auto get_or(T1&& t1, T2&& t2) -> decltype(auto) {
      return t1 ? *t1 : *t2;
   }
 
   struct force_copy_tag {};
   // Get a pointer which is guaranteed to be invalid to use (but not UB to
   // merely store)
   template <typename T>
   auto get_magic_ptr() -> T* {
      static const char enumeration_magic_pointer = '\0';
      return reinterpret_cast<T*>(
          const_cast<char*>(&enumeration_magic_pointer));
   }
 
} // namespace detail_enumerate
 
template <typename T>
class enumeration {
 public:
   enumeration() = default;
 
   enumeration(const enumeration& other)
       : idx(other.idx)
       , local([&] {
          assert(other.source or other.local);
          assert(other.source != detail_enumerate::get_magic_ptr<T>());
          return other.copied();
       }())
       , source(nullptr) {}
   enumeration(volatile enumeration& other)
       : enumeration(const_cast<const enumeration&>(other)) {}
 
   enumeration(enumeration&&) = delete;
   auto operator=(const enumeration&) = delete;
   auto operator=(enumeration&&) = delete;
 
   ~enumeration() = default;
 
 private:
   enumeration(detail_enumerate::force_copy_tag, std::size_t i)
       : idx(i) {}
 
 public:
   auto index() const noexcept -> std::size_t { return idx; }
 
   auto copied() & noexcept -> std::remove_const_t<T>& {
      assert(source != detail_enumerate::get_magic_ptr<T>());
      assert(local);
      return *local;
   }
   auto copied() const& noexcept -> const T& {
      assert(source != detail_enumerate::get_magic_ptr<T>());
      return detail_enumerate::get_or(local, source);
   }
 
   auto reffed() & noexcept -> T& {
      assert(source != detail_enumerate::get_magic_ptr<T>());
      return detail_enumerate::get_or(local, source);
   }
   auto reffed() const& noexcept -> const T& {
      assert(source != detail_enumerate::get_magic_ptr<T>());
      return detail_enumerate::get_or(local, source);
   }
 
 private:
   auto set(T* t) & -> void { source = t; }
 
   auto advance() & noexcept -> void {
      ++idx;
      source = detail_enumerate::get_magic_ptr<T>();
      local = std::nullopt;
   }
 
   std::size_t idx = 0;
   mutable std::optional<std::remove_const_t<T>> local = std::nullopt;
   T* source = detail_enumerate::get_magic_ptr<T>();
 
   template <typename>
   friend class enumerator_iterator;
};
} // namespace kblib
 
namespace std {
#  if defined(__clang__)
// Fix from: https://github.com/nlohmann/json/issues/1401
#     pragma clang diagnostic push
#     pragma clang diagnostic ignored "-Wmismatched-tags"
#  endif
 
template <typename T>
class tuple_size<::kblib::enumeration<T>>
    : public std::integral_constant<std::size_t, 2> {};
 
template <typename T>
class tuple_element<0, ::kblib::enumeration<T>> {
 public:
   using type = std::size_t;
};
template <typename T>
class tuple_element<0, volatile ::kblib::enumeration<T>> {
 public:
   using type = std::size_t;
};
template <typename T>
class tuple_element<0, const volatile ::kblib::enumeration<T>> {
 public:
   using type = const std::size_t;
};
 
template <typename T>
class tuple_element<1, volatile ::kblib::enumeration<T>> {
 public:
   using type = T;
};
template <typename T>
class tuple_element<1, const volatile ::kblib::enumeration<T>> {
 public:
   using type = const T;
};
template <typename T>
class tuple_element<1, ::kblib::enumeration<T>> {
 public:
   using type = std::remove_const_t<T>;
};
template <typename T>
class tuple_element<1, const ::kblib::enumeration<T>> {
 public:
   using type = const T;
};
 
#  if defined(__clang__)
#     pragma clang diagnostic pop
#  endif
 
} // namespace std
 
namespace kblib {
 
// When a structured binding is created by value, this function is called as if
// by get<i>(std::move(e)), so it does not call the lvalue reference function.
// I have no idea why it's implicitly moved, but it works for my purposes.
template <std::size_t I, typename T>
auto get(enumeration<T>&& e) -> decltype(auto) {
   static_assert(I <= 1, "enumeration only has two elements");
   if constexpr (I == 0) {
      return e.index();
   } else {
      return e.copied();
   }
}
template <std::size_t I, typename T>
auto get(const enumeration<T>&& e) -> decltype(auto) {
   static_assert(I <= 1, "enumeration only has two elements");
   if constexpr (I == 0) {
      return e.index();
   } else {
      return e.copied();
   }
}
// When captured by reference, the volatile qualifier is added, which allows
// std::tuple_element to detect the copying-nonconst-from-const case.
template <std::size_t I, typename T>
auto get(volatile enumeration<T>& e) -> decltype(auto) {
   static_assert(I <= 1, "enumeration only has two elements");
   if constexpr (I == 0) {
      return const_cast<enumeration<T>&>(e).index();
   } else {
      return const_cast<enumeration<T>&>(e).reffed();
   }
}
 
template <std::size_t I, typename T>
auto get(const volatile enumeration<T>& e) -> decltype(auto) {
   static_assert(I <= 1, "enumeration only has two elements");
   if constexpr (I == 0) {
      return const_cast<const enumeration<T>&>(e).index();
   } else {
      return const_cast<const enumeration<T>&>(e).reffed();
   }
}
 
template <typename It>
class enumerator_iterator {
 public:
   using nested_value
       = copy_const_t<decltype(*std::declval<It&>()),
                      typename std::iterator_traits<It>::value_type>;
 
   using value_type = enumeration<nested_value>;
   using difference_type = std::ptrdiff_t;
   using pointer = const value_type*;
   using reference = const value_type&;
   using iterator_category = std::input_iterator_tag;
 
   enumerator_iterator() = default;
   enumerator_iterator(const enumerator_iterator& other)
       : enumerator_iterator(detail_enumerate::force_copy_tag{},
                             other.curr_.idx, other.it_) {}
   enumerator_iterator(It it)
       : it_(it) {}
 
   enumerator_iterator(enumerator_iterator&&) = default;
   auto operator=(const enumerator_iterator&) -> enumerator_iterator& = default;
   auto operator=(enumerator_iterator&&) -> enumerator_iterator& = default;
 
   ~enumerator_iterator() = default;
 
   auto operator*() & -> volatile value_type& {
      if (not captured) {
         curr_.set(to_pointer(it_));
         captured = true;
      }
      return curr_;
   }
   auto operator++() & -> enumerator_iterator& {
      curr_.advance();
      captured = false;
      ++it_;
      return *this;
   }
 
   friend auto operator==(const enumerator_iterator& lhs,
                          const enumerator_iterator& rhs) noexcept -> bool {
      return lhs.it_ == rhs.it_;
   }
   friend auto operator!=(const enumerator_iterator& lhs,
                          const enumerator_iterator& rhs) noexcept -> bool {
      return lhs.it_ != rhs.it_;
   }
 
 private:
   enumerator_iterator(detail_enumerate::force_copy_tag t, std::size_t idx,
                       It it)
       : it_(it)
       , curr_(t, idx) {}
 
   It it_;
   bool captured = false;
   value_type curr_;
};
 
template <typename Range, typename = void>
class enumerator_t;
 
template <typename Range>
class enumerator_t<Range, void> {
 public:
   detail::no_dangle_t<Range> r;
 
   using range_t = typename std::remove_reference_t<Range>;
   using nested_iterator = decltype(r.begin());
   using nested_end_iterator = decltype(r.end());
   using iterator = enumerator_iterator<nested_iterator>;
   using end_iterator = enumerator_iterator<nested_end_iterator>;
 
   using nested_const_iterator = typename range_t::const_iterator;
   using const_iterator = enumerator_iterator<nested_const_iterator>;
 
   auto begin() const& noexcept(noexcept(r.cbegin())) -> const_iterator {
      return r.cbegin();
   }
   auto begin() & noexcept(noexcept(r.begin())) -> iterator {
      return r.begin();
   }
 
   auto end() const& noexcept(noexcept(r.cend())) -> const_iterator {
      return r.cend();
   }
   auto end() & noexcept(noexcept(r.end())) -> end_iterator { return r.end(); }
};
 
template <typename It, typename EndIt>
class enumerator_t {
 public:
   using nested_iterator = It;
   using iterator = enumerator_iterator<nested_iterator>;
   using end_iterator = enumerator_iterator<EndIt>;
 
   auto begin() const& noexcept -> iterator { return {r_begin}; }
 
   auto end() const& noexcept -> end_iterator { return {r_end}; }
 
   It r_begin;
   EndIt r_end;
};
 
template <typename It, typename EIt>
auto magic_enumerate(It begin, EIt end) -> enumerator_t<It, EIt> {
   return {begin, end};
}
 
template <typename Range>
auto magic_enumerate(Range&& r) -> auto {
   if constexpr (std::is_lvalue_reference_v<Range&&>) {
      using std::begin;
      using std::end;
      return magic_enumerate(begin(r), end(r));
   } else {
      return enumerator_t<Range&&>{std::forward<Range>(r)};
   }
}
 
#endif
 
template <typename Iter1, typename Iter2>
struct indirect_range {
   Iter1 begin_;
   Iter2 end_;
 
   using value_type = decltype(*begin_);
 
   constexpr auto begin() const noexcept -> Iter1 { return begin_; }
   constexpr auto end() const noexcept -> Iter2 { return end_; }
   constexpr auto rbegin() const noexcept -> auto {
      return std::make_reverse_iterator(begin_);
   }
   constexpr auto rend() const noexcept -> auto {
      return std::make_reverse_iterator(end_);
   }
 
   constexpr friend auto begin(const indirect_range& r) noexcept -> Iter1 {
      return r.begin_;
   }
   constexpr friend auto end(const indirect_range& r) noexcept -> Iter2 {
      return r.end_;
   }
};
 
template <typename Iter1, typename Iter2>
constexpr auto indirect(Iter1 begin, Iter2 end) noexcept(noexcept(
    indirect_range<Iter1, Iter2>{begin, end})) -> indirect_range<Iter1, Iter2> {
   return {begin, end};
}
 
#if KBLIB_USE_CXX17
 
template <typename Iter1, typename Iter2>
indirect_range(Iter1, Iter2) -> indirect_range<Iter1, Iter2>;
 
template <typename Iter1, typename Iter2>
auto cry_enumerate(Iter1 begin, Iter2 end) -> auto {
   return cry_enumerate(indirect_range{begin, end});
}
 
#endif
 
// Fixed number of ranges
template <typename Iter1, typename EndIter = Iter1, std::size_t count = 0>
class multi_range {
 public:
 private:
   struct range {
      Iter1 begin;
      EndIter end;
   };
 
   std::array<range, count> ranges;
};
 
// Dynamic number of ranges
template <typename Iter1, typename EndIter>
class multi_range<Iter1, EndIter, 0> {
 public:
 private:
   struct range {
      Iter1 begin;
      EndIter end;
   };
 
   std::vector<range> ranges;
};
 
template <typename T>
struct containing_ptr {
   constexpr auto operator*() noexcept -> T& { return val; }
   constexpr auto operator*() const noexcept -> const T& { return val; }
 
   constexpr auto operator->() noexcept -> T* { return &val; }
   constexpr auto operator->() const noexcept -> const T* { return &val; }
 
   constexpr auto get() noexcept -> T* { return &val; }
   constexpr auto get() const noexcept -> const T* { return &val; }
 
   T val;
};
 
#if KBLIB_USE_CXX17
 
template <typename base_iterator, typename operation>
class transform_iterator {
 private:
   base_iterator it;
   operation op;
 
 public:
   using difference_type = std::ptrdiff_t;
   using result_type = decltype(kblib::invoke(op, *it));
   using const_result_type
       = decltype(kblib::invoke(std::as_const(op), *std::as_const(it)));
   using value_type = result_type;
   using pointer = void;
   using reference = value_type;
   using iterator_category = std::input_iterator_tag;
 
   transform_iterator(base_iterator _it,
                      operation _op) noexcept(noexcept(base_iterator{
       _it}) and noexcept(std::is_nothrow_move_constructible<operation>::value))
       : it(_it)
       , op(std::move(_op)) {}
 
   transform_iterator(base_iterator end_it) noexcept(noexcept(base_iterator{
       end_it}))
       : it(end_it)
       , op() {}
 
   auto operator*() noexcept(noexcept(kblib::invoke(op, *it)))
       -> decltype(auto) {
      return kblib::invoke(op, *it);
   }
   decltype(auto) operator*() const noexcept(noexcept(kblib::invoke(op, *it))) {
      return kblib::invoke(op, *it);
   }
 
   auto operator->() noexcept(noexcept(kblib::invoke(op, *it))) -> auto {
      return containing_ptr<result_type>{{kblib::invoke(op, *it)}};
   }
   auto operator->() const noexcept(noexcept(kblib::invoke(op, *it))) -> auto {
      return containing_ptr<const_result_type>{{kblib::invoke(op, *it)}};
   }
 
   auto operator++() noexcept(noexcept(++it)) -> transform_iterator& {
      ++it;
      return *this;
   }
 
   [[deprecated("Needlessly copies op. Use preincrement instead.")]] auto
   operator++(int) noexcept(noexcept(transform_iterator{it++, op}))
       -> transform_iterator {
      return {it++, op};
   }
 
   auto base() const noexcept -> base_iterator { return it; }
 
   friend auto operator==(const transform_iterator& lhs,
                          const transform_iterator& rhs) noexcept -> bool {
      return lhs.it == rhs.it;
   }
 
   friend auto operator!=(const transform_iterator& lhs,
                          const transform_iterator& rhs) noexcept -> bool {
      return lhs.it != rhs.it;
   }
 
   template <typename OIt>
   friend auto operator==(const transform_iterator& lhs,
                          const OIt& rhs) noexcept -> bool {
      return lhs.base() == rhs;
   }
   template <typename OIt>
   friend auto operator==(const OIt& lhs,
                          const transform_iterator& rhs) noexcept -> bool {
      return lhs == rhs.base();
   }
 
   template <typename OIt>
   friend auto operator!=(const transform_iterator& lhs,
                          const OIt& rhs) noexcept -> bool {
      return lhs.base() != rhs;
   }
   template <typename OIt>
   friend auto operator!=(const OIt& lhs,
                          const transform_iterator& rhs) noexcept -> bool {
      return lhs != rhs.base();
   }
};
 
template <typename It, typename operation>
transform_iterator(It, operation) -> transform_iterator<It, operation>;
 
template <typename base_iterator, typename operation>
[[deprecated("use transformer instead")]] auto make_transform_iterator(
    base_iterator it,
    operation
        op) noexcept(noexcept(transform_iterator<base_iterator, operation>{
    it, std::move(op)})) -> transform_iterator<base_iterator, operation> {
   return {it, std::move(op)};
}
 
template <typename base_iterator, typename operation>
auto transformer(base_iterator it, operation op) noexcept(
    noexcept(transform_iterator<base_iterator, operation>{it, std::move(op)}))
    -> transform_iterator<base_iterator, operation> {
   return {it, std::move(op)};
}
 
template <typename It, typename EndIt, typename operation>
auto transform_range(It begin, EndIt end, operation op) noexcept(
    noexcept(indirect(transform_iterator{begin, op}, end))) -> auto {
   return indirect(transform_iterator{begin, op}, end);
}
#endif
 
template <typename InputIt1, typename EndIt, typename InputIt2>
struct zip_iterator {
   InputIt1 pos1{};
   EndIt end1{};
   InputIt2 pos2{};
 
   constexpr static bool is_nothrow_copyable
       = std::is_nothrow_copy_constructible<InputIt1>::value
         and std::is_nothrow_copy_constructible<EndIt>::value
         and std::is_nothrow_copy_constructible<InputIt2>::value;
 
   auto operator++() noexcept(noexcept(++pos1) and noexcept(++pos2))
       -> zip_iterator& {
      ++pos1;
      ++pos2;
      return *this;
   }
   auto operator++(int) noexcept(is_nothrow_copyable and noexcept(
       ++pos1) and noexcept(++pos2)) -> const zip_iterator {
      auto tmp = *this;
      ++pos1;
      ++pos2;
      return tmp;
   }
 
   KBLIB_NODISCARD auto operator*() const noexcept -> auto {
      return std::forward_as_tuple(*pos1, *pos2);
   }
 
   KBLIB_NODISCARD auto begin() const noexcept(is_nothrow_copyable)
       -> zip_iterator {
      return *this;
   }
   KBLIB_NODISCARD auto end() const
       noexcept(std::is_nothrow_copy_constructible<EndIt>::value and
                    std::is_nothrow_copy_constructible<InputIt2>::value)
           -> zip_iterator<EndIt, EndIt, InputIt2> {
      return {end1, end1};
   }
 
   KBLIB_NODISCARD friend auto operator==(
       const zip_iterator& z1,
       const zip_iterator& z2) noexcept(noexcept(z1.pos1 == z2.pos1)) -> bool {
      return z1.pos1 == z2.pos1;
   }
   KBLIB_NODISCARD friend auto operator!=(
       const zip_iterator& z1,
       const zip_iterator& z2) noexcept(noexcept(z1.pos1 != z2.pos1)) -> bool {
      return z1.pos1 != z2.pos1;
   }
   KBLIB_NODISCARD friend auto operator==(
       const zip_iterator& z1,
       zip_iterator<EndIt, EndIt, InputIt2> end) noexcept(noexcept(z1.pos1
                                                                   == end.val))
       -> bool {
      return z1.end1 == end.val;
   }
   KBLIB_NODISCARD friend auto operator!=(
       const zip_iterator& z1,
       zip_iterator<EndIt, EndIt, InputIt2> end) noexcept(noexcept(z1.pos1
                                                                   == end.val))
       -> bool {
      return z1.end1 != end.val;
   }
};
 
template <typename It1, typename It2>
struct zip_iterator<It1, It1, It2> {
   It1 pos1{};
   It1 end1{};
   It2 pos2{};
 
   constexpr static bool is_nothrow_copyable
       = std::is_nothrow_copy_constructible<It1>::value
         and std::is_nothrow_copy_constructible<It2>::value;
 
   auto operator++() noexcept(noexcept(++pos1)) -> zip_iterator& {
      ++pos1;
      ++pos2;
      return *this;
   }
   auto operator++(int) noexcept(is_nothrow_copyable and noexcept(++pos1))
       -> const zip_iterator {
      auto tmp = *this;
      ++pos1;
      ++pos2;
      return tmp;
   }
 
   KBLIB_NODISCARD auto operator*() -> auto {
      return std::forward_as_tuple(*pos1, *pos2);
   }
 
   KBLIB_NODISCARD auto begin() const noexcept(is_nothrow_copyable)
       -> zip_iterator {
      return *this;
   }
   KBLIB_NODISCARD auto end() const
       noexcept(std::is_nothrow_copy_constructible<It1>::value)
           -> zip_iterator {
      return {end1, end1, pos2};
   }
 
   KBLIB_NODISCARD friend auto operator==(
       const zip_iterator& z1,
       const zip_iterator& z2) noexcept(noexcept(z1.pos1 == z2.pos1)) -> bool {
      return z1.pos1 == z2.pos1;
   }
   KBLIB_NODISCARD friend auto operator!=(
       const zip_iterator& z1,
       const zip_iterator& z2) noexcept(noexcept(z1.pos1 == z2.pos1)) -> bool {
      return z1.pos1 != z2.pos1;
   }
};
 
template <typename InputIt1, typename EndIt, typename InputIt2>
KBLIB_NODISCARD auto zip(InputIt1 begin1, EndIt end1, InputIt2 begin2) noexcept(
    zip_iterator<InputIt1, EndIt, InputIt2>::is_nothrow_copyable)
    -> zip_iterator<InputIt1, EndIt, InputIt2> {
   return {begin1, end1, begin2};
}
 
template <typename Range1, typename Range2>
KBLIB_NODISCARD auto zip(Range1&& r1, Range2&& r2) noexcept(
    zip_iterator<decltype(begin(r1)), decltype(end(r1)),
                 decltype(begin(r2))>::is_nothrow_copyable)
    -> zip_iterator<decltype(begin(r1)), decltype(end(r1)),
                    decltype(begin(r2))> {
   return {begin(r1), end(r1), begin(r2)};
}
 
template <typename ForwardIt, typename EndIt>
class adjacent_iterator {
 public:
   using difference_type = std::ptrdiff_t;
   using base_reference = typename std::iterator_traits<ForwardIt>::reference;
   using value_type = std::pair<base_reference, base_reference>;
   using pointer = void;
   using reference = value_type;
   using iterator_category = std::input_iterator_tag;
 
 private:
   ForwardIt it;
};
 
template <typename Container, typename F>
class back_insert_iterator_F {
 public:
   explicit back_insert_iterator_F(Container& c, F f)
       : container(c)
       , fun(std::move(f)) {}
 
   using value_type = void;
   using difference_type = void;
   using pointer = void;
   using reference = void;
   using iterator_category = std::output_iterator_tag;
 
   template <typename V>
   auto operator=(V&& value) -> back_insert_iterator_F& {
      container.push_back(invoke(fun, std::forward<V>(value)));
      return *this;
   }
 
   auto operator*() -> back_insert_iterator_F& { return *this; }
   auto operator++() -> back_insert_iterator_F& { return *this; }
 
 private:
   Container& container;
   F fun;
};
 
template <typename F>
class consume_iterator {
 private:
   F fun;
 
 public:
   using value_type = void;
   using difference_type = void;
   using pointer = void;
   using reference = void;
   using iterator_category = std::output_iterator_tag;
 
   explicit consume_iterator(F f)
       : fun(std::move(f)) {}
 
   consume_iterator(const consume_iterator&) = default;
   consume_iterator(consume_iterator&&) = default;
   auto operator=(const consume_iterator&) & -> consume_iterator& = default;
   auto operator=(consume_iterator&&) & -> consume_iterator& = default;
   ~consume_iterator() = default;
 
   template <typename V>
   auto operator=(V&& value) noexcept(
       noexcept(kblib::invoke(fun, std::forward<V>(value))))
       -> kblib::ignore_t<decltype(kblib::invoke(fun, std::forward<V>(value))),
                          consume_iterator&> {
      kblib::invoke(fun, std::forward<V>(value));
      return *this;
   }
 
   auto operator*() -> consume_iterator& { return *this; }
   auto operator++() -> consume_iterator& { return *this; }
   auto operator++(int) -> consume_iterator& { return *this; }
};
 
template <typename F>
auto consumer(F f) -> consume_iterator<F> {
   return consume_iterator<F>{std::move(f)};
}
 
} // namespace kblib
 
#endif // KBLIB_ITERATORS_H