SortUtils.h
117 lines
| 4.1 KiB
| text/x-c
|
CLexer
Alexandre Leroux
|
r416 | #ifndef SCIQLOP_SORTUTILS_H | ||
| #define SCIQLOP_SORTUTILS_H | ||||
| #include <algorithm> | ||||
|
Alexandre Leroux
|
r577 | #include <cmath> | ||
|
Alexandre Leroux
|
r423 | #include <numeric> | ||
|
Alexandre Leroux
|
r416 | #include <vector> | ||
| /** | ||||
| * Utility class with methods for sorting data | ||||
| */ | ||||
| struct SortUtils { | ||||
| /** | ||||
| * Generates a vector representing the index of insertion of each data of a container if this | ||||
| * one had to be sorted according to a comparison function. | ||||
| * | ||||
| * For example: | ||||
| * If the container is a vector {1; 4; 2; 5; 3} and the comparison function is std::less, the | ||||
| * result would be : {0; 3; 1; 4; 2} | ||||
| * | ||||
| * @tparam Container the type of the container. | ||||
| * @tparam Compare the type of the comparison function | ||||
| * @param container the container from which to generate the result. The container must have a | ||||
| * at() method that returns a value associated to an index | ||||
| * @param compare the comparison function | ||||
| */ | ||||
| template <typename Container, typename Compare> | ||||
| static std::vector<int> sortPermutation(const Container &container, const Compare &compare) | ||||
| { | ||||
| auto permutation = std::vector<int>{}; | ||||
| permutation.resize(container.size()); | ||||
| std::iota(permutation.begin(), permutation.end(), 0); | ||||
| std::sort(permutation.begin(), permutation.end(), | ||||
| [&](int i, int j) { return compare(container.at(i), container.at(j)); }); | ||||
| return permutation; | ||||
| } | ||||
|
Alexandre Leroux
|
r464 | |||
| /** | ||||
| * Sorts a container according to indices passed in parameter | ||||
| * @param container the container sorted | ||||
| * @param sortPermutation the indices used to sort the container | ||||
| * @return the container sorted | ||||
| * @warning no verification is made on validity of sortPermutation (i.e. the vector has unique | ||||
| * indices and its range is [0 ; vector.size()[ ) | ||||
| */ | ||||
| template <typename Container> | ||||
| static Container sort(const Container &container, const std::vector<int> &sortPermutation) | ||||
| { | ||||
| if (container.size() != sortPermutation.size()) { | ||||
| return Container{}; | ||||
| } | ||||
| // Inits result | ||||
| auto sortedData = Container{}; | ||||
| sortedData.resize(container.size()); | ||||
| std::transform(sortPermutation.cbegin(), sortPermutation.cend(), sortedData.begin(), | ||||
| [&container](int i) { return container.at(i); }); | ||||
| return sortedData; | ||||
| } | ||||
|
Alexandre Leroux
|
r567 | |||
| /** | ||||
| * Compares two values that can be NaN. This method is intended to be used as a compare function | ||||
| * for searching min value by excluding NaN values. | ||||
| * | ||||
| * Examples of use: | ||||
| * - f({1, 3, 2, 4, 5}) will return 1 | ||||
| * - f({NaN, 3, 2, 4, 5}) will return 2 (NaN is excluded) | ||||
| * - f({NaN, NaN, 3, NaN, NaN}) will return 3 (NaN are excluded) | ||||
| * - f({NaN, NaN, NaN, NaN, NaN}) will return NaN (no existing value) | ||||
| * | ||||
| * @param v1 first value | ||||
| * @param v2 second value | ||||
| * @return true if v1 < v2, false otherwise | ||||
| * @sa std::min_element | ||||
| */ | ||||
| template <typename T> | ||||
| static bool minCompareWithNaN(const T &v1, const T &v2) | ||||
| { | ||||
| // Table used with NaN values: | ||||
| // NaN < v2 -> false | ||||
| // v1 < NaN -> true | ||||
| // NaN < NaN -> false | ||||
| // v1 < v2 -> v1 < v2 | ||||
| return std::isnan(v1) ? false : std::isnan(v2) || (v1 < v2); | ||||
| } | ||||
| /** | ||||
| * Compares two values that can be NaN. This method is intended to be used as a compare function | ||||
| * for searching max value by excluding NaN values. | ||||
| * | ||||
| * Examples of use: | ||||
| * - f({1, 3, 2, 4, 5}) will return 5 | ||||
| * - f({1, 3, 2, 4, NaN}) will return 4 (NaN is excluded) | ||||
| * - f({NaN, NaN, 3, NaN, NaN}) will return 3 (NaN are excluded) | ||||
| * - f({NaN, NaN, NaN, NaN, NaN}) will return NaN (no existing value) | ||||
| * | ||||
| * @param v1 first value | ||||
| * @param v2 second value | ||||
| * @return true if v1 < v2, false otherwise | ||||
| * @sa std::max_element | ||||
| */ | ||||
| template <typename T> | ||||
| static bool maxCompareWithNaN(const T &v1, const T &v2) | ||||
| { | ||||
| // Table used with NaN values: | ||||
| // NaN < v2 -> true | ||||
| // v1 < NaN -> false | ||||
| // NaN < NaN -> false | ||||
| // v1 < v2 -> v1 < v2 | ||||
| return std::isnan(v1) ? true : !std::isnan(v2) && (v1 < v2); | ||||
| } | ||||
|
Alexandre Leroux
|
r416 | }; | ||
| #endif // SCIQLOP_SORTUTILS_H | ||||