import numpy
import six

import cupy
from cupy import core
from cupy import internal

from cupy.linalg.solve import inv
from cupy.util import collections_abc


matmul = core.matmul


def dot(a, b, out=None):
    """Returns a dot product of two arrays.

    For arrays with more than one axis, it computes the dot product along the
    last axis of ``a`` and the second-to-last axis of ``b``. This is just a
    matrix product if the both arrays are 2-D. For 1-D arrays, it uses their
    unique axis as an axis to take dot product over.

    Args:
        a (cupy.ndarray): The left argument.
        b (cupy.ndarray): The right argument.
        out (cupy.ndarray): Output array.

    Returns:
        cupy.ndarray: The dot product of ``a`` and ``b``.

    .. seealso:: :func:`numpy.dot`

    """
    # TODO(okuta): check type
    return a.dot(b, out)


def vdot(a, b):
    """Returns the dot product of two vectors.

    The input arrays are flattened into 1-D vectors and then it performs inner
    product of these vectors.

    Args:
        a (cupy.ndarray): The first argument.
        b (cupy.ndarray): The second argument.

    Returns:
        cupy.ndarray: Zero-dimensional array of the dot product result.

    .. seealso:: :func:`numpy.vdot`

    """
    if a.size != b.size:
        raise ValueError('Axis dimension mismatch')
    if a.dtype.kind == 'c':
        a = a.conj()

    return core.tensordot_core(a, b, None, 1, 1, a.size, ())


def inner(a, b):
    """Returns the inner product of two arrays.

    It uses the last axis of each argument to take sum product.

    Args:
        a (cupy.ndarray): The first argument.
        b (cupy.ndarray): The second argument.

    Returns:
        cupy.ndarray: The inner product of ``a`` and ``b``.

    .. seealso:: :func:`numpy.inner`

    """
    a_ndim = a.ndim
    b_ndim = b.ndim
    if a_ndim == 0 or b_ndim == 0:
        return cupy.multiply(a, b)

    a_axis = a_ndim - 1
    b_axis = b_ndim - 1

    if a.shape[-1] != b.shape[-1]:
        raise ValueError('Axis dimension mismatch')

    if a_axis:
        a = cupy.rollaxis(a, a_axis, 0)
    if b_axis:
        b = cupy.rollaxis(b, b_axis, 0)

    ret_shape = a.shape[1:] + b.shape[1:]

    k = a.shape[0]
    n = a.size // k
    m = b.size // k

    return core.tensordot_core(a, b, None, n, m, k, ret_shape)


def outer(a, b, out=None):
    """Returns the outer product of two vectors.

    The input arrays are flattened into 1-D vectors and then it performs outer
    product of these vectors.

    Args:
        a (cupy.ndarray): The first argument.
        b (cupy.ndarray): The second argument.
        out (cupy.ndarray): Output array.

    Returns:
        cupy.ndarray: 2-D array of the outer product of ``a`` and ``b``.

    .. seealso:: :func:`numpy.outer`

    """
    n = a.size
    m = b.size
    ret_shape = (n, m)

    if out is None:
        return core.tensordot_core(a, b, None, n, m, 1, ret_shape)

    if out.size != n * m:
        raise ValueError('Output array has an invalid size')
    if out.flags.c_contiguous:
        return core.tensordot_core(a, b, out, n, m, 1, ret_shape)
    else:
        out[:] = core.tensordot_core(a, b, None, n, m, 1, ret_shape)
        return out


def tensordot(a, b, axes=2):
    """Returns the tensor dot product of two arrays along specified axes.

    This is equivalent to compute dot product along the specified axes which
    are treated as one axis by reshaping.

    Args:
        a (cupy.ndarray): The first argument.
        b (cupy.ndarray): The second argument.
        axes:
            - If it is an integer, then ``axes`` axes at the last of ``a`` and
              the first of ``b`` are used.
            - If it is a pair of sequences of integers, then these two
              sequences specify the list of axes for ``a`` and ``b``. The
              corresponding axes are paired for sum-product.

    Returns:
        cupy.ndarray: The tensor dot product of ``a`` and ``b`` along the
        axes specified by ``axes``.

    .. seealso:: :func:`numpy.tensordot`

    """
    a_ndim = a.ndim
    b_ndim = b.ndim
    if a_ndim == 0 or b_ndim == 0:
        if axes != 0 and axes != ((), ()):
            raise ValueError('An input is zero-dim while axes has dimensions')
        return cupy.multiply(a, b)

    if isinstance(axes, collections_abc.Sequence):
        if len(axes) != 2:
            raise ValueError('Axes must consist of two arrays.')
        a_axes, b_axes = axes
        if numpy.isscalar(a_axes):
            a_axes = a_axes,
        if numpy.isscalar(b_axes):
            b_axes = b_axes,
    else:
        a_axes = tuple(six.moves.range(a_ndim - axes, a_ndim))
        b_axes = tuple(six.moves.range(axes))

    sum_ndim = len(a_axes)
    if sum_ndim != len(b_axes):
        raise ValueError('Axes length mismatch')

    for a_axis, b_axis in zip(a_axes, b_axes):
        if a.shape[a_axis] != b.shape[b_axis]:
            raise ValueError('Axis dimension mismatch')

    # Make the axes non-negative
    a = _move_axes_to_head(a, [axis % a_ndim for axis in a_axes])
    b = _move_axes_to_head(b, [axis % b_ndim for axis in b_axes])

    ret_shape = a.shape[sum_ndim:] + b.shape[sum_ndim:]

    k = internal.prod(a.shape[:sum_ndim])
    # Avoid division by zero: core.tensordot_core returns zeros without
    # checking n, m consistency, thus allowing 0-length dimensions to work
    n = a.size // k if k != 0 else 0
    m = b.size // k if k != 0 else 0

    return core.tensordot_core(a, b, None, n, m, k, ret_shape)


def matrix_power(M, n):
    """Raise a square matrix to the (integer) power `n`.

    Args:
        M (~cupy.ndarray): Matrix to raise by power n.
        n (~int): Power to raise matrix to.

    Returns:
        ~cupy.ndarray: Output array.

    .. note:: M must be of dtype `float32` or `float64`.

    ..seealso:: :func:`numpy.linalg.matrix_power`
    """
    if M.ndim != 2 or M.shape[0] != M.shape[1]:
        raise ValueError('input must be a square array')
    if not isinstance(n, six.integer_types):
        raise TypeError('exponent must be an integer')

    if n == 0:
        return cupy.identity(M.shape[0], dtype=M.dtype)
    elif n < 0:
        M = inv(M)
        n *= -1

    # short-cuts
    if n <= 3:
        if n == 1:
            return M
        elif n == 2:
            return cupy.matmul(M, M)
        else:
            return cupy.matmul(cupy.matmul(M, M), M)

    # binary decomposition to reduce the number of Matrix
    # multiplications for n > 3.
    result, Z = None, None
    for b in cupy.binary_repr(n)[::-1]:
        Z = M if Z is None else cupy.matmul(Z, Z)
        if b == '1':
            result = Z if result is None else cupy.matmul(result, Z)

    return result


def kron(a, b):
    """Returns the kronecker product of two arrays.

    Args:
        a (~cupy.ndarray): The first argument.
        b (~cupy.ndarray): The second argument.

    Returns:
        ~cupy.ndarray: Output array.

    .. seealso:: :func:`numpy.kron`

    """
    a_ndim = a.ndim
    b_ndim = b.ndim
    if a_ndim == 0 or b_ndim == 0:
        return cupy.multiply(a, b)

    ndim = b_ndim
    a_shape = a.shape
    b_shape = b.shape
    if a_ndim != b_ndim:
        if b_ndim > a_ndim:
            a_shape = (1,) * (b_ndim - a_ndim) + a_shape
        else:
            b_shape = (1,) * (a_ndim - b_ndim) + b_shape
            ndim = a_ndim

    axis = ndim - 1
    out = core.tensordot_core(a, b, None, a.size, b.size, 1, a_shape + b_shape)
    for _ in six.moves.range(ndim):
        out = core.concatenate_method(out, axis=axis)

    return out


def _move_axes_to_head(a, axes):
    # This function moves the axes of ``s`` to the head of the shape.
    for idx, axis in enumerate(axes):
        if idx != axis:
            break
    else:
        return a

    return a.transpose(
        axes + [i for i in six.moves.range(a.ndim) if i not in axes])

[((59, 11, 59, 60), 'cupy.core.tensordot_core', 'core.tensordot_core', ({(59, 31, 59, 32): 'a', (59, 34, 59, 35): 'b', (59, 37, 59, 41): 'None', (59, 43, 59, 44): '(1)', (59, 46, 59, 47): '(1)', (59, 49, 59, 55): 'a.size', (59, 57, 59, 59): '()'}, {}), '(a, b, None, 1, 1, a.size, ())', False, 'from cupy import core\n'), ((99, 11, 99, 62), 'cupy.core.tensordot_core', 'core.tensordot_core', ({(99, 31, 99, 32): 'a', (99, 34, 99, 35): 'b', (99, 37, 99, 41): 'None', (99, 43, 99, 44): 'n', (99, 46, 99, 47): 'm', (99, 49, 99, 50): 'k', (99, 52, 99, 61): 'ret_shape'}, {}), '(a, b, None, n, m, k, ret_shape)', False, 'from cupy import core\n'), ((191, 8, 191, 41), 'cupy.internal.prod', 'internal.prod', ({(191, 22, 191, 40): 'a.shape[:sum_ndim]'}, {}), '(a.shape[:sum_ndim])', False, 'from cupy import internal\n'), ((197, 11, 197, 62), 'cupy.core.tensordot_core', 'core.tensordot_core', ({(197, 31, 197, 32): 'a', (197, 34, 197, 35): 'b', (197, 37, 197, 41): 'None', (197, 43, 197, 44): 'n', (197, 46, 197, 47): 'm', (197, 49, 197, 50): 'k', (197, 52, 197, 61): 'ret_shape'}, {}), '(a, b, None, n, m, k, ret_shape)', False, 'from cupy import core\n'), ((274, 10, 274, 79), 'cupy.core.tensordot_core', 'core.tensordot_core', ({(274, 30, 274, 31): 'a', (274, 33, 274, 34): 'b', (274, 36, 274, 40): 'None', (274, 42, 274, 48): 'a.size', (274, 50, 274, 56): 'b.size', (274, 58, 274, 59): '1', (274, 61, 274, 78): 'a_shape + b_shape'}, {}), '(a, b, None, a.size, b.size, 1, a_shape + b_shape)', False, 'from cupy import core\n'), ((275, 13, 275, 34), 'six.moves.range', 'six.moves.range', ({(275, 29, 275, 33): 'ndim'}, {}), '(ndim)', False, 'import six\n'), ((80, 15, 80, 34), 'cupy.multiply', 'cupy.multiply', ({(80, 29, 80, 30): 'a', (80, 32, 80, 33): 'b'}, {}), '(a, b)', False, 'import cupy\n'), ((89, 12, 89, 39), 'cupy.rollaxis', 'cupy.rollaxis', ({(89, 26, 89, 27): 'a', (89, 29, 89, 35): 'a_axis', (89, 37, 89, 38): '0'}, {}), '(a, a_axis, 0)', False, 'import cupy\n'), ((91, 12, 91, 39), 'cupy.rollaxis', 'cupy.rollaxis', ({(91, 26, 91, 27): 'b', (91, 29, 91, 35): 'b_axis', (91, 37, 91, 38): '0'}, {}), '(b, b_axis, 0)', False, 'import cupy\n'), ((124, 15, 124, 66), 'cupy.core.tensordot_core', 'core.tensordot_core', ({(124, 35, 124, 36): 'a', (124, 38, 124, 39): 'b', (124, 41, 124, 45): 'None', (124, 47, 124, 48): 'n', (124, 50, 124, 51): 'm', (124, 53, 124, 54): '(1)', (124, 56, 124, 65): 'ret_shape'}, {}), '(a, b, None, n, m, 1, ret_shape)', False, 'from cupy import core\n'), ((129, 15, 129, 65), 'cupy.core.tensordot_core', 'core.tensordot_core', ({(129, 35, 129, 36): 'a', (129, 38, 129, 39): 'b', (129, 41, 129, 44): 'out', (129, 46, 129, 47): 'n', (129, 49, 129, 50): 'm', (129, 52, 129, 53): '(1)', (129, 55, 129, 64): 'ret_shape'}, {}), '(a, b, out, n, m, 1, ret_shape)', False, 'from cupy import core\n'), ((131, 17, 131, 68), 'cupy.core.tensordot_core', 'core.tensordot_core', ({(131, 37, 131, 38): 'a', (131, 40, 131, 41): 'b', (131, 43, 131, 47): 'None', (131, 49, 131, 50): 'n', (131, 52, 131, 53): 'm', (131, 55, 131, 56): '1', (131, 58, 131, 67): 'ret_shape'}, {}), '(a, b, None, n, m, 1, ret_shape)', False, 'from cupy import core\n'), ((163, 15, 163, 34), 'cupy.multiply', 'cupy.multiply', ({(163, 29, 163, 30): 'a', (163, 32, 163, 33): 'b'}, {}), '(a, b)', False, 'import cupy\n'), ((169, 11, 169, 33), 'numpy.isscalar', 'numpy.isscalar', ({(169, 26, 169, 32): 'a_axes'}, {}), '(a_axes)', False, 'import numpy\n'), ((171, 11, 171, 33), 'numpy.isscalar', 'numpy.isscalar', ({(171, 26, 171, 32): 'b_axes'}, {}), '(b_axes)', False, 'import numpy\n'), ((220, 15, 220, 55), 'cupy.identity', 'cupy.identity', (), '', False, 'import cupy\n'), ((237, 13, 237, 32), 'cupy.binary_repr', 'cupy.binary_repr', ({(237, 30, 237, 31): 'n'}, {}), '(n)', False, 'import cupy\n'), ((261, 15, 261, 34), 'cupy.multiply', 'cupy.multiply', ({(261, 29, 261, 30): 'a', (261, 32, 261, 33): 'b'}, {}), '(a, b)', False, 'import cupy\n'), ((276, 14, 276, 53), 'cupy.core.concatenate_method', 'core.concatenate_method', (), '', False, 'from cupy import core\n'), ((174, 23, 174, 61), 'six.moves.range', 'six.moves.range', ({(174, 39, 174, 52): 'a_ndim - axes', (174, 54, 174, 60): 'a_ndim'}, {}), '(a_ndim - axes, a_ndim)', False, 'import six\n'), ((175, 23, 175, 44), 'six.moves.range', 'six.moves.range', ({(175, 39, 175, 43): 'axes'}, {}), '(axes)', False, 'import six\n'), ((222, 12, 222, 18), 'cupy.linalg.solve.inv', 'inv', ({(222, 16, 222, 17): 'M'}, {}), '(M)', False, 'from cupy.linalg.solve import inv\n'), ((238, 32, 238, 49), 'cupy.matmul', 'cupy.matmul', ({(238, 44, 238, 45): 'Z', (238, 47, 238, 48): 'Z'}, {}), '(Z, Z)', False, 'import cupy\n'), ((230, 19, 230, 36), 'cupy.matmul', 'cupy.matmul', ({(230, 31, 230, 32): 'M', (230, 34, 230, 35): 'M'}, {}), '(M, M)', False, 'import cupy\n'), ((240, 46, 240, 68), 'cupy.matmul', 'cupy.matmul', ({(240, 58, 240, 64): 'result', (240, 66, 240, 67): 'Z'}, {}), '(result, Z)', False, 'import cupy\n'), ((232, 31, 232, 48), 'cupy.matmul', 'cupy.matmul', ({(232, 43, 232, 44): 'M', (232, 46, 232, 47): 'M'}, {}), '(M, M)', False, 'import cupy\n'), ((290, 27, 290, 50), 'six.moves.range', 'six.moves.range', ({(290, 43, 290, 49): 'a.ndim'}, {}), '(a.ndim)', False, 'import six\n')]