]>
Commit | Line | Data |
---|---|---|
5b9daa7e | 1 | // ratio -*- C++ -*- |
4acedca1 | 2 | |
5b9daa7e | 3 | // Copyright (C) 2008, 2009 Free Software Foundation, Inc. |
4acedca1 CF |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
4acedca1 CF |
9 | // any later version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
4acedca1 | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
4acedca1 CF |
24 | |
25 | /** @file ratio | |
26 | * This is a Standard C++ Library header. | |
27 | */ | |
28 | ||
29 | #ifndef _GLIBCXX_RATIO | |
30 | #define _GLIBCXX_RATIO 1 | |
31 | ||
32 | #pragma GCC system_header | |
33 | ||
34 | #ifndef __GXX_EXPERIMENTAL_CXX0X__ | |
35 | # include <c++0x_warning.h> | |
36 | #else | |
37 | ||
38 | #include <type_traits> | |
39 | #include <cstdint> | |
40 | ||
41 | #ifdef _GLIBCXX_USE_C99_STDINT_TR1 | |
42 | ||
43 | namespace std | |
44 | { | |
5b9daa7e BK |
45 | /** |
46 | * @defgroup ratio Rational Arithmetic | |
47 | * @ingroup utilities | |
48 | * | |
79e2c7b0 | 49 | * Compile time representation of finite rational numbers. |
5b9daa7e BK |
50 | * @{ |
51 | */ | |
52 | ||
4acedca1 CF |
53 | template<intmax_t _Pn> |
54 | struct __static_sign | |
55 | : integral_constant<intmax_t, (_Pn < 0) ? -1 : 1> | |
56 | { }; | |
57 | ||
58 | template<intmax_t _Pn> | |
59 | struct __static_abs | |
60 | : integral_constant<intmax_t, _Pn * __static_sign<_Pn>::value> | |
61 | { }; | |
62 | ||
63 | template<intmax_t _Pn, intmax_t _Qn> | |
64 | struct __static_gcd; | |
65 | ||
66 | template<intmax_t _Pn, intmax_t _Qn> | |
67 | struct __static_gcd | |
68 | : __static_gcd<_Qn, (_Pn % _Qn)> | |
69 | { }; | |
70 | ||
71 | template<intmax_t _Pn> | |
72 | struct __static_gcd<_Pn, 0> | |
73 | : integral_constant<intmax_t, __static_abs<_Pn>::value> | |
74 | { }; | |
75 | ||
76 | template<intmax_t _Qn> | |
77 | struct __static_gcd<0, _Qn> | |
78 | : integral_constant<intmax_t, __static_abs<_Qn>::value> | |
79 | { }; | |
80 | ||
81 | // Let c = 2^(half # of bits in an intmax_t) | |
82 | // then we find a1, a0, b1, b0 s.t. N = a1*c + a0, M = b1*c + b0 | |
83 | // The multiplication of N and M becomes, | |
84 | // N * M = (a1 * b1)c^2 + (a0 * b1 + b0 * a1)c + a0 * b0 | |
85 | // Multiplication is safe if each term and the sum of the terms | |
86 | // is representable by intmax_t. | |
87 | template<intmax_t _Pn, intmax_t _Qn> | |
88 | struct __safe_multiply | |
89 | { | |
90 | private: | |
91 | static const uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4); | |
92 | ||
93 | static const uintmax_t __a0 = __static_abs<_Pn>::value % __c; | |
94 | static const uintmax_t __a1 = __static_abs<_Pn>::value / __c; | |
95 | static const uintmax_t __b0 = __static_abs<_Qn>::value % __c; | |
96 | static const uintmax_t __b1 = __static_abs<_Qn>::value / __c; | |
97 | ||
98 | static_assert(__a1 == 0 || __b1 == 0, | |
99 | "overflow in multiplication"); | |
100 | static_assert(__a0 * __b1 + __b0 * __a1 < (__c >> 1), | |
101 | "overflow in multiplication"); | |
ea31932d | 102 | static_assert(__b0 * __a0 <= __INTMAX_MAX__, |
4acedca1 CF |
103 | "overflow in multiplication"); |
104 | static_assert((__a0 * __b1 + __b0 * __a1) * __c <= | |
ea31932d | 105 | __INTMAX_MAX__ - __b0 * __a0, "overflow in multiplication"); |
4acedca1 CF |
106 | |
107 | public: | |
108 | static const intmax_t value = _Pn * _Qn; | |
109 | }; | |
110 | ||
111 | // Helpers for __safe_add | |
112 | template<intmax_t _Pn, intmax_t _Qn, bool> | |
113 | struct __add_overflow_check_impl | |
ea31932d | 114 | : integral_constant<bool, (_Pn <= __INTMAX_MAX__ - _Qn)> |
4acedca1 CF |
115 | { }; |
116 | ||
117 | template<intmax_t _Pn, intmax_t _Qn> | |
118 | struct __add_overflow_check_impl<_Pn, _Qn, false> | |
ea31932d | 119 | : integral_constant<bool, (_Pn >= -__INTMAX_MAX__ - _Qn)> |
4acedca1 CF |
120 | { }; |
121 | ||
122 | template<intmax_t _Pn, intmax_t _Qn> | |
123 | struct __add_overflow_check | |
124 | : __add_overflow_check_impl<_Pn, _Qn, (_Qn >= 0)> | |
125 | { }; | |
126 | ||
127 | template<intmax_t _Pn, intmax_t _Qn> | |
128 | struct __safe_add | |
129 | { | |
130 | static_assert(__add_overflow_check<_Pn, _Qn>::value != 0, | |
131 | "overflow in addition"); | |
132 | ||
133 | static const intmax_t value = _Pn + _Qn; | |
134 | }; | |
135 | ||
ea31932d PC |
136 | /** |
137 | * @brief Provides compile-time rational arithmetic. | |
5b9daa7e | 138 | * |
ea31932d PC |
139 | * This class template represents any finite rational number with a |
140 | * numerator and denominator representable by compile-time constants of | |
141 | * type intmax_t. The ratio is simplified when instantiated. | |
142 | * | |
143 | * For example: | |
144 | * @code | |
145 | * std::ratio<7,-21>::num == -1; | |
146 | * std::ratio<7,-21>::den == 3; | |
147 | * @endcode | |
148 | * | |
149 | */ | |
4acedca1 CF |
150 | template<intmax_t _Num, intmax_t _Den = 1> |
151 | struct ratio | |
152 | { | |
153 | static_assert(_Den != 0, "denominator cannot be zero"); | |
ea31932d PC |
154 | static_assert(_Num >= -__INTMAX_MAX__ && _Den >= -__INTMAX_MAX__, |
155 | "out of range"); | |
156 | ||
4acedca1 CF |
157 | // Note: sign(N) * abs(N) == N |
158 | static const intmax_t num = | |
159 | _Num * __static_sign<_Den>::value / __static_gcd<_Num, _Den>::value; | |
160 | ||
161 | static const intmax_t den = | |
162 | __static_abs<_Den>::value / __static_gcd<_Num, _Den>::value; | |
163 | }; | |
164 | ||
165 | template<intmax_t _Num, intmax_t _Den> | |
166 | const intmax_t ratio<_Num, _Den>::num; | |
167 | ||
168 | template<intmax_t _Num, intmax_t _Den> | |
169 | const intmax_t ratio<_Num, _Den>::den; | |
170 | ||
ad68e9fc | 171 | /// ratio_add |
4acedca1 CF |
172 | template<typename _R1, typename _R2> |
173 | struct ratio_add | |
174 | { | |
175 | private: | |
176 | static const intmax_t __gcd = | |
177 | __static_gcd<_R1::den, _R2::den>::value; | |
178 | ||
179 | public: | |
180 | typedef ratio< | |
181 | __safe_add< | |
182 | __safe_multiply<_R1::num, (_R2::den / __gcd)>::value, | |
183 | __safe_multiply<_R2::num, (_R1::den / __gcd)>::value>::value, | |
184 | __safe_multiply<_R1::den, (_R2::den / __gcd)>::value> type; | |
185 | }; | |
186 | ||
ad68e9fc | 187 | /// ratio_subtract |
4acedca1 CF |
188 | template<typename _R1, typename _R2> |
189 | struct ratio_subtract | |
190 | { | |
191 | typedef typename ratio_add< | |
192 | _R1, | |
193 | ratio<-_R2::num, _R2::den>>::type type; | |
194 | }; | |
195 | ||
ad68e9fc | 196 | /// ratio_multiply |
4acedca1 CF |
197 | template<typename _R1, typename _R2> |
198 | struct ratio_multiply | |
199 | { | |
200 | private: | |
201 | static const intmax_t __gcd1 = | |
202 | __static_gcd<_R1::num, _R2::den>::value; | |
203 | static const intmax_t __gcd2 = | |
204 | __static_gcd<_R2::num, _R1::den>::value; | |
205 | ||
206 | public: | |
207 | typedef ratio< | |
208 | __safe_multiply<(_R1::num / __gcd1), | |
209 | (_R2::num / __gcd2)>::value, | |
210 | __safe_multiply<(_R1::den / __gcd2), | |
211 | (_R2::den / __gcd1)>::value> type; | |
212 | }; | |
213 | ||
ad68e9fc | 214 | /// ratio_divide |
4acedca1 CF |
215 | template<typename _R1, typename _R2> |
216 | struct ratio_divide | |
217 | { | |
218 | static_assert(_R2::num != 0, "division by 0"); | |
219 | ||
220 | typedef typename ratio_multiply< | |
221 | _R1, | |
222 | ratio<_R2::den, _R2::num>>::type type; | |
223 | }; | |
224 | ||
ad68e9fc | 225 | /// ratio_equal |
4acedca1 CF |
226 | template<typename _R1, typename _R2> |
227 | struct ratio_equal | |
228 | : integral_constant<bool, _R1::num == _R2::num && _R1::den == _R2::den> | |
229 | { }; | |
230 | ||
ad68e9fc | 231 | /// ratio_not_equal |
4acedca1 CF |
232 | template<typename _R1, typename _R2> |
233 | struct ratio_not_equal | |
234 | : integral_constant<bool, !ratio_equal<_R1, _R2>::value> | |
235 | { }; | |
236 | ||
237 | template<typename _R1, typename _R2> | |
ea31932d | 238 | struct __ratio_less_simple_impl |
4acedca1 | 239 | : integral_constant<bool, |
ea31932d PC |
240 | (__safe_multiply<_R1::num, _R2::den>::value |
241 | < __safe_multiply<_R2::num, _R1::den>::value)> | |
242 | { }; | |
243 | ||
244 | // If the denominators are equal or the signs differ, we can just compare | |
245 | // numerators, otherwise fallback to the simple cross-multiply method. | |
246 | template<typename _R1, typename _R2> | |
247 | struct __ratio_less_impl | |
248 | : conditional<(_R1::den == _R2::den | |
249 | || (__static_sign<_R1::num>::value | |
250 | != __static_sign<_R2::num>::value)), | |
251 | integral_constant<bool, (_R1::num < _R2::num)>, | |
252 | __ratio_less_simple_impl<_R1, _R2>>::type | |
253 | { }; | |
254 | ||
ad68e9fc | 255 | /// ratio_less |
ea31932d PC |
256 | template<typename _R1, typename _R2> |
257 | struct ratio_less | |
258 | : __ratio_less_impl<_R1, _R2>::type | |
4acedca1 CF |
259 | { }; |
260 | ||
ad68e9fc | 261 | /// ratio_less_equal |
4acedca1 CF |
262 | template<typename _R1, typename _R2> |
263 | struct ratio_less_equal | |
264 | : integral_constant<bool, !ratio_less<_R2, _R1>::value> | |
265 | { }; | |
266 | ||
ad68e9fc | 267 | /// ratio_greater |
4acedca1 CF |
268 | template<typename _R1, typename _R2> |
269 | struct ratio_greater | |
270 | : integral_constant<bool, ratio_less<_R2, _R1>::value> | |
271 | { }; | |
272 | ||
ad68e9fc | 273 | /// ratio_greater_equal |
4acedca1 CF |
274 | template<typename _R1, typename _R2> |
275 | struct ratio_greater_equal | |
276 | : integral_constant<bool, !ratio_less<_R1, _R2>::value> | |
277 | { }; | |
278 | ||
279 | typedef ratio<1, 1000000000000000000> atto; | |
280 | typedef ratio<1, 1000000000000000> femto; | |
281 | typedef ratio<1, 1000000000000> pico; | |
282 | typedef ratio<1, 1000000000> nano; | |
283 | typedef ratio<1, 1000000> micro; | |
284 | typedef ratio<1, 1000> milli; | |
285 | typedef ratio<1, 100> centi; | |
286 | typedef ratio<1, 10> deci; | |
287 | typedef ratio< 10, 1> deca; | |
288 | typedef ratio< 100, 1> hecto; | |
289 | typedef ratio< 1000, 1> kilo; | |
290 | typedef ratio< 1000000, 1> mega; | |
291 | typedef ratio< 1000000000, 1> giga; | |
292 | typedef ratio< 1000000000000, 1> tera; | |
293 | typedef ratio< 1000000000000000, 1> peta; | |
294 | typedef ratio< 1000000000000000000, 1> exa; | |
5b9daa7e BK |
295 | |
296 | // @} group ratio | |
4acedca1 CF |
297 | } |
298 | ||
299 | #endif //_GLIBCXX_USE_C99_STDINT_TR1 | |
300 | ||
301 | #endif //__GXX_EXPERIMENTAL_CXX0X__ | |
302 | ||
303 | #endif //_GLIBCXX_RATIO |