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

/* Generic dynamic array of void* */
typedef struct {
    void **data;
    size_t size;
    size_t capacity;
} DynArr;

#define DYN_DEFAULT_CAP 8

/* Create dynamic array */
DynArr *dyn_create(size_t initial_cap) {
    DynArr *a = malloc(sizeof(DynArr));  // Level 1: Create Dynamic array Object
    if (!a) return NULL;
    a->capacity = (initial_cap > 0) ? initial_cap : DYN_DEFAULT_CAP;
    a->size = 0;
    a->data = calloc(a->capacity, sizeof(void *)); // Level 2: Create Array of void Ptr 
    if (!a->data) { free(a); return NULL; }
    return a;
}

/* Free dynamic array structure; free_fn may be NULL (then objects are not freed) */
void dyn_destroy(DynArr *a, void (*free_fn)(void *)) {
    if (!a) return;
    if (free_fn) {
        for (size_t i = 0; i < a->size; ++i) {
            if (a->data[i]) free_fn(a->data[i]);  //Free level 3
        }
    }
    free(a->data);  //Free level 2: Array of void Ptr    
    free(a);     // Free Level 1: Dynaimc Array Object
}

/* Internal ensure capacity */
static int dyn_ensure_cap(DynArr *a, size_t min_cap) {
    if (a->capacity >= min_cap) return 1;
    size_t newcap = a->capacity ? a->capacity * 2 : DYN_DEFAULT_CAP;
    while (newcap < min_cap) newcap *= 2;
    void **tmp = realloc(a->data, newcap * sizeof(void *));
    if (!tmp) return 0;
    a->data = tmp;
    /* zero the new region (not strictly necessary) */
    for (size_t i = a->capacity; i < newcap; ++i) a->data[i] = NULL;
    a->capacity = newcap;
    return 1;
}

/* Append (insert at end) */
int dyn_insert(DynArr *a, void *obj) {
    if (!dyn_ensure_cap(a, a->size + 1)) return 0;
    a->data[a->size++] = obj;
    return 1;
}

/* Insert at index (0..size). If index == size, it's append. */
int dyn_insert_at(DynArr *a, size_t index, void *obj) {
    if (index > a->size) return 0;
    if (!dyn_ensure_cap(a, a->size + 1)) return 0;
    /* shift right */
    for (size_t i = a->size; i > index; --i) a->data[i] = a->data[i - 1];
    a->data[index] = obj;
    a->size++;
    return 1;
}

/* Delete at index; optionally free the object with free_fn */
int dyn_delete_at(DynArr *a, size_t index, void (*free_fn)(void *)) {
    if (index >= a->size) return 0;
    if (free_fn && a->data[index]) free_fn(a->data[index]);
    /* shift left */
    for (size_t i = index; i + 1 < a->size; ++i) a->data[i] = a->data[i + 1];
    a->size--;
    a->data[a->size] = NULL;
    return 1;
}

/* Search: cmp(element, key) -> 0 when equal. Returns index or -1 if not found. */
ssize_t dyn_search(DynArr *a, const void *key, int (*cmp)(const void *, const void *)) {
    if (!a || !cmp) return -1;
    for (size_t i = 0; i < a->size; ++i) {
        if (cmp(a->data[i], key) == 0) return (ssize_t)i;
    }
    return -1;
}

/* Find pointer to max element using comparator cmp(a,b): returns >0 if a > b. */
void *dyn_find_max(DynArr *a, int (*cmp)(const void *, const void *)) {
    if (!a || a->size == 0) return NULL;
    void *best = a->data[0];
    for (size_t i = 1; i < a->size; ++i) {
        if (cmp(a->data[i], best) > 0) best = a->data[i];
    }
    return best;
}

/* Find pointer to min element using comparator cmp(a,b): returns >0 if a > b. */
void *dyn_find_min(DynArr *a, int (*cmp)(const void *, const void *)) {
    if (!a || a->size == 0) return NULL;
    void *best = a->data[0];
    for (size_t i = 1; i < a->size; ++i) {
        if (cmp(a->data[i], best) < 0) best = a->data[i];
    }
    return best;
}

/* Example object type and helper functions */
typedef struct {
    int id;
    char name[64];
} Person;

Person *person_new(int id, const char *name) {
    Person *p = malloc(sizeof(Person)); //Create Level 3: Data of Objects
    if (!p) return NULL;
    p->id = id;
    strncpy(p->name, name ? name : "", sizeof(p->name) - 1);
    p->name[sizeof(p->name) - 1] = '\0';
    return p;
}

void person_free(void *vp) {
    free(vp);
}

/* Comparator: compare by id */
int person_cmp_by_id(const void *a, const void *b_key) {
    const Person *pa = (const Person *)a;
    /* b_key may be Person* or int* (we'll support both styles). We try Person* first. */
    if (!a || !b_key) return 0;
    /* If b_key points to Person (detect by size? not reliable) — assume if pointed memory looks like Person (we can't check). */
    /* Simpler: caller will pass a Person* or an int* explicitly and expect matching comparator type. */
    const Person *pb = (const Person *)b_key;
    if (pa->id < pb->id) return -1;
    if (pa->id > pb->id) return 1;
    return 0;
}

/* Helper comparator that compares two Person* */
int person_cmp_personptr(const void *a, const void *b) {
    const Person *pa = (const Person *)a;
    const Person *pb = (const Person *)b;
    if (pa->id < pb->id) return -1;
    if (pa->id > pb->id) return 1;
    return 0;
}

/* Example usage */
int main(void) {
    DynArr *arr = dyn_create(4);
    if (!arr) { fprintf(stderr, "alloc fail\n"); return 1; }

    dyn_insert(arr, person_new(10, "Alice"));
    dyn_insert(arr, person_new(3, "Bob"));
    dyn_insert(arr, person_new(42, "Carol"));
    dyn_insert(arr, person_new(7, "Dave"));

    printf("Array size after inserts: %zu\n", arr->size);
    for (size_t i = 0; i < arr->size; ++i) {
        Person *p = (Person *)arr->data[i];
        printf(" [%zu] id=%d name=%s\n", i, p->id, p->name);
    }

    /* Search by key (build a Person key with same id) */
    Person key;
    key.id = 42;
    key.name[0] = '\0';
    ssize_t idx = dyn_search(arr, &key, person_cmp_by_id);
    if (idx >= 0) {
        Person *found = (Person *)arr->data[idx];
        printf("Found id=%d at index %zd, name=%s\n", found->id, idx, found->name);
    } else {
        printf("Not found\n");
    }

    /* Find max and min by id */
    Person *maxp = (Person *)dyn_find_max(arr, person_cmp_personptr);
    Person *minp = (Person *)dyn_find_min(arr, person_cmp_personptr);
    if (maxp) printf("Max id=%d name=%s\n", maxp->id, maxp->name);
    if (minp) printf("Min id=%d name=%s\n", minp->id, minp->name);

    /* Delete element at index 1 (Bob) */
    if (dyn_delete_at(arr, 1, person_free)) {
        printf("Deleted element at index 1\n");
    }

    printf("Array after deletion:\n");
    for (size_t i = 0; i < arr->size; ++i) {
        Person *p = (Person *)arr->data[i];
        printf(" [%zu] id=%d name=%s\n", i, p->id, p->name);
    }

    /* Insert at index 1 */
    dyn_insert_at(arr, 1, person_new(99, "Eve"));
    printf("After inserting Eve at index 1:\n");
    for (size_t i = 0; i < arr->size; ++i) {
        Person *p = (Person *)arr->data[i];
        printf(" [%zu] id=%d name=%s\n", i, p->id, p->name);
    }

    /* Cleanup */
    dyn_destroy(arr, person_free);
    return 0;
}