import torch
import torch.nn as nn
import torch.utils.data.distributed


class HSIC(nn.Module):
    """Base class for the finite sample estimator of Hilbert-Schmidt Independence Criterion (HSIC)
    ..math:: HSIC (X, Y) := || C_{x, y} ||^2_{HS}, where HSIC (X, Y) = 0 iif X and Y are independent.

    Empirically, we use the finite sample estimator of HSIC (with m observations) by,
    (1) biased estimator (HSIC_0)
        Gretton, Arthur, et al. "Measuring statistical dependence with Hilbert-Schmidt norms." 2005.
        :math: (m - 1)^2 tr KHLH.
        where K_{ij} = kernel_x (x_i, x_j), L_{ij} = kernel_y (y_i, y_j), H = 1 - m^{-1} 1 1 (Hence, K, L, H are m by m matrices).
    (2) unbiased estimator (HSIC_1)
        Song, Le, et al. "Feature selection via dependence maximization." 2012.
        :math: rac{1}{m (m - 3)} igg[ tr (	ilde K 	ilde L) + rac{1^	op 	ilde K 1 1^	op 	ilde L 1}{(m-1)(m-2)} - rac{2}{m-2} 1^	op 	ilde K 	ilde L 1 igg].
        where 	ilde K and 	ilde L are related to K and L by the diagonal entries of 	ilde K_{ij} and 	ilde L_{ij} are set to zero.

    Parameters
    ----------
    sigma_x : float
        the kernel size of the kernel function for X.
    sigma_y : float
        the kernel size of the kernel function for Y.
    algorithm: str ('unbiased' / 'biased')
        the algorithm for the finite sample estimator. 'unbiased' is used for our paper.
    reduction: not used (for compatibility with other losses).
    """

    def __init__(self, sigma_x, sigma_y=None, algorithm='unbiased',
        reduction=None):
        super(HSIC, self).__init__()
        if sigma_y is None:
            sigma_y = sigma_x
        self.sigma_x = sigma_x
        self.sigma_y = sigma_y
        if algorithm == 'biased':
            self.estimator = self.biased_estimator
        elif algorithm == 'unbiased':
            self.estimator = self.unbiased_estimator
        else:
            raise ValueError('invalid estimator: {}'.format(algorithm))

    def _kernel_x(self, X):
        raise NotImplementedError

    def _kernel_y(self, Y):
        raise NotImplementedError

    def biased_estimator(self, input1, input2):
        """Biased estimator of Hilbert-Schmidt Independence Criterion
        Gretton, Arthur, et al. "Measuring statistical dependence with Hilbert-Schmidt norms." 2005.
        """
        K = self._kernel_x(input1)
        L = self._kernel_y(input2)
        KH = K - K.mean(0, keepdim=True)
        LH = L - L.mean(0, keepdim=True)
        N = len(input1)
        return torch.trace(KH @ LH / (N - 1) ** 2)

    def unbiased_estimator(self, input1, input2):
        """Unbiased estimator of Hilbert-Schmidt Independence Criterion
        Song, Le, et al. "Feature selection via dependence maximization." 2012.
        """
        kernel_XX = self._kernel_x(input1)
        kernel_YY = self._kernel_y(input2)
        tK = kernel_XX - torch.diag(kernel_XX)
        tL = kernel_YY - torch.diag(kernel_YY)
        N = len(input1)
        hsic = torch.trace(tK @ tL) + torch.sum(tK) * torch.sum(tL) / (N - 1
            ) / (N - 2) - 2 * torch.sum(tK, 0).dot(torch.sum(tL, 0)) / (N - 2)
        return hsic / (N * (N - 3))

    def forward(self, input1, input2, **kwargs):
        return self.estimator(input1, input2)


class RbfHSIC(HSIC):
    """Radial Basis Function (RBF) kernel HSIC implementation.
    """

    def _kernel(self, X, sigma):
        X = X.view(len(X), -1)
        XX = X @ X.t()
        X_sqnorms = torch.diag(XX)
        X_L2 = -2 * XX + X_sqnorms.unsqueeze(1) + X_sqnorms.unsqueeze(0)
        gamma = 1 / (2 * sigma ** 2)
        kernel_XX = torch.exp(-gamma * X_L2)
        return kernel_XX

    def _kernel_x(self, X):
        return self._kernel(X, self.sigma_x)

    def _kernel_y(self, Y):
        return self._kernel(Y, self.sigma_y)


class MinusRbfHSIC(RbfHSIC):
    """``Minus'' RbfHSIC for the ``max'' optimization.
    """

    def forward(self, input1, input2, **kwargs):
        return -self.estimator(input1, input2)


def get_inputs():
    return [torch.rand([4, 4, 4, 4]), torch.rand([4, 4, 4, 4])]


def get_init_inputs():
    return [[], {'sigma_x': 4}]

import torch
from torch._inductor.select_algorithm import extern_kernels
import triton
import triton.language as tl
from torch._inductor.runtime.triton_heuristics import grid
from torch._C import _cuda_getCurrentRawStream as get_raw_stream
from torch._inductor.runtime.triton_helpers import math as tl_math
import torch.nn as nn
import torch.utils.data.distributed
assert_size_stride = torch._C._dynamo.guards.assert_size_stride
empty_strided_cuda = torch._C._dynamo.guards._empty_strided_cuda
reinterpret_tensor = torch._C._dynamo.guards._reinterpret_tensor


@triton.jit
def triton_per_fused_add_diagonal_copy_exp_mul_sub_sum_0(in_ptr0, out_ptr0,
    out_ptr1, xnumel, rnumel, XBLOCK: tl.constexpr):
    RBLOCK: tl.constexpr = 16
    xoffset = tl.program_id(0) * XBLOCK
    xoffset + tl.arange(0, XBLOCK)[:, None]
    tl.full([XBLOCK, RBLOCK], True, tl.int1)
    rindex = tl.arange(0, RBLOCK)[None, :]
    tl.full([XBLOCK, RBLOCK], True, tl.int1)
    r2 = rindex
    r1 = rindex // 4
    r0 = rindex % 4
    tmp0 = tl.load(in_ptr0 + r2, None)
    tmp3 = tl.load(in_ptr0 + 5 * r1, None, eviction_policy='evict_last')
    tmp5 = tl.load(in_ptr0 + 5 * r0, None, eviction_policy='evict_last')
    tmp1 = -2.0
    tmp2 = tmp0 * tmp1
    tmp4 = tmp2 + tmp3
    tmp6 = tmp4 + tmp5
    tmp7 = -0.03125
    tmp8 = tmp6 * tmp7
    tmp9 = tl_math.exp(tmp8)
    tmp10 = tmp5 * tmp1
    tmp11 = tmp10 + tmp5
    tmp12 = tmp11 + tmp5
    tmp13 = tmp12 * tmp7
    tmp14 = tl_math.exp(tmp13)
    tmp15 = tmp9 - tmp14
    tmp16 = tl.broadcast_to(tmp15, [XBLOCK, RBLOCK])
    tmp18 = tl.sum(tmp16, 1)[:, None]
    tl.store(out_ptr0 + tl.broadcast_to(r2, [XBLOCK, RBLOCK]), tmp15, None)
    tl.store(out_ptr1 + tl.full([XBLOCK, 1], 0, tl.int32), tmp18, None)


@triton.jit
def triton_per_fused_add_div_dot_mul_neg_sub_sum_trace_1(in_out_ptr0,
    in_ptr0, in_ptr1, in_ptr2, in_ptr3, in_ptr4, xnumel, rnumel, XBLOCK: tl
    .constexpr):
    RBLOCK: tl.constexpr = 4
    xoffset = tl.program_id(0) * XBLOCK
    xoffset + tl.arange(0, XBLOCK)[:, None]
    tl.full([XBLOCK, RBLOCK], True, tl.int1)
    rindex = tl.arange(0, RBLOCK)[None, :]
    tl.full([XBLOCK, RBLOCK], True, tl.int1)
    r0 = rindex
    tmp0 = tl.load(in_ptr0 + 5 * r0, None, eviction_policy='evict_last')
    tmp4 = tl.load(in_ptr1 + r0, None)
    tmp5 = tl.load(in_ptr1 + (4 + r0), None)
    tmp7 = tl.load(in_ptr1 + (8 + r0), None)
    tmp9 = tl.load(in_ptr1 + (12 + r0), None)
    tmp11 = tl.load(in_ptr2 + r0, None)
    tmp12 = tl.load(in_ptr2 + (4 + r0), None)
    tmp14 = tl.load(in_ptr2 + (8 + r0), None)
    tmp16 = tl.load(in_ptr2 + (12 + r0), None)
    tmp22 = tl.load(in_ptr3 + 0)
    tmp23 = tl.broadcast_to(tmp22, [XBLOCK, 1])
    tmp24 = tl.load(in_ptr4 + 0)
    tmp25 = tl.broadcast_to(tmp24, [XBLOCK, 1])
    tmp1 = tl.broadcast_to(tmp0, [XBLOCK, RBLOCK])
    tmp3 = tl.sum(tmp1, 1)[:, None]
    tmp6 = tmp4 + tmp5
    tmp8 = tmp6 + tmp7
    tmp10 = tmp8 + tmp9
    tmp13 = tmp11 + tmp12
    tmp15 = tmp13 + tmp14
    tmp17 = tmp15 + tmp16
    tmp18 = tmp10 * tmp17
    tmp19 = tl.broadcast_to(tmp18, [XBLOCK, RBLOCK])
    tmp21 = tl.sum(tmp19, 1)[:, None]
    tmp26 = tmp23 * tmp25
    tmp27 = 0.3333333333333333
    tmp28 = tmp26 * tmp27
    tmp29 = 0.5
    tmp30 = tmp28 * tmp29
    tmp31 = tmp3 + tmp30
    tmp32 = 2.0
    tmp33 = tmp21 * tmp32
    tmp34 = tmp33 * tmp29
    tmp35 = tmp31 - tmp34
    tmp36 = 0.25
    tmp37 = tmp35 * tmp36
    tmp38 = -tmp37
    tl.debug_barrier()
    tl.store(in_out_ptr0 + tl.full([XBLOCK, 1], 0, tl.int32), tmp38, None)


def call(args):
    arg0_1, arg1_1 = args
    args.clear()
    assert_size_stride(arg0_1, (4, 4, 4, 4), (64, 16, 4, 1))
    assert_size_stride(arg1_1, (4, 4, 4, 4), (64, 16, 4, 1))
    with torch.cuda._DeviceGuard(0):
        torch.cuda.set_device(0)
        buf0 = empty_strided_cuda((4, 4), (4, 1), torch.float32)
        extern_kernels.mm(reinterpret_tensor(arg0_1, (4, 64), (64, 1), 0),
            reinterpret_tensor(arg0_1, (64, 4), (1, 64), 0), out=buf0)
        del arg0_1
        buf1 = empty_strided_cuda((4, 4), (4, 1), torch.float32)
        buf6 = empty_strided_cuda((), (), torch.float32)
        get_raw_stream(0)
        triton_per_fused_add_diagonal_copy_exp_mul_sub_sum_0[grid(1)](buf0,
            buf1, buf6, 1, 16, XBLOCK=1, num_warps=2, num_stages=1)
        buf2 = buf0
        del buf0
        extern_kernels.mm(reinterpret_tensor(arg1_1, (4, 64), (64, 1), 0),
            reinterpret_tensor(arg1_1, (64, 4), (1, 64), 0), out=buf2)
        del arg1_1
        buf3 = empty_strided_cuda((4, 4), (4, 1), torch.float32)
        buf7 = empty_strided_cuda((), (), torch.float32)
        triton_per_fused_add_diagonal_copy_exp_mul_sub_sum_0[grid(1)](buf2,
            buf3, buf7, 1, 16, XBLOCK=1, num_warps=2, num_stages=1)
        buf4 = buf2
        del buf2
        extern_kernels.mm(buf1, buf3, out=buf4)
        buf5 = empty_strided_cuda((), (), torch.float32)
        buf9 = buf5
        del buf5
        triton_per_fused_add_div_dot_mul_neg_sub_sum_trace_1[grid(1)](buf9,
            buf4, buf1, buf3, buf6, buf7, 1, 4, XBLOCK=1, num_warps=2,
            num_stages=1)
        del buf1
        del buf3
        del buf4
        del buf6
        del buf7
    return buf9,


class HSIC(nn.Module):
    """Base class for the finite sample estimator of Hilbert-Schmidt Independence Criterion (HSIC)
    ..math:: HSIC (X, Y) := || C_{x, y} ||^2_{HS}, where HSIC (X, Y) = 0 iif X and Y are independent.

    Empirically, we use the finite sample estimator of HSIC (with m observations) by,
    (1) biased estimator (HSIC_0)
        Gretton, Arthur, et al. "Measuring statistical dependence with Hilbert-Schmidt norms." 2005.
        :math: (m - 1)^2 tr KHLH.
        where K_{ij} = kernel_x (x_i, x_j), L_{ij} = kernel_y (y_i, y_j), H = 1 - m^{-1} 1 1 (Hence, K, L, H are m by m matrices).
    (2) unbiased estimator (HSIC_1)
        Song, Le, et al. "Feature selection via dependence maximization." 2012.
        :math: rac{1}{m (m - 3)} igg[ tr (	ilde K 	ilde L) + rac{1^	op 	ilde K 1 1^	op 	ilde L 1}{(m-1)(m-2)} - rac{2}{m-2} 1^	op 	ilde K 	ilde L 1 igg].
        where 	ilde K and 	ilde L are related to K and L by the diagonal entries of 	ilde K_{ij} and 	ilde L_{ij} are set to zero.

    Parameters
    ----------
    sigma_x : float
        the kernel size of the kernel function for X.
    sigma_y : float
        the kernel size of the kernel function for Y.
    algorithm: str ('unbiased' / 'biased')
        the algorithm for the finite sample estimator. 'unbiased' is used for our paper.
    reduction: not used (for compatibility with other losses).
    """

    def __init__(self, sigma_x, sigma_y=None, algorithm='unbiased',
        reduction=None):
        super(HSIC, self).__init__()
        if sigma_y is None:
            sigma_y = sigma_x
        self.sigma_x = sigma_x
        self.sigma_y = sigma_y
        if algorithm == 'biased':
            self.estimator = self.biased_estimator
        elif algorithm == 'unbiased':
            self.estimator = self.unbiased_estimator
        else:
            raise ValueError('invalid estimator: {}'.format(algorithm))

    def _kernel_x(self, X):
        raise NotImplementedError

    def _kernel_y(self, Y):
        raise NotImplementedError

    def biased_estimator(self, input1, input2):
        """Biased estimator of Hilbert-Schmidt Independence Criterion
        Gretton, Arthur, et al. "Measuring statistical dependence with Hilbert-Schmidt norms." 2005.
        """
        K = self._kernel_x(input1)
        L = self._kernel_y(input2)
        KH = K - K.mean(0, keepdim=True)
        LH = L - L.mean(0, keepdim=True)
        N = len(input1)
        return torch.trace(KH @ LH / (N - 1) ** 2)

    def unbiased_estimator(self, input1, input2):
        """Unbiased estimator of Hilbert-Schmidt Independence Criterion
        Song, Le, et al. "Feature selection via dependence maximization." 2012.
        """
        kernel_XX = self._kernel_x(input1)
        kernel_YY = self._kernel_y(input2)
        tK = kernel_XX - torch.diag(kernel_XX)
        tL = kernel_YY - torch.diag(kernel_YY)
        N = len(input1)
        hsic = torch.trace(tK @ tL) + torch.sum(tK) * torch.sum(tL) / (N - 1
            ) / (N - 2) - 2 * torch.sum(tK, 0).dot(torch.sum(tL, 0)) / (N - 2)
        return hsic / (N * (N - 3))

    def forward(self, input1, input2, **kwargs):
        return self.estimator(input1, input2)


class RbfHSIC(HSIC):
    """Radial Basis Function (RBF) kernel HSIC implementation.
    """

    def _kernel(self, X, sigma):
        X = X.view(len(X), -1)
        XX = X @ X.t()
        X_sqnorms = torch.diag(XX)
        X_L2 = -2 * XX + X_sqnorms.unsqueeze(1) + X_sqnorms.unsqueeze(0)
        gamma = 1 / (2 * sigma ** 2)
        kernel_XX = torch.exp(-gamma * X_L2)
        return kernel_XX

    def _kernel_x(self, X):
        return self._kernel(X, self.sigma_x)

    def _kernel_y(self, Y):
        return self._kernel(Y, self.sigma_y)


class MinusRbfHSICNew(RbfHSIC):
    """``Minus'' RbfHSIC for the ``max'' optimization.
    """

    def forward(self, input_0, input_1):
        arg0_1 = input_0
        arg1_1 = input_1
        output = call([arg0_1, arg1_1])
        return output[0]
