]>
Commit | Line | Data |
---|---|---|
4acedca1 CF |
1 | // <ratio> -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2008 Free Software Foundation, Inc. | |
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 | { | |
50 | template<intmax_t _Pn> | |
51 | struct __static_sign | |
52 | : integral_constant<intmax_t, (_Pn < 0) ? -1 : 1> | |
53 | { }; | |
54 | ||
55 | template<intmax_t _Pn> | |
56 | struct __static_abs | |
57 | : integral_constant<intmax_t, _Pn * __static_sign<_Pn>::value> | |
58 | { }; | |
59 | ||
60 | template<intmax_t _Pn, intmax_t _Qn> | |
61 | struct __static_gcd; | |
62 | ||
63 | template<intmax_t _Pn, intmax_t _Qn> | |
64 | struct __static_gcd | |
65 | : __static_gcd<_Qn, (_Pn % _Qn)> | |
66 | { }; | |
67 | ||
68 | template<intmax_t _Pn> | |
69 | struct __static_gcd<_Pn, 0> | |
70 | : integral_constant<intmax_t, __static_abs<_Pn>::value> | |
71 | { }; | |
72 | ||
73 | template<intmax_t _Qn> | |
74 | struct __static_gcd<0, _Qn> | |
75 | : integral_constant<intmax_t, __static_abs<_Qn>::value> | |
76 | { }; | |
77 | ||
78 | // Let c = 2^(half # of bits in an intmax_t) | |
79 | // then we find a1, a0, b1, b0 s.t. N = a1*c + a0, M = b1*c + b0 | |
80 | // The multiplication of N and M becomes, | |
81 | // N * M = (a1 * b1)c^2 + (a0 * b1 + b0 * a1)c + a0 * b0 | |
82 | // Multiplication is safe if each term and the sum of the terms | |
83 | // is representable by intmax_t. | |
84 | template<intmax_t _Pn, intmax_t _Qn> | |
85 | struct __safe_multiply | |
86 | { | |
87 | private: | |
88 | static const uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4); | |
89 | ||
90 | static const uintmax_t __a0 = __static_abs<_Pn>::value % __c; | |
91 | static const uintmax_t __a1 = __static_abs<_Pn>::value / __c; | |
92 | static const uintmax_t __b0 = __static_abs<_Qn>::value % __c; | |
93 | static const uintmax_t __b1 = __static_abs<_Qn>::value / __c; | |
94 | ||
95 | static_assert(__a1 == 0 || __b1 == 0, | |
96 | "overflow in multiplication"); | |
97 | static_assert(__a0 * __b1 + __b0 * __a1 < (__c >> 1), | |
98 | "overflow in multiplication"); | |
ea31932d | 99 | static_assert(__b0 * __a0 <= __INTMAX_MAX__, |
4acedca1 CF |
100 | "overflow in multiplication"); |
101 | static_assert((__a0 * __b1 + __b0 * __a1) * __c <= | |
ea31932d | 102 | __INTMAX_MAX__ - __b0 * __a0, "overflow in multiplication"); |
4acedca1 CF |
103 | |
104 | public: | |
105 | static const intmax_t value = _Pn * _Qn; | |
106 | }; | |
107 | ||
108 | // Helpers for __safe_add | |
109 | template<intmax_t _Pn, intmax_t _Qn, bool> | |
110 | struct __add_overflow_check_impl | |
ea31932d | 111 | : integral_constant<bool, (_Pn <= __INTMAX_MAX__ - _Qn)> |
4acedca1 CF |
112 | { }; |
113 | ||
114 | template<intmax_t _Pn, intmax_t _Qn> | |
115 | struct __add_overflow_check_impl<_Pn, _Qn, false> | |
ea31932d | 116 | : integral_constant<bool, (_Pn >= -__INTMAX_MAX__ - _Qn)> |
4acedca1 CF |
117 | { }; |
118 | ||
119 | template<intmax_t _Pn, intmax_t _Qn> | |
120 | struct __add_overflow_check | |
121 | : __add_overflow_check_impl<_Pn, _Qn, (_Qn >= 0)> | |
122 | { }; | |
123 | ||
124 | template<intmax_t _Pn, intmax_t _Qn> | |
125 | struct __safe_add | |
126 | { | |
127 | static_assert(__add_overflow_check<_Pn, _Qn>::value != 0, | |
128 | "overflow in addition"); | |
129 | ||
130 | static const intmax_t value = _Pn + _Qn; | |
131 | }; | |
132 | ||
ea31932d PC |
133 | /** |
134 | * @brief Provides compile-time rational arithmetic. | |
135 | * | |
136 | * This class template represents any finite rational number with a | |
137 | * numerator and denominator representable by compile-time constants of | |
138 | * type intmax_t. The ratio is simplified when instantiated. | |
139 | * | |
140 | * For example: | |
141 | * @code | |
142 | * std::ratio<7,-21>::num == -1; | |
143 | * std::ratio<7,-21>::den == 3; | |
144 | * @endcode | |
145 | * | |
146 | */ | |
4acedca1 CF |
147 | template<intmax_t _Num, intmax_t _Den = 1> |
148 | struct ratio | |
149 | { | |
150 | static_assert(_Den != 0, "denominator cannot be zero"); | |
ea31932d PC |
151 | static_assert(_Num >= -__INTMAX_MAX__ && _Den >= -__INTMAX_MAX__, |
152 | "out of range"); | |
153 | ||
4acedca1 CF |
154 | // Note: sign(N) * abs(N) == N |
155 | static const intmax_t num = | |
156 | _Num * __static_sign<_Den>::value / __static_gcd<_Num, _Den>::value; | |
157 | ||
158 | static const intmax_t den = | |
159 | __static_abs<_Den>::value / __static_gcd<_Num, _Den>::value; | |
160 | }; | |
161 | ||
162 | template<intmax_t _Num, intmax_t _Den> | |
163 | const intmax_t ratio<_Num, _Den>::num; | |
164 | ||
165 | template<intmax_t _Num, intmax_t _Den> | |
166 | const intmax_t ratio<_Num, _Den>::den; | |
167 | ||
ad68e9fc | 168 | /// ratio_add |
4acedca1 CF |
169 | template<typename _R1, typename _R2> |
170 | struct ratio_add | |
171 | { | |
172 | private: | |
173 | static const intmax_t __gcd = | |
174 | __static_gcd<_R1::den, _R2::den>::value; | |
175 | ||
176 | public: | |
177 | typedef ratio< | |
178 | __safe_add< | |
179 | __safe_multiply<_R1::num, (_R2::den / __gcd)>::value, | |
180 | __safe_multiply<_R2::num, (_R1::den / __gcd)>::value>::value, | |
181 | __safe_multiply<_R1::den, (_R2::den / __gcd)>::value> type; | |
182 | }; | |
183 | ||
ad68e9fc | 184 | /// ratio_subtract |
4acedca1 CF |
185 | template<typename _R1, typename _R2> |
186 | struct ratio_subtract | |
187 | { | |
188 | typedef typename ratio_add< | |
189 | _R1, | |
190 | ratio<-_R2::num, _R2::den>>::type type; | |
191 | }; | |
192 | ||
ad68e9fc | 193 | /// ratio_multiply |
4acedca1 CF |
194 | template<typename _R1, typename _R2> |
195 | struct ratio_multiply | |
196 | { | |
197 | private: | |
198 | static const intmax_t __gcd1 = | |
199 | __static_gcd<_R1::num, _R2::den>::value; | |
200 | static const intmax_t __gcd2 = | |
201 | __static_gcd<_R2::num, _R1::den>::value; | |
202 | ||
203 | public: | |
204 | typedef ratio< | |
205 | __safe_multiply<(_R1::num / __gcd1), | |
206 | (_R2::num / __gcd2)>::value, | |
207 | __safe_multiply<(_R1::den / __gcd2), | |
208 | (_R2::den / __gcd1)>::value> type; | |
209 | }; | |
210 | ||
ad68e9fc | 211 | /// ratio_divide |
4acedca1 CF |
212 | template<typename _R1, typename _R2> |
213 | struct ratio_divide | |
214 | { | |
215 | static_assert(_R2::num != 0, "division by 0"); | |
216 | ||
217 | typedef typename ratio_multiply< | |
218 | _R1, | |
219 | ratio<_R2::den, _R2::num>>::type type; | |
220 | }; | |
221 | ||
ad68e9fc | 222 | /// ratio_equal |
4acedca1 CF |
223 | template<typename _R1, typename _R2> |
224 | struct ratio_equal | |
225 | : integral_constant<bool, _R1::num == _R2::num && _R1::den == _R2::den> | |
226 | { }; | |
227 | ||
ad68e9fc | 228 | /// ratio_not_equal |
4acedca1 CF |
229 | template<typename _R1, typename _R2> |
230 | struct ratio_not_equal | |
231 | : integral_constant<bool, !ratio_equal<_R1, _R2>::value> | |
232 | { }; | |
233 | ||
234 | template<typename _R1, typename _R2> | |
ea31932d | 235 | struct __ratio_less_simple_impl |
4acedca1 | 236 | : integral_constant<bool, |
ea31932d PC |
237 | (__safe_multiply<_R1::num, _R2::den>::value |
238 | < __safe_multiply<_R2::num, _R1::den>::value)> | |
239 | { }; | |
240 | ||
241 | // If the denominators are equal or the signs differ, we can just compare | |
242 | // numerators, otherwise fallback to the simple cross-multiply method. | |
243 | template<typename _R1, typename _R2> | |
244 | struct __ratio_less_impl | |
245 | : conditional<(_R1::den == _R2::den | |
246 | || (__static_sign<_R1::num>::value | |
247 | != __static_sign<_R2::num>::value)), | |
248 | integral_constant<bool, (_R1::num < _R2::num)>, | |
249 | __ratio_less_simple_impl<_R1, _R2>>::type | |
250 | { }; | |
251 | ||
ad68e9fc | 252 | /// ratio_less |
ea31932d PC |
253 | template<typename _R1, typename _R2> |
254 | struct ratio_less | |
255 | : __ratio_less_impl<_R1, _R2>::type | |
4acedca1 CF |
256 | { }; |
257 | ||
ad68e9fc | 258 | /// ratio_less_equal |
4acedca1 CF |
259 | template<typename _R1, typename _R2> |
260 | struct ratio_less_equal | |
261 | : integral_constant<bool, !ratio_less<_R2, _R1>::value> | |
262 | { }; | |
263 | ||
ad68e9fc | 264 | /// ratio_greater |
4acedca1 CF |
265 | template<typename _R1, typename _R2> |
266 | struct ratio_greater | |
267 | : integral_constant<bool, ratio_less<_R2, _R1>::value> | |
268 | { }; | |
269 | ||
ad68e9fc | 270 | /// ratio_greater_equal |
4acedca1 CF |
271 | template<typename _R1, typename _R2> |
272 | struct ratio_greater_equal | |
273 | : integral_constant<bool, !ratio_less<_R1, _R2>::value> | |
274 | { }; | |
275 | ||
276 | typedef ratio<1, 1000000000000000000> atto; | |
277 | typedef ratio<1, 1000000000000000> femto; | |
278 | typedef ratio<1, 1000000000000> pico; | |
279 | typedef ratio<1, 1000000000> nano; | |
280 | typedef ratio<1, 1000000> micro; | |
281 | typedef ratio<1, 1000> milli; | |
282 | typedef ratio<1, 100> centi; | |
283 | typedef ratio<1, 10> deci; | |
284 | typedef ratio< 10, 1> deca; | |
285 | typedef ratio< 100, 1> hecto; | |
286 | typedef ratio< 1000, 1> kilo; | |
287 | typedef ratio< 1000000, 1> mega; | |
288 | typedef ratio< 1000000000, 1> giga; | |
289 | typedef ratio< 1000000000000, 1> tera; | |
290 | typedef ratio< 1000000000000000, 1> peta; | |
291 | typedef ratio< 1000000000000000000, 1> exa; | |
292 | } | |
293 | ||
294 | #endif //_GLIBCXX_USE_C99_STDINT_TR1 | |
295 | ||
296 | #endif //__GXX_EXPERIMENTAL_CXX0X__ | |
297 | ||
298 | #endif //_GLIBCXX_RATIO |