Module Reference
================

Symbols
-------

*Symbols* are the basic components to build expressions and constraints.
They correspond to mathematical variables.

.. class:: Symbol(name)

    Return a symbol with the name string given in argument.
    Alternatively, the function :func:`symbols` allows to create several symbols at once.
    Symbols are instances of class :class:`LinExpr` and inherit its functionalities.

    >>> x = Symbol('x')
    >>> x
    x

    Two instances of :class:`Symbol` are equal if they have the same name.

    .. attribute:: name

        The name of the symbol.

    .. method:: asdummy()

        Return a new :class:`Dummy` symbol instance with the same name.

    .. method:: sortkey()

        Return a sorting key for the symbol.
        It is useful to sort a list of symbols in a consistent order, as comparison functions are overridden (see the documentation of class :class:`LinExpr`).

        >>> sort(symbols, key=Symbol.sortkey)


.. function:: symbols(names)

    This function returns a tuple of symbols whose names are taken from a comma or whitespace delimited string, or a sequence of strings.
    It is useful to define several symbols at once.

    >>> x, y = symbols('x y')
    >>> x, y = symbols('x, y')
    >>> x, y = symbols(['x', 'y'])


Sometimes you need to have a unique symbol. For example, you might need a temporary one in some calculation, which is going to be substituted for something else at the end anyway.
This is achieved using ``Dummy('x')``.

.. class:: Dummy(name=None)

    A variation of :class:`Symbol` in which all symbols are unique and identified by an internal count index.
    If a name is not supplied then a string value of the count index will be used.
    This is useful when a unique, temporary variable is needed and the name of the variable used in the expression is not important.

    Unlike :class:`Symbol`, :class:`Dummy` instances with the same name are not equal:

    >>> x = Symbol('x')
    >>> x1, x2 = Dummy('x'), Dummy('x')
    >>> x == x1
    False
    >>> x1 == x2
    False
    >>> x1 == x1
    True


Linear Expressions
------------------

A *linear expression* consists of a list of coefficient-variable pairs that capture the linear terms, plus a constant term.
Linear expressions are used to build constraints. They are temporary objects that typically have short lifespans.

Linear expressions are generally built using overloaded operators.
For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :class:`LinExpr`.

.. class:: LinExpr(coefficients=None, constant=0)
              LinExpr(string)

    Return a linear expression from a dictionary or a sequence, that maps symbols to their coefficients, and a constant term.
    The coefficients and the constant term must be rational numbers.

    For example, the linear expression ``x + 2y + 1`` can be constructed using one of the following instructions:

    >>> x, y = symbols('x y')
    >>> LinExpr({x: 1, y: 2}, 1)
    >>> LinExpr([(x, 1), (y, 2)], 1)

    However, it may be easier to use overloaded operators:

    >>> x, y = symbols('x y')
    >>> x + 2*y + 1

    Alternatively, linear expressions can be constructed from a string:

    >>> LinExpr('x + 2*y + 1')

    :class:`LinExpr` instances are hashable, and should be treated as immutable.

    A linear expression with a single symbol of coefficient 1 and no constant term is automatically subclassed as a :class:`Symbol` instance.
    A linear expression with no symbol, only a constant term, is automatically subclassed as a :class:`Rational` instance.

    .. method:: coefficient(symbol)
                __getitem__(symbol)

        Return the coefficient value of the given symbol, or ``0`` if the symbol does not appear in the expression.

    .. method:: coefficients()

        Iterate over the pairs ``(symbol, value)`` of linear terms in the expression.
        The constant term is ignored.

    .. attribute:: constant

        The constant term of the expression.

    .. attribute:: symbols

        The tuple of symbols present in the expression, sorted according to :meth:`Symbol.sortkey`.

    .. attribute:: dimension

        The dimension of the expression, i.e. the number of symbols present in it.

    .. method:: isconstant()

        Return ``True`` if the expression only consists of a constant term.
        In this case, it is a :class:`Rational` instance.

    .. method:: issymbol()

        Return ``True`` if an expression only consists of a symbol with coefficient ``1``.
        In this case, it is a :class:`Symbol` instance.

    .. method:: values()

        Iterate over the coefficient values in the expression, and the constant term.

    .. method:: __add__(expr)

        Return the sum of two linear expressions.

    .. method:: __sub__(expr)

        Return the difference between two linear expressions.

    .. method:: __mul__(value)

        Return the product of the linear expression by a rational.

    .. method:: __truediv__(value)

        Return the quotient of the linear expression by a rational.

    .. method:: __eq__(expr)

        Test whether two linear expressions are equal.

    As explained below, it is possible to create polyhedra from linear expressions using comparison methods.

    .. method:: __lt__(expr)
                __le__(expr)
                __ge__(expr)
                __gt__(expr)

        Create a new :class:`Polyhedron` instance whose unique constraint is the comparison between two linear expressions.
        As an alternative, functions :func:`Lt`, :func:`Le`, :func:`Ge` and :func:`Gt` can be used.

        >>> x, y = symbols('x y')
        >>> x < y
        Le(x - y + 1, 0)


    .. method:: scaleint()

        Return the expression multiplied by its lowest common denominator to make all values integer.

    .. method:: subs(symbol, expression)
                subs(pairs)

        Substitute the given symbol by an expression and return the resulting expression.
        Raise :exc:`TypeError` if the resulting expression is not linear.

        >>> x, y = symbols('x y')
        >>> e = x + 2*y + 1
        >>> e.subs(y, x - 1)
        3*x - 1

        To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.

        >>> e.subs({x: y, y: x})
        2*x + y + 1

    .. classmethod:: fromstring(string)

        Create an expression from a string.
        Raise :exc:`SyntaxError` if the string is not properly formatted.

    There are also methods to convert linear expressions to and from `SymPy <http://sympy.org>`_ expressions:

    .. classmethod:: fromsympy(expr)

        Create a linear expression from a :mod:`sympy` expression.
        Raise :exc:`TypeError` is the :mod:`sympy` expression is not linear.

    .. method:: tosympy()

        Convert the linear expression to a sympy expression.


Apart from :mod:`Symbol`, a particular case of linear expressions are rational values, i.e. linear expressions consisting only of a constant term, with no symbol.
They are implemented by the :class:`Rational` class, that inherits from both :class:`LinExpr` and :class:`fractions.Fraction` classes.

.. class:: Rational(numerator, denominator=1)
              Rational(string)

    The first version requires that the *numerator* and *denominator* are instances of :class:`numbers.Rational` and returns a new :class:`Rational` instance with the value ``numerator/denominator``.
    If the denominator is ``0``, it raises a :exc:`ZeroDivisionError`.
    The other version of the constructor expects a string.
    The usual form for this instance is::

        [sign] numerator ['/' denominator]

    where the optional ``sign`` may be either '+' or '-' and the ``numerator`` and ``denominator`` (if present) are strings of decimal digits.

    See the documentation of :class:`fractions.Fraction` for more information and examples.

Polyhedra
---------

A *convex polyhedron* (or simply "polyhedron") is the space defined by a system of linear equalities and inequalities.
This space can be unbounded.

.. class:: Polyhedron(equalities, inequalities)
              Polyhedron(string)
              Polyhedron(geometric object)

    Return a polyhedron from two sequences of linear expressions: *equalities* is a list of expressions equal to ``0``, and *inequalities* is a list of expressions greater or equal to ``0``.
    For example, the polyhedron ``0 <= x <= 2, 0 <= y <= 2`` can be constructed with:

    >>> x, y = symbols('x y')
    >>> square = Polyhedron([], [x, 2 - x, y, 2 - y])

    It may be easier to use comparison operators :meth:`LinExpr.__lt__`, :meth:`LinExpr.__le__`, :meth:`LinExpr.__ge__`, :meth:`LinExpr.__gt__`, or functions :func:`Lt`, :func:`Le`, :func:`Eq`, :func:`Ge` and :func:`Gt`, using one of the following instructions:

    >>> x, y = symbols('x y')
    >>> square = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2)
    >>> square = Le(0, x, 2) & Le(0, y, 2)

    It is also possible to build a polyhedron from a string.

    >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')

    Finally, a polyhedron can be constructed from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.aspolyedron` method.
    This way, it is possible to compute the polyhedral hull of a :class:`Domain` instance, i.e., the convex hull of two polyhedra:

    >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
    >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
    >>> Polyhedron(square | square2)

    A polyhedron is a :class:`Domain` instance, and, therefore, inherits the functionalities of this class.
    It is also a :class:`GeometricObject` instance.

    .. attribute:: equalities

        The tuple of equalities.
        This is a list of :class:`LinExpr` instances that are equal to ``0`` in the polyhedron.

    .. attribute:: inequalities

        The tuple of inequalities.
        This is a list of :class:`LinExpr` instances that are greater or equal to ``0`` in the polyhedron.

    .. attribute:: constraints

        The tuple of constraints, i.e., equalities and inequalities.
        This is semantically equivalent to: ``equalities + inequalities``.

    .. method:: widen(polyhedron)

        Compute the *standard widening* of two polyhedra, à la Halbwachs.

        In its current implementation, this method is slow and should not be used on large polyhedra.


.. data:: Empty

    The empty polyhedron, whose set of constraints is not satisfiable.

.. data:: Universe

    The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.

Domains
-------

A *domain* is a union of polyhedra.
Unlike polyhedra, domains allow exact computation of union and complementary operations.

.. class:: Domain(*polyhedra)
              Domain(string)
              Domain(geometric object)

    Return a domain from a sequence of polyhedra.

    >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
    >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
    >>> dom = Domain([square, square2])

    It is also possible to build domains from polyhedra using arithmetic operators :meth:`Domain.__and__`, :meth:`Domain.__or__` or functions :func:`And` and :func:`Or`, using one of the following instructions:

    >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
    >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
    >>> dom = square | square2
    >>> dom = Or(square, square2)

    Alternatively, a domain can be built from a string:

    >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 2 <= x <= 4, 2 <= y <= 4')

    Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.

    A domain is also a :class:`GeometricObject` instance.
    A domain with a unique polyhedron is automatically subclassed as a :class:`Polyhedron` instance.

    .. attribute:: polyhedra

        The tuple of polyhedra present in the domain.

    .. attribute:: symbols

        The tuple of symbols present in the domain equations, sorted according to :meth:`Symbol.sortkey`.

    .. attribute:: dimension

        The dimension of the domain, i.e. the number of symbols present in it.

    .. method:: isempty()

        Return ``True`` if the domain is empty, that is, equal to :data:`Empty`.

    .. method:: __bool__()

        Return ``True`` if the domain is non-empty.

    .. method:: isuniverse()

        Return ``True`` if the domain is universal, that is, equal to :data:`Universe`.

    .. method:: isbounded()

        Return ``True`` is the domain is bounded.

    .. method:: __eq__(domain)

        Return ``True`` if two domains are equal.

    .. method:: isdisjoint(domain)

        Return ``True`` if two domains have a null intersection.

    .. method:: issubset(domain)
                __le__(domain)

        Report whether another domain contains the domain.

    .. method:: __lt__(domain)

        Report whether another domain is contained within the domain.

    .. method:: complement()
                __invert__()

        Return the complementary domain of the domain.

    .. method:: make_disjoint()

        Return an equivalent domain, whose polyhedra are disjoint.

    .. method:: coalesce()

        Simplify the representation of the domain by trying to combine pairs of polyhedra into a single polyhedron, and return the resulting domain.

    .. method:: detect_equalities()

        Simplify the representation of the domain by detecting implicit equalities, and return the resulting domain.

    .. method:: remove_redundancies()

        Remove redundant constraints in the domain, and return the resulting domain.

    .. method:: project(symbols)

        Project out the sequence of symbols given in arguments, and return the resulting domain.

    .. method:: sample()

        Return a sample of the domain, as an integer instance of :class:`Point`.
        If the domain is empty, a :exc:`ValueError` exception is raised.

    .. method:: intersection(domain[, ...])
                __and__(domain)

        Return the intersection of two or more domains as a new domain.
        As an alternative, function :func:`And` can be used.

    .. method:: union(domain[, ...])
                __or__(domain)
                __add__(domain)

        Return the union of two or more domains as a new domain.
        As an alternative, function :func:`Or` can be used.

    .. method:: difference(domain)
                __sub__(domain)

        Return the difference between two domains as a new domain.

    .. method:: lexmin()

        Return the lexicographic minimum of the elements in the domain.

    .. method:: lexmax()

        Return the lexicographic maximum of the elements in the domain.

    .. method:: vertices()

        Return the vertices of the domain, as a list of rational instances of :class:`Point`.

    .. method:: points()

        Return the integer points of a bounded domain, as a list of integer instances of :class:`Point`.
        If the domain is not bounded, a :exc:`ValueError` exception is raised.

    .. method:: __contains__(point)

        Return ``True`` if the point is contained within the domain.

    .. method:: faces()

        Return the list of faces of a bounded domain.
        Each face is represented by a list of vertices, in the form of rational instances of :class:`Point`.
        If the domain is not bounded, a :exc:`ValueError` exception is raised.

    .. method:: plot(plot=None, **options)

        Plot a 2D or 3D domain using `matplotlib <http://matplotlib.org/>`_.
        Draw it to the current *plot* object if present, otherwise create a new one.
        *options* are keyword arguments passed to the matplotlib drawing functions, they can be used to set the drawing color for example.
        Raise :exc:`ValueError` is the domain is not 2D or 3D.

    .. method:: subs(symbol, expression)
                subs(pairs)

        Substitute the given symbol by an expression in the domain constraints.
        To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
        The syntax of this function is similar to :func:`LinExpr.subs`.

    .. classmethod:: fromstring(string)

        Create a domain from a string.
        Raise :exc:`SyntaxError` if the string is not properly formatted.

    There are also methods to convert a domain to and from `SymPy <http://sympy.org>`_ expressions:

    .. classmethod:: fromsympy(expr)

        Create a domain from a sympy expression.

    .. method:: tosympy()

        Convert the domain to a sympy expression.


Comparison and Logic Operators
------------------------------

The following functions create :class:`Polyhedron` or :class:`Domain` instances using the comparisons of two or more :class:`LinExpr` instances:

.. function:: Lt(expr1, expr2[, expr3, ...])

    Create the polyhedron with constraints ``expr1 < expr2 < expr3 ...``.

.. function:: Le(expr1, expr2[, expr3, ...])

    Create the polyhedron with constraints ``expr1 <= expr2 <= expr3 ...``.

.. function:: Eq(expr1, expr2[, expr3, ...])

    Create the polyhedron with constraints ``expr1 == expr2 == expr3 ...``.

.. function:: Ne(expr1, expr2[, expr3, ...])

    Create the domain such that ``expr1 != expr2 != expr3 ...``.
    The result is a :class:`Domain`, not a :class:`Polyhedron`.

.. function:: Ge(expr1, expr2[, expr3, ...])

    Create the polyhedron with constraints ``expr1 >= expr2 >= expr3 ...``.

.. function:: Gt(expr1, expr2[, expr3, ...])

    Create the polyhedron with constraints ``expr1 > expr2 > expr3 ...``.

The following functions combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:

.. function:: Or(domain1, domain2[, ...])

    Create the union domain of the domains given in arguments.

.. function:: And(domain1, domain2[, ...])

    Create the intersection domain of the domains given in arguments.

.. function:: Not(domain)

    Create the complementary domain of the domain given in argument.


Geometric Objects
-----------------

.. class:: GeometricObject

    :class:`GeometricObject` is an abstract class to represent objects with a geometric representation in space.
    Subclasses of :class:`GeometricObject` are :class:`Polyhedron`, :class:`Domain` and :class:`Point`.
    The following elements must be provided:

    .. attribute:: symbols

        The tuple of symbols present in the object expression, sorted according to :class:`Symbol.sortkey()`.

    .. attribute:: dimension

        The dimension of the object, i.e. the number of symbols present in it.

    .. method:: aspolyedron()

        Return a :class:`Polyhedron` object that approximates the geometric object.

    .. method:: asdomain()

        Return a :class:`Domain` object that approximates the geometric object.

.. class:: Point(coordinates)

    Create a point from a dictionary or a sequence that maps the symbols to their coordinates.
    Coordinates must be rational numbers.

    For example, the point ``(x: 1, y: 2)`` can be constructed using one of the following instructions:

    >>> x, y = symbols('x y')
    >>> p = Point({x: 1, y: 2})
    >>> p = Point([(x, 1), (y, 2)])

    :class:`Point` instances are hashable and should be treated as immutable.

    A point is a :class:`GeometricObject` instance.

    .. attribute:: symbols

        The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.

    .. attribute:: dimension

        The dimension of the point, i.e. the number of symbols present in it.

    .. method:: coordinate(symbol)
                __getitem__(symbol)

        Return the coordinate value of the given symbol.
        Raise :exc:`KeyError` if the symbol is not involved in the point.

    .. method:: coordinates()

        Iterate over the pairs ``(symbol, value)`` of coordinates in the point.

    .. method:: values()

        Iterate over the coordinate values in the point.

    .. method:: isorigin()

        Return ``True`` if all coordinates are ``0``.

    .. method:: __bool__()

        Return ``True`` if not all coordinates are ``0``.

    .. method:: __add__(vector)

        Translate the point by a :class:`Vector` object and return the resulting point.

    .. method:: __sub__(point)
                __sub__(vector)

        The first version substracts a point from another and returns the resulting vector.
        The second version translates the point by the opposite vector of *vector* and returns the resulting point.

    .. method:: __eq__(point)

        Test whether two points are equal.


.. class:: Vector(coordinates)
           Vector(point1, point2)

    The first version creates a vector from a dictionary or a sequence that maps the symbols to their coordinates, similarly to :meth:`Point`.
    The second version creates a vector between two points.

    :class:`Vector` instances are hashable and should be treated as immutable.

    .. attribute:: symbols

        The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.

    .. attribute:: dimension

        The dimension of the point, i.e. the number of symbols present in it.

    .. method:: coordinate(symbol)
                __getitem__(symbol)

        Return the coordinate value of the given symbol.
        Raise :exc:`KeyError` if the symbol is not involved in the point.

    .. method:: coordinates()

        Iterate over the pairs ``(symbol, value)`` of coordinates in the point.

    .. method:: values()

        Iterate over the coordinate values in the point.

    .. method:: isnull()

        Return ``True`` if all coordinates are ``0``.

    .. method:: __bool__()

        Return ``True`` if not all coordinates are ``0``.

    .. method:: __add__(point)
                __add__(vector)

        The first version translates the point *point* to the vector and returns the resulting point.
        The second version adds vector *vector* to the vector and returns the resulting vector.

    .. method:: __sub__(point)
                __sub__(vector)

        The first version substracts a point from a vector and returns the resulting point.
        The second version returns the difference vector between two vectors.

    .. method:: __neg__()

        Return the opposite vector.

    .. method:: __mul__(value)

        Multiply the vector by a scalar value and return the resulting vector.

    .. method:: __truediv__(value)

        Divide the vector by a scalar value and return the resulting vector.

    .. method:: __eq__(vector)

        Test whether two vectors are equal.

    .. method:: angle(vector)

        Retrieve the angle required to rotate the vector into the vector passed in argument.
        The result is an angle in radians, ranging between ``-pi`` and ``pi``.

    .. method:: cross(vector)

        Compute the cross product of two 3D vectors.
        If either one of the vectors is not three-dimensional, a :exc:`ValueError` exception is raised.

    .. method:: dot(vector)

        Compute the dot product of two vectors.

    .. method:: norm()

        Return the norm of the vector.

    .. method:: norm2()

        Return the squared norm of the vector.

    .. method:: asunit()

        Return the normalized vector, i.e. the vector of same direction but with norm 1.