from basic import Basic, S
from operations import AssocOp
from cache import cacheit
from logic import fuzzy_not
from numbers import Integer, Rational
from symbol import Symbol, Wild
from sympy.utilities.iterables import make_list

# internal marker to indicate:
#   "there are still non-commutative objects -- don't forget to process them"
class NC_Marker:
    is_Order    = False
    is_Mul      = False
    is_Number   = False
    is_Poly     = False

    is_commutative = False


class Mul(AssocOp):

    __slots__ = []

    is_Mul = True

    @classmethod
    def flatten(cls, seq):

        # apply associativity, separate commutative part of seq
        c_part = []         # out: commutative factors
        nc_part = []        # out: non-commutative factors

        nc_seq = []

        coeff = S.One       # standalone term
                            # e.g. 3 * ...

        c_powers = []       # (base,exp)      n
                            # e.g. (x,n) for x

        num_exp = []        # (num-base, exp)           y
                            # e.g.  (3, y)  for  ... * 3  * ...

        order_symbols = None



        # --- PART 1 ---
        #
        # "collect powers and coeff":
        #
        # o coeff
        # o c_powers
        # o num_exp
        #
        # NOTE: this is optimized for all-objects-are-commutative case

        for o in seq:
            # O(x)
            if o.is_Order:
                o, order_symbols = o.as_expr_symbols(order_symbols)

            # Mul([...])
            if o.is_Mul:
                if o.is_commutative:
                    seq.extend(o.args)    # XXX zerocopy?

                else:
                    # NCMul can have commutative parts as well
                    for q in o.args:
                        if q.is_commutative:
                            seq.append(q)
                        else:
                            nc_seq.append(q)

                    # append non-commutative marker, so we don't forget to
                    # process scheduled non-commutative objects
                    seq.append(NC_Marker)

                continue

            # 3
            elif o.is_Number:
                coeff *= o
                continue


            elif o.is_commutative:
                #      e
                # o = b
                b, e = o.as_base_exp()

                #  y
                # 3
                if o.is_Pow and b.is_Number:
                    # get all the factors with numeric base so they can be
                    # combined below
                    num_exp.append((b,e))
                    continue


                #         n          n          n
                # (-3 + y)   ->  (-1)  * (3 - y)
                if not Basic.keep_sign and b.is_Add and e.is_Number:
                    #found factor (x+y)**number; split off initial coefficient
                    c, t = b.as_coeff_terms()
                    #last time I checked, Add.as_coeff_terms returns One or NegativeOne
                    #but this might change
                    if c.is_negative and not e.is_integer:
                        # extracting root from negative number: ignore sign
                        if c is not S.NegativeOne:
                            # make c positive (probably never occurs)
                            coeff *= (-c) ** e
                            assert len(t)==1,`t`
                            b = -t[0]
                        #else: ignoring sign from NegativeOne: nothing to do!
                    elif c is not S.One:
                        coeff *= c ** e
                        assert len(t)==1,`t`
                        b = t[0]
                    #else: c is One, so pass

                c_powers.append((b,e))


            # NON-COMMUTATIVE
            # TODO: Make non-commutative exponents not combine automatically
            else:
                if o is not NC_Marker:
                    nc_seq.append(o)

                # process nc_seq (if any)
                while nc_seq:
                    o = nc_seq.pop(0)
                    if not nc_part:
                        nc_part.append(o)
                        continue

                    #                             b    c       b+c
                    # try to combine last terms: a  * a   ->  a
                    o1 = nc_part.pop()
                    b1,e1 = o1.as_base_exp()
                    b2,e2 = o.as_base_exp()
                    if b1==b2:
                        o12 = b1 ** (e1 + e2)

                        # now o12 could be a commutative object
                        if o12.is_commutative:
                            seq.append(o12)
                            continue

                        else:
                            nc_seq.insert(0, o12)

                    else:
                        nc_part.append(o1)
                        nc_part.append(o)
        # We do want a combined exponent if it would not be an Add, such as
        #  y    2y     3y
        # x  * x   -> x
        # We determine this if two exponents have the same term in as_coeff_terms
        #
        # Unfortunately, this isn't smart enough to consider combining into
        # exponents that might already be adds, so things like:
        #  z - y    y
        # x      * x  will be left alone.  This is because checking every possible
        # combination can slow things down.
        new_c_powers = []
        common_b = {} # b:e

        # First gather exponents of common bases
        for b, e in c_powers:
            co = e.as_coeff_terms()
            if b in common_b:
                if  co[1] in common_b[b]:
                    common_b[b][co[1]] += co[0]
                else:
                    common_b[b][co[1]] = co[0]
            else:
                common_b[b] = {co[1]:co[0]}

        for b,e, in common_b.items():
            for t, c in e.items():
                new_c_powers.append((b,c*Mul(*t)))
        c_powers = new_c_powers

        # And the same for numeric bases
        new_num_exp = []
        common_b = {} # b:e
        for b, e in num_exp:
            co = e.as_coeff_terms()
            if b in common_b:
                if  co[1] in common_b[b]:
                    common_b[b][co[1]] += co[0]
                else:
                    common_b[b][co[1]] = co[0]
            else:
                common_b[b] = {co[1]:co[0]}

        for b,e, in common_b.items():
            for t, c in e.items():
                new_num_exp.append((b,c*Mul(*t)))
        num_exp = new_num_exp


        # --- PART 2 ---
        #
        # o process collected powers  (x**0 -> 1; x**1 -> x; otherwise Pow)
        # o combine collected powers  (2**x * 3**x -> 6**x)
        #   with numeric base

        # ................................
        # now we have:
        # - coeff:
        # - c_powers:    (b, e)
        # - num_exp:     (2, e)

        #  0             1
        # x  -> 1       x  -> x
        for b, e in c_powers:
            if e is S.Zero:
                continue

            if e is S.One:
                if b.is_Number:
                    coeff *= b
                else:
                    c_part.append(b)
            elif e.is_Integer and b.is_Number:
                coeff *= b ** e
            else:
                c_part.append(Pow(b, e))

        #  x    x     x
        # 2  * 3  -> 6
        inv_exp_dict = {}   # exp:Mul(num-bases)     x    x
                            # e.g.  x:6  for  ... * 2  * 3  * ...
        for b,e in num_exp:
            if e in inv_exp_dict:
                inv_exp_dict[e] *= b
            else:
                inv_exp_dict[e] = b

        for e,b in inv_exp_dict.items():
            if e is S.Zero:
                continue

            if e is S.One:
                if b.is_Number:
                    coeff *= b
                else:
                    c_part.append(b)
            elif e.is_Integer and b.is_Number:
                coeff *= b ** e
            else:
                obj = b**e
                if obj.is_Number:
                    coeff *= obj
                else:
                    c_part.append(obj)


        # oo, -oo
        if (coeff is S.Infinity) or (coeff is S.NegativeInfinity):
            new_c_part = []
            for t in c_part:
                if t.is_positive:
                    continue
                if t.is_negative:
                    coeff = -coeff
                    continue
                new_c_part.append(t)
            c_part = new_c_part
            new_nc_part = []
            for t in nc_part:
                if t.is_positive:
                    continue
                if t.is_negative:
                    coeff = -coeff
                    continue
                new_nc_part.append(t)
            nc_part = new_nc_part

        # 0, nan
        elif (coeff is S.Zero) or (coeff is S.NaN):
            # we know for sure the result will be the same as coeff (0 or nan)
            return [coeff], [], order_symbols

        elif coeff.is_Real:
            if coeff == Real(0):
                c_part, nc_part = [coeff], []
            elif coeff == Real(1):
                # change it to One, so it doesn't get inserted to slot0
                coeff = S.One


        # order commutative part canonically
        c_part.sort(Basic.compare)

        # current code expects coeff to be always in slot-0
        if coeff is not S.One:
            c_part.insert(0, coeff)


        # we are done
        if len(c_part)==2 and c_part[0].is_Number and c_part[1].is_Add:
            # 2*(1+a) -> 2 + 2 * a
            coeff = c_part[0]
            c_part = [Add(*[coeff*f for f in c_part[1].args])]

        return c_part, nc_part, order_symbols


    def _eval_power(b, e):