source: titan/mediathek/localhoster/lib/python2.7/fractions.py @ 40523

Last change on this file since 40523 was 40094, checked in by obi, 7 years ago

tithek add yoztube-dl support

File size: 21.9 KB
Line 
1# Originally contributed by Sjoerd Mullender.
2# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>.
3
4"""Rational, infinite-precision, real numbers."""
5
6from __future__ import division
7from decimal import Decimal
8import math
9import numbers
10import operator
11import re
12
13__all__ = ['Fraction', 'gcd']
14
15Rational = numbers.Rational
16
17
18def gcd(a, b):
19    """Calculate the Greatest Common Divisor of a and b.
20
21    Unless b==0, the result will have the same sign as b (so that when
22    b is divided by it, the result comes out positive).
23    """
24    while b:
25        a, b = b, a%b
26    return a
27
28
29_RATIONAL_FORMAT = re.compile(r"""
30    \A\s*                      # optional whitespace at the start, then
31    (?P<sign>[-+]?)            # an optional sign, then
32    (?=\d|\.\d)                # lookahead for digit or .digit
33    (?P<num>\d*)               # numerator (possibly empty)
34    (?:                        # followed by
35       (?:/(?P<denom>\d+))?    # an optional denominator
36    |                          # or
37       (?:\.(?P<decimal>\d*))? # an optional fractional part
38       (?:E(?P<exp>[-+]?\d+))? # and optional exponent
39    )
40    \s*\Z                      # and optional whitespace to finish
41""", re.VERBOSE | re.IGNORECASE)
42
43
44class Fraction(Rational):
45    """This class implements rational numbers.
46
47    In the two-argument form of the constructor, Fraction(8, 6) will
48    produce a rational number equivalent to 4/3. Both arguments must
49    be Rational. The numerator defaults to 0 and the denominator
50    defaults to 1 so that Fraction(3) == 3 and Fraction() == 0.
51
52    Fractions can also be constructed from:
53
54      - numeric strings similar to those accepted by the
55        float constructor (for example, '-2.3' or '1e10')
56
57      - strings of the form '123/456'
58
59      - float and Decimal instances
60
61      - other Rational instances (including integers)
62
63    """
64
65    __slots__ = ('_numerator', '_denominator')
66
67    # We're immutable, so use __new__ not __init__
68    def __new__(cls, numerator=0, denominator=None):
69        """Constructs a Fraction.
70
71        Takes a string like '3/2' or '1.5', another Rational instance, a
72        numerator/denominator pair, or a float.
73
74        Examples
75        --------
76
77        >>> Fraction(10, -8)
78        Fraction(-5, 4)
79        >>> Fraction(Fraction(1, 7), 5)
80        Fraction(1, 35)
81        >>> Fraction(Fraction(1, 7), Fraction(2, 3))
82        Fraction(3, 14)
83        >>> Fraction('314')
84        Fraction(314, 1)
85        >>> Fraction('-35/4')
86        Fraction(-35, 4)
87        >>> Fraction('3.1415') # conversion from numeric string
88        Fraction(6283, 2000)
89        >>> Fraction('-47e-2') # string may include a decimal exponent
90        Fraction(-47, 100)
91        >>> Fraction(1.47)  # direct construction from float (exact conversion)
92        Fraction(6620291452234629, 4503599627370496)
93        >>> Fraction(2.25)
94        Fraction(9, 4)
95        >>> Fraction(Decimal('1.47'))
96        Fraction(147, 100)
97
98        """
99        self = super(Fraction, cls).__new__(cls)
100
101        if denominator is None:
102            if isinstance(numerator, Rational):
103                self._numerator = numerator.numerator
104                self._denominator = numerator.denominator
105                return self
106
107            elif isinstance(numerator, float):
108                # Exact conversion from float
109                value = Fraction.from_float(numerator)
110                self._numerator = value._numerator
111                self._denominator = value._denominator
112                return self
113
114            elif isinstance(numerator, Decimal):
115                value = Fraction.from_decimal(numerator)
116                self._numerator = value._numerator
117                self._denominator = value._denominator
118                return self
119
120            elif isinstance(numerator, basestring):
121                # Handle construction from strings.
122                m = _RATIONAL_FORMAT.match(numerator)
123                if m is None:
124                    raise ValueError('Invalid literal for Fraction: %r' %
125                                     numerator)
126                numerator = int(m.group('num') or '0')
127                denom = m.group('denom')
128                if denom:
129                    denominator = int(denom)
130                else:
131                    denominator = 1
132                    decimal = m.group('decimal')
133                    if decimal:
134                        scale = 10**len(decimal)
135                        numerator = numerator * scale + int(decimal)
136                        denominator *= scale
137                    exp = m.group('exp')
138                    if exp:
139                        exp = int(exp)
140                        if exp >= 0:
141                            numerator *= 10**exp
142                        else:
143                            denominator *= 10**-exp
144                if m.group('sign') == '-':
145                    numerator = -numerator
146
147            else:
148                raise TypeError("argument should be a string "
149                                "or a Rational instance")
150
151        elif (isinstance(numerator, Rational) and
152            isinstance(denominator, Rational)):
153            numerator, denominator = (
154                numerator.numerator * denominator.denominator,
155                denominator.numerator * numerator.denominator
156                )
157        else:
158            raise TypeError("both arguments should be "
159                            "Rational instances")
160
161        if denominator == 0:
162            raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
163        g = gcd(numerator, denominator)
164        self._numerator = numerator // g
165        self._denominator = denominator // g
166        return self
167
168    @classmethod
169    def from_float(cls, f):
170        """Converts a finite float to a rational number, exactly.
171
172        Beware that Fraction.from_float(0.3) != Fraction(3, 10).
173
174        """
175        if isinstance(f, numbers.Integral):
176            return cls(f)
177        elif not isinstance(f, float):
178            raise TypeError("%s.from_float() only takes floats, not %r (%s)" %
179                            (cls.__name__, f, type(f).__name__))
180        if math.isnan(f) or math.isinf(f):
181            raise TypeError("Cannot convert %r to %s." % (f, cls.__name__))
182        return cls(*f.as_integer_ratio())
183
184    @classmethod
185    def from_decimal(cls, dec):
186        """Converts a finite Decimal instance to a rational number, exactly."""
187        from decimal import Decimal
188        if isinstance(dec, numbers.Integral):
189            dec = Decimal(int(dec))
190        elif not isinstance(dec, Decimal):
191            raise TypeError(
192                "%s.from_decimal() only takes Decimals, not %r (%s)" %
193                (cls.__name__, dec, type(dec).__name__))
194        if not dec.is_finite():
195            # Catches infinities and nans.
196            raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__))
197        sign, digits, exp = dec.as_tuple()
198        digits = int(''.join(map(str, digits)))
199        if sign:
200            digits = -digits
201        if exp >= 0:
202            return cls(digits * 10 ** exp)
203        else:
204            return cls(digits, 10 ** -exp)
205
206    def limit_denominator(self, max_denominator=1000000):
207        """Closest Fraction to self with denominator at most max_denominator.
208
209        >>> Fraction('3.141592653589793').limit_denominator(10)
210        Fraction(22, 7)
211        >>> Fraction('3.141592653589793').limit_denominator(100)
212        Fraction(311, 99)
213        >>> Fraction(4321, 8765).limit_denominator(10000)
214        Fraction(4321, 8765)
215
216        """
217        # Algorithm notes: For any real number x, define a *best upper
218        # approximation* to x to be a rational number p/q such that:
219        #
220        #   (1) p/q >= x, and
221        #   (2) if p/q > r/s >= x then s > q, for any rational r/s.
222        #
223        # Define *best lower approximation* similarly.  Then it can be
224        # proved that a rational number is a best upper or lower
225        # approximation to x if, and only if, it is a convergent or
226        # semiconvergent of the (unique shortest) continued fraction
227        # associated to x.
228        #
229        # To find a best rational approximation with denominator <= M,
230        # we find the best upper and lower approximations with
231        # denominator <= M and take whichever of these is closer to x.
232        # In the event of a tie, the bound with smaller denominator is
233        # chosen.  If both denominators are equal (which can happen
234        # only when max_denominator == 1 and self is midway between
235        # two integers) the lower bound---i.e., the floor of self, is
236        # taken.
237
238        if max_denominator < 1:
239            raise ValueError("max_denominator should be at least 1")
240        if self._denominator <= max_denominator:
241            return Fraction(self)
242
243        p0, q0, p1, q1 = 0, 1, 1, 0
244        n, d = self._numerator, self._denominator
245        while True:
246            a = n//d
247            q2 = q0+a*q1
248            if q2 > max_denominator:
249                break
250            p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
251            n, d = d, n-a*d
252
253        k = (max_denominator-q0)//q1
254        bound1 = Fraction(p0+k*p1, q0+k*q1)
255        bound2 = Fraction(p1, q1)
256        if abs(bound2 - self) <= abs(bound1-self):
257            return bound2
258        else:
259            return bound1
260
261    @property
262    def numerator(a):
263        return a._numerator
264
265    @property
266    def denominator(a):
267        return a._denominator
268
269    def __repr__(self):
270        """repr(self)"""
271        return ('Fraction(%s, %s)' % (self._numerator, self._denominator))
272
273    def __str__(self):
274        """str(self)"""
275        if self._denominator == 1:
276            return str(self._numerator)
277        else:
278            return '%s/%s' % (self._numerator, self._denominator)
279
280    def _operator_fallbacks(monomorphic_operator, fallback_operator):
281        """Generates forward and reverse operators given a purely-rational
282        operator and a function from the operator module.
283
284        Use this like:
285        __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
286
287        In general, we want to implement the arithmetic operations so
288        that mixed-mode operations either call an implementation whose
289        author knew about the types of both arguments, or convert both
290        to the nearest built in type and do the operation there. In
291        Fraction, that means that we define __add__ and __radd__ as:
292
293            def __add__(self, other):
294                # Both types have numerators/denominator attributes,
295                # so do the operation directly
296                if isinstance(other, (int, long, Fraction)):
297                    return Fraction(self.numerator * other.denominator +
298                                    other.numerator * self.denominator,
299                                    self.denominator * other.denominator)
300                # float and complex don't have those operations, but we
301                # know about those types, so special case them.
302                elif isinstance(other, float):
303                    return float(self) + other
304                elif isinstance(other, complex):
305                    return complex(self) + other
306                # Let the other type take over.
307                return NotImplemented
308
309            def __radd__(self, other):
310                # radd handles more types than add because there's
311                # nothing left to fall back to.
312                if isinstance(other, Rational):
313                    return Fraction(self.numerator * other.denominator +
314                                    other.numerator * self.denominator,
315                                    self.denominator * other.denominator)
316                elif isinstance(other, Real):
317                    return float(other) + float(self)
318                elif isinstance(other, Complex):
319                    return complex(other) + complex(self)
320                return NotImplemented
321
322
323        There are 5 different cases for a mixed-type addition on
324        Fraction. I'll refer to all of the above code that doesn't
325        refer to Fraction, float, or complex as "boilerplate". 'r'
326        will be an instance of Fraction, which is a subtype of
327        Rational (r : Fraction <: Rational), and b : B <:
328        Complex. The first three involve 'r + b':
329
330            1. If B <: Fraction, int, float, or complex, we handle
331               that specially, and all is well.
332            2. If Fraction falls back to the boilerplate code, and it
333               were to return a value from __add__, we'd miss the
334               possibility that B defines a more intelligent __radd__,
335               so the boilerplate should return NotImplemented from
336               __add__. In particular, we don't handle Rational
337               here, even though we could get an exact answer, in case
338               the other type wants to do something special.
339            3. If B <: Fraction, Python tries B.__radd__ before
340               Fraction.__add__. This is ok, because it was
341               implemented with knowledge of Fraction, so it can
342               handle those instances before delegating to Real or
343               Complex.
344
345        The next two situations describe 'b + r'. We assume that b
346        didn't know about Fraction in its implementation, and that it
347        uses similar boilerplate code:
348
349            4. If B <: Rational, then __radd_ converts both to the
350               builtin rational type (hey look, that's us) and
351               proceeds.
352            5. Otherwise, __radd__ tries to find the nearest common
353               base ABC, and fall back to its builtin type. Since this
354               class doesn't subclass a concrete type, there's no
355               implementation to fall back to, so we need to try as
356               hard as possible to return an actual value, or the user
357               will get a TypeError.
358
359        """
360        def forward(a, b):
361            if isinstance(b, (int, long, Fraction)):
362                return monomorphic_operator(a, b)
363            elif isinstance(b, float):
364                return fallback_operator(float(a), b)
365            elif isinstance(b, complex):
366                return fallback_operator(complex(a), b)
367            else:
368                return NotImplemented
369        forward.__name__ = '__' + fallback_operator.__name__ + '__'
370        forward.__doc__ = monomorphic_operator.__doc__
371
372        def reverse(b, a):
373            if isinstance(a, Rational):
374                # Includes ints.
375                return monomorphic_operator(a, b)
376            elif isinstance(a, numbers.Real):
377                return fallback_operator(float(a), float(b))
378            elif isinstance(a, numbers.Complex):
379                return fallback_operator(complex(a), complex(b))
380            else:
381                return NotImplemented
382        reverse.__name__ = '__r' + fallback_operator.__name__ + '__'
383        reverse.__doc__ = monomorphic_operator.__doc__
384
385        return forward, reverse
386
387    def _add(a, b):
388        """a + b"""
389        return Fraction(a.numerator * b.denominator +
390                        b.numerator * a.denominator,
391                        a.denominator * b.denominator)
392
393    __add__, __radd__ = _operator_fallbacks(_add, operator.add)
394
395    def _sub(a, b):
396        """a - b"""
397        return Fraction(a.numerator * b.denominator -
398                        b.numerator * a.denominator,
399                        a.denominator * b.denominator)
400
401    __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
402
403    def _mul(a, b):
404        """a * b"""
405        return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
406
407    __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)
408
409    def _div(a, b):
410        """a / b"""
411        return Fraction(a.numerator * b.denominator,
412                        a.denominator * b.numerator)
413
414    __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)
415    __div__, __rdiv__ = _operator_fallbacks(_div, operator.div)
416
417    def __floordiv__(a, b):
418        """a // b"""
419        # Will be math.floor(a / b) in 3.0.
420        div = a / b
421        if isinstance(div, Rational):
422            # trunc(math.floor(div)) doesn't work if the rational is
423            # more precise than a float because the intermediate
424            # rounding may cross an integer boundary.
425            return div.numerator // div.denominator
426        else:
427            return math.floor(div)
428
429    def __rfloordiv__(b, a):
430        """a // b"""
431        # Will be math.floor(a / b) in 3.0.
432        div = a / b
433        if isinstance(div, Rational):
434            # trunc(math.floor(div)) doesn't work if the rational is
435            # more precise than a float because the intermediate
436            # rounding may cross an integer boundary.
437            return div.numerator // div.denominator
438        else:
439            return math.floor(div)
440
441    def __mod__(a, b):
442        """a % b"""
443        div = a // b
444        return a - b * div
445
446    def __rmod__(b, a):
447        """a % b"""
448        div = a // b
449        return a - b * div
450
451    def __pow__(a, b):
452        """a ** b
453
454        If b is not an integer, the result will be a float or complex
455        since roots are generally irrational. If b is an integer, the
456        result will be rational.
457
458        """
459        if isinstance(b, Rational):
460            if b.denominator == 1:
461                power = b.numerator
462                if power >= 0:
463                    return Fraction(a._numerator ** power,
464                                    a._denominator ** power)
465                else:
466                    return Fraction(a._denominator ** -power,
467                                    a._numerator ** -power)
468            else:
469                # A fractional power will generally produce an
470                # irrational number.
471                return float(a) ** float(b)
472        else:
473            return float(a) ** b
474
475    def __rpow__(b, a):
476        """a ** b"""
477        if b._denominator == 1 and b._numerator >= 0:
478            # If a is an int, keep it that way if possible.
479            return a ** b._numerator
480
481        if isinstance(a, Rational):
482            return Fraction(a.numerator, a.denominator) ** b
483
484        if b._denominator == 1:
485            return a ** b._numerator
486
487        return a ** float(b)
488
489    def __pos__(a):
490        """+a: Coerces a subclass instance to Fraction"""
491        return Fraction(a._numerator, a._denominator)
492
493    def __neg__(a):
494        """-a"""
495        return Fraction(-a._numerator, a._denominator)
496
497    def __abs__(a):
498        """abs(a)"""
499        return Fraction(abs(a._numerator), a._denominator)
500
501    def __trunc__(a):
502        """trunc(a)"""
503        if a._numerator < 0:
504            return -(-a._numerator // a._denominator)
505        else:
506            return a._numerator // a._denominator
507
508    def __hash__(self):
509        """hash(self)
510
511        Tricky because values that are exactly representable as a
512        float must have the same hash as that float.
513
514        """
515        # XXX since this method is expensive, consider caching the result
516        if self._denominator == 1:
517            # Get integers right.
518            return hash(self._numerator)
519        # Expensive check, but definitely correct.
520        if self == float(self):
521            return hash(float(self))
522        else:
523            # Use tuple's hash to avoid a high collision rate on
524            # simple fractions.
525            return hash((self._numerator, self._denominator))
526
527    def __eq__(a, b):
528        """a == b"""
529        if isinstance(b, Rational):
530            return (a._numerator == b.numerator and
531                    a._denominator == b.denominator)
532        if isinstance(b, numbers.Complex) and b.imag == 0:
533            b = b.real
534        if isinstance(b, float):
535            if math.isnan(b) or math.isinf(b):
536                # comparisons with an infinity or nan should behave in
537                # the same way for any finite a, so treat a as zero.
538                return 0.0 == b
539            else:
540                return a == a.from_float(b)
541        else:
542            # Since a doesn't know how to compare with b, let's give b
543            # a chance to compare itself with a.
544            return NotImplemented
545
546    def _richcmp(self, other, op):
547        """Helper for comparison operators, for internal use only.
548
549        Implement comparison between a Rational instance `self`, and
550        either another Rational instance or a float `other`.  If
551        `other` is not a Rational instance or a float, return
552        NotImplemented. `op` should be one of the six standard
553        comparison operators.
554
555        """
556        # convert other to a Rational instance where reasonable.
557        if isinstance(other, Rational):
558            return op(self._numerator * other.denominator,
559                      self._denominator * other.numerator)
560        # comparisons with complex should raise a TypeError, for consistency
561        # with int<->complex, float<->complex, and complex<->complex comparisons.
562        if isinstance(other, complex):
563            raise TypeError("no ordering relation is defined for complex numbers")
564        if isinstance(other, float):
565            if math.isnan(other) or math.isinf(other):
566                return op(0.0, other)
567            else:
568                return op(self, self.from_float(other))
569        else:
570            return NotImplemented
571
572    def __lt__(a, b):
573        """a < b"""
574        return a._richcmp(b, operator.lt)
575
576    def __gt__(a, b):
577        """a > b"""
578        return a._richcmp(b, operator.gt)
579
580    def __le__(a, b):
581        """a <= b"""
582        return a._richcmp(b, operator.le)
583
584    def __ge__(a, b):
585        """a >= b"""
586        return a._richcmp(b, operator.ge)
587
588    def __nonzero__(a):
589        """a != 0"""
590        return a._numerator != 0
591
592    # support for pickling, copy, and deepcopy
593
594    def __reduce__(self):
595        return (self.__class__, (str(self),))
596
597    def __copy__(self):
598        if type(self) == Fraction:
599            return self     # I'm immutable; therefore I am my own clone
600        return self.__class__(self._numerator, self._denominator)
601
602    def __deepcopy__(self, memo):
603        if type(self) == Fraction:
604            return self     # My components are also immutable
605        return self.__class__(self._numerator, self._denominator)
Note: See TracBrowser for help on using the repository browser.