openMSX
cstd.hh
Go to the documentation of this file.
1 #ifndef CSTD_HH
2 #define CSTD_HH
3 
4 #include "string_view.hh"
5 #include <cmath>
6 #include <cstddef>
7 #include <functional>
8 #include <utility>
9 
10 namespace cstd {
11 
12 // Inspired by this post:
13 // http://tristanbrindle.com/posts/a-more-useful-compile-time-quicksort
14 
15 // Constexpr reimplementations of standard algorithms or data-structures.
16 //
17 // Everything implemented in 'cstd' will very likely become part of standard
18 // C++ in the future. Or it already is part of C++17. So in the future we can
19 // remove our (re)implementation and change the callers from 'cstd::xxx()' to
20 // 'std::xxx()'.
21 
22 //
23 // Various constexpr reimplementation of STL algorithms.
24 //
25 // Many of these are already constexpr in C++17, or are proposed to be made
26 // constexpr for the next C++ standard.
27 //
28 
29 // begin/end are already constexpr in c++17
30 template<typename Container>
31 constexpr auto begin(Container&& c)
32 {
33  return c.begin();
34 }
35 
36 template<typename Container>
37 constexpr auto end(Container&& c)
38 {
39  return c.end();
40 }
41 
42 
43 template<typename Iter1, typename Iter2>
44 constexpr void iter_swap(Iter1 a, Iter2 b)
45 {
46  auto temp = std::move(*a);
47  *a = std::move(*b);
48  *b = std::move(temp);
49 }
50 
51 template<typename InputIt, typename UnaryPredicate>
52 constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate p)
53 {
54  for (; first != last; ++first) {
55  if (!p(*first)) {
56  return first;
57  }
58  }
59  return last;
60 }
61 
62 template<typename ForwardIt, typename UnaryPredicate>
63 constexpr ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
64 {
65  first = cstd::find_if_not(first, last, p);
66  if (first == last) return first;
67 
68  for (ForwardIt i = first + 1; i != last; ++i) {
69  if (p(*i)) {
70  cstd::iter_swap(i, first);
71  ++first;
72  }
73  }
74  return first;
75 }
76 
77 // Workaround for lack of C++17 constexpr-lambda-functions.
78 template<typename T, typename Compare>
79 struct CmpLeft
80 {
81  T pivot;
82  Compare cmp;
83 
84  constexpr bool operator()(const T& elem) const {
85  return cmp(elem, pivot);
86  }
87 };
88 
89 // Workaround for lack of C++17 constexpr-lambda-functions.
90 template<typename T, typename Compare>
91 struct CmpRight
92 {
93  T pivot;
94  Compare cmp;
95 
96  constexpr bool operator()(const T& elem) const {
97  return !cmp(pivot, elem);
98  }
99 };
100 
101 // Textbook implementation of quick sort. Not optimized, but the intention is
102 // that it only gets executed during compile-time.
103 template<typename RAIt, typename Compare = std::less<>>
104 constexpr void sort(RAIt first, RAIt last, Compare cmp = Compare{})
105 {
106  auto const N = last - first;
107  if (N <= 1) return;
108  auto const pivot = *(first + N / 2);
109  auto const middle1 = cstd::partition(
110  first, last, CmpLeft<decltype(pivot), Compare>{pivot, cmp});
111  auto const middle2 = cstd::partition(
112  middle1, last, CmpRight<decltype(pivot), Compare>{pivot, cmp});
113  cstd::sort(first, middle1, cmp);
114  cstd::sort(middle2, last, cmp);
115 }
116 
117 template<typename RandomAccessRange, typename Compare = std::less<>>
118 constexpr void sort(RandomAccessRange&& range, Compare cmp = Compare{})
119 {
120  cstd::sort(cstd::begin(range), cstd::end(range), cmp);
121 }
122 
123 template<typename InputIt1, typename InputIt2>
124 constexpr bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
125  InputIt2 first2, InputIt2 last2)
126 {
127  for (; (first1 != last1) && (first2 != last2); ++first1, ++first2) {
128  if (*first1 < *first2) return true;
129  if (*first2 < *first1) return false;
130  }
131  return (first1 == last1) && (first2 != last2);
132 }
133 
134 // In C++17 this is (constexpr) available as std::char_traits::length().
135 constexpr size_t strlen(const char* s) noexcept
136 {
137  auto* p = s;
138  while (*p) ++p;
139  return p - s;
140 }
141 
142 
143 //
144 // Constrexpr reimplementation of (a subset of) std::array.
145 // Can be removed once we switch to C++17.
146 //
147 
148 template<typename T, size_t N> struct array
149 {
150  T storage[N];
151 
152  using value_type = T;
153  using pointer = T*;
154  using const_pointer = const T*;
155  using reference = T&;
156  using const_reference = const T&;
157  using iterator = T*;
158  using const_iterator = const T*;
159  using size_type = size_t;
160  using difference_type = ptrdiff_t;
161 
162  constexpr T* begin() noexcept
163  {
164  return storage;
165  }
166 
167  constexpr const T* begin() const noexcept
168  {
169  return storage;
170  }
171 
172  constexpr T* end() noexcept
173  {
174  return storage + N;
175  }
176 
177  constexpr const T* end() const noexcept
178  {
179  return storage + N;
180  }
181 
182  constexpr size_type size() const noexcept
183  {
184  return N;
185  }
186 
187  constexpr bool empty() const noexcept
188  {
189  return N == 0;
190  }
191 
192  constexpr T& operator[](size_type n) noexcept
193  {
194  return storage[n];
195  }
196 
197  constexpr const T& operator[](size_type n) const noexcept
198  {
199  return storage[n];
200  }
201 
202  constexpr T& front() noexcept
203  {
204  return storage[0];
205  }
206 
207  constexpr const T& front() const noexcept
208  {
209  return storage[0];
210  }
211 
212  constexpr T& back() noexcept
213  {
214  return storage[N - 1];
215  }
216 
217  constexpr const T& back() const noexcept
218  {
219  return storage[N - 1];
220  }
221 
222  constexpr T* data() noexcept
223  {
224  return storage;
225  }
226 
227  constexpr const T* data() const noexcept
228  {
229  return storage;
230  }
231 };
232 
233 template<typename V, typename ...Ts>
234 constexpr cstd::array<V, sizeof...(Ts)> array_of(Ts&& ...ts)
235 {
236  return {{ std::forward<Ts>(ts)... }};
237 }
238 
239 
240 //
241 // Reimplementation of (a very small subset of) C++17 std::string_view.
242 //
243 // The main difference with our string_view class is that cstd::string offers
244 // a constexpr constructor.
245 //
246 
247 class string
248 {
249 public:
250  constexpr string(const char* s)
251  : dat(s), sz(cstd::strlen(s))
252  {
253  }
254 
255  constexpr const char* begin() const
256  {
257  return dat;
258  }
259 
260  constexpr const char* end() const
261  {
262  return dat + sz;
263  }
264 
265  friend constexpr bool operator<(string x, string y)
266  {
267  return cstd::lexicographical_compare(x.begin(), x.end(),
268  y.begin(), y.end());
269  }
270 
271  operator string_view() const
272  {
273  return string_view(dat, sz);
274  }
275 
276 private:
277  const char* dat;
278  size_t sz;
279 };
280 
281 // Reimplementation of various mathematical functions. You must specify an
282 // iteration count, this controls how accurate the result will be.
283 #if (defined(__GNUC__) && !defined(__clang__))
284 
285 // Gcc has constexpr versions of most mathematical functions (this is a
286 // non-standard extension). Prefer those over our implementations.
287 template<int> constexpr double sin (double x) { return std::sin (x); }
288 template<int> constexpr double cos (double x) { return std::cos (x); }
289 template<int, int> constexpr double log (double x) { return std::log (x); }
290 template<int, int> 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?)
291 template<int, int> constexpr double log10(double x) { return std::log10(x); }
292 template<int> constexpr double exp (double x) { return std::exp (x); }
293 template<int> constexpr double exp2 (double x) { return ::exp2 (x); } // see log2, but apparently no need to use exp(log(2) * x) here?!
294 template<int, int> constexpr double pow(double x, double y) { return std::pow(x, y); }
295 inline constexpr double round(double x) { return ::round(x); } // should be std::round(), see above
296 
297 #else
298 
299 constexpr double upow(double x, unsigned u)
300 {
301  double y = 1.0;
302  while (u) {
303  if (u & 1) y *= x;
304  x *= x;
305  u >>= 1;
306  }
307  return y;
308 }
309 
310 constexpr double ipow(double x, int i)
311 {
312  return (i >= 0) ? upow(x, i) : upow(x, -i);
313 }
314 
315 template<int ITERATIONS>
316 constexpr double exp(double x)
317 {
318  // Split x into integral and fractional part:
319  // exp(x) = exp(i + f) = exp(i) * exp(f)
320  // with: i an int (undefined if out of range)
321  // -1 < f < 1
322  int i = int(x);
323  double f = x - i;
324 
325  // Approximate exp(f) with Taylor series.
326  double y = 1.0;
327  double t = f;
328  double n = 1.0;
329  for (int k = 2; k < (2 + ITERATIONS); ++k) {
330  y += t / n;
331  t *= f;
332  n *= k;
333  }
334 
335  // Approximate exp(i) by squaring.
336  int p = (i >= 0) ? i : -i; // abs(i);
337  double s = upow(M_E, p);
338 
339  // Combine the results.
340  if (i >= 0) {
341  return y * s;
342  } else {
343  return y / s;
344  }
345 }
346 
347 constexpr double simple_fmod(double x, double y)
348 {
349  assert(y > 0.0);
350  return x - int(x / y) * y;
351 }
352 
353 template<int ITERATIONS>
354 constexpr double sin_iter(double x)
355 {
356  double x2 = x * x;
357  double y = 0.0;
358  double t = x;
359  double n = 1.0;
360  for (int k = 1; k < (1 + 4 * ITERATIONS); ) {
361  y += t / n;
362  t *= x2;
363  n *= ++k;
364  n *= ++k;
365 
366  y -= t / n;
367  t *= x2;
368  n *= ++k;
369  n *= ++k;
370  }
371  return y;
372 }
373 
374 template<int ITERATIONS>
375 constexpr double cos_iter(double x)
376 {
377  double x2 = x * x;
378  double y = 1.0;
379  double t = x2;
380  double n = 2.0;
381  for (int k = 2; k < (2 + 4 * ITERATIONS); ) {
382  y -= t / n;
383  t *= x2;
384  n *= ++k;
385  n *= ++k;
386 
387  y += t / n;
388  t *= x2;
389  n *= ++k;
390  n *= ++k;
391  }
392  return y;
393 }
394 
395 template<int ITERATIONS>
396 constexpr double sin(double x)
397 {
398  double sign = 1.0;
399 
400  // reduce to [0, +inf)
401  if (x < 0.0) {
402  sign = -1.0;
403  x = -x;
404  }
405 
406  // reduce to [0, 2pi)
407  x = simple_fmod(x, 2 * M_PI);
408 
409  // reduce to [0, pi]
410  if (x > M_PI) {
411  sign = -sign;
412  x -= M_PI;
413  }
414 
415  // reduce to [0, pi/2]
416  if (x > M_PI/2) {
417  x = M_PI - x;
418  }
419 
420  // reduce to [0, pi/4]
421  if (x > M_PI/4) {
422  x = M_PI/2 - x;
423  return sign * cos_iter<ITERATIONS>(x);
424  } else {
425  return sign * sin_iter<ITERATIONS>(x);
426  }
427 }
428 
429 template<int ITERATIONS>
430 constexpr double cos(double x)
431 {
432  double sign = 1.0;
433 
434  // reduce to [0, +inf)
435  if (x < 0.0) {
436  x = -x;
437  }
438 
439  // reduce to [0, 2pi)
440  x = simple_fmod(x, 2 * M_PI);
441 
442  // reduce to [0, pi]
443  if (x > M_PI) {
444  x = 2.0 * M_PI - x;
445  }
446 
447  // reduce to [0, pi/2]
448  if (x > M_PI/2) {
449  sign = -sign;
450  x = M_PI - x;
451  }
452 
453  // reduce to [0, pi/4]
454  if (x > M_PI/4) {
455  x = M_PI/2 - x;
456  return sign * sin_iter<ITERATIONS>(x);
457  } else {
458  return sign * cos_iter<ITERATIONS>(x);
459  }
460 }
461 
462 
463 // https://en.wikipedia.org/wiki/Natural_logarithm#High_precision
464 template<int E_ITERATIONS, int L_ITERATIONS>
465 constexpr double log(double x)
466 {
467  int a = 0;
468  while (x <= 0.25) {
469  x *= M_E;
470  ++a;
471  }
472  double y = 0.0;
473  for (int i = 0; i < L_ITERATIONS; ++i) {
474  auto ey = cstd::exp<E_ITERATIONS>(y);
475  y = y + 2.0 * (x - ey) / (x + ey);
476  }
477  return y - a;
478 }
479 
480 template<int E_ITERATIONS, int L_ITERATIONS>
481 constexpr double log2(double x)
482 {
483  return cstd::log<E_ITERATIONS, L_ITERATIONS>(x) / M_LN2;
484 }
485 
486 template<int E_ITERATIONS, int L_ITERATIONS>
487 constexpr double log10(double x)
488 {
489  return cstd::log<E_ITERATIONS, L_ITERATIONS>(x) / M_LN10;
490 }
491 
492 template<int E_ITERATIONS, int L_ITERATIONS>
493 constexpr double pow(double x, double y)
494 {
495  return cstd::exp<E_ITERATIONS>(cstd::log<E_ITERATIONS, L_ITERATIONS>(x) * y);
496 }
497 
498 template<int ITERATIONS>
499 constexpr double exp2(double x)
500 {
501  return cstd::exp<ITERATIONS>(M_LN2 * x);
502 }
503 
504 constexpr double round(double x)
505 {
506  return (x >= 0) ? int( x + 0.5)
507  : -int(-x + 0.5);
508 }
509 
510 #endif
511 
512 } // namespace cstd
513 
514 #endif
constexpr double simple_fmod(double x, double y)
Definition: cstd.hh:347
size_t size_type
Definition: cstd.hh:159
Definition: cstd.hh:10
Compare cmp
Definition: cstd.hh:82
constexpr T * data() noexcept
Definition: cstd.hh:222
constexpr void iter_swap(Iter1 a, Iter2 b)
Definition: cstd.hh:44
constexpr T & front() noexcept
Definition: cstd.hh:202
constexpr const T * begin() const noexcept
Definition: cstd.hh:167
constexpr T * begin() noexcept
Definition: cstd.hh:162
constexpr const T & front() const noexcept
Definition: cstd.hh:207
constexpr const T * end() const noexcept
Definition: cstd.hh:177
constexpr void sort(RAIt first, RAIt last, Compare cmp=Compare{})
Definition: cstd.hh:104
constexpr T * end() noexcept
Definition: cstd.hh:172
constexpr T & back() noexcept
Definition: cstd.hh:212
#define M_PI
Definition: Math.hh:26
ptrdiff_t difference_type
Definition: cstd.hh:160
Compare cmp
Definition: cstd.hh:94
#define M_E
Definition: Math.hh:17
constexpr double exp2(double x)
Definition: cstd.hh:499
constexpr const T * data() const noexcept
Definition: cstd.hh:227
constexpr double ipow(double x, int i)
Definition: cstd.hh:310
constexpr double log(double x)
Definition: cstd.hh:465
constexpr auto end(Container &&c)
Definition: cstd.hh:37
constexpr double sin(double x)
Definition: cstd.hh:396
constexpr double cos_iter(double x)
Definition: cstd.hh:375
constexpr string(const char *s)
Definition: cstd.hh:250
constexpr double pow(double x, double y)
Definition: cstd.hh:493
constexpr const char * end() const
Definition: cstd.hh:260
constexpr double exp(double x)
Definition: cstd.hh:316
T * iterator
Definition: cstd.hh:157
constexpr size_t strlen(const char *s) noexcept
Definition: cstd.hh:135
friend constexpr bool operator<(string x, string y)
Definition: cstd.hh:265
constexpr bool operator()(const T &elem) const
Definition: cstd.hh:96
constexpr double upow(double x, unsigned u)
Definition: cstd.hh:299
const T * const_pointer
Definition: cstd.hh:154
T * pointer
Definition: cstd.hh:153
#define M_LN2
Definition: Math.hh:20
constexpr size_type size() const noexcept
Definition: cstd.hh:182
constexpr bool operator()(const T &elem) const
Definition: cstd.hh:84
constexpr double sin_iter(double x)
Definition: cstd.hh:354
constexpr const T & operator[](size_type n) const noexcept
Definition: cstd.hh:197
T value_type
Definition: cstd.hh:152
constexpr bool empty() const noexcept
Definition: cstd.hh:187
constexpr double log2(double x)
Definition: cstd.hh:481
constexpr double round(double x)
Definition: cstd.hh:504
#define M_LN10
Definition: Math.hh:23
constexpr auto begin(Container &&c)
Definition: cstd.hh:31
This class implements a (close approximation) of the std::string_view class.
Definition: string_view.hh:16
constexpr const char * begin() const
Definition: cstd.hh:255
constexpr T & operator[](size_type n) noexcept
Definition: cstd.hh:192
constexpr bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
Definition: cstd.hh:124
const T & const_reference
Definition: cstd.hh:156
constexpr cstd::array< V, sizeof...(Ts)> array_of(Ts &&...ts)
Definition: cstd.hh:234
constexpr const T & back() const noexcept
Definition: cstd.hh:217
constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate p)
Definition: cstd.hh:52
T & reference
Definition: cstd.hh:155
TclObject t
constexpr ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
Definition: cstd.hh:63
constexpr double log10(double x)
Definition: cstd.hh:487
const T * const_iterator
Definition: cstd.hh:158
constexpr double cos(double x)
Definition: cstd.hh:430