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