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