from sage.all import *


def face_generated_by(K,S):
    r"""
    Return the intersection of all faces of ``K`` that contain ``S``.

    REFERENCES:

    .. [Tam] Bit-Shun Tam. On the duality operator of a convex cone. Linear
       Algebra and its Applications, 64:33-56, 1985, doi:10.1016/0024-3795(85)
       90265-4.

    SETUP::

        sage: from mjo.cone.faces import face_generated_by

    EXAMPLES:

    The face generated by a standard basis vector in the nonnegative
    orthant should be the cone consisting of all nonnegative multiples
    of that standard basis vector::

        sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
        sage: F = Cone([(1,0,0)])
        sage: face_generated_by(K,F) == F
        True

    If we take a nontrivial combination of standard basis vectors in the
    nonnegative orthant, then the face that the combination generates
    should be the cone generated by those two basis vectors::

        sage: e1 = vector(QQ, [1,0,0])
        sage: e2 = vector(QQ, [0,1,0])
        sage: e3 = vector(QQ, [0,0,1])
        sage: K = Cone([e1,e2,e2])
        sage: F = [e1/2 + e2/2]
        sage: face_generated_by(K,F).is_equivalent(Cone([e1,e2]))
        True

     An error is raised if ``S`` is not contained in ``K``::

        sage: K = Cone([(1,0),(0,1)])
        sage: S = [(1,1), (-1,3)]
        sage: face_generated_by(K,S)
        Traceback (most recent call last):
        ...
        ValueError: S is not a subset of the cone

    TESTS:

    The face generated by <whatever> should be a face::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8, max_rays=10)
        sage: S = ( K.random_element() for idx in range(5) )
        sage: F = face_generated_by(K, S)
        sage: F.is_face_of(K)
        True

    The face generated by a set should always contain that set::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8, max_rays=10)
        sage: S = ( K.random_element() for idx in range(5) )
        sage: F = face_generated_by(K, S)
        sage: all(F.contains(x) for x in S)
        True

    The generators of a proper cone are all extreme vectors of the cone,
    and therefore generate their own faces::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8,
        ....:                 max_rays=10,
        ....:                 strictly_convex=True,
        ....:                 solid=True)
        sage: all(face_generated_by(K, [r]) == Cone([r]) for r in K)
        True

    For any point ``x`` in ``K`` and any face ``F`` of ``K``, we have
    that ``x`` is in the relative interior of ``F`` if and only if
    ``F`` is the face generated by ``x`` [Tam]_::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8, max_rays=10)
        sage: x = K.random_element()
        sage: S = [x]
        sage: F = K.face_lattice().random_element()
        sage: expected = F.relative_interior_contains(x)
        sage: actual = (F == face_generated_by(K, S))
        sage: actual == expected
        True

    If ``F`` and ``G`` are two faces of ``K``, then the join of ``F``
    and ``G`` in the face lattice is equal to the face generated by
    ``F + G`` (in the Minkowski sense) [Tam]_::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8, max_rays=10)
        sage: L = K.face_lattice()
        sage: F = L.random_element()
        sage: G = L.random_element()
        sage: expected = L.join(F,G)
        sage: actual = face_generated_by(K, F.rays() + G.rays())
        sage: actual == expected
        True

    Combining Proposition 3.1 and Corollary 3.9 in [Tam]_ gives the
    following equality for any ``y`` in ``K``::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8, max_rays=10)
        sage: y = K.random_element()
        sage: S = [y]
        sage: phi_y = face_generated_by(K,S)
        sage: points_cone_gens = list(K.rays()) + [-z for z in phi_y.rays()]
        sage: points_cone = Cone(points_cone_gens, K.lattice())
        sage: actual = phi_y.span(QQ)
        sage: expected = points_cone.linear_subspace()
        sage: actual == expected
        True

    """
    face_lattice = K.face_lattice()
    candidates = [F for F in face_lattice if all(F.contains(x) for x in S)]

    # K itself is a face of K, so unless we were given a set S that
    # isn't a subset of K, the candidates list will be nonempty.
    if len(candidates) == 0:
        raise ValueError('S is not a subset of the cone')
    else:
        return face_lattice.sorted(candidates)[0]


def dual_face(K,F):
    r"""
    Return the dual face of ``F`` with respect to the cone ``K``.

    OUTPUT:

    A face of ``K.dual()``.

    REFERENCES:

    .. [HilgertHofmannLawson] Joachim Hilgert, Karl Heinrich Hofmann, and Jimmie
       D. Lawson. Lie groups, convex cones and semigroups. Oxford Mathematical
       Monographs. Clarendon Press, Oxford, 1989. ISBN 9780198535690.

    .. [Tam] Bit-Shun Tam. On the duality operator of a convex cone. Linear
       Algebra and its Applications, 64:33-56, 1985, doi:10.1016/0024-3795(85)
       90265-4.

    SETUP::

        sage: from mjo.cone.faces import (dual_face, face_generated_by)

    EXAMPLES:

    The dual face of the first standard basis vector in three dimensions
    is the face generated by the other two standard basis vectors::

        sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
        sage: F = Cone([(1,0,0)])
        sage: dual_face(K,F).rays()
        M(0, 0, 1),
        M(0, 1, 0)
        in 3-d lattice M

    TESTS:

    The dual face of ``K`` with respect to itself should be the
    lineality space of its dual [Tam]_::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8, max_rays=10)
        sage: K_dual = K.dual()
        sage: lKd_gens = ( dir*l for dir in [1,-1] for l in K_dual.lines() )
        sage: linspace_K_dual = Cone(lKd_gens, K_dual.lattice())
        sage: dual_face(K,K).is_equivalent(linspace_K_dual)
        True

    If ``K`` is proper, then the dual face of its trivial face is the
    dual of ``K`` [Tam]_::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8,
        ....:                 max_rays=10,
        ....:                 strictly_convex=True,
        ....:                 solid=True)
        sage: L = K.lattice()
        sage: trivial_face = Cone([L.zero()], L)
        sage: dual_face(K,trivial_face).is_equivalent(K.dual())
        True

    The dual of the cone of ``K`` at ``y`` is the dual face of the face
    of ``K`` generated by ``y`` ([Tam]_ Corollary 3.2)::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8, max_rays=10)
        sage: y = K.random_element()
        sage: S = [y]
        sage: phi_y = face_generated_by(K,S)
        sage: points_cone_gens = list(K.rays()) + [-z for z in phi_y.rays()]
        sage: points_cone = Cone(points_cone_gens, K.lattice())
        sage: points_cone.dual().is_equivalent(dual_face(K, phi_y))
        True

    Since all faces of a polyhedral cone are exposed, the dual face of a
    dual face should be the original face [HilgertHofmannLawson]_::

        sage: set_random_seed()
        sage: def check_prop(K,F):
        ....:     return dual_face(K.dual(), dual_face(K,F)).is_equivalent(F)
        sage: K = random_cone(max_ambient_dim=8, max_rays=10)
        sage: all(check_prop(K,F) for F in K.face_lattice())
        True

    """
    # Ensure that F is actually a face of K before continuing.
    if not F.is_face_of(K):
        raise ValueError("%s is not a face of %s" % (F,K))

    span_F = Cone((c*g for c in [1,-1] for g in F), F.lattice())
    return K.dual().intersection(span_F.dual())