ah-stl-functional.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_STL_FUNCTIONAL_H
# define AH_STL_FUNCTIONAL_H
 
# include <type_traits>
# include <vector>
# include <optional>
# include <functional>
# include <algorithm>
# include <numeric>
# include <utility>
# include <tuple>
# include <iterator>
# include <stdexcept>
# include <unordered_set>
# include <unordered_map>
# include <ah-concepts.H>
# include <ah-ranges.H>
 
namespace Aleph
{
  // ============================================================================
  // Type Traits and Concepts
  // ============================================================================
 
  namespace stl_detail
  {
    inline constexpr size_t ADAPTIVE_THRESHOLD = 64;
 
    template <typename T>
    struct has_size : std::bool_constant<requires { std::declval<T>().size(); }> {};
 
    template <typename T>
    inline constexpr bool has_size_v = has_size<T>::value;
 
    template <typename T>
    struct is_std_hashable : std::bool_constant<requires { std::hash<T>{}(std::declval<T>()); }> {};
 
    template <typename T>
    inline constexpr bool is_std_hashable_v = is_std_hashable<T>::value;
 
    template <typename T>
    struct has_reverse_iterators : std::bool_constant<requires
      {
        std::declval<T>().rbegin();
        std::declval<T>().rend();
      }> {};
 
    template <typename T>
    inline constexpr bool has_reverse_iterators_v = has_reverse_iterators<T>::value;
 
    template <typename Container>
    [[nodiscard]] size_t safe_size(const Container & c)
    {
      if constexpr (has_size_v<Container>)
        return c.size();
      else
        return 0;  // Cannot determine size efficiently
    }
 
    template <typename Result, typename Container>
    void try_reserve(Result & result, const Container & c)
    {
      if constexpr (has_size_v<Container>)
        result.reserve(c.size());
    }
 
    template <typename Result>
    void try_reserve_n(Result & result, size_t n)
    {
      if constexpr (requires { result.reserve(n); })
        result.reserve(n);
    }
  } // namespace stl_detail
 
  // ============================================================================
  // Range Generation
  // ============================================================================
 
  template <typename T = int>
  [[nodiscard]] std::vector<T> stl_range(T start, T end, T step = 1)
  {
    std::vector<T> result;
    if (step > 0 and start <= end)
      {
        result.reserve(static_cast<size_t>((end - start) / step + 1));
        for (T i = start; i <= end; i += step)
          result.push_back(i);
      }
    else if (step < 0 and start >= end)
      {
        result.reserve(static_cast<size_t>((start - end) / (-step) + 1));
        for (T i = start; i >= end; i += step)
          result.push_back(i);
      }
    return result;
  }
 
  template <typename T = int>
  [[nodiscard]] std::vector<T> stl_range(T n)
  {
    std::vector<T> result;
    result.reserve(static_cast<size_t>(n));
    for (T i = 0; i < n; ++i)
      result.push_back(i);
    return result;
  }
 
  template <typename T = double>
  [[nodiscard]] std::vector<T> stl_linspace(T start, T end, size_t n)
  {
    std::vector<T> result;
    if (n == 0) return result;
    result.reserve(n);
    if (n == 1)
      {
        result.push_back(start);
        return result;
      }
 
    result.reserve(n);
    const auto step = (end - start) / static_cast<T>(n - 1);
    for (size_t i = 0; i < n; ++i)
      result.push_back(start + static_cast<T>(i) * step);
    return result;
  }
 
  template <typename T>
  [[nodiscard]] std::vector<T> stl_rep(size_t n, const T & value)
  {
    return std::vector<T>(n, value);
  }
 
  template <typename Gen>
  [[nodiscard]] auto stl_generate(size_t n, Gen && gen)
  {
    using T = std::decay_t<decltype(gen(size_t{}))>;
    std::vector<T> result;
    result.reserve(n);
    auto & gen_ref = gen;  // Preserve as lvalue to avoid moving in loop
    for (size_t i = 0; i < n; ++i)
      result.push_back(gen_ref(i));
    return result;
  }
 
  // ============================================================================
  // Core Functional Operations
  // ============================================================================
 
  template <typename Op, typename Container>
  void stl_for_each(Op && op, const Container & c)
  {
    auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      op_ref(item);
  }
 
  template <typename Op, typename Container>
  void stl_for_each_indexed(Op && op, const Container & c)
  {
    auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
    size_t i = 0;
    for (const auto & item: c)
      op_ref(i++, item);
  }
 
  template <typename Op, typename Container>
  [[nodiscard]] auto stl_map(Op && op, const Container & c)
  {
    using T = typename Container::value_type;
    using R = std::decay_t<decltype(op(std::declval<T>()))>;
 
    std::vector<R> result;
    stl_detail::try_reserve(result, c);
    auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      result.push_back(op_ref(item));
    return result;
  }
 
  template <typename Op, typename Container>
  [[nodiscard]] auto stl_mapi(Op && op, const Container & c)
  {
    using T = typename Container::value_type;
    using R = std::decay_t<decltype(op(size_t{}, std::declval<T>()))>;
 
    std::vector<R> result;
    stl_detail::try_reserve(result, c);
    auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
    size_t i = 0;
    for (const auto & item: c)
      result.push_back(op_ref(i++, item));
    return result;
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] auto stl_filter(Pred && pred, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      if (pred_ref(item))
        result.push_back(item);
    return result;
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] auto stl_filteri(Pred && pred, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    size_t i = 0;
    for (const auto & item: c)
      {
        if (pred_ref(i, item))
          result.push_back(item);
        ++i;
      }
    return result;
  }
 
  template <typename T, typename Op, typename Container>
  [[nodiscard]] T stl_foldl(T init, Op && op, const Container & c)
  {
#if ALEPH_HAS_RANGES
    if constexpr (std::ranges::range<Container>)
      return detail::ranges_fold_left(c, std::move(init), std::forward<Op>(op));
    else
#endif
      {
        T acc = std::move(init);
        auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
        for (const auto & item: c)
          acc = op_ref(std::move(acc), item);
        return acc;
      }
  }
 
  template <typename T, typename Op, typename Container>
  [[nodiscard]] T stl_foldr(T init, Op && op, const Container & c)
  {
    static_assert(stl_detail::has_reverse_iterators_v<Container>,
      "stl_foldr requires a container with reverse iterators (rbegin/rend)");
    T acc = std::move(init);
    auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
    for (auto it = c.rbegin(); it != c.rend(); ++it)
      acc = op_ref(*it, std::move(acc));
    return acc;
  }
 
  template <typename T, typename Op, typename Container>
  [[nodiscard]] std::vector<T> stl_scan_left(T init, Op && op, const Container & c)
  {
    std::vector<T> result;
    if constexpr (stl_detail::has_size_v<Container>)
      result.reserve(c.size() + 1);
    result.push_back(init);
 
    T acc = std::move(init);
    auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      {
        acc = op_ref(std::move(acc), item);
        result.push_back(acc);
      }
    return result;
  }
 
  template <typename T, typename Op, typename Container>
  [[nodiscard]] std::vector<T> stl_scan_right(T init, Op && op, const Container & c)
  {
    static_assert(stl_detail::has_reverse_iterators_v<Container>,
      "stl_scan_right requires a container with reverse iterators (rbegin/rend)");
    std::vector<T> result;
    if constexpr (stl_detail::has_size_v<Container>)
      result.reserve(c.size() + 1);
 
    T acc = std::move(init);
    result.push_back(acc);
 
    auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
    for (auto it = c.rbegin(); it != c.rend(); ++it)
      {
        acc = op_ref(*it, std::move(acc));
        result.push_back(acc);
      }
 
    std::reverse(result.begin(), result.end());
    return result;
  }
 
  template <typename T, typename Op, typename Container>
  [[nodiscard]] T stl_reduce(T init, Op && op, const Container & c)
  {
    return stl_foldl(std::move(init), std::forward<Op>(op), c);
  }
 
  // ============================================================================
  // Predicates
  // ============================================================================
 
  template <typename Pred, typename Container>
  [[nodiscard]] bool stl_all(Pred && pred, const Container & c)
  {
#if ALEPH_HAS_RANGES
    if constexpr (std::ranges::range<Container>)
      return detail::ranges_all_of(c, std::forward<Pred>(pred));
    else
#endif
      {
        auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
        for (const auto & item: c)
          if (not pred_ref(item))
            return false;
        return true;
      }
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] bool stl_exists(Pred && pred, const Container & c)
  {
#if ALEPH_HAS_RANGES
    if constexpr (std::ranges::range<Container>)
      return detail::ranges_any_of(c, std::forward<Pred>(pred));
    else
#endif
      {
        auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
        for (const auto & item: c)
          if (pred_ref(item))
            return true;
        return false;
      }
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] bool stl_any(Pred && pred, const Container & c)
  {
    return stl_exists(std::forward<Pred>(pred), c);
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] bool stl_none(Pred && pred, const Container & c)
  {
    return not stl_exists(std::forward<Pred>(pred), c);
  }
 
  // ============================================================================
  // Finding Elements
  // ============================================================================
 
  template <typename Pred, typename Container>
  [[nodiscard]] auto stl_find(Pred && pred, const Container & c)
  {
    using T = typename Container::value_type;
 
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      if (pred_ref(item))
        return std::optional<T>(item);
    return std::optional<T>{};
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] auto stl_find_last(Pred && pred, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::optional<T> result;
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      if (pred_ref(item))
        result = item;
    return result;
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] std::optional<size_t> stl_find_index(Pred && pred, const Container & c)
  {
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    size_t i = 0;
    for (const auto & item: c)
      {
        if (pred_ref(item))
          return i;
        ++i;
      }
    return std::nullopt;
  }
 
  template <typename Op, typename Container>
  [[nodiscard]] auto stl_find_mapi(Op && op, const Container & c)
  {
    using T = typename Container::value_type;
    using OptType = std::decay_t<decltype(op(size_t{}, std::declval<T>()))>;
    static_assert(std::is_default_constructible_v<OptType>,
      "stl_find_mapi requires the return type to be default-constructible (like std::optional)");
 
    auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
    size_t i = 0;
    for (const auto & item: c)
        if (auto result = op_ref(i++, item))
          return result;
    return OptType{};
  }
 
  template <typename T, typename Container>
  [[nodiscard]] bool stl_mem(const T & target, const Container & c)
  {
    for (const auto & item: c)
      if (item == target)
        return true;
    return false;
  }
 
  // ============================================================================
  // Counting
  // ============================================================================
 
  template <typename Pred, typename Container>
  [[nodiscard]] size_t stl_count(Pred && pred, const Container & c)
  {
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    size_t count = 0;
    for (const auto & item: c)
      if (pred_ref(item))
        ++count;
    return count;
  }
 
  template <typename T, typename Container>
  [[nodiscard]] size_t stl_count_value(const T & target, const Container & c)
  {
    size_t count = 0;
    for (const auto & item: c)
      if (item == target)
        ++count;
    return count;
  }
 
  // ============================================================================
  // Taking and Dropping
  // ============================================================================
 
  template <typename Container>
  [[nodiscard]] auto stl_take(size_t n, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    result.reserve(n);
    size_t count = 0;
    for (const auto & item: c)
      {
        if (count >= n) break;
        result.push_back(item);
        ++count;
      }
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_drop(size_t n, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    if constexpr (stl_detail::has_size_v<Container>)
      {
        if (const size_t size = c.size(); size > n)
          result.reserve(size - n);
      }
    size_t count = 0;
    for (const auto & item: c)
      {
        if (count >= n)
          result.push_back(item);
        ++count;
      }
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_take_last(size_t n, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    size_t size = stl_detail::safe_size(c);
 
    // If container doesn't have size(), we need to iterate twice or use a different approach
    if constexpr (!stl_detail::has_size_v<Container>)
      {
        // For containers without size(), collect all then take last n
        std::vector<T> all(c.begin(), c.end());
        size = all.size();
        const size_t skip = size > n ? (size - n) : 0;
        result.reserve(size > n ? n : size);
        for (size_t i = skip; i < size; ++i)
          result.push_back(std::move(all[i]));
        return result;
      }
    else
      {
        size_t actual_n = size > n ? n : size;
        result.reserve(actual_n);
        const size_t skip = size > n ? (size - n) : 0;
 
        size_t count = 0;
        for (const auto & item: c)
          {
            if (count >= skip)
              result.push_back(item);
            ++count;
          }
        return result;
      }
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] auto stl_take_while(Pred && pred, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      {
        if (not pred_ref(item))
          break;
        result.push_back(item);
      }
    return result;
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] auto stl_drop_while(Pred && pred, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    bool dropping = true;
    for (const auto & item: c)
      {
        if (dropping and pred_ref(item))
          continue;
        dropping = false;
        result.push_back(item);
      }
    return result;
  }
 
  // ============================================================================
  // Accessing Elements
  // ============================================================================
 
  template <typename Container>
  [[nodiscard]] auto stl_first(const Container & c)
  {
    using T = typename Container::value_type;
 
    auto it = c.begin();
    if (it == c.end())
      return std::optional<T>{};
    return std::optional<T>(*it);
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_last(const Container & c)
  {
    using T = typename Container::value_type;
 
    auto it = c.begin();
    if (it == c.end())
      return std::optional<T>{};
 
    // Use reverse iterators if available (more efficient)
    if constexpr (stl_detail::has_reverse_iterators_v<Container>)
      {
        return std::optional<T>(*c.rbegin());
      }
    else
      {
        // Fallback: iterate through entire container (for forward_list, etc.)
        T last = *it;
        ++it;
        for (; it != c.end(); ++it)
          last = *it;
        return std::optional<T>(last);
      }
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_nth(const size_t n, const Container & c)
  {
    using T = typename Container::value_type;
 
    size_t i = 0;
    for (const auto & item: c)
      {
        if (i == n)
          return std::optional<T>(item);
        ++i;
      }
    return std::optional<T>{};
  }
 
  // ============================================================================
  // Min/Max
  // ============================================================================
 
  template <typename Container>
  [[nodiscard]] auto stl_min(const Container & c)
  {
    using T = typename Container::value_type;
 
    auto it = c.begin();
    if (it == c.end())
      return std::optional<T>{};
 
    T min_val = *it;
    ++it;
    for (; it != c.end(); ++it)
      if (*it < min_val)
        min_val = *it;
    return std::optional<T>(min_val);
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_max(const Container & c)
  {
    using T = typename Container::value_type;
 
    auto it = c.begin();
    if (it == c.end())
      return std::optional<T>{};
 
    T max_val = *it;
    ++it;
    for (; it != c.end(); ++it)
      if (*it > max_val)
        max_val = *it;
    return std::optional<T>(max_val);
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_min_max(const Container & c)
  {
    using T = typename Container::value_type;
    using ResultType = std::optional<std::pair<T, T>>;
 
    auto it = c.begin();
    if (it == c.end())
      return ResultType{};
 
    T min_val = *it;
    T max_val = *it;
    ++it;
 
    for (; it != c.end(); ++it)
      {
        if (*it < min_val) min_val = *it;
        if (*it > max_val) max_val = *it;
      }
    return ResultType(std::make_pair(min_val, max_val));
  }
 
  template <typename Key, typename Container>
  [[nodiscard]] auto stl_min_by(Key && key, const Container & c)
  {
    using T = typename Container::value_type;
 
    auto it = c.begin();
    if (it == c.end())
      return std::optional<T>{};
 
    auto & key_ref = key;  // Preserve as lvalue to avoid moving in loop
    T min_elem = *it;
    auto min_key = key_ref(min_elem);
    ++it;
 
    for (; it != c.end(); ++it)
      {
        auto k = key_ref(*it);
        if (k < min_key)
          {
            min_key = k;
            min_elem = *it;
          }
      }
    return std::optional<T>(min_elem);
  }
 
  template <typename Key, typename Container>
  [[nodiscard]] auto stl_max_by(Key && key, const Container & c)
  {
    using T = typename Container::value_type;
 
    auto it = c.begin();
    if (it == c.end())
      return std::optional<T>{};
 
    auto & key_ref = key;  // Preserve as lvalue to avoid moving in loop
    T max_elem = *it;
    auto max_key = key_ref(max_elem);
    ++it;
 
    for (; it != c.end(); ++it)
      {
        auto k = key_ref(*it);
        if (k > max_key)
          {
            max_key = k;
            max_elem = *it;
          }
      }
    return std::optional<T>(max_elem);
  }
 
  // ============================================================================
  // Sum and Product
  // ============================================================================
 
  template <typename Container>
  [[nodiscard]] auto stl_sum(const Container & c)
  {
    using T = typename Container::value_type;
    T sum{};
    for (const auto & item: c)
      sum = sum + item;
    return sum;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_product(const Container & c)
  {
    using T = typename Container::value_type;
    if (c.empty()) return T{};
 
    auto it = c.begin();
    T prod = *it;
    ++it;
    for (; it != c.end(); ++it)
      prod = prod * (*it);
    return prod;
  }
 
  // ============================================================================
  // Partitioning
  // ============================================================================
 
  template <typename Pred, typename Container>
  [[nodiscard]] auto stl_partition(Pred && pred, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> matching, non_matching;
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      if (pred_ref(item))
        matching.push_back(item);
      else
        non_matching.push_back(item);
    return std::make_pair(std::move(matching), std::move(non_matching));
  }
 
  // ============================================================================
  // Zipping and Pairing
  // ============================================================================
 
  template <typename Container1, typename Container2>
  [[nodiscard]] auto stl_zip_to_pairs(const Container1 & c1, const Container2 & c2)
  {
    using T1 = typename Container1::value_type;
    using T2 = typename Container2::value_type;
 
    std::vector<std::pair<T1, T2>> result;
    if constexpr (stl_detail::has_size_v<Container1> && stl_detail::has_size_v<Container2>)
      result.reserve(std::min(c1.size(), c2.size()));
    auto it1 = c1.begin();
    auto it2 = c2.begin();
    for (; it1 != c1.end() and it2 != c2.end(); ++it1, ++it2)
      result.emplace_back(*it1, *it2);
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_unzip_pairs(const Container & c)
  {
    using PairType = typename Container::value_type;
    using T1 = std::decay_t<decltype(std::declval<PairType>().first)>;
    using T2 = std::decay_t<decltype(std::declval<PairType>().second)>;
 
    std::vector<T1> v1;
    std::vector<T2> v2;
    stl_detail::try_reserve(v1, c);
    stl_detail::try_reserve(v2, c);
 
    for (const auto & p: c)
      {
        v1.push_back(p.first);
        v2.push_back(p.second);
      }
    return std::make_pair(std::move(v1), std::move(v2));
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_enumerate_to_pairs(const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<std::pair<size_t, T>> result;
    stl_detail::try_reserve(result, c);
    size_t i = 0;
    for (const auto & item: c)
      result.emplace_back(i++, item);
    return result;
  }
 
  // ============================================================================
  // Comparison
  // ============================================================================
 
  template <typename Container1, typename Container2>
  [[nodiscard]] bool stl_equal(const Container1 & c1, const Container2 & c2)
  {
    auto it1 = c1.begin();
    auto it2 = c2.begin();
    for (; it1 != c1.end() and it2 != c2.end(); ++it1, ++it2)
      if (not (*it1 == *it2))
        return false;
    return it1 == c1.end() and it2 == c2.end();
  }
 
  template <typename Container1, typename Container2>
  [[nodiscard]] int stl_compare(const Container1 & c1, const Container2 & c2)
  {
    auto it1 = c1.begin();
    auto it2 = c2.begin();
 
    for (; it1 != c1.end() and it2 != c2.end(); ++it1, ++it2)
      {
        if (*it1 < *it2) return -1;
        if (*it2 < *it1) return 1;
      }
 
    if (it1 == c1.end() and it2 == c2.end()) return 0;
    return (it1 == c1.end()) ? -1 : 1;
  }
 
  // ============================================================================
  // Reversing and Sorting
  // ============================================================================
 
  template <typename Container>
  [[nodiscard]] auto stl_reverse(const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result(c.begin(), c.end());
    std::reverse(result.begin(), result.end());
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_sort(const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result(c.begin(), c.end());
    sort_range(result);
    return result;
  }
 
  template <typename Cmp, typename Container>
  [[nodiscard]] auto stl_sort_by(Cmp && cmp, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result(c.begin(), c.end());
    sort_range(result, std::forward<Cmp>(cmp));
    return result;
  }
 
  // ============================================================================
  // Uniqueness
  // ============================================================================
 
  template <typename Container>
  [[nodiscard]] auto stl_unique(const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    for (const auto & item: c)
        if (result.empty() or not (result.back() == item))
          result.push_back(item);
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_distinct(const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    const size_t size = stl_detail::safe_size(c);
 
    // Use linear search for small containers or if type is not hashable
    if constexpr (!stl_detail::is_std_hashable_v<T>)
      {
        // Linear search only (type not hashable)
        for (const auto & item : c)
          if (std::find(result.begin(), result.end(), item) == result.end())
            result.push_back(item);
      }
    else if (size <= stl_detail::ADAPTIVE_THRESHOLD)
      {
        // Linear search for small containers (better cache, no hash overhead)
        for (const auto & item : c)
          if (std::find(result.begin(), result.end(), item) == result.end())
            result.push_back(item);
      }
    else
      {
        // Hash-based for large containers
        std::unordered_set<T> seen;
        seen.reserve(size);
        for (const auto & item : c)
          if (seen.insert(item).second)
            result.push_back(item);
      }
 
    return result;
  }
 
  // ============================================================================
  // Concatenation and Flattening
  // ============================================================================
 
  template <typename Container1, typename Container2>
  [[nodiscard]] auto stl_concat(const Container1 & c1, const Container2 & c2)
  {
    using T = typename Container1::value_type;
 
    std::vector<T> result;
    if constexpr (stl_detail::has_size_v<Container1> && stl_detail::has_size_v<Container2>)
      result.reserve(c1.size() + c2.size());
    for (const auto & item: c1)
      result.push_back(item);
    for (const auto & item: c2)
      result.push_back(item);
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_flatten(const Container & c)
  {
    using InnerContainer = typename Container::value_type;
    using T = typename InnerContainer::value_type;
 
    std::vector<T> result;
    for (const auto & inner: c)
      for (const auto & item: inner)
        result.push_back(item);
    return result;
  }
 
  template <typename Op, typename Container>
  [[nodiscard]] auto stl_flat_map(Op && op, const Container & c)
  {
    using T = typename Container::value_type;
    using InnerContainer = std::decay_t<decltype(op(std::declval<T>()))>;
    using R = typename InnerContainer::value_type;
 
    std::vector<R> result;
    auto & op_ref = op;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      for (const auto & inner_item: op_ref(item))
        result.push_back(inner_item);
    return result;
  }
 
  // ============================================================================
  // Grouping
  // ============================================================================
 
  template <typename Container>
  [[nodiscard]] auto stl_group(const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<std::vector<T>> result;
    if (c.empty()) return result;
 
    auto it = c.begin();
    result.emplace_back();
    result.back().push_back(*it);
    T current = *it;
    ++it;
 
    for (; it != c.end(); ++it)
      {
        if (not (*it == current))
          {
            result.emplace_back();
            current = *it;
          }
        result.back().push_back(*it);
      }
    return result;
  }
 
  template <typename Key, typename Container>
  [[nodiscard]] auto stl_group_by(Key && key, const Container & c)
  {
    using T = typename Container::value_type;
    using K = std::decay_t<decltype(key(std::declval<T>()))>;
 
    std::vector<std::pair<K, std::vector<T>>> result;
    auto & key_ref = key;  // Preserve as lvalue to avoid moving in loop
    const size_t size = stl_detail::safe_size(c);
 
    // Use linear search for small containers or if key type is not hashable
    if constexpr (!stl_detail::is_std_hashable_v<K>)
      {
        // Linear search only (key type not hashable)
        for (const auto & item : c)
          {
            auto k = key_ref(item);
            auto it = std::find_if(result.begin(), result.end(),
                                   [&k](const auto & p) { return p.first == k; });
            if (it != result.end())
              it->second.push_back(item);
            else
              result.emplace_back(std::move(k), std::vector<T>{item});
          }
      }
    else if (size <= stl_detail::ADAPTIVE_THRESHOLD)
      {
        // Linear search for small containers
        for (const auto & item : c)
          {
            auto k = key_ref(item);
            auto it = std::find_if(result.begin(), result.end(),
                                   [&k](const auto & p) { return p.first == k; });
            if (it != result.end())
              it->second.push_back(item);
            else
              result.emplace_back(std::move(k), std::vector<T>{item});
          }
      }
    else
      {
        // Hash-based for large containers
        std::unordered_map<K, size_t> key_to_index;
        key_to_index.reserve(size);
 
        for (const auto & item : c)
          {
            auto k = key_ref(item);
            auto [it, inserted] = key_to_index.try_emplace(k, result.size());
            if (inserted)
              result.emplace_back(std::move(k), std::vector<T>{item});
            else
              result[it->second].second.push_back(item);
          }
      }
 
    return result;
  }
 
  // ============================================================================
  // Combinatorics: Permutations, Combinations, Arrangements
  // ============================================================================
 
  namespace stl_comb_detail
  {
    template <typename T, typename Op>
    bool permutations_impl(std::vector<T> & arr, size_t start, Op & op_ref)
    {
      if (start >= arr.size())
        return op_ref(arr);
 
      for (size_t i = start; i < arr.size(); ++i)
        {
          std::swap(arr[start], arr[i]);
          if (not permutations_impl(arr, start + 1, op_ref))
            {
              std::swap(arr[start], arr[i]);
              return false;
            }
          std::swap(arr[start], arr[i]);
        }
      return true;
    }
 
    template <typename T, typename Op>
    bool combinations_impl(const std::vector<T> & arr, size_t k, size_t start,
                           std::vector<T> & current, Op & op_ref)
    {
      if (current.size() == k)
        return op_ref(current);
 
      for (size_t i = start; i <= arr.size() - (k - current.size()); ++i)
        {
          current.push_back(arr[i]);
          if (not combinations_impl(arr, k, i + 1, current, op_ref))
            {
              current.pop_back();
              return false;
            }
          current.pop_back();
        }
      return true;
    }
 
    template <typename T, typename Op>
    bool arrangements_impl(const std::vector<T> & arr, size_t k,
                           std::vector<T> & current, std::vector<bool> & used, Op & op_ref)
    {
      if (current.size() == k)
        return op_ref(current);
 
      for (size_t i = 0; i < arr.size(); ++i)
        {
          if (used[i]) continue;
          used[i] = true;
          current.push_back(arr[i]);
          if (not arrangements_impl(arr, k, current, used, op_ref))
            {
              current.pop_back();
              used[i] = false;
              return false;
            }
          current.pop_back();
          used[i] = false;
        }
      return true;
    }
  } // namespace stl_comb_detail
 
  template <typename Op, typename Container>
  bool stl_traverse_permutations(Op && op, const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<T> arr(c.begin(), c.end());
    auto & op_ref = op;  // Preserve as lvalue for recursive calls
    return stl_comb_detail::permutations_impl(arr, 0, op_ref);
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_permutations(const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<std::vector<T>> result;
 
    stl_traverse_permutations([&result](const std::vector<T> & p)
                                {
                                  result.push_back(p);
                                  return true;
                                }, c);
 
    return result;
  }
 
  template <typename Op, typename Container>
  bool stl_traverse_combinations(size_t k, Op && op, const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<T> arr(c.begin(), c.end());
 
    if (k > arr.size())
      return true;
 
    std::vector<T> current;
    current.reserve(k);
    auto & op_ref = op;  // Preserve as lvalue for recursive calls
    return stl_comb_detail::combinations_impl(arr, k, 0, current, op_ref);
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_combinations(size_t k, const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<std::vector<T>> result;
 
    stl_traverse_combinations(k, [&result](const std::vector<T> & combo)
                                {
                                  result.push_back(combo);
                                  return true;
                                }, c);
 
    return result;
  }
 
  template <typename Op, typename Container>
  bool stl_traverse_arrangements(size_t k, Op && op, const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<T> arr(c.begin(), c.end());
 
    if (k > arr.size())
      return true;
 
    std::vector<T> current;
    current.reserve(k);
    std::vector<bool> used(arr.size(), false);
    auto & op_ref = op;  // Preserve as lvalue for recursive calls
    return stl_comb_detail::arrangements_impl(arr, k, current, used, op_ref);
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_arrangements(size_t k, const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<std::vector<T>> result;
 
    stl_traverse_arrangements(k, [&result](const std::vector<T> & arr)
                                {
                                  result.push_back(arr);
                                  return true;
                                }, c);
 
    return result;
  }
 
  template <typename T>
  [[nodiscard]] auto stl_cartesian_product(const std::vector<std::vector<T>> & containers)
  {
    std::vector<std::vector<T>> result;
 
    if (containers.empty())
      return result;
 
    // Start with first container
    for (const auto & elem: containers[0])
      result.push_back({elem});
 
    // Extend with each subsequent container
    for (size_t i = 1; i < containers.size(); ++i)
      {
        std::vector<std::vector<T>> new_result;
        for (const auto & partial: result)
          for (const auto & elem: containers[i])
            {
              auto extended = partial;
              extended.push_back(elem);
              new_result.push_back(std::move(extended));
            }
        result = std::move(new_result);
      }
 
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_power_set(const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<T> arr(c.begin(), c.end());
    std::vector<std::vector<T>> result;
 
    const size_t n = arr.size();
 
    // Protect against overflow: 2^n overflows for n >= 64
    if (n >= 63)
      throw std::overflow_error("stl_power_set: container too large (n >= 63 would overflow)");
 
    const size_t total = 1ULL << n; // 2^n
    result.reserve(total);
 
    for (size_t mask = 0; mask < total; ++mask)
      {
        std::vector<T> subset;
        for (size_t i = 0; i < n; ++i)
          if (mask & (1ULL << i))
            subset.push_back(arr[i]);
        result.push_back(std::move(subset));
      }
 
    return result;
  }
 
  // ============================================================================
  // Additional Ruby/ML-style Operations
  // ============================================================================
 
  template <typename Container>
  [[nodiscard]] auto stl_sliding_window(size_t n, const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<std::vector<T>> result;
 
    if (n == 0) return result;
 
    std::vector<T> arr(c.begin(), c.end());
    if (arr.size() < n) return result;
 
    for (size_t i = 0; i <= arr.size() - n; ++i)
      result.emplace_back(arr.begin() + i, arr.begin() + i + n);
 
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_chunks(size_t n, const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<std::vector<T>> result;
 
    if (n == 0) return result;
 
    std::vector<T> arr(c.begin(), c.end());
 
    for (size_t i = 0; i < arr.size(); i += n)
      {
        size_t end = std::min(i + n, arr.size());
        result.emplace_back(arr.begin() + i, arr.begin() + end);
      }
 
    return result;
  }
 
  template <typename T, typename Container>
  [[nodiscard]] auto stl_intersperse(const T & sep, const Container & c)
  {
    std::vector<T> result;
 
    bool first = true;
    for (const auto & item: c)
      {
        if (not first)
          result.push_back(sep);
        result.push_back(item);
        first = false;
      }
 
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_split_at(size_t n, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> first, second;
    size_t i = 0;
    for (const auto & item: c)
      {
        if (i < n)
          first.push_back(item);
        else
          second.push_back(item);
        ++i;
      }
 
    return std::make_pair(std::move(first), std::move(second));
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] auto stl_span(Pred && pred, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> first, second;
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    bool taking = true;
 
    for (const auto & item: c)
      if (taking and pred_ref(item))
        first.push_back(item);
      else
        {
          taking = false;
          second.push_back(item);
        }
 
    return std::make_pair(std::move(first), std::move(second));
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_init(const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<T> arr(c.begin(), c.end());
 
    if (not arr.empty())
      arr.pop_back();
 
    return arr;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_tail(const Container & c)
  {
    using T = typename Container::value_type;
    std::vector<T> result;
 
    bool first = true;
    for (const auto & item: c)
      {
        if (first)
          first = false;
        else
          result.push_back(item);
      }
 
    return result;
  }
 
  template <typename Container>
  [[nodiscard]] auto stl_tally(const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<std::pair<T, size_t>> result;
    const size_t size = stl_detail::safe_size(c);
 
    // Use linear search for small containers or if type is not hashable
    if constexpr (!stl_detail::is_std_hashable_v<T>)
      {
        // Linear search only (type not hashable)
        for (const auto & item : c)
          {
            auto it = std::find_if(result.begin(), result.end(),
                                   [&item](const auto & p) { return p.first == item; });
            if (it != result.end())
              ++it->second;
            else
              result.emplace_back(item, 1);
          }
      }
    else if (size <= stl_detail::ADAPTIVE_THRESHOLD)
      {
        // Linear search for small containers
        for (const auto & item : c)
          {
            auto it = std::find_if(result.begin(), result.end(),
                                   [&item](const auto & p) { return p.first == item; });
            if (it != result.end())
              ++it->second;
            else
              result.emplace_back(item, 1);
          }
      }
    else
      {
        // Hash-based for large containers
        std::unordered_map<T, size_t> counts;
        counts.reserve(size);
        std::vector<T> order;  // Track insertion order
        order.reserve(size);
 
        for (const auto & item : c)
          {
            auto [it, inserted] = counts.try_emplace(item, 0);
            ++it->second;
            if (inserted)
              order.push_back(item);
          }
 
        result.reserve(order.size());
        for (const auto & item : order)
          result.emplace_back(item, counts[item]);
      }
 
    return result;
  }
 
  template <typename Pred, typename Container>
  [[nodiscard]] auto stl_reject(Pred && pred, const Container & c)
  {
    using T = typename Container::value_type;
 
    std::vector<T> result;
    auto & pred_ref = pred;  // Preserve as lvalue to avoid moving in loop
    for (const auto & item: c)
      if (not pred_ref(item))
        result.push_back(item);
    return result;
  }
} // end namespace Aleph
 
# endif // AH_STL_FUNCTIONAL_H