kblib  0.2.3
General utilities library for modern C++
sort.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 
31 #ifndef SORT_H
32 #define SORT_H
33 
34 #include "algorithm.h"
35 #include "bits.h"
36 #include "fakestd.h"
37 #include "simple.h"
38 
39 #include <bitset>
40 #include <numeric>
41 
42 namespace kblib {
43 
56 template <typename RandomAccessIt, typename Compare = std::less<>>
57 constexpr auto insertion_sort(
58  const RandomAccessIt begin, const RandomAccessIt end,
59  Compare&& compare
60  = {}) noexcept(noexcept(swap(*begin, *begin)) and noexcept(compare(*begin,
61  *begin)))
62  -> void {
63  // Trivial inputs are trivially already sorted.
64  if (end - begin <= 1) {
65  return;
66  }
67  for (auto pos = begin + 1; pos != end; ++pos) {
68  // This search is linear, not binary, because insertion_sort is meant
69  // to never be used for arrays large enough for binary search.
70  auto index = kblib::find_if(begin, pos, [&compare, pos](const auto& a) {
71  return compare(*pos, a);
72  });
73  kblib::rotate(index, pos, pos + 1);
74  }
75  return;
76 }
77 
91 template <typename RandomAccessIt, typename RandomAccessIt2,
92  typename Compare = std::less<>>
93 constexpr auto insertion_sort_copy(
94  const RandomAccessIt begin, const RandomAccessIt end,
95  const RandomAccessIt2 d_begin, const RandomAccessIt2 d_end,
96  Compare&& compare
97  = {}) noexcept(noexcept(detail_algorithm::
98  shift_backward(d_begin, d_begin,
99  d_end)) and noexcept(*d_begin
100  = *begin))
101  -> void {
102  const auto dist = end - begin;
103  assert(end - begin == d_end - d_begin);
104  if (dist == 0) {
105  return;
106  } else if (dist == 1) {
107  // ranges of 1 are trivial to sort
108  *d_begin = *begin;
109  return;
110  } else if (dist == 2) {
111  // Special case distance=2 to perform no swaps, and because the loop
112  // for the general case assumes 3 or more elements.
113  if (compare(*begin, *(begin + 1))) {
114  *d_begin = *begin;
115  *(d_begin + 1) = *(begin + 1);
116  return;
117  } else {
118  *d_begin = *(begin + 1);
119  *(d_begin + 1) = *begin;
120  }
121  } else {
122  // This loop writes in reverse because shifting backwards can be done
123  // in a forward pass, making it simpler than a forward shift, and is
124  // sufficient for the algorithm, and reads in reverse to avoid worst-
125  // case complexity for sorted inputs, given that it writes in reverse.
126  auto read = std::prev(end);
127  auto write = std::prev(d_end);
128  // push first element to get the loop invariant
129  *write = *read;
130  do {
131  --read, --write;
132  // This search is linear, not binary, because insertion_sort_copy
133  // is meant to never be used for arrays large enough for binary
134  // search.
135 #if 1
136  auto index = kblib::find_if(
137  write + 1, d_end,
138  [&compare, read](const auto& a) { return not compare(a, *read); });
139 #else
140  auto index = kblib::find_if(write + 1, d_end,
141  [&compare, read](const auto& a) {
142  if (stable) {
143  // find first element greater than
144  // *read
145  return compare(*read, a);
146  } else {
147  // find first element greater than
148  // or equal to *read
149  return ! compare(a, *read);
150  }
151  });
152 #endif
153  detail_algorithm::shift_backward(write, write + 1, index);
154  *(index - 1) = *read;
155  } while (write != d_begin);
156  return;
157  }
158 }
159 
176 template <typename RandomAccessIt, typename RandomAccessIt2,
177  typename Compare = std::less<>>
179  const RandomAccessIt begin, const RandomAccessIt end,
180  const RandomAccessIt2 d_begin, const RandomAccessIt2 d_end,
181  Compare&& compare
182  = {}) noexcept(noexcept(detail_algorithm::
183  shift_backward(d_begin, d_begin,
184  d_end)) and noexcept(*d_begin
185  = *begin))
186  -> void {
187  const auto dist = end - begin;
188  // For trivial inputs, don't bother doing anything
189  if (dist < 3) {
190  insertion_sort_copy(begin, end, d_begin, d_end,
191  std::forward<Compare>(compare));
192  }
193  // A very rudimentary way of estimating the sortedness of the input, by
194  // counting the relative number of ascending and descending adjacent pairs
195  // within the first sqrt(n) elements.
196  const auto scan_end
197  = begin
198  + static_cast<std::ptrdiff_t>(std::sqrt(static_cast<float>(dist)));
199  std::ptrdiff_t dir{};
200  for (auto pos = begin; pos != scan_end - 1; ++pos) {
201  if (compare(*pos, *(pos + 1))) {
202  ++dir;
203  } else if (compare(*(pos + 1), *pos)) {
204  --dir;
205  }
206  }
207  if (dir >= 0) {
208  insertion_sort_copy(begin, end, d_begin, d_end,
209  std::forward<Compare>(compare));
210  } else {
211  // If the input is predominantly in reverse order, sort it in reverse
212  // IMPORTANT: the reverse iterators go end, begin
213  insertion_sort_copy(std::make_reverse_iterator(end),
214  std::make_reverse_iterator(begin), d_begin, d_end,
215  std::forward<Compare>(compare));
216  }
217 }
218 
219 template <typename T, typename = void>
220 struct is_radix_sortable : std::false_type {};
221 
222 template <typename T>
223 struct is_radix_sortable<T, void_if_t<std::is_integral<T>::value>>
224  : std::true_type {};
225 
226 template <typename T>
227 struct is_radix_sortable<T, void_if_t<std::is_enum<T>::value>>
228  : std::true_type {};
229 
230 template <std::size_t B>
231 struct is_radix_sortable<std::bitset<B>, void> : std::true_type {};
232 
233 template <typename T>
235  T, void_if_t<is_linear_container_v<
236  T> and std::is_integral<typename T::value_type>::value>>
237  : std::true_type {};
238 
239 template <typename T>
241 
242 #if __cpp_lib_byte
243 template <typename T>
244 constexpr bool is_byte_v
245  = std::is_same<typename std::remove_cv<T>::type, std::byte>::value;
246 #else
247 template <typename T>
248 constexpr bool is_byte_v = false;
249 #endif
250 
251 template <typename T>
252 KBLIB_NODISCARD constexpr auto byte_count(T) noexcept
253  -> enable_if_t<std::is_integral<T>::value, std::size_t> {
254  auto res
255  = kblib::div(kblib::bits_of<T> + std::is_signed<T>::value, CHAR_BIT);
256  return to_unsigned(res.quot + (res.rem != 0));
257 }
258 template <typename T>
259 KBLIB_NODISCARD constexpr auto byte_count(T) noexcept
260  -> enable_if_t<std::is_enum<T>::value, std::size_t> {
261  using U = typename std::underlying_type<T>::type;
262  auto res
263  = kblib::div(kblib::bits_of<U> + std::is_signed<U>::value, CHAR_BIT);
264  return to_unsigned(res.quot + (res.rem != 0));
265 }
266 template <typename T>
267 KBLIB_NODISCARD constexpr auto byte_count(T*) noexcept -> std::size_t {
268  return byte_count(std::uintptr_t{});
269 }
270 template <typename T>
271 KBLIB_NODISCARD constexpr auto byte_count(const std::unique_ptr<T>&) noexcept
272  -> std::size_t {
273  return byte_count(std::uintptr_t{});
274 }
275 template <typename T>
276 KBLIB_NODISCARD constexpr auto byte_count(const T& x) noexcept -> enable_if_t<
277  is_linear_container_v<
278  T> and (std::is_integral<typename T::value_type>::value or is_byte_v<T>)
279  and sizeof(typename T::value_type) == 1,
280  std::size_t> {
281  return fakestd::size(x);
282 }
283 template <typename T>
284 constexpr auto byte_count(const T& x) noexcept -> enable_if_t<
285  is_linear_container_v<T> and std::is_integral<typename T::value_type>::value
286  and (sizeof(typename T::value_type) > 1),
287  std::size_t> {
288  using value_type = typename T::value_type;
289  return fakestd::size(x) * byte_count(value_type{});
290 }
291 
292 // Can be used to detect unsupported types with overload resolution.
293 
294 // cert-dcl50-cpp: An exception to the rule for defining as deleted is not
295 // implemented by clang-tidy. This definition does not pose a security risk.
296 constexpr auto byte_count(...) -> void = delete;
297 
298 template <typename T>
299 KBLIB_NODISCARD constexpr auto get_byte_index(T x, std::size_t idx) noexcept
300  -> enable_if_t<std::is_integral<T>::value, unsigned char> {
301  return static_cast<unsigned char>(x >> (idx * CHAR_BIT));
302 }
303 template <typename T>
304 KBLIB_NODISCARD constexpr auto get_byte_index(const T& x,
305  std::size_t idx) noexcept
306  -> enable_if_t<std::is_enum<T>::value, unsigned char> {
307  return static_cast<unsigned char>(etoi(x) >> (idx * CHAR_BIT));
308 }
309 // Note that the ordering created by casting to std::uintptr_t may not agree
310 // with the ordering imposed by std::less<T*>.
311 template <typename T>
312 KBLIB_NODISCARD auto get_byte_index(T* x, std::size_t idx) noexcept
313  -> unsigned char {
314  return get_byte_index(byte_cast<std::uintptr_t>(x), idx);
315 }
316 template <typename T>
317 KBLIB_NODISCARD auto get_byte_index(const std::unique_ptr<T>& x,
318  std::size_t idx) noexcept -> unsigned char {
319  return get_byte_index(byte_cast<std::uintptr_t>(x.get()), idx);
320 }
321 template <typename T>
322 KBLIB_NODISCARD constexpr auto
323 get_byte_index(const T& x, std::size_t idx) noexcept -> enable_if_t<
324  is_linear_container_v<
325  T> and (std::is_integral<typename T::value_type>::value or is_byte_v<T>)
326  and sizeof(typename T::value_type) == 1,
327  unsigned char> {
328  return static_cast<unsigned char>(x[idx]);
329 }
330 template <typename T>
331 KBLIB_NODISCARD constexpr auto get_byte_index(const T& x,
332  std::size_t idx) noexcept
333  -> enable_if_t<is_linear_container_v<
334  T> and std::is_integral<typename T::value_type>::value
335  and (sizeof(typename T::value_type) > 1),
336  unsigned char> {
337  using value_type = typename T::value_type;
338  auto bytes_per = byte_count(value_type{});
339  return static_cast<unsigned char>(to_unsigned(x[idx / bytes_per])
340  >> (idx % bytes_per * CHAR_BIT));
341 }
342 template <typename T>
343 KBLIB_NODISCARD constexpr auto get_byte_index(const T& x,
344  std::size_t idx) noexcept
345  -> enable_if_t<is_linear_container_v<
346  T> and std::is_enum<typename T::value_type>::value,
347  unsigned char> {
348  using U = typename std::underlying_type<typename T::U>::type;
349  auto bytes_per = byte_count(U{});
350  return static_cast<unsigned char>(to_unsigned(etoi(x[idx / bytes_per]))
351  >> (idx % bytes_per * CHAR_BIT));
352 }
353 
354 template <typename T>
356  : bool_constant<std::is_member_object_pointer<T>::value> {};
357 
358 template <>
359 struct is_trivial_transformation<identity> : std::true_type {};
360 
361 namespace detail_sort {
362 
363  template <typename RandomAccessIt, typename Compare>
364  constexpr auto sort(RandomAccessIt, const RandomAccessIt, Compare) -> void {}
365  template <typename RandomAccessIt, typename Compare>
366  constexpr auto stable_sort(RandomAccessIt, const RandomAccessIt, Compare)
367  -> void {}
368 
369  template <typename RandomAccessIt, typename Compare, std::size_t small_size>
370  constexpr auto merge_sort(RandomAccessIt begin, const RandomAccessIt end,
371  Compare cmp) -> void {
372  if (end - begin <= small_size) {
373  insertion_sort(begin, end, cmp);
374  return;
375  } else {
376  auto middle = begin + (end - begin) / 2;
377  merge_sort(begin, middle, cmp);
378  merge_sort(middle, end, cmp);
379  std::inplace_merge(begin, middle, end, cmp);
380  return;
381  }
382  }
383 
384  template <typename RandomAccessIt, typename Compare, std::size_t small_size>
385  constexpr auto heap_sort(RandomAccessIt begin, const RandomAccessIt end,
386  Compare cmp) -> void {
387  std::make_heap(begin, end, cmp);
388  while (begin != end) {
389  std::pop_heap(begin, end--, cmp);
390  }
391  return;
392  }
393 
395 
396  template <sort_direction dir, typename RandomAccessIt, typename Projection>
397  constexpr auto radix_sort_i(RandomAccessIt begin, const RandomAccessIt end,
398  Projection proj) -> void {
399  using E = decay_t<decltype(proj(*begin))>;
400  const auto max_bytes = byte_count(E{});
401  for (const auto byte : range(max_bytes)) {
402  for (auto it = begin; it != end; ++it) {
403  }
404  }
405  }
406  template <sort_direction dir, typename RandomAccessIt, typename Projection>
407  constexpr auto radix_sort_s(RandomAccessIt begin, const RandomAccessIt end,
408  Projection proj) -> void {
409  if (begin != end) {
410  const auto max_bytes = kblib::accumulate(
411  begin, end, std::size_t{}, [&](auto m, const auto& el) {
412  return max(m, byte_count(proj(*el)));
413  });
414  }
415  const auto max_bytes = [&] {
416  std::size_t max_bytes{};
417  for (const auto v : indirect(begin, end)) {
418  max_bytes = max(max_bytes, byte_count(v));
419  }
420  return max_bytes;
421  }();
422  }
423 
424  template <std::size_t size>
425  constexpr auto make_array_for(std::false_type)
427  return {};
428  }
429  template <std::size_t size>
430  auto make_array_for(std::true_type)
432  return {in_place_agg};
433  }
434 
435  template <sort_direction dir, typename RandomAccessIt1,
436  typename RandomAccessIt2, typename Projection>
437  constexpr auto counting_sort(RandomAccessIt1 begin,
438  const RandomAccessIt1 end,
439  RandomAccessIt2 d_begin, Projection proj)
440  -> void {
441  using E = decay_t<decltype(proj(*begin))>;
442  constexpr auto size = std::numeric_limits<std::make_unsigned_t<E>>::max();
443  auto count = make_array_for<size>(bool_constant<(size > 256)>{});
444 
445  for (auto cur = begin; cur != end; ++cur) {
446  ++count->at(proj(*cur));
447  }
448  kblib::transform_exclusive_scan(begin(*count), end(*count), begin(*count),
449  std::size_t{}, std::plus<>{}, proj);
450 
451  for (auto cur = end; cur != begin; --cur) {
452  auto el = std::prev(cur);
453  d_begin[--count->at(proj(*el))] = *el;
454  }
455 
456  return;
457  }
458 
464  template <typename RandomAccessIt, typename UnaryOperation,
465  typename BinaryPredicate, typename SortKey,
466  std::size_t small_size = 8,
468  bool = std::is_fundamental<SortKey>::value,
469  bool = is_radix_sortable_v<SortKey>,
470  bool = std::is_integral<SortKey>::value>
472  static constexpr auto inplace(RandomAccessIt begin,
473  const RandomAccessIt end,
474  UnaryOperation&& transform,
475  BinaryPredicate&& compare) -> void {
476  auto comp
477  = [&compare, &transform](RandomAccessIt a, RandomAccessIt b) {
478  return kblib::invoke(compare, kblib::invoke(transform, *a),
479  kblib::invoke(transform, *b));
480  };
481  if (end - begin < small_size) {
482  insertion_sort(begin, end, comp);
483  return;
484  } else {
486  }
487  }
488 
489  static constexpr auto scratch(RandomAccessIt begin,
490  const RandomAccessIt end,
491  UnaryOperation&& transform,
492  BinaryPredicate&& compare) -> void {
493  auto comp
494  = [&compare, &transform](RandomAccessIt a, RandomAccessIt b) {
495  return kblib::invoke(compare, kblib::invoke(transform, *a),
496  kblib::invoke(transform, *b));
497  };
498  if (end - begin < small_size) {
499  insertion_sort(begin, end, comp);
500  return;
501  } else {
503  }
504  }
505 
506  template <typename RandomAccessIt2>
507  static constexpr auto copy(RandomAccessIt begin, const RandomAccessIt end,
508  RandomAccessIt2 d_begin, RandomAccessIt2 d_end,
509  UnaryOperation&& transform,
510  BinaryPredicate&& compare) -> void {
511  auto comp
512  = [&compare, &transform](RandomAccessIt a, RandomAccessIt b) {
513  return kblib::invoke(compare, kblib::invoke(transform, *a),
514  kblib::invoke(transform, *b));
515  };
516  if (end - begin < small_size) {
517  insertion_sort_copy(begin, end, d_begin, d_end, comp);
518  return;
519  } else {
521  }
522  }
523  };
524 
525 #if 1
531  template <typename RandomAccessIt, typename UnaryOperation,
532  typename BinaryPredicate, typename SortKey, std::size_t small_size>
533  struct sort_transform_impl<RandomAccessIt, UnaryOperation, BinaryPredicate,
534  SortKey, small_size, true, false, false, false> {
535  static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
536  KBLIB_UNUSED const RandomAccessIt end,
537  KBLIB_UNUSED UnaryOperation&& transform,
538  KBLIB_UNUSED BinaryPredicate&& compare)
539  -> void {
540  auto comp
541  = [&compare, &transform](RandomAccessIt a, RandomAccessIt b) {
542  return kblib::invoke(compare, kblib::invoke(transform, *a),
543  kblib::invoke(transform, *b));
544  };
546  }
547  };
548 #endif
549 
555  template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
556  typename SortKey, std::size_t small_size>
557  struct sort_transform_impl<RandomAccessIt, UnaryOperation, std::less<LessT>,
558  SortKey, small_size, true, true, false, false> {
559  static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
560  KBLIB_UNUSED const RandomAccessIt end,
561  KBLIB_UNUSED UnaryOperation&& transform,
562  KBLIB_UNUSED std::less<LessT>&& compare)
563  -> void {
565  }
566  };
572  template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
573  typename SortKey, std::size_t small_size>
574  struct sort_transform_impl<RandomAccessIt, UnaryOperation,
575  std::greater<LessT>, SortKey, small_size, true,
576  true, false, false> {
577  static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
578  KBLIB_UNUSED const RandomAccessIt end,
579  KBLIB_UNUSED UnaryOperation&& transform,
580  KBLIB_UNUSED std::greater<LessT>&& compare)
581  -> void {
583  }
584  };
585 
590  template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
591  typename SortKey, std::size_t small_size>
592  struct sort_transform_impl<RandomAccessIt, UnaryOperation, std::less<LessT>,
593  SortKey, small_size, true, true, true, true> {
594  static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
595  KBLIB_UNUSED const RandomAccessIt end,
596  KBLIB_UNUSED UnaryOperation&& transform,
597  KBLIB_UNUSED std::less<LessT>&& compare)
598  -> void {
600  }
601  };
606  template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
607  typename SortKey, std::size_t small_size>
608  struct sort_transform_impl<RandomAccessIt, UnaryOperation,
609  std::greater<LessT>, SortKey, small_size, true,
610  true, true, true> {
611  static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
612  KBLIB_UNUSED const RandomAccessIt end,
613  KBLIB_UNUSED UnaryOperation&& transform,
614  KBLIB_UNUSED std::greater<LessT>&& compare)
615  -> void {
617  }
618  };
619 
620 #if 1 // Do string radix sorting
625  template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
626  typename SortKey, std::size_t small_size, bool M>
627  struct sort_transform_impl<RandomAccessIt, UnaryOperation, std::less<LessT>,
628  SortKey, small_size, M, false, true, false> {
629  static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
630  KBLIB_UNUSED const RandomAccessIt end,
631  KBLIB_UNUSED UnaryOperation&& transform,
632  KBLIB_UNUSED std::less<LessT>&& compare)
633  -> void {
635  }
636  };
641  template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
642  typename SortKey, std::size_t small_size, bool M>
643  struct sort_transform_impl<RandomAccessIt, UnaryOperation,
644  std::greater<LessT>, SortKey, small_size, M,
645  false, true, false> {
646  static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
647  KBLIB_UNUSED const RandomAccessIt end,
648  KBLIB_UNUSED UnaryOperation&& transform,
649  KBLIB_UNUSED std::greater<LessT>&& compare)
650  -> void {
652  }
653  };
654 #endif
655 } // namespace detail_sort
656 
672 template <typename RandomAccessIt, typename UnaryOperation,
673  typename BinaryPredicate>
674 constexpr auto sort_transform(RandomAccessIt begin, RandomAccessIt end,
675  UnaryOperation&& transform,
676  BinaryPredicate&& compare) -> void {
678  RandomAccessIt, UnaryOperation, BinaryPredicate,
679  decltype(kblib::invoke(transform, *begin))>::
680  inplace(begin, end, std::forward<UnaryOperation>(transform),
681  std::forward<BinaryPredicate>(compare));
682 }
683 
690 template <typename RandomAccessIt, typename UnaryOperation>
691 constexpr auto sort_transform(RandomAccessIt begin, RandomAccessIt end,
692  UnaryOperation&& transform) -> void {
694  RandomAccessIt, UnaryOperation, std::less<>,
695  decltype(kblib::invoke(transform,
696  *begin))>::inplace(begin, end,
697  std::forward<UnaryOperation>(
698  transform),
699  std::less<>{});
700 }
701 
714 template <typename RandomAccessIt, typename BinaryPredicate>
715 constexpr auto sort(RandomAccessIt begin, RandomAccessIt end,
716  BinaryPredicate&& compare) -> void {
718  RandomAccessIt, identity, BinaryPredicate,
719  decltype(kblib::invoke(transform,
720  *begin))>::inplace(begin, end, identity{},
721  std::forward<BinaryPredicate>(
722  compare));
723 }
724 
730 template <typename RandomAccessIt>
731 constexpr auto sort(RandomAccessIt begin, RandomAccessIt end) -> void {
733  RandomAccessIt, identity, std::less<>,
734  decltype(kblib::invoke(transform, *begin))>::inplace(begin, end,
735  identity{},
736  std::less<>{});
737 }
738 
739 } // namespace kblib
740 
741 #endif // SORT_H
Provides general-purpose algorithms, similar to the <algorithms> header.
Provides bit-manipulation functions and classes.
This header provides some features of C++17 <type_traits> and other headers for C++14,...
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
constexpr auto merge_sort(RandomAccessIt begin, const RandomAccessIt end, Compare cmp) -> void
Definition: sort.h:370
constexpr auto counting_sort(RandomAccessIt1 begin, const RandomAccessIt1 end, RandomAccessIt2 d_begin, Projection proj) -> void
Definition: sort.h:437
constexpr auto radix_sort_i(RandomAccessIt begin, const RandomAccessIt end, Projection proj) -> void
Definition: sort.h:397
constexpr auto heap_sort(RandomAccessIt begin, const RandomAccessIt end, Compare cmp) -> void
Definition: sort.h:385
constexpr auto make_array_for(std::false_type) -> kblib::containing_ptr< std::array< std::size_t, size >>
Definition: sort.h:425
constexpr auto sort(RandomAccessIt, const RandomAccessIt, Compare) -> void
Definition: sort.h:364
constexpr auto radix_sort_s(RandomAccessIt begin, const RandomAccessIt end, Projection proj) -> void
Definition: sort.h:407
constexpr auto stable_sort(RandomAccessIt, const RandomAccessIt, Compare) -> void
Definition: sort.h:366
constexpr auto size(const C &c) -> decltype(c.size())
Definition: fakestd.h:365
constexpr struct kblib::nums::max_t max
The main namespace in which all entities from kblib are defined.
Definition: algorithm.h:44
constexpr auto size(const C &c) -> decltype(c.size())
Definition: fakestd.h:1069
constexpr auto a(const std::initializer_list< T > &a) -> auto
Index an array literal without naming its type.
Definition: simple.h:255
typename std::enable_if< B, T >::type enable_if_t
Definition: fakestd.h:54
constexpr auto byte_count(T) noexcept -> enable_if_t< std::is_integral< T >::value, std::size_t >
Definition: sort.h:252
constexpr auto insertion_sort(const RandomAccessIt begin, const RandomAccessIt end, Compare &&compare={}) noexcept(noexcept(swap(*begin, *begin)) and noexcept(compare(*begin, *begin))) -> void
In-place insertion sort. As is usual, it is stable. Provides as a guarantee that it will perform no m...
Definition: sort.h:57
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 insertion_sort_copy(const RandomAccessIt begin, const RandomAccessIt end, const RandomAccessIt2 d_begin, const RandomAccessIt2 d_end, Compare &&compare={}) noexcept(noexcept(detail_algorithm::shift_backward(d_begin, d_begin, d_end)) and noexcept(*d_begin= *begin)) -> void
Out-of-place insertion sort, which does not modify the input. Provides as a guarantee that it will pe...
Definition: sort.h:93
constexpr auto adaptive_insertion_sort_copy(const RandomAccessIt begin, const RandomAccessIt end, const RandomAccessIt2 d_begin, const RandomAccessIt2 d_end, Compare &&compare={}) noexcept(noexcept(detail_algorithm::shift_backward(d_begin, d_begin, d_end)) and noexcept(*d_begin= *begin)) -> void
An adaptive sort which, at the cost of some additional work (time complexity Θ(sqrt(n))),...
Definition: sort.h:178
constexpr auto range(Value min, Value max, Delta step=0) -> range_t< Value, Delta >
Constructs a range from beginning, end, and step amount. The range is half-open, that is min is in th...
Definition: iterators.h:620
constexpr auto sort_transform(RandomAccessIt begin, RandomAccessIt end, UnaryOperation &&transform, BinaryPredicate &&compare) -> void
Sorts a range after applying a transformation.
Definition: sort.h:674
constexpr auto indirect(Iter1 begin, Iter2 end) noexcept(noexcept(indirect_range< Iter1, Iter2 >{begin, end})) -> indirect_range< Iter1, Iter2 >
Create a range from an iterator pair. Primarily useful for range-for loops.
Definition: iterators.h:1059
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
typename std::decay< T >::type decay_t
Definition: fakestd.h:57
constexpr auto transform_exclusive_scan(InputIt first, EndIt last, OutputIt d_first, T init, BinaryAccumulation accum, UnaryTransform proj) -> OutputIt
Definition: algorithm.h:251
std::integral_constant< bool, v > bool_constant
Definition: fakestd.h:64
typename void_if< b >::type void_if_t
Definition: fakestd.h:512
constexpr bool is_radix_sortable_v
Definition: sort.h:240
constexpr auto div(T num, U den) noexcept -> decltype(std::div(num, den))
Definition: stats.h:48
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 bool is_byte_v
Definition: sort.h:248
constexpr auto etoi(E e) -> auto
Definition: convert.h:244
constexpr auto sort(RandomAccessIt begin, RandomAccessIt end, BinaryPredicate &&compare) -> void
Sorts a range.
Definition: sort.h:715
constexpr auto get_byte_index(T x, std::size_t idx) noexcept -> enable_if_t< std::is_integral< T >::value, unsigned char >
Definition: sort.h:299
constexpr struct kblib::in_place_agg_t in_place_agg
constexpr auto to_unsigned(I x) -> std::make_unsigned_t< I >
Cast integral argument to corresponding unsigned type.
Definition: fakestd.h:585
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
Provides general utilities which do not fit in any more specific header.
A smart pointer to an object contained inside the smart pointer object.
Definition: iterators.h:1108
static constexpr auto inplace([[maybe_unused]] RandomAccessIt begin, [[maybe_unused]] const RandomAccessIt end, [[maybe_unused]] UnaryOperation &&transform, [[maybe_unused]] std::less< LessT > &&compare) -> void
Definition: sort.h:594
static constexpr auto inplace([[maybe_unused]] RandomAccessIt begin, [[maybe_unused]] const RandomAccessIt end, [[maybe_unused]] UnaryOperation &&transform, [[maybe_unused]] std::greater< LessT > &&compare) -> void
Definition: sort.h:577
static constexpr auto inplace([[maybe_unused]] RandomAccessIt begin, [[maybe_unused]] const RandomAccessIt end, [[maybe_unused]] UnaryOperation &&transform, [[maybe_unused]] std::greater< LessT > &&compare) -> void
Definition: sort.h:646
static constexpr auto inplace([[maybe_unused]] RandomAccessIt begin, [[maybe_unused]] const RandomAccessIt end, [[maybe_unused]] UnaryOperation &&transform, [[maybe_unused]] BinaryPredicate &&compare) -> void
Definition: sort.h:535
static constexpr auto inplace([[maybe_unused]] RandomAccessIt begin, [[maybe_unused]] const RandomAccessIt end, [[maybe_unused]] UnaryOperation &&transform, [[maybe_unused]] std::greater< LessT > &&compare) -> void
Definition: sort.h:611
static constexpr auto inplace([[maybe_unused]] RandomAccessIt begin, [[maybe_unused]] const RandomAccessIt end, [[maybe_unused]] UnaryOperation &&transform, [[maybe_unused]] std::less< LessT > &&compare) -> void
Definition: sort.h:559
static constexpr auto inplace([[maybe_unused]] RandomAccessIt begin, [[maybe_unused]] const RandomAccessIt end, [[maybe_unused]] UnaryOperation &&transform, [[maybe_unused]] std::less< LessT > &&compare) -> void
Definition: sort.h:629
Sort data after applying an arbitrary transformation to it. The primary template handles the general ...
Definition: sort.h:471
static constexpr auto scratch(RandomAccessIt begin, const RandomAccessIt end, UnaryOperation &&transform, BinaryPredicate &&compare) -> void
Definition: sort.h:489
static constexpr auto inplace(RandomAccessIt begin, const RandomAccessIt end, UnaryOperation &&transform, BinaryPredicate &&compare) -> void
Definition: sort.h:472
static constexpr auto copy(RandomAccessIt begin, const RandomAccessIt end, RandomAccessIt2 d_begin, RandomAccessIt2 d_end, UnaryOperation &&transform, BinaryPredicate &&compare) -> void
Definition: sort.h:507
The identity function, as a function object.
Definition: simple.h:206
#define KBLIB_UNUSED
This internal macro is used to provide a fallback for [[maybe_unused]] in C++14.
Definition: tdecl.h:92
#define KBLIB_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:81