ahSort.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 AHSORT_H
#define AHSORT_H
 
#include <algorithm>
#include <functional>
#include <numeric>
#include <stdexcept>
#include <utility>
#include <vector>
 
#include <ah-errors.H>
#include <ahFunctional.H>
#include <tpl_sort_utils.H>
#include <tpl_dynDlist.H>
#include <htlist.H>
#include <ah-zip.H>
 
#define List_Sort(List)                                                 \
                 \
  template <typename T, class Cmp = Aleph::less<T>> [[nodiscard]] inline \
  List<T> sort(const List<T> & c, Cmp & cmp)                            \
  {                                                                     \
    List<T> ret_val = c;                                                \
    mergesort<List, T, Cmp>(ret_val, cmp);                              \
    return ret_val;                                                     \
  }                                                                     \
                                                                        \
                        \
  template <typename T, class Cmp = Aleph::less<T>> [[nodiscard]] inline \
  List<T> sort(const List<T> & c, Cmp && cmp = Cmp())                   \
  {                                                                     \
    return sort<T, Cmp>(c, cmp);                                        \
  }                                                                     \
                                                                        \
\
  template <typename T, class Cmp = Aleph::less<T>> [[nodiscard]] inline \
  List<T> sort(List<T> && c, Cmp & cmp)                                 \
  {                                                                     \
    mergesort<List, T, Cmp>(c, cmp);                                    \
    return std::move(c);                                                \
  }                                                                     \
                                                                        \
                             \
  template <typename T, class Cmp = Aleph::less<T>> [[nodiscard]] inline \
  List<T> sort(List<T> && c, Cmp && cmp = Cmp())                        \
  {                                                                     \
    return sort<T, Cmp>(std::move(c), cmp);                             \
  }                                                                     \
                                                                        \
   \
  template <typename T, class Cmp = Aleph::less<T>> inline              \
  List<T> & in_place_sort(List<T> & c, Cmp & cmp)                       \
  {                                                                     \
    mergeinsertsort(c, cmp);                                            \
    return c;                                                           \
  }                                                                     \
                                                                        \
                     \
  template <typename T, class Cmp = Aleph::less<T>> inline              \
  List<T> & in_place_sort(List<T> & c, Cmp && cmp = Cmp())              \
  {                                                                     \
    return in_place_sort<T, Cmp>(c, cmp);                               \
  }
 
namespace Aleph
{
  // Generate sort overloads for DynList and DynDlist
  List_Sort(DynList);
  List_Sort(DynDlist);
 
  template<typename T, class Cmp = Aleph::less<T>>
  [[nodiscard]] inline
  DynArray<T> sort(const DynArray<T> & a, Cmp && cmp = Cmp())
  {
    DynArray<T> ret_val = a;
    introsort(ret_val, cmp);
    return ret_val;
  }
 
  template<typename T, class Cmp = Aleph::less<T>>
  [[nodiscard]] inline
  DynArray<T> sort(DynArray<T> && a, Cmp && cmp = Cmp())
  {
    introsort(a, cmp);
    return std::move(a);
  }
 
  template<typename T, class Cmp = Aleph::less<T>>
  [[nodiscard]] inline
  Array<T> sort(const Array<T> & a, Cmp && cmp = Cmp())
  {
    Array<T> ret_val = a;
    introsort(ret_val, cmp);
    return ret_val;
  }
 
  template<typename T, class Cmp = Aleph::less<T>>
  [[nodiscard]] inline
  Array<T> sort(Array<T> && a, Cmp && cmp = Cmp())
  {
    introsort(a, cmp);
    return std::move(a);
  }
 
  template<typename Container,
           class Cmp = std::less<typename Container::value_type>>
  [[nodiscard]] inline
  Container stdsort(const Container & c, Cmp cmp = Cmp())
  {
    Container ret = c;
    std::sort(ret.begin(), ret.end(), cmp);
    return ret;
  }
 
  template<typename T, class Cmp = Aleph::less<T>>
  inline
  DynArray<T> & in_place_sort(DynArray<T> & c, Cmp cmp = Cmp())
  {
    introsort(c, cmp);
    return c;
  }
 
  template<typename T, class Cmp = Aleph::less<T>>
  inline
  Array<T> & in_place_sort(Array<T> & c, Cmp cmp = Cmp())
  {
    introsort(c, cmp);
    return c;
  }
 
  template <class C,
            class Compare = Aleph::less<sort_utils_detail::Indexed_Value_Type<C>>>
  [[nodiscard]] inline Array<size_t> argsort(const C &a,
                                             const Compare &cmp = Compare())
  {
    return build_index(a, cmp);
  }
 
  template <class C,
            class Compare = Aleph::less<sort_utils_detail::Indexed_Value_Type<C>>>
  [[nodiscard]] inline Array<size_t> stable_argsort(const C &a,
                                                    const Compare &cmp = Compare())
  {
    return stable_build_index(a, cmp);
  }
 
 
  template<typename T, template <typename> class C>
  class Compute_Ranks
  {
    using P = std::pair<T, size_t>;
 
  public:
    C<size_t> compute_ranks(const C<T> & c)
    {
      const size_t n = c.size();
      C<size_t> indexes;
      indexes.reserve(n);
      for (size_t i = 0; i < n; ++i)
        indexes(i) = i;  // DynArray auto-expands
      quicksort_op(indexes, [&c](auto i1, auto i2)
      {
        return c(i1) < c(i2);
      });
      C<size_t> ret;
      ret.reserve(n);
      for (size_t i = 0; i < n; ++i)
        ret(indexes(i)) = i;  // DynArray auto-expands
      return ret;
    }
 
    template<template <typename Type> class List>
    C<size_t> list_compute_ranks(const List<T> & c)
    {
      C<T> items;
      size_t n = 0;
      C<size_t> indexes;
      c.for_each([&items, &n, &indexes](auto k)
      {
        items.append(k);
        indexes.append(n++);
      });
      quicksort_op(indexes, [&items](auto i1, auto i2)
      {
        return items(i1) < items(i2);
      });
      C<size_t> ret;
      ret.reserve(n);
      for (size_t i = 0; i < n; ++i)
        ret(indexes(i)) = i;  // DynArray auto-expands
      return ret;
    }
 
    C<P> compute_pair_ranks(const C<T> & c)
    {
      const size_t n = c.size();
      C<size_t> indexes;
      indexes.reserve(n);
      for (size_t i = 0; i < n; ++i)
        indexes(i) = i;
      quicksort_op(indexes, [&c](auto i1, auto i2)
      {
        return c(i1) < c(i2);
      });
      C<P> ret;
      ret.reserve(n);
      for (size_t i = 0; i < n; ++i)
        {
          auto idx = indexes(i);
          ret(idx) = P(c(idx), i);
        }
      return ret;
    }
 
    template<template <typename Type> class List>
    C<P> list_pair_ranks(const List<T> & c)
    {
      C<T> items;
      size_t n = 0;
      C<size_t> indexes;
      c.for_each([&items, &n, &indexes](auto k)
      {
        items.append(k);
        indexes.append(n++);
      });
      quicksort_op(indexes, [&items](auto i1, auto i2)
      {
        return items(i1) < items(i2);
      });
      C<P> ret;
      ret.reserve(n);
      for (size_t i = 0; i < n; ++i)
        {
          auto idx = indexes(i);
          ret(idx) = P(items(idx), i);
        }
      return ret;
    }
  };
 
  template<typename T>
  class Compute_Ranks<T, Array>
  {
    using P = std::pair<T, size_t>;
 
  public:
    Array<size_t> compute_ranks(const Array<T> & c)
    {
      const size_t n = c.size();
      Array<size_t> indexes(n);
      for (size_t i = 0; i < n; ++i)
        indexes.append(i);  // Use append to grow size
      quicksort_op(indexes, [&c](auto i1, auto i2)
      {
        return c(i1) < c(i2);
      });
      Array<size_t> ret(n);
      ret.putn(n);  // Allocate n slots (expands size)
      for (size_t i = 0; i < n; ++i)
        ret(indexes(i)) = i;
      return ret;
    }
 
    Array<P> compute_pair_ranks(const Array<T> & c)
    {
      const size_t n = c.size();
      Array<size_t> indexes(n);
      for (size_t i = 0; i < n; ++i)
        indexes.append(i);
      quicksort_op(indexes, [&c](auto i1, auto i2)
      {
        return c(i1) < c(i2);
      });
      Array<P> ret(n);
      ret.putn(n);  // Allocate n slots
      for (size_t i = 0; i < n; ++i)
        {
          auto idx = indexes(i);
          ret(idx) = P(c(idx), i);
        }
      return ret;
    }
  };
 
  template<typename T>
  [[nodiscard]] Array<size_t> ranks(const Array<T> & array)
  {
    return Compute_Ranks<T, Array>().compute_ranks(array);
  }
 
  template<typename T>
  [[nodiscard]] DynArray<size_t> ranks(const DynArray<T> & array)
  {
    return Compute_Ranks<T, DynArray>().compute_ranks(array);
  }
 
  template<typename T>
  [[nodiscard]] DynArray<size_t> ranks(const DynList<T> & l)
  {
    return Compute_Ranks<T, DynArray>().list_compute_ranks(l);
  }
 
  template<typename T>
  [[nodiscard]] DynArray<size_t> ranks(const DynDlist<T> & l)
  {
    return Compute_Ranks<T, DynArray>().list_compute_ranks(l);
  }
 
  template<typename T>
  [[nodiscard]] auto pair_ranks(const Array<T> & c)
  {
    return Compute_Ranks<T, Array>().compute_pair_ranks(c);
  }
 
  template<typename T>
  [[nodiscard]] auto pair_ranks(const DynArray<T> & c)
  {
    return Compute_Ranks<T, DynArray>().compute_pair_ranks(c);
  }
 
  template<typename T>
  [[nodiscard]] auto pair_ranks(const DynList<T> & l)
  {
    Compute_Ranks<T, DynArray> func;
    return func.list_pair_ranks(l);
  }
 
  template<typename T>
  [[nodiscard]] auto pair_ranks(const DynDlist<T> & l)
  {
    Compute_Ranks<T, DynArray> func;
    return func.list_pair_ranks(l);
  }
 
  template<typename C, typename... Args,
           typename Cmp = std::less<typename C::value_type>>
  inline
  void in_place_multisort_arrays(Cmp cmp, const bool stable, C & first, Args &... args)
  {
    const size_t n = first.size();
    if (n == 0)
      return;
 
    const bool all_same_size = ((args.size() == n) && ...);
    ah_invalid_argument_if(not all_same_size)
      << "all arrays must have the same size";
 
    std::vector<size_t> indices(n);
    std::iota(indices.begin(), indices.end(), static_cast<size_t>(0));
 
    const auto index_cmp_unstable = [&first, &cmp](const size_t i1, const size_t i2)
      {
        return cmp(first[i1], first[i2]);
      };
 
    const auto index_cmp_stable = [&first, &cmp](const size_t i1, const size_t i2)
      {
        if (cmp(first[i1], first[i2]))
          return true;
        if (cmp(first[i2], first[i1]))
          return false;
        return i1 < i2;
      };
 
    if (stable)
      Aleph::mergesort(indices.data(), 0L,
                       static_cast<long>(indices.size() - 1), index_cmp_stable);
    else
      Aleph::introsort(indices.data(), indices.size(), index_cmp_unstable);
 
    // Apply permutation.
    // After sorting, indices[new_pos] = old_pos. Build inverse permutation
    // perm[old_pos] = new_pos and fix it in-place via swaps.
    Array<size_t> perm = Array<size_t>::create(n);
    for (size_t new_pos = 0; new_pos < n; ++new_pos)
      perm[indices[new_pos]] = new_pos;
 
    using std::swap;  // Enable ADL for user-defined swap
    for (size_t i = 0; i < n; ++i)
      while (perm[i] != i)
        {
          const size_t j = perm[i];
          swap(first[i], first[j]);
          (swap(args[i], args[j]), ...);
          swap(perm[i], perm[j]);
        }
  }
 
  template<typename C, typename... Args,
           typename Cmp = std::less<typename C::value_type>>
  inline
  void in_place_multisort_arrays(Cmp cmp, C & first, Args &... args)
  {
    in_place_multisort_arrays(std::move(cmp), true, first, args...);
  }
 
 
} // end namespace Aleph
 
#endif // AHSORT_H