1import operator
2import sys
3from .libmp import int_types, mpf_hash, bitcount, from_man_exp, HASH_MODULUS
4
5new = object.__new__
6
7def create_reduced(p, q, _cache={}):
8    key = p, q
9    if key in _cache:
10        return _cache[key]
11    x, y = p, q
12    while y:
13        x, y = y, x % y
14    if x != 1:
15        p //= x
16        q //= x
17    v = new(mpq)
18    v._mpq_ = p, q
19    # Speedup integers, half-integers and other small fractions
20    if q <= 4 and abs(key[0]) < 100:
21        _cache[key] = v
22    return v
23
24class mpq(object):
25    """
26    Exact rational type, currently only intended for internal use.
27    """
28
29    __slots__ = ["_mpq_"]
30
31    def __new__(cls, p, q=1):
32        if type(p) is tuple:
33            p, q = p
34        elif hasattr(p, '_mpq_'):
35            p, q = p._mpq_
36        return create_reduced(p, q)
37
38    def __repr__(s):
39        return "mpq(%s,%s)" % s._mpq_
40
41    def __str__(s):
42        return "(%s/%s)" % s._mpq_
43
44    def __int__(s):
45        a, b = s._mpq_
46        return a // b
47
48    def __nonzero__(s):
49        return bool(s._mpq_[0])
50
51    __bool__ = __nonzero__
52
53    def __hash__(s):
54        a, b = s._mpq_
55        if sys.version_info >= (3, 2):
56            inverse = pow(b, HASH_MODULUS-2, HASH_MODULUS)
57            if not inverse:
58                h = sys.hash_info.inf
59            else:
60                h = (abs(a) * inverse) % HASH_MODULUS
61            if a < 0: h = -h
62            if h == -1: h = -2
63            return h
64        else:
65            if b == 1:
66                return hash(a)
67            # Power of two: mpf compatible hash
68            if not (b & (b-1)):
69                return mpf_hash(from_man_exp(a, 1-bitcount(b)))
70            return hash((a,b))
71
72    def __eq__(s, t):
73        ttype = type(t)
74        if ttype is mpq:
75            return s._mpq_ == t._mpq_
76        if ttype in int_types:
77            a, b = s._mpq_
78            if b != 1:
79                return False
80            return a == t
81        return NotImplemented
82
83    def __ne__(s, t):
84        ttype = type(t)
85        if ttype is mpq:
86            return s._mpq_ != t._mpq_
87        if ttype in int_types:
88            a, b = s._mpq_
89            if b != 1:
90                return True
91            return a != t
92        return NotImplemented
93
94    def _cmp(s, t, op):
95        ttype = type(t)
96        if ttype in int_types:
97            a, b = s._mpq_
98            return op(a, t*b)
99        if ttype is mpq:
100            a, b = s._mpq_
101            c, d = t._mpq_
102            return op(a*d, b*c)
103        return NotImplementedError
104
105    def __lt__(s, t): return s._cmp(t, operator.lt)
106    def __le__(s, t): return s._cmp(t, operator.le)
107    def __gt__(s, t): return s._cmp(t, operator.gt)
108    def __ge__(s, t): return s._cmp(t, operator.ge)
109
110    def __abs__(s):
111        a, b = s._mpq_
112        if a >= 0:
113            return s
114        v = new(mpq)
115        v._mpq_ = -a, b
116        return v
117
118    def __neg__(s):
119        a, b = s._mpq_
120        v = new(mpq)
121        v._mpq_ = -a, b
122        return v
123
124    def __pos__(s):
125        return s
126
127    def __add__(s, t):
128        ttype = type(t)
129        if ttype is mpq:
130            a, b = s._mpq_
131            c, d = t._mpq_
132            return create_reduced(a*d+b*c, b*d)
133        if ttype in int_types:
134            a, b = s._mpq_
135            v = new(mpq)
136            v._mpq_ = a+b*t, b
137            return v
138        return NotImplemented
139
140    __radd__ = __add__
141
142    def __sub__(s, t):
143        ttype = type(t)
144        if ttype is mpq:
145            a, b = s._mpq_
146            c, d = t._mpq_
147            return create_reduced(a*d-b*c, b*d)
148        if ttype in int_types:
149            a, b = s._mpq_
150            v = new(mpq)
151            v._mpq_ = a-b*t, b
152            return v
153        return NotImplemented
154
155    def __rsub__(s, t):
156        ttype = type(t)
157        if ttype is mpq:
158            a, b = s._mpq_
159            c, d = t._mpq_
160            return create_reduced(b*c-a*d, b*d)
161        if ttype in int_types:
162            a, b = s._mpq_
163            v = new(mpq)
164            v._mpq_ = b*t-a, b
165            return v
166        return NotImplemented
167
168    def __mul__(s, t):
169        ttype = type(t)
170        if ttype is mpq:
171            a, b = s._mpq_
172            c, d = t._mpq_
173            return create_reduced(a*c, b*d)
174        if ttype in int_types:
175            a, b = s._mpq_
176            return create_reduced(a*t, b)
177        return NotImplemented
178
179    __rmul__ = __mul__
180
181    def __div__(s, t):
182        ttype = type(t)
183        if ttype is mpq:
184            a, b = s._mpq_
185            c, d = t._mpq_
186            return create_reduced(a*d, b*c)
187        if ttype in int_types:
188            a, b = s._mpq_
189            return create_reduced(a, b*t)
190        return NotImplemented
191
192    def __rdiv__(s, t):
193        ttype = type(t)
194        if ttype is mpq:
195            a, b = s._mpq_
196            c, d = t._mpq_
197            return create_reduced(b*c, a*d)
198        if ttype in int_types:
199            a, b = s._mpq_
200            return create_reduced(b*t, a)
201        return NotImplemented
202
203    def __pow__(s, t):
204        ttype = type(t)
205        if ttype in int_types:
206            a, b = s._mpq_
207            if t:
208                if t < 0:
209                    a, b, t = b, a, -t
210                v = new(mpq)
211                v._mpq_ = a**t, b**t
212                return v
213            raise ZeroDivisionError
214        return NotImplemented
215
216
217mpq_1 = mpq((1,1))
218mpq_0 = mpq((0,1))
219mpq_1_2 = mpq((1,2))
220mpq_3_2 = mpq((3,2))
221mpq_1_4 = mpq((1,4))
222mpq_1_16 = mpq((1,16))
223mpq_3_16 = mpq((3,16))
224mpq_5_2 = mpq((5,2))
225mpq_3_4 = mpq((3,4))
226mpq_7_4 = mpq((7,4))
227mpq_5_4 = mpq((5,4))
228
229
230# Register with "numbers" ABC
231#     We do not subclass, hence we do not use the @abstractmethod checks. While
232#     this is less invasive it may turn out that we do not actually support
233#     parts of the expected interfaces.  See
234#     http://docs.python.org/2/library/numbers.html for list of abstract
235#     methods.
236try:
237    import numbers
238    numbers.Rational.register(mpq)
239except ImportError:
240    pass
241