##// END OF EJS Templates
Updates sort() method to be compatible with a single vector
Alexandre Leroux -
r643:5ccc65b48599
parent child
Show More
@@ -1,117 +1,139
1 1 #ifndef SCIQLOP_SORTUTILS_H
2 2 #define SCIQLOP_SORTUTILS_H
3 3
4 4 #include <algorithm>
5 5 #include <cmath>
6 6 #include <numeric>
7 7 #include <vector>
8 8
9 9 /**
10 10 * Utility class with methods for sorting data
11 11 */
12 12 struct SortUtils {
13 13 /**
14 14 * Generates a vector representing the index of insertion of each data of a container if this
15 15 * one had to be sorted according to a comparison function.
16 16 *
17 17 * For example:
18 18 * If the container is a vector {1; 4; 2; 5; 3} and the comparison function is std::less, the
19 19 * result would be : {0; 3; 1; 4; 2}
20 20 *
21 21 * @tparam Container the type of the container.
22 22 * @tparam Compare the type of the comparison function
23 23 * @param container the container from which to generate the result. The container must have a
24 24 * at() method that returns a value associated to an index
25 25 * @param compare the comparison function
26 26 */
27 27 template <typename Container, typename Compare>
28 28 static std::vector<int> sortPermutation(const Container &container, const Compare &compare)
29 29 {
30 30 auto permutation = std::vector<int>{};
31 31 permutation.resize(container.size());
32 32
33 33 std::iota(permutation.begin(), permutation.end(), 0);
34 34 std::sort(permutation.begin(), permutation.end(),
35 35 [&](int i, int j) { return compare(container.at(i), container.at(j)); });
36 36 return permutation;
37 37 }
38 38
39 39 /**
40 * Sorts a container according to indices passed in parameter
40 * Sorts a container according to indices passed in parameter. The number of data in the
41 * container must be a multiple of the number of indices used to sort the container.
42 *
43 * Example 1:
44 * container: {1, 2, 3, 4, 5, 6}
45 * sortPermutation: {1, 0}
46 *
47 * Values will be sorted three by three, and the result will be:
48 * {4, 5, 6, 1, 2, 3}
49 *
50 * Example 2:
51 * container: {1, 2, 3, 4, 5, 6}
52 * sortPermutation: {2, 0, 1}
53 *
54 * Values will be sorted two by two, and the result will be:
55 * {5, 6, 1, 2, 3, 4}
56 *
41 57 * @param container the container sorted
42 58 * @param sortPermutation the indices used to sort the container
43 59 * @return the container sorted
44 60 * @warning no verification is made on validity of sortPermutation (i.e. the vector has unique
45 61 * indices and its range is [0 ; vector.size()[ )
46 62 */
47 63 template <typename Container>
48 static Container sort(const Container &container, const std::vector<int> &sortPermutation)
64 static Container sort(const Container &container, int nbValues,
65 const std::vector<int> &sortPermutation)
49 66 {
50 if (container.size() != sortPermutation.size()) {
67 auto containerSize = container.size();
68 if (containerSize % nbValues != 0
69 || ((containerSize / nbValues) != sortPermutation.size())) {
51 70 return Container{};
52 71 }
53 72
54 73 // Inits result
55 74 auto sortedData = Container{};
56 sortedData.resize(container.size());
75 sortedData.reserve(containerSize);
57 76
58 std::transform(sortPermutation.cbegin(), sortPermutation.cend(), sortedData.begin(),
59 [&container](int i) { return container.at(i); });
77 for (auto i = 0, componentIndex = 0, permutationIndex = 0; i < containerSize;
78 ++i, componentIndex = i % nbValues, permutationIndex = i / nbValues) {
79 auto insertIndex = sortPermutation.at(permutationIndex) * nbValues + componentIndex;
80 sortedData.append(container.at(insertIndex));
81 }
60 82
61 83 return sortedData;
62 84 }
63 85
64 86 /**
65 87 * Compares two values that can be NaN. This method is intended to be used as a compare function
66 88 * for searching min value by excluding NaN values.
67 89 *
68 90 * Examples of use:
69 91 * - f({1, 3, 2, 4, 5}) will return 1
70 92 * - f({NaN, 3, 2, 4, 5}) will return 2 (NaN is excluded)
71 93 * - f({NaN, NaN, 3, NaN, NaN}) will return 3 (NaN are excluded)
72 94 * - f({NaN, NaN, NaN, NaN, NaN}) will return NaN (no existing value)
73 95 *
74 96 * @param v1 first value
75 97 * @param v2 second value
76 98 * @return true if v1 < v2, false otherwise
77 99 * @sa std::min_element
78 100 */
79 101 template <typename T>
80 102 static bool minCompareWithNaN(const T &v1, const T &v2)
81 103 {
82 104 // Table used with NaN values:
83 105 // NaN < v2 -> false
84 106 // v1 < NaN -> true
85 107 // NaN < NaN -> false
86 108 // v1 < v2 -> v1 < v2
87 109 return std::isnan(v1) ? false : std::isnan(v2) || (v1 < v2);
88 110 }
89 111
90 112 /**
91 113 * Compares two values that can be NaN. This method is intended to be used as a compare function
92 114 * for searching max value by excluding NaN values.
93 115 *
94 116 * Examples of use:
95 117 * - f({1, 3, 2, 4, 5}) will return 5
96 118 * - f({1, 3, 2, 4, NaN}) will return 4 (NaN is excluded)
97 119 * - f({NaN, NaN, 3, NaN, NaN}) will return 3 (NaN are excluded)
98 120 * - f({NaN, NaN, NaN, NaN, NaN}) will return NaN (no existing value)
99 121 *
100 122 * @param v1 first value
101 123 * @param v2 second value
102 124 * @return true if v1 < v2, false otherwise
103 125 * @sa std::max_element
104 126 */
105 127 template <typename T>
106 128 static bool maxCompareWithNaN(const T &v1, const T &v2)
107 129 {
108 130 // Table used with NaN values:
109 131 // NaN < v2 -> true
110 132 // v1 < NaN -> false
111 133 // NaN < NaN -> false
112 134 // v1 < v2 -> v1 < v2
113 135 return std::isnan(v1) ? true : !std::isnan(v2) && (v1 < v2);
114 136 }
115 137 };
116 138
117 139 #endif // SCIQLOP_SORTUTILS_H
@@ -1,301 +1,296
1 1 #ifndef SCIQLOP_ARRAYDATA_H
2 2 #define SCIQLOP_ARRAYDATA_H
3 3
4 4 #include "Data/ArrayDataIterator.h"
5 5 #include <Common/SortUtils.h>
6 6
7 7 #include <QReadLocker>
8 8 #include <QReadWriteLock>
9 9 #include <QVector>
10 10
11 11 #include <memory>
12 12
13 13 template <int Dim>
14 14 class ArrayData;
15 15
16 16 using DataContainer = QVector<double>;
17 17
18 18 namespace arraydata_detail {
19 19
20 20 /// Struct used to sort ArrayData
21 21 template <int Dim>
22 22 struct Sort {
23 static std::shared_ptr<ArrayData<Dim> > sort(const DataContainer &data,
23 static std::shared_ptr<ArrayData<Dim> > sort(const DataContainer &data, int nbComponents,
24 24 const std::vector<int> &sortPermutation)
25 25 {
26 auto nbComponents = data.size();
27 auto sortedData = DataContainer(nbComponents);
28
29 for (auto i = 0; i < nbComponents; ++i) {
30 sortedData[i] = SortUtils::sort(data.at(i), sortPermutation);
31 }
32
33 return std::make_shared<ArrayData<Dim> >(std::move(sortedData));
26 return std::make_shared<ArrayData<Dim> >(
27 SortUtils::sort(data, nbComponents, sortPermutation), nbComponents);
34 28 }
35 29 };
36 30
37 31 /// Specialization for uni-dimensional ArrayData
38 32 template <>
39 33 struct Sort<1> {
40 static std::shared_ptr<ArrayData<1> > sort(const DataContainer &data,
34 static std::shared_ptr<ArrayData<1> > sort(const DataContainer &data, int nbComponents,
41 35 const std::vector<int> &sortPermutation)
42 36 {
43 return std::make_shared<ArrayData<1> >(SortUtils::sort(data.at(0), sortPermutation));
37 Q_UNUSED(nbComponents)
38 return std::make_shared<ArrayData<1> >(SortUtils::sort(data, 1, sortPermutation));
44 39 }
45 40 };
46 41
47 42 template <int Dim>
48 43 class IteratorValue : public ArrayDataIteratorValue::Impl {
49 44 public:
50 45 explicit IteratorValue(const DataContainer &container, bool begin) : m_Its{}
51 46 {
52 47 for (auto i = 0; i < container.size(); ++i) {
53 48 m_Its.push_back(begin ? container.at(i).cbegin() : container.at(i).cend());
54 49 }
55 50 }
56 51
57 52 IteratorValue(const IteratorValue &other) = default;
58 53
59 54 std::unique_ptr<ArrayDataIteratorValue::Impl> clone() const override
60 55 {
61 56 return std::make_unique<IteratorValue<Dim> >(*this);
62 57 }
63 58
64 59 bool equals(const ArrayDataIteratorValue::Impl &other) const override try {
65 60 const auto &otherImpl = dynamic_cast<const IteratorValue &>(other);
66 61 return m_Its == otherImpl.m_Its;
67 62 }
68 63 catch (const std::bad_cast &) {
69 64 return false;
70 65 }
71 66
72 67 void next() override
73 68 {
74 69 for (auto &it : m_Its) {
75 70 ++it;
76 71 }
77 72 }
78 73
79 74 void prev() override
80 75 {
81 76 for (auto &it : m_Its) {
82 77 --it;
83 78 }
84 79 }
85 80
86 81 double at(int componentIndex) const override { return *m_Its.at(componentIndex); }
87 82 double first() const override { return *m_Its.front(); }
88 83 double min() const override
89 84 {
90 85 auto end = m_Its.cend();
91 86 auto it = std::min_element(m_Its.cbegin(), end, [](const auto &it1, const auto &it2) {
92 87 return SortUtils::minCompareWithNaN(*it1, *it2);
93 88 });
94 89 return it != end ? **it : std::numeric_limits<double>::quiet_NaN();
95 90 }
96 91 double max() const override
97 92 {
98 93 auto end = m_Its.cend();
99 94 auto it = std::max_element(m_Its.cbegin(), end, [](const auto &it1, const auto &it2) {
100 95 return SortUtils::maxCompareWithNaN(*it1, *it2);
101 96 });
102 97 return it != end ? **it : std::numeric_limits<double>::quiet_NaN();
103 98 }
104 99
105 100 private:
106 101 std::vector<DataContainer::value_type::const_iterator> m_Its;
107 102 };
108 103
109 104 } // namespace arraydata_detail
110 105
111 106 /**
112 107 * @brief The ArrayData class represents a dataset for a data series.
113 108 *
114 109 * A dataset can be unidimensional or two-dimensional. This property is determined by the Dim
115 110 * template-parameter. In a case of a two-dimensional dataset, each dataset component has the same
116 111 * number of values
117 112 *
118 113 * @tparam Dim the dimension of the ArrayData (one or two)
119 114 * @sa IDataSeries
120 115 */
121 116 template <int Dim>
122 117 class ArrayData {
123 118 public:
124 119 // ///// //
125 120 // Ctors //
126 121 // ///// //
127 122
128 123 /**
129 124 * Ctor for a unidimensional ArrayData
130 125 * @param data the data the ArrayData will hold
131 126 */
132 127 template <int D = Dim, typename = std::enable_if_t<D == 1> >
133 128 explicit ArrayData(DataContainer data) : m_Data{std::move(data)}, m_NbComponents{1}
134 129 {
135 130 }
136 131
137 132 /**
138 133 * Ctor for a two-dimensional ArrayData. The number of components (number of lines) must be
139 134 * greater than 2 and must be a divisor of the total number of data in the vector
140 135 * @param data the data the ArrayData will hold
141 136 * @param nbComponents the number of components
142 137 * @throws std::invalid_argument if the number of components is less than 2 or is not a divisor
143 138 * of the size of the data
144 139 */
145 140 template <int D = Dim, typename = std::enable_if_t<D == 2> >
146 141 explicit ArrayData(DataContainer data, int nbComponents)
147 142 : m_Data{std::move(data)}, m_NbComponents{nbComponents}
148 143 {
149 144 if (nbComponents < 2) {
150 145 throw std::invalid_argument{
151 146 QString{"A multidimensional ArrayData must have at least 2 components (found: %1)"}
152 147 .arg(nbComponents)
153 148 .toStdString()};
154 149 }
155 150
156 151 if (m_Data.size() % m_NbComponents != 0) {
157 152 throw std::invalid_argument{QString{
158 153 "The number of components (%1) is inconsistent with the total number of data (%2)"}
159 154 .arg(m_Data.size(), nbComponents)
160 155 .toStdString()};
161 156 }
162 157 }
163 158
164 159 /// Copy ctor
165 160 explicit ArrayData(const ArrayData &other)
166 161 {
167 162 QReadLocker otherLocker{&other.m_Lock};
168 163 m_Data = other.m_Data;
169 164 m_NbComponents = other.m_NbComponents;
170 165 }
171 166
172 167 // /////////////// //
173 168 // General methods //
174 169 // /////////////// //
175 170
176 171 /**
177 172 * Merges into the array data an other array data. The two array datas must have the same number
178 173 * of components so the merge can be done
179 174 * @param other the array data to merge with
180 175 * @param prepend if true, the other array data is inserted at the beginning, otherwise it is
181 176 * inserted at the end
182 177 */
183 178 void add(const ArrayData<Dim> &other, bool prepend = false)
184 179 {
185 180 QWriteLocker locker{&m_Lock};
186 181 QReadLocker otherLocker{&other.m_Lock};
187 182
188 183 if (m_NbComponents != other.componentCount()) {
189 184 return;
190 185 }
191 186
192 187 if (prepend) {
193 188 auto otherDataSize = other.m_Data.size();
194 189 m_Data.insert(m_Data.begin(), otherDataSize, 0.);
195 190 for (auto i = 0; i < otherDataSize; ++i) {
196 191 m_Data.replace(i, other.m_Data.at(i));
197 192 }
198 193 }
199 194 else {
200 195 m_Data.append(other.m_Data);
201 196 }
202 197 }
203 198
204 199 void clear()
205 200 {
206 201 QWriteLocker locker{&m_Lock};
207 202 m_Data.clear();
208 203 }
209 204
210 205 int componentCount() const noexcept { return m_NbComponents; }
211 206
212 207 /// @return the size (i.e. number of values) of a single component
213 208 /// @remarks in a case of a two-dimensional ArrayData, each component has the same size
214 209 int size() const
215 210 {
216 211 QReadLocker locker{&m_Lock};
217 212 return m_Data.size() / m_NbComponents;
218 213 }
219 214
220 215 std::shared_ptr<ArrayData<Dim> > sort(const std::vector<int> &sortPermutation)
221 216 {
222 217 QReadLocker locker{&m_Lock};
223 218 return arraydata_detail::Sort<Dim>::sort(m_Data, m_NbComponents, sortPermutation);
224 219 }
225 220
226 221 // ///////// //
227 222 // Iterators //
228 223 // ///////// //
229 224
230 225 ArrayDataIterator cbegin() const
231 226 {
232 227 return ArrayDataIterator{ArrayDataIteratorValue{
233 228 std::make_unique<arraydata_detail::IteratorValue<Dim> >(m_Data, true)}};
234 229 }
235 230 ArrayDataIterator cend() const
236 231 {
237 232 return ArrayDataIterator{ArrayDataIteratorValue{
238 233 std::make_unique<arraydata_detail::IteratorValue<Dim> >(m_Data, false)}};
239 234 }
240 235
241 236 // ///////////// //
242 237 // 1-dim methods //
243 238 // ///////////// //
244 239
245 240 /**
246 241 * @return the data at a specified index
247 242 * @remarks index must be a valid position
248 243 * @remarks this method is only available for a unidimensional ArrayData
249 244 */
250 245 template <int D = Dim, typename = std::enable_if_t<D == 1> >
251 246 double at(int index) const noexcept
252 247 {
253 248 QReadLocker locker{&m_Lock};
254 249 return m_Data.at(index);
255 250 }
256 251
257 252 /**
258 253 * @return the data as a vector, as a const reference
259 254 * @remarks this method is only available for a unidimensional ArrayData
260 255 */
261 256 template <int D = Dim, typename = std::enable_if_t<D == 1> >
262 257 const QVector<double> &cdata() const noexcept
263 258 {
264 259 QReadLocker locker{&m_Lock};
265 260 return m_Data.at(0);
266 261 }
267 262
268 263 /**
269 264 * @return the data as a vector
270 265 * @remarks this method is only available for a unidimensional ArrayData
271 266 */
272 267 template <int D = Dim, typename = std::enable_if_t<D == 1> >
273 268 QVector<double> data() const noexcept
274 269 {
275 270 QReadLocker locker{&m_Lock};
276 271 return m_Data[0];
277 272 }
278 273
279 274 // ///////////// //
280 275 // 2-dim methods //
281 276 // ///////////// //
282 277
283 278 /**
284 279 * @return the data
285 280 * @remarks this method is only available for a two-dimensional ArrayData
286 281 */
287 282 template <int D = Dim, typename = std::enable_if_t<D == 2> >
288 283 DataContainer data() const noexcept
289 284 {
290 285 QReadLocker locker{&m_Lock};
291 286 return m_Data;
292 287 }
293 288
294 289 private:
295 290 DataContainer m_Data;
296 291 /// Number of components (lines). Is always 1 in a 1-dim ArrayData
297 292 int m_NbComponents;
298 293 mutable QReadWriteLock m_Lock;
299 294 };
300 295
301 296 #endif // SCIQLOP_ARRAYDATA_H
General Comments 0
You need to be logged in to leave comments. Login now