kblib  0.2.3
General utilities library for modern C++
stats.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 KBLIB_STATS_H
32 #define KBLIB_STATS_H
33 
34 #include <array>
35 #include <cassert>
36 #include <cinttypes>
37 #include <cstdlib>
38 #include <limits>
39 #include <numeric>
40 
41 #include "fakestd.h"
42 #include "logic.h"
43 #include "tdecl.h"
44 
45 namespace kblib {
46 
47 template <typename T, typename U>
48 KBLIB_NODISCARD constexpr auto div(T num, U den) noexcept
49  -> decltype(std::div(num, den)) {
50  decltype(std::div(num, den)) ret{};
51  ret.quot = num / den;
52  ret.rem = num % den;
53  return ret;
54 }
55 
60 template <typename T>
61 struct trivial_pair {
62  T first;
63  T second;
64 };
65 
66 #if 0 and KBLIB_USE_CXX17
67 
74 template <typename T, std::size_t N>
75 using trivial_array = std::array<T, N>;
76 
77 #else
78 
83 template <typename T, std::size_t N>
84 struct trivial_array {
85  T arr[N];
86  KBLIB_NODISCARD constexpr auto operator[](std::size_t n) -> T& {
87  return arr[n];
88  }
89  KBLIB_NODISCARD constexpr auto operator[](std::size_t n) const -> const T& {
90  return arr[n];
91  }
92  KBLIB_NODISCARD constexpr auto size() const -> std::size_t { return N; }
93  KBLIB_NODISCARD constexpr auto begin() & noexcept -> T* { return arr; }
94  KBLIB_NODISCARD constexpr auto begin() const& noexcept -> const T* {
95  return arr;
96  }
97  KBLIB_NODISCARD constexpr auto end() & noexcept -> T* { return arr + N; }
98  KBLIB_NODISCARD constexpr auto end() const& noexcept -> const T* {
99  return arr + N;
100  }
101 
102  KBLIB_NODISCARD constexpr friend auto operator==(
103  const trivial_array& a, const trivial_array& b) noexcept -> bool {
104  return equal(a.begin(), a.end(), b.begin());
105  }
106  KBLIB_NODISCARD constexpr friend auto operator!=(
107  const trivial_array& a, const trivial_array& b) noexcept -> bool {
108  return not (a == b);
109  }
110 };
111 
112 #endif
113 
131 template <typename U>
132 KBLIB_NODISCARD constexpr auto calc_fib_size() noexcept -> std::size_t {
133  static_assert(std::is_unsigned<U>::value, "U must be unsigned");
134  std::size_t n{};
135  trivial_pair<U> state{0, 1};
136  U& a = state.first;
137  U& b = state.second;
138  while (b >= a) {
139  state = {b, static_cast<U>(a + b)};
140  ++n;
141  }
142  return n;
143 }
144 
155 template <typename U, std::size_t N = calc_fib_size<U>() + 1>
156 KBLIB_NODISCARD constexpr auto make_fib_arr() noexcept -> trivial_array<U, N> {
157  static_assert(
158  implies<(N > calc_fib_size<U>()), std::is_unsigned<U>::value>::value,
159  "signed U with large N would trigger signed overflow");
160  // Initialize the first two elements of the array
161  trivial_array<U, N> ret{{0, 1}};
162  // A loop initializes the rest
163  for (std::size_t i = 2; i < N; ++i) {
164  ret[i] = ret[i - 1] + ret[i - 2];
165  }
166  return ret;
167 }
168 
176 template <typename U = std::uintmax_t>
177 KBLIB_NODISCARD constexpr auto fibonacci(int n) noexcept -> U {
178  constexpr auto arr = make_fib_arr<U>();
179  assert(n >= 0 and static_cast<std::size_t>(n) < arr.size());
180  return arr[to_unsigned(n)];
181 }
182 
183 inline namespace nums {
194  constexpr struct max_t {
195  template <typename T>
196  constexpr /* implicit*/ operator T() const
197  noexcept(noexcept(std::numeric_limits<T>::max())) {
199  }
200  template <typename T>
201  KBLIB_NODISCARD constexpr static auto of() noexcept(
202  noexcept(std::numeric_limits<T>::max())) {
204  }
205 
209  template <typename L, typename R>
210  KBLIB_NODISCARD constexpr auto operator()(L&& lhs, R&& rhs) const noexcept
211  -> decltype(auto) {
212  return std::less<>{}(lhs, rhs) ? std::forward<R>(rhs)
213  : std::forward<L>(lhs);
214  }
215 
216  KBLIB_NODISCARD constexpr inline friend auto operator==(max_t, max_t)
217  -> std::true_type {
218  return {};
219  }
220  KBLIB_NODISCARD constexpr inline friend auto operator!=(max_t, max_t)
221  -> std::false_type {
222  return {};
223  }
224  KBLIB_NODISCARD constexpr inline friend auto operator<(max_t, max_t)
225  -> std::false_type {
226  return {};
227  }
228  KBLIB_NODISCARD constexpr inline friend auto operator>(max_t, max_t)
229  -> std::false_type {
230  return {};
231  }
232  KBLIB_NODISCARD constexpr inline friend auto operator<=(max_t, max_t)
233  -> std::true_type {
234  return {};
235  }
236  KBLIB_NODISCARD constexpr inline friend auto operator>=(max_t, max_t)
237  -> std::true_type {
238  return {};
239  }
240 
241  template <typename T>
242  KBLIB_NODISCARD constexpr friend auto operator==(T t, max_t) -> bool {
243  return t == of<T>();
244  }
245  template <typename T>
246  KBLIB_NODISCARD constexpr friend auto operator==(max_t, T t) -> bool {
247  return t == of<T>();
248  }
249  template <typename T>
250  KBLIB_NODISCARD constexpr friend auto operator!=(T t, max_t) -> bool {
251  return t != of<T>();
252  }
253  template <typename T>
254  KBLIB_NODISCARD constexpr friend auto operator!=(max_t, T t) -> bool {
255  return t != of<T>();
256  }
257 
258  template <typename T>
259  KBLIB_NODISCARD constexpr friend auto operator<(T t, max_t) -> bool {
260  return t < of<T>();
261  }
262  template <typename T>
263  KBLIB_NODISCARD constexpr friend auto operator<(max_t, T t) -> bool {
264  return of<T>() < t;
265  }
266  template <typename T>
267  KBLIB_NODISCARD constexpr friend auto operator>(T t, max_t) -> bool {
268  return t > of<T>();
269  }
270  template <typename T>
271  KBLIB_NODISCARD constexpr friend auto operator>(max_t, T t) -> bool {
272  return of<T>() > t;
273  }
274 
275  template <typename T>
276  KBLIB_NODISCARD constexpr friend auto operator<=(T t, max_t) -> bool {
277  return t <= of<T>();
278  }
279  template <typename T>
280  KBLIB_NODISCARD constexpr friend auto operator<=(max_t, T t) -> bool {
281  return of<T>() <= t;
282  }
283  template <typename T>
284  KBLIB_NODISCARD constexpr friend auto operator>=(T t, max_t) -> bool {
285  return t >= of<T>();
286  }
287  template <typename T>
288  KBLIB_NODISCARD constexpr friend auto operator>=(max_t, T t) -> bool {
289  return of<T>() >= t;
290  }
291 
292  } max;
304  constexpr struct min_t {
305  template <typename T>
306  constexpr /* implicit*/ operator T() const
307  noexcept(noexcept(std::numeric_limits<T>::min())) {
309  }
310  template <typename T>
311  KBLIB_NODISCARD constexpr static auto of() noexcept(
312  noexcept(std::numeric_limits<T>::min())) {
314  }
315 
319  template <typename L, typename R>
320  KBLIB_NODISCARD constexpr auto operator()(L&& lhs, R&& rhs) const noexcept
321  -> decltype(auto) {
322  return std::less<>{}(lhs, rhs) ? std::forward<R>(lhs)
323  : std::forward<L>(rhs);
324  }
325 
326  template <typename T>
327  KBLIB_NODISCARD constexpr friend auto operator==(T t, min_t) -> bool {
328  return t == of<T>();
329  }
330  template <typename T>
331  KBLIB_NODISCARD constexpr friend auto operator==(min_t, T t) -> bool {
332  return t == of<T>();
333  }
334  template <typename T>
335  KBLIB_NODISCARD constexpr friend auto operator!=(T t, min_t) -> bool {
336  return t != of<T>();
337  }
338  template <typename T>
339  KBLIB_NODISCARD constexpr friend auto operator!=(min_t, T t) -> bool {
340  return t != of<T>();
341  }
342 
343  template <typename T>
344  KBLIB_NODISCARD constexpr friend auto operator<(T t, min_t) -> bool {
345  return t < of<T>();
346  }
347  template <typename T>
348  KBLIB_NODISCARD constexpr friend auto operator<(min_t, T t) -> bool {
349  return of<T>() < t;
350  }
351  template <typename T>
352  KBLIB_NODISCARD constexpr friend auto operator>(T t, min_t) -> bool {
353  return t > of<T>();
354  }
355  template <typename T>
356  KBLIB_NODISCARD constexpr friend auto operator>(min_t, T t) -> bool {
357  return of<T>() > t;
358  }
359 
360  template <typename T>
361  KBLIB_NODISCARD constexpr friend auto operator<=(T t, min_t) -> bool {
362  return t <= of<T>();
363  }
364  template <typename T>
365  KBLIB_NODISCARD constexpr friend auto operator<=(min_t, T t) -> bool {
366  return of<T>() <= t;
367  }
368  template <typename T>
369  KBLIB_NODISCARD constexpr friend auto operator>=(T t, min_t) -> bool {
370  return t >= of<T>();
371  }
372  template <typename T>
373  KBLIB_NODISCARD constexpr friend auto operator>=(min_t, T t) -> bool {
374  return of<T>() >= t;
375  }
376 
377  KBLIB_NODISCARD constexpr inline friend auto operator==(min_t, min_t)
378  -> std::true_type {
379  return {};
380  }
381  KBLIB_NODISCARD constexpr inline friend auto operator!=(min_t, min_t)
382  -> std::false_type {
383  return {};
384  }
385  KBLIB_NODISCARD constexpr inline friend auto operator<(min_t, min_t)
386  -> std::false_type {
387  return {};
388  }
389  KBLIB_NODISCARD constexpr inline friend auto operator>(min_t, min_t)
390  -> std::false_type {
391  return {};
392  }
393  KBLIB_NODISCARD constexpr inline friend auto operator<=(min_t, min_t)
394  -> std::true_type {
395  return {};
396  }
397  KBLIB_NODISCARD constexpr inline friend auto operator>=(min_t, min_t)
398  -> std::true_type {
399  return {};
400  }
401 
402  KBLIB_NODISCARD constexpr inline friend auto operator==(max_t, min_t)
403  -> std::false_type {
404  return {};
405  }
406  KBLIB_NODISCARD constexpr inline friend auto operator==(min_t, max_t)
407  -> std::false_type {
408  return {};
409  }
410  KBLIB_NODISCARD constexpr inline friend auto operator!=(max_t, min_t)
411  -> std::true_type {
412  return {};
413  }
414  KBLIB_NODISCARD constexpr inline friend auto operator!=(min_t, max_t)
415  -> std::true_type {
416  return {};
417  }
418  KBLIB_NODISCARD constexpr inline friend auto operator<(max_t, min_t)
419  -> std::false_type {
420  return {};
421  }
422  KBLIB_NODISCARD constexpr inline friend auto operator<(min_t, max_t)
423  -> std::true_type {
424  return {};
425  }
426  KBLIB_NODISCARD constexpr inline friend auto operator>(max_t, min_t)
427  -> std::true_type {
428  return {};
429  }
430  KBLIB_NODISCARD constexpr inline friend auto operator>(min_t, max_t)
431  -> std::false_type {
432  return {};
433  }
434  KBLIB_NODISCARD constexpr inline friend auto operator<=(max_t, min_t)
435  -> std::false_type {
436  return {};
437  }
438  KBLIB_NODISCARD constexpr inline friend auto operator<=(min_t, max_t)
439  -> std::true_type {
440  return {};
441  }
442  KBLIB_NODISCARD constexpr inline friend auto operator>=(max_t, min_t)
443  -> std::true_type {
444  return {};
445  }
446  KBLIB_NODISCARD constexpr inline friend auto operator>=(min_t, max_t)
447  -> std::false_type {
448  return {};
449  }
450 
451  } min;
454 } // namespace nums
455 
456 template <typename T = double>
457 KBLIB_NODISCARD constexpr auto pi() -> T {
458  return 3.1415926535897932384626433832795028841971693993751l;
459 }
460 template <typename T = double>
461 KBLIB_NODISCARD constexpr auto tau() -> T {
462  return 2 * pi<T>;
463 }
464 template <typename T = double>
465 KBLIB_NODISCARD constexpr auto e() -> T {
466  return 2.7182818284590452353602874713526624977572470937000l;
467 }
468 template <typename T = double>
469 KBLIB_NODISCARD constexpr auto root_2() -> T {
470  return 1.4142135623730950488016887242096980785696718753769l;
471 }
472 template <typename T = double>
473 KBLIB_NODISCARD constexpr auto phi() -> T {
474  return 1.6180339887498948482045868343656381177203091798058l;
475 }
476 
477 // saturating to_unsigned
478 template <typename A, typename F>
479 KBLIB_NODISCARD constexpr auto saturating_cast(F x) noexcept
480  -> enable_if_t<std::is_integral<A>::value and std::is_integral<F>::value
481  and std::is_unsigned<A>::value,
482  A> {
483  if (x < 0) {
484  return 0;
485  } else if (to_unsigned(x) > A(max)) {
486  return max;
487  } else {
488  return static_cast<A>(x);
489  }
490 }
491 
492 // saturating to_signed(signed)
493 template <typename A, typename F>
494 KBLIB_NODISCARD constexpr auto saturating_cast(F x) noexcept
495  -> enable_if_t<std::is_integral<A>::value and std::is_integral<F>::value
496  and std::is_signed<A>::value
497  and std::is_signed<F>::value,
498  A> {
499  if (x < A(min)) {
500  return min;
501  } else if (to_unsigned(x) > A(max)) {
502  return max;
503  } else {
504  return x;
505  }
506 }
507 // saturating to_signed(unsigned)
508 template <typename A, typename F>
509 KBLIB_NODISCARD constexpr auto saturating_cast(F x) noexcept
510  -> enable_if_t<std::is_integral<A>::value and std::is_integral<F>::value
511  and std::is_signed<A>::value
512  and std::is_unsigned<F>::value,
513  A> {
514  if (x > to_unsigned(A(max))) {
515  return max;
516  } else {
517  return x;
518  }
519 }
520 
523 
533 template <typename T, typename F>
534 KBLIB_NODISCARD constexpr auto quantize_step(F low, F delta, F val) noexcept
535  -> T {
536  static_assert(std::is_unsigned<T>::value, "Destination must be unsigned.");
537  return static_cast<T>((val - low) * static_cast<T>(max) * delta);
538 }
539 
549 template <typename T, typename F>
550 KBLIB_NODISCARD constexpr auto quantize_range(F low, F high, F val) noexcept
551  -> T {
552  static_assert(std::is_unsigned<T>::value, "Destination must be unsigned.");
553  auto delta = (high - low) / static_cast<T>(max);
554  return static_cast<T>((val - low) * static_cast<T>(max) * delta);
555 }
556 
557 } // namespace kblib
558 
559 #endif // KBLIB_STATS_H
This header provides some features of C++17 <type_traits> and other headers for C++14,...
Provides basic compile-time logic operations.
constexpr struct kblib::nums::min_t min
constexpr struct kblib::nums::max_t max
The main namespace in which all entities from kblib are defined.
Definition: algorithm.h:44
constexpr auto quantize_step(F low, F delta, F val) noexcept -> T
Quantize a real-valued value into a discrete integer.
Definition: stats.h:534
constexpr auto a(const std::initializer_list< T > &a) -> auto
Index an array literal without naming its type.
Definition: simple.h:255
constexpr auto fibonacci(int n) noexcept -> U
Compile-time table fibonacci function.
Definition: stats.h:177
constexpr auto root_2() -> T
Definition: stats.h:469
typename std::enable_if< B, T >::type enable_if_t
Definition: fakestd.h:54
constexpr auto e() -> T
Definition: stats.h:465
constexpr auto pi() -> T
Definition: stats.h:457
constexpr auto calc_fib_size() noexcept -> std::size_t
Calculate the index of the largest fibonacci number that can be represented by a given unsigned integ...
Definition: stats.h:132
constexpr auto phi() -> T
Definition: stats.h:473
constexpr auto make_fib_arr() noexcept -> trivial_array< U, N >
Generates the first N values of the fibonacci sequence.
Definition: stats.h:156
constexpr auto tau() -> T
Definition: stats.h:461
constexpr auto quantize_range(F low, F high, F val) noexcept -> T
Quantize a real-valued value into a discrete integer.
Definition: stats.h:550
constexpr auto saturating_cast(F x) noexcept -> enable_if_t< std::is_integral< A >::value and std::is_integral< F >::value and std::is_unsigned< A >::value, A >
Definition: stats.h:479
constexpr auto div(T num, U den) noexcept -> decltype(std::div(num, den))
Definition: stats.h:48
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
Definition: bits.h:714
A metafunction for logical implication. That is, if A, then B. If not A, B is unimportant.
Definition: logic.h:45
Shorthand for std::numeric_limits::max().
Definition: stats.h:194
constexpr friend auto operator>=(max_t, T t) -> bool
Definition: stats.h:288
constexpr friend auto operator!=(T t, max_t) -> bool
Definition: stats.h:250
constexpr friend auto operator==(T t, max_t) -> bool
Definition: stats.h:242
constexpr friend auto operator>(max_t, T t) -> bool
Definition: stats.h:271
constexpr friend auto operator>(T t, max_t) -> bool
Definition: stats.h:267
constexpr friend auto operator<(T t, max_t) -> bool
Definition: stats.h:259
constexpr friend auto operator>=(T t, max_t) -> bool
Definition: stats.h:284
constexpr friend auto operator==(max_t, T t) -> bool
Definition: stats.h:246
constexpr auto operator()(L &&lhs, R &&rhs) const noexcept -> decltype(auto)
Return the larger of two values. Returns lhs if equal.
Definition: stats.h:210
constexpr friend auto operator<=(T t, max_t) -> bool
Definition: stats.h:276
constexpr static auto of() noexcept(noexcept(std::numeric_limits< T >::max()))
Definition: stats.h:201
constexpr friend auto operator!=(max_t, T t) -> bool
Definition: stats.h:254
constexpr friend auto operator<(max_t, max_t) -> std::false_type
Definition: stats.h:224
constexpr friend auto operator!=(max_t, max_t) -> std::false_type
Definition: stats.h:220
constexpr friend auto operator<=(max_t, max_t) -> std::true_type
Definition: stats.h:232
constexpr friend auto operator>=(max_t, max_t) -> std::true_type
Definition: stats.h:236
constexpr friend auto operator>(max_t, max_t) -> std::false_type
Definition: stats.h:228
constexpr friend auto operator==(max_t, max_t) -> std::true_type
Definition: stats.h:216
constexpr friend auto operator<(max_t, T t) -> bool
Definition: stats.h:263
constexpr friend auto operator<=(max_t, T t) -> bool
Definition: stats.h:280
Shorthand for std::numeric_limits::min()
Definition: stats.h:304
constexpr friend auto operator<=(min_t, min_t) -> std::true_type
Definition: stats.h:393
constexpr friend auto operator>(T t, min_t) -> bool
Definition: stats.h:352
constexpr friend auto operator>=(T t, min_t) -> bool
Definition: stats.h:369
constexpr friend auto operator>(max_t, min_t) -> std::true_type
Definition: stats.h:426
constexpr friend auto operator!=(min_t, min_t) -> std::false_type
Definition: stats.h:381
constexpr friend auto operator<=(T t, min_t) -> bool
Definition: stats.h:361
constexpr friend auto operator>(min_t, T t) -> bool
Definition: stats.h:356
constexpr friend auto operator==(min_t, max_t) -> std::false_type
Definition: stats.h:406
constexpr friend auto operator<(min_t, max_t) -> std::true_type
Definition: stats.h:422
constexpr static auto of() noexcept(noexcept(std::numeric_limits< T >::min()))
Definition: stats.h:311
constexpr friend auto operator>=(max_t, min_t) -> std::true_type
Definition: stats.h:442
constexpr friend auto operator==(T t, min_t) -> bool
Definition: stats.h:327
constexpr friend auto operator<(min_t, min_t) -> std::false_type
Definition: stats.h:385
constexpr friend auto operator==(max_t, min_t) -> std::false_type
Definition: stats.h:402
constexpr friend auto operator<(min_t, T t) -> bool
Definition: stats.h:348
constexpr friend auto operator>=(min_t, max_t) -> std::false_type
Definition: stats.h:446
constexpr friend auto operator>(min_t, max_t) -> std::false_type
Definition: stats.h:430
constexpr friend auto operator<(T t, min_t) -> bool
Definition: stats.h:344
constexpr friend auto operator==(min_t, T t) -> bool
Definition: stats.h:331
constexpr friend auto operator!=(min_t, T t) -> bool
Definition: stats.h:339
constexpr friend auto operator>(min_t, min_t) -> std::false_type
Definition: stats.h:389
constexpr auto operator()(L &&lhs, R &&rhs) const noexcept -> decltype(auto)
Returns the smaller of two values. Returns rhs if equal.
Definition: stats.h:320
constexpr friend auto operator!=(T t, min_t) -> bool
Definition: stats.h:335
constexpr friend auto operator<=(min_t, max_t) -> std::true_type
Definition: stats.h:438
constexpr friend auto operator==(min_t, min_t) -> std::true_type
Definition: stats.h:377
constexpr friend auto operator>=(min_t, T t) -> bool
Definition: stats.h:373
constexpr friend auto operator!=(max_t, min_t) -> std::true_type
Definition: stats.h:410
constexpr friend auto operator<=(max_t, min_t) -> std::false_type
Definition: stats.h:434
constexpr friend auto operator!=(min_t, max_t) -> std::true_type
Definition: stats.h:414
constexpr friend auto operator<=(min_t, T t) -> bool
Definition: stats.h:365
constexpr friend auto operator<(max_t, min_t) -> std::false_type
Definition: stats.h:418
constexpr friend auto operator>=(min_t, min_t) -> std::true_type
Definition: stats.h:397
std::array isn't constexpr enough in C++14, so a dedicated array class is needed for constexpr functi...
Definition: stats.h:84
constexpr auto size() const -> std::size_t
Definition: stats.h:92
constexpr auto begin() const &noexcept -> const T *
Definition: stats.h:94
constexpr auto begin() &noexcept -> T *
Definition: stats.h:93
constexpr auto end() const &noexcept -> const T *
Definition: stats.h:98
constexpr auto operator[](std::size_t n) -> T &
Definition: stats.h:86
constexpr auto operator[](std::size_t n) const -> const T &
Definition: stats.h:89
constexpr friend auto operator==(const trivial_array &a, const trivial_array &b) noexcept -> bool
Definition: stats.h:102
constexpr auto end() &noexcept -> T *
Definition: stats.h:97
constexpr friend auto operator!=(const trivial_array &a, const trivial_array &b) noexcept -> bool
Definition: stats.h:106
std::pair isn't constexpr enough, so I'm stuck with this. All I use it for is removing a temporary va...
Definition: stats.h:61
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