# Class Decimal, version 0.0.8
# Written by Aahz (aahz@pobox.com)
# Currently under BSD-style license (copyright 2001)

'''
This is a first stab at a decimal arithmetic module based on the decimal
arithmetic ANSI standard X3.274-1996.  It should work with Python 1.5.2
and later.

Most of the information used to create this module was helpfully provided 
by Mike Cowlishaw's work at
http://www2.hursley.ibm.com/decimal/
The rest comes from Tim Peters's FixedPoint.py, particularly the string
conversion routine and general Pythonic practices.

In the current form of Decimal(), precision is finite but unbounded, with
the exception of division.  You must use the round() method to perform
any trimming.  Division and eng() and sci() conversion routines are not
yet written.

Here are some simple test cases that show how to use Decimal.  There
will be a separate full-blown test harness once Mike Cowlishaw releases
the language-independent test cases:

>>> Decimal(0)
Decimal( (0, (0,), 0L) )
>>> Decimal("1")
Decimal( (0, (1,), 0L) )
>>> Decimal("-.0123") 
Decimal( (1, (1, 2, 3), -4L) )
>>> Decimal("1.20")
Decimal( (0, (1, 2, 0), -2L) )
>>> str(Decimal(123456789012345678901234567890L))
'123456789012345678901234567890'
>>> str(Decimal("123.45e12345678901234567890"))
'1.2345e12345678901234567892'
>>> str(Decimal("1.33") + Decimal("1.27"))
'2.60'
>>> str(Decimal("12.34") + Decimal("3.87") - Decimal("18.41"))
'-2.20'
>>> str(Decimal("43e9") + Decimal("82e-9"))
'43000000000.000000082'
>>> str(Decimal("24.32347e27") * Decimal("-22.34500e-30"))
'-0.5435079371500'
>>> str(Decimal("34.89") * Decimal("1e3"))
'3.489e4'
>>> str(Decimal("-3.125").round(3))
'-3.13'
>>> str(Decimal("4.23").round(5))
'4.2300'
>>> Decimal("123.345346213462346234512342456813451235e20")
Decimal( (0, (1, 2, 3, 3, 4, 5, 3, 4, 6, 2, 1, 3, 4, 6, 2, 3, 4, 6, 2, 3, 4, 5, 1, 2, 3, 4, 2, 4, 5, 6, 8, 1, 3, 4, 5, 1, 2, 3, 5), -16L) )
>>> Decimal(str(Decimal("123.345346213462346234512342456813451235e20")))
Decimal( (0, (1, 2, 3, 3, 4, 5, 3, 4, 6, 2, 1, 3, 4, 6, 2, 3, 4, 6, 2, 3, 4, 5, 1, 2, 3, 4, 2, 4, 5, 6, 8, 1, 3, 4, 5, 1, 2, 3, 5), -16L) )
>>> str(Decimal(123.45))
'123.4500000000000028421709430404007434844970703125'
>>> Decimal("foo")
Traceback (most recent call last):
ValueError: Can't parse as number: 'foo'
>>> str(Decimal("123.45e12345678901234567890") + Decimal("123.45e-12345678901234567890"))
Traceback (most recent call last):
OverflowError: long int too long to convert

'''


# 0.0.8     2001.5.24   Fixed multiplication with trailing zeroes
# 0.0.7     2001.5.23   Fixed string conversion to follow spec
# 0.0.6     2001.5.20   Tim Peters's _floatToString()
# 0.0.5     2001.5.20   Now with multiplication, round(), and conversions
# 0.0.0     2001.5.18   First public release with just addtion/subtraction

# To-do list:
#
# Division
# pow()
# sci() and eng() methods
# better error handling
# additional rounding methods
# test cases when Cowlishaw makes them available



import string



DEFAULT_PRECISION = 9

ROUND_DOWN = 0
ROUND_UP = 1
ROUND_EVEN = 2

DEFAULT_ROUNDING = ROUND_UP



class Decimal:
    def __init__(self, value, context=None):
        # XXX We don't actually use this for anything yet
        self._context = context

        # tuple conversion for/from repr()
        if isinstance(value, type((None,)) ):
            self._sign = value[0]
            self._int = tuple(value[1])     # Allow list input
            self._exp = long(value[2])
            return

        # Turn an intermediate value back to Decimal()
        if isinstance(value, _WorkRep):
            if value.sign == 1:
                self._sign = 0
            else:
                self._sign = 1
            self._int = tuple(value.int)
            self._exp = long(value.exp)
            return

        # Make a copy
        if isinstance(value, Decimal):
            self._sign = value._sign
            self._int = value._int
            self._exp = value._exp

        if isinstance(value, type("1")):
            self._convertString(value)
            return

        if isinstance(value, type(1)):
            self._convertString(repr(value))
            return

        if isinstance(value, type(1L)):
            # chop the trailing 'L'
            value = repr(value)[:-1]
            self._convertString(value)
            return

        if isinstance(value, type(1.0)):
            self._convertString(_floatToString(value))
            return

        raise TypeError("Can't convert " + `value`)

    def _convertString(self, value):
        self._sign, self._int, self._exp = _string2exact(value)

    def __cmp__(self, other):
        raise

    # Hashes whole numbers to their long equivalent
    def __hash__(self):
        if self._exp >= 0:
            return hash(long(self))
        else:
            return hash( (self._sign, self._int, self._exp) )

    # Does not preserve context
    def __repr__(self):
        return "Decimal( (" + `self._sign` + ", " + `self._int` + ", " + `self._exp` + ") )"

    # String is guaranteed to have perfect accuracy
    def __str__(self):
        tmp = []
        for digit in self._int:
            tmp.append(str(digit))
        numdigits = len(self._int)
        adjexp = self._exp + (numdigits - 1)
        if self._exp == 0:
            pass
        elif self._exp < 0 and adjexp >= 0:
            tmp.insert(adjexp + 1, '.')
        elif self._exp < 0 and adjexp >= -6:
            tmp[0:0] = ['0'] * int(-adjexp - 1)
            tmp.insert(0, '0.')
        else:
            if numdigits > 1:
                tmp.insert(1, '.')
            tmp.append('e')
            # Use repr() instead of str() because of 1.5.2
            tmp.append(repr(adjexp)[:-1])
        if self._sign:
            tmp.insert(0, '-')
        return string.join(tmp, '')

    def __neg__(self):
        if self._sign:
            sign = 0
        else:
            sign = 1
        return Decimal( (sign, self._int, self._exp), self._context)

    def __abs__(self):
        if self._sign:
            return -self
        else:
            return self

    def __add__(self, other):
        if self._int == (0,):
            return other
        if other._int == (0,):
            return self

        op1 = _WorkRep(self)
        op2 = _WorkRep(other)
        op1, op2 = _normalize(op1, op2)
        result = _WorkRep()
        if op1.sign != op2.sign:
            diff = cmp(abs(op1), abs(op2))
            if diff == 0:
                return Decimal(0)
            if diff < 0:
                op1, op2 = op2, op1
            if op1.sign == -1:
                result.sign = -1
                op1.sign, op2.sign = op2.sign, op1.sign
            else:
                result.sign = 1
        elif op1.sign == -1:
            result.sign = -1
            op1.sign, op2.sign = (1, 1)
        else:
            result.sign = 1

        carry, loan = (0, 0)
        op1.int.reverse()
        op2.int.reverse()
        for i in range(len(op1.int)):
            tmp = op1.int[i] + (op2.sign * op2.int[i]) + carry - loan
            carry, loan = (0, 0)
            if tmp > 9:
                carry = 1
                tmp = tmp - 10
            if tmp < 0:
                loan = 1
                tmp = tmp + 10
            result.int.append(tmp)
        if carry:
            result.int.append(1)
        if loan:
            raise "What are we doing here?"
        while result.int[-1] == 0:
            result.int.pop()
        result.int.reverse()
        result.exp = op1.exp
        return Decimal(result)

    __radd__ = __add__

    def __sub__(self, other):
        if not isinstance(other, Decimal):
            other = Decimal(other, self._context)
        return self.__add__(-other)

    def __rsub__(self, other):
            return (-self) + other

    def __mul__(self, other):
        # Special case for multiplying by zero
        if self._int == (0,) or other._int == (0,):
            return Decimal(0)

        if self._sign == other._sign:
            resultsign = 0
        else:
            resultsign = 1
        resultexp = self._exp + other._exp

        # Special case for multiplying by power of 10
        if self._int == (1,):
            return Decimal( (resultsign, other._int, resultexp) )
        if other._int == (1,):
            return Decimal( (resultsign, self._int, resultexp) )

        op1 = list(self._int)
        op2 = list(other._int)
        op1.reverse()
        op2.reverse()
        # Minimize Decimal additions
        if len(op2) > len(op1):
            op1, op2 = op2, op1

        accumulator = Decimal(0)
        shift = 0
        for i in range(len(op2)):
            # preserve precision
            if op2[i] == 0:
                shift = shift + 1
                continue
            mult = op2[i]
            tmp = []
            carry = 0
            for j in range(len(op1)):
                carry, digit = divmod( ((mult * op1[j]) + carry), 10 )
                tmp.append(digit)
            if carry:
                tmp.append(carry)
            tmp.reverse()
            tmp.extend([0] * shift)
            accumulator = accumulator + Decimal( (0, tmp, i-shift) )

        return Decimal( (resultsign, accumulator._int, resultexp+accumulator._exp) )

    __rmul__ = __mul__

    def __div__(self, other):
        raise

    def __rdiv__(self, other):
        raise

    def __divmod__(self, other):
        raise

    def __rdivmod__(self, other):
        raise

    def __mod__(self, other):
        raise

    def __rmod__(self, other):
        raise

    def __float__(self):
        return float(str(self))

    def __long__(self):
        raise

    def __int__(self):
        return int(self.__long__())

    def round(self, prec=None):
        if prec is None:
            if self._context is None or self._context.prec is None:
                prec = DEFAULT_PRECISION
            else:
                prec = self._context.prec
        numdigits = len(self._int)
        if prec == numdigits:
            return self

        # See if we need to extend precision
        expdiff = prec - numdigits
        if expdiff > 0:
            tmp = list(self._int)
            tmp.extend([0] * expdiff)
            return Decimal( (self._sign, tmp, self._exp - expdiff) )

        # Okay, let's round
        tmp = Decimal( (self._sign, self._int[:prec], self._exp - expdiff) )
        if self._int[prec] >= 5:
            tmp = tmp + Decimal( (tmp._sign, (1,), tmp._exp) )
            if len(tmp._int) > prec:
                return Decimal( (tmp._sign, tmp._int[:-1], tmp._exp + 1) )
            else:
                return tmp
        else:
            return tmp

    def fixedPoint(self, digits):
        '''
        Convenience function to allow rounding to a specified number of
        places after the decimal point.  Negative numbers indicate
        rounding before the decimal point.

        >>> str(Decimal("1234.34567").fixedPoint(2))
        '1234.35'
        '''
        raise

    def eng():
        raise

    def pow():
        raise



class _WorkRep:
    def __init__(self, value=None):
        if value is None:
            self.sign = None
            self.int = []
            self.exp = None
        if isinstance(value, Decimal):
            if value._sign:
                self.sign = -1
            else:
                self.sign = 1
            self.int = list(value._int)
            self.exp = value._exp
        if isinstance(value, type((None,)) ):
            self.sign = value[0]
            self.int = value[1]
            self.exp = value[2]

    def __repr__(self):
        return "(" + `self.sign` + ", " + `self.int` + ", " + `self.exp` + ")"

    __str__ = __repr__

    def __neg__(self):
        if self.sign:
            return _WorkRep( (0, self.int, self.exp) )
        else:
            return _WorkRep( (1, self.int, self.exp) )

    def __abs__(self):
        if self.sign:
            return -self
        else:
            return self

    def __cmp__(self, other):
        if self.exp != other.exp:
            raise ValueError("Operands not normalized: " + `self` + ", " + `other`)
        if self.sign != other.sign:
            if self.sign:
                return -1
            else:
                return 1
        if self.sign:
            direction = -1
        else:
            direction = 1
        int1 = self.int
        int2 = other.int
        if len(int1) > len(int2):
            return direction * 1
        if len(int1) < len(int2):
            return direction * -1
        for i in range(len(int1)):
            if int1[i] > int2[i]:
                return direction * 1
            if int1[i] < int2[i]:
                return direction * -1
        return 0



def _normalize(op1, op2):
    # Yes, the exponent is a long, but the difference between exponents
    # must be an int
    numdigits = int(op1.exp - op2.exp)
    if numdigits < 0:
        numdigits = -numdigits
        tmp = op2
    else:
        tmp = op1
    tmp.int.extend([0] * numdigits)
    tmp.exp = tmp.exp - numdigits
    numdigits = len(op1.int) - len(op2.int)
    if numdigits < 0:
        numdigits = -numdigits
        tmp = op1
    else:
        tmp = op2
    tmp.int[0:0] = [0] * numdigits
    return op1, op2



# Code ripped more-or-less directly from FixedPoint.py
# _floatToString modified by Tim Peters to give exact results

# crud for parsing strings
import re

# There's an optional sign at the start, and an optional exponent
# at the end.  The exponent has an optional sign and at least one
# digit.  In between, must have either at least one digit followed
# by an optional fraction, or a decimal point followed by at least
# one digit.  Yuck.

_parser = re.compile(r"""
    \s*
    (?P<sign>[-+])?
    (
        (?P<int>\d+) (\. (?P<frac>\d*))?
    |
        \. (?P<onlyfrac>\d+)
    )
    ([eE](?P<exp>[-+]? \d+))?
    \s* $
""", re.VERBOSE).match

del re

# return n, p s.t. float string value == n * 10**p exactly

def _string2exact(s):
    m = _parser(s)
    if m is None:
        raise ValueError("Can't parse as number: " + `s`)

    exp = m.group('exp')
    if exp is None:
        exp = 0L
    else:
        exp = long(exp)

    intpart = m.group('int')
    if intpart is None:
        intpart = ""
        fracpart = m.group('onlyfrac')
    else:
        fracpart = m.group('frac')
        if fracpart is None:
            fracpart = ""

    nfrac = len(fracpart)
    exp = exp - nfrac

    mantissa = intpart + fracpart
    tmp = []
    for digit in mantissa:
        tmp.append(int(digit))
    while tmp and tmp[0] == 0:
        del tmp[0]
    # It's a zero
    if not tmp:
        return (0, (0,), 0L)
    mantissa = tuple(tmp)

    if m.group('sign') == "-":
        sign = 1
    else:
        sign = 0

    return (sign, mantissa, exp)



def _floatToString(x):
    """Return float x as exact decimal string.

    The string is of the form:
        "-", if and only if x is < 0.
        One or more decimal digits.  The last digit is not 0 unless x is 0.
        "e"
        The exponent, a (possibly signed) integer
    """

    import math
    # XXX ignoring infinities and NaNs for now.

    if x == 0:
        return "0e0"

    sign = ""
    if x < 0:
        sign = "-"
        x = -x

    f, e = math.frexp(x)
    assert 0.5 <= f < 1.0
    # x = f * 2**e exactly

    # Suck up CHUNK bits at a time; 28 is enough so that we suck
    # up all bits in 2 iterations for all known binary double-
    # precision formats, and small enough to fit in an int.
    CHUNK = 28
    top = 0L
    # invariant: x = (top + f) * 2**e exactly
    while f:
        f = math.ldexp(f, CHUNK)
        digit = int(f)
        assert digit >> CHUNK == 0
        top = (top << CHUNK) | digit
        f = f - digit
        assert 0.0 <= f < 1.0
        e = e - CHUNK
    assert top > 0

    # Now x = top * 2**e exactly.  Get rid of trailing 0 bits if e < 0
    # (purely to increase efficiency a little later -- this loop can
    # be removed without changing the result).
    while e < 0 and top & 1 == 0:
        top = top >> 1
        e = e + 1

    # Transform this into an equal value top' * 10**e'.
    if e > 0:
        top = top << e
        e = 0
    elif e < 0:
        # Exact is top/2**-e.  Multiply top and bottom by 5**-e to
        # get top*5**-e/10**-e = top*5**-e * 10**e
        top = top * 5L**-e

    # Nuke trailing (decimal) zeroes.
    while 1:
        assert top > 0
        newtop, rem = divmod(top, 10L)
        if rem:
            break
        top = newtop
        e = e + 1

    return "%s%se%d" % (sign, repr(top)[:-1], e)




def _test():
    import doctest, Decimal
    return doctest.testmod(Decimal)



if __name__ == '__main__':
    _test()