##// END OF EJS Templates
Adds methods to handle search of min/max values in structures that can contain NaN values...
Alexandre Leroux -
r606:36d29ea2f20f
parent child
Show More
@@ -1,64 +1,116
1 #ifndef SCIQLOP_SORTUTILS_H
1 #ifndef SCIQLOP_SORTUTILS_H
2 #define SCIQLOP_SORTUTILS_H
2 #define SCIQLOP_SORTUTILS_H
3
3
4 #include <algorithm>
4 #include <algorithm>
5 #include <numeric>
5 #include <numeric>
6 #include <vector>
6 #include <vector>
7
7
8 /**
8 /**
9 * Utility class with methods for sorting data
9 * Utility class with methods for sorting data
10 */
10 */
11 struct SortUtils {
11 struct SortUtils {
12 /**
12 /**
13 * Generates a vector representing the index of insertion of each data of a container if this
13 * Generates a vector representing the index of insertion of each data of a container if this
14 * one had to be sorted according to a comparison function.
14 * one had to be sorted according to a comparison function.
15 *
15 *
16 * For example:
16 * For example:
17 * If the container is a vector {1; 4; 2; 5; 3} and the comparison function is std::less, the
17 * If the container is a vector {1; 4; 2; 5; 3} and the comparison function is std::less, the
18 * result would be : {0; 3; 1; 4; 2}
18 * result would be : {0; 3; 1; 4; 2}
19 *
19 *
20 * @tparam Container the type of the container.
20 * @tparam Container the type of the container.
21 * @tparam Compare the type of the comparison function
21 * @tparam Compare the type of the comparison function
22 * @param container the container from which to generate the result. The container must have a
22 * @param container the container from which to generate the result. The container must have a
23 * at() method that returns a value associated to an index
23 * at() method that returns a value associated to an index
24 * @param compare the comparison function
24 * @param compare the comparison function
25 */
25 */
26 template <typename Container, typename Compare>
26 template <typename Container, typename Compare>
27 static std::vector<int> sortPermutation(const Container &container, const Compare &compare)
27 static std::vector<int> sortPermutation(const Container &container, const Compare &compare)
28 {
28 {
29 auto permutation = std::vector<int>{};
29 auto permutation = std::vector<int>{};
30 permutation.resize(container.size());
30 permutation.resize(container.size());
31
31
32 std::iota(permutation.begin(), permutation.end(), 0);
32 std::iota(permutation.begin(), permutation.end(), 0);
33 std::sort(permutation.begin(), permutation.end(),
33 std::sort(permutation.begin(), permutation.end(),
34 [&](int i, int j) { return compare(container.at(i), container.at(j)); });
34 [&](int i, int j) { return compare(container.at(i), container.at(j)); });
35 return permutation;
35 return permutation;
36 }
36 }
37
37
38 /**
38 /**
39 * Sorts a container according to indices passed in parameter
39 * Sorts a container according to indices passed in parameter
40 * @param container the container sorted
40 * @param container the container sorted
41 * @param sortPermutation the indices used to sort the container
41 * @param sortPermutation the indices used to sort the container
42 * @return the container sorted
42 * @return the container sorted
43 * @warning no verification is made on validity of sortPermutation (i.e. the vector has unique
43 * @warning no verification is made on validity of sortPermutation (i.e. the vector has unique
44 * indices and its range is [0 ; vector.size()[ )
44 * indices and its range is [0 ; vector.size()[ )
45 */
45 */
46 template <typename Container>
46 template <typename Container>
47 static Container sort(const Container &container, const std::vector<int> &sortPermutation)
47 static Container sort(const Container &container, const std::vector<int> &sortPermutation)
48 {
48 {
49 if (container.size() != sortPermutation.size()) {
49 if (container.size() != sortPermutation.size()) {
50 return Container{};
50 return Container{};
51 }
51 }
52
52
53 // Inits result
53 // Inits result
54 auto sortedData = Container{};
54 auto sortedData = Container{};
55 sortedData.resize(container.size());
55 sortedData.resize(container.size());
56
56
57 std::transform(sortPermutation.cbegin(), sortPermutation.cend(), sortedData.begin(),
57 std::transform(sortPermutation.cbegin(), sortPermutation.cend(), sortedData.begin(),
58 [&container](int i) { return container.at(i); });
58 [&container](int i) { return container.at(i); });
59
59
60 return sortedData;
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 #endif // SCIQLOP_SORTUTILS_H
116 #endif // SCIQLOP_SORTUTILS_H
General Comments 0
You need to be logged in to leave comments. Login now