from core import C
from singleton import S
from operations import AssocOp
from cache import cacheit
from numbers import ilcm, igcd

from collections import defaultdict

class Add(AssocOp):

    __slots__ = []

    is_Add = True

    #identity = S.Zero
    # cyclic import, so defined in numbers.py

    @classmethod
    def flatten(cls, seq):
        """
        Takes the sequence "seq" of nested Adds and returns a flatten list.

        Returns: (commutative_part, noncommutative_part, order_symbols)

        Applies associativity, all terms are commutable with respect to
        addition.

        NB: the removal of 0 is already handled by AssocOp.__new__

        See also
        ========

        sympy.core.mul.Mul.flatten

        """
        rv = None
        if len(seq) == 2:
            a, b = seq
            if b.is_Rational:
                a, b = b, a
            assert a
            if a.is_Rational:
                if b.is_Mul:
                    # if it's an unevaluated 2-arg, expand it
                    c, t = b.as_coeff_Mul()
                    if t.is_Add:
                        h, t = t.as_coeff_Add()
                        bargs = [c*ti for ti in Add.make_args(t)]
                        bargs.sort(key=hash)
                        ch = c*h
                        if ch:
                            bargs.insert(0, ch)
                        b = Add._from_args(bargs)
                if b.is_Add:
                    bargs = list(b.args)
                    if bargs[0].is_Number:
                        bargs[0] += a
                        if not bargs[0]:
                            bargs.pop(0)
                    else:
                        bargs.insert(0, a)
                    rv = bargs, [], None
                elif b.is_Mul:
                    rv = [a, b], [], None
            if rv:
                if all(s.is_commutative for s in rv[0]):
                    return rv
                return [], rv[0], None

        terms = {}      # term -> coeff
                        # e.g. x**2 -> 5   for ... + 5*x**2 + ...

        coeff = S.Zero  # standalone term (Number or zoo will always be in slot 0)
                        # e.g. 3 + ...
        order_factors = []

        for o in seq:

            # O(x)
            if o.is_Order:
                for o1 in order_factors:
                    if o1.contains(o):
                        o = None
                        break
                if o is None:
                    continue
                order_factors = [o]+[o1 for o1 in order_factors if not o.contains(o1)]
                continue

            # 3 or NaN
            elif o.is_Number:
                if o is S.NaN or coeff is S.ComplexInfinity and o.is_bounded is False:
                    # we know for sure the result will be nan
                    return [S.NaN], [], None
                if coeff.is_Number:
                    coeff += o
                    if coeff is S.NaN:
                        # we know for sure the result will be nan
                        return [S.NaN], [], None
                continue

            elif o is S.ComplexInfinity:
                if coeff.is_bounded is False:
                    # we know for sure the result will be nan
                    return [S.NaN], [], None
                coeff = S.ComplexInfinity
                continue

            # Add([...])
            elif o.is_Add:
                # NB: here we assume Add is always commutative
                seq.extend(o.args)  # TODO zerocopy?
                continue

            # Mul([...])
            elif o.is_Mul:
                c, s = o.as_coeff_Mul()

                # 3*...
                # unevaluated 2-arg Mul, but we always unfold it so
                # it can combine with other terms (just like is done
                # with the Pow below)
                if c.is_Number and s.is_Add:
                    seq.extend([c*a for a in s.args])
                    continue

            # check for unevaluated Pow, e.g. 2**3 or 2**(-1/2)
            elif o.is_Pow:
                b, e = o.as_base_exp()
                if b.is_Number and (e.is_Integer or (e.is_Rational and e.is_negative)):
                    seq.append(b**e)
                    continue
                c, s = S.One, o

            else:
                # everything else
                c = S.One
                s = o


            # now we have:
            # o = c*s, where
            #
            # c is a Number
            # s is an expression with number factor extracted

            # let's collect terms with the same s, so e.g.
            # 2*x**2 + 3*x**2  ->  5*x**2
            if s in terms:
                terms[s] += c
            else:
                terms[s] = c


        # now let's construct new args:
        # [2*x**2, x**3, 7*x**4, pi, ...]
        newseq = []
        noncommutative = False
        for s,c in terms.items():
            # 0*s
            if c is S.Zero:
                continue
            # 1*s
            elif c is S.One:
                newseq.append(s)
            # c*s
            else:
                if s.is_Mul:
                    # Mul, already keeps its arguments in perfect order.
                    # so we can simply put c in slot0 and go the fast way.
                    cs = s._new_rawargs(*((c,) + s.args))
                    newseq.append(cs)

                else:
                    # alternatively we have to call all Mul's machinery (slow)
                    newseq.append(Mul(c,s))

            noncommutative = noncommutative or not s.is_commutative

        # oo, -oo
        if coeff is S.Infinity:
            newseq = [f for f in newseq if not (f.is_nonnegative or f.is_real and
                                                (f.is_bounded or
                                                 f.is_finite or
                                                 f.is_infinitesimal))]
        elif coeff is S.NegativeInfinity:
            newseq = [f for f in newseq if not (f.is_nonpositive or f.is_real and
                                                (f.is_bounded or
                                                 f.is_finite or
                                                 f.is_infinitesimal))]
        if coeff is S.ComplexInfinity:
            # zoo might be
            #   unbounded_real + bounded_im
            #   bounded_real + unbounded_im
            #   unbounded_real + unbounded_im
            # addition of a bounded real or imaginary number won't be able to
            # change the zoo nature; if unbounded a NaN condition could result if
            # the unbounded symbol had sign opposite of the unbounded portion of zoo,
            # e.g. unbounded_real - unbounded_real
            newseq = [c for c in newseq if not (c.is_bounded and
                                                c.is_real is not None)]

        # process O(x)
        if order_factors:
            newseq2 = []
            for t in newseq:
                for o in order_factors:
                    # x + O(x) -> O(x)
                    if o.contains(t):
                        t = None
                        break
                # x + O(x**2) -> x + O(x**2)
                if t is not None:
                    newseq2.append(t)
            newseq = newseq2 + order_factors
            # 1 + O(1) -> O(1)
            for o in order_factors: