SortBy.hpp

Go to the documentation of this file.

#ifndef WEIGHTEDLOWESS_SORTBY_HPP
#define WEIGHTEDLOWESS_SORTBY_HPP
 
#include <algorithm>
#include <numeric>
#include <vector>
#include <cstdint>
#include <type_traits>
#include <initializer_list>
#include <cstddef>
 
#include "sanisizer/sanisizer.hpp"
 
#include "utils.hpp"
 
namespace WeightedLowess {
 
class SortBy {
private:
    std::vector<std::size_t> my_permutation;
    bool my_sorted = true;
 
public:
    template<typename Sortable_>
    SortBy(const std::size_t num_points, const Sortable_* x) {
        set(num_points, x);
    }
 
    SortBy() = default;
 
    template<typename Sortable_>
    void set(const std::size_t num_points, const Sortable_* x) {
        if (num_points) {
            my_sorted = std::is_sorted(x, x + num_points);
            if (!my_sorted) {
                sanisizer::resize(my_permutation, num_points);
                std::iota(my_permutation.begin(), my_permutation.end(), static_cast<std::size_t>(0));
                std::sort(my_permutation.begin(), my_permutation.end(), [&](std::size_t left, std::size_t right) -> bool { return x[left] < x[right]; });
            }
        }
    }
 
private:
    template<typename AllData_, typename Used_>
    void permute_raw(AllData_& data, Used_* work) const {
        if (my_sorted) {
            return;
        }
 
        const auto num_points = my_permutation.size();
        std::fill_n(work, num_points, 0);
 
        // Reordering values in place.
        for (decltype(internal::I(num_points)) i = 0; i < num_points; ++i) {
            if (work[i]) {
                continue;
            }
            work[i] = 1;
 
            std::size_t current = i, replacement = my_permutation[i];
            while (replacement != i) {
                if constexpr(std::is_pointer<AllData_>::value) {
                    std::swap(data[current], data[replacement]);
                } else {
                    for (auto d : data) {
                        std::swap(d[current], d[replacement]);
                    }
                }
                current = replacement;
                work[replacement] = 1;
                replacement = my_permutation[replacement]; 
            } 
        }
    }
 
public:
    template<typename Data_, typename Used_>
    void permute(Data_* data, Used_* work) const {
        permute_raw(data, work);
    }
 
    template<typename Data_, typename Used_>
    void permute(std::initializer_list<Data_> data, Used_* work) const {
        permute_raw(data, work);
    }
 
    template<typename DataPointers_, typename Used_>
    void permute(DataPointers_ data, Used_* work) const {
        permute_raw(data, work);
    }
 
    template<typename Data_, typename Used_>
    void permute(Data_* data, std::vector<Used_>& work) const {
        const auto num_points = my_permutation.size();
        sanisizer::resize(work, num_points);
        permute(data, work.data());
    }
 
    template<typename Data_, typename Used_>
    void permute(std::initializer_list<Data_> data, std::vector<Used_>& work) const {
        const auto num_points = my_permutation.size();
        sanisizer::resize(work, num_points);
        permute(data, work.data());
    }
 
    template<typename DataPointers_, typename Used_>
    void permute(DataPointers_ data, std::vector<Used_>& work) const {
        const auto num_points = my_permutation.size();
        sanisizer::resize(work, num_points);
        permute(data, work.data());
    }
 
private:
    template<typename AllData_, typename Used_>
    void unpermute_raw(AllData_& data, Used_* work) const {
        if (my_sorted) {
            return;
        }
 
        const auto num_points = my_permutation.size();
        std::fill_n(work, num_points, 0);
 
        for (decltype(internal::I(num_points)) i = 0; i < num_points; ++i) {
            if (work[i]) {
                continue;
            }
            work[i] = 1;
 
            auto replacement = my_permutation[i];
            while (replacement != i) {
                if constexpr(std::is_pointer<AllData_>::value) {
                    std::swap(data[i], data[replacement]);
                } else {
                    for (auto d : data) {
                        std::swap(d[i], d[replacement]);
                    }
                }
                work[replacement] = 1;
                replacement = my_permutation[replacement]; 
            } 
        }
    }
 
public:
    template<typename Data_, typename Used_>
    void unpermute(Data_* data, Used_* work) const {
        unpermute_raw(data, work);
    }
 
    template<typename Data_, typename Used_>
    void unpermute(std::initializer_list<Data_*> data, Used_* work) const {
        unpermute_raw(data, work);
    }
 
    template<typename DataPointers_, typename Used_>
    void unpermute(DataPointers_ data, Used_* work) const {
        unpermute_raw(data, work);
    }
 
    template<typename Data_, typename Used_>
    void unpermute(Data_* data, std::vector<Used_>& work) const {
        const auto num_points = my_permutation.size();
        sanisizer::resize(work, num_points);
        unpermute(data, work.data());
    }
 
    template<typename Data_, typename Used_>
    void unpermute(std::initializer_list<Data_*> data, std::vector<Used_>& work) const {
        const auto num_points = my_permutation.size();
        sanisizer::resize(work, num_points);
        unpermute(data, work.data());
    }
 
    template<typename DataPointers_, typename Used_>
    void unpermute(DataPointers_ data, std::vector<Used_>& work) const {
        const auto num_points = my_permutation.size();
        sanisizer::resize(work, num_points);
        unpermute(data, work.data());
    }
};
 
}
 
#endif