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 <optional>
# include <ah-errors.H>
# include <ah-ranges.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]] virtual T & get_item() override
    {
      ah_invalid_argument() << "Access from None type";
      __builtin_unreachable();  // Satisfies compiler after throw
    }
 
    [[noreturn]] virtual const T & get_item() const override
    {
      ah_invalid_argument() << "Access from None type";
      __builtin_unreachable();
    }
 
    virtual bool is_found() const noexcept override { return false; }
  };
 
  template <typename T> struct Some : public Found_Item<T>
  {
    T & item;
 
    Some(T & i) : item(i) {}
 
    virtual T & get_item() override { return item; }
    virtual const T & get_item() const override { return item; }
    virtual 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 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]] inline 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(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(size_t n, T && item = T())
  {
    return rep<T>(n, item);
  }
 
  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>
  void each(size_t start, size_t end, Op & op)
  {
    for (size_t i = start; i <= end; ++i)
      op();
  }
 
  template <class Op>
  void each(size_t start, size_t end, Op && op)
  {
    each(start, end, op);
  }
 
  template <class Op>
  void each(size_t n, Op & op)
  {
    if (n == 0) return;
    each(0, n - 1, op);
  }
 
  template <class 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, 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> 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> inline
  void enum_for_each(const Container & container, Operation && operation)
  {
    enum_for_each(container, operation);
  }
 
  template <class Container, class Operation> inline
  bool all(Container & container, Operation & operation)
  {
    return container.traverse(operation);
  }
 
  template <class Container, class Operation> inline
  bool all(const Container & container, Operation & operation)
  {
    return container.template traverse<Operation>(operation);
  }
 
  template <class Container, class Operation> inline
  bool all(Container & container, Operation && operation = Operation())
  {
    return all<Container, Operation>(container, operation);
  }
 
  template <class Container, class Operation> 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>
  [[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;
 
    typename Container1::Iterator it1(a);
    typename Container2::Iterator it2(b);
    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;
 
    typename Container1::Iterator it1(a);
    typename Container2::Iterator it2(b);
    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()));
 
    if (it1.has_curr() or it2.has_curr())
      ah_length_error() << "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;
 
    typename Container1::Iterator it1(a);
    typename Container2::Iterator it2(b);
    for (; it1.has_curr() and it2.has_curr(); it1.next_ne(), it2.next_ne())
      ret_val.append(Tuple(it1.get_curr(), it2.get_curr()));
 
    if (it1.has_curr() or it2.has_curr())
      ah_length_error() << "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;
        else 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;
    typename Container::Iterator it(c);
    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()) {}
 
    bool has_curr() const noexcept { return it1.has_curr() and it2.has_curr(); }
 
    bool has_curr1() const noexcept { return it1.has_curr(); }
 
    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();
    }
 
    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;
    I1 i1(c1);
    I2 i2(c2);
    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, size_t pos)
  {
    using I1 = typename C1::Iterator;
    using I2 = typename C2::Iterator;
    I1 i1(c1);
    I2 i2(c2);
    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 function are defined in tpl_dynSetHash.H
 
  // union
  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> [[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> [[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> [[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> [[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>>
  [[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>>
  [[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>>
  [[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> [[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 <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 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 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