/*
 * Ex. No. 4: ARRAY IMPLEMENTATION OF LIST
 * Course enrollment roster with dynamic array
 * Supports: APPEND, INSERT, REMOVE, FIND, DEDUP, RESIZE
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ArrayList {
    int *data;
    int size;
    int capacity;
};

/* Initialize list with capacity 2 */
void initList(struct ArrayList *list) {
    list->capacity = 2;
    list->size = 0;
    list->data = (int *)malloc(list->capacity * sizeof(int));
}

/* Double capacity when full */
void resize(struct ArrayList *list) {
    int newCapacity = list->capacity * 2;
    int *newData = (int *)malloc(newCapacity * sizeof(int));
    for (int i = 0; i < list->size; i++)
        newData[i] = list->data[i];
    free(list->data);
    list->data = newData;
    list->capacity = newCapacity;
}

/* APPEND(x): Add element at end */
void append(struct ArrayList *list, int x) {
    if (list->size == list->capacity)
        resize(list);
    list->data[list->size] = x;
    list->size++;
}

/* INSERT(pos, x): Insert at position pos */
void insert(struct ArrayList *list, int pos, int x) {
    if (pos < 0 || pos > list->size) {
        printf("Invalid position for INSERT\n");
        return;
    }
    if (list->size == list->capacity)
        resize(list);
    for (int i = list->size; i > pos; i--)
        list->data[i] = list->data[i - 1];
    list->data[pos] = x;
    list->size++;
}

/* REMOVE(pos): Remove element at position pos */
void removeAt(struct ArrayList *list, int pos) {
    if (pos < 0 || pos >= list->size) {
        printf("Invalid position for REMOVE\n");
        return;
    }
    for (int i = pos; i < list->size - 1; i++)
        list->data[i] = list->data[i + 1];
    list->size--;
}

/* FIND(x): Return index of x, or -1 if not found */
int find(struct ArrayList *list, int x) {
    for (int i = 0; i < list->size; i++) {
        if (list->data[i] == x)
            return i;
    }
    return -1;
}

/* DEDUP: Remove duplicates, keep first occurrence, preserve order */
void dedup(struct ArrayList *list) {
    if (list->size <= 1) return;

    int *temp = (int *)malloc(list->size * sizeof(int));
    int tempSize = 0;

    for (int i = 0; i < list->size; i++) {
        int isDup = 0;
        for (int j = 0; j < tempSize; j++) {
            if (list->data[i] == temp[j]) {
                isDup = 1;
                break;
            }
        }
        if (!isDup) {
            temp[tempSize] = list->data[i];
            tempSize++;
        }
    }

    for (int i = 0; i < tempSize; i++)
        list->data[i] = temp[i];
    list->size = tempSize;
    free(temp);
}

/* Display current roster */
void display(struct ArrayList *list) {
    printf("Roster: ");
    for (int i = 0; i < list->size; i++)
        printf("%d ", list->data[i]);
    printf("\n");
}

int main() {
    struct ArrayList list;
    initList(&list);

    printf("=== Course Roster ===\n");
    printf("Commands (one per line):\n");
    printf("  APPEND x        -> add x to end\n");
    printf("  INSERT pos x    -> insert x at index pos\n");
    printf("  REMOVE pos      -> remove element at pos\n");
    printf("  FIND x          -> print index of x (-1 if not found)\n");
    printf("  DEDUP           -> remove duplicates\n");

    int M;
    printf("How many commands will you enter? ");
    scanf("%d", &M);

    for (int cmdNum = 1; cmdNum <= M; cmdNum++) {
        char cmd[10];
        printf("\nCommand %d/%d> ", cmdNum, M);
        scanf("%s", cmd);

        if (strcmp(cmd, "APPEND") == 0) {
            int x;
            scanf("%d", &x);
            append(&list, x);
            printf("Appended %d.  ", x);
            display(&list);
        }
        else if (strcmp(cmd, "INSERT") == 0) {
            int pos, x;
            scanf("%d %d", &pos, &x);
            insert(&list, pos, x);
            printf("Inserted %d at index %d.  ", x, pos);
            display(&list);
        }
        else if (strcmp(cmd, "REMOVE") == 0) {
            int pos;
            scanf("%d", &pos);
            removeAt(&list, pos);
            printf("Removed index %d.  ", pos);
            display(&list);
        }
        else if (strcmp(cmd, "FIND") == 0) {
            int x;
            scanf("%d", &x);
            int pos = find(&list, x);
            printf("FIND(%d) = %d\n", x, pos);
        }
        else if (strcmp(cmd, "DEDUP") == 0) {
            dedup(&list);
            printf("Duplicates removed.  ");
            display(&list);
        }
        else {
            printf("Unknown command: %s\n", cmd);
        }
    }

    printf("\n=== Final roster ===\n");
    display(&list);

    free(list.data);
    return 0;
}