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 |
368 | |