openMSX
cstd.hh
Go to the documentation of this file.
1 #ifndef CSTD_HH
2 #define CSTD_HH
3 
4 #include "xrange.hh"
5 #include <cassert>
6 #include <cmath>
7 #include <cstddef>
8 #include <functional>
9 #include <string_view>
10 #include <utility>
11 
12 namespace cstd {
13 
14 // Inspired by this post:
15 // http://tristanbrindle.com/posts/a-more-useful-compile-time-quicksort
16 
17 // Constexpr reimplementations of standard algorithms or data-structures.
18 //
19 // Everything implemented in 'cstd' will very likely become part of standard
20 // C++ in the future. So then we can remove our (re)implementation and change
21 // the callers from 'cstd::xxx()' to 'std::xxx()'.
22 
23 //
24 // Various constexpr reimplementations of STL algorithms.
25 //
26 
27 template<typename Iter1, typename Iter2>
28 constexpr void iter_swap(Iter1 a, Iter2 b)
29 {
30  auto temp = std::move(*a);
31  *a = std::move(*b);
32  *b = std::move(temp);
33 }
34 
35 template<typename InputIt, typename UnaryPredicate>
36 [[nodiscard]] constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate p)
37 {
38  for (; first != last; ++first) {
39  if (!p(*first)) {
40  return first;
41  }
42  }
43  return last;
44 }
45 
46 template<typename ForwardIt, typename UnaryPredicate>
47 [[nodiscard]] constexpr ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
48 {
49  first = cstd::find_if_not(first, last, p);
50  if (first == last) return first;
51 
52  for (ForwardIt i = first + 1; i != last; ++i) {
53  if (p(*i)) {
54  cstd::iter_swap(i, first);
55  ++first;
56  }
57  }
58  return first;
59 }
60 
61 // Textbook implementation of quick sort. Not optimized, but the intention is
62 // that it only gets executed during compile-time.
63 template<typename RAIt, typename Compare = std::less<>>
64 constexpr void sort(RAIt first, RAIt last, Compare cmp = Compare{})
65 {
66  auto const N = last - first;
67  if (N <= 1) return;
68  auto const pivot = *(first + N / 2);
69  auto const middle1 = cstd::partition(
70  first, last, [&](const auto& elem) { return cmp(elem, pivot); });
71  auto const middle2 = cstd::partition(
72  middle1, last, [&](const auto& elem) { return !cmp(pivot, elem); });
73  cstd::sort(first, middle1, cmp);
74  cstd::sort(middle2, last, cmp);
75 }
76 
77 template<typename RandomAccessRange, typename Compare = std::less<>>
78 constexpr void sort(RandomAccessRange&& range, Compare cmp = Compare{})
79 {
80  cstd::sort(std::begin(range), std::end(range), cmp);
81 }
82 
83 template<typename InputIt1, typename InputIt2>
84 [[nodiscard]] constexpr bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
85  InputIt2 first2, InputIt2 last2)
86 {
87  for (; (first1 != last1) && (first2 != last2); ++first1, ++first2) {
88  if (*first1 < *first2) return true;
89  if (*first2 < *first1) return false;
90  }
91  return (first1 == last1) && (first2 != last2);
92 }
93 
94 template<typename ForwardIt, typename T>
95 constexpr void replace(ForwardIt first, ForwardIt last, const T& old_value, const T& new_value)
96 {
97  while (first != last) {
98  if (*first == old_value) {
99  *first = new_value;
100  }
101  ++first;
102  }
103 }
104 template<typename ForwardRange, typename T>
105 constexpr void replace(ForwardRange& range, const T& old_value, const T& new_value)
106 {
107  cstd::replace(std::begin(range), std::end(range), old_value, new_value);
108 }
109 
110 template<typename ForwardIt, typename T>
111 constexpr void fill(ForwardIt first, ForwardIt last, const T& value)
112 {
113  while (first != last) {
114  *first = value;
115  ++first;
116  }
117 }
118 template<typename ForwardRange, typename T>
119 constexpr void fill(ForwardRange& range, const T& value)
120 {
121  cstd::fill(std::begin(range), std::end(range), value);
122 }
123 
124 template<typename T>
125 [[nodiscard]] constexpr T abs(T t)
126 {
127  return (t >= 0) ? t : -t;
128 }
129 
130 // Reimplementation of various mathematical functions. You must specify an
131 // iteration count, this controls how accurate the result will be.
132 #if (defined(__GNUC__) && !defined(__clang__))
133 
134 // Gcc has constexpr versions of most mathematical functions (this is a
135 // non-standard extension). Prefer those over our implementations.
136 template<int> [[nodiscard]] constexpr double sin (double x) { return std::sin (x); }
137 template<int> [[nodiscard]] constexpr double cos (double x) { return std::cos (x); }
138 template<int, int> [[nodiscard]] constexpr double log (double x) { return std::log (x); }
139 template<int, int> [[nodiscard]] constexpr double log2 (double x) { return ::log (x) / ::log(2); } // should be std::log2(x) but this doesn't seem to compile in g++-4.8/g++-4.9 (bug?)
140 template<int, int> [[nodiscard]] constexpr double log10(double x) { return std::log10(x); }
141 template<int> [[nodiscard]] constexpr double exp (double x) { return std::exp (x); }
142 template<int> [[nodiscard]] constexpr double exp2 (double x) { return ::exp2 (x); } // see log2, but apparently no need to use exp(log(2) * x) here?!
143 template<int, int> [[nodiscard]] constexpr double pow(double x, double y) { return std::pow(x, y); }
144 [[nodiscard]] constexpr double round(double x) { return ::round(x); } // should be std::round(), see above
145 [[nodiscard]] constexpr float round(float x) { return ::round(x); }
146 [[nodiscard]] constexpr double sqrt (double x) { return ::sqrt (x); }
147 
148 #else
149 
150 [[nodiscard]] constexpr double upow(double x, unsigned u)
151 {
152  double y = 1.0;
153  while (u) {
154  if (u & 1) y *= x;
155  x *= x;
156  u >>= 1;
157  }
158  return y;
159 }
160 
161 [[nodiscard]] constexpr double ipow(double x, int i)
162 {
163  return (i >= 0) ? upow(x, i) : upow(x, -i);
164 }
165 
166 template<int ITERATIONS>
167 [[nodiscard]] constexpr double exp(double x)
168 {
169  // Split x into integral and fractional part:
170  // exp(x) = exp(i + f) = exp(i) * exp(f)
171  // with: i an int (undefined if out of range)
172  // -1 < f < 1
173  int i = int(x);
174  double f = x - i;
175 
176  // Approximate exp(f) with Taylor series.
177  double y = 1.0;
178  double t = f;
179  double n = 1.0;
180  for (auto k : xrange(ITERATIONS)) {
181  y += t / n;
182  t *= f;
183  n *= k + 2;
184  }
185 
186  // Approximate exp(i) by squaring.
187  int p = (i >= 0) ? i : -i; // abs(i);
188  double s = upow(M_E, p);
189 
190  // Combine the results.
191  if (i >= 0) {
192  return y * s;
193  } else {
194  return y / s;
195  }
196 }
197 
198 [[nodiscard]] constexpr double simple_fmod(double x, double y)
199 {
200  assert(y > 0.0);
201  return x - int(x / y) * y;
202 }
203 
204 template<int ITERATIONS>
205 [[nodiscard]] constexpr double sin_iter(double x)
206 {
207  double x2 = x * x;
208  double y = 0.0;
209  double t = x;
210  double n = 1.0;
211  for (int k = 1; k < (1 + 4 * ITERATIONS); ) {
212  y += t / n;
213  t *= x2;
214  n *= ++k;
215  n *= ++k;
216 
217  y -= t / n;
218  t *= x2;
219  n *= ++k;
220  n *= ++k;
221  }
222  return y;
223 }
224 
225 template<int ITERATIONS>
226 [[nodiscard]] constexpr double cos_iter(double x)
227 {
228  double x2 = x * x;
229  double y = 1.0;
230  double t = x2;
231  double n = 2.0;
232  for (int k = 2; k < (2 + 4 * ITERATIONS); ) {
233  y -= t / n;
234  t *= x2;
235  n *= ++k;
236  n *= ++k;
237 
238  y += t / n;
239  t *= x2;
240  n *= ++k;
241  n *= ++k;
242  }
243  return y;
244 }
245 
246 template<int ITERATIONS>
247 [[nodiscard]] constexpr double sin(double x)
248 {
249  double sign = 1.0;
250 
251  // reduce to [0, +inf)
252  if (x < 0.0) {
253  sign = -1.0;
254  x = -x;
255  }
256 
257  // reduce to [0, 2pi)
258  x = simple_fmod(x, 2 * M_PI);
259 
260  // reduce to [0, pi]
261  if (x > M_PI) {
262  sign = -sign;
263  x -= M_PI;
264  }
265 
266  // reduce to [0, pi/2]
267  if (x > M_PI/2) {
268  x = M_PI - x;
269  }
270 
271  // reduce to [0, pi/4]
272  if (x > M_PI/4) {
273  x = M_PI/2 - x;
274  return sign * cos_iter<ITERATIONS>(x);
275  } else {
276  return sign * sin_iter<ITERATIONS>(x);
277  }
278 }
279 
280 template<int ITERATIONS>
281 [[nodiscard]] constexpr double cos(double x)
282 {
283  double sign = 1.0;
284 
285  // reduce to [0, +inf)
286  if (x < 0.0) {
287  x = -x;
288  }
289 
290  // reduce to [0, 2pi)
291  x = simple_fmod(x, 2 * M_PI);
292 
293  // reduce to [0, pi]
294  if (x > M_PI) {
295  x = 2.0 * M_PI - x;
296  }
297 
298  // reduce to [0, pi/2]
299  if (x > M_PI/2) {
300  sign = -sign;
301  x = M_PI - x;
302  }
303 
304  // reduce to [0, pi/4]
305  if (x > M_PI/4) {
306  x = M_PI/2 - x;
307  return sign * sin_iter<ITERATIONS>(x);
308  } else {
309  return sign * cos_iter<ITERATIONS>(x);
310  }
311 }
312 
313 
314 // https://en.wikipedia.org/wiki/Natural_logarithm#High_precision
315 template<int E_ITERATIONS, int L_ITERATIONS>
316 [[nodiscard]] constexpr double log(double x)
317 {
318  int a = 0;
319  while (x <= 0.25) {
320  x *= M_E;
321  ++a;
322  }
323  double y = 0.0;
324  repeat(L_ITERATIONS, [&] {
325  auto ey = cstd::exp<E_ITERATIONS>(y);
326  y = y + 2.0 * (x - ey) / (x + ey);
327  });
328  return y - a;
329 }
330 
331 template<int E_ITERATIONS, int L_ITERATIONS>
332 [[nodiscard]] constexpr double log2(double x)
333 {
334  return cstd::log<E_ITERATIONS, L_ITERATIONS>(x) / M_LN2;
335 }
336 
337 template<int E_ITERATIONS, int L_ITERATIONS>
338 [[nodiscard]] constexpr double log10(double x)
339 {
340  return cstd::log<E_ITERATIONS, L_ITERATIONS>(x) / M_LN10;
341 }
342 
343 template<int E_ITERATIONS, int L_ITERATIONS>
344 [[nodiscard]] constexpr double pow(double x, double y)
345 {
346  return cstd::exp<E_ITERATIONS>(cstd::log<E_ITERATIONS, L_ITERATIONS>(x) * y);
347 }
348 
349 template<int ITERATIONS>
350 [[nodiscard]] constexpr double exp2(double x)
351 {
352  return cstd::exp<ITERATIONS>(M_LN2 * x);
353 }
354 
355 [[nodiscard]] constexpr double round(double x)
356 {
357  return (x >= 0) ? int( x + 0.5)
358  : -int(-x + 0.5);
359 }
360 
361 [[nodiscard]] constexpr float round(float x)
362 {
363  return (x >= 0) ? int( x + 0.5f)
364  : -int(-x + 0.5f);
365 }
366 
367 [[nodiscard]] constexpr double sqrt(double x)
368 {
369  assert(x >= 0.0);
370  double curr = x;
371  double prev = 0.0;
372  while (curr != prev) {
373  prev = curr;
374  curr = 0.5 * (curr + x / curr);
375  }
376  return curr;
377 }
378 
379 #endif
380 
381 } // namespace cstd
382 
383 #endif
#define M_LN10
Definition: Math.hh:24
#define M_LN2
Definition: Math.hh:21
#define M_E
Definition: Math.hh:18
#define M_PI
Definition: Math.hh:27
TclObject t
Definition: cstd.hh:12
constexpr double pow(double x, double y)
Definition: cstd.hh:344
constexpr double log(double x)
Definition: cstd.hh:316
constexpr ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
Definition: cstd.hh:47
constexpr void sort(RAIt first, RAIt last, Compare cmp=Compare{})
Definition: cstd.hh:64
constexpr float round(float x)
Definition: cstd.hh:361
constexpr double sin_iter(double x)
Definition: cstd.hh:205
constexpr void fill(ForwardIt first, ForwardIt last, const T &value)
Definition: cstd.hh:111
constexpr double simple_fmod(double x, double y)
Definition: cstd.hh:198
constexpr double exp2(double x)
Definition: cstd.hh:350
constexpr double sqrt(double x)
Definition: cstd.hh:367
constexpr void iter_swap(Iter1 a, Iter2 b)
Definition: cstd.hh:28
constexpr double round(double x)
Definition: cstd.hh:355
constexpr T abs(T t)
Definition: cstd.hh:125
constexpr double exp(double x)
Definition: cstd.hh:167
constexpr bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
Definition: cstd.hh:84
constexpr double cos_iter(double x)
Definition: cstd.hh:226
constexpr double ipow(double x, int i)
Definition: cstd.hh:161
constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate p)
Definition: cstd.hh:36
constexpr double log10(double x)
Definition: cstd.hh:338
constexpr void replace(ForwardIt first, ForwardIt last, const T &old_value, const T &new_value)
Definition: cstd.hh:95
constexpr double sin(double x)
Definition: cstd.hh:247
constexpr double cos(double x)
Definition: cstd.hh:281
constexpr double log2(double x)
Definition: cstd.hh:332
constexpr double upow(double x, unsigned u)
Definition: cstd.hh:150
constexpr unsigned N
Definition: ResampleHQ.cc:229
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:124
constexpr void repeat(T n, Op op)
Repeat the given operation 'op' 'n' times.
Definition: xrange.hh:170
constexpr auto xrange(T e)
Definition: xrange.hh:155
constexpr auto begin(const zstring_view &x)
Definition: zstring_view.hh:82
constexpr auto end(const zstring_view &x)
Definition: zstring_view.hh:83