Program Listing for File algorithm.hpp

↰ Return to documentation for file (SeQuant/core/algorithm.hpp)

//
// Created by Eduard Valeyev on 2019-02-19.
//

#ifndef SEQUANT_ALGORITHM_HPP
#define SEQUANT_ALGORITHM_HPP

#include <SeQuant/core/container.hpp>
#include <SeQuant/core/meta.hpp>
#include <SeQuant/core/utility/swap.hpp>

#include <range/v3/view/slice.hpp>

#include <algorithm>
#include <bit>
#include <functional>
#include <iterator>
#include <optional>
#include <ranges>
#include <tuple>
#include <type_traits>

namespace sequant {

template <typename Callable, typename... Args>
using suitable_call_operator =
    decltype(std::declval<Callable>()(std::declval<Args>()...));

template <typename ForwardIter, typename Sentinel,
          typename Compare = std::less<>>
void bubble_sort(ForwardIter begin, Sentinel end, Compare comp = {}) {
  if (begin == end) return;  // no-op for empty range
  bool swapped;
  do {
    swapped = false;
    auto i = begin;
    auto inext = i;

    using deref_type = decltype(*(std::declval<ForwardIter>()));
    constexpr const bool comp_works_for_range_type =
        meta::is_detected_v<suitable_call_operator, Compare, deref_type,
                            deref_type>;

    for (++inext; inext != end; ++i, ++inext) {
      if constexpr (comp_works_for_range_type) {
        const auto& val0 = *inext;
        const auto& val1 = *i;
        if (comp(val0, val1)) {
          // current assumption: whenever iter_swap from below does not fall
          // back to std::iter_swap, we are handling zipped ranges where the
          // tuple sizes is two (even) -> thus using a non-std swap
          // implementation won't mess with the information of whether or not an
          // even amount of swaps has occurred.
          using ranges::iter_swap;
          iter_swap(i, inext);
          swapped = true;
        }
      } else {
        const auto& val0 = *inext;
        const auto& val1 = *i;
        static_assert(std::tuple_size_v<std::decay_t<decltype(val0)>> == 2,
                      "need to generalize comparer to handle tuples");
        using lhs_type = decltype(std::get<0>(val0));
        using rhs_type = decltype(std::get<1>(val0));
        constexpr const bool comp_works_for_tuple_entries =
            meta::is_detected_v<suitable_call_operator, Compare, lhs_type,
                                rhs_type>;
        static_assert(comp_works_for_tuple_entries,
                      "Provided comparator not suitable for entries in "
                      "tuple-like objects (in zipped range?)");

        auto composite_compare = [&comp](auto&& c0, auto&& c1) {
          if (comp(std::get<0>(c0), std::get<0>(c1))) {  // c0[0] < c1[0]
            return true;
          } else if (!comp(std::get<0>(c1),
                           std::get<0>(c0))) {  // c0[0] == c1[0]
            return comp(std::get<1>(c0), std::get<1>(c1));
          } else {  // c0[0] > c1[0]
            return false;
          }
        };
        auto composite_swap = [](auto& c0, auto& c1) {
          using std::swap;
          swap(std::get<0>(c0), std::get<0>(c1));
          swap(std::get<1>(c0), std::get<1>(c1));
        };
        if (composite_compare(val0, val1)) {
          composite_swap(val1, val0);
          swapped = true;
        }
      }
    }
  } while (swapped);
}

template <typename Range, typename T>
std::optional<std::size_t> find_position(const Range& rng, const T& value) {
  std::size_t pos = 0;
  for (auto&& elem : rng) {
    if (elem == value) return pos;
    ++pos;
  }
  return std::nullopt;
}

template <std::ranges::forward_range Range>
bool has_duplicates(const Range& rng) {
  const auto the_end = std::ranges::end(rng);
  for (auto it = std::ranges::begin(rng); it != the_end; ++it) {
    if (std::ranges::find(std::next(it), the_end, *it) != the_end) return true;
  }
  return false;
}

namespace detail {
template <typename T>
struct swap_counter_key {
  using type = T;
};
template <typename T>
struct swap_counter_key<SwapCountable<T>> {
  using type = T;
};
template <typename T>
struct swap_counter_key<SwapCountableRef<T>> {
  using type = T;
};
}  // namespace detail

template <std::ranges::range Range, typename Compare = std::less<>>
int bubble_sort_parity(Range&& rng, Compare comp = {}) {
  using counter_key = typename detail::swap_counter_key<
      std::ranges::range_value_t<Range>>::type;
  reset_ts_swap_counter<counter_key>();
  bubble_sort(std::ranges::begin(rng), std::ranges::end(rng), comp);
  return ts_swap_counter_is_even<counter_key>() ? +1 : -1;
}

template <typename BidirIt,
          typename Comp = std::less<decltype(*std::declval<BidirIt>())>>
bool next_permutation_parity(int& parity, BidirIt first, BidirIt last,
                             Comp const& comp = {}) {
  BidirIt i = last;
  if (first == last || first == --i) return false;

  for (;;) {
    BidirIt ii = i;
    --i;
    if (comp(*i, *ii)) {
      BidirIt j = last;

      while (!comp(*i, *(--j))) {
        // do nothing here
      }

      int p = parity + 1 /* for the single iter_swap */
              + std::distance(ii, last) / 2;
      parity = p % 2;
      std::iter_swap(i, j);
      std::reverse(ii, last);
      return true;
    }
    if (i == first) {
      std::reverse(first, last);
      int p = parity + std::distance(first, last) / 2;
      parity = p % 2;
      return false;
    }
  }
}

using EvalSequence = container::svector<int>;

template <typename Rng>
auto inits(Rng const& rng) {
  using ranges::views::slice;
  using std::views::transform;
  return rng | transform([n = 0, &rng](auto&&) mutable {
           return slice(rng, 0, ++n);
         });
}

namespace bits {

template <std::unsigned_integral T>
constexpr auto bipartitions_ordered(T mask) {
  // number of possible bipartitions
  size_t const nparts = (size_t{1} << std::popcount(mask));
  return std::views::iota(size_t{0}, nparts) |
         std::views::transform([mask, p = mask](auto) mutable {
           auto p_ = p;
           p = (p - 1) & mask;
           return std::pair<T, T>{p_ ^ mask, p_};
         });
}

constexpr auto bipartitions_unordered(std::unsigned_integral auto mask) {
  auto bps = bipartitions_ordered(mask);
  const std::integral auto nparts = std::ranges::size(bps) / 2;
  return bps | std::views::take(nparts);
}

constexpr auto bipartitions(std::unsigned_integral auto mask) {
  return bipartitions_unordered(mask);
}

constexpr auto subsets_ascending(std::unsigned_integral auto mask) {
  return bipartitions_ordered(mask) | std::views::elements<0>;
}

constexpr auto subsets_descending(std::unsigned_integral auto mask) {
  return bipartitions_ordered(mask) | std::views::elements<1>;
}

constexpr auto subsets(std::unsigned_integral auto mask) {
  return subsets_ascending(mask);
}

constexpr auto on_bits_index(std::unsigned_integral auto mask) {
  size_t const nbits = std::popcount(mask);
  return std::views::iota(size_t{0}, nbits) |
         std::views::transform([m = mask](auto) mutable {
           size_t i = std::countr_zero(m);
           m &= (m - 1);
           return i;
         });
}

constexpr auto sieve(std::ranges::viewable_range auto&& rng) {
  auto elems = std::views::all(std::forward<decltype(rng)>(rng));
  return std::views::transform([elems](auto i) {
    return *std::ranges::next(std::ranges::begin(elems), i);
  });
}

}  // namespace bits

}  // namespace sequant

#endif  // SEQUANT_ALGORITHM_HPP