ah-ranges.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_RANGES_H
#define AH_RANGES_H
 
// Check for C++20 ranges support
// We need both the header AND the actual implementation.
// libc++ in Clang 14 has <ranges> header but incomplete implementation.
//
// Detection strategy:
// - GCC 11+: __cpp_lib_ranges >= 202106L (basic ranges support)
// - GCC 12+: __cpp_lib_ranges >= 202110L (complete ranges support)
// - Clang with libc++: Often has <ranges> but incomplete std::views
//
// We accept __cpp_lib_ranges >= 202106L for GCC, but exclude Clang + libc++
// which has the header but incomplete views implementation.
// Manual override (portability escape hatch):
//   - Define ALEPH_NO_RANGES (e.g. -DALEPH_NO_RANGES) to force ranges support
//     OFF regardless of what the compiler reports.
//   - Or pre-define ALEPH_HAS_RANGES to 0/1 to skip auto-detection entirely.
//   This lets users on toolchains whose std::ranges is present but unreliable
//   opt out without editing the library.
#if defined(ALEPH_NO_RANGES)
#undef ALEPH_HAS_RANGES
#define ALEPH_HAS_RANGES 0
#endif
 
// <version> defines the standard library feature-test macros (e.g.
// __cpp_lib_ranges) without pulling in a heavy header. It must be included
// before the detection below, otherwise __cpp_lib_ranges is undefined and the
// check wrongly resolves to "no ranges".
#if __has_include(<version>)
#include <version>
#endif
 
#ifndef ALEPH_HAS_RANGES
#if __cplusplus >= 202002L && __has_include(<ranges>) &&                     \
      defined(__cpp_lib_ranges) && __cpp_lib_ranges >= 202106L
// Exclude Clang with libc++ < 16 (incomplete std::views implementation)
#if defined(_LIBCPP_VERSION) && _LIBCPP_VERSION < 160000
#define ALEPH_HAS_RANGES 0
#else
#define ALEPH_HAS_RANGES 1
#endif
#else
#define ALEPH_HAS_RANGES 0
#endif
#endif
 
// Support headers required by the C++20 baseline (always available).
#include <algorithm>
#include <iterator>
#include <concepts>
 
// The <ranges> header is pulled in only when the feature is actually enabled.
#if ALEPH_HAS_RANGES
#include <ranges>
#endif
 
// Feature detection for C++23 views
#ifdef __cpp_lib_ranges_stride
#define ALEPH_HAS_STRIDE 1
#else
#define ALEPH_HAS_STRIDE 0
#endif
 
#ifdef __cpp_lib_ranges_repeat
#define ALEPH_HAS_REPEAT 1
#else
#define ALEPH_HAS_REPEAT 0
#endif
 
#ifdef __cpp_lib_ranges_zip
#define ALEPH_HAS_ZIP 1
#else
#define ALEPH_HAS_ZIP 0
#endif
 
#ifdef __cpp_lib_ranges_enumerate
#define ALEPH_HAS_ENUMERATE 1
#else
#define ALEPH_HAS_ENUMERATE 0
#endif
 
// `std::views::join` is C++20 but the adaptor object (as opposed to
// the `std::ranges::join_view` class) was incomplete in libc++ until
// version 17. AppleClang 15 (shipped with Xcode 15 on macos-14) reports
// `_LIBCPP_VERSION = 16xxxx` and triggers a compile error on the join
// pipeline. Conservatively disable the wrapper when libc++ is older
// than 17; libstdc++ exposes the adaptor since GCC 11.
#if defined(_LIBCPP_VERSION) && _LIBCPP_VERSION < 170000
#define ALEPH_HAS_JOIN 0
#else
#define ALEPH_HAS_JOIN 1
#endif
 
#include <type_traits>
#include <utility>
#include <tuple>
#include <functional>
 
namespace Aleph {
 
template <typename Range, typename Cmp>
inline void sort_range(Range &r, Cmp cmp)
#if ALEPH_HAS_RANGES
{
  std::ranges::sort(r, std::move(cmp));
}
#else
{
  std::sort(std::begin(r), std::end(r), std::move(cmp));
}  // NOLINT(modernize-use-ranges)
#endif
 
template <typename Range>
inline void sort_range(Range &r)
#if ALEPH_HAS_RANGES
{
  std::ranges::sort(r, std::ranges::less{});
}
#else
{
  std::sort(std::begin(r), std::end(r));
}  // NOLINT(modernize-use-ranges)
#endif
 
// Forward declarations for major Aleph containers with simple template signatures.
// Containers with complex template signatures (like DynSetTree, DynBinHeap)
// should use the generic to<Container>() adaptor instead.
template <typename T>
class DynList;
template <typename T>
class DynArray;
template <typename T>
class DynDlist;
template <typename T>
class DynListStack;
template <typename T>
class DynListQueue;
template <typename T>
class ArrayStack;
template <typename T>
class ArrayQueue;
template <typename T>
class Random_Set;
 
#if ALEPH_HAS_RANGES
 
// ============================================================================
// Concepts for Aleph containers
// ============================================================================
 
template <typename C>
concept AlephContainer = requires(C c) {
  typename C::Iterator;
  typename C::Item_Type;
  { c.begin() } -> std::input_or_output_iterator;
  { c.end() } -> std::sentinel_for<decltype(c.begin())>;
};
 
template <typename C>
concept AlephAppendable =
  AlephContainer<C> && requires(C c, typename C::Item_Type v) { c.append(v); };
 
template <typename R>
concept RangeLike = std::ranges::range<R>;
 
// ============================================================================
// Range Adaptors - Convert ranges to Aleph containers
// ============================================================================
 
template <AlephAppendable Container, RangeLike R>
[[nodiscard]] Container to_aleph(R &&r)
{
  Container result;
  for (auto &&elem : r)
    result.append(std::forward<decltype(elem)>(elem));
  return result;
}
 
// ============================================================================
// Lazy Range Generation (zero-allocation until materialized)
// ============================================================================
 
template <typename T = int>
[[nodiscard]] constexpr auto lazy_range(T start, T end)
{
  return std::views::iota(start, end);
}
 
template <typename T = int>
[[nodiscard]] constexpr auto lazy_range(T n)
{
  return std::views::iota(T{0}, n);
}
 
template <typename T = int>
[[nodiscard]] constexpr auto lazy_iota(T start = T{0})
{
  return std::views::iota(start);
}
 
#if ALEPH_HAS_REPEAT
template <typename T>
[[nodiscard]] constexpr auto lazy_repeat(const T &value, size_t n)
{
  return std::views::repeat(value) | std::views::take(n);
}
#endif
 
// ============================================================================
// Internal Utilities using Ranges (for performance optimization)
// ============================================================================
 
namespace detail {
 
template <RangeLike R, typename Pred>
[[nodiscard]] constexpr bool ranges_all_of(R &&r, Pred &&pred)
{
  return std::ranges::all_of(std::forward<R>(r), std::forward<Pred>(pred));
}
 
template <RangeLike R, typename Pred>
[[nodiscard]] constexpr bool ranges_any_of(R &&r, Pred &&pred)
{
  return std::ranges::any_of(std::forward<R>(r), std::forward<Pred>(pred));
}
 
template <RangeLike R, typename Pred>
[[nodiscard]] constexpr bool ranges_none_of(R &&r, Pred &&pred)
{
  return std::ranges::none_of(std::forward<R>(r), std::forward<Pred>(pred));
}
 
template <RangeLike R, typename Pred>
[[nodiscard]] constexpr auto ranges_find_if(R &&r, Pred &&pred)
{
  return std::ranges::find_if(std::forward<R>(r), std::forward<Pred>(pred));
}
 
template <RangeLike R, typename Pred>
[[nodiscard]] constexpr auto ranges_count_if(R &&r, Pred &&pred)
{
  return std::ranges::count_if(std::forward<R>(r), std::forward<Pred>(pred));
}
 
template <RangeLike R, typename Func>
[[nodiscard]] constexpr auto ranges_transform(R &&r, Func &&func)
{
  return std::forward<R>(r) | std::views::transform(std::forward<Func>(func));
}
 
template <RangeLike R, typename Pred>
[[nodiscard]] constexpr auto ranges_filter(R &&r, Pred &&pred)
{
  return std::forward<R>(r) | std::views::filter(std::forward<Pred>(pred));
}
 
template <RangeLike R>
[[nodiscard]] constexpr auto ranges_take(R &&r, size_t n)
{
  return std::forward<R>(r) | std::views::take(n);
}
 
template <RangeLike R>
[[nodiscard]] constexpr auto ranges_drop(R &&r, size_t n)
{
  return std::forward<R>(r) | std::views::drop(n);
}
 
template <RangeLike R>
  requires std::ranges::bidirectional_range<R>
[[nodiscard]] constexpr auto ranges_reverse(R &&r)
{
  return std::forward<R>(r) | std::views::reverse;
}
 
#if ALEPH_HAS_JOIN
template <RangeLike R>
[[nodiscard]] constexpr auto ranges_flatten(R &&r)
{
  return std::forward<R>(r) | std::views::join;
}
#endif
 
#if ALEPH_HAS_ZIP
template <RangeLike... Rs>
[[nodiscard]] constexpr auto ranges_zip(Rs &&...rs)
{
  return std::views::zip(std::forward<Rs>(rs)...);
}
#endif
 
#if ALEPH_HAS_ENUMERATE
template <RangeLike R>
[[nodiscard]] constexpr auto ranges_enumerate(R &&r)
{
  return std::forward<R>(r) | std::views::enumerate;
}
#endif
 
template <RangeLike R, typename T, typename BinaryOp>
[[nodiscard]] constexpr T ranges_fold_left(R &&r, T init, BinaryOp &&op)
{
#ifdef __cpp_lib_ranges_fold
  return std::ranges::fold_left(std::forward<R>(r), init, std::forward<BinaryOp>(op));
#else
  // Fallback for C++20 - use explicit variable to avoid rvalue issues
  for (auto &&elem : r)
    init = op(init, elem);
  return init;
#endif
}
 
template <RangeLike R>
[[nodiscard]] constexpr auto ranges_sum(R &&r)
{
  using T = std::ranges::range_value_t<R>;
  return ranges_fold_left(std::forward<R>(r), T{0}, std::plus<>{});
}
 
template <RangeLike R>
[[nodiscard]] constexpr auto ranges_product(R &&r)
{
  using T = std::ranges::range_value_t<R>;
  return ranges_fold_left(std::forward<R>(r), T{1}, std::multiplies<>{});
}
 
template <RangeLike R>
[[nodiscard]] constexpr auto ranges_min(R &&r)
{
  return std::ranges::min_element(std::forward<R>(r));
}
 
template <RangeLike R>
[[nodiscard]] constexpr auto ranges_max(R &&r)
{
  return std::ranges::max_element(std::forward<R>(r));
}
 
template <RangeLike R, typename Comp = std::less<>>
constexpr void ranges_sort(R &&r, Comp &&comp = Comp{})
{
  std::ranges::sort(std::forward<R>(r), std::forward<Comp>(comp));
}
 
}  // namespace detail
 
// ============================================================================
// Pipe Operator Support for Aleph Containers
// ============================================================================
 
struct aleph_adaptor_tag
{
};
 
template <typename T>
concept AlephAdaptor = std::derived_from<std::remove_cvref_t<T>, aleph_adaptor_tag>;
 
template <typename R, AlephAdaptor Adaptor>
  requires std::ranges::range<std::remove_cvref_t<R>>
[[nodiscard]] auto operator | (R &&r, const Adaptor &adaptor)
{
  return adaptor(std::forward<R>(r));
}
 
template <template <typename> class Container>
struct to_aleph_adaptor : aleph_adaptor_tag
{
  template <typename R>
    requires std::ranges::range<std::remove_cvref_t<R>>
  [[nodiscard]] auto operator () (R &&r) const
  {
    using T = std::ranges::range_value_t<std::remove_cvref_t<R>>;
    Container<T> result;
    for (auto &&elem : r)
      result.append(std::forward<decltype(elem)>(elem));
    return result;
  }
};
 
inline constexpr to_aleph_adaptor<DynList> to_dynlist_v{};
 
inline constexpr to_aleph_adaptor<DynArray> to_dynarray_v{};
 
inline constexpr to_aleph_adaptor<DynDlist> to_dyndlist_v{};
 
template <template <typename> class Container>
struct to_aleph_push_adaptor : aleph_adaptor_tag
{
  template <typename R>
    requires std::ranges::range<std::remove_cvref_t<R>>
  [[nodiscard]] auto operator () (R &&r) const
  {
    using T = std::ranges::range_value_t<std::remove_cvref_t<R>>;
    Container<T> result;
    for (auto &&elem : r)
      result.push(std::forward<decltype(elem)>(elem));
    return result;
  }
};
 
inline constexpr to_aleph_push_adaptor<DynListStack> to_dynliststack_v{};
 
inline constexpr to_aleph_push_adaptor<ArrayStack> to_arraystack_v{};
 
template <template <typename> class Container>
struct to_aleph_put_adaptor : aleph_adaptor_tag
{
  template <typename R>
    requires std::ranges::range<std::remove_cvref_t<R>>
  [[nodiscard]] auto operator () (R &&r) const
  {
    using T = std::ranges::range_value_t<std::remove_cvref_t<R>>;
    Container<T> result;
    for (auto &&elem : r)
      result.put(std::forward<decltype(elem)>(elem));
    return result;
  }
};
 
inline constexpr to_aleph_put_adaptor<DynListQueue> to_dynlistqueue_v{};
 
inline constexpr to_aleph_put_adaptor<ArrayQueue> to_arrayqueue_v{};
 
inline constexpr to_aleph_adaptor<Random_Set> to_randomset_v{};
 
template <template <typename, typename...> class Container, typename... ExtraArgs>
struct to_aleph_insert_adaptor : aleph_adaptor_tag
{
  template <typename R>
    requires std::ranges::range<std::remove_cvref_t<R>>
  [[nodiscard]] auto operator () (R &&r) const
  {
    using T = std::ranges::range_value_t<std::remove_cvref_t<R>>;
    Container<T, ExtraArgs...> result;
    for (auto &&elem : r)
      result.insert(std::forward<decltype(elem)>(elem));
    return result;
  }
};
 
template <typename Container, RangeLike R>
[[nodiscard]] Container collect(R &&r)
{
  Container result;
  for (auto &&elem : r)
    {
      if constexpr (requires { result.append(elem); })
        result.append(std::forward<decltype(elem)>(elem));
      else if constexpr (requires { result.insert(elem); })
        result.insert(std::forward<decltype(elem)>(elem));
      else if constexpr (requires { result.push(elem); })
        result.push(std::forward<decltype(elem)>(elem));
      else
        static_assert(sizeof(Container) == 0,
                      "Container must have append(), insert(), or push() method");
    }
  return result;
}
 
template <typename Container>
struct to_adaptor : aleph_adaptor_tag
{
  template <typename R>
    requires std::ranges::range<std::remove_cvref_t<R>>
  [[nodiscard]] Container operator () (R &&r) const
  {
    return collect<Container>(std::forward<R>(r));
  }
};
 
template <typename Container>
[[nodiscard]] constexpr to_adaptor<Container> to()
{
  return {};
}
 
#else  // !ALEPH_HAS_RANGES
 
// ============================================================================
// Fallback for C++17 and earlier
// ============================================================================
 
// Define ALEPH_HAS_RANGES as 0 for feature detection
// The public API in ahFunctional.H will be used instead
 
namespace detail {
 
// Fallback implementations that work without ranges
template <typename Container, typename Pred>
[[nodiscard]] bool fallback_all_of(const Container &c, Pred &&pred)
{
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    if (!pred(it.get_curr()))
      return false;
  return true;
}
 
template <typename Container, typename Pred>
[[nodiscard]] bool fallback_any_of(const Container &c, Pred &&pred)
{
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    if (pred(it.get_curr()))
      return true;
  return false;
}
 
template <typename Container, typename Pred>
[[nodiscard]] bool fallback_none_of(const Container &c, Pred &&pred)
{
  return !fallback_any_of(c, std::forward<Pred>(pred));
}
 
template <typename Container, typename T, typename BinaryOp>
[[nodiscard]] constexpr T ranges_fold_left(Container &&c, T init, BinaryOp &&op)
{
  for (auto &&elem : c)
    init = op(std::move(init), elem);
  return init;
}
 
template <typename Container, typename Pred>
[[nodiscard]] bool ranges_all_of(const Container &c, Pred &&pred)
{
  for (const auto &elem : c)
    if (!pred(elem))
      return false;
  return true;
}
 
template <typename Container, typename Pred>
[[nodiscard]] bool ranges_any_of(const Container &c, Pred &&pred)
{
  for (const auto &elem : c)
    if (pred(elem))
      return true;
  return false;
}
 
template <typename Container, typename Pred>
[[nodiscard]] bool ranges_none_of(const Container &c, Pred &&pred)
{
  return !ranges_any_of(c, std::forward<Pred>(pred));
}
 
template <typename Container, typename Pred>
[[nodiscard]] auto ranges_count_if(const Container &c, Pred &&pred)
{
  size_t count = 0;
  for (const auto &elem : c)
    if (pred(elem))
      ++count;
  return count;
}
 
}  // namespace detail
 
#endif  // ALEPH_HAS_RANGES
 
}  // namespace Aleph
 
#endif  // AH_RANGES_H