import matplotlib.pyplot as plt
from io import BytesIO
import imageio
import numpy as np

def generate_bubble_sort_gif(values, output_path):
    """
    Given a list of integer values (e.g. [5,3,8,1]), produce an animated GIF showing
    each comparison + swap step in bubble sort. Save the GIF to output_path.
    """
    if not values:
        # Create a single frame with empty array if no values provided
        fig, ax = plt.subplots()
        ax.bar([], [], color="skyblue")
        ax.set_title("Bubble Sort: No values provided")
        buf = BytesIO()
        plt.savefig(buf, format='png')
        plt.close(fig)
        buf.seek(0)
        imageio.mimsave(output_path, [imageio.imread(buf)], format='GIF', fps=1)
        return output_path

    images = []
    arr = values.copy()
    n = len(arr)
    
    # Always add initial state
    fig, ax = plt.subplots()
    ax.bar(range(len(arr)), arr, color="skyblue")
    ax.set_title("Bubble Sort: Initial State")
    buf = BytesIO()
    plt.savefig(buf, format='png')
    plt.close(fig)
    buf.seek(0)
    images.append(imageio.imread(buf))

    # Perform bubble sort and capture each step
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            # Plot current array state as a bar chart
            fig, ax = plt.subplots()
            ax.bar(range(len(arr)), arr, color="skyblue")
            ax.set_title(f"Bubble Sort: pass {i}, compare {j}")
            buf = BytesIO()
            plt.savefig(buf, format='png')
            plt.close(fig)
            buf.seek(0)
            images.append(imageio.imread(buf))

    # Add final state if no swaps were made
    if len(images) == 1:
        fig, ax = plt.subplots()
        ax.bar(range(len(arr)), arr, color="skyblue")
        ax.set_title("Bubble Sort: Final State")
        buf = BytesIO()
        plt.savefig(buf, format='png')
        plt.close(fig)
        buf.seek(0)
        images.append(imageio.imread(buf))

    # Save as GIF
    imageio.mimsave(output_path, images, format='GIF', fps=1)
    return output_path