import numpy as np


def create_Gaussian_kernel(cutoff_frequency):
    """
        Returns a 2D Gaussian kernel using the specified filter size standard
        deviation and cutoff frequency.

        The kernel should have:
        - shape (k, k) where k = cutoff_frequency * 4 + 1
        - mean = floor(k / 2)
        - standard deviation = cutoff_frequency
        - values that sum to 1

        Args:
        - cutoff_frequency: an int controlling how much low frequency to leave in
          the image.
        Returns:
        - kernel: numpy nd-array of shape (k, k)

        HINT:
        - The 2D Gaussian kernel here can be calculated as the outer product of two
          vectors with values populated from evaluating the 1D Gaussian PDF at each
          corrdinate.
    """
    k = cutoff_frequency * 4 + 1
    mean = np.floor(k / 2)
    std = cutoff_frequency
    gauss_1d = np.zeros((k, 1))

    total = 0
    index = 0
    for x in range(-int(mean), int(mean) + 1):
        x1 = 1 / np.sqrt(2 * np.pi * std ** 2)
        x2 = np.exp(-(x ** 2) / (2 * std ** 2))
        g = x1 * x2
        gauss_1d[index] = g
        index += 1
        total += g
    kernel = np.outer(gauss_1d, gauss_1d) / total ** 2
    return kernel


def my_imfilter(image, filter):
    """
    Apply a filter to an image. Return the filtered image.

    Args
    - image: numpy nd-array of shape (m, n, c)
    - filter: numpy nd-array of shape (k, j)
    Returns
    - filtered_image: numpy nd-array of shape (m, n, c)

    HINTS:
    - You may not use any libraries that do the work for you. Using numpy to work
    with matrices is fine and encouraged. Using OpenCV or similar to do the
    filtering for you is not allowed.
    - I encourage you to try implementing this naively first, just be aware that
    it may take an absurdly long time to run. You will need to get a function
    that takes a reasonable amount of time to run so that the TAs can verify
    your code works.
    """
    m = image.shape[0]
    n = image.shape[1]
    c = image.shape[2]

    padding_height = filter.shape[0] // 2
    padding_width = filter.shape[1] // 2

    # padding manually
    padded_image = np.zeros((m + padding_height * 2, n + padding_width * 2, c))
    padded_image[padding_height:padding_height + m, padding_width:padding_width + n, :] = image

    # convolution
    filtered_image = np.zeros((m, n, c))

    for a in range(0, c):
        for i in range(0, m):
            for j in range(0, n):
                x = np.multiply(padded_image[i: i + filter.shape[0], j:j + filter.shape[1], a], filter)
                filtered_image[i, j, a] = x.sum()

    return filtered_image


def create_hybrid_image(image1, image2, filter):
    """
    Takes two images and a low-pass filter and creates a hybrid image. Returns
    the low frequency content of image1, the high frequency content of image 2,
    and the hybrid image.

    Args
    - image1: numpy nd-array of dim (m, n, c)
    - image2: numpy nd-array of dim (m, n, c)
    - filter: numpy nd-array of dim (x, y)
    Returns
    - low_frequencies: numpy nd-array of shape (m, n, c)
    - high_frequencies: numpy nd-array of shape (m, n, c)
    - hybrid_image: numpy nd-array of shape (m, n, c)

    HINTS:
    - You will use your my_imfilter function in this function.
    - You can get just the high frequency content of an image by removing its low
      frequency content. Think about how to do this in mathematical terms.
    - Don't forget to make sure the pixel values of the hybrid image are between
      0 and 1. This is known as 'clipping'.
    - If you want to use images with different dimensions, you should resize them
      in the notebook code.
    """
    assert image1.shape[0] == image2.shape[0]
    assert image1.shape[1] == image2.shape[1]
    assert image1.shape[2] == image2.shape[2]
    assert filter.shape[0] <= image1.shape[0]
    assert filter.shape[1] <= image1.shape[1]
    assert filter.shape[0] % 2 == 1
    assert filter.shape[1] % 2 == 1

    image1_low = my_imfilter(image1, filter)
    image2_low = my_imfilter(image2, filter)
    image2_high = image2 - image2_low

    hybrid_image = np.clip(image1_low + image2_high, 0, 1)

    low_frequencies = image1_low
    high_frequencies = image2_high

    return low_frequencies, high_frequencies, hybrid_image