1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_RATIO
11#define _LIBCPP_RATIO
12
13/*
14    ratio synopsis
15
16namespace std
17{
18
19template <intmax_t N, intmax_t D = 1>
20class ratio
21{
22public:
23    static constexpr intmax_t num;
24    static constexpr intmax_t den;
25    typedef ratio<num, den> type;
26};
27
28// ratio arithmetic
29template <class R1, class R2> using ratio_add = ...;
30template <class R1, class R2> using ratio_subtract = ...;
31template <class R1, class R2> using ratio_multiply = ...;
32template <class R1, class R2> using ratio_divide = ...;
33
34// ratio comparison
35template <class R1, class R2> struct ratio_equal;
36template <class R1, class R2> struct ratio_not_equal;
37template <class R1, class R2> struct ratio_less;
38template <class R1, class R2> struct ratio_less_equal;
39template <class R1, class R2> struct ratio_greater;
40template <class R1, class R2> struct ratio_greater_equal;
41
42// convenience SI typedefs
43typedef ratio<1, 1000000000000000000000000> yocto;  // not supported
44typedef ratio<1,    1000000000000000000000> zepto;  // not supported
45typedef ratio<1,       1000000000000000000> atto;
46typedef ratio<1,          1000000000000000> femto;
47typedef ratio<1,             1000000000000> pico;
48typedef ratio<1,                1000000000> nano;
49typedef ratio<1,                   1000000> micro;
50typedef ratio<1,                      1000> milli;
51typedef ratio<1,                       100> centi;
52typedef ratio<1,                        10> deci;
53typedef ratio<                       10, 1> deca;
54typedef ratio<                      100, 1> hecto;
55typedef ratio<                     1000, 1> kilo;
56typedef ratio<                  1000000, 1> mega;
57typedef ratio<               1000000000, 1> giga;
58typedef ratio<            1000000000000, 1> tera;
59typedef ratio<         1000000000000000, 1> peta;
60typedef ratio<      1000000000000000000, 1> exa;
61typedef ratio<   1000000000000000000000, 1> zetta;  // not supported
62typedef ratio<1000000000000000000000000, 1> yotta;  // not supported
63
64  // 20.11.5, ratio comparison
65  template <class R1, class R2> inline constexpr bool ratio_equal_v
66    = ratio_equal<R1, R2>::value;                                       // C++17
67  template <class R1, class R2> inline constexpr bool ratio_not_equal_v
68    = ratio_not_equal<R1, R2>::value;                                   // C++17
69  template <class R1, class R2> inline constexpr bool ratio_less_v
70    = ratio_less<R1, R2>::value;                                        // C++17
71  template <class R1, class R2> inline constexpr bool ratio_less_equal_v
72    = ratio_less_equal<R1, R2>::value;                                  // C++17
73  template <class R1, class R2> inline constexpr bool ratio_greater_v
74    = ratio_greater<R1, R2>::value;                                     // C++17
75  template <class R1, class R2> inline constexpr bool ratio_greater_equal_v
76    = ratio_greater_equal<R1, R2>::value;                               // C++17
77}
78*/
79
80#include <__assert> // all public C++ headers provide the assertion handler
81#include <__config>
82#include <climits>
83#include <cstdint>
84#include <type_traits>
85#include <version>
86
87#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
88#  pragma GCC system_header
89#endif
90
91_LIBCPP_PUSH_MACROS
92#include <__undef_macros>
93
94
95_LIBCPP_BEGIN_NAMESPACE_STD
96
97// __static_gcd
98
99template <intmax_t _Xp, intmax_t _Yp>
100struct __static_gcd
101{
102    static const intmax_t value = __static_gcd<_Yp, _Xp % _Yp>::value;
103};
104
105template <intmax_t _Xp>
106struct __static_gcd<_Xp, 0>
107{
108    static const intmax_t value = _Xp;
109};
110
111template <>
112struct __static_gcd<0, 0>
113{
114    static const intmax_t value = 1;
115};
116
117// __static_lcm
118
119template <intmax_t _Xp, intmax_t _Yp>
120struct __static_lcm
121{
122    static const intmax_t value = _Xp / __static_gcd<_Xp, _Yp>::value * _Yp;
123};
124
125template <intmax_t _Xp>
126struct __static_abs
127{
128    static const intmax_t value = _Xp < 0 ? -_Xp : _Xp;
129};
130
131template <intmax_t _Xp>
132struct __static_sign
133{
134    static const intmax_t value = _Xp == 0 ? 0 : (_Xp < 0 ? -1 : 1);
135};
136
137template <intmax_t _Xp, intmax_t _Yp, intmax_t = __static_sign<_Yp>::value>
138class __ll_add;
139
140template <intmax_t _Xp, intmax_t _Yp>
141class __ll_add<_Xp, _Yp, 1>
142{
143    static const intmax_t min = (1LL << (sizeof(intmax_t) * CHAR_BIT - 1)) + 1;
144    static const intmax_t max = -min;
145
146    static_assert(_Xp <= max - _Yp, "overflow in __ll_add");
147public:
148    static const intmax_t value = _Xp + _Yp;
149};
150
151template <intmax_t _Xp, intmax_t _Yp>
152class __ll_add<_Xp, _Yp, 0>
153{
154public:
155    static const intmax_t value = _Xp;
156};
157
158template <intmax_t _Xp, intmax_t _Yp>
159class __ll_add<_Xp, _Yp, -1>
160{
161    static const intmax_t min = (1LL << (sizeof(intmax_t) * CHAR_BIT - 1)) + 1;
162    static const intmax_t max = -min;
163
164    static_assert(min - _Yp <= _Xp, "overflow in __ll_add");
165public:
166    static const intmax_t value = _Xp + _Yp;
167};
168
169template <intmax_t _Xp, intmax_t _Yp, intmax_t = __static_sign<_Yp>::value>
170class __ll_sub;
171
172template <intmax_t _Xp, intmax_t _Yp>
173class __ll_sub<_Xp, _Yp, 1>
174{
175    static const intmax_t min = (1LL << (sizeof(intmax_t) * CHAR_BIT - 1)) + 1;
176    static const intmax_t max = -min;
177
178    static_assert(min + _Yp <= _Xp, "overflow in __ll_sub");
179public:
180    static const intmax_t value = _Xp - _Yp;
181};
182
183template <intmax_t _Xp, intmax_t _Yp>
184class __ll_sub<_Xp, _Yp, 0>
185{
186public:
187    static const intmax_t value = _Xp;
188};
189
190template <intmax_t _Xp, intmax_t _Yp>
191class __ll_sub<_Xp, _Yp, -1>
192{
193    static const intmax_t min = (1LL << (sizeof(intmax_t) * CHAR_BIT - 1)) + 1;
194    static const intmax_t max = -min;
195
196    static_assert(_Xp <= max + _Yp, "overflow in __ll_sub");
197public:
198    static const intmax_t value = _Xp - _Yp;
199};
200
201template <intmax_t _Xp, intmax_t _Yp>
202class __ll_mul
203{
204    static const intmax_t nan = (1LL << (sizeof(intmax_t) * CHAR_BIT - 1));
205    static const intmax_t min = nan + 1;
206    static const intmax_t max = -min;
207    static const intmax_t __a_x = __static_abs<_Xp>::value;
208    static const intmax_t __a_y = __static_abs<_Yp>::value;
209
210    static_assert(_Xp != nan && _Yp != nan && __a_x <= max / __a_y, "overflow in __ll_mul");
211public:
212    static const intmax_t value = _Xp * _Yp;
213};
214
215template <intmax_t _Yp>
216class __ll_mul<0, _Yp>
217{
218public:
219    static const intmax_t value = 0;
220};
221
222template <intmax_t _Xp>
223class __ll_mul<_Xp, 0>
224{
225public:
226    static const intmax_t value = 0;
227};
228
229template <>
230class __ll_mul<0, 0>
231{
232public:
233    static const intmax_t value = 0;
234};
235
236// Not actually used but left here in case needed in future maintenance
237template <intmax_t _Xp, intmax_t _Yp>
238class __ll_div
239{
240    static const intmax_t nan = (1LL << (sizeof(intmax_t) * CHAR_BIT - 1));
241    static const intmax_t min = nan + 1;
242    static const intmax_t max = -min;
243
244    static_assert(_Xp != nan && _Yp != nan && _Yp != 0, "overflow in __ll_div");
245public:
246    static const intmax_t value = _Xp / _Yp;
247};
248
249template <intmax_t _Num, intmax_t _Den = 1>
250class _LIBCPP_TEMPLATE_VIS ratio
251{
252    static_assert(__static_abs<_Num>::value >= 0, "ratio numerator is out of range");
253    static_assert(_Den != 0, "ratio divide by 0");
254    static_assert(__static_abs<_Den>::value >  0, "ratio denominator is out of range");
255    static _LIBCPP_CONSTEXPR const intmax_t __na = __static_abs<_Num>::value;
256    static _LIBCPP_CONSTEXPR const intmax_t __da = __static_abs<_Den>::value;
257    static _LIBCPP_CONSTEXPR const intmax_t __s = __static_sign<_Num>::value * __static_sign<_Den>::value;
258    static _LIBCPP_CONSTEXPR const intmax_t __gcd = __static_gcd<__na, __da>::value;
259public:
260    static _LIBCPP_CONSTEXPR const intmax_t num = __s * __na / __gcd;
261    static _LIBCPP_CONSTEXPR const intmax_t den = __da / __gcd;
262
263    typedef ratio<num, den> type;
264};
265
266template <intmax_t _Num, intmax_t _Den>
267_LIBCPP_CONSTEXPR const intmax_t ratio<_Num, _Den>::num;
268
269template <intmax_t _Num, intmax_t _Den>
270_LIBCPP_CONSTEXPR const intmax_t ratio<_Num, _Den>::den;
271
272template <class _Tp>                    struct __is_ratio                     : false_type {};
273template <intmax_t _Num, intmax_t _Den> struct __is_ratio<ratio<_Num, _Den> > : true_type  {};
274
275typedef ratio<1LL, 1000000000000000000LL> atto;
276typedef ratio<1LL,    1000000000000000LL> femto;
277typedef ratio<1LL,       1000000000000LL> pico;
278typedef ratio<1LL,          1000000000LL> nano;
279typedef ratio<1LL,             1000000LL> micro;
280typedef ratio<1LL,                1000LL> milli;
281typedef ratio<1LL,                 100LL> centi;
282typedef ratio<1LL,                  10LL> deci;
283typedef ratio<                 10LL, 1LL> deca;
284typedef ratio<                100LL, 1LL> hecto;
285typedef ratio<               1000LL, 1LL> kilo;
286typedef ratio<            1000000LL, 1LL> mega;
287typedef ratio<         1000000000LL, 1LL> giga;
288typedef ratio<      1000000000000LL, 1LL> tera;
289typedef ratio<   1000000000000000LL, 1LL> peta;
290typedef ratio<1000000000000000000LL, 1LL> exa;
291
292template <class _R1, class _R2>
293struct __ratio_multiply
294{
295private:
296    static const intmax_t __gcd_n1_d2 = __static_gcd<_R1::num, _R2::den>::value;
297    static const intmax_t __gcd_d1_n2 = __static_gcd<_R1::den, _R2::num>::value;
298public:
299    typedef typename ratio
300        <
301            __ll_mul<_R1::num / __gcd_n1_d2, _R2::num / __gcd_d1_n2>::value,
302            __ll_mul<_R2::den / __gcd_n1_d2, _R1::den / __gcd_d1_n2>::value
303        >::type type;
304};
305
306#ifndef _LIBCPP_CXX03_LANG
307
308template <class _R1, class _R2> using ratio_multiply
309                                    = typename __ratio_multiply<_R1, _R2>::type;
310
311#else  // _LIBCPP_CXX03_LANG
312
313template <class _R1, class _R2>
314struct _LIBCPP_TEMPLATE_VIS ratio_multiply
315    : public __ratio_multiply<_R1, _R2>::type {};
316
317#endif // _LIBCPP_CXX03_LANG
318
319template <class _R1, class _R2>
320struct __ratio_divide
321{
322private:
323    static const intmax_t __gcd_n1_n2 = __static_gcd<_R1::num, _R2::num>::value;
324    static const intmax_t __gcd_d1_d2 = __static_gcd<_R1::den, _R2::den>::value;
325public:
326    typedef typename ratio
327        <
328            __ll_mul<_R1::num / __gcd_n1_n2, _R2::den / __gcd_d1_d2>::value,
329            __ll_mul<_R2::num / __gcd_n1_n2, _R1::den / __gcd_d1_d2>::value
330        >::type type;
331};
332
333#ifndef _LIBCPP_CXX03_LANG
334
335template <class _R1, class _R2> using ratio_divide
336                                      = typename __ratio_divide<_R1, _R2>::type;
337
338#else  // _LIBCPP_CXX03_LANG
339
340template <class _R1, class _R2>
341struct _LIBCPP_TEMPLATE_VIS ratio_divide
342    : public __ratio_divide<_R1, _R2>::type {};
343
344#endif // _LIBCPP_CXX03_LANG
345
346template <class _R1, class _R2>
347struct __ratio_add
348{
349private:
350    static const intmax_t __gcd_n1_n2 = __static_gcd<_R1::num, _R2::num>::value;
351    static const intmax_t __gcd_d1_d2 = __static_gcd<_R1::den, _R2::den>::value;
352public:
353    typedef typename ratio_multiply
354        <
355            ratio<__gcd_n1_n2, _R1::den / __gcd_d1_d2>,
356            ratio
357            <
358                __ll_add
359                <
360                    __ll_mul<_R1::num / __gcd_n1_n2, _R2::den / __gcd_d1_d2>::value,
361                    __ll_mul<_R2::num / __gcd_n1_n2, _R1::den / __gcd_d1_d2>::value
362                >::value,
363                _R2::den
364            >
365        >::type type;
366};
367
368#ifndef _LIBCPP_CXX03_LANG
369
370template <class _R1, class _R2> using ratio_add
371                                         = typename __ratio_add<_R1, _R2>::type;
372
373#else  // _LIBCPP_CXX03_LANG
374
375template <class _R1, class _R2>
376struct _LIBCPP_TEMPLATE_VIS ratio_add
377    : public __ratio_add<_R1, _R2>::type {};
378
379#endif // _LIBCPP_CXX03_LANG
380
381template <class _R1, class _R2>
382struct __ratio_subtract
383{
384private:
385    static const intmax_t __gcd_n1_n2 = __static_gcd<_R1::num, _R2::num>::value;
386    static const intmax_t __gcd_d1_d2 = __static_gcd<_R1::den, _R2::den>::value;
387public:
388    typedef typename ratio_multiply
389        <
390            ratio<__gcd_n1_n2, _R1::den / __gcd_d1_d2>,
391            ratio
392            <
393                __ll_sub
394                <
395                    __ll_mul<_R1::num / __gcd_n1_n2, _R2::den / __gcd_d1_d2>::value,
396                    __ll_mul<_R2::num / __gcd_n1_n2, _R1::den / __gcd_d1_d2>::value
397                >::value,
398                _R2::den
399            >
400        >::type type;
401};
402
403#ifndef _LIBCPP_CXX03_LANG
404
405template <class _R1, class _R2> using ratio_subtract
406                                    = typename __ratio_subtract<_R1, _R2>::type;
407
408#else  // _LIBCPP_CXX03_LANG
409
410template <class _R1, class _R2>
411struct _LIBCPP_TEMPLATE_VIS ratio_subtract
412    : public __ratio_subtract<_R1, _R2>::type {};
413
414#endif // _LIBCPP_CXX03_LANG
415
416// ratio_equal
417
418template <class _R1, class _R2>
419struct _LIBCPP_TEMPLATE_VIS ratio_equal
420    : _BoolConstant<(_R1::num == _R2::num && _R1::den == _R2::den)> {};
421
422template <class _R1, class _R2>
423struct _LIBCPP_TEMPLATE_VIS ratio_not_equal
424    : _BoolConstant<!ratio_equal<_R1, _R2>::value> {};
425
426// ratio_less
427
428template <class _R1, class _R2, bool _Odd = false,
429          intmax_t _Q1 = _R1::num / _R1::den, intmax_t _M1 = _R1::num % _R1::den,
430          intmax_t _Q2 = _R2::num / _R2::den, intmax_t _M2 = _R2::num % _R2::den>
431struct __ratio_less1
432{
433    static const bool value = _Odd ? _Q2 < _Q1 : _Q1 < _Q2;
434};
435
436template <class _R1, class _R2, bool _Odd, intmax_t _Qp>
437struct __ratio_less1<_R1, _R2, _Odd, _Qp, 0, _Qp, 0>
438{
439    static const bool value = false;
440};
441
442template <class _R1, class _R2, bool _Odd, intmax_t _Qp, intmax_t _M2>
443struct __ratio_less1<_R1, _R2, _Odd, _Qp, 0, _Qp, _M2>
444{
445    static const bool value = !_Odd;
446};
447
448template <class _R1, class _R2, bool _Odd, intmax_t _Qp, intmax_t _M1>
449struct __ratio_less1<_R1, _R2, _Odd, _Qp, _M1, _Qp, 0>
450{
451    static const bool value = _Odd;
452};
453
454template <class _R1, class _R2, bool _Odd, intmax_t _Qp, intmax_t _M1,
455                                                        intmax_t _M2>
456struct __ratio_less1<_R1, _R2, _Odd, _Qp, _M1, _Qp, _M2>
457{
458    static const bool value = __ratio_less1<ratio<_R1::den, _M1>,
459                                            ratio<_R2::den, _M2>, !_Odd>::value;
460};
461
462template <class _R1, class _R2, intmax_t _S1 = __static_sign<_R1::num>::value,
463                                intmax_t _S2 = __static_sign<_R2::num>::value>
464struct __ratio_less
465{
466    static const bool value = _S1 < _S2;
467};
468
469template <class _R1, class _R2>
470struct __ratio_less<_R1, _R2, 1LL, 1LL>
471{
472    static const bool value = __ratio_less1<_R1, _R2>::value;
473};
474
475template <class _R1, class _R2>
476struct __ratio_less<_R1, _R2, -1LL, -1LL>
477{
478    static const bool value = __ratio_less1<ratio<-_R2::num, _R2::den>, ratio<-_R1::num, _R1::den> >::value;
479};
480
481template <class _R1, class _R2>
482struct _LIBCPP_TEMPLATE_VIS ratio_less
483    : _BoolConstant<__ratio_less<_R1, _R2>::value> {};
484
485template <class _R1, class _R2>
486struct _LIBCPP_TEMPLATE_VIS ratio_less_equal
487    : _BoolConstant<!ratio_less<_R2, _R1>::value> {};
488
489template <class _R1, class _R2>
490struct _LIBCPP_TEMPLATE_VIS ratio_greater
491    : _BoolConstant<ratio_less<_R2, _R1>::value> {};
492
493template <class _R1, class _R2>
494struct _LIBCPP_TEMPLATE_VIS ratio_greater_equal
495    : _BoolConstant<!ratio_less<_R1, _R2>::value> {};
496
497template <class _R1, class _R2>
498struct __ratio_gcd
499{
500    typedef ratio<__static_gcd<_R1::num, _R2::num>::value,
501                  __static_lcm<_R1::den, _R2::den>::value> type;
502};
503
504#if _LIBCPP_STD_VER > 14
505template <class _R1, class _R2>
506inline constexpr bool ratio_equal_v = ratio_equal<_R1, _R2>::value;
507
508template <class _R1, class _R2>
509inline constexpr bool ratio_not_equal_v = ratio_not_equal<_R1, _R2>::value;
510
511template <class _R1, class _R2>
512inline constexpr bool ratio_less_v = ratio_less<_R1, _R2>::value;
513
514template <class _R1, class _R2>
515inline constexpr bool ratio_less_equal_v = ratio_less_equal<_R1, _R2>::value;
516
517template <class _R1, class _R2>
518inline constexpr bool ratio_greater_v = ratio_greater<_R1, _R2>::value;
519
520template <class _R1, class _R2>
521inline constexpr bool ratio_greater_equal_v = ratio_greater_equal<_R1, _R2>::value;
522#endif
523
524_LIBCPP_END_NAMESPACE_STD
525
526_LIBCPP_POP_MACROS
527
528#endif // _LIBCPP_RATIO
529