Ocean
Loading...
Searching...
No Matches
Subset.h
Go to the documentation of this file.
1/*
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8#ifndef META_OCEAN_BASE_SUBSET_H
9#define META_OCEAN_BASE_SUBSET_H
10
11#include "ocean/base/Base.h"
12
13namespace Ocean
14{
15
16/**
17 * This class implements subset functions.
18 * @ingroup base
19 */
20class Subset
21{
22 private:
23
24 /**
25 * This helper class implements a subset functions.
26 * @tparam TIndex Data type of the index elements
27 */
28 template <typename TIndex>
30 {
31 public:
32
33 /**
34 * Extracts a subset of a given set of objects by usage of an index vector holding the indices of all objects to be used.
35 * If the index data type is an uint8_t, than the (boolean != 0u) statement is used to use the corresponding object or not.<br>
36 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
37 * @param objects Entire set of objects from that a subset will be extracted
38 * @param indices Indices defining the subset to be extracted
39 * @return Resulting subset of the given objects
40 * @tparam T Data type of the objects
41 */
42 template <typename T>
43 static inline std::vector<T> subset(const std::vector<T>& objects, const std::vector<TIndex>& indices);
44
45 /**
46 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be used.
47 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
48 * @param objects Entire set of objects from that a subset will be extracted
49 * @param indices Indices defining the subset to be extracted
50 * @return Resulting subset of the given objects
51 * @tparam T Data type of the objects
52 */
53 template <typename T>
54 static inline std::vector<T> subset(const std::vector<T>& objects, const std::set<TIndex>& indices);
55
56 /**
57 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not used.
58 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
59 * @param objects Entire set of objects from that a subset will be extracted
60 * @param indices Indices defining the inverted subset to be extracted
61 * @return Resulting subset of the given objects
62 * @tparam T Data type of the objects
63 */
64 template <typename T>
65 static inline std::vector<T> invertedSubset(const std::vector<T>& objects, const std::unordered_set<TIndex>& indices);
66
67 /**
68 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not used.
69 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
70 * @param objects Entire set of objects from that a subset will be extracted
71 * @param indices Indices defining the inverted subset to be extracted
72 * @return Resulting subset of the given objects
73 * @tparam T Data type of the objects
74 */
75 template <typename T>
76 static inline std::vector<T> invertedSubset(const std::vector<T>& objects, const std::set<TIndex>& indices);
77
78 /**
79 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be used.
80 * If the index data type is an uint8_t, than the (boolean != 0u) statement is used to use the corresponding object or not.<br>
81 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
82 * @param objects Entire set of objects from that a subset will be extracted
83 * @param numberObjects Number of given objects
84 * @param indices Indices defining the subset to be extracted
85 * @param numberIndices Number of given indices
86 * @return Resulting subset of the given objects
87 * @tparam T Data type of the objects
88 */
89 template <typename T>
90 static inline std::vector<T> subset(const T* objects, const size_t numberObjects, const TIndex* indices, const size_t numberIndices);
91
92 /**
93 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be used.
94 * If the index data type is an uint8_t, than the (boolean != 0u) statement is used to use the corresponding object or not.<br>
95 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
96 * @param objects Entire set of objects from that a subset will be extracted
97 * @param numberObjects Number of given objects
98 * @param indices Indices defining the subset to be extracted
99 * @return Resulting subset of the given objects
100 * @tparam T Data type of the objects
101 */
102 template <typename T>
103 static inline std::vector<T> subset(const T* objects, const size_t numberObjects, const std::vector<TIndex>& indices);
104
105 /**
106 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be used.
107 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
108 * @param objects Entire set of objects from that a subset will be extracted
109 * @param numberObjects Number of given objects
110 * @param indices Indices defining the subset to be extracted
111 * @return Resulting subset of the given objects
112 * @tparam T Data type of the objects
113 */
114 template <typename T>
115 static inline std::vector<T> subset(const T* objects, const size_t numberObjects, const std::set<TIndex>& indices);
116
117 /**
118 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not used.
119 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
120 * @param objects Entire set of objects from that a subset will be extracted
121 * @param numberObjects Number of given objects
122 * @param indices Indices defining the inverted subset to be extracted
123 * @return Resulting subset of the given objects
124 * @tparam T Data type of the objects
125 */
126 template <typename T>
127 static inline std::vector<T> invertedSubset(const T* objects, const size_t numberObjects, const std::unordered_set<TIndex>& indices);
128
129 /**
130 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not used.
131 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
132 * @param objects Entire set of objects from that a subset will be extracted
133 * @param numberObjects Number of given objects
134 * @param indices Indices defining the inverted subset to be extracted
135 * @return Resulting subset of the given objects
136 * @tparam T Data type of the objects
137 */
138 template <typename T>
139 static inline std::vector<T> invertedSubset(const T* objects, const size_t numberObjects, const std::set<TIndex>& indices);
140
141 /**
142 * Converts object indices to an uint8_t vector holding statements for each object.
143 * @param indices Indices defining the subset of the objects, with range [0, numberObjects)
144 * @param numberObjects Number of objects that can be addressed by the indices
145 * @return Resulting (boolean != 0u) statements
146 * @tparam TContainer The container to be used, e.g., std::vector, std::set, std::unordred_set
147 * @tparam tValue Value for objects that are defined in the indices, the inverse value is applied otherwise
148 */
149 template <typename TContainer, uint8_t tValue>
150 static inline std::vector<uint8_t> indices2statements(const TContainer& indices, const size_t numberObjects);
151
152 /**
153 * Converts object indices to an uint8_t vector holding statements for each object.
154 * @param indices Indices defining the subset of the objects, with range [0, numberObjects)
155 * @param numberIndices Number of provided indices
156 * @param numberObjects Number of objects that can be addressed by the indices
157 * @return Resulting boolean statements
158 * @tparam tValue Value for objects that are defined in the indices, the inverse value is applied otherwise
159 */
160 template <uint8_t tValue>
161 static inline std::vector<uint8_t> indices2statements(const TIndex* indices, const size_t numberIndices, const size_t numberObjects);
162
163 /**
164 * Converts an uint8_t vector holding statements for each object into object indices.
165 * @param statements Boolean statement for each object
166 * @return Resulting object indices
167 * @tparam tValue Value for objects that will be defined in the indices
168 */
169 template <uint8_t tValue>
170 static inline std::vector<TIndex> statements2indices(const std::vector<uint8_t>& statements);
171
172 /**
173 * Converts an uint8_t vector holding statements for each object into object indices.
174 * @param statements Boolean statement for each object
175 * @param numberStatements Number of statements
176 * @return Resulting object indices
177 * @tparam tValue Value for objects that will be defined in the indices
178 */
179 template <uint8_t tValue>
180 static inline std::vector<TIndex> statements2indices(const uint8_t* statements, const size_t numberStatements);
181 };
182
183 public:
184
185 /**
186 * Extracts a subset of a given set of objects by usage of an index vector holding the indices of all objects to be used.
187 * If the index data type is an uint8_t, than the (boolean != 0u) statement is used to use the corresponding object or not.<br>
188 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
189 * @param objects Entire set of objects from that a subset will be extracted
190 * @param indices Indices defining the subset to be extracted
191 * @return Resulting subset of the given objects
192 * @tparam TIndex Data type of the index elements
193 * @tparam T Data type of the objects
194 */
195 template <typename TIndex, typename T>
196 static inline std::vector<T> subset(const std::vector<T>& objects, const std::vector<TIndex>& indices);
197
198 /**
199 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be used.
200 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
201 * @param objects Entire set of objects from that a subset will be extracted
202 * @param indices Indices defining the subset to be extracted
203 * @return Resulting subset of the given objects
204 * @tparam TIndex Data type of the index elements
205 * @tparam T Data type of the objects
206 */
207 template <typename TIndex, typename T>
208 static inline std::vector<T> subset(const std::vector<T>& objects, const std::set<TIndex>& indices);
209
210 /**
211 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not used.
212 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
213 * @param objects Entire set of objects from that a subset will be extracted
214 * @param indices Indices defining the inverted subset to be extracted
215 * @return Resulting subset of the given objects
216 * @tparam TIndex Data type of the index elements
217 * @tparam T Data type of the objects
218 */
219 template <typename TIndex, typename T>
220 static inline std::vector<T> invertedSubset(const std::vector<T>& objects, const std::unordered_set<TIndex>& indices);
221
222 /**
223 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not used.
224 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
225 * @param objects Entire set of objects from that a subset will be extracted
226 * @param indices Indices defining the inverted subset to be extracted
227 * @return Resulting subset of the given objects
228 * @tparam TIndex Data type of the index elements
229 * @tparam T Data type of the objects
230 */
231 template <typename TIndex, typename T>
232 static inline std::vector<T> invertedSubset(const std::vector<T>& objects, const std::set<TIndex>& indices);
233
234 /**
235 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be used.
236 * If the index data type is an uint8_t, than the (boolean != 0u) statement is used to use the corresponding object or not.<br>
237 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
238 * @param objects Entire set of objects from that a subset will be extracted
239 * @param numberObjects Number of given objects
240 * @param indices Indices defining the subset to be extracted
241 * @param numberIndices Number of given indices
242 * @return Resulting subset of the given objects
243 * @tparam TIndex Data type of the index elements
244 * @tparam T Data type of the objects
245 */
246 template <typename TIndex, typename T>
247 static inline std::vector<T> subset(const T* objects, const size_t numberObjects, const TIndex* indices, const size_t numberIndices);
248
249 /**
250 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be used.
251 * If the index data type is an uint8_t, than the (boolean != 0u) statement is used to use the corresponding object or not.<br>
252 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
253 * @param objects Entire set of objects from that a subset will be extracted
254 * @param numberObjects Number of given objects
255 * @param indices Indices defining the subset to be extracted
256 * @return Resulting subset of the given objects
257 * @tparam TIndex Data type of the index elements
258 * @tparam T Data type of the objects
259 */
260 template <typename TIndex, typename T>
261 static inline std::vector<T> subset(const T* objects, const size_t numberObjects, const std::vector<TIndex>& indices);
262
263 /**
264 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be used.
265 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
266 * @param objects Entire set of objects from that a subset will be extracted
267 * @param numberObjects Number of given objects
268 * @param indices Indices defining the subset to be extracted
269 * @return Resulting subset of the given objects
270 * @tparam TIndex Data type of the index elements
271 * @tparam T Data type of the objects
272 */
273 template <typename TIndex, typename T>
274 static inline std::vector<T> subset(const T* objects, const size_t numberObjects, const std::set<TIndex>& indices);
275
276 /**
277 * Applies a subset to a vector of objects.
278 * @param objects The entire set of objects on which the subset will be applied
279 * @param begin Iterator to the first element of the subset
280 * @param end Iterator to the end of the subset
281 */
282 template <typename TIndexIterator, typename T>
283 static void applySubset(std::vector<T>& objects, const TIndexIterator& begin, const TIndexIterator& end);
284
285 /**
286 * Applies a subset to a vector of objects.
287 * @param objects The entire set of objects on which the subset will be applied
288 * @param indices The indices of the subset to be applied
289 */
290 template <typename TIndex, typename T>
291 static inline void applySubset(std::vector<T>& objects, const std::vector<TIndex>& indices);
292
293 /**
294 * Applies a subset to a vector of objects.
295 * @param objects The entire set of objects on which the subset will be applied
296 * @param indices The indices of the subset to be applied, can be nullptr if numberIndices is 0
297 * @param numberIndices The number of indices, with range [0, infinity)
298 */
299 template <typename TIndex, typename T>
300 static inline void applySubset(std::vector<T>& objects, const TIndex* indices, const size_t numberIndices);
301
302 /**
303 * Extracts the indices that are not given within a set indices.
304 * @param indices The set of given indices, the resulting indices will not contain any of these indices, can contain indices with range [0, maximalIndex]
305 * @param numberElements The number of possible elements defining the entire range of possible indices: [0, numberElements)
306 * @tparam TIndex Data type of the index elements
307 */
308 template <typename TIndex>
309 static std::vector<TIndex> invertedIndices(const std::vector<TIndex>& indices, const size_t numberElements);
310
311 /**
312 * Extracts the indices that are not given within a set indices.
313 * @param indices The set of given indices, the resulting indices will not contain any of these indices, can contain indices with range [0, maximalIndex]
314 * @param numberElements The number of possible elements defining the entire range of possible indices: [0, numberElements)
315 * @tparam TIndex Data type of the index elements
316 */
317 template <typename TIndex>
318 static std::unordered_set<TIndex> invertedIndices(const std::unordered_set<TIndex>& indices, const size_t numberElements);
319
320 /**
321 * Extracts the indices that are not given within a set indices.
322 * @param indices The set of given indices, the resulting indices will not contain any of these indices, can contain indices with range [0, maximalIndex]
323 * @param numberElements The number of possible elements defining the entire range of possible indices: [0, numberElements)
324 * @tparam TIndex Data type of the index elements
325 */
326 template <typename TIndex>
327 static std::set<TIndex> invertedIndices(const std::set<TIndex>& indices, const size_t numberElements);
328
329 /**
330 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not used.
331 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
332 * @param objects Entire set of objects from that a subset will be extracted
333 * @param numberObjects Number of given objects
334 * @param indices Indices defining the inverted subset to be extracted
335 * @return Resulting subset of the given objects
336 * @tparam TIndex Data type of the index elements
337 * @tparam T Data type of the objects
338 */
339 template <typename TIndex, typename T>
340 static inline std::vector<T> invertedSubset(const T* objects, const size_t numberObjects, const std::unordered_set<TIndex>& indices);
341
342 /**
343 * Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not used.
344 * Beware: No range check is done! Thus, each index must not exceed the number of given objects.<br>
345 * @param objects Entire set of objects from that a subset will be extracted
346 * @param numberObjects Number of given objects
347 * @param indices Indices defining the inverted subset to be extracted
348 * @return Resulting subset of the given objects
349 * @tparam TIndex Data type of the index elements
350 * @tparam T Data type of the objects
351 */
352 template <typename TIndex, typename T>
353 static inline std::vector<T> invertedSubset(const T* objects, const size_t numberObjects, const std::set<TIndex>& indices);
354
355 /**
356 * Converts object indices to an uint8_t vector holding statements for each object.
357 * @param indices Indices defining the subset of the objects, with range [0, numberObjects)
358 * @param numberObjects Number of objects that can be addressed by the indices
359 * @return Resulting boolean statements
360 * @tparam TIndex Data type of the index elements
361 * @tparam tValue Value for objects that are defined in the indices, the inverse value is applied otherwise
362 */
363 template <typename TIndex, uint8_t tValue>
364 static inline std::vector<uint8_t> indices2statements(const std::vector<TIndex>& indices, const size_t numberObjects);
365
366 /**
367 * Converts object indices to an uint8_t vector holding statements for each object.
368 * @param indices Indices defining the subset of the objects, with range [0, numberObjects)
369 * @param numberObjects Number of objects that can be addressed by the indices
370 * @return Resulting boolean statements
371 * @tparam TIndex Data type of the index elements
372 * @tparam tValue Value for objects that are defined in the indices, the inverse value is applied otherwise
373 */
374 template <typename TIndex, uint8_t tValue>
375 static inline std::vector<uint8_t> indices2statements(const std::set<TIndex>& indices, const size_t numberObjects);
376
377 /**
378 * Converts object indices to an uint8_t vector holding statements for each object.
379 * @param indices Indices defining the subset of the objects, with range [0, numberObjects)
380 * @param numberObjects Number of objects that can be addressed by the indices
381 * @return Resulting boolean statements
382 * @tparam TIndex Data type of the index elements
383 * @tparam tValue Value for objects that are defined in the indices, the inverse value is applied otherwise
384 */
385 template <typename TIndex, uint8_t tValue>
386 static inline std::vector<uint8_t> indices2statements(const std::unordered_set<TIndex>& indices, const size_t numberObjects);
387
388 /**
389 * Converts object indices to an uint8_t vector holding statements for each object.
390 * @param indices Indices defining the subset of the objects, with range [0, numberObjects)
391 * @param numberIndices Number of provided indices
392 * @param numberObjects Number of objects that can be addressed by the indices
393 * @return Resulting boolean statements
394 * @tparam TIndex Data type of the index elements
395 * @tparam tValue Value for objects that are defined in the indices, the inverse value is applied otherwise
396 */
397 template <typename TIndex, uint8_t tValue>
398 static inline std::vector<uint8_t> indices2statements(const TIndex* indices, const size_t numberIndices, const size_t numberObjects);
399
400 /**
401 * Converts an uint8_t vector holding statements for each object into object indices.
402 * @param statements Boolean statement for each object
403 * @return Resulting object indices
404 * @tparam TIndex Data type of the index elements
405 * @tparam tValue Value for objects that will be defined in the indices
406 */
407 template <typename TIndex, uint8_t tValue>
408 static inline std::vector<TIndex> statements2indices(const std::vector<uint8_t>& statements);
409
410 /**
411 * Converts an uint8_t vector holding statements for each object into object indices.
412 * @param statements Boolean statement for each object
413 * @param numberStatements Number of statements
414 * @return Resulting object indices
415 * @tparam TIndex Data type of the index elements
416 * @tparam tValue Value for objects that will be defined in the indices
417 */
418 template <typename TIndex, uint8_t tValue>
419 static inline std::vector<TIndex> statements2indices(const uint8_t* statements, const size_t numberStatements);
420
421 /**
422 * Determines corresponding element pairs from two sets of element maps.
423 * Two elements correspond with each other if they have the same key.
424 * @param elementMapA The first map of elements
425 * @param elementMapB The second map of elements
426 * @param elementsA The resulting elements from the first map which have a corresponding element in the second map
427 * @param elementsB The resulting elements from the second map which have a corresponding element in the first map
428 * @tparam TKey The data type of each key
429 * @tparam TElement The data type of each element
430 */
431 template <typename TKey, typename TElement>
432 static void correspondingElements(const std::map<TKey, TElement>& elementMapA, const std::map<TKey, TElement>& elementMapB, std::vector<TElement>& elementsA, std::vector<TElement>& elementsB);
433
434 /**
435 * Determines whether two (ordered) sets have at least one intersecting element.
436 * Both input sets must be in ascending order.
437 * @param firstA The iterator to the first element in the first set
438 * @param endA The iterator to the (exclusive) element after the last element in the first set
439 * @param firstB The iterator to the first element in the second set
440 * @param endB The iterator to the (exclusive) element after the last element in the second set
441 * @return True, if so
442 */
443 template <typename TIterator>
444 static bool hasIntersectingElement(const TIterator& firstA, const TIterator& endA, const TIterator& firstB, const TIterator& endB);
445
446 /**
447 * Determines whether two (ordered) sets have at least one intersecting element.
448 * @param setA The first set to check, can be empty
449 * @param setB The second set to check, can be empty
450 * @return True, if so
451 */
452 template <typename T>
453 static inline bool hasIntersectingElement(const std::set<T>& setA, const std::set<T>& setB);
454
455 /**
456 * Determines whether two ordered vectors have at least one intersecting element.
457 * @param sortedA The first vector to check, can be empty
458 * @param sortedB The second vector to check, can be empty
459 * @return True, if so
460 */
461 template <typename T>
462 static inline bool hasIntersectingElement(const std::vector<T>& sortedA, const std::vector<T>& sortedB);
463};
464
465template <typename TIndex>
466template <typename T>
467inline std::vector<T> Subset::InternalSubset<TIndex>::subset(const std::vector<T>& objects, const std::vector<TIndex>& indices)
468{
469 std::vector<T> result;
470 result.reserve(indices.size());
471
472 for (const TIndex& index : indices)
473 {
474 ocean_assert(size_t(index) < objects.size());
475 result.push_back(objects[size_t(index)]);
476 }
477
478 return result;
479}
480
481template <>
482template <typename T>
483inline std::vector<T> Subset::InternalSubset<uint8_t>::subset(const std::vector<T>& objects, const std::vector<uint8_t>& indices)
484{
485 std::vector<T> result;
486 result.reserve(indices.size());
487
488 typename std::vector<T>::const_iterator iObject = objects.begin();
489
490 for (const uint8_t index : indices)
491 {
492 if (index != 0u)
493 {
494 result.push_back(*iObject);
495 }
496
497 ++iObject;
498 }
499
500 return result;
501}
502
503template <typename TIndex>
504template <typename T>
505inline std::vector<T> Subset::InternalSubset<TIndex>::subset(const std::vector<T>& objects, const std::set<TIndex>& indices)
506{
507 std::vector<T> result;
508 result.reserve(indices.size());
509
510 for (typename std::set<TIndex>::const_iterator i = indices.begin(); i != indices.end(); ++i)
511 {
512 ocean_assert(*i < objects.size());
513 result.push_back(objects[size_t(*i)]);
514 }
515
516 return result;
517}
518
519template <typename TIndex>
520template <typename T>
521inline std::vector<T> Subset::InternalSubset<TIndex>::invertedSubset(const std::vector<T>& objects, const std::unordered_set<TIndex>& indices)
522{
523 ocean_assert(objects.size() >= indices.size());
524 ocean_assert((unsigned long long)(objects.size()) < (unsigned long long)(std::numeric_limits<TIndex>::max()));
525
526 if (objects.size() == indices.size())
527 {
528#ifdef OCEAN_DEBUG
529 for (const TIndex& index : indices)
530 {
531 ocean_assert(index < objects.size());
532 }
533#endif
534
535 return std::vector<T>();
536 }
537
538 std::vector<T> result;
539 result.reserve(objects.size() - indices.size());
540
541 for (size_t n = 0u; n < objects.size(); ++n)
542 {
543 if (indices.find(TIndex(n)) == indices.cend())
544 {
545 result.push_back(objects[n]);
546 }
547 }
548
549 return result;
550}
551
552template <typename TIndex>
553template <typename T>
554inline std::vector<T> Subset::InternalSubset<TIndex>::invertedSubset(const std::vector<T>& objects, const std::set<TIndex>& indices)
555{
556 ocean_assert(objects.size() >= indices.size());
557 ocean_assert((unsigned long long)(objects.size()) < (unsigned long long)(std::numeric_limits<TIndex>::max()));
558
559 if (objects.size() == indices.size())
560 {
561#ifdef OCEAN_DEBUG
562 for (const TIndex& index : indices)
563 {
564 ocean_assert(index < objects.size());
565 }
566#endif
567
568 return std::vector<T>();
569 }
570
571 std::vector<T> result;
572 result.reserve(objects.size() - indices.size());
573
574 for (size_t n = 0u; n < objects.size(); ++n)
575 {
576 if (indices.find(TIndex(n)) == indices.cend())
577 {
578 result.push_back(objects[n]);
579 }
580 }
581
582 return result;
583}
584
585template <typename TIndex>
586template <typename T>
587inline std::vector<T> Subset::InternalSubset<TIndex>::subset(const T* objects, const size_t numberObjects, const TIndex* indices, const size_t numberIndices)
588{
589 std::vector<T> result;
590 result.reserve(numberIndices);
591
592 for (size_t n = 0; n < numberIndices; ++n)
593 {
594 ocean_assert_and_suppress_unused(indices[n] < numberObjects, numberObjects);
595
596 result.push_back(objects[indices[n]]);
597 }
598
599 return result;
600}
601
602template <>
603template <typename T>
604inline std::vector<T> Subset::InternalSubset<uint8_t>::subset(const T* objects, const size_t numberObjects, const uint8_t* indices, const size_t numberIndices)
605{
606 ocean_assert_and_suppress_unused(numberIndices <= numberObjects, numberObjects);
607
608 std::vector<T> result;
609 result.reserve(numberIndices);
610
611 for (size_t n = 0; n < numberIndices; ++n)
612 {
613 if (indices[n] != 0u)
614 {
615 result.push_back(objects[n]);
616 }
617 }
618
619 return result;
620}
621
622template <typename TIndex>
623template <typename T>
624inline std::vector<T> Subset::InternalSubset<TIndex>::subset(const T* objects, const size_t numberObjects, const std::vector<TIndex>& indices)
625{
626 return subset(objects, numberObjects, indices.data(), indices.size());
627}
628
629template <typename TIndex>
630template <typename T>
631inline std::vector<T> Subset::InternalSubset<TIndex>::subset(const T* objects, const size_t numberObjects, const std::set<TIndex>& indices)
632{
633 std::vector<T> result;
634 result.reserve(indices.size());
635
636 for (const TIndex& index : indices)
637 {
638 ocean_assert_and_suppress_unused(index < numberObjects, numberObjects);
639
640 result.push_back(objects[index]);
641 }
642
643 return result;
644}
645
646template <typename TIndex>
647template <typename T>
648inline std::vector<T> Subset::InternalSubset<TIndex>::invertedSubset(const T* objects, const size_t numberObjects, const std::unordered_set<TIndex>& indices)
649{
650 ocean_assert(numberObjects >= indices.size());
651 ocean_assert((unsigned long long)(numberObjects) < (unsigned long long)(std::numeric_limits<TIndex>::max()));
652
653 if (numberObjects == indices.size())
654 {
655#ifdef OCEAN_DEBUG
656 for (const TIndex& index : indices)
657 {
658 ocean_assert(indices < numberObjects);
659 }
660#endif
661
662 return std::vector<T>();
663 }
664
665 std::vector<T> result;
666 result.reserve(numberObjects - indices.size());
667
668 for (size_t n = 0; n < numberObjects; ++n)
669 {
670 if (indices.find(TIndex(n)) == indices.cend())
671 {
672 result.push_back(objects[n]);
673 }
674 }
675
676 return result;
677}
678
679template <typename TIndex>
680template <typename T>
681inline std::vector<T> Subset::InternalSubset<TIndex>::invertedSubset(const T* objects, const size_t numberObjects, const std::set<TIndex>& indices)
682{
683 ocean_assert(numberObjects >= indices.size());
684 ocean_assert((unsigned long long)(numberObjects) < (unsigned long long)(std::numeric_limits<TIndex>::max()));
685
686 if (numberObjects == indices.size())
687 {
688#ifdef OCEAN_DEBUG
689 for (const TIndex& index : indices)
690 {
691 ocean_assert(index < numberObjects);
692 }
693#endif
694
695 return std::vector<T>();
696 }
697
698 std::vector<T> result;
699 result.reserve(numberObjects - indices.size());
700
701 for (size_t n = 0; n < numberObjects; ++n)
702 {
703 if (indices.find(TIndex(n)) == indices.cend())
704 {
705 result.push_back(objects[n]);
706 }
707 }
708
709 return result;
710}
711
712template <typename TIndex>
713template <typename TContainer, uint8_t tValue>
714inline std::vector<uint8_t> Subset::InternalSubset<TIndex>::indices2statements(const TContainer& indices, const size_t numberObjects)
715{
716 std::vector<uint8_t> result(numberObjects, !tValue);
717
718 for (const TIndex& index : indices)
719 {
720 ocean_assert(index < result.size());
721 result[index] = tValue;
722 }
723
724 return result;
725}
726
727template <typename TIndex>
728template <uint8_t tValue>
729inline std::vector<uint8_t> Subset::InternalSubset<TIndex>::indices2statements(const TIndex* indices, const size_t numberIndices, const size_t numberObjects)
730{
731 std::vector<uint8_t> result(numberObjects, !tValue);
732
733 for (size_t n = 0; n < numberIndices; ++n)
734 {
735 ocean_assert(indices[n] < result.size());
736 result[indices[n]] = tValue;
737 }
738
739 return result;
740}
741
742template <typename TIndex>
743template <uint8_t tValue>
744inline std::vector<TIndex> Subset::InternalSubset<TIndex>::statements2indices(const std::vector<uint8_t>& statements)
745{
746 std::vector<TIndex> result;
747
748 for (size_t n = 0; n < statements.size(); ++n)
749 {
750 if (statements[n] == tValue)
751 {
752 result.push_back(TIndex(n));
753 }
754 }
755
756 return result;
757}
758
759template <typename TIndex>
760template <uint8_t tValue>
761inline std::vector<TIndex> Subset::InternalSubset<TIndex>::statements2indices(const uint8_t* statements, const size_t numberStatements)
762{
763 std::vector<TIndex> result;
764
765 for (size_t n = 0; n < numberStatements; ++n)
766 {
767 if (statements[n] == tValue)
768 {
769 result.push_back(TIndex(n));
770 }
771 }
772
773 return result;
774}
775
776template <typename TIndex, typename T>
777inline std::vector<T> Subset::subset(const std::vector<T>& objects, const std::vector<TIndex>& indices)
778{
779 return InternalSubset<TIndex>::template subset<T>(objects, indices);
780}
781
782template <typename TIndex, typename T>
783inline std::vector<T> Subset::subset(const std::vector<T>& objects, const std::set<TIndex>& indices)
784{
785 return InternalSubset<TIndex>::template subset<T>(objects, indices);
786}
787
788template <typename TIndex>
789std::vector<TIndex> Subset::invertedIndices(const std::vector<TIndex>& indices, const size_t numberElements)
790{
791 ocean_assert(indices.size() <= TIndex(numberElements));
792
793 if (indices.size() == numberElements)
794 {
795#ifdef OCEAN_DEBUG
796 const std::unordered_set<TIndex> indexSet(indices.begin(), indices.end());
797 ocean_assert(indexSet.size() == indices.size());
798
799 for (size_t n = 0; n < numberElements; ++n)
800 {
801 ocean_assert(indexSet.find(TIndex(n)) != indexSet.cend());
802 }
803#endif
804
805 return std::vector<TIndex>();
806 }
807
808 const std::unordered_set<TIndex> indexSet(indices.begin(), indices.end());
809 ocean_assert(indexSet.size() == indices.size());
810
811 std::vector<TIndex> result;
812 result.reserve(numberElements - indices.size());
813
814 for (TIndex i = TIndex(0); i < TIndex(numberElements); ++i)
815 {
816 if (indexSet.find(i) == indexSet.cend())
817 {
818 result.push_back(i);
819 }
820 }
821
822 return result;
823}
824
825template <typename TIndex>
826std::unordered_set<TIndex> Subset::invertedIndices(const std::unordered_set<TIndex>& indices, const size_t numberElements)
827{
828 ocean_assert(indices.size() <= TIndex(numberElements));
829
830 if (indices.size() == numberElements)
831 {
832#ifdef OCEAN_DEBUG
833 for (size_t n = 0; n < numberElements; ++n)
834 {
835 ocean_assert(indices.find(TIndex(n)) != indices.end());
836 }
837#endif
838
839 return std::unordered_set<TIndex>();
840 }
841
842 std::unordered_set<TIndex> result;
843 result.reserve(numberElements - indices.size());
844
845 for (TIndex i = TIndex(0); i < TIndex(numberElements); ++i)
846 {
847 if (indices.find(i) == indices.cend())
848 {
849 result.emplace(i);
850 }
851 }
852
853 return result;
854}
855
856template <typename TIndex>
857std::set<TIndex> Subset::invertedIndices(const std::set<TIndex>& indices, const size_t numberElements)
858{
859 ocean_assert(indices.size() <= TIndex(numberElements));
860
861 if (indices.size() == numberElements)
862 {
863#ifdef OCEAN_DEBUG
864 for (size_t n = 0; n < numberElements; ++n)
865 {
866 ocean_assert(indices.find(TIndex(n)) != indices.end());
867 }
868#endif
869
870 return std::set<TIndex>();
871 }
872
873 std::set<TIndex> result;
874
875 for (TIndex i = TIndex(0); i < TIndex(numberElements); ++i)
876 {
877 if (indices.find(i) == indices.cend())
878 {
879 result.insert(i);
880 }
881 }
882
883 return result;
884}
885
886template <typename TIndex, typename T>
887inline std::vector<T> Subset::invertedSubset(const std::vector<T>& objects, const std::unordered_set<TIndex>& indices)
888{
889 return InternalSubset<TIndex>::template invertedSubset<T>(objects, indices);
890}
891
892template <typename TIndex, typename T>
893inline std::vector<T> Subset::invertedSubset(const std::vector<T>& objects, const std::set<TIndex>& indices)
894{
895 return InternalSubset<TIndex>::template invertedSubset<T>(objects, indices);
896}
897
898template <typename TIndex, typename T>
899inline std::vector<T> Subset::subset(const T* objects, const size_t numberObjects, const TIndex* indices, const size_t numberIndices)
900{
901 return InternalSubset<TIndex>::template subset<T>(objects, numberObjects, indices, numberIndices);
902}
903
904template <typename TIndex, typename T>
905inline std::vector<T> Subset::subset(const T* objects, const size_t numberObjects, const std::vector<TIndex>& indices)
906{
907 return InternalSubset<TIndex>::template subset<T>(objects, numberObjects, indices);
908}
909
910template <typename TIndex, typename T>
911inline std::vector<T> Subset::subset(const T* objects, const size_t numberObjects, const std::set<TIndex>& indices)
912{
913 return InternalSubset<TIndex>::template subset<T>(objects, numberObjects, indices);
914}
915
916template <typename TIndexIterator, typename T>
917void Subset::applySubset(std::vector<T>& objects, const TIndexIterator& begin, const TIndexIterator& end)
918{
919 if (begin == end)
920 {
921 objects.clear();
922 return;
923 }
924
925 size_t nIndex = 0;
926
927 for (TIndexIterator iterator = begin; iterator < end; ++iterator)
928 {
929 objects[nIndex] = std::move(objects[*iterator]);
930
931 ++nIndex;
932 }
933
934 objects.resize(nIndex);
935}
936
937template <typename TIndex, typename T>
938void Subset::applySubset(std::vector<T>& objects, const std::vector<TIndex>& sortedIndices)
939{
940 applySubset(objects, sortedIndices.cbegin(), sortedIndices.cend());
941}
942
943template <typename TIndex, typename T>
944void Subset::applySubset(std::vector<T>& objects, const TIndex* sortedIndices, const size_t numberSortedIndices)
945{
946 applySubset(objects, sortedIndices, sortedIndices + numberSortedIndices);
947}
948
949template <typename TIndex, typename T>
950inline std::vector<T> Subset::invertedSubset(const T* objects, const size_t numberObjects, const std::unordered_set<TIndex>& indices)
951{
952 return InternalSubset<TIndex>::template invertedSubset<T>(objects, numberObjects, indices);
953}
954
955template <typename TIndex, typename T>
956inline std::vector<T> Subset::invertedSubset(const T* objects, const size_t numberObjects, const std::set<TIndex>& indices)
957{
958 return InternalSubset<TIndex>::template invertedSubset<T>(objects, numberObjects, indices);
959}
960
961template <typename TIndex, uint8_t tValue>
962inline std::vector<uint8_t> Subset::indices2statements(const std::vector<TIndex>& indices, const size_t numberObjects)
963{
964 return InternalSubset<TIndex>::template indices2statements<std::vector<TIndex>, tValue>(indices, numberObjects);
965}
966
967template <typename TIndex, uint8_t tValue>
968inline std::vector<uint8_t> Subset::indices2statements(const std::unordered_set<TIndex>& indices, const size_t numberObjects)
969{
970 return InternalSubset<TIndex>::template indices2statements<std::unordered_set<TIndex>, tValue>(indices, numberObjects);
971}
972
973template <typename TIndex, uint8_t tValue>
974inline std::vector<uint8_t> Subset::indices2statements(const std::set<TIndex>& indices, const size_t numberObjects)
975{
976 return InternalSubset<TIndex>::template indices2statements<std::set<TIndex>, tValue>(indices, numberObjects);
977}
978
979template <typename TIndex, uint8_t tValue>
980inline std::vector<uint8_t> Subset::indices2statements(const TIndex* indices, const size_t numberIndices, const size_t numberObjects)
981{
982 return InternalSubset<TIndex>::template indices2statements<tValue>(indices, numberIndices, numberObjects);
983}
984
985template <typename TIndex, uint8_t tValue>
986inline std::vector<TIndex> Subset::statements2indices(const std::vector<uint8_t>& statements)
987{
988 return InternalSubset<TIndex>::template statements2indices<tValue>(statements);
989}
990
991template <typename TIndex, uint8_t tValue>
992inline std::vector<TIndex> Subset::statements2indices(const uint8_t* statements, const size_t numberStatements)
993{
994 return InternalSubset<TIndex>::template statements2indices<tValue>(statements, numberStatements);
995}
996
997template <typename TKey, typename TElement>
998void Subset::correspondingElements(const std::map<TKey, TElement>& elementMapA, const std::map<TKey, TElement>& elementMapB, std::vector<TElement>& elementsA, std::vector<TElement>& elementsB)
999{
1000 elementsA.clear();
1001 elementsB.clear();
1002
1003 // we expect that the map entries are sorted based on their keys
1004 ocean_assert(elementMapA.size() < 2 || elementMapA.cbegin()->first < elementMapA.crbegin()->first);
1005 ocean_assert(elementMapB.size() < 2 || elementMapB.cbegin()->first < elementMapB.crbegin()->first);
1006
1007 typename std::map<TKey, TElement>::const_iterator iA = elementMapA.cbegin();
1008 typename std::map<TKey, TElement>::const_iterator iB = elementMapB.cbegin();
1009
1010 while (iA != elementMapA.cend() && iB != elementMapB.cend())
1011 {
1012 // let's find elements with identical keys
1013
1014 if (iA->first > iB->first)
1015 {
1016 ++iB;
1017 }
1018 else if (iA->first < iB->first)
1019 {
1020 ++iA;
1021 }
1022 else
1023 {
1024 ocean_assert(iA->first == iB->first);
1025
1026 elementsA.emplace_back(iA->second);
1027 elementsB.emplace_back(iB->second);
1028
1029 ++iA;
1030 ++iB;
1031 }
1032 }
1033}
1034
1035template <typename TIterator>
1036bool Subset::hasIntersectingElement(const TIterator& firstA, const TIterator& endA, const TIterator& firstB, const TIterator& endB)
1037{
1038 if (firstA == endA || firstB == endB)
1039 {
1040 return false;
1041 }
1042
1043#ifdef OCEAN_DEBUG
1044 TIterator debugLeftA = firstA;
1045 TIterator debugRightA = firstA;
1046 ++debugRightA;
1047
1048 TIterator debugLeftB = firstB;
1049 TIterator debugRightB = firstB;
1050 ++debugRightB;
1051
1052 while (debugRightA != endA && debugRightB != endB)
1053 {
1054 ocean_assert(*debugLeftA++ <= *debugRightA++);
1055 ocean_assert(*debugLeftB++ <= *debugRightB++);
1056 }
1057#endif
1058
1059 TIterator lastA = endA;
1060 TIterator lastB = endB;
1061
1062 if (*(--lastA) < *firstB || *(--lastB) < *firstA)
1063 {
1064 return false;
1065 }
1066
1067 TIterator iA = firstA;
1068 TIterator iB = firstB;
1069
1070 while (iA != endA && iB != endB)
1071 {
1072 if (*iA == *iB)
1073 {
1074 return true;
1075 }
1076
1077 if (*iA < *iB)
1078 {
1079 ++iA;
1080 }
1081 else
1082 {
1083 ocean_assert(*iA > *iB);
1084 ++iB;
1085 }
1086 }
1087
1088 return false;
1089}
1090
1091template <typename T>
1092bool Subset::hasIntersectingElement(const std::set<T>& setA, const std::set<T>& setB)
1093{
1094 return hasIntersectingElement(setA.cbegin(), setA.cend(), setB.cbegin(), setB.cend());
1095}
1096
1097template <typename T>
1098bool Subset::hasIntersectingElement(const std::vector<T>& sortedA, const std::vector<T>& sortedB)
1099{
1100 return hasIntersectingElement(sortedA.cbegin(), sortedA.cend(), sortedB.cbegin(), sortedB.cend());
1101}
1102
1103}
1104
1105#endif // META_OCEAN_BASE_SUBSET_H
This helper class implements a subset functions.
Definition Subset.h:30
static std::vector< T > invertedSubset(const std::vector< T > &objects, const std::unordered_set< TIndex > &indices)
Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not use...
Definition Subset.h:521
static std::vector< uint8_t > indices2statements(const TContainer &indices, const size_t numberObjects)
Converts object indices to an uint8_t vector holding statements for each object.
Definition Subset.h:714
static std::vector< TIndex > statements2indices(const std::vector< uint8_t > &statements)
Converts an uint8_t vector holding statements for each object into object indices.
Definition Subset.h:744
static std::vector< T > subset(const std::vector< T > &objects, const std::vector< TIndex > &indices)
Extracts a subset of a given set of objects by usage of an index vector holding the indices of all ob...
Definition Subset.h:467
This class implements subset functions.
Definition Subset.h:21
static void applySubset(std::vector< T > &objects, const TIndexIterator &begin, const TIndexIterator &end)
Applies a subset to a vector of objects.
Definition Subset.h:917
static std::vector< uint8_t > indices2statements(const std::vector< TIndex > &indices, const size_t numberObjects)
Converts object indices to an uint8_t vector holding statements for each object.
Definition Subset.h:962
static bool hasIntersectingElement(const TIterator &firstA, const TIterator &endA, const TIterator &firstB, const TIterator &endB)
Determines whether two (ordered) sets have at least one intersecting element.
Definition Subset.h:1036
static std::vector< T > subset(const std::vector< T > &objects, const std::vector< TIndex > &indices)
Extracts a subset of a given set of objects by usage of an index vector holding the indices of all ob...
Definition Subset.h:777
static std::vector< TIndex > invertedIndices(const std::vector< TIndex > &indices, const size_t numberElements)
Extracts the indices that are not given within a set indices.
Definition Subset.h:789
static void correspondingElements(const std::map< TKey, TElement > &elementMapA, const std::map< TKey, TElement > &elementMapB, std::vector< TElement > &elementsA, std::vector< TElement > &elementsB)
Determines corresponding element pairs from two sets of element maps.
Definition Subset.h:998
static std::vector< TIndex > statements2indices(const std::vector< uint8_t > &statements)
Converts an uint8_t vector holding statements for each object into object indices.
Definition Subset.h:986
static std::vector< T > invertedSubset(const std::vector< T > &objects, const std::unordered_set< TIndex > &indices)
Extracts a subset of a given set of objects by usage of a set of indices of all objects to be not use...
Definition Subset.h:887
The namespace covering the entire Ocean framework.
Definition Accessor.h:15