#include <algorithm>
#include <numeric>
#include <radixbug/bug.hh>
#include <utility>  // swap
#include <vector>
#include "radixcore/visibility.hh"

namespace radix
{
struct RADIX_PUBLIC super_sad_necessary_hack_for_dll_lib_creation
{
  void foo_method();
};

template <typename list_type, typename compare_type>
RADIX_PUBLIC std::vector<size_t> sort_permutation(const list_type &data,
                                                  compare_type &comparator)
{
  // create list of indices the size of the incoming data
  std::vector<std::size_t> order(data.size());
  // initialize list with initial index, starting at zero
  std::iota(order.begin(), order.end(), 0);

  // order ordering according to comparator
  std::sort(order.begin(), order.end(),
            [&](std::size_t data_i, std::size_t data_j) {
              radix_line("Comparing [" << data_i << ", " << data_j << "]");
              return comparator(data[data_i], data[data_j]);
            });
  return order;
}  // sort_permutation

template <typename list_type>
RADIX_PUBLIC void apply_permutation(list_type &data,
                                    const std::vector<size_t> &order)
{
  std::vector<bool> done(data.size(), false);
  for (size_t i = 0; i < data.size(); ++i)
  {
    if (done[i]) continue;
    done[i] = true;
    // previous ordering is that of the loop, so index i it is
    size_t prev_j = i;
    // get the new order lookup
    size_t j = order[i];
    //
    while (i != j)
    {
      radix_line(i << ". swapping " << prev_j << " for " << j);
      std::swap(data[prev_j], data[j]);
      done[j] = true;
      prev_j  = j;
      j       = order[j];
    }
  }
}  // apply_permutation
}  // namespace radix