ahFunctional.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef AH_FUNCTIONAL_H
#define AH_FUNCTIONAL_H
 
#include <stdexcept>
#include <utility>
#include <tuple>
#include <functional>
#include <algorithm>
#include <concepts>
#include <optional>
#include <type_traits>
#include <ah-errors.H>
#include <ah-ranges.H>
#include <ah-concepts.H>
#include <hash-dry.H>
 
namespace Aleph {
template <typename T>
struct Found_Item
{
  virtual T &get_item() = 0;
  virtual const T &get_item() const = 0;
  virtual bool is_found() const noexcept = 0;
  virtual ~Found_Item() = default;
};
 
template <typename T>
struct None : public Found_Item<T>
{
  [[noreturn]] T &get_item() override
  {
    ah_invalid_argument() << "Access from None type";
#if defined(__GNUC__) || defined(__clang__)
    __builtin_unreachable();  // Satisfies compiler after throw
#elif defined(_MSC_VER)
    __assume(0);
#endif
  }
 
  [[noreturn]] const T &get_item() const override
  {
    ah_invalid_argument() << "Access from None type";
#if defined(__GNUC__) || defined(__clang__)
    __builtin_unreachable();
#elif defined(_MSC_VER)
    __assume(0);
#endif
  }
 
  [[nodiscard]] bool is_found() const noexcept override
  {
    return false;
  }
};
 
template <typename T>
struct Some : public Found_Item<T>
{
  T &item;
 
  Some(T &i) : item(i) {}
 
  T &get_item() override
  {
    return item;
  }
  const T &get_item() const override
  {
    return item;
  }
  [[nodiscard]] bool is_found() const noexcept override
  {
    return true;
  }
};
 
template <typename tgtT, typename srcT>
struct Dft_Map_Op
{
  tgtT operator()(const srcT &item) const noexcept
  {
    return static_cast<tgtT>(item);
  }
};
 
template <typename TR, typename TD>
struct Dft_Fold_Op
{
  TR operator()(const TR & /*acc */, const TD & /* val */) const noexcept
  {
    return TR();
  }
};
 
template <typename Key, class Cmp>
  requires EqualityComparator<Cmp, Key>
struct DynSetLhash;
 
namespace functional_detail {
template <class C>
using get_it_t = std::decay_t<decltype(std::declval<const C &>().get_it())>;
 
template <class C>
using get_curr_t = decltype(std::declval<get_it_t<C> &>().get_curr());
 
template <class C>
using get_curr_cref_t = const std::remove_reference_t<get_curr_t<C>> &;
 
template <typename T, class Eq, typename = void>
struct Dyn_Set_Lhash_Available : public std::false_type
{
};
 
template <typename T, class Eq>
struct Dyn_Set_Lhash_Available<T, Eq, std::void_t<decltype(sizeof(DynSetLhash<T, Eq>))>>
  : public std::true_type
{
};
 
template <typename T, class Eq>
inline constexpr bool dyn_set_lhash_available = Dyn_Set_Lhash_Available<T, Eq>::value;
 
template <AlephSequentialIterableContainer Container, class Equal>
[[nodiscard]] inline bool pairwise_all_unique(const Container &container, Equal &eq)
{
  for (auto it1 = container.get_it(); it1.has_curr(); it1.next_ne())
    {
      auto it2 = it1;
      it2.next_ne();
      for (; it2.has_curr(); it2.next_ne())
        if (eq(it1.get_curr(), it2.get_curr()))
          return false;
    }
  return true;
}
 
template <AlephSequentialIterableContainer Container, class Hash, class Equal>
  requires std::copy_constructible<typename Container::Item_Type>
       and requires(const typename Container::Item_Type &v, Hash h, Equal e) {
             { h(v) } -> std::convertible_to<size_t>;
             { e(v, v) } -> std::convertible_to<bool>;
           }
[[nodiscard]] inline bool all_unique_hash_path(const Container &container, Hash &hash, Equal &eq)
{
  using T = typename Container::Item_Type;
  using Eq_Type = std::remove_cvref_t<Equal>;
 
  if constexpr (dyn_set_lhash_available<T, Eq_Type>)
    {
      using Set_Type = DynSetLhash<T, Eq_Type>;
      using Hash_Fct = typename Set_Type::Hash_Fct;
 
      Hash_Fct hash_fct([&hash](const T &value)
      {
        return static_cast<size_t>(hash(value));
      });
 
      Set_Type seen(17, hash_fct, eq, hash_default_lower_alpha, hash_default_upper_alpha);
 
      for (auto it = container.get_it(); it.has_curr(); it.next_ne())
        if (seen.contains_or_insert(it.get_curr()).second)
          return false;
      return true;
    }
 
  return pairwise_all_unique(container, eq);
}
}  // namespace functional_detail
 
template <typename T>
class DynList;
 
template <typename T = int, template <typename> class Container = DynList>
[[nodiscard]] inline Container<T> range(const T start, const T end, const T step = 1)
{
  Container<T> ret_val;
  for (T i = start; i <= end; i += step)
    ret_val.append(i);
  return ret_val;
}
 
template <typename T = int, template <typename> class Container = DynList>
[[nodiscard]] inline Container<T> nrange(const T start, const T end, const size_t n)
{
  ah_domain_error_if(n == 0) << "nrange: n must be greater than 0";
 
  Container<T> ret_val;
  if (n == 1)
    {
      ret_val.append(start);
      return ret_val;
    }
 
  const auto step = static_cast<double>(end - start) / (n - 1);
  for (size_t i = 0; i < n; ++i)
    ret_val.append(static_cast<T>(start + i * step));
 
  return ret_val;
}
 
template <typename T = int, template <typename> class Container = DynList, class Op>
[[nodiscard]] inline auto set_range(const T start, const T end, const T step, Op &op)
  -> Container<std::decay_t<decltype(op(start))>>
{
  Container<std::decay_t<decltype(op(start))>> ret_val;
  for (T i = start; i <= end; i += step)
    ret_val.append(op(i));
  return ret_val;
}
 
template <typename T = int, template <typename> class Container = DynList, class Op>
[[nodiscard]] inline auto set_range(const T start, const T end, const T step = 1, Op &&op = Op())
  -> Container<std::decay_t<decltype(op(start))>>
{
  return set_range<T, Container, Op>(start, end, step, op);
}
 
template <typename T = int, template <typename> class Container = DynList>
[[nodiscard]] inline Container<T> contiguous_range(T start, const size_t n)
{
  Container<T> ret_val;
  for (size_t i = 0; i < n; ++i)
    ret_val.append(start++);
  return ret_val;
}
 
template <typename T = int, template <typename> class Container = DynList>
[[nodiscard]] Container<T> range(const T n)
{
  Container<T> ret_val;
  for (T i = 0; i < n; ++i)
    ret_val.append(i);
  return ret_val;
}
 
template <typename T = int>
[[nodiscard]] inline DynList<T> rep(const size_t n, const T &item)
{
  DynList<T> ret_val;
  for (size_t i = 0; i < n; ++i)
    ret_val.append(item);
  return ret_val;
}
 
template <typename T = int>
[[nodiscard]] inline DynList<T> rep(const size_t n, T &&item = T())
{
  return rep<T>(n, item);
}
 
// ─── In-place fill operations ─────────────────────────────────────────────
 
template <AlephSequentialContainer C>
void fill(C &container, const typename C::Item_Type &value)
{
  container.mutable_for_each([&value](typename C::Item_Type &item)
  {
    item = value;
  });
}
 
template <AlephSequentialContainer C>
  requires requires(typename C::Item_Type v) { ++v; }
void iota(C &container, typename C::Item_Type start)
{
  container.mutable_for_each([&start](typename C::Item_Type &item)
  {
    item = start++;
  });
}
 
template <AlephSequentialContainer C>
  requires requires(typename C::Item_Type v, typename C::Item_Type s) { v += s; }
void iota(C &container, typename C::Item_Type start, const typename C::Item_Type step)
{
  container.mutable_for_each([&start, &step](typename C::Item_Type &item)
  {
    item = start;
    start += step;
  });
}
 
template <class Container>
[[nodiscard]]
DynList<typename Container::Item_Type *> pointers_list(Container &c)
{
  DynList<typename Container::Item_Type *> ret;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    ret.append(&it.get_curr());
  return ret;
}
 
template <class Container>
[[nodiscard]]
DynList<const typename Container::Item_Type *> pointers_list(const Container &c)
{
  using T = const typename Container::Item_Type *;
  DynList<T> ret;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    ret.append(&it.get_curr());
  return ret;
}
 
template <class Op>
  requires CallableWith<Op &>
void each(const size_t start, const size_t end, Op &op)
{
  for (size_t i = start; i <= end; ++i)
    op();
}
 
template <class Op>
  requires CallableWith<Op &>
void each(size_t start, size_t end, Op &&op)
{
  each(start, end, op);
}
 
template <class Op>
  requires CallableWith<Op &>
void each(const size_t n, Op &op)
{
  if (n == 0)
    return;
  each(0, n - 1, op);
}
 
template <class Op>
  requires CallableWith<Op &>
void each(size_t n, Op &&op)
{
  each(n, op);
}
 
template <class Container>
[[nodiscard]]
DynList<typename Container::Item_Type> sublist(const Container &c, size_t pos, const size_t stride)
{
  DynList<typename Container::Item_Type> ret;
  try
    {
      for (auto it = c.get_it(pos); it.has_curr(); each(0, stride - 1, [&it]()
      {
        it.next();
      }))
        ret.append(it.get_curr());
    }
  catch (const std::overflow_error &)
    { /* end of container reached */
    }
 
  return ret;
}
 
template <class Container>
[[nodiscard]]
DynList<typename Container::Item_Type> sublist(const Container &c, size_t stride)
{
  return sublist(c, 0, stride);
}
 
template <class Container, class Operation>
inline Container &for_each(Container &container, Operation &operation)
{
  container.traverse([&operation](const auto &item)
  {
    operation(item);
    return true;
  });
  return container;
}
 
template <class Container, class Operation>
inline const Container &for_each(const Container &container, Operation &operation)
{
  container.traverse([&operation](const auto &item)
  {
    operation(item);
    return true;
  });
  return container;
}
 
template <class Container, class Operation>
inline Container &for_each(Container &container, Operation &&operation = Operation())
{
  return for_each<Container, Operation>(container, operation);
}
 
template <class Container, class Operation>
inline const Container &for_each(const Container &container, Operation &&operation = Operation())
{
  return for_each<Container, Operation>(container, operation);
}
 
template <class Container, class Operation>
  requires CallableWith<Operation &, functional_detail::get_curr_t<Container>, std::size_t &>
inline void enum_for_each(const Container &container, Operation &operation)
{
  size_t i = 0;
  for (auto it = container.get_it(); it.has_curr(); it.next_ne(), ++i)
    operation(it.get_curr(), i);
}
 
template <class Container, class Operation>
  requires CallableWith<Operation &, functional_detail::get_curr_t<Container>, std::size_t &>
inline void enum_for_each(const Container &container, Operation &&operation)
{
  enum_for_each(container, operation);
}
 
template <class Container, class Operation>
  requires requires(Container &c, Operation &op) { { c.traverse(op) } -> std::convertible_to<bool>; }
inline bool all(Container &container, Operation &operation)
{
  return container.traverse(operation);
}
 
template <class Container, class Operation>
  requires requires(const Container &c, Operation &op) { { c.template traverse<Operation>(op) } -> std::convertible_to<bool>; }
inline bool all(const Container &container, Operation &operation)
{
  return container.template traverse<Operation>(operation);
}
 
template <class Container, class Operation>
  requires requires(Container &c, Operation &op) { { c.traverse(op) } -> std::convertible_to<bool>; }
inline bool all(Container &container, Operation &&operation = Operation())
{
  return all<Container, Operation>(container, operation);
}
 
template <class Container, class Operation>
  requires requires(const Container &c, Operation &op) { { c.template traverse<Operation>(op) } -> std::convertible_to<bool>; }
inline bool all(const Container &container, Operation &&operation = Operation())
{
  return all<Container, Operation>(container, operation);
}
 
template <class Container, class Operation>
inline bool exists(Container &container, Operation &operation)
{
  return not container.traverse([&operation](const auto &item)
  {
    return not operation(item);
  });
}
 
template <class Container, class Operation>
inline bool exists(const Container &container, Operation &operation)
{
  return not container.traverse([&operation](const auto &item)
  {
    return not operation(item);
  });
}
 
template <class Container, class Operation>
inline bool exists(Container &container, Operation &&operation = Operation())
{
  return exists<Container, Operation>(container, operation);
}
 
template <class Container, class Operation>
inline bool exists(const Container &container, Operation &&operation = Operation())
{
  return exists<Container, Operation>(container, operation);
}
 
template <typename T>
struct Dft_Filter_Op
{
  bool operator()(const T &) const noexcept
  {
    return true;
  }
};
 
template <class Container1,
          template <typename> class Container2 = Aleph::DynList,
          class Operation = Dft_Filter_Op<typename Container1::Item_Type>>
[[nodiscard]] inline Container2<typename Container1::Item_Type> filter(Container1 &container,
                                                                       Operation &operation)
{
  Container2<typename Container1::Item_Type> ret_val;
  container.for_each([&ret_val, &operation](const auto &item)
  {
    if (operation(item))
      ret_val.append(item);
  });
  return ret_val;
}
 
template <class Container1,
          template <typename> class Container2 = Aleph::DynList,
          class Operation = Dft_Filter_Op<typename Container1::Item_Type>>
[[nodiscard]] inline Container2<typename Container1::Item_Type> filter(const Container1 &container,
                                                                       Operation &operation)
{
  Container2<typename Container1::Item_Type> ret_val;
  container.for_each([&ret_val, &operation](const auto &item)
  {
    if (operation(item))
      ret_val.append(item);
  });
  return ret_val;
}
 
template <class Container1,
          template <typename> class Container2 = Aleph::DynList,
          class Operation = Dft_Filter_Op<typename Container1::Item_Type>>
[[nodiscard]] inline Container2<typename Container1::Item_Type> filter(Container1 &container,
                                                                       Operation &&operation)
{
  return filter<Container1, Container2, Operation>(container, operation);
}
 
template <class Container1,
          template <typename> class Container2 = Aleph::DynList,
          class Operation = Dft_Filter_Op<typename Container1::Item_Type>>
[[nodiscard]] inline Container2<typename Container1::Item_Type> filter(const Container1 &container,
                                                                       Operation &&operation)
{
  return filter<Container1, Container2, Operation>(container, operation);
}
 
template <typename T, class C, class Op>
  requires requires(DynList<T> &ret, Op &op) { ret.append(op(std::declval<functional_detail::get_curr_t<C>>())); }
[[nodiscard]] DynList<T> maps(const C &c, Op op)
{
  DynList<T> ret;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    ret.append(op(it.get_curr()));
  return ret;
}
 
template <typename T, class Container, class Operation>
[[nodiscard]] inline T foldl(const Container &container, const T &init, Operation operation)
{
#if ALEPH_HAS_RANGES
  if constexpr (std::ranges::range<Container>)
    return detail::ranges_fold_left(container, init, std::move(operation));
  else
#endif
    {
      T ret_val = init;
      for (auto it = container.get_it(); it.has_curr(); it.next_ne())
        ret_val = operation(ret_val, it.get_curr());
      return ret_val;
    }
}
 
template <class Container1, class Container2>
[[nodiscard]] inline DynList<std::pair<typename Container1::Item_Type, typename Container2::Item_Type>>
zip(const Container1 &a, const Container2 &b)
{
  typedef typename Container1::Item_Type T1;
  typedef typename Container2::Item_Type T2;
  DynList<std::pair<T1, T2>> ret_val;
 
  auto it1 = a.get_it();
  auto it2 = b.get_it();
  for (; it1.has_curr() and it2.has_curr(); it1.next_ne(), it2.next_ne())
    ret_val.append(std::pair<T1, T2>(it1.get_curr(), it2.get_curr()));
 
  return ret_val;
}
 
template <class Container1, class Container2>
[[nodiscard]] inline DynList<std::tuple<typename Container1::Item_Type, typename Container2::Item_Type>>
tzip(const Container1 &a, const Container2 &b)
{
  typedef typename Container1::Item_Type T1;
  typedef typename Container2::Item_Type T2;
  using Tuple = std::tuple<T1, T2>;
  DynList<Tuple> ret_val;
 
  auto it1 = a.get_it();
  auto it2 = b.get_it();
  for (; it1.has_curr() and it2.has_curr(); it1.next_ne(), it2.next_ne())
    ret_val.append(Tuple(it1.get_curr(), it2.get_curr()));
 
  return ret_val;
}
 
template <class Container1, class Container2>
[[nodiscard]] inline DynList<std::pair<typename Container1::Item_Type, typename Container2::Item_Type>>
zipEq(const Container1 &a, const Container2 &b)
{
  typedef typename Container1::Item_Type T1;
  typedef typename Container2::Item_Type T2;
  DynList<std::pair<T1, T2>> ret_val;
 
  auto it1 = a.get_it();
  auto it2 = b.get_it();
  for (; it1.has_curr() and it2.has_curr(); it1.next_ne(), it2.next_ne())
    ret_val.append(std::pair<T1, T2>(it1.get_curr(), it2.get_curr()));
 
  ah_length_error_if(it1.has_curr() or it2.has_curr()) << "Container sizes mismatch";
 
  return ret_val;
}
 
template <class Container1, class Container2>
[[nodiscard]] inline DynList<std::tuple<typename Container1::Item_Type, typename Container2::Item_Type>>
tzipEq(const Container1 &a, const Container2 &b)
{
  typedef typename Container1::Item_Type T1;
  typedef typename Container2::Item_Type T2;
  using Tuple = std::tuple<T1, T2>;
  DynList<Tuple> ret_val;
 
  auto it1 = a.get_it();
  auto it2 = b.get_it();
  for (; it1.has_curr() and it2.has_curr(); it1.next_ne(), it2.next_ne())
    ret_val.append(Tuple(it1.get_curr(), it2.get_curr()));
 
  ah_length_error_if(it1.has_curr() or it2.has_curr()) << "Container sizes mismatch";
 
  return ret_val;
}
 
template <class Container>
[[nodiscard]]
auto inline enumerate(const Container &c)
{
  using Item = typename Container::Item_Type;
  using Pair = std::pair<Item, size_t>;
  DynList<Pair> ret;
  size_t i = 0;
  c.for_each([&i, &ret](const Item &item)
  {
    ret.append(Pair(item, i++));
  });
  return ret;
}
 
template <class C1, class C2, class Eq = std::equal_to<typename C1::Item_Type>>
[[nodiscard]] inline bool eq(const C1 &c1, const C2 &c2, Eq e = Eq())
{
  auto it1 = c1.get_it();
  auto it2 = c2.get_it();
  for (; it1.has_curr() and it2.has_curr(); it1.next_ne(), it2.next_ne())
    if (not(e(it1.get_curr(), it2.get_curr())))
      return false;
 
  return not(it1.has_curr() or it2.has_curr());
}
 
template <typename T>
[[nodiscard]] inline bool operator==(const DynList<T> &l1, const DynList<T> &l2)
{
  return eq(l1, l2);
}
 
template <class C1, class C2, class Eq>
[[nodiscard]] inline bool containers_eq(const C1 &c1, const C2 &c2, Eq e)
{
  return eq(c1, c2, e);
}
 
template <class C1, class C2, class Eq = std::equal_to<typename C1::Item_Type>>
[[nodiscard]] inline std::tuple<bool, size_t, typename C1::Item_Type, typename C2::Item_Type>
are_eq(const C1 &c1, const C2 &c2, Eq e = Eq())
{
  using T = typename C1::Item_Type;
  auto it1 = c1.get_it();
  auto it2 = c2.get_it();
  size_t n = 0;
  for (; it1.has_curr() and it2.has_curr(); it1.next_ne(), it2.next_ne(), n++)
    {
      auto &i1 = it1.get_curr();
      auto &i2 = it2.get_curr();
      if (not(e(i1, i2)))
        return std::make_tuple(false, n, i1, i2);
    }
 
  return std::make_tuple(not(it1.has_curr() or it2.has_curr()), n, T(), T());
}
 
template <class C1, class C2, class Cmp = std::less<typename C1::Item_Type>>
[[nodiscard]] inline bool lesser(const C1 &c1, const C2 &c2, Cmp cmp = Cmp())
{
  auto it1 = c1.get_it();
  auto it2 = c2.get_it();
  for (; it1.has_curr() and it2.has_curr(); it1.next_ne(), it2.next_ne())
    {
      auto &curr1 = it1.get_curr();
      auto &curr2 = it2.get_curr();
      if (cmp(curr1, curr2))
        return true;
      if (cmp(curr2, curr1))
        return false;
    }
 
  if (not it1.has_curr() and not it2.has_curr())
    return false;
 
  return it2.has_curr();
}
 
template <class C1, class C2, class Eq = std::equal_to<typename C1::Item_Type>>
[[nodiscard]] inline bool diff(const C1 &c1, const C2 &c2, Eq e = Eq())
{
  return not eq(c1, c2, e);
}
 
template <class Container>
[[nodiscard]] inline auto unzip(const Container &l)
{
  using T1 = std::decay_t<decltype(l.get_first().first)>;
  using T2 = std::decay_t<decltype(l.get_first().second)>;
  DynList<T1> l1;
  DynList<T2> l2;
  for (auto it = l.get_it(); it.has_curr(); it.next_ne())
    {
      auto &curr = it.get_curr();
      l1.append(curr.first);
      l2.append(curr.second);
    }
 
  return std::make_pair(std::move(l1), std::move(l2));
}
 
template <template <typename> class Container, typename T1, typename T2>
[[nodiscard]] inline std::tuple<Container<T1>, Container<T2>> tunzip(
  const Container<std::tuple<T1, T2>> &l)
{
  Container<T1> l1;
  Container<T2> l2;
  for (auto it = l.get_it(); it.has_curr(); it.next_ne())
    {
      auto &curr = it.get_curr();
      l1.append(std::get<0>(curr));
      l2.append(std::get<1>(curr));
    }
 
  return std::make_tuple(std::move(l1), std::move(l2));
}
 
template <class SrcContainer, template <typename> class TgtContainer = Aleph::DynList>
[[nodiscard]] inline std::pair<TgtContainer<typename SrcContainer::Item_Type>,
                               TgtContainer<typename SrcContainer::Item_Type>>
partition(const SrcContainer &c,
          std::function<bool(const typename SrcContainer::Item_Type &)> operation)
{
  typedef typename SrcContainer::Item_Type Type;
  typedef std::pair<TgtContainer<Type>, TgtContainer<Type>> Pair;
 
  Pair ret_val;
  for_each(c, [&ret_val, &operation](const Type &item)
  {
    if (operation(item))
      ret_val.first.append(item);
    else
      ret_val.second.append(item);
  });
  return ret_val;
}
 
template <class Container>
[[nodiscard]] inline DynList<std::pair<size_t, typename Container::Key_Type>> indexes(const Container &c)
{
  using T = typename Container::Key_Type;
  using Pair = std::pair<size_t, T>;
  size_t i = 0;
 
  return c.Container::template maps<Pair>([&i](const T &d)
  {
    return Pair(i++, d);
  });
}
 
template <class Container>
[[nodiscard]] inline DynList<std::tuple<size_t, typename Container::Key_Type>> tindexes(
  const Container &c)
{
  using T = typename Container::Key_Type;
  using Tuple = std::tuple<size_t, typename Container::Key_Type>;
  size_t i = 0;
  return c.Container::template maps<std::tuple<size_t, T>>([&i](const T &d)
  {
    return Tuple(i++, d);
  });
}
 
template <typename T, template <typename> class Container>
[[nodiscard]] inline Container<T> reverse(const Container<T> &l)
{
  Container<T> ret_val;
  l.for_each([&ret_val](const T &item)
  {
    ret_val.insert(item);
  });
  return ret_val;
}
 
template <class Container>
[[nodiscard]]
auto gen_seq_list_tuples(const Container &c, size_t n)
{
  using T = typename Container::Item_Type;
  auto it = c.get_it();
  DynList<T> l;
  for (size_t i = 0; i < n; ++i, it.next())
    l.append(it.get_curr());
 
  DynList<DynList<T>> ret;
  ret.append(l);
  for (; it.has_curr(); it.next_ne())
    {
      l.remove_first();
      l.append(it.get_curr());
      ret.append(l);
    }
 
  return ret;
}
 
template <typename T, template <typename> class Container, class Equal>
[[nodiscard]] std::pair<DynList<DynList<T>>, size_t> sequential_groups(const Container<T> &c,
                                                                       Equal &eq)
{
  using P = std::pair<DynList<DynList<T>>, size_t>;
  if (c.is_empty())
    return P(DynList<DynList<T>>(), 0);
 
  DynList<DynList<T>> ret;  // this will be the result
 
  DynList<T> *group = &ret.append(DynList<T>());  // creates a first group
 
  auto it = c.get_it();  // put the firstitem into the group
  auto curr_item = it.get_curr();
  group->append(curr_item);
 
  size_t count = 1;  // count the number of groups
 
  for (it.next(); it.has_curr(); it.next_ne())
    {
      auto &curr = it.get_curr();
      if (not eq(curr, curr_item))  // group change?
        {
          curr_item = curr;
          group = &ret.append(DynList<T>());  // create new group and insert it
          ++count;                            // increase the number of groups
        }
 
      group->append(curr);
    }
 
  return P(ret, count);
}
 
template <typename T, template <typename> class Container, class Equal = std::equal_to<T>>
[[nodiscard]] std::pair<DynList<DynList<T>>, size_t> sequential_groups(const Container<T> &c,
                                                                       Equal &&eq = Equal())
{
  return sequential_groups(c, eq);
}
 
template <typename T, template <typename> class Container, class Equal>
[[nodiscard]] std::pair<DynList<T>, size_t> unique_sequential(const Container<T> &c, Equal &eq)
{
  using P = std::pair<DynList<T>, size_t>;
  if (c.is_empty())
    return P(DynList<T>(), 0);
 
  DynList<T> ret;
 
  auto it = c.get_it();  // put the first item
  auto curr_item = it.get_curr();
  ret.append(curr_item);
 
  size_t count = 1;  // count the number of groups
 
  for (it.next(); it.has_curr(); it.next_ne())
    {
      auto &curr = it.get_curr();
      if (not eq(curr, curr_item))  // group change?
        {
          curr_item = curr;
          ret.append(curr_item);
          ++count;  // increase the number of groups
        }
    }
 
  return P(ret, count);
}
 
template <typename T, template <typename> class Container, class Equal = std::equal_to<T>>
[[nodiscard]] std::pair<DynList<T>, size_t> unique_sequential(const Container<T> &c,
                                                              Equal &&eq = Equal())
{
  return unique_sequential(c, eq);
}
 
template <class Itor1, class Itor2 = Itor1>
class Pair_Iterator
{
  Itor1 it1;
  Itor2 it2;
 
public:
  Pair_Iterator(Itor1 i1, Itor2 i2) : it1(i1), it2(i2) {}
 
  template <class C1, class C2>
  Pair_Iterator(const C1 &c1, const C2 &c2) : Pair_Iterator(c1.get_it(), c2.get_it())
  {}
 
  [[nodiscard]] bool has_curr() const noexcept
  {
    return it1.has_curr() and it2.has_curr();
  }
 
  [[nodiscard]] bool has_curr1() const noexcept
  {
    return it1.has_curr();
  }
 
  [[nodiscard]] bool has_curr2() const noexcept
  {
    return it2.has_curr();
  }
 
  auto get_curr() const
  {
    return std::make_pair(it1.get_curr(), it2.get_curr());
  }
 
  auto get_curr_ne() const noexcept
  {
    return std::make_pair(it1.get_curr_ne(), it2.get_curr_ne());
  }
 
  void next()
  {
    it1.next();
    it2.next();
  }
 
  void next_ne() noexcept
  {
    it1.next_ne();
    it2.next_ne();
  }
 
  [[nodiscard]] bool was_traversed() const noexcept
  {
    return not(it1.has_curr() or it2.has_curr());
  }
};
 
template <class C1, class C2>
[[nodiscard]] Pair_Iterator<typename C1::Iterator, typename C2::Iterator> inline get_pair_it(
  const C1 &c1,
  const C2 &c2)
{
  using I1 = typename C1::Iterator;
  using I2 = typename C2::Iterator;
  auto i1 = c1.get_it();
  auto i2 = c2.get_it();
  return Pair_Iterator<I1, I2>(i1, i2);
}
 
template <class C1, class C2>
[[nodiscard]] Pair_Iterator<typename C1::Iterator, typename C2::Iterator> inline get_pair_it(
  const C1 &c1,
  const C2 &c2,
  const size_t pos)
{
  using I1 = typename C1::Iterator;
  using I2 = typename C2::Iterator;
  auto i1 = c1.get_it();
  auto i2 = c2.get_it();
  for (size_t i = 0; i < pos; ++i)
    {
      i1.next();
      i2.next();
    }
  return Pair_Iterator<I1, I2>(i1, i2);
}
 
template <class C>
inline void insert_in_container(C &, size_t &)
{}
 
template <class C, typename T, typename... Args>
inline void insert_in_container(C &c, size_t &n, const T &item, Args &...args)
{
  c.insert(item);
  ++n;
  insert_in_container(c, n, args...);
}
 
template <class C, typename... Args>
inline size_t insert_in_container(C &c, Args... args)
{
  size_t n = 0;
  insert_in_container(c, n, args...);
  return n;
}
 
template <class C>
inline void append_in_container(C &, size_t &)
{}
 
template <class C, typename T, typename... Args>
inline void append_in_container(C &c, size_t &n, const T &item, Args &...args)
{
  c.append(item);
  ++n;
  append_in_container(c, n, args...);
}
 
template <class C, typename... Args>
inline size_t append_in_container(C &c, Args... args)
{
  size_t n = 0;
  append_in_container(c, n, args...);
  return n;
}
 
template <class C, typename... Args>
[[nodiscard]] C build_container(Args... args)
{
  C c;
  append_in_container(c, args...);
  return c;
}
 
template <class SrcC, class TgtC>
[[nodiscard]] TgtC assign_container(const SrcC &srcc)
{
  TgtC ret;
  for (auto it = srcc.get_it(); it.has_curr(); it.next_ne())
    ret.append(it.get_curr());
 
  return ret;
}
 
template <typename T, typename... Args>
[[nodiscard]] DynList<T> build_dynlist(Args... args)
{
  return build_container<DynList<T>>(args...);
}
 
template <class C>
inline void remove_from_container(C &, size_t &)
{}
 
template <class C, typename T, typename... Args>
inline void remove_from_container(C &c, size_t &n, const T &item, Args &...args)
{
  c.remove(item);
  ++n;
  remove_from_container(c, n, args...);
}
 
template <class C, typename... Args>
inline size_t remove_from_container(C &c, Args... args)
{
  size_t n = 0;
  remove_from_container(c, n, args...);
  return n;
}
 
// These functions are defined in tpl_dynSetHash.H
 
template <typename T, template <typename> class Container>
[[nodiscard]] inline DynList<T> join(const Container<T> &c1, const Container<T> &c2);
 
template <typename T, template <typename> class Container>
[[nodiscard]] inline DynList<T> intercept(const Container<T> &c1, const Container<T> &c2);
 
template <typename T, template <typename> class Container>
[[nodiscard]] inline DynList<T> unique(const Container<T> &c);
 
template <typename T, template <typename> class Container>
[[nodiscard]] inline DynList<T> repeated(const Container<T> &c);
 
template <typename T, template <typename> class Container>
[[nodiscard]] inline DynList<std::pair<T, size_t>> repeated_with_index(const Container<T> &c);
 
template <typename T, template <typename> class C1, template <typename> class C2>
[[nodiscard]] DynList<T> flatten(const C2<C1<T>> &c)
{
  DynList<T> ret;
  for (auto it_c = c.get_it(); it_c.has_curr(); it_c.next_ne())
    {
      const auto &curr_c = it_c.get_curr();
      for (auto it = curr_c.get_it(); it.has_curr(); it.next_ne())
        ret.append(it.get_curr());
    }
  return ret;
}
 
template <typename T, template <typename> class C1, template <typename> class C2, template <typename> class C3>
[[nodiscard]] DynList<T> flatten(const C3<C2<C1<T>>> &c)
{
  DynList<T> ret;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    ret.append(flatten(it.get_curr()));
  return ret;
}
 
template <typename T,
          template <typename> class C1,
          template <typename> class C2,
          template <typename> class C3,
          template <typename> class C4>
[[nodiscard]] DynList<T> flatten(const C4<C3<C2<C1<T>>>> &c)
{
  DynList<T> ret;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    ret.append(flatten(it.get_curr()));
  return ret;
}
 
template <typename T,
          template <typename> class C1,
          template <typename> class C2,
          template <typename> class C3,
          template <typename> class C4,
          template <typename> class C5>
[[nodiscard]] DynList<T> flatten(const C5<C4<C3<C2<C1<T>>>>> &c)
{
  DynList<T> ret;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    ret.append(flatten(it.get_curr()));
  return ret;
}
 
template <typename T>
[[nodiscard]] inline bool is_inside(const T &val, const DynList<T> &values)
{
  for (const auto &v : values)
    if (val == v)
      return true;
  return false;
}
 
template <typename T>
[[nodiscard]] inline bool is_equal(const T &val)
{
  (void) val;
  return false;
}
 
template <typename T, typename U, typename... Args>
[[nodiscard]] inline bool is_equal(const T &val, const U &rhs, const Args &...args)
{
  return (val == rhs) or is_equal(val, args...);
}
 
template <class Container, class Operation>
[[nodiscard]] inline bool none(const Container &container, Operation &operation)
{
  return not exists(container, operation);
}
 
template <class Container, class Operation>
[[nodiscard]] inline bool none(const Container &container, Operation &&operation = Operation())
{
  return none<Container, Operation>(container, operation);
}
 
template <class Container, class Pred>
[[nodiscard]] inline typename Container::Item_Type *find_ptr(Container &container, Pred &pred)
{
  typename Container::Item_Type *result = nullptr;
  container.traverse([&result, &pred](auto &item)
  {
    if (pred(item))
      {
        result = &item;
        return false;
      }
    return true;
  });
  return result;
}
 
template <class Container, class Pred>
[[nodiscard]] inline const typename Container::Item_Type *find_ptr(const Container &container,
                                                                   Pred &pred)
{
  const typename Container::Item_Type *result = nullptr;
  container.traverse([&result, &pred](const auto &item)
  {
    if (pred(item))
      {
        result = &item;
        return false;
      }
    return true;
  });
  return result;
}
 
template <class Container, class Pred>
[[nodiscard]] inline typename Container::Item_Type *find_ptr(Container &container, Pred &&pred)
{
  return find_ptr<Container, Pred>(container, pred);
}
 
template <class Container, class Pred>
[[nodiscard]] inline const typename Container::Item_Type *find_ptr(const Container &container,
                                                                   Pred &&pred)
{
  return find_ptr<Container, Pred>(container, pred);
}
 
template <class Container, class Pred>
[[nodiscard]] inline std::optional<typename Container::Item_Type> find_opt(const Container &container,
                                                                           Pred &pred)
{
  std::optional<typename Container::Item_Type> result;
  container.traverse([&result, &pred](const auto &item)
  {
    if (pred(item))
      {
        result = item;
        return false;
      }
    return true;
  });
  return result;
}
 
template <class Container, class Pred>
[[nodiscard]] inline std::optional<typename Container::Item_Type> find_opt(const Container &container,
                                                                           Pred &&pred)
{
  return find_opt<Container, Pred>(container, pred);
}
 
template <typename T, class Container, class Operation>
  requires requires(T &acc, Operation &op, T &x) { acc = op(x, acc); }
[[nodiscard]] inline T foldr(const Container &container, const T &init, Operation operation)
{
  DynList<T> reversed;
  for (auto it = container.get_it(); it.has_curr(); it.next_ne())
    reversed.insert(it.get_curr());
 
  T ret_val = init;
  for (auto it = reversed.get_it(); it.has_curr(); it.next_ne())
    ret_val = operation(it.get_curr(), ret_val);
  return ret_val;
}
 
template <class Container, typename T = typename Container::Item_Type>
[[nodiscard]] inline T sum(const Container &container, const T &init = T{})
{
#if ALEPH_HAS_RANGES
  if constexpr (std::ranges::range<Container>)
    return detail::ranges_fold_left(container, init, std::plus<>{});
  else
#endif
    {
      T result = init;
      for (auto it = container.get_it(); it.has_curr(); it.next_ne())
        result = result + it.get_curr();
      return result;
    }
}
 
template <class Container, typename T = typename Container::Item_Type>
[[nodiscard]] inline T product(const Container &container, const T &init = T{1})
{
#if ALEPH_HAS_RANGES
  if constexpr (std::ranges::range<Container>)
    return detail::ranges_fold_left(container, init, std::multiplies<>{});
  else
#endif
    {
      T result = init;
      for (auto it = container.get_it(); it.has_curr(); it.next_ne())
        result = result * it.get_curr();
      return result;
    }
}
 
template <class C1, class C2>
[[nodiscard]] inline DynList<typename C1::Item_Type> concat(const C1 &c1, const C2 &c2)
{
  DynList<typename C1::Item_Type> result;
  for (auto it = c1.get_it(); it.has_curr(); it.next_ne())
    result.append(it.get_curr());
  for (auto it = c2.get_it(); it.has_curr(); it.next_ne())
    result.append(it.get_curr());
  return result;
}
 
template <class Container, class Pred>
  requires PredicateWith<Pred &, functional_detail::get_curr_cref_t<Container>>
[[nodiscard]] inline DynList<typename Container::Item_Type> take_while(const Container &c, Pred pred)
{
  DynList<typename Container::Item_Type> result;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    {
      const auto &item = it.get_curr();
      if (not pred(item))
        break;
      result.append(item);
    }
  return result;
}
 
template <class Container, class Pred>
  requires PredicateWith<Pred &, functional_detail::get_curr_cref_t<Container>>
[[nodiscard]] inline DynList<typename Container::Item_Type> drop_while(const Container &c, Pred pred)
{
  DynList<typename Container::Item_Type> result;
  bool dropping = true;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    {
      const auto &item = it.get_curr();
      if (dropping and pred(item))
        continue;
      dropping = false;
      result.append(item);
    }
  return result;
}
 
template <class Container, class Op>
[[nodiscard]] inline auto flat_map(const Container &container, Op op)
  -> DynList<typename std::decay_t<decltype(op(std::declval<typename Container::Item_Type>()))>::Item_Type>
{
  using ResultItemType =
    typename std::decay_t<decltype(op(std::declval<typename Container::Item_Type>()))>::Item_Type;
  DynList<ResultItemType> result;
  for (auto it = container.get_it(); it.has_curr(); it.next_ne())
    {
      auto sub = op(it.get_curr());
      for (auto sit = sub.get_it(); sit.has_curr(); sit.next_ne())
        result.append(sit.get_curr());
    }
  return result;
}
 
template <typename T, class Container>
[[nodiscard]] inline DynList<T> scanl_sum(const Container &container, const T &init)
{
  DynList<T> result;
  T acc = init;
  result.append(acc);
  for (auto it = container.get_it(); it.has_curr(); it.next_ne())
    {
      acc = acc + it.get_curr();
      result.append(acc);
    }
  return result;
}
 
template <typename T, class Container, class Op>
  requires requires(T &acc, Op &op) { acc = op(acc, std::declval<functional_detail::get_curr_t<Container>>()); }
[[nodiscard]] inline DynList<T> scanl(const Container &container, const T &init, Op op)
{
  DynList<T> result;
  T acc = init;
  result.append(acc);
  for (auto it = container.get_it(); it.has_curr(); it.next_ne())
    {
      acc = op(acc, it.get_curr());
      result.append(acc);
    }
  return result;
}
 
template <class Container, class Cmp = std::less<typename Container::Item_Type>>
  requires PredicateWith<Cmp &, functional_detail::get_curr_cref_t<Container>, const typename Container::Item_Type &>
[[nodiscard]] inline const typename Container::Item_Type *min_ptr(const Container &container,
                                                                  Cmp cmp = Cmp())
{
  auto it = container.get_it();
  if (not it.has_curr())
    return nullptr;
 
  const typename Container::Item_Type *min_elem = &it.get_curr();
  for (it.next_ne(); it.has_curr(); it.next_ne())
    {
      const auto &curr = it.get_curr();
      if (cmp(curr, *min_elem))
        min_elem = &curr;
    }
  return min_elem;
}
 
template <class Container, class Cmp = std::less<typename Container::Item_Type>>
  requires PredicateWith<Cmp &, const typename Container::Item_Type &, functional_detail::get_curr_cref_t<Container>>
[[nodiscard]] inline const typename Container::Item_Type *max_ptr(const Container &container,
                                                                  Cmp cmp = Cmp())
{
  auto it = container.get_it();
  if (not it.has_curr())
    return nullptr;
 
  const typename Container::Item_Type *max_elem = &it.get_curr();
  for (it.next_ne(); it.has_curr(); it.next_ne())
    {
      const auto &curr = it.get_curr();
      if (cmp(*max_elem, curr))
        max_elem = &curr;
    }
  return max_elem;
}
 
template <class Container, class Cmp = std::less<typename Container::Item_Type>>
  requires PredicateWith<Cmp &, functional_detail::get_curr_cref_t<Container>, const typename Container::Item_Type &> and
           PredicateWith<Cmp &, const typename Container::Item_Type &, functional_detail::get_curr_cref_t<Container>>
[[nodiscard]] inline std::pair<const typename Container::Item_Type *, const typename Container::Item_Type *>
minmax_ptr(const Container &container, Cmp cmp = Cmp())
{
  using T = typename Container::Item_Type;
  auto it = container.get_it();
  if (not it.has_curr())
    return {nullptr, nullptr};
 
  const T *min_elem = &it.get_curr();
  const T *max_elem = min_elem;
  for (it.next_ne(); it.has_curr(); it.next_ne())
    {
      const auto &curr = it.get_curr();
      if (cmp(curr, *min_elem))
        min_elem = &curr;
      if (cmp(*max_elem, curr))
        max_elem = &curr;
    }
  return {min_elem, max_elem};
}
 
template <class Container, class Pred>
  requires PredicateWith<Pred &, functional_detail::get_curr_t<Container>>
[[nodiscard]] inline size_t count_if(const Container &container, Pred pred)
{
  size_t count = 0;
  for (auto it = container.get_it(); it.has_curr(); it.next_ne())
    if (pred(it.get_curr()))
      ++count;
  return count;
}
 
template <AlephSequentialIterableContainer Container, class Equal>
[[nodiscard]] inline bool all_unique(const Container &container, Equal &eq)
{
  using T = typename Container::Item_Type;
  using Eq = std::remove_cvref_t<Equal>;
 
  if constexpr (std::is_same_v<Eq, std::equal_to<T>> and std::copy_constructible<T>
                and requires(const T &v) {
                      { std::hash<T>{}(v) } -> std::convertible_to<size_t>;
                    })
    {
      auto hash = [](const T &value) -> size_t
      {
        return std::hash<T>{}(value);
      };
      return functional_detail::all_unique_hash_path(container, hash, eq);
    }
 
  return functional_detail::pairwise_all_unique(container, eq);
}
 
template <AlephSequentialIterableContainer Container,
          class Equal = std::equal_to<typename Container::Item_Type>>
[[nodiscard]] inline bool all_unique(const Container &container, Equal &&eq = Equal())
{
  return all_unique<Container, Equal>(container, eq);
}
 
template <AlephSequentialIterableContainer Container, class Hash, class Equal>
  requires std::copy_constructible<typename Container::Item_Type>
       and requires(const typename Container::Item_Type &v, Hash h, Equal e) {
             { h(v) } -> std::convertible_to<size_t>;
             { e(v, v) } -> std::convertible_to<bool>;
           }
[[nodiscard]] inline bool all_unique(const Container &container, Hash &hash, Equal &eq)
{
  return functional_detail::all_unique_hash_path(container, hash, eq);
}
 
template <AlephSequentialIterableContainer Container, class Hash, class Equal>
  requires std::copy_constructible<typename Container::Item_Type>
       and requires(const typename Container::Item_Type &v, Hash h, Equal e) {
             { h(v) } -> std::convertible_to<size_t>;
             { e(v, v) } -> std::convertible_to<bool>;
           }
[[nodiscard]] inline bool all_unique(const Container &container, Hash &&hash, Equal &&eq)
{
  using Hash_Type = std::remove_reference_t<Hash>;
  using Eq_Type = std::remove_reference_t<Equal>;
 
  Hash_Type hash_obj = std::forward<Hash>(hash);
  Eq_Type eq_obj = std::forward<Equal>(eq);
  return all_unique(container, hash_obj, eq_obj);
}
 
template <class Container>
[[nodiscard]] inline bool contains(const Container &container,
                                   const typename Container::Item_Type &value)
{
  for (auto it = container.get_it(); it.has_curr(); it.next_ne())
    if (it.get_curr() == value)
      return true;
  return false;
}
 
template <class Container>
[[nodiscard]] inline DynList<std::tuple<size_t, typename Container::Item_Type>> enumerate_tuple(
  const Container &container)
{
  using T = typename Container::Item_Type;
  using Tuple = std::tuple<size_t, T>;
  DynList<Tuple> result;
  size_t i = 0;
  for (auto it = container.get_it(); it.has_curr(); it.next_ne(), ++i)
    result.append(Tuple(i, it.get_curr()));
  return result;
}
 
template <class Container1, class Container2>
[[nodiscard]] inline DynList<std::pair<typename Container1::Item_Type, typename Container2::Item_Type>>
zip_longest(const Container1 &a,
            const Container2 &b,
            const typename Container1::Item_Type &fill_a = typename Container1::Item_Type(),
            const typename Container2::Item_Type &fill_b = typename Container2::Item_Type())
{
  using T1 = typename Container1::Item_Type;
  using T2 = typename Container2::Item_Type;
  DynList<std::pair<T1, T2>> ret_val;
 
  auto it1 = a.get_it();
  auto it2 = b.get_it();
 
  // Process while both have elements
  while (it1.has_curr() and it2.has_curr())
    {
      ret_val.append(std::pair<T1, T2>(it1.get_curr(), it2.get_curr()));
      it1.next_ne();
      it2.next_ne();
    }
 
  // Process remaining elements from the first container
  while (it1.has_curr())
    {
      ret_val.append(std::pair<T1, T2>(it1.get_curr(), fill_b));
      it1.next_ne();
    }
 
  // Process remaining elements from the second container
  while (it2.has_curr())
    {
      ret_val.append(std::pair<T1, T2>(fill_a, it2.get_curr()));
      it2.next_ne();
    }
 
  return ret_val;
}
 
template <class Container1, class Container2>
[[nodiscard]] inline DynList<std::tuple<typename Container1::Item_Type, typename Container2::Item_Type>>
tzip_longest(const Container1 &a,
             const Container2 &b,
             const typename Container1::Item_Type &fill_a = typename Container1::Item_Type(),
             const typename Container2::Item_Type &fill_b = typename Container2::Item_Type())
{
  using T1 = typename Container1::Item_Type;
  using T2 = typename Container2::Item_Type;
  using Tuple = std::tuple<T1, T2>;
  DynList<Tuple> ret_val;
 
  auto it1 = a.get_it();
  auto it2 = b.get_it();
 
  while (it1.has_curr() and it2.has_curr())
    {
      ret_val.append(Tuple(it1.get_curr(), it2.get_curr()));
      it1.next_ne();
      it2.next_ne();
    }
 
  while (it1.has_curr())
    {
      ret_val.append(Tuple(it1.get_curr(), fill_b));
      it1.next_ne();
    }
 
  while (it2.has_curr())
    {
      ret_val.append(Tuple(fill_a, it2.get_curr()));
      it2.next_ne();
    }
 
  return ret_val;
}
 
template <class Container1, class Container2>
[[nodiscard]] inline DynList<std::pair<std::optional<typename Container1::Item_Type>,
                                       std::optional<typename Container2::Item_Type>>>
zip_longest_opt(const Container1 &a, const Container2 &b)
{
  using T1 = typename Container1::Item_Type;
  using T2 = typename Container2::Item_Type;
  using Opt1 = std::optional<T1>;
  using Opt2 = std::optional<T2>;
  DynList<std::pair<Opt1, Opt2>> ret_val;
 
  auto it1 = a.get_it();
  auto it2 = b.get_it();
 
  while (it1.has_curr() and it2.has_curr())
    {
      ret_val.append(std::make_pair(Opt1(it1.get_curr()), Opt2(it2.get_curr())));
      it1.next_ne();
      it2.next_ne();
    }
 
  while (it1.has_curr())
    {
      ret_val.append(std::make_pair(Opt1(it1.get_curr()), std::nullopt));
      it1.next_ne();
    }
 
  while (it2.has_curr())
    {
      ret_val.append(std::make_pair(std::nullopt, Opt2(it2.get_curr())));
      it2.next_ne();
    }
 
  return ret_val;
}
 
template <typename T, template <typename> class Container, class KeyFunc>
[[nodiscard]]
DynList<std::pair<std::invoke_result_t<KeyFunc, const T &>, DynList<T>>> group_by(const Container<T> &c,
                                                                                  KeyFunc key_func)
{
  using Key = std::invoke_result_t<KeyFunc, const T &>;
  using Group = DynList<T>;
  using Result = DynList<std::pair<Key, Group>>;
 
  Result ret;
  if (c.is_empty())
    return ret;
 
  auto it = c.get_it();
  Key curr_key = key_func(it.get_curr());
  Group *curr_group = &ret.append(std::make_pair(curr_key, Group())).second;
  curr_group->append(it.get_curr());
 
  for (it.next_ne(); it.has_curr(); it.next_ne())
    {
      const auto &item = it.get_curr();
      Key new_key = key_func(item);
 
      if (new_key != curr_key)
        {
          curr_key = new_key;
          curr_group = &ret.append(std::make_pair(curr_key, Group())).second;
        }
 
      curr_group->append(item);
    }
 
  return ret;
}
 
template <typename T, template <typename> class Container, class KeyFunc, class KeyEqual>
[[nodiscard]]
DynList<std::pair<std::invoke_result_t<KeyFunc, const T &>, DynList<T>>>
group_by_eq(const Container<T> &c, KeyFunc key_func, KeyEqual key_equal)
{
  using Key = std::invoke_result_t<KeyFunc, const T &>;
  using Group = DynList<T>;
  using Result = DynList<std::pair<Key, Group>>;
 
  Result ret;
  if (c.is_empty())
    return ret;
 
  auto it = c.get_it();
  Key curr_key = key_func(it.get_curr());
  Group *curr_group = &ret.append(std::make_pair(curr_key, Group())).second;
  curr_group->append(it.get_curr());
 
  for (it.next_ne(); it.has_curr(); it.next_ne())
    {
      const auto &item = it.get_curr();
      Key new_key = key_func(item);
 
      if (not key_equal(new_key, curr_key))
        {
          curr_key = new_key;
          curr_group = &ret.append(std::make_pair(curr_key, Group())).second;
        }
 
      curr_group->append(item);
    }
 
  return ret;
}
 
template <typename T, template <typename> class Container, class KeyFunc, class Reducer>
[[nodiscard]]
auto group_by_reduce(const Container<T> &c, KeyFunc key_func, Reducer reducer) -> DynList<
  std::pair<std::invoke_result_t<KeyFunc, const T &>, std::invoke_result_t<Reducer, const DynList<T> &>>>
{
  using Key = std::invoke_result_t<KeyFunc, const T &>;
  using ReducedType = std::invoke_result_t<Reducer, const DynList<T> &>;
  using Result = DynList<std::pair<Key, ReducedType>>;
 
  auto groups = group_by(c, key_func);
  Result ret;
 
  for (auto it = groups.get_it(); it.has_curr(); it.next_ne())
    {
      auto &[key, group] = it.get_curr();
      ret.append(std::make_pair(key, reducer(group)));
    }
 
  return ret;
}
 
}  // end namespace Aleph
 
#endif  // AH_FUNCTIONAL_H