from sympy.core import Basic, S, Function, diff, Tuple
from sympy.core.relational import Equality, Relational
from sympy.core.symbol import Dummy
from sympy.functions.elementary.miscellaneous import Max, Min
from sympy.logic.boolalg import And, Boolean, Or
from sympy.utilities.misc import default_sort_key

class ExprCondPair(Tuple):
    """Represents an expression, condition pair."""

    true_sentinel = Dummy('True')

    def __new__(cls, expr, cond):
        if cond is True:
            cond = ExprCondPair.true_sentinel
        return Tuple.__new__(cls, expr, cond)

    @property
    def expr(self):
        """
        Returns the expression of this pair.
        """
        return self.args[0]

    @property
    def cond(self):
        """
        Returns the condition of this pair.
        """
        if self.args[1] == ExprCondPair.true_sentinel:
            return True
        return self.args[1]

    @property
    def free_symbols(self):
        """
        Return the free symbols of this pair.
        """
        # Overload Basic.free_symbols because self.args[1] may contain non-Basic
        result = self.expr.free_symbols
        if hasattr(self.cond, 'free_symbols'):
            result |= self.cond.free_symbols
        return result

    @property
    def is_commutative(self):
        return self.expr.is_commutative

    def __iter__(self):
        yield self.expr
        yield self.cond

class Piecewise(Function):
    """
    Represents a piecewise function.

    Usage:

      Piecewise( (expr,cond), (expr,cond), ... )
        - Each argument is a 2-tuple defining a expression and condition
        - The conds are evaluated in turn returning the first that is True.
          If any of the evaluated conds are not determined explicitly False,
          e.g. x < 1, the function is returned in symbolic form.
        - If the function is evaluated at a place where all conditions are False,
          a ValueError exception will be raised.
        - Pairs where the cond is explicitly False, will be removed.

    Examples
    ========

      >>> from sympy import Piecewise, log
      >>> from sympy.abc import x
      >>> f = x**2
      >>> g = log(x)
      >>> p = Piecewise( (0, x<-1), (f, x<=1), (g, True))
      >>> p.subs(x,1)
      1
      >>> p.subs(x,5)
      log(5)

    See Also
    ========

    piecewise_fold
    """

    nargs = None
    is_Piecewise = True

    def __new__(cls, *args, **options):
        # (Try to) sympify args first
        newargs = []
        for ec in args:
            pair = ExprCondPair(*ec)
            cond = pair.cond
            if cond is False:
                continue
            if not isinstance(cond, (bool, Relational, Boolean)):
                raise TypeError(
                    "Cond %s is of type %s, but must be a Relational," \
                    " Boolean, or a built-in bool." % (cond, type(cond)))
            newargs.append(pair)
            if cond is True:
                break

        if options.pop('evaluate', True):
            r = cls.eval(*newargs)
        else:
            r = None

        if r is None:
            return Basic.__new__(cls, *newargs, **options)
        else:
            return r

    @classmethod
    def eval(cls, *args):
        # Check for situations where we can evaluate the Piecewise object.
        # 1) Hit an unevaluable cond (e.g. x<1) -> keep object
        # 2) Hit a true condition -> return that expr
        # 3) Remove false conditions, if no conditions left -> raise ValueError
        all_conds_evaled = True    # Do all conds eval to a bool?
        piecewise_again = False    # Should we pass args to Piecewise again?
        non_false_ecpairs = []
        or1 = Or(*[cond for (_, cond) in args if cond is not True])
        for expr, cond in args:
            # Check here if expr is a Piecewise and collapse if one of
            # the conds in expr matches cond. This allows the collapsing
            # of Piecewise((Piecewise(x,x<0),x<0)) to Piecewise((x,x<0)).
            # This is important when using piecewise_fold to simplify
            # multiple Piecewise instances having the same conds.
            # Eventually, this code should be able to collapse Piecewise's
            # having different intervals, but this will probably require
            # using the new assumptions.
            if isinstance(expr, Piecewise):
                or2 = Or(*[c for (_, c) in expr.args if c is not True])
                for e, c in expr.args:
                    # Don't collapse if cond is "True" as this leads to
                    # incorrect simplifications with nested Piecewises.
                    if c == cond and (or1 == or2 or cond is not True):
                        expr = e
                        piecewise_again = True
            cond_eval = cls.__eval_cond(cond)
            if cond_eval is None:
                all_conds_evaled = False
            elif cond_eval:
                if all_conds_evaled:
                    return expr
            if len(non_false_ecpairs) != 0 and non_false_ecpairs[-1].expr == expr:
                non_false_ecpairs[-1] = ExprCondPair(expr, Or(cond, non_false_ecpairs[-1].cond))
            else:
                non_false_ecpairs.append( ExprCondPair(expr, cond) )
        if len(non_false_ecpairs) != len(args) or piecewise_again:
            return Piecewise(*non_false_ecpairs)

        return None

    def doit(self, **hints):
        """
        Evaluate this piecewise function.
        """
        newargs = []
        for e, c in self.args:
            if hints.get('deep', True):
                if isinstance(e, Basic):
                    e = e.doit(**hints)
                if isinstance(c, Basic):
                    c = c.doit(**hints)
            newargs.append((e, c))
        return Piecewise(*newargs)

    def _eval_as_leading_term(self, x):
        for e, c in self.args:
            if c is True or c.subs(x, 0) is True:
                return e.as_leading_term(x)

    def _eval_conjugate(self):
        from sympy.functions.elementary.complexes import conjugate
        return Piecewise(*[(conjugate(e), c) for e, c in self.args])

    def _eval_derivative(self, x):
        return Piecewise(*[(diff(e, x), c) for e, c in self.args])

    def _eval_evalf(self, prec):
        return Piecewise(*[(e.evalf(prec), c) for e, c in self.args])

    def _eval_integral(self, x):
        from sympy.integrals import integrate
        return Piecewise(*[(integrate(e, x), c) for e, c in self.args])

    def _eval_interval(self, sym, a, b):
        """Evaluates the function along the sym in a given interval ab"""
        # FIXME: Currently complex intervals are not supported.  A possible
        # replacement algorithm, discussed in issue 2128, can be found in the
        # following papers;
        #     http://portal.acm.org/citation.cfm?id=281649
        #     http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.4127&rep=rep1&type=pdf
        mul = 1
        if (a == b) is True:
            return S.Zero
        elif (a > b) is True:
            a, b, mul = b, a, -1
        elif (a <= b) is not True:
            newargs = []
            for e, c in self.args:
                intervals = self._sort_expr_cond(sym, S.NegativeInfinity, S.Infinity, c)
                values = []
                for lower, upper in intervals:
                    if (a < lower) is True:
                        mid = lower
                        rep = b
                        val = e.subs(sym, b) - e.subs(sym, mid)
                        val += self._eval_interval(sym, a, mid)
                    elif (a > upper) is True:
                        mid = upper
                        rep = b
                        val = e.subs(sym, b) - e.subs(sym, mid)
                        val += self._eval_interval(sym, a, mid)
                    elif (a >= lower) is True and (a <= upper) is True:
                        rep = b
                        val = e.subs(sym, b) - e.subs(sym, a)
                    elif (b < lower) is True:
                        mid = lower
                        rep = a
                        val = e.subs(sym, mid) - e.subs(sym, a)
                        val += self._eval_interval(sym, mid, b)
                    elif (b > upper) is True:
                        mid = upper
                        rep = a
                        val = e.subs(sym, mid) - e.subs(sym, a)
                        val += self._eval_interval(sym, mid, b)
                    elif ((b >= lower) is True) and ((b <= upper) is True):
                        rep = a
                        val = e.subs(sym, b) - e.subs(sym, a)
                    else:
                        raise NotImplementedError(
                            """The evaluation of a Piecewise interval when both the lower
                            and the upper limit are symbolic is not yet implemented.""")
                    values.append(val)
                if len(set(values)) == 1 :
                    try:
                        c = c.subs(sym, rep)
                    except AttributeError:
                        pass
                    e = values[0]
                    newargs.append((e, c))
                else:
                    for i in range(len(values)):
                        newargs.append((values[i], (c is True and i == len(values) - 1) or
                            And(rep >= intervals[i][0], rep <= intervals[i][1])))
            return Piecewise(*newargs)

        # Determine what intervals the expr,cond pairs affect.
        int_expr = self._sort_expr_cond(sym, a, b)

        # Finally run through the intervals and sum the evaluation.
        ret_fun = 0
        for int_a, int_b, expr in int_expr:
            ret_fun += expr._eval_interval(sym, Max(a, int_a), Min(b, int_b))
        return mul * ret_fun

    def _sort_expr_cond(self, sym, a, b, targetcond = None):
        """Determine what intervals the expr, cond pairs affect.

        1) If cond is True, then log it as default
        1.1) Currently if cond can't be evaluated, throw NotImplementedError.
        2) For each inequality, if previous cond defines part of the interval