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