"""
Compute all mixed Nash equilibria of a 2-player normal form game by
vertex enumeration.

References
----------
B. von Stengel, "Equilibrium Computation for Two-Player Games in
Strategic and Extensive Form," Chapter 3, N. Nisan, T. Roughgarden, E.
Tardos, and V. Vazirani eds., Algorithmic Game Theory, 2007.

"""
import numpy as np
import scipy.spatial
from numba import jit, guvectorize


def vertex_enumeration(g, qhull_options=None):
    """
    Compute mixed-action Nash equilibria of a 2-player normal form game
    by enumeration and matching of vertices of the best response
    polytopes. For a non-degenerate game input, these are all the Nash
    equilibria.

    Internally, `scipy.spatial.ConvexHull` is used to compute vertex
    enumeration of the best response polytopes, or equivalently, facet
    enumeration of their polar polytopes. Then, for each vertex of the
    polytope for player 0, vertices of the polytope for player 1 are
    searched to find a completely labeled pair.

    Parameters
    ----------
    g : NormalFormGame
        NormalFormGame instance with 2 players.

    qhull_options : str, optional(default=None)
        Options to pass to `scipy.spatial.ConvexHull`. See the `Qhull
        manual <http://www.qhull.org>`_  for details.

    Returns
    -------
    list(tuple(ndarray(float, ndim=1)))
        List containing tuples of Nash equilibrium mixed actions.

    """
    return list(vertex_enumeration_gen(g, qhull_options=qhull_options))


def vertex_enumeration_gen(g, qhull_options=None):
    """
    Generator version of `vertex_enumeration`.

    Parameters
    ----------
    g : NormalFormGame
        NormalFormGame instance with 2 players.

    qhull_options : str, optional(default=None)
        Options to pass to `scipy.spatial.ConvexHull`. See the `Qhull
        manual <http://www.qhull.org>`_  for details.

    Yields
    -------
    tuple(ndarray(float, ndim=1))
        Tuple of Nash equilibrium mixed actions.

    """
    try:
        N = g.N
    except AttributeError:
        raise TypeError('input must be a 2-player NormalFormGame')
    if N != 2:
        raise NotImplementedError('Implemented only for 2-player games')

    brps = [_BestResponsePolytope(
        g.players[1-i], idx=i, qhull_options=qhull_options
    ) for i in range(N)]

    labelings_bits_tup = \
        tuple(_ints_arr_to_bits(brps[i].labelings) for i in range(N))
    equations_tup = tuple(brps[i].equations for i in range(N))
    trans_recips = tuple(brps[i].trans_recip for i in range(N))

    return _vertex_enumeration_gen(labelings_bits_tup, equations_tup,
                                   trans_recips)


@jit(nopython=True)
def _vertex_enumeration_gen(labelings_bits_tup, equations_tup, trans_recips):
    """
    Main body of `vertex_enumeration_gen`.

    Parameters
    ----------
    labelings_bits_tup : tuple(ndarray(np.uint64, ndim=1))
        Tuple of ndarrays of integers representing labelings of the
        vertices of the best response polytopes.

    equations_tup : tuple(ndarray(float, ndim=2))
        Tuple of ndarrays containing the hyperplane equations of the
        polar polytopes.

    trans_recips : tuple(scalar(float))
        Tuple of the reciprocals of the translations.

    """
    m, n = equations_tup[0].shape[1] - 1, equations_tup[1].shape[1] - 1
    num_vertices0, num_vertices1 = \
        equations_tup[0].shape[0], equations_tup[1].shape[0]
    ZERO_LABELING0_BITS = (np.uint64(1) << np.uint64(m)) - np.uint64(1)
    COMPLETE_LABELING_BITS = (np.uint64(1) << np.uint64(m+n)) - np.uint64(1)

    for i in range(num_vertices0):
        if labelings_bits_tup[0][i] == ZERO_LABELING0_BITS:
            continue
        for j in range(num_vertices1):
            xor = labelings_bits_tup[0][i] ^ labelings_bits_tup[1][j]
            if xor == COMPLETE_LABELING_BITS:
                yield _get_mixed_actions(
                    labelings_bits_tup[0][i],
                    (equations_tup[0][i], equations_tup[1][j]),
                    trans_recips
                )
                break


class _BestResponsePolytope:
    """
    Class that represents a best response polytope for a player in a
    two-player normal form game.

    Let :math:`A` and :math:`B` be the m x n and n x m payoff matrices
    of players 0 and 1, respectively, where the payoffs are assumed to
    have been shifted in such a way that :math:`A` and :math:`B` are
    nonnegative and have no zero column. In von Stegel (2007), the best
    response polytope for player 0 is defined by

    .. math::

        P = \{x \in \mathbb{R}^m \mid x \geq 0,\ B x \leq 1\},

    and that for player 1 by

    .. math::

        Q = \{y \in \mathbb{R}^n \mid A y \leq 1,\ y \geq 0\}.

    Here, by translation we represent these in the form

    .. math::

        \hat{P} = \{z \in \mathbb{R}^m \mid D z \leq 1\},

    and

    .. math::

        \hat{Q} = \{w \in \mathbb{R}^n \mid C w \leq 1\},

    where :math:`D` and :math:`C` are (m+n) x m and (m+n) x n matrices,
    respectively. The 2d array of matrix :math:`D` for player 0 (or
    :math:`C` for player 1) is passed as its `points` argument to
    `scipy.spatial.ConvexHull`, which then computes, by the Qhull
    library, convex hull (or facet enumeration). By polar duality, this
    is equivalent to vertex enumeration of the polytope :math:`\hat{P}`,
    where its k-th vertex is obtained by `-equations[k, :-1]/
    equations[k, -1]`, and the indices of the corresponding binding
    inequalities by `labelings[k]`, while the vertex of the original
    polytope :math:`P` can be obtained by `-equations[k, :-1]/
    equations[k, -1] + 1/trans_recip`.

    Parameters
    ----------
    opponent_player : Player
        Instance of Player with one opponent.

    idx : scalar(int), optional(default=0)
        Player index in the normal form game, either 0 or 1.

    qhull_options : str, optional(default=None)
        Options to pass to `scipy.spatial.ConvexHull`. See the `Qhull
        manual <http://www.qhull.org>`_  for details.

    Attributes
    ----------
    ndim : scalar(int)
        Dimension of the polytope.

    hull : scipy.spatial.ConvexHull
        `ConvexHull` instance reprensenting the polar polytope.

    num_vertices : scalar(int)
        Number of the vertices identified by `ConvexHull`.

    equations : ndarray(float, ndim=2)