#include <stdio.h>
#include <stdlib.h>

#ifdef _WIN32
#include <windows.h> // For Windows API functions
#else
#include <unistd.h> // For usleep on Unix
#endif

// ANSI escape codes for colors
#define RESET_COLOR "\x1b[0m"
#define HIGHLIGHT "\x1b[44m"  // Blue background
#define GREY "\x1b[90m"       // Grey text

// Global sleep time definition (in milliseconds)
#define SLEEP_TIME_MS 2000

void clearScreen() {
    #ifdef _WIN32
    system("cls");
    #else
    system("clear");
    #endif
}

void sleepMs(int milliseconds) {
    #ifdef _WIN32
    Sleep(milliseconds);
    #else
    usleep(milliseconds * 1000); // convert to microseconds
    #endif
}

void printAnnotation(int position, const char* annotation, int listSize) {
    for (int i = 0; i < position * 4 + 11; i++) { // Adjust position for correct alignment
        printf(" ");
    }
    printf("%s\n", annotation); // Print the annotation (Fir, Mid, Las)
}

void printAnnotations(int listSize, int first, int last, int middle) {
    if (first >= 0) printAnnotation(first, "Fir", listSize);
    if (middle >= 0) printAnnotation(middle, "Mid", listSize);
    if (last >= 0) printAnnotation(last, "Las", listSize);
}

void printArray(int list[], int listSize, int first, int last, int middle, int initialDisplay) {
    printf("+");
    for (int i = 0; i < listSize * 4 + 9; i++) { // Adjust border size based on array size
        printf("-");
    }
    printf("+\n");

    printf("|Elements |");
    for (int i = 0; i < listSize; i++) {
        if (!initialDisplay && (i < first || i > last)) {
            printf(GREY); // Grey out discarded elements during search
        } else if (i == first || i == last || i == middle) {
            printf(HIGHLIGHT); // Highlight the first, last, and middle elements during search
        }
        printf(" %2d" RESET_COLOR "|", list[i]);
    }
    printf("\n");

    printf("+");
    for (int i = 0; i < listSize * 4 + 9; i++) { // Adjust border size based on array size
        printf("-");
    }
    printf("+\n");

    printf("|Index    |");
    for (int i = 0; i < listSize; i++) {
        if (!initialDisplay && (i < first || i > last)) {
            printf(GREY); // Grey out discarded indexes during search
        } else if (i == first || i == last || i == middle) {
            printf(HIGHLIGHT); // Highlight the first, last, and middle indexes during search
        }
        printf(" %2d" RESET_COLOR "|", i);
    }
    printf("\n");

    printf("+");
    for (int i = 0; i < listSize * 4 + 9; i++) { // Adjust border size based on array size
        printf("-");
    }
    printf("+\n");
}

void displayInitialArray(int list[], int listSize) {
    printf("\nInitial array:\n");
    printArray(list, listSize, -1, -1, -1, 1); // Display all elements normally
    printf("\nPress Enter to start the search...");
    getchar(); // Wait for user to press enter to continue
}

int binarySearch(int key, int list[], int listSize, int stepThrough, int *comparisonCount) {
    int first = 0;
    int last = listSize - 1;
    int middle = first + (last - first) / 2;

    while (first <= last) {
        (*comparisonCount)++; // Increment the comparison count
        clearScreen();
        printArray(list, listSize, first, last, middle, 0);
        printAnnotations(listSize, first, last, middle); // Print the annotations

        if (key == list[middle]) {
            printf("\nKey %d found at index %d.\n", key, middle);
            return middle;
        } else if (key < list[middle]) {
            printf("\nKey %d is less than %d, searching lower half.\n", key, list[middle]);
            last = middle - 1;
        } else {
            printf("\nKey %d is greater than %d, searching upper half.\n", key, list[middle]);
            first = middle + 1;
        }
        middle = first + (last - first) / 2;

        if (stepThrough) {
            printf("Press Enter to continue...");
            getchar(); // Wait for user to press enter to continue to the next step
        } else {
            sleepMs(SLEEP_TIME_MS);
        }
    }

    printf("\nKey %d not found.\n", key);
    return -1;
}

int main() {
    // Modify the array here for different demonstrations
    //int list[10] = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50};
    int list[] = {3, 6, 8, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51};
    int listSize = sizeof(list) / sizeof(list[0]); // Calculate the size of the array
    int key, stepThrough, comparisonCount;

    printf("Enter 1 for step through, 0 for full animation: ");
    scanf("%d", &stepThrough);
    getchar(); // Consume the newline character left in the input buffer by scanf

    displayInitialArray(list, listSize); // Display the array before starting the search

    printf("\nEnter a search key (-1 to exit): ");
    scanf("%d", &key);
    while (key != -1) {
        getchar(); // Consume the newline character left in the input buffer by scanf
        comparisonCount = 0; // Reset comparison count for each search
        binarySearch(key, list, listSize, stepThrough, &comparisonCount);
        printf("Number of comparisons made: %d\n", comparisonCount);

        printf("\nEnter a search key (-1 to exit): ");
        scanf("%d", &key);
    }

    return 0;
}