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 
44 namespace kblib {
45 
52 template <typename Callable>
53 constexpr 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 
67 template <typename Container, typename Elem>
68 constexpr 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 
80 template <typename Container, typename UnaryPredicate>
81 constexpr 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 
93 template <typename Obj>
94 KBLIB_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 
105 template <typename Obj, typename Compare>
106 KBLIB_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 
122 template <typename Compare = void, typename Obj = void>
123 struct equivalent {
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 
131 template <typename Obj>
132 struct 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 
139 template <typename Compare>
140 struct 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 
149 template <>
150 struct 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 
161 template <typename InputIt, typename T>
162 KBLIB_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 
173 template <class InputIt, class T, class BinaryOperation>
174 KBLIB_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 
193 template <typename InputIt>
194 KBLIB_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 
215 template <typename InputIt, typename BinaryOperation>
216 KBLIB_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 
236 template <typename Range>
237 KBLIB_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 
249 template <typename InputIt, typename EndIt, typename OutputIt, typename T,
250  typename BinaryAccumulation, typename UnaryTransform>
251 constexpr 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
263 template <typename InputIt, typename BinaryAccumulation,
264  typename BinaryTransform>
265 KBLIB_NODISCARD constexpr auto
266 adjacent_reduce(InputIt begin, InputIt begin1, InputIt end,
267  BinaryAccumulation acc, BinaryTransform op) {}
268 
269 template <typename InputIt, typename BinaryTransform>
270 KBLIB_NODISCARD constexpr auto adjacent_transform(InputIt begin, InputIt begin1,
271  InputIt end,
272  BinaryTransform op) {}
273 
274 template <typename InputIt, typename BinaryAccumulation,
275  typename BinaryTransform>
276 KBLIB_NODISCARD constexpr auto
277 adjacent_inclusive_scan(InputIt begin, InputIt begin1, InputIt end,
278  BinaryAccumulation acc, BinaryTransform op) {}
279 #endif
280 
289 template <typename ForwardIt, typename EndIt, typename Elem>
290 KBLIB_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 
308 template <typename ForwardIt, typename EndIt, typename Elem, typename Comp>
309 KBLIB_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 
326 template <typename ForwardIt, typename EndIt, typename UnaryPredicate>
327 KBLIB_NODISCARD constexpr auto find_if(
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 
345 template <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 
365 template <typename ForwardIt, typename EndIt, typename Elem>
366 KBLIB_NODISCARD constexpr auto find_last(
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 
395 template <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 
426 template <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 
457 template <typename ForwardIt, typename EndIt, typename Elem>
458 KBLIB_NODISCARD constexpr auto find_in(
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 
473 template <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 }
489 template <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 
509 template <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 
524 template <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 }
540 template <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 
557 template <typename Container, typename T>
558 KBLIB_NODISCARD constexpr auto
559 find_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
567 template<typename ExecutionPolicy, typename Container, typename T>
568 KBLIB_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 
584 template <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 }
606 template <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
619 template<typename ExecutionPolicy, typename Container, typename UnaryPredicate>
620 KBLIB_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 }
625 template<typename ExecutionPolicy, typename Container, typename UnaryPredicate>
626 KBLIB_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 
643 template <typename Container, typename T>
644 KBLIB_NODISCARD constexpr auto
645 find_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 
663 template <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 }
685 template <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 
699 template <typename InputIt1, typename EndIt1, typename InputIt2,
700  typename BinaryPredicate = std::equal_to<>>
701 KBLIB_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 }
715 template <typename InputIt1, typename EndIt1, typename InputIt2,
716  typename EndIt2, typename BinaryPredicate = std::equal_to<>>
717 KBLIB_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 
736 template <typename InputIt1, typename EndIt1, typename InputIt2,
737  typename EndIt2, typename BinaryPred>
738 KBLIB_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 
757 template <typename RandomAccessIt1, typename RandomAccessIt2,
758  typename BinaryPred = std::equal_to<>>
759 KBLIB_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 
779 template <typename BidirIt1, typename BidirIt2,
780  typename BinaryPred = std::equal_to<>>
781 KBLIB_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 
801 template <typename RandomAccessIt1, typename RandomAccessIt2,
802  typename BinaryPred = std::equal_to<>>
803 KBLIB_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 
820 template <typename InputIt, typename EndIt, typename T, typename UnaryTransform>
821 KBLIB_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 }
833 template <typename InputIt1, typename EndIt1, typename InputIt2, typename T,
834  typename BinaryTransform>
835 KBLIB_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 }
849 template <typename InputIt1, typename EndIt1, typename InputIt2,
850  typename EndIt2, typename T, typename BinaryTransform>
851 KBLIB_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 
866 template <typename InputIt, typename EndIt, typename T, typename UnaryTransform,
867  typename UnaryPredicate>
868 KBLIB_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 }
879 template <typename InputIt1, typename EndIt1, typename InputIt2, typename T,
880  typename BinaryTransform, typename BinaryPredicate>
881 KBLIB_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 }
895 template <typename InputIt1, typename EndIt1, typename InputIt2,
896  typename EndIt2, typename T, typename BinaryTransform,
897  typename BinaryPredicate>
898 KBLIB_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
914 template <typename T>
915 struct is_optional : std::false_type {};
916 template <typename U>
917 struct is_optional<std::optional<U>> : std::true_type {};
918 
919 template <typename InputIt, typename EndIt, typename T, typename UnaryTransform>
920 KBLIB_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 }
932 template <typename InputIt1, typename EndIt1, typename InputIt2, typename T,
933  typename BinaryTransform>
934 KBLIB_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 }
948 template <typename InputIt1, typename EndIt1, typename InputIt2,
949  typename EndIt2, typename T, typename BinaryTransform>
950 KBLIB_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 
969 template <typename InputIt, typename UnaryPredicate>
970 KBLIB_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 }
983 template <typename Range, typename UnaryPredicate>
984 KBLIB_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 }
996 template <typename InputIt, typename UnaryPredicate>
997 KBLIB_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 }
1010 template <typename Range, typename UnaryPredicate>
1011 KBLIB_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 }
1023 template <typename InputIt, typename UnaryPredicate>
1024 KBLIB_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 }
1037 template <typename Range, typename UnaryPredicate>
1038 KBLIB_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 
1051 template <typename InputIt, typename Value>
1052 KBLIB_NODISCARD constexpr auto contains(
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 
1062 template <typename Set, typename Value>
1063 KBLIB_NODISCARD constexpr auto contains(
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 
1075 template <typename InputIt1, typename InputIt2>
1076 KBLIB_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 
1086 template <typename InputIt, typename Range2>
1087 KBLIB_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 
1097 template <typename Range1, typename Range2>
1098 KBLIB_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 
1108 template <typename ForwardIt, typename EndIt, typename Compare = std::less<>>
1109 constexpr 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 
1144 template <typename SequenceContainer, typename Comp = std::less<>, typename It,
1145  enable_if_t<is_linear_container_v<SequenceContainer>, int> = 0>
1146 KBLIB_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 
1178 template <typename SetlikeContainer, typename Comp = std::less<>, typename It,
1179  enable_if_t<is_setlike_v<SetlikeContainer>, int> = 0>
1180 KBLIB_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 
1201 template <typename SequenceContainer, typename Comp = std::less<>, typename It,
1202  enable_if_t<is_linear_container_v<SequenceContainer>, int> = 0>
1203 KBLIB_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 
1228 template <typename SetlikeContainer, typename Comp = std::less<>, typename It,
1229  enable_if_t<is_setlike_v<SetlikeContainer>, int> = 0>
1230 KBLIB_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 
1255 template <typename Comp = std::less<>, typename InputIt, typename OutputIt,
1256  typename Elem = typename std::iterator_traits<InputIt>::value_type>
1257 constexpr 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 
1278 template <typename ForwardIt, typename EndIt, typename ForwardIt2,
1279  typename BinaryFunction>
1280 constexpr 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 
1299 template <typename ForwardIt, typename ForwardIt2, typename Size,
1300  typename BinaryFunction>
1301 constexpr 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 
1321 template <typename InputIt, typename EndIt, typename OutputIt>
1322 constexpr auto copy(InputIt first, EndIt last, OutputIt out) -> OutputIt {
1323  while (first != last) {
1324  *out++ = *first++;
1325  }
1326  return out;
1327 }
1328 
1341 template <typename InputIt, typename EndIt, typename OutputIt,
1342  typename UnaryPredicate>
1343 constexpr 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 
1364 template <typename InputIt, typename Size, typename OutputIt>
1365 constexpr 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 
1384 template <typename InputIt, typename Size, typename OutputIt,
1385  typename UnaryPredicate>
1386 constexpr 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 
1411 template <typename InputIt, typename EndIt, typename OutputIt,
1412  typename UnaryPredicate, typename T>
1413 constexpr 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 
1442 template <typename InputIt, typename Size, typename OutputIt,
1443  typename UnaryPredicate, typename T>
1444 constexpr 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
1460 template <typename ForwardIt1, typename ForwardIt2, typename ForwardIt3,
1461  typename OutputIt, typename BinaryPredicate = std::equal_to<>>
1462 constexpr 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 
1485 template <typename Haystack, typename Needle, typename Replacement,
1486  typename OutputIt, typename BinaryPredicate = std::equal_to<>>
1487 constexpr auto search_replace_copy(Haystack&& haystack, Needle&& needle,
1488  Replacement&& replacement, OutputIt d_begin,
1489  BinaryPredicate compare = {}) {
1490  using std::begin, std::end;
1491  return search_replace_copy(begin(haystack), end(haystack), //
1492  begin(needle), end(needle), //
1493  begin(replacement), end(replacement), //
1494  d_begin, //
1495  compare);
1496 }
1497 
1507 template <class ForwardIt>
1508 constexpr auto rotate(ForwardIt first, ForwardIt n_first,
1509  ForwardIt last) noexcept(noexcept(swap(*first, *first)))
1510  -> ForwardIt {
1511  if (first == n_first)
1512  return last;
1513  if (n_first == last)
1514  return first;
1515 
1516  ForwardIt read = n_first;
1517  ForwardIt write = first;
1518  ForwardIt next_read = first; // read position for when "read" hits "last"
1519 
1520  while (read != last) {
1521  if (write == next_read)
1522  next_read = read; // track where "first" went
1523  // iter_swap is not constexpr
1524  // std::iter_swap(write++, read++);
1525  swap(*(write++), *(read++));
1526  }
1527 
1528  // rotate the remaining sequence into place
1529  kblib::rotate(write, next_read, last);
1530  return write;
1531 }
1532 
1543 template <typename OutputIt, typename EndIt, typename Generator>
1544 constexpr auto generate(OutputIt first, EndIt last,
1545  Generator g) noexcept(noexcept(*++first = g()))
1546  -> OutputIt {
1547  while (first != last) {
1548  *first = g();
1549  ++first;
1550  }
1551  return first;
1552 }
1553 
1563 template <typename OutputIt, typename Size, typename Generator>
1564 constexpr auto generate_n(OutputIt first, Size count,
1565  Generator g) noexcept(noexcept(*first++ = g()))
1566  -> OutputIt {
1567  for (Size i = 0; i < count; i++) {
1568  *first++ = g();
1569  }
1570  return first;
1571 }
1572 
1573 template <typename ForwardIt, typename T>
1574 constexpr auto iota(ForwardIt first, ForwardIt last, T value) noexcept(
1575  noexcept(*first++ = value) and noexcept(++value)) -> void {
1576  while (first != last) {
1577  *first++ = value;
1578  ++value;
1579  }
1580 }
1581 
1582 // For some reason these long noexcept specifications really trip
1583 // up clang-format
1584 // clang-format off
1585 template <typename ForwardIt, typename T, typename UnaryOperation>
1586 constexpr auto iota(
1587  ForwardIt first, ForwardIt last, T value,
1588  UnaryOperation unary_op
1589  ) noexcept(noexcept(*first++ = value)
1590  and noexcept(kblib::invoke(unary_op,
1591  std::move(value))))
1592  -> void {
1593  // clang-format on
1594  while (first != last) {
1595  *first++ = value;
1596  value = kblib::invoke(unary_op, std::move(value));
1597  }
1598 }
1599 
1600 // clang-format off
1601 template <typename InputIt, typename EndIt, typename... Params>
1602 constexpr auto call_each(
1603  InputIt first, EndIt last, Params&&... params
1604  ) noexcept(noexcept(kblib::invoke(*first++,
1605  std::forward<Params>(params)...)))
1606  -> InputIt {
1607  // clang-format on
1608  while (first != last) {
1609  kblib::invoke(*first++, std::forward<Params>(params)...);
1610  }
1611  return first;
1612 }
1613 
1629 template <typename InputIt, typename EndIt, typename OutputIt,
1630  typename UnaryOperation>
1631 constexpr auto transform(InputIt first, EndIt last, OutputIt d_first,
1632  UnaryOperation unary_op) -> OutputIt {
1633  while (first != last) {
1634  *d_first++ = kblib::invoke(unary_op, *first);
1635  ++first;
1636  }
1637  return d_first;
1638 }
1639 
1656 template <typename InputIt, typename EndIt, typename InputIt2,
1657  typename OutputIt, typename BinaryOperation>
1658 constexpr auto transform(InputIt first, EndIt last, InputIt first2,
1659  OutputIt d_first, BinaryOperation binary_op)
1660  -> OutputIt {
1661  while (first != last) {
1662  *d_first++ = kblib::invoke(binary_op, *first, *first2);
1663  ++first;
1664  ++first2;
1665  }
1666  return d_first;
1667 }
1668 
1687 template <typename InputIt, typename EndIt, typename OutputIt,
1688  typename UnaryPredicate, typename UnaryOperation>
1689 constexpr auto transform_if(InputIt first, EndIt last, OutputIt d_first,
1690  UnaryPredicate pred, UnaryOperation unary_op)
1691  -> OutputIt {
1692  while (first != last) {
1693  if (kblib::invoke(pred, *first)) {
1694  *d_first++ = kblib::invoke(unary_op, *first);
1695  }
1696  ++first;
1697  }
1698  return d_first;
1699 }
1700 
1701 namespace detail_algorithm {
1702 
1712  template <class ForwardIt>
1713  constexpr auto shift_backward(
1714  ForwardIt first, ForwardIt n_first,
1715  ForwardIt last) noexcept(noexcept(*first = std::move(*first))) -> void {
1716  if (first == n_first or n_first == last)
1717  return;
1718 
1719  ForwardIt read = n_first;
1720  ForwardIt write = first;
1721 
1722  while (read != last) {
1723  *(write++) = std::move(*(read++));
1724  }
1725 
1726  return;
1727  }
1728 
1729 } // namespace detail_algorithm
1730 
1731 } // namespace kblib
1732 
1733 #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:1713
The main namespace in which all entities from kblib are defined.
Definition: algorithm.h:44
constexpr auto call_each(InputIt first, EndIt last, Params &&... params) noexcept(noexcept(kblib::invoke(*first++, std::forward< Params >(params)...))) -> InputIt
Definition: algorithm.h:1602
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 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:1689
constexpr auto exchange(T &obj, U &&new_value) -> T
Definition: fakestd.h:718
constexpr auto find_in_if_not(ForwardIt begin, EndIt end, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin))) -> size_t
Find the offset of the first element for which p returns false. It also allows for a sentinel end ite...
Definition: algorithm.h:490
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 a(const std::initializer_list< T > &a) -> auto
Index an array literal without naming its type.
Definition: simple.h:255
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:1544
typename std::enable_if< B, T >::type enable_if_t
Definition: fakestd.h:54
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 iota(ForwardIt first, ForwardIt last, T value) noexcept(noexcept(*first++=value) and noexcept(++value)) -> void
Definition: algorithm.h:1574
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:1564
constexpr auto find_last_in_if(ForwardIt begin, EndIt end, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin))) -> size_t
Definition: algorithm.h:525
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
typename iterator_type_for< Range >::type iterator_type_for_t
Definition: traits.h:397
constexpr auto first_result_if(InputIt begin, EndIt end, T def, UnaryTransform op, UnaryPredicate ch) -> enable_if_t< is_input_iterator< InputIt >::value, decltype(op(*begin))>
Definition: algorithm.h:868
constexpr auto e() -> T
Definition: stats.h:465
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 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 equals(const Obj &a, const Obj &b) noexcept(noexcept(a< b)) -> bool
Synthesize an equivalence relation from <.
Definition: algorithm.h:94
constexpr auto find_in(ForwardIt begin, EndIt end, const Elem &value) noexcept(noexcept(*begin==value)) -> size_t
Find the offset of the first ocurrence of v in a range from the beginning. It also allows for a senti...
Definition: algorithm.h:458
constexpr auto get_max_n(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:1203
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 max_element(ForwardIt first, EndIt last, Compare comp={}) -> ForwardIt
Definition: algorithm.h:1109
constexpr auto ends_with(BidirIt1 begin1, BidirIt1 end1, BidirIt2 begin2, BidirIt2 end2, BinaryPred pred={}) -> enable_if_t<(is_bidirectional_iterator_v< BidirIt1 > and is_bidirectional_iterator_v< BidirIt2 >) and not(is_random_access_iterator_v< BidirIt1 > and is_random_access_iterator_v< BidirIt2 >), bool >
Checks if a given range ends with a particular subrange.
Definition: algorithm.h:781
constexpr auto starts_with(InputIt1 begin1, EndIt1 end1, InputIt2 begin2, EndIt2 end2, BinaryPred pred) -> enable_if_t<(is_input_iterator_v< InputIt1 > and is_input_iterator_v< InputIt2 >) and not(is_random_access_iterator_v< InputIt1 > and is_random_access_iterator_v< InputIt2 >), bool >
Checks if a given range starts with a particular subrange.
Definition: algorithm.h:738
constexpr auto contains_any(InputIt1 begin, InputIt1 end, InputIt2 n_begin, InputIt2 n_end) -> enable_if_t< is_input_iterator< InputIt1 >::value and is_input_iterator< InputIt2 >::value, bool >
Definition: algorithm.h:1076
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:130
constexpr auto find_last_in_if_not(ForwardIt begin, EndIt end, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin))) -> size_t
Find the offset of the last element for which p returns false. It also allows for a sentinel end iter...
Definition: algorithm.h:541
typename std::decay< T >::type decay_t
Definition: fakestd.h:57
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 none_of(InputIt begin, InputIt end, UnaryPredicate pred) -> enable_if_t< is_input_iterator< InputIt >::value, bool >
Determine if pred is false for every element of the range.
Definition: algorithm.h:997
constexpr auto sum(InputIt first, InputIt last) -> std::decay_t< decltype(*first)>
Sum a range.
Definition: algorithm.h:194
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 all_of(InputIt begin, InputIt end, UnaryPredicate pred) -> enable_if_t< is_input_iterator< InputIt >::value, bool >
Determine if pred is true for every element of the range.
Definition: algorithm.h:970
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:1508
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(ForwardIt1 h_begin, ForwardIt1 h_end, ForwardIt2 n_begin, ForwardIt2 n_end, ForwardIt3 r_begin, ForwardIt3 r_end, OutputIt d_begin, BinaryPredicate Compare={}) -> OutputIt
Definition: algorithm.h:1462
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 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
constexpr auto find_match(InputIt1 begin1, EndIt1 end1, InputIt2 begin2, 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:701
typename return_assert< V, T >::type return_assert_t
Definition: fakestd.h:542
constexpr auto first_result(InputIt begin, EndIt end, T def, UnaryTransform op) -> enable_if_t< is_input_iterator< InputIt >::value, std::decay_t< decltype(op(*begin))>>
Definition: algorithm.h:821
constexpr auto first_result_opt(InputIt begin, EndIt end, T def, UnaryTransform op) -> enable_if_t< is_input_iterator< InputIt >::value, std::decay_t< decltype(op(*begin))>>
Definition: algorithm.h:920
constexpr auto find_last_in(ForwardIt begin, EndIt end, const Elem &value) noexcept(noexcept(*begin==value)) -> size_t
Find the offset of the last ocurrence of v in a range from the beginning. It also allows for a sentin...
Definition: algorithm.h:510
constexpr auto find_in_if(ForwardIt begin, EndIt end, UnaryPredicate pred) noexcept(noexcept(kblib::invoke(pred, *begin))) -> size_t
Find the offset of the first element for which p returns true. It also allows for a sentinel end iter...
Definition: algorithm.h:474
constexpr auto to_unsigned(I x) -> std::make_unsigned_t< I >
Cast integral argument to corresponding unsigned type.
Definition: fakestd.h:585
constexpr auto equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) -> bool
Definition: fakestd.h:959
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
constexpr auto transform(InputIt first, EndIt last, OutputIt d_first, UnaryOperation unary_op) -> OutputIt
transform applies the given function to a range and stores the result in another range,...
Definition: algorithm.h:1631
Definition: bits.h:714
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_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:81
Contains some type traits not in the standard library that are useful in the implementation of kblib.