import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class FibonacciHeapExperiments {
    // Class to hold experiment results
    public static class ExperimentResult {
        long runningTime;
        int finalHeapSize;
        int totalLinks;
        int totalCuts;
        int finalTrees;

        public ExperimentResult(long time, int size, int links, int cuts, int trees) {
            this.runningTime = time;
            this.finalHeapSize = size;
            this.totalLinks = links;
            this.totalCuts = cuts;
            this.finalTrees = trees;
        }
    }

    // Generate array of integers 1 to n in random order
    private static ArrayList<Integer> getRandomArray(int n) {
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            arr.add(i);
        }
        Collections.shuffle(arr, new Random()); // Fixed seed for reproducibility
        return arr;
    }

    // First experiment: Insert n items randomly and delete minimum
    public static ExperimentResult experiment1(int n) {
        FibonacciHeap heap = new FibonacciHeap();
        ArrayList<Integer> randomArray = getRandomArray(n);

        long startTime = System.nanoTime();

        // Insert all numbers
        for (int num : randomArray) {
            heap.insert(num, String.valueOf(num));
        }

        // Delete minimum once
        heap.deleteMin();

        long endTime = System.nanoTime();

        return new ExperimentResult(
                (endTime - startTime) / 1_000_000,
                heap.size(),
                heap.totalLinks(),
                heap.totalCuts(),
                heap.numTrees()
        );
    }

    // Second experiment: Insert n items randomly and delete minimum n/2 times
    public static ExperimentResult experiment2(int n) {
        FibonacciHeap heap = new FibonacciHeap();
        ArrayList<Integer> randomArray = getRandomArray(n);

        long startTime = System.nanoTime();

        // Insert all numbers
        for (int num : randomArray) {
            heap.insert(num, String.valueOf(num));
        }

        // Delete minimum n/2 times
        for (int i = 0; i < n/2; i++) {
            heap.deleteMin();
        }

        long endTime = System.nanoTime();

        return new ExperimentResult(
                (endTime - startTime) / 1_000_000,
                heap.size(),
                heap.totalLinks(),
                heap.totalCuts(),
                heap.numTrees()
        );
    }

    // Third experiment: Insert n items randomly, delete min, then delete by index until 31 items remain
    public static ExperimentResult experiment3(int n) {
        FibonacciHeap heap = new FibonacciHeap();
        ArrayList<Integer> randomArray = getRandomArray(n);

        // Create sorted array of nodes, indexed by their values
        FibonacciHeap.HeapNode[] sortedNodes = new FibonacciHeap.HeapNode[n + 1];

        long startTime = System.nanoTime();

        // Insert all numbers randomly but keep track in sorted order
        for (int num : randomArray) {
            FibonacciHeap.HeapNode node = heap.insert(num, String.valueOf(num));
            sortedNodes[num] = node;
        }

        // Delete minimum once
        heap.deleteMin();

        // Delete elements until 31 remain, using index-based deletion
        int currentSize = heap.size();
        while (currentSize > 31) {
            int indexToDelete = currentSize - 1;  // Start from last index
            if (sortedNodes[indexToDelete] != null) {
                heap.delete(sortedNodes[indexToDelete]);
                sortedNodes[indexToDelete] = null;
                currentSize--;
            }
        }

        long endTime = System.nanoTime();

        return new ExperimentResult(
                (endTime - startTime) / 1_000_000,
                heap.size(),
                heap.totalLinks(),
                heap.totalCuts(),
                heap.numTrees()
        );
    }

    // Run multiple trials of an experiment and average the results
    public static ExperimentResult runTrials(int n, int numTrials, int experimentNum) {
        long totalTime = 0;
        int totalSize = 0;
        int totalLinks = 0;
        int totalCuts = 0;
        int totalTrees = 0;

        for (int i = 0; i < numTrials; i++) {
            ExperimentResult result;
            switch (experimentNum) {
                case 1:
                    result = experiment1(n);
                    break;
                case 2:
                    result = experiment2(n);
                    break;
                case 3:
                    result = experiment3(n);
                    break;
                default:
                    throw new IllegalArgumentException("Invalid experiment number");
            }

            totalTime += result.runningTime;
            totalSize += result.finalHeapSize;
            totalLinks += result.totalLinks;
            totalCuts += result.totalCuts;
            totalTrees += result.finalTrees;
        }

        return new ExperimentResult(
                totalTime / numTrials,
                totalSize / numTrials,
                totalLinks / numTrials,
                totalCuts / numTrials,
                totalTrees / numTrials
        );
    }

    // Print results in table format
    private static void printTableResults(int experimentNumber, int m) {
        System.out.println("\nExperiment " + experimentNumber + ":");
        System.out.println("┌────┬──────────┬────────────┬───────────┬────────────┬────────────┬───────────┐");
        System.out.println("│ i  │    n     │ Time (ms)  │Final Size │Total Links │Total Cuts  │Final Trees│");
        System.out.println("├────┼──────────┼────────────┼───────────┼────────────┼────────────┼───────────┤");

        for (int i = 1; i <= m; i++) {
            int n = (int) Math.pow(3, i + 7) - 1;
            ExperimentResult result = runTrials(n, 20, experimentNumber);

            System.out.printf("│ %-2d │ %-8d │ %-10d │ %-9d │ %-10d │ %-10d │ %-9d │%n",
                    i,
                    n,
                    result.runningTime,
                    result.finalHeapSize,
                    result.totalLinks,
                    result.totalCuts,
                    result.finalTrees
            );
        }
        System.out.println("└────┴──────────┴────────────┴───────────┴────────────┴────────────┴───────────┘");
    }

    // Main method to run all experiments
    public static void main(String[] args) {
        System.out.println("Running all experiments with 20 trials each...");

        for (int exp = 1; exp <= 3; exp++) {
            printTableResults(exp, 5);  // Run for i = 1 to 5
        }
    }
}