kblib 0.2.3
General utilities library for modern C++
algorithm.h
Go to the documentation of this file.
1/* *****************************************************************************
2 * kblib is a general utility library for C++14 and C++17, intended to provide
3 * performant high-level abstractions and more expressive ways to do simple
4 * things.
5 *
6 * Copyright (c) 2021 killerbee
7 *
8 * This program is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 * ****************************************************************************/
21
32#ifndef ALGORITHM_H
33#define ALGORITHM_H
34
35#include "tdecl.h"
36
37#include "iterators.h"
38#include "traits.h"
39
40#include <algorithm>
41#include <cmath>
42#include <tuple>
43
44namespace KBLIB_NS {
45
52template <typename Callable>
53constexpr auto repeat(std::size_t N, Callable func) noexcept(noexcept(func()))
55 for (std::size_t I = 0; I != N; ++I) {
56 func();
57 }
58 return;
59}
60
67template <typename Container, typename Elem>
68constexpr auto erase(Container& c, const Elem& val) noexcept(
69 noexcept(c.erase(std::remove(c.begin(), c.end(), val), c.end()))) -> void {
70 c.erase(std::remove(c.begin(), c.end(), val), c.end());
71 return;
72}
73
80template <typename Container, typename UnaryPredicate>
81constexpr auto erase_if(Container& c, UnaryPredicate p) noexcept(
82 noexcept(c.erase(std::remove_if(c.begin(), c.end(), std::ref(p)), c.end())))
83 -> void {
84 c.erase(std::remove_if(c.begin(), c.end(), std::ref(p)), c.end());
85 return;
86}
87
93template <typename Obj>
94KBLIB_NODISCARD constexpr auto equals(const Obj& a,
95 const Obj& b) noexcept(noexcept(a < b))
96 -> bool {
97 return not (a < b) and not (b < a);
98}
99
105template <typename Obj, typename Compare>
106KBLIB_NODISCARD constexpr auto equals(const Obj& a, const Obj& b,
107 Compare comp) noexcept(noexcept(comp(a,
108 b)))
109 -> bool {
110 return not comp(a, b) and not comp(b, a);
111}
112
122template <typename Compare = void, typename Obj = void>
124 KBLIB_NODISCARD constexpr auto operator()(const Obj& a, const Obj& b,
125 Compare comp) const
126 noexcept(noexcept(equals(a, b, comp))) -> bool {
127 return equals(a, b, comp);
128 }
129};
130
131template <typename Obj>
132struct equivalent<void, Obj> {
133 KBLIB_NODISCARD constexpr auto operator()(const Obj& a, const Obj& b) const
134 noexcept(noexcept(equals(a, b))) -> bool {
135 return equals(a, b);
136 }
137};
138
139template <typename Compare>
140struct equivalent<Compare, void> {
141 template <typename Obj>
142 KBLIB_NODISCARD constexpr auto operator()(const Obj& a, const Obj& b,
143 Compare comp) const
144 noexcept(noexcept(equals(a, b, comp))) -> bool {
145 return equals(a, b, comp);
146 }
147};
148
149template <>
150struct equivalent<void, void> {
151 template <typename Obj>
152 KBLIB_NODISCARD constexpr auto operator()(const Obj& a, const Obj& b) const
153 noexcept(noexcept(equals(a, b))) -> bool {
154 return equals(a, b);
155 }
156};
157
161template <typename InputIt, typename T>
162KBLIB_NODISCARD constexpr auto accumulate(InputIt first, InputIt last, T init)
163 -> T {
164 for (; first != last; ++first) {
165 init = std::move(init) + *first;
166 }
167 return init;
168}
169
173template <class InputIt, class T, class BinaryOperation>
174KBLIB_NODISCARD constexpr auto accumulate(InputIt first, InputIt last, T init,
175 BinaryOperation op) -> T {
176 for (; first != last; ++first) {
177 init = op(std::move(init), *first);
178 }
179 return init;
180}
181
193template <typename InputIt>
194KBLIB_NODISCARD constexpr auto sum(InputIt first, InputIt last)
195 -> std::decay_t<decltype(*first)> {
196 if (first == last) {
197 return {};
198 }
199 auto init = *first++;
200 return kblib::accumulate(first, last, std::move(init));
201}
202
215template <typename InputIt, typename BinaryOperation>
216KBLIB_NODISCARD constexpr auto sum(InputIt first, InputIt last,
217 BinaryOperation op)
218 -> std::decay_t<decltype(*first)> {
219 if (first == last) {
220 return {};
221 }
222 auto init = *first++;
223 return kblib::accumulate(first, last, std::move(init), op);
224}
225
236template <typename Range>
237KBLIB_NODISCARD constexpr auto sum(Range&& r) -> auto {
238 using std::begin;
239 using std::end;
240 auto first = begin(r);
241 auto last = end(r);
242 if (first == last) {
243 return std::decay_t<decltype(*first)>{};
244 }
245 auto init = *first++;
246 return kblib::accumulate(first, last, std::move(init));
247}
248
249template <typename InputIt, typename EndIt, typename OutputIt, typename T,
250 typename BinaryAccumulation, typename UnaryTransform>
251constexpr auto transform_exclusive_scan(InputIt first, EndIt last,
252 OutputIt d_first, T init,
253 BinaryAccumulation accum,
254 UnaryTransform proj) -> OutputIt {
255 while (first != last) {
256 *d_first++
257 = kblib::exchange(init, accum(std::move(init), proj(*first++)));
258 }
259 return d_first;
260}
261
262#if 0
263template <typename InputIt, typename BinaryAccumulation,
264 typename BinaryTransform>
265KBLIB_NODISCARD constexpr auto
266adjacent_reduce(InputIt begin, InputIt begin1, InputIt end,
267 BinaryAccumulation acc, BinaryTransform op) {}
268
269template <typename InputIt, typename BinaryTransform>
270KBLIB_NODISCARD constexpr auto adjacent_transform(InputIt begin, InputIt begin1,
271 InputIt end,
272 BinaryTransform op) {}
273
274template <typename InputIt, typename BinaryAccumulation,
275 typename BinaryTransform>
276KBLIB_NODISCARD constexpr auto
277adjacent_inclusive_scan(InputIt begin, InputIt begin1, InputIt end,
278 BinaryAccumulation acc, BinaryTransform op) {}
279#endif
280
289template <typename ForwardIt, typename EndIt, typename Elem>
290KBLIB_NODISCARD constexpr auto find(
291 ForwardIt begin, EndIt end,
292 const Elem& value) noexcept(noexcept(*begin == value)) -> ForwardIt {
293 while (begin != end and *begin != value) {
294 ++begin;
295 }
296 return begin;
297}
298
308template <typename ForwardIt, typename EndIt, typename Elem, typename Comp>
309KBLIB_NODISCARD constexpr auto find(
310 ForwardIt begin, EndIt end, const Elem& value,
311 Comp&& comp) noexcept(noexcept(comp(*begin, value))) -> ForwardIt {
312 while (begin != end and not equals(*begin, value, comp)) {
313 ++begin;
314 }
315 return begin;
316}
317
326template <typename ForwardIt, typename EndIt, typename UnaryPredicate>
328 ForwardIt begin, EndIt end,
329 UnaryPredicate&& pred) noexcept(noexcept(kblib::invoke(pred, *begin)))
330 -> ForwardIt {
331 while (begin != end and not kblib::invoke(pred, *begin)) {
332 ++begin;
333 }
334 return begin;
335}
336
345template <typename ForwardIt, typename EndIt, typename UnaryPredicate>
347 ForwardIt begin, EndIt end,
348 UnaryPredicate&& pred) noexcept(noexcept(kblib::invoke(pred, *begin)))
349 -> ForwardIt {
350 while (begin != end and kblib::invoke(pred, *begin)) {
351 ++begin;
352 }
353 return begin;
354}
355
365template <typename ForwardIt, typename EndIt, typename Elem>
367 ForwardIt begin, EndIt end,
368 const Elem& value) noexcept(noexcept(*begin == value)) -> ForwardIt {
369 if (begin == end) {
370 return begin;
371 }
372 auto result = end;
373 while (true) {
374 auto new_result = kblib::find(begin, end, value);
375 if (new_result == end) {
376 break;
377 } else {
378 result = new_result;
379 begin = result;
380 ++begin;
381 }
382 }
383 return result;
384}
385
395template <typename ForwardIt, typename EndIt, typename UnaryPredicate>
397 ForwardIt begin, EndIt end,
398 UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin)))
399 -> ForwardIt {
400 if (begin == end) {
401 return begin;
402 }
403 auto result = end;
404 while (true) {
405 auto new_result = kblib::find_if(begin, end, pred);
406 if (new_result == end) {
407 break;
408 } else {
409 result = new_result;
410 begin = result;
411 ++begin;
412 }
413 }
414 return result;
415}
416
426template <typename ForwardIt, typename EndIt, typename UnaryPredicate>
428 ForwardIt begin, EndIt end,
429 UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin)))
430 -> ForwardIt {
431 if (begin == end) {
432 return begin;
433 }
434 auto result = end;
435 while (true) {
436 auto new_result = kblib::find_if_not(begin, end, pred);
437 if (new_result == end) {
438 break;
439 } else {
440 result = new_result;
441 begin = result;
442 ++begin;
443 }
444 }
445 return result;
446}
447
457template <typename ForwardIt, typename EndIt, typename Elem>
459 ForwardIt begin, EndIt end,
460 const Elem& value) noexcept(noexcept(*begin == value)) -> size_t {
461 return to_unsigned(kblib::find(begin, end, value) - begin);
462}
463
473template <typename ForwardIt, typename EndIt, typename UnaryPredicate>
475 ForwardIt begin, EndIt end,
476 UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin)))
477 -> size_t {
478 return to_unsigned(kblib::find_if(begin, end, pred) - begin);
479}
489template <typename ForwardIt, typename EndIt, typename UnaryPredicate>
491 ForwardIt begin, EndIt end,
492 UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin)))
493 -> size_t {
494 return to_unsigned(kblib::find_if_not(begin, end, pred) - begin);
495}
496
497// find_last_in:
498// 1. Finds last v in range [begin, end) and returns the offset from begin
499
509template <typename ForwardIt, typename EndIt, typename Elem>
511 ForwardIt begin, EndIt end,
512 const Elem& value) noexcept(noexcept(*begin == value)) -> size_t {
513 return to_unsigned(kblib::find_last(begin, end, value) - begin);
514}
515
524template <typename ForwardIt, typename EndIt, typename UnaryPredicate>
526 ForwardIt begin, EndIt end,
527 UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin)))
528 -> size_t {
529 return to_unsigned(kblib::find_last_if(begin, end, pred) - begin);
530}
540template <typename ForwardIt, typename EndIt, typename UnaryPredicate>
542 ForwardIt begin, EndIt end,
543 UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin)))
544 -> size_t {
545 return to_unsigned(kblib::find_last_if_not(begin, end, pred) - begin);
546}
547
557template <typename Container, typename T>
558KBLIB_NODISCARD constexpr auto
559find_in(const Container& c, const T& value) noexcept(
560 noexcept(*std::declval<iterator_type_for_t<const Container>&>() == value))
561 -> size_t {
562 using std::begin;
563 using std::end;
564 return to_unsigned(kblib::find(begin(c), end(c), value) - begin(c));
565}
566#if 0
567template<typename ExecutionPolicy, typename Container, typename T>
568KBLIB_NODISCARD constexpr auto find_in(ExecutionPolicy&& policy,
569 const Container& c, const T& v) -> size_t {
570 return to_unsigned(std::find(policy, std::begin(c), std::end(c), v) - std::begin(c));
571}
572#endif
573
584template <typename Container, typename UnaryPredicate>
586 const Container& c,
587 UnaryPredicate
588 pred) noexcept(noexcept(kblib::invoke(pred,
589 *std::declval<iterator_type_for_t<
590 const Container>&>())))
591 -> size_t {
592 using std::begin;
593 using std::end;
594 return to_unsigned(kblib::find_if(begin(c), end(c), pred) - begin(c));
595}
606template <typename Container, typename UnaryPredicate>
608 const Container& c,
609 UnaryPredicate
610 pred) noexcept(noexcept(kblib::invoke(pred,
611 *std::declval<iterator_type_for_t<
612 const Container>&>())))
613 -> size_t {
614 using std::begin;
615 using std::end;
616 return to_unsigned(kblib::find_if_not(begin(c), end(c), pred) - begin(c));
617}
618#if 0
619template<typename ExecutionPolicy, typename Container, typename UnaryPredicate>
620KBLIB_NODISCARD constexpr auto find_in_if(ExecutionPolicy&& policy,
621 const Container& c,
622 UnaryPredicate p) -> size_t {
623 return std::find_if(policy, std::begin(c), std::end(c), p) - std::begin(c);
624}
625template<typename ExecutionPolicy, typename Container, typename UnaryPredicate>
626KBLIB_NODISCARD constexpr auto find_in_if_not(ExecutionPolicy&& policy,
627 const Container& c,
628 UnaryPredicate p) -> size_t {
629 return std::find_if_not(policy, std::begin(c), std::end(c), p)
630 - std::begin(c);
631}
632#endif
633
643template <typename Container, typename T>
644KBLIB_NODISCARD constexpr auto
645find_last_in(const Container& c, const T& value) noexcept(
646 noexcept(*std::declval<iterator_type_for_t<const Container>&>() == value))
647 -> size_t {
648 using std::begin;
649 using std::end;
650 return to_unsigned(kblib::find_last(begin(c), end(c), value) - begin(c));
651}
652
663template <typename Container, typename UnaryPredicate>
665 const Container& c,
666 UnaryPredicate
667 pred) noexcept(noexcept(kblib::invoke(pred,
668 *std::declval<iterator_type_for_t<
669 const Container>&>())))
670 -> size_t {
671 using std::begin;
672 using std::end;
673 return to_unsigned(kblib::find_last_if(begin(c), end(c), pred) - begin(c));
674}
685template <typename Container, typename UnaryPredicate>
687 const Container& c,
688 UnaryPredicate
689 pred) noexcept(noexcept(kblib::invoke(pred,
690 *std::declval<iterator_type_for_t<
691 const Container>&>())))
692 -> size_t {
693 using std::begin;
694 using std::end;
695 return to_unsigned(kblib::find_last_if_not(begin(c), end(c), pred)
696 - begin(c));
697}
698
699template <typename InputIt1, typename EndIt1, typename InputIt2,
700 typename BinaryPredicate = std::equal_to<>>
701KBLIB_NODISCARD constexpr auto find_match(InputIt1 begin1, EndIt1 end1,
702 InputIt2 begin2, BinaryPredicate cmp)
705 and is_invocable<BinaryPredicate, decltype(*begin1),
706 decltype(*begin2)>::value,
707 std::pair<InputIt1, InputIt2>> {
708 while (begin1 != end1) {
709 if (kblib::invoke(cmp, *begin1++, *begin2++)) {
710 return std::make_pair(begin1, begin2);
711 }
712 }
713 return std::make_pair(begin1, begin2);
714}
715template <typename InputIt1, typename EndIt1, typename InputIt2,
716 typename EndIt2, typename BinaryPredicate = std::equal_to<>>
717KBLIB_NODISCARD constexpr auto find_match(InputIt1 begin1, EndIt1 end1,
718 InputIt2 begin2, EndIt2 end2,
719 BinaryPredicate cmp)
722 and is_invocable<BinaryPredicate, decltype(*begin1),
723 decltype(*begin2)>::value,
724 std::pair<InputIt1, InputIt2>> {
725 while (begin1 != end1 and begin2 != end2) {
726 if (kblib::invoke(cmp, *begin1++, *begin2++)) {
727 return std::make_pair(begin1, begin2);
728 }
729 }
730 return std::make_pair(begin1, begin2);
731}
732
736template <typename InputIt1, typename EndIt1, typename InputIt2,
737 typename EndIt2, typename BinaryPred>
738KBLIB_NODISCARD constexpr auto starts_with(InputIt1 begin1, EndIt1 end1,
739 InputIt2 begin2, EndIt2 end2,
740 BinaryPred pred)
741 -> enable_if_t<
742 (is_input_iterator_v<InputIt1> and is_input_iterator_v<InputIt2>) //
744 InputIt1> and is_random_access_iterator_v<InputIt2>),
745 bool> {
746 while (begin1 != end1 and begin2 != end2) {
747 if (not kblib::invoke(pred, *begin1++, *begin2++)) {
748 return false;
749 }
750 }
751 return begin2 == end2;
752}
753
757template <typename RandomAccessIt1, typename RandomAccessIt2,
758 typename BinaryPred = std::equal_to<>>
759KBLIB_NODISCARD constexpr auto starts_with(RandomAccessIt1 begin1,
760 RandomAccessIt1 end1,
761 RandomAccessIt2 begin2,
762 RandomAccessIt2 end2,
763 BinaryPred pred = {})
764 -> enable_if_t<
766 RandomAccessIt1> and is_random_access_iterator_v<RandomAccessIt2>,
767 bool> {
768 if (end2 - begin2 > end1 - begin1) {
769 return false;
770 } else {
771 auto N = end2 - begin2;
772 return kblib::equal(begin1, begin1 + N, begin2, pred);
773 }
774}
775
779template <typename BidirIt1, typename BidirIt2,
780 typename BinaryPred = std::equal_to<>>
781KBLIB_NODISCARD constexpr auto ends_with(BidirIt1 begin1, BidirIt1 end1,
782 BidirIt2 begin2, BidirIt2 end2,
783 BinaryPred pred = {})
784 -> enable_if_t<
785 (is_bidirectional_iterator_v<BidirIt1> //
786 and is_bidirectional_iterator_v<BidirIt2>) //
788 BidirIt1> and is_random_access_iterator_v<BidirIt2>),
789 bool> {
790 while (begin1 != end1 and begin2 != end2) {
791 if (not kblib::invoke(pred, *--end1, *--end2)) {
792 return false;
793 }
794 }
795 return begin2 == end2;
796}
797
801template <typename RandomAccessIt1, typename RandomAccessIt2,
802 typename BinaryPred = std::equal_to<>>
803KBLIB_NODISCARD constexpr auto ends_with(RandomAccessIt1 begin1,
804 RandomAccessIt1 end1,
805 RandomAccessIt2 begin2,
806 RandomAccessIt2 end2,
807 BinaryPred pred = {})
808 -> enable_if_t<
810 RandomAccessIt1> and is_random_access_iterator_v<RandomAccessIt2>,
811 bool> {
812 if (end2 - begin2 > end1 - begin1) {
813 return false;
814 } else {
815 auto N = end2 - begin2;
816 return kblib::equal(end1 - N, end1, begin2, pred);
817 }
818}
819
820template <typename InputIt, typename EndIt, typename T, typename UnaryTransform>
821KBLIB_NODISCARD constexpr auto first_result(InputIt begin, EndIt end, T def,
822 UnaryTransform op)
824 std::decay_t<decltype(op(*begin))>> {
825 for (; begin != end; ++begin) {
826 auto cur = op(*begin);
827 if (cur != def) {
828 return cur;
829 }
830 }
831 return def;
832}
833template <typename InputIt1, typename EndIt1, typename InputIt2, typename T,
834 typename BinaryTransform>
835KBLIB_NODISCARD constexpr auto first_result(InputIt1 begin1, EndIt1 end1,
836 InputIt2 begin2, T def,
837 BinaryTransform op)
840 std::decay_t<decltype(op(*begin1, *begin2))>> {
841 for (; begin1 != end1; ++begin1, ++begin2) {
842 auto cur = op(*begin1, *begin2);
843 if (cur != def) {
844 return cur;
845 }
846 }
847 return def;
848}
849template <typename InputIt1, typename EndIt1, typename InputIt2,
850 typename EndIt2, typename T, typename BinaryTransform>
851KBLIB_NODISCARD constexpr auto first_result(InputIt1 begin1, EndIt1 end1,
852 InputIt2 begin2, EndIt2 end2, T def,
853 BinaryTransform op)
856 std::decay_t<decltype(op(*begin1, *begin2))>> {
857 for (; begin1 != end1 and begin2 != end2; ++begin1, ++begin2) {
858 auto cur = op(*begin1, *begin2);
859 if (cur != def) {
860 return cur;
861 }
862 }
863 return def;
864}
865
866template <typename InputIt, typename EndIt, typename T, typename UnaryTransform,
867 typename UnaryPredicate>
868KBLIB_NODISCARD constexpr auto first_result_if(InputIt begin, EndIt end, T def,
869 UnaryTransform op,
870 UnaryPredicate ch)
871 -> enable_if_t<is_input_iterator<InputIt>::value, decltype(op(*begin))> {
872 for (; begin != end; ++begin) {
873 if (ch(*begin)) {
874 return op(*begin);
875 }
876 }
877 return def;
878}
879template <typename InputIt1, typename EndIt1, typename InputIt2, typename T,
880 typename BinaryTransform, typename BinaryPredicate>
881KBLIB_NODISCARD constexpr auto first_result_if(InputIt1 begin1, EndIt1 end1,
882 InputIt2 begin2, T def,
883 BinaryTransform op,
884 BinaryPredicate ch)
887 decltype(op(*begin1, *begin2))> {
888 for (; begin1 != end1; ++begin1, ++begin2) {
889 if (ch(*begin1, *begin2)) {
890 return op(*begin1, *begin2);
891 }
892 }
893 return def;
894}
895template <typename InputIt1, typename EndIt1, typename InputIt2,
896 typename EndIt2, typename T, typename BinaryTransform,
897 typename BinaryPredicate>
898KBLIB_NODISCARD constexpr auto first_result_if(InputIt1 begin1, EndIt1 end1,
899 InputIt2 begin2, EndIt2 end2,
900 T def, BinaryTransform op,
901 BinaryPredicate ch)
904 decltype(op(*begin1, *begin2))> {
905 for (; begin1 != end1 and begin2 != end2; ++begin1, ++begin2) {
906 if (ch(*begin1, *begin2)) {
907 return op(*begin1, *begin2);
908 }
909 }
910 return def;
911}
912
913#if KBLIB_USE_CXX17
914template <typename T>
915struct is_optional : std::false_type {};
916template <typename U>
917struct is_optional<std::optional<U>> : std::true_type {};
918
919template <typename InputIt, typename EndIt, typename T, typename UnaryTransform>
920KBLIB_NODISCARD constexpr auto first_result_opt(InputIt begin, EndIt end, T def,
921 UnaryTransform op)
923 std::decay_t<decltype(op(*begin))>> {
924 for (; begin != end; ++begin) {
925 auto cur = op(*begin);
926 if (cur) {
927 return cur;
928 }
929 }
930 return def;
931}
932template <typename InputIt1, typename EndIt1, typename InputIt2, typename T,
933 typename BinaryTransform>
934KBLIB_NODISCARD constexpr auto first_result_opt(InputIt1 begin1, EndIt1 end1,
935 InputIt2 begin2, T def,
936 BinaryTransform op)
939 std::decay_t<decltype(op(*begin1, *begin2))>> {
940 for (; begin1 != end1; ++begin1, ++begin2) {
941 auto cur = op(*begin1, *begin2);
942 if (cur) {
943 return cur;
944 }
945 }
946 return def;
947}
948template <typename InputIt1, typename EndIt1, typename InputIt2,
949 typename EndIt2, typename T, typename BinaryTransform>
950KBLIB_NODISCARD constexpr auto first_result_opt(InputIt1 begin1, EndIt1 end1,
951 InputIt2 begin2, EndIt2 end2,
952 T def, BinaryTransform op)
955 std::decay_t<decltype(op(*begin1, *begin2))>> {
956 for (; begin1 != end1 and begin2 != end2; ++begin1, ++begin2) {
957 auto cur = op(*begin1, *begin2);
958 if (cur) {
959 return cur;
960 }
961 }
962 return def;
963}
964#endif
965
969template <typename InputIt, typename UnaryPredicate>
970KBLIB_NODISCARD constexpr auto all_of(InputIt begin, InputIt end,
971 UnaryPredicate pred)
973 for (; begin != end; ++begin) {
974 if (not kblib::invoke(pred, *begin)) {
975 return false;
976 }
977 }
978 return true;
979}
983template <typename Range, typename UnaryPredicate>
984KBLIB_NODISCARD constexpr auto all_of(Range&& rng, UnaryPredicate pred)
986 for (auto&& el : std::forward<Range>(rng)) {
987 if (not kblib::invoke(pred, static_cast<decltype(el)>(el))) {
988 return false;
989 }
990 }
991 return true;
992}
996template <typename InputIt, typename UnaryPredicate>
997KBLIB_NODISCARD constexpr auto none_of(InputIt begin, InputIt end,
998 UnaryPredicate pred)
1000 for (; begin != end; ++begin) {
1001 if (kblib::invoke(pred, *begin)) {
1002 return false;
1003 }
1004 }
1005 return true;
1006}
1010template <typename Range, typename UnaryPredicate>
1011KBLIB_NODISCARD constexpr auto none_of(Range&& rng, UnaryPredicate pred)
1013 for (auto&& el : std::forward<Range>(rng)) {
1014 if (kblib::invoke(pred, static_cast<decltype(el)>(el))) {
1015 return false;
1016 }
1017 }
1018 return true;
1019}
1023template <typename InputIt, typename UnaryPredicate>
1024KBLIB_NODISCARD constexpr auto any_of(InputIt begin, InputIt end,
1025 UnaryPredicate pred)
1027 for (; begin != end; ++begin) {
1028 if (kblib::invoke(pred, *begin)) {
1029 return true;
1030 }
1031 }
1032 return false;
1033}
1037template <typename Range, typename UnaryPredicate>
1038KBLIB_NODISCARD constexpr auto any_of(Range&& rng, UnaryPredicate pred)
1040 for (auto&& el : std::forward<Range>(rng)) {
1041 if (kblib::invoke(pred, static_cast<decltype(el)>(el))) {
1042 return true;
1043 }
1044 }
1045 return false;
1046}
1047
1051template <typename InputIt, typename Value>
1053 InputIt begin, InputIt end,
1054 const Value& val) noexcept(noexcept(*begin == val))
1056 return kblib::any_of(begin, end, [&](const auto& e) { return e == val; });
1057}
1058
1062template <typename Set, typename Value>
1064 const Set& set,
1065 const Value&
1066 val) noexcept(noexcept(*std::declval<iterator_type_for_t<const Set>&>()
1067 == val))
1069 using std::begin;
1070 using std::end;
1071 return kblib::any_of(begin(set), end(set),
1072 [&](const auto& e) { return e == val; });
1073}
1074
1075template <typename InputIt1, typename InputIt2>
1076KBLIB_NODISCARD constexpr auto contains_any(InputIt1 begin, InputIt1 end,
1077 InputIt2 n_begin, InputIt2 n_end)
1080 bool> {
1081 return kblib::any_of(begin, end, [=](const auto& v) {
1082 return kblib::contains(n_begin, n_end, v);
1083 });
1084}
1085
1086template <typename InputIt, typename Range2>
1087KBLIB_NODISCARD constexpr auto contains_any(InputIt begin, InputIt end,
1088 Range2&& needle)
1091 bool> {
1092 return kblib::any_of(begin, end, [&needle](const auto& v) {
1093 return kblib::contains(needle, v);
1094 });
1095}
1096
1097template <typename Range1, typename Range2>
1098KBLIB_NODISCARD constexpr auto contains_any(Range1&& haystack, Range2&& needle)
1100 bool> {
1101 using std::begin;
1102 using std::end;
1103 return kblib::any_of(
1104 begin(haystack), end(haystack),
1105 [&needle](const auto& v) { return kblib::contains(needle, v); });
1106}
1107
1108template <typename ForwardIt, typename EndIt, typename Compare = std::less<>>
1109constexpr auto max_element(ForwardIt first, EndIt last, Compare comp = {})
1110 -> ForwardIt {
1111 if (first == last) {
1112 return first;
1113 }
1114
1115 ForwardIt largest = first;
1116 ++first;
1117 for (; first != last; ++first) {
1118 if (comp(*largest, *first)) {
1119 largest = first;
1120 }
1121 }
1122 return largest;
1123}
1124
1144template <typename SequenceContainer, typename Comp = std::less<>, typename It,
1145 enable_if_t<is_linear_container_v<SequenceContainer>, int> = 0>
1146KBLIB_NODISCARD constexpr auto get_max_n_old(It first, It last,
1147 std::size_t count, Comp cmp = {})
1148 -> SequenceContainer {
1149 using std::begin;
1150 using std::end;
1151 assert(first + count <= last);
1152 SequenceContainer c{first, first + count};
1153 std::for_each(first + count, last, [&](const auto& v) {
1154 auto& min_v = *std::min_element(begin(c), end(c), cmp);
1155 if (kblib::invoke(cmp, min_v, v)) {
1156 min_v = v;
1157 }
1158 });
1159 return c;
1160}
1161
1178template <typename SetlikeContainer, typename Comp = std::less<>, typename It,
1179 enable_if_t<is_setlike_v<SetlikeContainer>, int> = 0>
1180KBLIB_NODISCARD constexpr auto get_max_n_old(It first, It last,
1181 std::size_t count, Comp cmp = {})
1182 -> SetlikeContainer {
1183 auto temp = get_max_n_old<std::vector<key_type_setlike_t<SetlikeContainer>>>(
1184 first, last, count, cmp);
1185 return SetlikeContainer{std::make_move_iterator(temp.begin()),
1186 std::make_move_iterator(temp.end())};
1187}
1188
1201template <typename SequenceContainer, typename Comp = std::less<>, typename It,
1202 enable_if_t<is_linear_container_v<SequenceContainer>, int> = 0>
1203KBLIB_NODISCARD constexpr auto get_max_n(It first, It last, std::size_t count,
1204 Comp cmp = {}) -> SequenceContainer {
1205 using std::begin;
1206 using std::end;
1207 SequenceContainer c(count);
1208 std::partial_sort_copy(first, last, begin(c), end(c),
1209 [&](auto&& a, auto&& b) -> decltype(auto) {
1210 return kblib::invoke(cmp,
1211 std::forward<decltype(b)>(b),
1212 std::forward<decltype(a)>(a));
1213 });
1214 return c;
1215}
1216
1228template <typename SetlikeContainer, typename Comp = std::less<>, typename It,
1229 enable_if_t<is_setlike_v<SetlikeContainer>, int> = 0>
1230KBLIB_NODISCARD constexpr auto get_max_n(It first, It last, std::size_t count,
1231 Comp cmp = {}) -> SetlikeContainer {
1232 auto temp = get_max_n<std::vector<key_type_setlike_t<SetlikeContainer>>>(
1233 first, last, count, cmp);
1234 return SetlikeContainer{std::make_move_iterator(temp.begin()),
1235 std::make_move_iterator(temp.end())};
1236}
1237
1255template <typename Comp = std::less<>, typename InputIt, typename OutputIt,
1256 typename Elem = typename std::iterator_traits<InputIt>::value_type>
1257constexpr auto get_max_n(InputIt first, InputIt last, OutputIt d_begin,
1258 std::size_t count, Comp cmp = {})
1259 -> return_assert_t<is_output_iterator_for<OutputIt, Elem>::value,
1260 OutputIt> {
1261 auto temp = get_max_n<std::vector<Elem>>(first, last, count, cmp);
1262 return std::move(temp.begin(), temp.end(), d_begin);
1263}
1264
1278template <typename ForwardIt, typename EndIt, typename ForwardIt2,
1279 typename BinaryFunction>
1280constexpr auto for_each(ForwardIt first, EndIt last, ForwardIt2 second,
1281 BinaryFunction f) -> BinaryFunction {
1282 for (; first != last; (void)++first, (void)++second) {
1283 kblib::invoke(f, *first, *second);
1284 }
1285 return std::move(f);
1286}
1287
1299template <typename ForwardIt, typename ForwardIt2, typename Size,
1300 typename BinaryFunction>
1301constexpr auto for_each_n(ForwardIt first, Size n, ForwardIt2 second,
1302 BinaryFunction f)
1303 -> std::pair<ForwardIt, ForwardIt2> {
1304 for (Size i = 0; i < n; (void)++first, (void)++second, (void)++i) {
1305 kblib::invoke(f, *first, *second);
1306 }
1307 return {first, second};
1308}
1309
1321template <typename InputIt, typename EndIt, typename OutputIt>
1322constexpr auto copy(InputIt first, EndIt last, OutputIt out) -> OutputIt {
1323 while (first != last) {
1324 *out++ = *first++;
1325 }
1326 return out;
1327}
1328
1341template <typename InputIt, typename EndIt, typename OutputIt,
1342 typename UnaryPredicate>
1343constexpr auto copy_if(InputIt first, EndIt last, OutputIt out,
1344 UnaryPredicate pred) -> OutputIt {
1345 while (first != last) {
1346 if (kblib::invoke(pred, *first)) {
1347 *out++ = *first;
1348 }
1349 first++;
1350 }
1351 return out;
1352}
1353
1364template <typename InputIt, typename Size, typename OutputIt>
1365constexpr auto copy_n(InputIt first, Size count, OutputIt out) -> OutputIt {
1366 for (Size i = 0; i < count; ++i) {
1367 *out++ = *first++;
1368 }
1369 return out;
1370}
1371
1384template <typename InputIt, typename Size, typename OutputIt,
1385 typename UnaryPredicate>
1386constexpr auto copy_n_if(InputIt first, Size count, OutputIt out,
1387 UnaryPredicate pred) -> OutputIt {
1388 for (Size i = 0; i < count; ++i) {
1389 if (kblib::invoke(pred, *first)) {
1390 *out++ = *first;
1391 }
1392 ++first;
1393 }
1394 return out;
1395}
1396
1411template <typename InputIt, typename EndIt, typename OutputIt,
1412 typename UnaryPredicate, typename T>
1413constexpr auto replace_copy_if(InputIt first, EndIt last, OutputIt out,
1414 UnaryPredicate pred, const T& new_value)
1415 -> OutputIt {
1416 while (first != last) {
1417 if (kblib::invoke(pred, *first)) {
1418 *out = *first;
1419 } else {
1420 *out = new_value;
1421 }
1422 ++first;
1423 ++out;
1424 }
1425 return out;
1426}
1427
1442template <typename InputIt, typename Size, typename OutputIt,
1443 typename UnaryPredicate, typename T>
1444constexpr auto replace_copy_n_if(InputIt first, Size count, OutputIt out,
1445 UnaryPredicate pred, const T& new_value)
1446 -> OutputIt {
1447 for (Size i = 0; i < count; ++i) {
1448 if (kblib::invoke(pred, *first)) {
1449 *out = *first;
1450 } else {
1451 *out = new_value;
1452 }
1453 ++first;
1454 ++out;
1455 }
1456 return out;
1457}
1458
1459// TODO(killerbee13): Debug and test search_replace_copy
1460template <typename ForwardIt1, typename ForwardIt2, typename ForwardIt3,
1461 typename OutputIt, typename BinaryPredicate = std::equal_to<>>
1462constexpr auto search_replace_copy(ForwardIt1 h_begin, ForwardIt1 h_end,
1463 ForwardIt2 n_begin, ForwardIt2 n_end,
1464 ForwardIt3 r_begin, ForwardIt3 r_end,
1465 OutputIt d_begin,
1466 BinaryPredicate Compare = {}) -> OutputIt {
1467 if (n_begin == n_end) {
1468 return copy(h_begin, h_end, d_begin);
1469 } else {
1470 const auto needle_length = std::distance(n_begin, n_end);
1471 while (h_begin != h_end) {
1472 const auto found
1473 = std::search(h_begin, h_end, n_begin, n_end, Compare);
1474 d_begin = kblib::copy(h_begin, found, d_begin);
1475 h_begin = found;
1476 if (h_begin != h_end) {
1477 d_begin = copy(r_begin, r_end, d_begin);
1478 std::advance(h_begin, needle_length);
1479 }
1480 }
1481 return d_begin;
1482 }
1483}
1484
1485template <typename Haystack, typename Needle, typename Replacement,
1486 typename OutputIt, typename BinaryPredicate = std::equal_to<>>
1487constexpr auto search_replace_copy(Haystack&& haystack, Needle&& needle,
1488 Replacement&& replacement, OutputIt d_begin,
1489 BinaryPredicate compare = {}) {
1490 using std::begin;
1491 using std::end;
1492 return search_replace_copy(begin(haystack), end(haystack), //
1493 begin(needle), end(needle), //
1494 begin(replacement), end(replacement), //
1495 d_begin, //
1496 compare);
1497}
1498
1508template <class ForwardIt>
1509constexpr auto rotate(ForwardIt first, ForwardIt n_first,
1510 ForwardIt last) noexcept(noexcept(swap(*first, *first)))
1511 -> ForwardIt {
1512 if (first == n_first)
1513 return last;
1514 if (n_first == last)
1515 return first;
1516
1517 ForwardIt read = n_first;
1518 ForwardIt write = first;
1519 ForwardIt next_read = first; // read position for when "read" hits "last"
1520
1521 while (read != last) {
1522 if (write == next_read)
1523 next_read = read; // track where "first" went
1524 // iter_swap is not constexpr
1525 // std::iter_swap(write++, read++);
1526 swap(*(write++), *(read++));
1527 }
1528
1529 // rotate the remaining sequence into place
1530 kblib::rotate(write, next_read, last);
1531 return write;
1532}
1533
1544template <typename OutputIt, typename EndIt, typename Generator>
1545constexpr auto generate(OutputIt first, EndIt last,
1546 Generator g) noexcept(noexcept(*++first = g()))
1547 -> OutputIt {
1548 while (first != last) {
1549 *first = g();
1550 ++first;
1551 }
1552 return first;
1553}
1554
1564template <typename OutputIt, typename Size, typename Generator>
1565constexpr auto generate_n(OutputIt first, Size count,
1566 Generator g) noexcept(noexcept(*first++ = g()))
1567 -> OutputIt {
1568 for (Size i = 0; i < count; i++) {
1569 *first++ = g();
1570 }
1571 return first;
1572}
1573
1574template <typename ForwardIt, typename T>
1575constexpr auto iota(ForwardIt first, ForwardIt last, T value) noexcept(
1576 noexcept(*first++ = value) and noexcept(++value)) -> void {
1577 while (first != last) {
1578 *first++ = value;
1579 ++value;
1580 }
1581}
1582
1583// For some reason these long noexcept specifications really trip
1584// up clang-format
1585// clang-format off
1586template <typename ForwardIt, typename T, typename UnaryOperation>
1587constexpr auto iota(
1588 ForwardIt first, ForwardIt last, T value,
1589 UnaryOperation unary_op
1590 ) noexcept(noexcept(*first++ = value)
1591 and noexcept(kblib::invoke(unary_op,
1592 std::move(value))))
1593 -> void {
1594 // clang-format on
1595 while (first != last) {
1596 *first++ = value;
1597 value = kblib::invoke(unary_op, std::move(value));
1598 }
1599}
1600
1601// clang-format off
1602template <typename InputIt, typename EndIt, typename... Params>
1603constexpr auto call_each(
1604 InputIt first, EndIt last, Params&&... params
1605 ) noexcept(noexcept(kblib::invoke(*first++,
1606 std::forward<Params>(params)...)))
1607 -> InputIt {
1608 // clang-format on
1609 while (first != last) {
1610 kblib::invoke(*first++, std::forward<Params>(params)...);
1611 }
1612 return first;
1613}
1614
1630template <typename InputIt, typename EndIt, typename OutputIt,
1631 typename UnaryOperation>
1632constexpr auto transform(InputIt first, EndIt last, OutputIt d_first,
1633 UnaryOperation unary_op) -> OutputIt {
1634 while (first != last) {
1635 *d_first++ = kblib::invoke(unary_op, *first);
1636 ++first;
1637 }
1638 return d_first;
1639}
1640
1657template <typename InputIt, typename EndIt, typename InputIt2,
1658 typename OutputIt, typename BinaryOperation>
1659constexpr auto transform(InputIt first, EndIt last, InputIt first2,
1660 OutputIt d_first, BinaryOperation binary_op)
1661 -> OutputIt {
1662 while (first != last) {
1663 *d_first++ = kblib::invoke(binary_op, *first, *first2);
1664 ++first;
1665 ++first2;
1666 }
1667 return d_first;
1668}
1669
1688template <typename InputIt, typename EndIt, typename OutputIt,
1689 typename UnaryPredicate, typename UnaryOperation>
1690constexpr auto transform_if(InputIt first, EndIt last, OutputIt d_first,
1691 UnaryPredicate pred, UnaryOperation unary_op)
1692 -> OutputIt {
1693 while (first != last) {
1694 if (kblib::invoke(pred, *first)) {
1695 *d_first++ = kblib::invoke(unary_op, *first);
1696 }
1697 ++first;
1698 }
1699 return d_first;
1700}
1701
1702namespace detail_algorithm {
1703
1713 template <class ForwardIt>
1714 constexpr auto shift_backward(
1715 ForwardIt first, ForwardIt n_first,
1716 ForwardIt last) noexcept(noexcept(*first = std::move(*first))) -> void {
1717 if (first == n_first or n_first == last)
1718 return;
1719
1720 ForwardIt read = n_first;
1721 ForwardIt write = first;
1722
1723 while (read != last) {
1724 *(write++) = std::move(*(read++));
1725 }
1726
1727 return;
1728 }
1729
1730} // namespace detail_algorithm
1731
1732} // namespace KBLIB_NS
1733
1734#endif // ALGORITHM_H
This file provides some iterators, ranges, iterator/range adapters, and operations that can be perfor...
constexpr auto shift_backward(ForwardIt first, ForwardIt n_first, ForwardIt last) noexcept(noexcept(*first=std::move(*first))) -> void
Implementation function for insertion_sort_copy. Like std::move(begin, end, d_begin) but using the in...
Definition: algorithm.h:1714
constexpr auto call_each(InputIt first, EndIt last, Params &&... params) noexcept(noexcept(kblib::invoke(*first++, std::forward< Params >(params)...))) -> InputIt
Definition: algorithm.h:1603
constexpr auto contains(const Set &set, const Value &val) noexcept(noexcept(*std::declval< iterator_type_for_t< const Set > & >()==val)) -> enable_if_t< is_iterable< Set >::value, bool >
Determine if a range contains a value.
Definition: algorithm.h:1063
constexpr auto find_last_in(const Container &c, const T &value) noexcept(noexcept(*std::declval< iterator_type_for_t< const Container > & >()==value)) -> size_t
Find the last element in c equal to v and return the position.
Definition: algorithm.h:645
constexpr auto contains(InputIt begin, InputIt end, const Value &val) noexcept(noexcept(*begin==val)) -> enable_if_t< is_input_iterator< InputIt >::value, bool >
Determine if a range contains a value.
Definition: algorithm.h:1052
constexpr auto get_max_n(InputIt first, InputIt last, OutputIt d_begin, std::size_t count, Comp cmp={}) -> return_assert_t< is_output_iterator_for< OutputIt, Elem >::value, OutputIt >
Copies the count greatest elements according to cmp of the range [first, last) to the range beginning...
Definition: algorithm.h:1257
constexpr auto transform_if(InputIt first, EndIt last, OutputIt d_first, UnaryPredicate pred, UnaryOperation unary_op) -> OutputIt
transform applies the given function to a range and stores the result in another range,...
Definition: algorithm.h:1690
constexpr auto exchange(T &obj, U &&new_value) -> T
Definition: fakestd.h:725
constexpr auto accumulate(InputIt first, InputIt last, T init, BinaryOperation op) -> T
A constexpr version of std::accumulate.
Definition: algorithm.h:174
constexpr auto any_of(Range &&rng, UnaryPredicate pred) -> enable_if_t< is_iterable< Range >::value, bool >
Determine if pred is true for every element of the range.
Definition: algorithm.h:1038
constexpr auto find_last_if_not(ForwardIt begin, EndIt end, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin))) -> ForwardIt
Searches a range for the last element on which a predicate returns false. It also allows for a sentin...
Definition: algorithm.h:427
constexpr auto equals(const Obj &a, const Obj &b, Compare comp) noexcept(noexcept(comp(a, b))) -> bool
Synthesize an equivalence relation from comp.
Definition: algorithm.h:106
constexpr auto a(const std::initializer_list< T > &a) -> auto
Index an array literal without naming its type.
Definition: simple.h:255
constexpr auto first_result(InputIt1 begin1, EndIt1 end1, InputIt2 begin2, EndIt2 end2, T def, BinaryTransform op) -> enable_if_t< is_input_iterator< InputIt1 >::value and is_input_iterator< InputIt2 >::value, std::decay_t< decltype(op(*begin1, *begin2))> >
Definition: algorithm.h:851
constexpr auto any_of(InputIt begin, InputIt end, UnaryPredicate pred) -> enable_if_t< is_input_iterator< InputIt >::value, bool >
Determine if pred is true for at least one element of the range.
Definition: algorithm.h:1024
constexpr auto generate(OutputIt first, EndIt last, Generator g) noexcept(noexcept(*++first=g())) -> OutputIt
Like std::generate except that it returns the output iterator at the end. It also allows for a sentin...
Definition: algorithm.h:1545
typename std::enable_if< B, T >::type enable_if_t
Definition: fakestd.h:61
constexpr auto all_of(Range &&rng, UnaryPredicate pred) -> enable_if_t< is_iterable< Range >::value, bool >
Determine if pred is true for every element of the range.
Definition: algorithm.h:984
constexpr auto replace_copy_if(InputIt first, EndIt last, OutputIt out, UnaryPredicate pred, const T &new_value) -> OutputIt
Copies an input range, but every element for which pred is true is replaced by new_value....
Definition: algorithm.h:1413
constexpr auto first_result_if(InputIt1 begin1, EndIt1 end1, InputIt2 begin2, EndIt2 end2, T def, BinaryTransform op, BinaryPredicate ch) -> enable_if_t< is_input_iterator< InputIt1 >::value and is_input_iterator< InputIt2 >::value, decltype(op(*begin1, *begin2))>
Definition: algorithm.h:898
constexpr auto copy_n(InputIt first, Size count, OutputIt out) -> OutputIt
Copies all elements of [first, std::advance(first, n)) to out.
Definition: algorithm.h:1365
constexpr auto generate_n(OutputIt first, Size count, Generator g) noexcept(noexcept(*first++=g())) -> OutputIt
Like std::generate_n except that it is constexpr.
Definition: algorithm.h:1565
struct kblib::@0 swap
constexpr auto find_if(ForwardIt begin, EndIt end, UnaryPredicate &&pred) noexcept(noexcept(kblib::invoke(pred, *begin))) -> ForwardIt
Finds the first value in range [begin, end) for which pred returns true. If not found,...
Definition: algorithm.h:327
constexpr auto find_in(const Container &c, const T &value) noexcept(noexcept(*std::declval< iterator_type_for_t< const Container > & >()==value)) -> size_t
Find the first element in c equal to v and return the position.
Definition: algorithm.h:559
typename iterator_type_for< Range >::type iterator_type_for_t
Definition: traits.h:397
constexpr auto e() -> T
Definition: stats.h:468
constexpr auto for_each(ForwardIt first, EndIt last, ForwardIt2 second, BinaryFunction f) -> BinaryFunction
Applies a binary operation to each pair of corresponding elements in two input ranges....
Definition: algorithm.h:1280
constexpr auto find_last_in_if(const Container &c, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *std::declval< iterator_type_for_t< const Container > & >()))) -> size_t
Find the last element in c for which p returns true and return the position.
Definition: algorithm.h:664
constexpr auto copy_if(InputIt first, EndIt last, OutputIt out, UnaryPredicate pred) -> OutputIt
Copies those elements of [first, last) which satisfy pred to out. It also allows for a sentinel end i...
Definition: algorithm.h:1343
constexpr auto for_each_n(ForwardIt first, Size n, ForwardIt2 second, BinaryFunction f) -> std::pair< ForwardIt, ForwardIt2 >
Applies a binary operation to each pair of corresponding elements in two input ranges.
Definition: algorithm.h:1301
constexpr auto ends_with(RandomAccessIt1 begin1, RandomAccessIt1 end1, RandomAccessIt2 begin2, RandomAccessIt2 end2, BinaryPred pred={}) -> enable_if_t< is_random_access_iterator_v< RandomAccessIt1 > and is_random_access_iterator_v< RandomAccessIt2 >, bool >
Checks if a given range ends with a particular subrange.
Definition: algorithm.h:803
constexpr auto first_result_opt(InputIt1 begin1, EndIt1 end1, InputIt2 begin2, EndIt2 end2, T def, BinaryTransform op) -> enable_if_t< is_input_iterator< InputIt1 >::value and is_input_iterator< InputIt2 >::value, std::decay_t< decltype(op(*begin1, *begin2))> >
Definition: algorithm.h:950
constexpr auto get_max_n_old(It first, It last, std::size_t count, Comp cmp={}) -> SequenceContainer
Returns a container of the greatest count elements according to cmp of the range [first,...
Definition: algorithm.h:1146
constexpr auto find(ForwardIt begin, EndIt end, const Elem &value, Comp &&comp) noexcept(noexcept(comp(*begin, value))) -> ForwardIt
Finds a value in range [begin, end). If not found, returns end. It also allows for a sentinel end ite...
Definition: algorithm.h:309
constexpr auto find_last_in_if_not(const Container &c, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *std::declval< iterator_type_for_t< const Container > & >()))) -> size_t
Find the last element in c for which p returns true and return the position.
Definition: algorithm.h:686
constexpr auto max_element(ForwardIt first, EndIt last, Compare comp={}) -> ForwardIt
Definition: algorithm.h:1109
constexpr auto find_last(ForwardIt begin, EndIt end, const Elem &value) noexcept(noexcept(*begin==value)) -> ForwardIt
Searches a range for the last occurence of a match, and returns an iterator to it....
Definition: algorithm.h:366
constexpr auto invoke(F &&f, Args &&... args) noexcept(noexcept(detail::do_invoke(std::forward< F >(f), std::forward< Args >(args)...))) -> decltype(auto)
Definition: fakestd.h:138
typename std::decay< T >::type decay_t
Definition: fakestd.h:64
KBLIB_CONSTANT_V is_random_access_iterator_v
Definition: traits.h:378
constexpr auto erase_if(Container &c, UnaryPredicate p) noexcept(noexcept(c.erase(std::remove_if(c.begin(), c.end(), std::ref(p)), c.end()))) -> void
Abbreviation of the erase-remove idiom as a free function.
Definition: algorithm.h:81
constexpr auto transform_exclusive_scan(InputIt first, EndIt last, OutputIt d_first, T init, BinaryAccumulation accum, UnaryTransform proj) -> OutputIt
Definition: algorithm.h:251
constexpr auto erase(Container &c, const Elem &val) noexcept(noexcept(c.erase(std::remove(c.begin(), c.end(), val), c.end()))) -> void
Abbreviation of the erase-remove idiom as a free function.
Definition: algorithm.h:68
constexpr auto replace_copy_n_if(InputIt first, Size count, OutputIt out, UnaryPredicate pred, const T &new_value) -> OutputIt
Copies an input range, but every element for which pred is true is replaced by new_value.
Definition: algorithm.h:1444
constexpr auto iota(ForwardIt first, ForwardIt last, T value, UnaryOperation unary_op) noexcept(noexcept(*first++=value) and noexcept(kblib::invoke(unary_op, std::move(value)))) -> void
Definition: algorithm.h:1587
constexpr auto copy_n_if(InputIt first, Size count, OutputIt out, UnaryPredicate pred) -> OutputIt
Copies those elements of [first, std::advance(first, n)) which satisfy pred to out.
Definition: algorithm.h:1386
constexpr auto contains_any(Range1 &&haystack, Range2 &&needle) -> enable_if_t< is_iterable< Range1 >::value and is_iterable< Range2 >::value, bool >
Definition: algorithm.h:1098
constexpr auto find_in_if(const Container &c, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *std::declval< iterator_type_for_t< const Container > & >()))) -> size_t
Find the first element in c for which p returns true and return the position.
Definition: algorithm.h:585
constexpr auto find(ForwardIt begin, EndIt end, const Elem &value) noexcept(noexcept(*begin==value)) -> ForwardIt
Finds a value in range [begin, end). If not found, returns end. It also allows for a sentinel end ite...
Definition: algorithm.h:290
constexpr auto rotate(ForwardIt first, ForwardIt n_first, ForwardIt last) noexcept(noexcept(swap(*first, *first))) -> ForwardIt
Rotates the input range. This is just a constexpr-in-C++14 version of std::rotate.
Definition: algorithm.h:1509
constexpr auto accumulate(InputIt first, InputIt last, T init) -> T
A constexpr version of std::accumulate.
Definition: algorithm.h:162
constexpr auto search_replace_copy(Haystack &&haystack, Needle &&needle, Replacement &&replacement, OutputIt d_begin, BinaryPredicate compare={})
Definition: algorithm.h:1487
constexpr auto find_if_not(ForwardIt begin, EndIt end, UnaryPredicate &&pred) noexcept(noexcept(kblib::invoke(pred, *begin))) -> ForwardIt
Finds the first value in range [begin, end) for which pred returns false. If not found,...
Definition: algorithm.h:346
constexpr auto sum(Range &&r) -> auto
Sum a range.
Definition: algorithm.h:237
constexpr auto copy(InputIt first, EndIt last, OutputIt out) -> OutputIt
Copies all elements of [first, last) to out. It also allows for a sentinel end iterator.
Definition: algorithm.h:1322
typename return_assert< V, T >::type return_assert_t
Definition: fakestd.h:550
constexpr auto find_in_if_not(const Container &c, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *std::declval< iterator_type_for_t< const Container > & >()))) -> size_t
Find the first element in c for which p returns false and return the position.
Definition: algorithm.h:607
constexpr auto none_of(Range &&rng, UnaryPredicate pred) -> enable_if_t< is_iterable< Range >::value, bool >
Determine if pred is true for every element of the range.
Definition: algorithm.h:1011
constexpr auto find_match(InputIt1 begin1, EndIt1 end1, InputIt2 begin2, EndIt2 end2, BinaryPredicate cmp) -> enable_if_t< is_input_iterator< InputIt1 >::value and is_input_iterator< InputIt2 >::value and is_invocable< BinaryPredicate, decltype(*begin1), decltype(*begin2)>::value, std::pair< InputIt1, InputIt2 > >
Definition: algorithm.h:717
constexpr auto transform(InputIt first, EndIt last, InputIt first2, OutputIt d_first, BinaryOperation binary_op) -> OutputIt
transform applies the given function to a range and stores the result in another range,...
Definition: algorithm.h:1659
constexpr auto starts_with(RandomAccessIt1 begin1, RandomAccessIt1 end1, RandomAccessIt2 begin2, RandomAccessIt2 end2, BinaryPred pred={}) -> enable_if_t< is_random_access_iterator_v< RandomAccessIt1 > and is_random_access_iterator_v< RandomAccessIt2 >, bool >
Checks if a given range starts with a particular subrange.
Definition: algorithm.h:759
constexpr auto to_unsigned(I x) -> std::make_unsigned_t< I >
Cast integral argument to corresponding unsigned type.
Definition: fakestd.h:592
constexpr auto equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) -> bool
Definition: fakestd.h:966
constexpr auto repeat(std::size_t N, Callable func) noexcept(noexcept(func())) -> return_assert_t< is_invocable< Callable >::value, void >
Invoke a function N times.
Definition: algorithm.h:53
constexpr auto find_last_if(ForwardIt begin, EndIt end, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin))) -> ForwardIt
Searches a range for the last element on which a predicate returns true. It also allows for a sentine...
Definition: algorithm.h:396
Definition: bits.h:721
constexpr auto operator()(const Obj &a, const Obj &b, Compare comp) const noexcept(noexcept(equals(a, b, comp))) -> bool
Definition: algorithm.h:142
constexpr auto operator()(const Obj &a, const Obj &b) const noexcept(noexcept(equals(a, b))) -> bool
Definition: algorithm.h:133
constexpr auto operator()(const Obj &a, const Obj &b) const noexcept(noexcept(equals(a, b))) -> bool
Definition: algorithm.h:152
A function object implementing the equivalence relationship over a comparison predicate.
Definition: algorithm.h:123
constexpr auto operator()(const Obj &a, const Obj &b, Compare comp) const noexcept(noexcept(equals(a, b, comp))) -> bool
Definition: algorithm.h:124
Provides macros and basic templates used by the rest of kblib.
#define KBLIB_NS
Definition: tdecl.h:113
#define KBLIB_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:129
Contains some type traits not in the standard library that are useful in the implementation of kblib.