# Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we
# have to explicitly mangle our sitedir here so that "mjo.cone"
# resolves.
from os.path import abspath
from site import addsitedir
addsitedir(abspath('../../'))

from sage.all import *

def rearrangement_cone(p,n):
    r"""
    Return the rearrangement cone of order ``p`` in ``n`` dimensions.

    The rearrangement cone in ``n`` dimensions has as its elements
    vectors of length ``n``. For inclusion in the cone, the smallest
    ``p`` components of a vector must sum to a nonnegative number.

    For example, the rearrangement cone of order ``p == 1`` has its
    single smallest component nonnegative. This implies that all
    components are nonnegative, and that therefore the rearrangement
    cone of order one is the nonnegative orthant.

    When ``p == n``, the sum of all components of a vector must be
    nonnegative for inclusion in the cone. That is, the cone is a
    half-space in ``n`` dimensions.

    INPUT:

    - ``p`` -- The number of components to "rearrange."

    - ``n`` -- The dimension of the ambient space for the resulting cone.

    OUTPUT:

    A polyhedral closed convex cone object representing a rearrangement
    cone of order ``p`` in ``n`` dimensions.

    EXAMPLES:

    The rearrangement cones of order one are nonnegative orthants::

        sage: rearrangement_cone(1,1) == Cone([(1,)])
        True
        sage: rearrangement_cone(1,2) == Cone([(0,1),(1,0)])
        True
        sage: rearrangement_cone(1,3) == Cone([(0,0,1),(0,1,0),(1,0,0)])
        True

    When ``p == n``, the resulting cone will be a half-space, so we
    expect its lineality to be one less than ``n`` because it will
    contain a hyperplane but is not the entire space::

        sage: rearrangement_cone(5,5).lineality()
        4

    All rearrangement cones are proper::

        sage: all([ rearrangement_cone(p,n).is_proper()
        ....:               for n in range(10)
        ....:               for p in range(n) ])
        True

    The Lyapunov rank of the rearrangement cone of order ``p`` in ``n``
    dimensions is ``n`` for ``p == 1`` or ``p == n`` and one otherwise::

        sage: all([ rearrangement_cone(p,n).lyapunov_rank() == n
        ....:               for n in range(2, 10)
        ....:               for p in [1, n-1] ])
        True
        sage: all([ rearrangement_cone(p,n).lyapunov_rank() == 1
        ....:               for n in range(3, 10)
        ....:               for p in range(2, n-1) ])
        True

    TESTS:

    The rearrangement cone is permutation-invariant::

        sage: n = ZZ.random_element(2,10).abs()
        sage: p = ZZ.random_element(1,n)
        sage: K = rearrangement_cone(p,n)
        sage: P = SymmetricGroup(n).random_element().matrix()
        sage: all([ K.contains(P*r) for r in K.rays() ])
        True

    """

    def d(j):
        v = [1]*n    # Create the list of all ones...
        v[j] = 1 - p # Now "fix" the ``j``th entry.
        return v

    V = VectorSpace(QQ, n)
    G = V.basis() + [ d(j) for j in range(n) ]
    return Cone(G)


def has_rearrangement_property(v, p):
    r"""
    Test if the vector ``v`` has the "rearrangement property."

    The rearrangement cone of order ``p`` in `n` dimensions has its
    members vectors of length `n`. The "rearrangement property,"
    satisfied by its elements, is to have its smallest ``p`` components
    sum to a nonnegative number.

    We believe that we have a description of the extreme vectors of the
    rearrangement cone: see ``rearrangement_cone()``. This function is
    used to test that conic combinations of those extreme vectors are in
    fact elements of the rearrangement cone. We can't test all conic
    combinations, obviously, but we can test a random one.

    To become more sure of the result, generate a bunch of vectors with
    ``random_element()`` and test them with this function.

    INPUT:

    - ``v`` -- An element of a cone suspected of being the rearrangement
               cone of order ``p``.

    - ``p`` -- The suspected order of the rearrangement cone.

    OUTPUT:

    If ``v`` has the rearrangement property (that is, if its smallest ``p``
    components sum to a nonnegative number), ``True`` is returned. Otherwise
    ``False`` is returned.

    EXAMPLES:

    Every element of a rearrangement cone should have the property::

        sage: for n in range(2,10):
        ....:     for p in range(1, n-1):
        ....:         K = rearrangement_cone(p,n)
        ....:         v = K.random_element()
        ....:         if not has_rearrangement_property(v,p): print v

    """
    components = sorted(v)[0:p]
    return sum(components) >= 0