]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // ratio.hpp ---------------------------------------------------------------// |
2 | ||
3 | // Copyright 2008 Howard Hinnant | |
4 | // Copyright 2008 Beman Dawes | |
5 | // Copyright 2009 Vicente J. Botet Escriba | |
6 | ||
7 | // Distributed under the Boost Software License, Version 1.0. | |
8 | // See http://www.boost.org/LICENSE_1_0.txt | |
9 | ||
10 | /* | |
11 | ||
12 | This code was derived by Beman Dawes from Howard Hinnant's time2_demo prototype. | |
13 | Many thanks to Howard for making his code available under the Boost license. | |
14 | The original code was modified to conform to Boost conventions and to section | |
15 | 20.4 Compile-time rational arithmetic [ratio], of the C++ committee working | |
16 | paper N2798. | |
17 | See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2798.pdf. | |
18 | ||
19 | time2_demo contained this comment: | |
20 | ||
21 | Much thanks to Andrei Alexandrescu, | |
22 | Walter Brown, | |
23 | Peter Dimov, | |
24 | Jeff Garland, | |
25 | Terry Golubiewski, | |
26 | Daniel Krugler, | |
27 | Anthony Williams. | |
28 | */ | |
29 | ||
30 | // The way overflow is managed for ratio_less is taken from llvm/libcxx/include/ratio | |
31 | ||
32 | #ifndef BOOST_RATIO_DETAIL_RATIO_OPERATIONS_HPP | |
33 | #define BOOST_RATIO_DETAIL_RATIO_OPERATIONS_HPP | |
34 | ||
35 | #include <boost/ratio/config.hpp> | |
36 | #include <boost/ratio/detail/mpl/abs.hpp> | |
37 | #include <boost/ratio/detail/mpl/sign.hpp> | |
38 | #include <cstdlib> | |
39 | #include <climits> | |
40 | #include <limits> | |
41 | #include <boost/cstdint.hpp> | |
42 | #include <boost/type_traits/integral_constant.hpp> | |
43 | #include <boost/core/enable_if.hpp> | |
44 | #include <boost/integer_traits.hpp> | |
45 | ||
46 | // | |
47 | // We simply cannot include this header on gcc without getting copious warnings of the kind: | |
48 | // | |
49 | // boost/integer.hpp:77:30: warning: use of C99 long long integer constant | |
50 | // | |
51 | // And yet there is no other reasonable implementation, so we declare this a system header | |
52 | // to suppress these warnings. | |
53 | // | |
54 | #if defined(__GNUC__) && (__GNUC__ >= 4) | |
55 | #pragma GCC system_header | |
56 | #endif | |
57 | ||
58 | namespace boost | |
59 | { | |
60 | ||
61 | //----------------------------------------------------------------------------// | |
62 | // helpers // | |
63 | //----------------------------------------------------------------------------// | |
64 | ||
65 | namespace ratio_detail | |
66 | { | |
67 | ||
68 | template <boost::intmax_t X, boost::intmax_t Y, boost::intmax_t = mpl::sign_c<boost::intmax_t, Y>::value> | |
69 | class br_add; | |
70 | ||
71 | template <boost::intmax_t X, boost::intmax_t Y> | |
72 | class br_add<X, Y, 1> | |
73 | { | |
74 | static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min; | |
75 | static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max; | |
76 | ||
77 | BOOST_RATIO_STATIC_ASSERT(X <= max - Y , BOOST_RATIO_OVERFLOW_IN_ADD, ()); | |
78 | public: | |
79 | static const boost::intmax_t value = X + Y; | |
80 | }; | |
81 | ||
82 | template <boost::intmax_t X, boost::intmax_t Y> | |
83 | class br_add<X, Y, 0> | |
84 | { | |
85 | public: | |
86 | static const boost::intmax_t value = X; | |
87 | }; | |
88 | ||
89 | template <boost::intmax_t X, boost::intmax_t Y> | |
90 | class br_add<X, Y, -1> | |
91 | { | |
92 | static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min; | |
93 | static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max; | |
94 | ||
95 | BOOST_RATIO_STATIC_ASSERT(min - Y <= X, BOOST_RATIO_OVERFLOW_IN_ADD, ()); | |
96 | public: | |
97 | static const boost::intmax_t value = X + Y; | |
98 | }; | |
99 | ||
100 | template <boost::intmax_t X, boost::intmax_t Y, boost::intmax_t = mpl::sign_c<boost::intmax_t, Y>::value> | |
101 | class br_sub; | |
102 | ||
103 | template <boost::intmax_t X, boost::intmax_t Y> | |
104 | class br_sub<X, Y, 1> | |
105 | { | |
106 | static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min; | |
107 | static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max; | |
108 | ||
109 | BOOST_RATIO_STATIC_ASSERT(min + Y <= X, BOOST_RATIO_OVERFLOW_IN_SUB, ()); | |
110 | public: | |
111 | static const boost::intmax_t value = X - Y; | |
112 | }; | |
113 | ||
114 | template <boost::intmax_t X, boost::intmax_t Y> | |
115 | class br_sub<X, Y, 0> | |
116 | { | |
117 | public: | |
118 | static const boost::intmax_t value = X; | |
119 | }; | |
120 | ||
121 | template <boost::intmax_t X, boost::intmax_t Y> | |
122 | class br_sub<X, Y, -1> | |
123 | { | |
124 | static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min; | |
125 | static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max; | |
126 | ||
127 | BOOST_RATIO_STATIC_ASSERT(X <= max + Y, BOOST_RATIO_OVERFLOW_IN_SUB, ()); | |
128 | public: | |
129 | static const boost::intmax_t value = X - Y; | |
130 | }; | |
131 | ||
132 | template <boost::intmax_t X, boost::intmax_t Y> | |
133 | class br_mul | |
134 | { | |
135 | static const boost::intmax_t nan = | |
136 | boost::intmax_t(BOOST_RATIO_UINTMAX_C(1) << (sizeof(boost::intmax_t) * CHAR_BIT - 1)); | |
137 | static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min; | |
138 | static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max; | |
139 | ||
140 | static const boost::intmax_t a_x = mpl::abs_c<boost::intmax_t, X>::value; | |
141 | static const boost::intmax_t a_y = mpl::abs_c<boost::intmax_t, Y>::value; | |
142 | ||
143 | BOOST_RATIO_STATIC_ASSERT(X != nan, BOOST_RATIO_OVERFLOW_IN_MUL, ()); | |
144 | BOOST_RATIO_STATIC_ASSERT(Y != nan, BOOST_RATIO_OVERFLOW_IN_MUL, ()); | |
145 | BOOST_RATIO_STATIC_ASSERT(a_x <= max / a_y, BOOST_RATIO_OVERFLOW_IN_MUL, ()); | |
146 | public: | |
147 | static const boost::intmax_t value = X * Y; | |
148 | }; | |
149 | ||
150 | template <boost::intmax_t Y> | |
151 | class br_mul<0, Y> | |
152 | { | |
153 | public: | |
154 | static const boost::intmax_t value = 0; | |
155 | }; | |
156 | ||
157 | template <boost::intmax_t X> | |
158 | class br_mul<X, 0> | |
159 | { | |
160 | public: | |
161 | static const boost::intmax_t value = 0; | |
162 | }; | |
163 | ||
164 | template <> | |
165 | class br_mul<0, 0> | |
166 | { | |
167 | public: | |
168 | static const boost::intmax_t value = 0; | |
169 | }; | |
170 | ||
171 | // Not actually used but left here in case needed in future maintenance | |
172 | template <boost::intmax_t X, boost::intmax_t Y> | |
173 | class br_div | |
174 | { | |
175 | static const boost::intmax_t nan = boost::intmax_t(BOOST_RATIO_UINTMAX_C(1) << (sizeof(boost::intmax_t) * CHAR_BIT - 1)); | |
176 | static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min; | |
177 | static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max; | |
178 | ||
179 | BOOST_RATIO_STATIC_ASSERT(X != nan, BOOST_RATIO_OVERFLOW_IN_DIV, ()); | |
180 | BOOST_RATIO_STATIC_ASSERT(Y != nan, BOOST_RATIO_OVERFLOW_IN_DIV, ()); | |
181 | BOOST_RATIO_STATIC_ASSERT(Y != 0, BOOST_RATIO_DIVIDE_BY_0, ()); | |
182 | public: | |
183 | static const boost::intmax_t value = X / Y; | |
184 | }; | |
185 | ||
186 | // ratio arithmetic | |
187 | template <class R1, class R2> struct ratio_add; | |
188 | template <class R1, class R2> struct ratio_subtract; | |
189 | template <class R1, class R2> struct ratio_multiply; | |
190 | template <class R1, class R2> struct ratio_divide; | |
191 | ||
192 | template <class R1, class R2> | |
193 | struct ratio_add | |
194 | { | |
195 | //The nested typedef type shall be a synonym for ratio<T1, T2>::type where T1 has the value R1::num * | |
196 | //R2::den + R2::num * R1::den and T2 has the value R1::den * R2::den. | |
197 | // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated. | |
198 | private: | |
199 | static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value; | |
200 | static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value; | |
201 | public: | |
202 | // No need to normalize as ratio_multiply is already normalized | |
203 | typedef typename ratio_multiply | |
204 | < | |
205 | ratio<gcd_n1_n2, R1::den / gcd_d1_d2>, | |
206 | ratio | |
207 | < | |
208 | boost::ratio_detail::br_add | |
209 | < | |
210 | boost::ratio_detail::br_mul<R1::num / gcd_n1_n2, R2::den / gcd_d1_d2>::value, | |
211 | boost::ratio_detail::br_mul<R2::num / gcd_n1_n2, R1::den / gcd_d1_d2>::value | |
212 | >::value, | |
213 | R2::den | |
214 | > | |
215 | >::type type; | |
216 | }; | |
217 | template <class R, boost::intmax_t D> | |
218 | struct ratio_add<R, ratio<0,D> > | |
219 | { | |
220 | typedef R type; | |
221 | }; | |
222 | ||
223 | template <class R1, class R2> | |
224 | struct ratio_subtract | |
225 | { | |
226 | //The nested typedef type shall be a synonym for ratio<T1, T2>::type where T1 has the value | |
227 | // R1::num *R2::den - R2::num * R1::den and T2 has the value R1::den * R2::den. | |
228 | // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated. | |
229 | private: | |
230 | static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value; | |
231 | static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value; | |
232 | public: | |
233 | // No need to normalize as ratio_multiply is already normalized | |
234 | typedef typename ratio_multiply | |
235 | < | |
236 | ratio<gcd_n1_n2, R1::den / gcd_d1_d2>, | |
237 | ratio | |
238 | < | |
239 | boost::ratio_detail::br_sub | |
240 | < | |
241 | boost::ratio_detail::br_mul<R1::num / gcd_n1_n2, R2::den / gcd_d1_d2>::value, | |
242 | boost::ratio_detail::br_mul<R2::num / gcd_n1_n2, R1::den / gcd_d1_d2>::value | |
243 | >::value, | |
244 | R2::den | |
245 | > | |
246 | >::type type; | |
247 | }; | |
248 | ||
249 | template <class R, boost::intmax_t D> | |
250 | struct ratio_subtract<R, ratio<0,D> > | |
251 | { | |
252 | typedef R type; | |
253 | }; | |
254 | ||
255 | template <class R1, class R2> | |
256 | struct ratio_multiply | |
257 | { | |
258 | // The nested typedef type shall be a synonym for ratio<R1::num * R2::den - R2::num * R1::den, R1::den * R2::den>::type. | |
259 | // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated. | |
260 | private: | |
261 | static const boost::intmax_t gcd_n1_d2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::den>::value; | |
262 | static const boost::intmax_t gcd_d1_n2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::num>::value; | |
263 | public: | |
264 | typedef typename ratio | |
265 | < | |
266 | boost::ratio_detail::br_mul<R1::num / gcd_n1_d2, R2::num / gcd_d1_n2>::value, | |
267 | boost::ratio_detail::br_mul<R2::den / gcd_n1_d2, R1::den / gcd_d1_n2>::value | |
268 | >::type type; | |
269 | }; | |
270 | ||
271 | template <class R1, class R2> | |
272 | struct ratio_divide | |
273 | { | |
274 | // The nested typedef type shall be a synonym for ratio<R1::num * R2::den, R2::num * R1::den>::type. | |
275 | // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated. | |
276 | private: | |
277 | static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value; | |
278 | static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value; | |
279 | public: | |
280 | typedef typename ratio | |
281 | < | |
282 | boost::ratio_detail::br_mul<R1::num / gcd_n1_n2, R2::den / gcd_d1_d2>::value, | |
283 | boost::ratio_detail::br_mul<R2::num / gcd_n1_n2, R1::den / gcd_d1_d2>::value | |
284 | >::type type; | |
285 | }; | |
286 | template <class R1, class R2> | |
287 | struct is_evenly_divisible_by | |
288 | { | |
289 | private: | |
290 | static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value; | |
291 | static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value; | |
292 | public: | |
293 | typedef integral_constant<bool, | |
294 | ((R2::num / gcd_n1_n2 ==1) && (R1::den / gcd_d1_d2)==1) | |
295 | > type; | |
296 | }; | |
297 | ||
298 | template <class T> | |
299 | struct is_ratio : public boost::false_type | |
300 | {}; | |
301 | template <boost::intmax_t N, boost::intmax_t D> | |
302 | struct is_ratio<ratio<N, D> > : public boost::true_type | |
303 | {}; | |
304 | ||
305 | template <class R1, class R2, | |
306 | boost::intmax_t Q1 = R1::num / R1::den, boost::intmax_t M1 = R1::num % R1::den, | |
307 | boost::intmax_t Q2 = R2::num / R2::den, boost::intmax_t M2 = R2::num % R2::den> | |
308 | struct ratio_less1 | |
309 | { | |
310 | static const bool value = Q1 < Q2; | |
311 | }; | |
312 | ||
313 | template <class R1, class R2, boost::intmax_t Q> | |
314 | struct ratio_less1<R1, R2, Q, 0, Q, 0> | |
315 | { | |
316 | static const bool value = false; | |
317 | }; | |
318 | ||
319 | template <class R1, class R2, boost::intmax_t Q, boost::intmax_t M2> | |
320 | struct ratio_less1<R1, R2, Q, 0, Q, M2> | |
321 | { | |
322 | static const bool value = true; | |
323 | }; | |
324 | ||
325 | template <class R1, class R2, boost::intmax_t Q, boost::intmax_t M1> | |
326 | struct ratio_less1<R1, R2, Q, M1, Q, 0> | |
327 | { | |
328 | static const bool value = false; | |
329 | }; | |
330 | ||
331 | template <class R1, class R2, boost::intmax_t Q, boost::intmax_t M1, boost::intmax_t M2> | |
332 | struct ratio_less1<R1, R2, Q, M1, Q, M2> | |
333 | { | |
334 | static const bool value = ratio_less1<ratio<R2::den, M2>, ratio<R1::den, M1> | |
335 | >::value; | |
336 | }; | |
337 | ||
338 | template < | |
339 | class R1, | |
340 | class R2, | |
341 | boost::intmax_t S1 = mpl::sign_c<boost::intmax_t, R1::num>::value, | |
342 | boost::intmax_t S2 = mpl::sign_c<boost::intmax_t, R2::num>::value | |
343 | > | |
344 | struct ratio_less | |
345 | { | |
346 | static const bool value = S1 < S2; | |
347 | }; | |
348 | ||
349 | template <class R1, class R2> | |
350 | struct ratio_less<R1, R2, 1LL, 1LL> | |
351 | { | |
352 | static const bool value = ratio_less1<R1, R2>::value; | |
353 | }; | |
354 | ||
355 | template <class R1, class R2> | |
356 | struct ratio_less<R1, R2, -1LL, -1LL> | |
357 | { | |
358 | static const bool value = ratio_less1<ratio<-R2::num, R2::den>, | |
359 | ratio<-R1::num, R1::den> >::value; | |
360 | }; | |
361 | ||
362 | ||
363 | } // namespace ratio_detail | |
364 | ||
365 | } // namespace boost | |
366 | ||
367 | #endif // BOOST_RATIO_HPP |