<filename>sympy/series/order.py
from sympy.core import Basic, S, sympify, Expr, Rational, Symbol
from sympy.core import Add, Mul, expand_power_base, expand_log
from sympy.core.cache import cacheit
from sympy.core.compatibility import cmp_to_key


class Order(Expr):
    """ Represents the limiting behavior of some function

    The order of a function characterizes the function based on the limiting
    behavior of the function as it goes to some limit. Only taking the limit
    point to be 0 is currently supported. This is expressed in big O notation
    [1]_.

    The formal definition for the order of a function `g(x)` about a point `a`
    is such that `g(x) = O(f(x))` as `x \\rightarrow a` if and only if for any
    `\delta > 0` there exists a `M > 0` such that `|g(x)| \leq M|f(x)|` for
    `|x-a| < \delta`. This is equivalent to `\lim_{x \\rightarrow a}
    |g(x)/f(x)| < \infty`.

    Let's illustrate it on the following example by taking the expansion of
    `\sin(x)` about 0:

    .. math ::
        \sin(x) = x - x^3/3! + O(x^5)

    where in this case `O(x^5) = x^5/5! - x^7/7! + \cdots`. By the definition
    of `O`, for any `\delta > 0` there is an `M` such that:

    .. math ::
        |x^5/5! - x^7/7! + ....| <= M|x^5| \\text{ for } |x| < \delta

    or by the alternate definition:

    .. math ::
        \lim_{x \\rightarrow 0} | (x^5/5! - x^7/7! + ....) / x^5| < \infty

    which surely is true, because

    .. math ::
        \lim_{x \\rightarrow 0} | (x^5/5! - x^7/7! + ....) / x^5| = 1/5!


    As it is usually used, the order of a function can be intuitively thought
    of representing all terms of powers greater than the one specified. For
    example, `O(x^3)` corresponds to any terms proportional to `x^3,
    x^4,\ldots` and any higher power. For a polynomial, this leaves terms
    proportional to `x^2`, `x` and constants.

    Examples
    ========

    >>> from sympy import O
    >>> from sympy.abc import x
    >>> O(x)
    O(x)
    >>> O(x)*x
    O(x**2)
    >>> O(x)-O(x)
    O(x)

    References
    ==========

    .. [1] `Big O notation <http://en.wikipedia.org/wiki/Big_O_notation>`_

    Notes
    =====

    In ``O(f(x), x)`` the expression ``f(x)`` is assumed to have a leading
    term.  ``O(f(x), x)`` is automatically transformed to
    ``O(f(x).as_leading_term(x),x)``.

        ``O(expr*f(x), x)`` is ``O(f(x), x)``

        ``O(expr, x)`` is ``O(1)``

        ``O(0, x)`` is 0.

    Multivariate O is also supported:

        ``O(f(x, y), x, y)`` is transformed to
        ``O(f(x, y).as_leading_term(x,y).as_leading_term(y), x, y)``

    In the multivariate case, it is assumed the limits w.r.t. the various
    symbols commute.

    If no symbols are passed then all symbols in the expression are used:

    """

    is_Order = True

    __slots__ = []

    @cacheit
    def __new__(cls, expr, *symbols, **assumptions):

        expr = sympify(expr)
        if expr is S.NaN:
            return S.NaN

        if symbols:
            symbols = map(sympify, symbols)
            if not all(isinstance(s, Symbol) for s in symbols):
                raise NotImplementedError(
                    'Order at points other than 0 not supported.')
        else:
            symbols = list(expr.free_symbols)

        if expr.is_Order:
            v = set(expr.variables)
            symbols = v | set(symbols)
            if symbols == v:
                return expr
            symbols = list(symbols)

        elif symbols:

            symbols = list(set(symbols))

            if len(symbols) > 1:
                # XXX: better way?  We need this expand() to
                # workaround e.g: expr = x*(x + y).
                # (x*(x + y)).as_leading_term(x, y) currently returns
                # x*y (wrong order term!).  That's why we want to deal with
                # expand()'ed expr (handled in "if expr.is_Add" branch below).
                expr = expr.expand()

            if expr.is_Add:
                lst = expr.extract_leading_order(*symbols)
                expr = Add(*[f.expr for (e, f) in lst])

            elif expr:
                expr = expr.as_leading_term(*symbols)
                expr = expr.as_independent(*symbols, **dict(as_Add=False))[1]

                expr = expand_power_base(expr)
                expr = expand_log(expr)

                if len(symbols) == 1:
                    # The definition of O(f(x)) symbol explicitly stated that
                    # the argument of f(x) is irrelevant.  That's why we can
                    # combine some power exponents (only "on top" of the
                    # expression tree for f(x)), e.g.:
                    # x**p * (-x)**q -> x**(p+q) for real p, q.
                    x = symbols[0]
                    margs = list(Mul.make_args(
                        expr.as_independent(x, **dict(as_Add=False))[1]))

                    for i, t in enumerate(margs):
                        if t.is_Pow:
                            b, q = t.args
                            if b in (x, -x) and q.is_real and not q.has(x):
                                margs[i] = x**q
                            elif b.is_Pow and not b.exp.has(x):
                                b, r = b.args
                                if b in (x, -x) and r.is_real:
                                    margs[i] = x**(r*q)
                            elif b.is_Mul and b.args[0] is S.NegativeOne:
                                b = -b
                                if b.is_Pow and not b.exp.has(x):
                                    b, r = b.args
                                    if b in (x, -x) and r.is_real:
                                        margs[i] = x**(r*q)

                    expr = Mul(*margs)

        if expr is S.Zero:
            return expr

        if not expr.has(*symbols):
            expr = S.One

        # create Order instance:
        symbols.sort(key=cmp_to_key(Basic.compare))
        obj = Expr.__new__(cls, expr, *symbols, **assumptions)

        return obj

    def _hashable_content(self):
        return self.args

    def oseries(self, order):
        return self

    def _eval_nseries(self, x, n, logx):
        return self

    @property
    def expr(self):
        return self._args[0]

    @property
    def variables(self):
        return self._args[1:]

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

    def _eval_power(b, e):
        if e.is_Number:
            return Order(b.expr ** e, *b.variables)
        return

    def as_expr_variables(self, order_symbols):
        if order_symbols is None:
            order_symbols = self.variables
        else:
            for s in self.variables:
                if s not in order_symbols:
                    order_symbols = order_symbols + (s,)
        return self.expr, order_symbols

    def removeO(self):
        return S.Zero

    def getO(self):
        return self

    @cacheit
    def contains(self, expr):
        """
        Return True if expr belongs to Order(self.expr, \*self.variables).
        Return False if self belongs to expr.
        Return None if the inclusion relation cannot be determined
        (e.g. when self and expr have different symbols).
        """
        # NOTE: when multiplying out series a lot of queries like
        #       O(...).contains(a*x**b) with many a and few b are made.
        #       Separating out the independent part allows for better caching.
        c, m = expr.as_coeff_mul(*self.variables)
        if m != ():
            return self._contains(Mul(*m))
        else:
            # Mul(*m) == 1, and O(1) treatment is somewhat peculiar ...
            # some day this else should not be necessary
            return self._contains(expr)

    @cacheit
    def _contains(self, expr):
        from sympy import powsimp, limit
        if expr is S.Zero:
            return True
        if expr is S.NaN:
            return False
        if expr.is_Order:
            if self.variables and expr.variables:
                common_symbols = tuple(
                    [s for s in self.variables if s in expr.variables])
            elif self.variables:
                common_symbols = self.variables
            else:
                common_symbols = expr.variables
            if not common_symbols:
                if not (self.variables or expr.variables):  # O(1),O(1)
                    return True
                return None
            r = None
            for s in common_symbols:
                l = limit(powsimp(self.expr/expr.expr, deep=True,
                combine='exp'), s, 0) != 0
                if r is None:
                    r = l
                else:
                    if r != l:
                        return
            return r
        obj = Order(expr, *self.variables)
        return self.contains(obj)

    def _eval_subs(self, old, new):
        if old.is_Symbol and old in self.variables:
            i = list(self.variables).index(old)
            if isinstance(new, Symbol):
                return Order(self.expr._subs(old, new), *(self.variables[:i] + (new,) + self.variables[i + 1:]))
            return Order(self.expr._subs(old, new), *(self.variables[:i] + self.variables[i + 1:]))
        return Order(self.expr._subs(old, new), *self.variables)

    def _eval_conjugate(self):
        expr = self.expr._eval_conjugate()
        if expr is not None:
            return self.func(expr, *self.variables)

    def _eval_derivative(self, x):
        return self.func(self.expr.diff(x), *self.variables) or self

    def _eval_transpose(self):
        expr = self.expr._eval_transpose()
        if expr is not None:
            return self.func(expr, *self.variables)

    def _sage_(self):
        #XXX: SAGE doesn't have Order yet. Let's return 0 instead.
        return Rational(0)._sage_()

O = Order

<filename>sympy/series/order.py
from sympy.core import Basic, S, sympify, Expr, Rational, Symbol
from sympy.core import Add, Mul, expand_power_base, expand_log
from sympy.core.cache import cacheit
from sympy.core.compatibility import cmp_to_key


class Order(Expr):
    """ Represents the limiting behavior of some function

    The order of a function characterizes the function based on the limiting
    behavior of the function as it goes to some limit. Only taking the limit
    point to be 0 is currently supported. This is expressed in big O notation
    [1]_.

    The formal definition for the order of a function `g(x)` about a point `a`
    is such that `g(x) = O(f(x))` as `x \\rightarrow a` if and only if for any
    `\delta > 0` there exists a `M > 0` such that `|g(x)| \leq M|f(x)|` for
    `|x-a| < \delta`. This is equivalent to `\lim_{x \\rightarrow a}
    |g(x)/f(x)| < \infty`.

    Let's illustrate it on the following example by taking the expansion of
    `\sin(x)` about 0:

    .. math ::
        \sin(x) = x - x^3/3! + O(x^5)

    where in this case `O(x^5) = x^5/5! - x^7/7! + \cdots`. By the definition
    of `O`, for any `\delta > 0` there is an `M` such that:

    .. math ::
        |x^5/5! - x^7/7! + ....| <= M|x^5| \\text{ for } |x| < \delta

    or by the alternate definition:

    .. math ::
        \lim_{x \\rightarrow 0} | (x^5/5! - x^7/7! + ....) / x^5| < \infty

    which surely is true, because

    .. math ::
        \lim_{x \\rightarrow 0} | (x^5/5! - x^7/7! + ....) / x^5| = 1/5!


    As it is usually used, the order of a function can be intuitively thought
    of representing all terms of powers greater than the one specified. For
    example, `O(x^3)` corresponds to any terms proportional to `x^3,
    x^4,\ldots` and any higher power. For a polynomial, this leaves terms
    proportional to `x^2`, `x` and constants.

    Examples
    ========

    >>> from sympy import O
    >>> from sympy.abc import x
    >>> O(x)
    O(x)
    >>> O(x)*x
    O(x**2)
    >>> O(x)-O(x)
    O(x)

    References
    ==========

    .. [1] `Big O notation <http://en.wikipedia.org/wiki/Big_O_notation>`_

    Notes
    =====

    In ``O(f(x), x)`` the expression ``f(x)`` is assumed to have a leading
    term.  ``O(f(x), x)`` is automatically transformed to
    ``O(f(x).as_leading_term(x),x)``.

        ``O(expr*f(x), x)`` is ``O(f(x), x)``

        ``O(expr, x)`` is ``O(1)``

        ``O(0, x)`` is 0.

    Multivariate O is also supported:

        ``O(f(x, y), x, y)`` is transformed to
        ``O(f(x, y).as_leading_term(x,y).as_leading_term(y), x, y)``

    In the multivariate case, it is assumed the limits w.r.t. the various
    symbols commute.

    If no symbols are passed then all symbols in the expression are used:

    """

    is_Order = True

    __slots__ = []

    @cacheit
    def __new__(cls, expr, *symbols, **assumptions):

        expr = sympify(expr)
        if expr is S.NaN:
            return S.NaN

        if symbols:
            symbols = map(sympify, symbols)
            if not all(isinstance(s, Symbol) for s in symbols):
                raise NotImplementedError(
                    'Order at points other than 0 not supported.')
        else:
            symbols = list(expr.free_symbols)

        if expr.is_Order:
            v = set(expr.variables)
            symbols = v | set(symbols)
            if symbols == v:
                return expr
            symbols = list(symbols)

        elif symbols:

            symbols = list(set(symbols))

            if len(symbols) > 1:
                # XXX: better way?  We need this expand() to
                # workaround e.g: expr = x*(x + y).
                # (x*(x + y)).as_leading_term(x, y) currently returns
                # x*y (wrong order term!).  That's why we want to deal with
                # expand()'ed expr (handled in "if expr.is_Add" branch below).
                expr = expr.expand()

            if expr.is_Add:
                lst = expr.extract_leading_order(*symbols)
                expr = Add(*[f.expr for (e, f) in lst])

            elif expr:
                expr = expr.as_leading_term(*symbols)
                expr = expr.as_independent(*symbols, **dict(as_Add=False))[1]

                expr = expand_power_base(expr)
                expr = expand_log(expr)

                if len(symbols) == 1:
                    # The definition of O(f(x)) symbol explicitly stated that
                    # the argument of f(x) is irrelevant.  That's why we can
                    # combine some power exponents (only "on top" of the
                    # expression tree for f(x)), e.g.:
                    # x**p * (-x)**q -> x**(p+q) for real p, q.
                    x = symbols[0]
                    margs = list(Mul.make_args(
                        expr.as_independent(x, **dict(as_Add=False))[1]))

                    for i, t in enumerate(margs):
                        if t.is_Pow:
                            b, q = t.args
                            if b in (x, -x) and q.is_real and not q.has(x):
                                margs[i] = x**q
                            elif b.is_Pow and not b.exp.has(x):
                                b, r = b.args
                                if b in (x, -x) and r.is_real:
                                    margs[i] = x**(r*q)
                            elif b.is_Mul and b.args[0] is S.NegativeOne:
                                b = -b
                                if b.is_Pow and not b.exp.has(x):
                                    b, r = b.args
                                    if b in (x, -x) and r.is_real:
                                        margs[i] = x**(r*q)

                    expr = Mul(*margs)

        if expr is S.Zero:
            return expr

        if not expr.has(*symbols):
            expr = S.One

        # create Order instance:
        symbols.sort(key=cmp_to_key(Basic.compare))
        obj = Expr.__new__(cls, expr, *symbols, **assumptions)

        return obj

    def _hashable_content(self):
        return self.args

    def oseries(self, order):
        return self

    def _eval_nseries(self, x, n, logx):
        return self

    @property
    def expr(self):
        return self._args[0]

    @property
    def variables(self):
        return self._args[1:]

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

    def _eval_power(b, e):
        if e.is_Number:
            return Order(b.expr ** e, *b.variables)
        return

    def as_expr_variables(self, order_symbols):
        if order_symbols is None:
            order_symbols = self.variables
        else:
            for s in self.variables:
                if s not in order_symbols:
                    order_symbols = order_symbols + (s,)
        return self.expr, order_symbols

    def removeO(self):
        return S.Zero

    def getO(self):
        return self

    @cacheit
    def contains(self, expr):
        """
        Return True if expr belongs to Order(self.expr, \*self.variables).
        Return False if self belongs to expr.
        Return None if the inclusion relation cannot be determined
        (e.g. when self and expr have different symbols).
        """
        # NOTE: when multiplying out series a lot of queries like
        #       O(...).contains(a*x**b) with many a and few b are made.
        #       Separating out the independent part allows for better caching.
        c, m = expr.as_coeff_mul(*self.variables)
        if m != ():
            return self._contains(Mul(*m))
        else:
            # Mul(*m) == 1, and O(1) treatment is somewhat peculiar ...
            # some day this else should not be necessary
            return self._contains(expr)

    @cacheit
    def _contains(self, expr):
        from sympy import powsimp, limit
        if expr is S.Zero:
            return True
        if expr is S.NaN:
            return False
        if expr.is_Order:
            if self.variables and expr.variables:
                common_symbols = tuple(
                    [s for s in self.variables if s in expr.variables])
            elif self.variables:
                common_symbols = self.variables
            else:
                common_symbols = expr.variables
            if not common_symbols:
                if not (self.variables or expr.variables):  # O(1),O(1)
                    return True
                return None
            r = None
            for s in common_symbols:
                l = limit(powsimp(self.expr/expr.expr, deep=True,
                combine='exp'), s, 0) != 0
                if r is None:
                    r = l
                else:
                    if r != l:
                        return
            return r
        obj = Order(expr, *self.variables)
        return self.contains(obj)

    def _eval_subs(self, old, new):
        if old.is_Symbol and old in self.variables:
            i = list(self.variables).index(old)
            if isinstance(new, Symbol):
                return Order(self.expr._subs(old, new), *(self.variables[:i] + (new,) + self.variables[i + 1:]))
            return Order(self.expr._subs(old, new), *(self.variables[:i] + self.variables[i + 1:]))
        return Order(self.expr._subs(old, new), *self.variables)

    def _eval_conjugate(self):
        expr = self.expr._eval_conjugate()
        if expr is not None:
            return self.func(expr, *self.variables)

    def _eval_derivative(self, x):
        return self.func(self.expr.diff(x), *self.variables) or self

    def _eval_transpose(self):
        expr = self.expr._eval_transpose()
        if expr is not None:
            return self.func(expr, *self.variables)

    def _sage_(self):
        #XXX: SAGE doesn't have Order yet. Let's return 0 instead.
        return Rational(0)._sage_()

O = Order

Represents the limiting behavior of some function      The order of a function characterizes the function based on the limiting     behavior of the function as it goes to some limit. Only taking the limit     point to be 0 is currently supported. This is expressed in big O notation     [1]_.      The formal definition for the order of a function `g(x)` about a point `a`     is such that `g(x) = O(f(x))` as `x \\rightarrow a` if and only if for any     `\delta > 0` there exists a `M > 0` such that `|g(x)| \leq M|f(x)|` for     `|x-a| < \delta`. This is equivalent to `\lim_{x \\rightarrow a}     |g(x)/f(x)| < \infty`.      Let's illustrate it on the following example by taking the expansion of     `\sin(x)` about 0:      .. math ::         \sin(x) = x - x^3/3! + O(x^5)      where in this case `O(x^5) = x^5/5! - x^7/7! + \cdots`. By the definition     of `O`, for any `\delta > 0` there is an `M` such that:      .. math ::         |x^5/5! - x^7/7! + ....| <= M|x^5| \\text{ for } |x| < \delta      or by the alternate definition:      .. math ::         \lim_{x \\rightarrow 0} | (x^5/5! - x^7/7! + ....) / x^5| < \infty      which surely is true, because      .. math ::         \lim_{x \\rightarrow 0} | (x^5/5! - x^7/7! + ....) / x^5| = 1/5!       As it is usually used, the order of a function can be intuitively thought     of representing all terms of powers greater than the one specified. For     example, `O(x^3)` corresponds to any terms proportional to `x^3,     x^4,\ldots` and any higher power. For a polynomial, this leaves terms     proportional to `x^2`, `x` and constants.      Examples     ========      >>> from sympy import O     >>> from sympy.abc import x     >>> O(x)     O(x)     >>> O(x)*x     O(x**2)     >>> O(x)-O(x)     O(x)      References     ==========      .. [1] `Big O notation <http://en.wikipedia.org/wiki/Big_O_notation>`_      Notes     =====      In ``O(f(x), x)`` the expression ``f(x)`` is assumed to have a leading     term.  ``O(f(x), x)`` is automatically transformed to     ``O(f(x).as_leading_term(x),x)``.          ``O(expr*f(x), x)`` is ``O(f(x), x)``          ``O(expr, x)`` is ``O(1)``          ``O(0, x)`` is 0.      Multivariate O is also supported:          ``O(f(x, y), x, y)`` is transformed to         ``O(f(x, y).as_leading_term(x,y).as_leading_term(y), x, y)``      In the multivariate case, it is assumed the limits w.r.t. the various     symbols commute.      If no symbols are passed then all symbols in the expression are used: # XXX: better way?  We need this expand() to # workaround e.g: expr = x*(x + y). # (x*(x + y)).as_leading_term(x, y) currently returns # x*y (wrong order term!).  That's why we want to deal with # expand()'ed expr (handled in "if expr.is_Add" branch below). # The definition of O(f(x)) symbol explicitly stated that # the argument of f(x) is irrelevant.  That's why we can # combine some power exponents (only "on top" of the # expression tree for f(x)), e.g.: # x**p * (-x)**q -> x**(p+q) for real p, q. # create Order instance: Return True if expr belongs to Order(self.expr, \*self.variables).         Return False if self belongs to expr.         Return None if the inclusion relation cannot be determined         (e.g. when self and expr have different symbols). # NOTE: when multiplying out series a lot of queries like #       O(...).contains(a*x**b) with many a and few b are made. #       Separating out the independent part allows for better caching. # Mul(*m) == 1, and O(1) treatment is somewhat peculiar ... # some day this else should not be necessary # O(1),O(1) #XXX: SAGE doesn't have Order yet. Let's return 0 instead.