| @@ -1,64 +1,116 | |||
|
|
1 | 1 | #ifndef SCIQLOP_SORTUTILS_H |
|
|
2 | 2 | #define SCIQLOP_SORTUTILS_H |
|
|
3 | 3 | |
|
|
4 | 4 | #include <algorithm> |
|
|
5 | 5 | #include <numeric> |
|
|
6 | 6 | #include <vector> |
|
|
7 | 7 | |
|
|
8 | 8 | /** |
|
|
9 | 9 | * Utility class with methods for sorting data |
|
|
10 | 10 | */ |
|
|
11 | 11 | struct SortUtils { |
|
|
12 | 12 | /** |
|
|
13 | 13 | * Generates a vector representing the index of insertion of each data of a container if this |
|
|
14 | 14 | * one had to be sorted according to a comparison function. |
|
|
15 | 15 | * |
|
|
16 | 16 | * For example: |
|
|
17 | 17 | * If the container is a vector {1; 4; 2; 5; 3} and the comparison function is std::less, the |
|
|
18 | 18 | * result would be : {0; 3; 1; 4; 2} |
|
|
19 | 19 | * |
|
|
20 | 20 | * @tparam Container the type of the container. |
|
|
21 | 21 | * @tparam Compare the type of the comparison function |
|
|
22 | 22 | * @param container the container from which to generate the result. The container must have a |
|
|
23 | 23 | * at() method that returns a value associated to an index |
|
|
24 | 24 | * @param compare the comparison function |
|
|
25 | 25 | */ |
|
|
26 | 26 | template <typename Container, typename Compare> |
|
|
27 | 27 | static std::vector<int> sortPermutation(const Container &container, const Compare &compare) |
|
|
28 | 28 | { |
|
|
29 | 29 | auto permutation = std::vector<int>{}; |
|
|
30 | 30 | permutation.resize(container.size()); |
|
|
31 | 31 | |
|
|
32 | 32 | std::iota(permutation.begin(), permutation.end(), 0); |
|
|
33 | 33 | std::sort(permutation.begin(), permutation.end(), |
|
|
34 | 34 | [&](int i, int j) { return compare(container.at(i), container.at(j)); }); |
|
|
35 | 35 | return permutation; |
|
|
36 | 36 | } |
|
|
37 | 37 | |
|
|
38 | 38 | /** |
|
|
39 | 39 | * Sorts a container according to indices passed in parameter |
|
|
40 | 40 | * @param container the container sorted |
|
|
41 | 41 | * @param sortPermutation the indices used to sort the container |
|
|
42 | 42 | * @return the container sorted |
|
|
43 | 43 | * @warning no verification is made on validity of sortPermutation (i.e. the vector has unique |
|
|
44 | 44 | * indices and its range is [0 ; vector.size()[ ) |
|
|
45 | 45 | */ |
|
|
46 | 46 | template <typename Container> |
|
|
47 | 47 | static Container sort(const Container &container, const std::vector<int> &sortPermutation) |
|
|
48 | 48 | { |
|
|
49 | 49 | if (container.size() != sortPermutation.size()) { |
|
|
50 | 50 | return Container{}; |
|
|
51 | 51 | } |
|
|
52 | 52 | |
|
|
53 | 53 | // Inits result |
|
|
54 | 54 | auto sortedData = Container{}; |
|
|
55 | 55 | sortedData.resize(container.size()); |
|
|
56 | 56 | |
|
|
57 | 57 | std::transform(sortPermutation.cbegin(), sortPermutation.cend(), sortedData.begin(), |
|
|
58 | 58 | [&container](int i) { return container.at(i); }); |
|
|
59 | 59 | |
|
|
60 | 60 | return sortedData; |
|
|
61 | 61 | } |
|
|
62 | ||
|
|
63 | /** | |
|
|
64 | * Compares two values that can be NaN. This method is intended to be used as a compare function | |
|
|
65 | * for searching min value by excluding NaN values. | |
|
|
66 | * | |
|
|
67 | * Examples of use: | |
|
|
68 | * - f({1, 3, 2, 4, 5}) will return 1 | |
|
|
69 | * - f({NaN, 3, 2, 4, 5}) will return 2 (NaN is excluded) | |
|
|
70 | * - f({NaN, NaN, 3, NaN, NaN}) will return 3 (NaN are excluded) | |
|
|
71 | * - f({NaN, NaN, NaN, NaN, NaN}) will return NaN (no existing value) | |
|
|
72 | * | |
|
|
73 | * @param v1 first value | |
|
|
74 | * @param v2 second value | |
|
|
75 | * @return true if v1 < v2, false otherwise | |
|
|
76 | * @sa std::min_element | |
|
|
77 | */ | |
|
|
78 | template <typename T> | |
|
|
79 | static bool minCompareWithNaN(const T &v1, const T &v2) | |
|
|
80 | { | |
|
|
81 | // Table used with NaN values: | |
|
|
82 | // NaN < v2 -> false | |
|
|
83 | // v1 < NaN -> true | |
|
|
84 | // NaN < NaN -> false | |
|
|
85 | // v1 < v2 -> v1 < v2 | |
|
|
86 | return std::isnan(v1) ? false : std::isnan(v2) || (v1 < v2); | |
|
|
87 | } | |
|
|
88 | ||
|
|
89 | /** | |
|
|
90 | * Compares two values that can be NaN. This method is intended to be used as a compare function | |
|
|
91 | * for searching max value by excluding NaN values. | |
|
|
92 | * | |
|
|
93 | * Examples of use: | |
|
|
94 | * - f({1, 3, 2, 4, 5}) will return 5 | |
|
|
95 | * - f({1, 3, 2, 4, NaN}) will return 4 (NaN is excluded) | |
|
|
96 | * - f({NaN, NaN, 3, NaN, NaN}) will return 3 (NaN are excluded) | |
|
|
97 | * - f({NaN, NaN, NaN, NaN, NaN}) will return NaN (no existing value) | |
|
|
98 | * | |
|
|
99 | * @param v1 first value | |
|
|
100 | * @param v2 second value | |
|
|
101 | * @return true if v1 < v2, false otherwise | |
|
|
102 | * @sa std::max_element | |
|
|
103 | */ | |
|
|
104 | template <typename T> | |
|
|
105 | static bool maxCompareWithNaN(const T &v1, const T &v2) | |
|
|
106 | { | |
|
|
107 | // Table used with NaN values: | |
|
|
108 | // NaN < v2 -> true | |
|
|
109 | // v1 < NaN -> false | |
|
|
110 | // NaN < NaN -> false | |
|
|
111 | // v1 < v2 -> v1 < v2 | |
|
|
112 | return std::isnan(v1) ? true : !std::isnan(v2) && (v1 < v2); | |
|
|
113 | } | |
|
|
62 | 114 | }; |
|
|
63 | 115 | |
|
|
64 | 116 | #endif // SCIQLOP_SORTUTILS_H |
General Comments 0
You need to be logged in to leave comments.
Login now