ordering.hh 1.66 KB
Newer Older
1
#include <algorithm>
2
#include <numeric>
3
#include <radixbug/bug.hh>
4
5
#include <utility>  // swap
#include <vector>
6
#include "radixcore/visibility.hh"
7

8
9
10
11
namespace radix
{
struct RADIX_PUBLIC super_sad_necessary_hack_for_dll_lib_creation
{
12
  void foo_method();
13
14
};

15
16
template <typename list_type, typename compare_type>
RADIX_PUBLIC std::vector<size_t> sort_permutation(const list_type &data,
17
18
                                                  compare_type &comparator)
{
19
20
21
22
  // 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);
23

24
25
26
27
28
29
30
31
  // 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
32
33

template <typename list_type>
34
RADIX_PUBLIC void apply_permutation(list_type &data,
35
36
                                    const std::vector<size_t> &order)
{
37
  std::vector<bool> done(data.size(), false);
38
39
  for (size_t i = 0; i < data.size(); ++i)
  {
40
41
42
43
44
45
46
    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];
    //
47
48
    while (i != j)
    {
49
50
51
52
53
      radix_line(i << ". swapping " << prev_j << " for " << j);
      std::swap(data[prev_j], data[j]);
      done[j] = true;
      prev_j  = j;
      j       = order[j];
54
    }
55
56
57
  }
}  // apply_permutation
}  // namespace radix