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