C++ Library Extensions 2022.12.09
To help learn modern C++ programming
tpf_set.hpp
Go to the documentation of this file.
1
11#ifndef _TPF_SET_HPP
12#define _TPF_SET_HPP
13
14#ifndef NOMINMAX
15#define NOMINMAX
16#endif
17
18#ifdef _MSVC_LANG
19 #if _MSVC_LANG < 201703L
20 #error This libary requires C++17 Standard (Visual Studio 2017).
21 #endif
22#else
23
24 #if __cplusplus < 201703
25 #error This library requires C++17 Standard (GNU g++ version 8.0 or clang++ version 8.0 above)
26 #endif // end of __cplusplus
27
28#endif // end of _MSVC_LANG
29
30#include <tpf_types.hpp>
31#include <tpf_output.hpp>
32#include <tpf_ncrnpr.hpp>
33
34#include <deque>
35#include <exception>
36#include <cassert>
37#include <sstream>
38#include <string>
39#include <algorithm>
40
45namespace tpf
46{
51 namespace set
52 {
53 // using set_tag = tpf::set_tag<int, std::vector>;
54
55 // using element_t = set_tag::element_t;
56 // using set_t = set_tag::set_t;
57 // using sets_t = set_tag::sets_t;
58 // using set_of_sets_t = set_tag::set_of_sets_t;
59 // using sets_of_sets_t = set_tag::sets_of_sets_t;
60
61 enum class sort_order { ascending, descending };
62 enum class sort_method { dictionary, size };
63
64 template<typename Type>
65 constexpr auto count_of_subsets(Type element_count)
66 {
67 return tpf::two_power_n(element_count);
68 }
69
70 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
71 types::enable_if_container_type_t<ContainerType<EleType, Types...>, void>
72 smart_shrink_to_fit(ContainerType<EleType, Types...>& container, size_t factor = 2)
73 {
74 using container_t = ContainerType<EleType, Types...>;
75
76 if constexpr(types::is_shrink_to_fit_available_v<container_t>
77 && types::is_capacity_available_v<container_t>)
78 {
79 if(container.empty())
80 {
81 container.shrink_to_fit();
82 }
83 else
84 {
85 if(container.capacity() > (container.size() * factor + container.size()/factor))
86 container.shrink_to_fit();
87 }
88 }
89 }
90
91 // if same, returns 0
92 // if left < right, returns -1
93 // otherwise, returns +1
94 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
95 types::enable_if_container_type_t<ContainerType<EleType, Types...>, int>
96 compare_sets_dictionary(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
97 {
98 size_t left_size = left.size();
99 size_t right_size = right.size();
100
101 // if element counts are equal
102 if (left_size == right_size)
103 {
104 if (left_size == 0) // if empty, the are the same
105 return 0;
106 else
107 {
108 for (size_t i = 0; i < left_size; ++i)
109 {
110 if (left[i] < right[i])
111 return -1;
112 else if (left[i] > right[i])
113 return 1;
114 }
115
116 return 0;
117 }
118 }
119 else // if element counts are NOT equal
120 {
121 size_t size = left_size < right_size ? left_size : right_size;
122
123 for (size_t i = 0; i < size; ++i)
124 {
125 if (left[i] < right[i])
126 return -1;
127 else if (left[i] > right[i])
128 return 1;
129 }
130
131 return left_size < right_size ? -1 : 1;
132 }
133 }
134
135 // if same, returns 0
136 // if left < right, returns -1
137 // otherwise, returns +1
138 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
139 types::enable_if_container_type_t<ContainerType<EleType, Types...>, int>
140 compare_sets_size(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
141 {
142 size_t left_size = left.size();
143 size_t right_size = right.size();
144
145 // if element counts are equal
146 if (left_size == right_size)
147 {
148 if (left_size == 0) // if empty, the are the same
149 return 0;
150 else
151 {
152 for (size_t i = 0; i < left_size; ++i)
153 {
154 if (left[i] < right[i])
155 return -1;
156 else if (left[i] > right[i])
157 return 1;
158 }
159
160 return 0;
161 }
162 }
163 else // if element counts are NOT equal
164 {
165 return left_size < right_size ? -1 : 1;
166 }
167 }
168
169 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
170 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
171 operator == (const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
172 {
173 // if element count is different
174 if(left.size() != right.size())
175 return false;
176 else // if element counts are the same
177 {
178 if(left.empty())
179 return true;
180 else
181 {
182 // the element counts of left and right are the same
183 size_t size = left.size();
184 for(size_t i= 0; i <size; ++i)
185 {
186 if(left[i] != right[i])
187 return false;
188 }
189
190 return true;
191 }
192 }
193 }
194
195 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
196 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
197 operator != (const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
198 {
199 return !(left == right);
200 }
201
202 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
203 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
204 compare_less_dictionary(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
205 {
206 return compare_sets_dictionary(left, right) < 0 ? true : false;
207 }
208
209 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
210 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
211 compare_less_equal_dictionary(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
212 {
213 return compare_sets_dictionary(left, right) <= 0 ? true : false;
214 }
215
216 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
217 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
218 compare_greater_dictionary(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
219 {
220 return compare_sets_dictionary(left, right) > 0 ? true : false;
221 }
222
223 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
224 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
225 compare_greater_equal_dictionary(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
226 {
227 return compare_sets_dictionary(left, right) >= 0 ? true : false;
228 }
229
230 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
231 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
232 compare_less_size(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
233 {
234 return compare_sets_size(left, right) < 0 ? true : false;
235 }
236
237 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
238 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
239 compare_less_equal_size(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
240 {
241 return compare_sets_size(left, right) < 0 ? true : false;
242 }
243
244 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
245 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
246 compare_greater_size(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
247 {
248 return compare_sets_size(left, right) > 0 ? true : false;
249 }
250
251 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
252 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
253 compare_greater_equal_size(const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
254 {
255 return compare_sets_size(left, right) >= 0 ? true : false;
256 }
257
258 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
259 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
260 operator < (const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
261 {
262 return compare_sets_size(left, right) < 0 ? true : false;
263 }
264
265 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
266 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
267 operator > (const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
268 {
269 return compare_sets_size(left, right) > 0 ? true : false;
270 }
271
272 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
273 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
274 operator <= (const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
275 {
276 return compare_sets_size(left, right) <= 0 ? true : false;
277 }
278
279 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
280 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
281 operator >= (const ContainerType<EleType, Types...>& left, const ContainerType<EleType, Types...>& right)
282 {
283 return compare_sets_size(left, right) >= 0 ? true : false;
284 }
285
286 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
287 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
288 is_in_container(const EleType& ele, const ContainerType<EleType, Types...>& container)
289 {
290 return std::binary_search(container.cbegin(), container.cend(), ele);
291 }
292
293 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
294 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
295 is_in_unsorted_container(const EleType& ele, const ContainerType<EleType, Types...>& container)
296 {
297 if(container.empty()) return false;
298
299 for(const auto& e: container)
300 {
301 if(e == ele) return true;
302 }
303
304 return false;
305 }
306
307 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
308 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
309 is_sorted(const ContainerType<EleType, Types...>& container,
310 sort_order order = sort_order::ascending,
311 sort_method method=sort_method::size)
312 {
313 using container_t = const ContainerType<EleType, Types...>&;
314
315 if(container.empty()) return true;
316
317 if constexpr(tpf::types::is_container_type_v<EleType>)
318 {
319 auto sort_predicate = [&order, &method](const auto& left, const auto& right)
320 {
321 if(method == sort_method::dictionary)
322 {
323 if(order == sort_order::ascending)
324 {
325 return compare_less_equal_dictionary(left, right);
326 }
327 else
328 { // sort_order::descending
329 return compare_greater_equal_dictionary(left, right);
330 }
331 }
332 else // sort_method::size
333 {
334 if(order == sort_order::ascending)
335 {
336 return compare_less_equal_size(left, right);
337 }
338 else
339 { // sort_order::descending
340 return compare_greater_equal_size(left, right);
341 }
342 }
343 };
344
345 for(const auto& e: container)
346 if(!is_sorted(e)) return false;
347
348 size_t size = container.size();
349
350 for(size_t i=1; i<size; ++i)
351 {
352 // should be optimized for list type
353 if(!sort_predicate(tpf::get_element<container_t>(container, i-1),
354 tpf::get_element<container_t>(container, i)))
355 return false;
356 }
357
358 return true;
359 }
360 else
361 {
362 size_t size = container.size();
363
364 for(size_t i = 1; i < size; ++i)
365 {
366 if(tpf::get_element<container_t>(container, i-1) > tpf::get_element<container_t>(container, i))
367 return false;
368 }
369
370 return true;
371 }
372 }
373
374 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
375 types::enable_if_container_type_t<ContainerType<EleType, Types...>, bool>
376 sort_in_place(ContainerType<EleType, Types...>& container,
377 sort_order order = sort_order::ascending,
378 sort_method method = sort_method::size)
379 {
380 if(container.empty()) return false; // do need to sort?
381
382 if(is_sorted(container)) return false; // do need to sort?
383
384 if constexpr(tpf::types::is_container_type_v<EleType>)
385 {
386 auto sort_predicate = [&order, &method](const auto& left, const auto& right)
387 {
388 if(method == sort_method::dictionary)
389 {
390 if(order == sort_order::ascending)
391 {
392 return compare_less_equal_dictionary(left, right);
393 }
394 else
395 { // sort_order::descending
396 return compare_greater_equal_dictionary(left, right);
397 }
398 }
399 else // sort_method::size
400 {
401 if(order == sort_order::ascending)
402 {
403 return compare_less_equal_size(left, right);
404 }
405 else
406 { // sort_order::descending
407 return compare_greater_equal_size(left, right);
408 }
409 }
410 };
411
412 bool bNeedToSort = false;
413 // sort elements themselves
414 for(auto& e: container)
415 {
416 if(sort_in_place(e, order, method))
417 bNeedToSort = true;
418 }
419
420 if(!bNeedToSort) return false;
421
422 // outer most sort
423 std::sort(container.begin(), container.end(), sort_predicate);
424 container.erase(std::unique(container.begin(), container.end()), container.end());
425 smart_shrink_to_fit(container);
426 return true;
427 }
428 else
429 {
430 std::sort(container.begin(), container.end());
431 container.erase(std::unique(container.begin(), container.end()), container.end());
432 smart_shrink_to_fit(container);
433 return true;
434 }
435 }
436
437 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
438 ContainerType<EleType> sort(ContainerType<EleType, Types...> container,
439 sort_order order = sort_order::ascending,
440 sort_method method = sort_method::size)
441 {
442 sort_in_place(container, order, method);
443 return container;
444 }
445
446 template<template<typename, typename...> class ContainerType,
447 typename EleType, typename RightContainerType, typename... Types>
448 std::enable_if_t<std::is_same_v<ContainerType<EleType, Types...>, remove_cv_ref_t<RightContainerType>>>
449 union_in_place(ContainerType<EleType, Types...>& left, RightContainerType&& right)
450 {
451 if constexpr(std::is_rvalue_reference_v<decltype(right)>)
452 {
453 left.insert(left.end(),
454 std::make_move_iterator(right.begin()),
455 std::make_move_iterator(right.end()));
456 sort_in_place(left);
457 }
458 else
459 {
460 left.insert(left.end(), right.cbegin(), right.cend());
461 sort_in_place(left);
462 }
463 }
464
465 template<template<typename, typename...> class ContainerType,
466 typename EleType, typename RightContainerType1, typename RightContainerType2, typename... Types>
467 std::enable_if_t<std::is_same_v<ContainerType<EleType, Types...>, remove_cv_ref_t<RightContainerType1>>&&
468 std::is_same_v<ContainerType<EleType, Types...>, remove_cv_ref_t<RightContainerType2>>>
469 union_in_place(ContainerType<EleType, Types...>& left,
470 RightContainerType1&& right1, RightContainerType2&& right2)
471 {
472 if constexpr(std::is_rvalue_reference_v<decltype(right1)>)
473 left.insert(left.end(),
474 std::make_move_iterator(right1.begin()),
475 std::make_move_iterator(right1.end()));
476 else
477 left.insert(left.end(), right1.cbegin(), right1.cend());
478
479 if constexpr(std::is_rvalue_reference_v<decltype(right2)>)
480 left.insert(left.end(),
481 std::make_move_iterator(right2.begin()),
482 std::make_move_iterator(right2.end()));
483 else
484 left.insert(left.end(), right2.cbegin(), right2.cend());
485
486 sort_in_place(left);
487 }
488
489 template<template<typename, typename...> class ContainerType,
490 typename EleType, typename RightContainerType, typename... Types>
491 std::enable_if_t<std::is_same_v<ContainerType<EleType, Types...>,
492 remove_cv_ref_t<RightContainerType>>, ContainerType<EleType, Types...>>
493 union_sets(ContainerType<EleType, Types...> left, RightContainerType&& right)
494 {
495 union_sets_in_place(left, std::forward<RightContainerType>(right));
496 return left;
497 }
498
499 template<template<typename, typename...> class ContainerType,
500 typename EleType, typename RightContainerType1, typename RightContainerType2, typename... Types>
501 std::enable_if_t<std::is_same_v<ContainerType<EleType, Types...>, remove_cv_ref_t<RightContainerType1>>&&
502 std::is_same_v<ContainerType<EleType, Types...>, remove_cv_ref_t<RightContainerType2>>,
503 ContainerType<EleType, Types...>>
504 union_sets(ContainerType<EleType, Types...> left,
505 RightContainerType1&& right1, RightContainerType2&& right2)
506 {
507 if constexpr(std::is_rvalue_reference_v<decltype(right1)>)
508 left.insert(left.end(),
509 std::make_move_iterator(right1.begin()),
510 std::make_move_iterator(right1.end()));
511 else
512 left.insert(left.end(), right1.cbegin(), right1.cend());
513
514 if constexpr(std::is_rvalue_reference_v<decltype(right2)>)
515 left.insert(left.end(),
516 std::make_move_iterator(right2.begin()),
517 std::make_move_iterator(right2.end()));
518 else
519 left.insert(left.end(), right2.cbegin(), right2.cend());
520
521 sort_in_place(left); return left;
522 }
523
524 template<typename EleType, template<typename, typename...> class ContainerType,
525 typename... Types1, typename... Types2>
526 ContainerType<EleType, Types1...> union_flat(const ContainerType<ContainerType<EleType, Types1...>, Types2...>& sets)
527 {
528 ContainerType<EleType, Types1...> set;
529
530 for(const auto& s: sets)
531 set.insert(set.begin(), s.cbegin(), s.cend());
532
533 union_sets_in_place(set); return set;
534 }
535
536 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
537 ContainerType<EleType, Types...> intersection(const ContainerType<EleType, Types...>& left,
538 const ContainerType<EleType, Types...>& right)
539 {
540 if(left.empty() || right.empty())
541 return {};
542
543 ContainerType<EleType, Types...> container;
544
545 for(const auto& s: left)
546 {
547 if(is_in_container(s, right))
548 container.push_back(s);
549 }
550
551 return container;
552 }
553
554 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
555 ContainerType<EleType, Types...> intersection(const ContainerType<EleType, Types...>& left,
556 const ContainerType<EleType, Types...>& right1, const ContainerType<EleType, Types...>& right2)
557 {
558 if(left.empty() || right1.empty() || right2.empty())
559 return {};
560
561 ContainerType<EleType, Types...> container;
562
563 for(const auto& s: left)
564 {
565 if(is_in_container(s, right1) && is_in_container(s, right2))
566 container.push_back(s);
567 }
568
569 return container;
570 }
571
572 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
573 ContainerType<EleType, Types...> difference(const ContainerType<EleType, Types...>& left,
574 const ContainerType<EleType, Types...>& right)
575 {
576 ContainerType<EleType, Types...> container;
577
578 for(const auto& s: left)
579 {
580 if(!is_in_container(s, right))
581 container.push_back(s);
582 }
583
584 return container;
585 }
586
587 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
588 ContainerType<EleType, Types...> difference(const ContainerType<EleType, Types...>& left,
589 const ContainerType<EleType, Types...>& right1, const ContainerType<EleType, Types...>& right2)
590 {
591 ContainerType<EleType, Types...> container;
592
593 for(const auto& s: left)
594 {
595 if(!is_in_container(s, right1) && !is_in_container(s, right2))
596 container.push_back(s);
597 }
598
599 return container;
600 }
601
602 namespace hidden
603 {
604 template<template<typename, typename...> class ContainerType,
605 typename EleType, typename... Types, typename... OuterTypes>
606 void build_subsets(ContainerType<ContainerType<EleType, Types...>, OuterTypes...>& SS,
607 ContainerType<EleType, Types...> R, ContainerType<EleType, Types...> S, size_t count)
608 {
609 using set_t = ContainerType<EleType, Types...>;
610 using sets_t = ContainerType<ContainerType<EleType, Types...>, OuterTypes...>;
611
612 if (count > S.size()) { return; } // RULE 1
613 else if (count == 0 && !R.empty()) // RULE 4
614 {
615 SS.emplace_back(std::move(R)); return;
616 }
617 else if (S.size() == count) // RULE 2
618 {
619 R.insert(R.end(), std::make_move_iterator(S.begin()),
620 std::make_move_iterator(S.end()));
621
622 SS.emplace_back(std::move(R));
623
624 return;
625 }
626 else
627 {
628 // make a room for new element
629 R.emplace_back(int{});
630
631 while (count <= S.size()) // RULE 2
632 {
633 // copy first element of S
634 // to the end of R
635 R.back() = types::pop_front(S);
636 build_subsets(SS, R, S, count - 1);
637 }
638 }
639 }
640
641
642 template<template<typename, typename...> class ContainerType, typename EleType, typename... Types>
643 void build_permutations(ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R, size_t r);
644
645 template<template<typename, typename...> class ContainerType,
646 typename EleType, typename... Types, typename... OuterTypes>
647 void build_permutations(ContainerType<ContainerType<EleType, Types...>, OuterTypes...>& permutations,
648 ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R, size_t r);
649
650 template<template<typename, typename...> class ContainerType, typename EleType, typename... Types>
651 void build_permutations_remainder(ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R, size_t r);
652
653 template<template<typename, typename...> class ContainerType,
654 typename EleType, typename... Types, typename... OuterTypes>
655 void build_permutations_remainder(ContainerType<ContainerType<EleType, Types...>, OuterTypes...>& permutations,
656 ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R, size_t r);
657
658 template<template<typename, typename...> class ContainerType,
659 typename EleType, typename... Types, typename... OuterTypes>
660 void build_permutations(tpf::thread_bundle& tb, ContainerType<ContainerType<EleType, Types...>, OuterTypes...>& permutations,
661 ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R, size_t r)
662 {
663 using set_t = ContainerType<EleType, Types...>;
664 using sets_t = ContainerType<ContainerType<EleType, Types...>, OuterTypes...>;
665 using smart_set_t = std::shared_ptr<set_t>;
666 using smart_sets_t = std::shared_ptr<sets_t>;
667
668 if(r==0 || L.empty())
669 {
670 permutations.emplace_back(R);
671 }
672 else
673 {
674 size_t size = L.size();
675
676 // make a room for last element
677 R.emplace_back(EleType{});
678
679 // if an exception is thrown before R.pop_back() is reached
680 // this program does not work properly
681 // we need to handle this issue in EXCEPTION-SAFE manner
682
683 auto r_pop_back = [](auto ptr) { ptr->pop_back(); };
684 using r_type_t = std::remove_reference_t<decltype(R)>;
685
686 // clean_up is also a local variable
687 std::unique_ptr<r_type_t, decltype(r_pop_back)>
688 clean_up(&R, r_pop_back);
689
690 using future_t = std::future<sets_t>;
691 using futures_t = std::vector<future_t>;
692
693 futures_t futures;
694
695 for(size_t i_th = 0; i_th < size; ++i_th)
696 {
697 // copy L to copied_L
698 auto copied_L = L;
699
700 // remove i_th element from copied_L
701 copied_L.erase(copied_L.begin()+i_th);
702
703 // move i_th element from L to R
704 // R.emplace_back( L[i_th] );
705 R.back() = L[i_th];
706
707 if(size < 7 || tb.thread_count >= tb.max_thread_count)
708 build_permutations(permutations, copied_L, R, r-1);
709 else
710 {
711 // smart_set_t shared_L{new set_t{copied_L}};
712 // smart_set_t shared_R{new set_t{R}};
713 // smart_sets_t shared_permutation{new sets_t{}};
714
715 auto go_parallel = [&tb, permutation = sets_t{},
716 L = copied_L, R = R, r=r]() mutable
717 {
718 build_permutations(tb, permutation, L, R, r-1);
719
720 return permutation;
721 };
722
723 futures.emplace_back(std::async(std::launch::async, go_parallel));
724 ++tb.thread_count;
725 }
726 }
727
728 for(auto& f: futures)
729 {
730 auto lps = f.get(); --tb.thread_count;
731
732 permutations.insert(permutations.end(),
733 std::make_move_iterator(lps.begin()),
734 std::make_move_iterator(lps.end()));
735 }
736 }
737
738 } // end of build_permutations()
739
740 template<template<typename, typename...> class ContainerType,
741 typename EleType, typename... Types, typename... OuterTypes>
742 void build_permutations(ContainerType<ContainerType<EleType, Types...>, OuterTypes...>& permutations,
743 ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R)
744 {
745 using set_t = ContainerType<EleType, Types...>;
746 using sets_t = ContainerType<ContainerType<EleType, Types...>, OuterTypes...>;
747 using smart_set_t = std::shared_ptr<set_t>;
748 using smart_sets_t = std::shared_ptr<sets_t>;
749
750 if(L.empty())
751 {
752 permutations.emplace_back(R);
753 }
754 else
755 {
756 size_t size = L.size();
757
758 // make a room for last element
759 R.emplace_back(EleType{});
760
761 // if an exception is thrown before R.pop_back() is reached
762 // this program does not work properly
763 // we need to handle this issue in EXCEPTION-SAFE manner
764
765 auto r_pop_back = [](auto ptr) { ptr->pop_back(); };
766 using r_type_t = std::remove_reference_t<decltype(R)>;
767
768 // clean_up is also a local variable
769 std::unique_ptr<r_type_t, decltype(r_pop_back)>
770 clean_up(&R, r_pop_back);
771
772 for(size_t i_th = 0; i_th < size; ++i_th)
773 {
774 // copy L to copied_L
775 auto copied_L = L;
776
777 // remove i_th element from copied_L
778 copied_L.erase(copied_L.begin()+i_th);
779
780 // move i_th element from L to R
781 // R.emplace_back( L[i_th] );
782 R.back() = L[i_th];
783
784 build_permutations(permutations, copied_L, R);
785 }
786 }
787
788 } // end of build_permutations()
789
790 template<template<typename, typename...> class ContainerType,
791 typename EleType, typename... Types, typename... OuterTypes>
792 void build_permutations(ContainerType<ContainerType<EleType, Types...>, OuterTypes...>& permutations,
793 ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R, size_t r)
794 {
795 using set_t = ContainerType<EleType, Types...>;
796 using sets_t = ContainerType<ContainerType<EleType, Types...>, OuterTypes...>;
797 using smart_set_t = std::shared_ptr<set_t>;
798 using smart_sets_t = std::shared_ptr<sets_t>;
799
800 if(r == 0 || L.empty())
801 {
802 permutations.emplace_back(R);
803 }
804 else
805 {
806 size_t size = L.size();
807
808 // make a room for last element
809 R.emplace_back(EleType{});
810
811 // if an exception is thrown before R.pop_back() is reached
812 // this program does not work properly
813 // we need to handle this issue in EXCEPTION-SAFE manner
814
815 auto r_pop_back = [](auto ptr) { ptr->pop_back(); };
816 using r_type_t = std::remove_reference_t<decltype(R)>;
817
818 // clean_up is also a local variable
819 std::unique_ptr<r_type_t, decltype(r_pop_back)>
820 clean_up(&R, r_pop_back);
821
822 for(size_t i_th = 0; i_th < size; ++i_th)
823 {
824 // copy L to copied_L
825 auto copied_L = L;
826
827 // remove i_th element from copied_L
828 copied_L.erase(copied_L.begin()+i_th);
829
830 // move i_th element from L to R
831 // R.emplace_back( L[i_th] );
832 R.back() = L[i_th];
833
834 build_permutations(permutations, copied_L, R, r-1);
835 }
836 }
837
838 } // end of build_permutations()
839
840
841 template<template<typename, typename...> class ContainerType,
842 typename EleType, typename... Types, typename... OuterTypes>
843 void build_permutations_remainder(ContainerType<ContainerType<EleType, Types...>, OuterTypes...>& permutations,
844 ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R, size_t r)
845 {
846 using set_t = ContainerType<EleType, Types...>;
847 using sets_t = ContainerType<ContainerType<EleType, Types...>, OuterTypes...>;
848 using smart_set_t = std::shared_ptr<set_t>;
849 using smart_sets_t = std::shared_ptr<sets_t>;
850
851 if(r == 0 || L.empty())
852 {
853 auto S = R;
854 if(!L.empty())
855 {
856 for(auto e: L)
857 S.push_back(e);
858 }
859
860 permutations.emplace_back(S);
861 }
862 else
863 {
864 size_t size = L.size();
865
866 // make a room for last element
867 R.emplace_back(EleType{});
868
869 // if an exception is thrown before R.pop_back() is reached
870 // this program does not work properly
871 // we need to handle this issue in EXCEPTION-SAFE manner
872
873 auto r_pop_back = [](auto ptr) { ptr->pop_back(); };
874 using r_type_t = std::remove_reference_t<decltype(R)>;
875
876 // clean_up is also a local variable
877 std::unique_ptr<r_type_t, decltype(r_pop_back)>
878 clean_up(&R, r_pop_back);
879
880 for(size_t i_th = 0; i_th < size; ++i_th)
881 {
882 // copy L to copied_L
883 auto copied_L = L;
884
885 // remove i_th element from copied_L
886 copied_L.erase(copied_L.begin()+i_th);
887
888 // move i_th element from L to R
889 // R.emplace_back( L[i_th] );
890 R.back() = L[i_th];
891
892 build_permutations_remainder(permutations, copied_L, R, r-1);
893 }
894 }
895
896 } // end of build_permutations_remainder()
897
899 template<template<typename, typename...> class ContainerType, typename EleType, typename... Types>
900 void build_permutations(tpf::thread_bundle& tb, ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R)
901 {
902 using set_t = ContainerType<EleType, Types...>;
903 using smart_set_t = std::shared_ptr<set_t>;
904
905 if(L.empty())
906 {
907 // permutations.emplace_back(R);
908 }
909 else
910 {
911 size_t size = L.size();
912
913 // make a room for last element
914 R.emplace_back(EleType{});
915
916 // if an exception is thrown before R.pop_back() is reached
917 // this program does not work properly
918 // we need to handle this issue in EXCEPTION-SAFE manner
919
920 auto r_pop_back = [](auto ptr) { ptr->pop_back(); };
921 using r_type_t = std::remove_reference_t<decltype(R)>;
922
923 // clean_up is also a local variable
924 std::unique_ptr<r_type_t, decltype(r_pop_back)>
925 clean_up(&R, r_pop_back);
926
927 using future_t = std::future<void>;
928 using futures_t = std::vector<future_t>;
929
930 futures_t futures;
931
932 for(size_t i_th = 0; i_th < size; ++i_th)
933 {
934 // copy L to copied_L
935 auto copied_L = L;
936
937 // remove i_th element from copied_L
938 copied_L.erase(copied_L.begin()+i_th);
939
940 // move i_th element from L to R
941 // R.emplace_back( L[i_th] );
942 R.back() = L[i_th];
943
944 if(size < 7 || tb.thread_count >= tb.max_thread_count)
945 build_permutations(copied_L, R);
946 else
947 {
948 smart_set_t shared_L{new set_t{copied_L}};
949 smart_set_t shared_R{new set_t{R}};
950
951 auto go_parallel = [&tb, shared_L, shared_R]()
952 {
953 build_permutations(tb, *shared_L, *shared_R);
954 };
955
956 futures.emplace_back(std::async(std::launch::async, go_parallel));
957 ++tb.thread_count;
958 }
959 }
960
961 for(auto& f: futures)
962 {
963 f.wait(); --tb.thread_count;
964 }
965 }
966
967 } // end of build_permutations()
968
969 template<template<typename, typename...> class ContainerType, typename EleType, typename... Types>
970 void build_permutations(ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R)
971 {
972 using set_t = ContainerType<EleType, Types...>;
973 using smart_set_t = std::shared_ptr<set_t>;
974
975 if(L.empty())
976 {
977 // permutations.emplace_back(R);
978 }
979 else
980 {
981 size_t size = L.size();
982
983 // make a room for last element
984 R.emplace_back(EleType{});
985
986 // if an exception is thrown before R.pop_back() is reached
987 // this program does not work properly
988 // we need to handle this issue in EXCEPTION-SAFE manner
989
990 auto r_pop_back = [](auto ptr) { ptr->pop_back(); };
991 using r_type_t = std::remove_reference_t<decltype(R)>;
992
993 // clean_up is also a local variable
994 std::unique_ptr<r_type_t, decltype(r_pop_back)>
995 clean_up(&R, r_pop_back);
996
997 for(size_t i_th = 0; i_th < size; ++i_th)
998 {
999 // copy L to copied_L
1000 auto copied_L = L;
1001
1002 // remove i_th element from copied_L
1003 copied_L.erase(copied_L.begin()+i_th);
1004
1005 // move i_th element from L to R
1006 // R.emplace_back( L[i_th] );
1007 R.back() = L[i_th];
1008 build_permutations(copied_L, R);
1009 }
1010 }
1011
1012 } // end of build_permutations()
1013
1014 template<template<typename, typename...> class ContainerType, typename EleType, typename... Types>
1015 void build_permutations(ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R, size_t r)
1016 {
1017 using set_t = ContainerType<EleType, Types...>;
1018 using smart_set_t = std::shared_ptr<set_t>;
1019
1020 if(r == 0 || L.empty())
1021 {
1022 // permutations.emplace_back(R);
1023 }
1024 else
1025 {
1026 size_t size = L.size();
1027
1028 // make a room for last element
1029 R.emplace_back(EleType{});
1030
1031 // if an exception is thrown before R.pop_back() is reached
1032 // this program does not work properly
1033 // we need to handle this issue in EXCEPTION-SAFE manner
1034
1035 auto r_pop_back = [](auto ptr) { ptr->pop_back(); };
1036 using r_type_t = std::remove_reference_t<decltype(R)>;
1037
1038 // clean_up is also a local variable
1039 std::unique_ptr<r_type_t, decltype(r_pop_back)>
1040 clean_up(&R, r_pop_back);
1041
1042 for(size_t i_th = 0; i_th < size; ++i_th)
1043 {
1044 // copy L to copied_L
1045 auto copied_L = L;
1046
1047 // remove i_th element from copied_L
1048 copied_L.erase(copied_L.begin()+i_th);
1049
1050 // move i_th element from L to R
1051 // R.emplace_back( L[i_th] );
1052 R.back() = L[i_th];
1053 build_permutations(copied_L, R, r-1);
1054 }
1055 }
1056
1057 } // end of build_permutations()
1058
1059 template<template<typename, typename...> class ContainerType, typename EleType, typename... Types>
1060 void build_permutations_remainder(ContainerType<EleType, Types...>& L, ContainerType<EleType, Types...>& R, size_t r)
1061 {
1062 using set_t = ContainerType<EleType, Types...>;
1063 using smart_set_t = std::shared_ptr<set_t>;
1064
1065 if(r == 0)
1066 {
1067 if(!L.empty())
1068 {
1069 for(auto e: L) R.push_back(e);
1070 }
1071 }
1072 else
1073 {
1074 size_t size = L.size();
1075
1076 // make a room for last element
1077 R.emplace_back(EleType{});
1078
1079 // if an exception is thrown before R.pop_back() is reached
1080 // this program does not work properly
1081 // we need to handle this issue in EXCEPTION-SAFE manner
1082
1083 auto r_pop_back = [](auto ptr) { ptr->pop_back(); };
1084 using r_type_t = std::remove_reference_t<decltype(R)>;
1085
1086 // clean_up is also a local variable
1087 std::unique_ptr<r_type_t, decltype(r_pop_back)>
1088 clean_up(&R, r_pop_back);
1089
1090 for(size_t i_th = 0; i_th < size; ++i_th)
1091 {
1092 // copy L to copied_L
1093 auto copied_L = L;
1094
1095 // remove i_th element from copied_L
1096 copied_L.erase(copied_L.begin()+i_th);
1097
1098 // move i_th element from L to R
1099 // R.emplace_back( L[i_th] );
1100 R.back() = L[i_th];
1101 build_permutations_remainder(copied_L, R, r-1);
1102 }
1103 }
1104
1105 } // end of build_permutations_remainder()
1106
1107 } // end of namespace hidden
1108
1109 template<typename ThreadCountType, typename NType, typename RType>
1110 auto build_permutations(ThreadCountType thread_count, NType n, RType r)
1111 {
1112 using set_tag = tpf::set_tag<std::vector, short>;
1113 using set_t = tpf::set_t<set_tag>;
1114 using sets_t = tpf::sets_t<set_tag>;
1115
1116 set_t L; L.reserve(n);
1117 for(size_t i= 0; i < (size_t)n; ++i)
1118 L.emplace_back((short)i);
1119
1120 set_t R; R.reserve(n);
1121
1122 sets_t permutations;
1123
1124 tpf::thread_bundle tb;
1125 tb.max_thread_count = thread_count;
1126 tb.thread_count = 0;
1127
1128 tpf::sstream stream;
1129
1130 try
1131 {
1132 hidden::build_permutations(tb, permutations, L, R, r);
1133
1134 }catch(const std::exception& e)
1135 {
1136 stream << e << tpf::endl;
1137 }
1138 return permutations;
1139 }
1140
1141 template<typename NType, typename RType>
1142 auto build_permutations(NType n, RType r)
1143 {
1144 using set_tag = tpf::set_tag<std::vector, NType>;
1145 using set_t = tpf::set_t<set_tag>;
1146 using sets_t = tpf::sets_t<set_tag>;
1147
1148 set_t L; L.reserve(n);
1149 for(size_t i= 0; i < (size_t)n; ++i)
1150 L.emplace_back((NType)i);
1151
1152 set_t R; R.reserve(n);
1153
1154 sets_t permutations;
1155
1156 tpf::sstream stream;
1157
1158 try
1159 {
1160 hidden::build_permutations(permutations, L, R, r);
1161
1162 }catch(const std::exception& e)
1163 {
1164 stream << e << tpf::endl;
1165 }
1166 return permutations;
1167 }
1168
1169 template<typename NType, typename RType>
1170 auto build_permutations_remainder(NType n, RType r)
1171 {
1172 using set_tag = tpf::set_tag<std::vector, NType>;
1173 using set_t = tpf::set_t<set_tag>;
1174 using sets_t = tpf::sets_t<set_tag>;
1175
1176 set_t L; L.reserve(n);
1177 for(size_t i= 0; i < (size_t)n; ++i)
1178 L.emplace_back((NType)i);
1179
1180 set_t R; R.reserve(n);
1181
1182 sets_t permutations;
1183
1184 tpf::sstream stream;
1185
1186 try
1187 {
1188 hidden::build_permutations_remainder(permutations, L, R, r);
1189
1190 }catch(const std::exception& e)
1191 {
1192 stream << e << tpf::endl;
1193 }
1194 return permutations;
1195 }
1196
1198
1199 template<typename ThreadCountType, typename NType, typename RType>
1200 auto build_permutations_flat(ThreadCountType thread_count, NType n, RType r)
1201 {
1202 using set_tag = tpf::set_tag<std::vector, NType>;
1203 using set_t = tpf::set_t<set_tag>;
1204 using sets_t = tpf::sets_t<set_tag>;
1205
1206 set_t L; L.reserve(n);
1207 for(size_t i= 0; i < (size_t)n; ++i)
1208 L.emplace_back((NType)i);
1209
1210 set_t R; R.reserve(n);
1211
1212 tpf::thread_bundle tb;
1213 tb.max_thread_count = thread_count;
1214 tb.thread_count = 0;
1215
1216 tpf::sstream stream;
1217 try
1218 {
1219 hidden::build_permutations(tb, L, R);
1220
1221 }catch(const std::exception& e)
1222 {
1223 stream << e << tpf::endl;
1224 }
1225
1226 }
1227
1228 template<typename NType, typename RType>
1229 auto build_permutations_flat(NType n, RType r)
1230 {
1231 using set_tag = tpf::set_tag<std::vector, NType>;
1232 using set_t = tpf::set_t<set_tag>;
1233 using sets_t = tpf::sets_t<set_tag>;
1234
1235 set_t L; L.reserve(n);
1236 for(size_t i= 0; i < (size_t)n; ++i)
1237 L.emplace_back((NType)i);
1238
1239 set_t R; R.reserve(n);
1240
1241 tpf::sstream stream;
1242
1243 try
1244 {
1245 hidden::build_permutations(L, R);
1246
1247 }catch(const std::exception& e)
1248 {
1249 stream << e << tpf::endl;
1250 }
1251
1252 return R;
1253
1254 }
1255
1256 template<template<typename, typename...> class ContainerType,
1257 typename EleType, typename... Types>
1258 ContainerType<ContainerType<EleType, Types...>>
1259 build_subsets(const ContainerType<EleType, Types...>& S, size_t count = InvalidIndex)
1260 {
1261 using set_t = ContainerType<EleType>;
1262 using sets_t = ContainerType<ContainerType<EleType>>;
1263
1264 sets_t subsets;
1265
1266 if (count == 0 || S.empty())
1267 {
1268 subsets.emplace_back(set_t{});
1269 return subsets;
1270 }
1271
1272 constexpr size_t limit = std::numeric_limits<size_t>::max();
1273
1274 // generate all subsets
1275 if (count == limit)
1276 {
1277 // empty set
1278 subsets.emplace_back(set_t{});
1279 size_t size = S.size();
1280
1281 auto go_parallel = [&subsets, &S](auto i)
1282 {
1283 set_t R{};
1284 hidden::build_subsets(subsets, R, S, i);
1285 };
1286
1287 #if defined(_GLIBCXX_PARALLEL)
1288 #pragma omp parallel for
1289 for (size_t i = 1; i < size; ++i)
1290 {
1291 set_t R{};
1292 hidden::build_subsets(subsets, R, S, i);
1293 }
1294 #elif defined(_MSC_VER)
1295
1296 concurrency::parallel_for((size_t)1, size, go_parallel);
1297
1298 #elif defined(__ICL)
1299 tbb::parallel_for((size_t)1, size, go_parallel);
1300 #else
1301 for (size_t i = 1; i < size; ++i)
1302 {
1303 set_t R{};
1304 hidden::build_subsets(subsets, R, S, i);
1305 }
1306 #endif
1307 subsets.emplace_back(S);
1308 }
1309 else
1310 {
1311 assert(count <= S.size());
1312 set_t R{}; hidden::build_subsets(subsets, R, S, count);
1313 }
1314
1315 return subsets;
1316 }
1317
1318 // returns m_th subset by selecting r elements from
1319 // the set from_set with n elements (from_set.size())
1320 // std::deque<Type> ele should be in order
1321 // ele = { 0, 1, 2, 3 }
1322 template<template<typename, typename...> class ReturnContainer = std::vector,
1323 template<typename, typename...> class SetContainer = std::list, typename... ContainerTails,
1324 typename EleType = int, typename CountType = int>
1325 ReturnContainer<ReturnContainer<EleType>>
1326 enumerate_combination_with_exclude(
1327 SetContainer<EleType, ContainerTails...> exclude_set,
1328 SetContainer<EleType, ContainerTails...> from_set, CountType r)
1329 {
1330
1331 }
1332
1333 template<typename EleType, template<typename, typename...> class ContainerType, typename... Types>
1334 types::enable_if_container_type_t<ContainerType<EleType, Types...>, size_t>
1335 minimum_value_index(const ContainerType<EleType, Types...>& container)
1336 {
1337 if(container.empty()) return tpf::type_max_v<size_t>;
1338
1339 EleType minimum = tpf::type_max_v<EleType>;
1340
1341 auto iterator = container.cend();
1342
1343 for(auto itr = container.cbegin(); itr != container.cend(); std::advance(itr, 1))
1344 {
1345 if(*itr < minimum)
1346 {
1347 iterator = itr; minimum = *itr;
1348 }
1349 }
1350
1351 return (iterator != container.cend()) ?
1352 std::distance(container.cbegin(), iterator) : tpf::type_max_v<size_t>;
1353 }
1354
1355 template<typename EleType, typename IndexType, template<typename, typename...> class ContainerType, typename... Types>
1356 types::enable_if_container_type_t<ContainerType<EleType, Types...>, size_t>
1357 minimum_value_index(const ContainerType<EleType, Types...>& container,
1358 const std::vector<IndexType>& exclude_set)
1359 {
1360 if(container.empty()) return tpf::type_max_v<size_t>;
1361
1362 EleType minimum = tpf::type_max_v<EleType>;
1363
1364 auto iterator = container.cend();
1365
1366 for(auto itr = container.cbegin(); itr != container.cend(); std::advance(itr, 1))
1367 {
1368 auto index = std::distance(container.cbegin(), itr);
1369
1370 if(is_in_unsorted_container((IndexType)index, exclude_set)) continue;
1371
1372 if(*itr < minimum)
1373 {
1374 iterator = itr; minimum = *itr;
1375 }
1376 }
1377
1378 return (iterator != container.cend()) ?
1379 std::distance(container.cbegin(), iterator) : tpf::type_max_v<size_t>;
1380 }
1381
1382 } // end of namespace set
1383
1384} // end of namespace tpf
1385
1386#endif // end of file _TPF_SET_HPP
count
std::atomic< int > count
Definition: 022-mutex.cpp:10
go_parallel
void go_parallel(Policy &&policy, IteratorBegin &&begin, IteratorEnd &&end, Callback &&callback)
Definition: 030-premature_exit.cpp:123
parallel_for
bool parallel_for(CallbackType &&callback, PolicyType &&policy, BeginType begin_index, EndType end_index)
Definition: 045-parallel_for.cpp:17
is_same_v
constexpr auto is_same_v
Definition: 11-type_dispatch.cpp:82
enable_if_t
typename enable_if< predicate, ReturnType >::type enable_if_t
Definition: 12_sfinae.cpp:23
stream
tpf::sstream stream
Definition: apply_operations.cpp:31
tpf::output::string_stream
Definition: tpf_output.hpp:844
cpg::InvalidIndex
constexpr size_t InvalidIndex
Definition: cpg_types.hpp:219
tpf::set::hidden::build_subsets
void build_subsets(ContainerType< ContainerType< EleType, Types... >, OuterTypes... > &SS, ContainerType< EleType, Types... > R, ContainerType< EleType, Types... > S, size_t count)
Definition: tpf_set.hpp:606
tpf::set::hidden::build_permutations_remainder
void build_permutations_remainder(ContainerType< EleType, Types... > &L, ContainerType< EleType, Types... > &R, size_t r)
Definition: tpf_set.hpp:1060
tpf::set::hidden::build_permutations
void build_permutations(ContainerType< EleType, Types... > &L, ContainerType< EleType, Types... > &R, size_t r)
Definition: tpf_set.hpp:1015
tpf::set
Implements set operations.
Definition: tpf_set.hpp:52
tpf::set::union_in_place
std::enable_if_t< std::is_same_v< ContainerType< EleType, Types... >, remove_cv_ref_t< RightContainerType > > > union_in_place(ContainerType< EleType, Types... > &left, RightContainerType &&right)
Definition: tpf_set.hpp:449
tpf::set::build_permutations
auto build_permutations(ThreadCountType thread_count, NType n, RType r)
Definition: tpf_set.hpp:1110
tpf::set::operator>
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > operator>(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:267
tpf::set::is_sorted
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > is_sorted(const ContainerType< EleType, Types... > &container, sort_order order=sort_order::ascending, sort_method method=sort_method::size)
Definition: tpf_set.hpp:309
tpf::set::compare_less_equal_dictionary
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > compare_less_equal_dictionary(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:211
tpf::set::minimum_value_index
types::enable_if_container_type_t< ContainerType< EleType, Types... >, size_t > minimum_value_index(const ContainerType< EleType, Types... > &container)
Definition: tpf_set.hpp:1335
tpf::set::compare_less_size
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > compare_less_size(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:232
tpf::set::is_in_container
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > is_in_container(const EleType &ele, const ContainerType< EleType, Types... > &container)
Definition: tpf_set.hpp:288
tpf::set::count_of_subsets
constexpr auto count_of_subsets(Type element_count)
Definition: tpf_set.hpp:65
tpf::set::compare_sets_size
types::enable_if_container_type_t< ContainerType< EleType, Types... >, int > compare_sets_size(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:140
tpf::set::is_in_unsorted_container
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > is_in_unsorted_container(const EleType &ele, const ContainerType< EleType, Types... > &container)
Definition: tpf_set.hpp:295
tpf::set::operator!=
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > operator!=(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:197
tpf::set::intersection
ContainerType< EleType, Types... > intersection(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:537
tpf::set::build_subsets
ContainerType< ContainerType< EleType, Types... > > build_subsets(const ContainerType< EleType, Types... > &S, size_t count=InvalidIndex)
Definition: tpf_set.hpp:1259
tpf::set::compare_sets_dictionary
types::enable_if_container_type_t< ContainerType< EleType, Types... >, int > compare_sets_dictionary(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:96
tpf::set::compare_greater_equal_dictionary
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > compare_greater_equal_dictionary(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:225
tpf::set::union_sets
std::enable_if_t< std::is_same_v< ContainerType< EleType, Types... >, remove_cv_ref_t< RightContainerType > >, ContainerType< EleType, Types... > > union_sets(ContainerType< EleType, Types... > left, RightContainerType &&right)
Definition: tpf_set.hpp:493
tpf::set::difference
ContainerType< EleType, Types... > difference(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:573
tpf::set::compare_greater_equal_size
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > compare_greater_equal_size(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:253
tpf::set::compare_greater_dictionary
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > compare_greater_dictionary(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:218
tpf::set::compare_less_equal_size
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > compare_less_equal_size(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:239
tpf::set::compare_less_dictionary
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > compare_less_dictionary(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:204
tpf::set::smart_shrink_to_fit
types::enable_if_container_type_t< ContainerType< EleType, Types... >, void > smart_shrink_to_fit(ContainerType< EleType, Types... > &container, size_t factor=2)
Definition: tpf_set.hpp:72
tpf::set::enumerate_combination_with_exclude
ReturnContainer< ReturnContainer< EleType > > enumerate_combination_with_exclude(SetContainer< EleType, ContainerTails... > exclude_set, SetContainer< EleType, ContainerTails... > from_set, CountType r)
Definition: tpf_set.hpp:1326
tpf::set::operator>=
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > operator>=(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:281
tpf::set::sort
ContainerType< EleType > sort(ContainerType< EleType, Types... > container, sort_order order=sort_order::ascending, sort_method method=sort_method::size)
Definition: tpf_set.hpp:438
tpf::set::sort_in_place
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > sort_in_place(ContainerType< EleType, Types... > &container, sort_order order=sort_order::ascending, sort_method method=sort_method::size)
Definition: tpf_set.hpp:376
tpf::set::union_flat
ContainerType< EleType, Types1... > union_flat(const ContainerType< ContainerType< EleType, Types1... >, Types2... > &sets)
Definition: tpf_set.hpp:526
tpf::set::operator==
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > operator==(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:171
tpf::set::compare_greater_size
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > compare_greater_size(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:246
tpf::set::build_permutations_remainder
auto build_permutations_remainder(NType n, RType r)
Definition: tpf_set.hpp:1170
tpf::set::operator<
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > operator<(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:260
tpf::set::operator<=
types::enable_if_container_type_t< ContainerType< EleType, Types... >, bool > operator<=(const ContainerType< EleType, Types... > &left, const ContainerType< EleType, Types... > &right)
Definition: tpf_set.hpp:274
tpf::set::build_permutations_flat
auto build_permutations_flat(ThreadCountType thread_count, NType n, RType r)
Definition: tpf_set.hpp:1200
tpf::types::enable_if_container_type_t
hidden::enable_if_container_type_t< Type, ReturnType > enable_if_container_type_t
Definition: tpf_types.hpp:5564
tpf::types::pop_front
auto pop_front(ContainerType< Type, Types... > &container)
Definition: tpf_types.hpp:7034
tpf
Includes subnamespace conversion.
Definition: 31-visit.cpp:7
tpf::two_power_n
constexpr unsigned long long two_power_n(Type n)
Definition: tpf_types.hpp:254
tpf::minimum
auto minimum(Type_1 a, Type_2 b)
Definition: tpf_types.hpp:196
tpf::set_t
typename SetTagType::set_t set_t
Definition: tpf_types.hpp:1966
tpf::remove_cv_ref_t
std::remove_cv_t< std::remove_reference_t< Type > > remove_cv_ref_t
Remove const volatile reference from Type.
Definition: tpf_types.hpp:151
tpf::endl
constexpr auto endl
Definition: tpf_output.hpp:973
tpf::sets_t
typename SetTagType::sets_t sets_t
Definition: tpf_types.hpp:1969
tpf::set_tag
Definition: tpf_types.hpp:1939
tpf::thread_bundle
Definition: tpf_types.hpp:1637
tpf::thread_bundle::thread_count
std::atomic< int > thread_count
Definition: tpf_types.hpp:1639
tpf::thread_bundle::max_thread_count
int max_thread_count
Definition: tpf_types.hpp:1638
factor
constexpr int factor
Definition: stupid_experiment.cpp:22
thread_count
std::atomic< int > thread_count
Definition: stupid_experiment.cpp:26
tpf_ncrnpr.hpp
tpf_output.hpp
Stream output operators << are implemented.
tpf_types.hpp
Type functions are implemented.