examples

/**
 * Dynamic Arrays in C - Examples
 * 
 * This file contains comprehensive examples demonstrating
 * dynamic array creation, manipulation, and various implementations.
 */

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

/* ============================================================
 * Example 1: Basic Dynamic Array Operations
 * ============================================================ */

void example_basic_dynamic_array(void) {
    printf("=== Example 1: Basic Dynamic Array Operations ===\n\n");
    
    /* Declare a pointer for our dynamic array */
    int *arr = NULL;
    size_t size = 0;
    size_t capacity = 4;
    
    /* Initial allocation */
    arr = malloc(capacity * sizeof(int));
    if (!arr) {
        fprintf(stderr, "Initial allocation failed!\n");
        return;
    }
    
    printf("Initial capacity: %zu\n", capacity);
    
    /* Add elements with automatic growing */
    for (int i = 0; i < 10; i++) {
        /* Check if we need to grow */
        if (size >= capacity) {
            capacity *= 2;
            printf("Growing array to capacity: %zu\n", capacity);
            
            int *temp = realloc(arr, capacity * sizeof(int));
            if (!temp) {
                fprintf(stderr, "Reallocation failed!\n");
                free(arr);
                return;
            }
            arr = temp;
        }
        
        arr[size++] = i * 10;
    }
    
    /* Print the array */
    printf("\nArray contents (size=%zu, capacity=%zu): ", size, capacity);
    for (size_t i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    free(arr);
}

/* ============================================================
 * Example 2: Array of Pointers for 2D Dynamic Array
 * ============================================================ */

void example_2d_array_pointers(void) {
    printf("=== Example 2: 2D Array Using Array of Pointers ===\n\n");
    
    size_t rows = 3;
    size_t cols = 4;
    
    /* Allocate array of row pointers */
    int **matrix = malloc(rows * sizeof(int *));
    if (!matrix) {
        fprintf(stderr, "Failed to allocate row pointers!\n");
        return;
    }
    
    /* Allocate each row */
    for (size_t i = 0; i < rows; i++) {
        matrix[i] = malloc(cols * sizeof(int));
        if (!matrix[i]) {
            fprintf(stderr, "Failed to allocate row %zu!\n", i);
            /* Cleanup already allocated rows */
            while (i > 0) free(matrix[--i]);
            free(matrix);
            return;
        }
    }
    
    /* Initialize with values */
    int value = 1;
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++) {
            matrix[i][j] = value++;
        }
    }
    
    /* Print the matrix */
    printf("Matrix (%zux%zu):\n", rows, cols);
    for (size_t i = 0; i < rows; i++) {
        printf("  [ ");
        for (size_t j = 0; j < cols; j++) {
            printf("%3d ", matrix[i][j]);
        }
        printf("]\n");
    }
    printf("\n");
    
    /* Free the matrix */
    for (size_t i = 0; i < rows; i++) {
        free(matrix[i]);
    }
    free(matrix);
}

/* ============================================================
 * Example 3: Contiguous 2D Array (Better Cache Performance)
 * ============================================================ */

typedef struct {
    int *data;
    size_t rows;
    size_t cols;
} ContiguousMatrix;

ContiguousMatrix *cm_create(size_t rows, size_t cols) {
    ContiguousMatrix *m = malloc(sizeof(ContiguousMatrix));
    if (!m) return NULL;
    
    m->data = calloc(rows * cols, sizeof(int));
    if (!m->data) {
        free(m);
        return NULL;
    }
    
    m->rows = rows;
    m->cols = cols;
    return m;
}

void cm_destroy(ContiguousMatrix *m) {
    if (m) {
        free(m->data);
        free(m);
    }
}

int cm_get(ContiguousMatrix *m, size_t r, size_t c) {
    return m->data[r * m->cols + c];
}

void cm_set(ContiguousMatrix *m, size_t r, size_t c, int val) {
    m->data[r * m->cols + c] = val;
}

void example_contiguous_2d_array(void) {
    printf("=== Example 3: Contiguous 2D Array ===\n\n");
    
    ContiguousMatrix *m = cm_create(3, 4);
    if (!m) {
        fprintf(stderr, "Failed to create matrix!\n");
        return;
    }
    
    /* Initialize */
    int value = 1;
    for (size_t i = 0; i < m->rows; i++) {
        for (size_t j = 0; j < m->cols; j++) {
            cm_set(m, i, j, value++);
        }
    }
    
    /* Print */
    printf("Contiguous Matrix:\n");
    for (size_t i = 0; i < m->rows; i++) {
        printf("  [ ");
        for (size_t j = 0; j < m->cols; j++) {
            printf("%3d ", cm_get(m, i, j));
        }
        printf("]\n");
    }
    
    /* Show memory layout */
    printf("\nMemory layout (all data contiguous):\n  ");
    for (size_t i = 0; i < m->rows * m->cols; i++) {
        printf("%d ", m->data[i]);
    }
    printf("\n\n");
    
    cm_destroy(m);
}

/* ============================================================
 * Example 4: Generic Dynamic Array (Integer Version)
 * ============================================================ */

#define INITIAL_CAPACITY 4
#define GROWTH_FACTOR 2

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} IntVector;

IntVector *ivec_create(void) {
    IntVector *v = malloc(sizeof(IntVector));
    if (!v) return NULL;
    
    v->data = malloc(INITIAL_CAPACITY * sizeof(int));
    if (!v->data) {
        free(v);
        return NULL;
    }
    
    v->size = 0;
    v->capacity = INITIAL_CAPACITY;
    return v;
}

void ivec_destroy(IntVector *v) {
    if (v) {
        free(v->data);
        free(v);
    }
}

int ivec_push(IntVector *v, int value) {
    if (v->size >= v->capacity) {
        size_t new_cap = v->capacity * GROWTH_FACTOR;
        int *temp = realloc(v->data, new_cap * sizeof(int));
        if (!temp) return -1;
        v->data = temp;
        v->capacity = new_cap;
    }
    v->data[v->size++] = value;
    return 0;
}

int ivec_pop(IntVector *v) {
    if (v->size == 0) return 0;
    return v->data[--v->size];
}

int ivec_get(IntVector *v, size_t index) {
    if (index >= v->size) return 0;
    return v->data[index];
}

void ivec_set(IntVector *v, size_t index, int value) {
    if (index < v->size) {
        v->data[index] = value;
    }
}

void ivec_print(IntVector *v) {
    printf("IntVector [size=%zu, cap=%zu]: ", v->size, v->capacity);
    for (size_t i = 0; i < v->size; i++) {
        printf("%d ", v->data[i]);
    }
    printf("\n");
}

void example_int_vector(void) {
    printf("=== Example 4: Integer Vector Implementation ===\n\n");
    
    IntVector *v = ivec_create();
    if (!v) {
        fprintf(stderr, "Failed to create vector!\n");
        return;
    }
    
    /* Push elements */
    printf("Pushing elements 0-9:\n");
    for (int i = 0; i < 10; i++) {
        ivec_push(v, i);
        printf("  After pushing %d: ", i);
        ivec_print(v);
    }
    
    /* Pop elements */
    printf("\nPopping 3 elements:\n");
    for (int i = 0; i < 3; i++) {
        int val = ivec_pop(v);
        printf("  Popped: %d, ", val);
        ivec_print(v);
    }
    
    /* Modify element */
    printf("\nSetting index 2 to 100:\n");
    ivec_set(v, 2, 100);
    ivec_print(v);
    printf("\n");
    
    ivec_destroy(v);
}

/* ============================================================
 * Example 5: Single Allocation 2D Array (Array of Pointers + Data)
 * ============================================================ */

int **create_unified_2d(size_t rows, size_t cols) {
    /* Single allocation for pointers + data */
    int **arr = malloc(rows * sizeof(int *) + rows * cols * sizeof(int));
    if (!arr) return NULL;
    
    /* Data starts after the pointer array */
    int *data = (int *)(arr + rows);
    
    /* Set up row pointers */
    for (size_t i = 0; i < rows; i++) {
        arr[i] = data + i * cols;
    }
    
    return arr;
}

void destroy_unified_2d(int **arr) {
    free(arr);  /* Single free */
}

void example_unified_2d_array(void) {
    printf("=== Example 5: Unified 2D Array (Single Allocation) ===\n\n");
    
    size_t rows = 3;
    size_t cols = 5;
    
    int **arr = create_unified_2d(rows, cols);
    if (!arr) {
        fprintf(stderr, "Failed to create array!\n");
        return;
    }
    
    /* Initialize */
    int val = 1;
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++) {
            arr[i][j] = val++;
        }
    }
    
    /* Print using standard 2D syntax */
    printf("Array contents:\n");
    for (size_t i = 0; i < rows; i++) {
        printf("  Row %zu: ", i);
        for (size_t j = 0; j < cols; j++) {
            printf("%3d ", arr[i][j]);
        }
        printf("\n");
    }
    
    /* Show that pointers are contiguous */
    printf("\nRow pointers (addresses):\n");
    for (size_t i = 0; i < rows; i++) {
        printf("  arr[%zu] = %p\n", i, (void *)arr[i]);
    }
    printf("\n");
    
    destroy_unified_2d(arr);
}

/* ============================================================
 * Example 6: Jagged Array (Rows of Different Sizes)
 * ============================================================ */

typedef struct {
    int *data;
    size_t length;
} Row;

typedef struct {
    Row *rows;
    size_t num_rows;
} JaggedArray;

JaggedArray *jagged_create(size_t num_rows) {
    JaggedArray *j = malloc(sizeof(JaggedArray));
    if (!j) return NULL;
    
    j->rows = calloc(num_rows, sizeof(Row));
    if (!j->rows) {
        free(j);
        return NULL;
    }
    
    j->num_rows = num_rows;
    return j;
}

int jagged_set_row(JaggedArray *j, size_t row_idx, size_t length) {
    if (row_idx >= j->num_rows) return -1;
    
    /* Free existing row if present */
    free(j->rows[row_idx].data);
    
    j->rows[row_idx].data = calloc(length, sizeof(int));
    if (!j->rows[row_idx].data && length > 0) return -1;
    
    j->rows[row_idx].length = length;
    return 0;
}

void jagged_destroy(JaggedArray *j) {
    if (j) {
        for (size_t i = 0; i < j->num_rows; i++) {
            free(j->rows[i].data);
        }
        free(j->rows);
        free(j);
    }
}

void example_jagged_array(void) {
    printf("=== Example 6: Jagged Array (Variable Row Lengths) ===\n\n");
    
    JaggedArray *j = jagged_create(5);
    if (!j) {
        fprintf(stderr, "Failed to create jagged array!\n");
        return;
    }
    
    /* Create rows of different lengths (like Pascal's triangle shape) */
    size_t lengths[] = {1, 2, 3, 4, 5};
    
    for (size_t i = 0; i < 5; i++) {
        jagged_set_row(j, i, lengths[i]);
        
        /* Fill row with values */
        for (size_t k = 0; k < lengths[i]; k++) {
            j->rows[i].data[k] = (int)(i * 10 + k);
        }
    }
    
    /* Print jagged array */
    printf("Jagged Array:\n");
    for (size_t i = 0; i < j->num_rows; i++) {
        printf("  Row %zu (len=%zu): [ ", i, j->rows[i].length);
        for (size_t k = 0; k < j->rows[i].length; k++) {
            printf("%2d ", j->rows[i].data[k]);
        }
        printf("]\n");
    }
    printf("\n");
    
    jagged_destroy(j);
}

/* ============================================================
 * Example 7: Dynamic Array with Insert and Remove
 * ============================================================ */

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} DynArray;

DynArray *da_create(void) {
    DynArray *arr = malloc(sizeof(DynArray));
    if (!arr) return NULL;
    
    arr->data = malloc(8 * sizeof(int));
    if (!arr->data) {
        free(arr);
        return NULL;
    }
    
    arr->size = 0;
    arr->capacity = 8;
    return arr;
}

void da_destroy(DynArray *arr) {
    if (arr) {
        free(arr->data);
        free(arr);
    }
}

int da_ensure_capacity(DynArray *arr, size_t min_cap) {
    if (min_cap <= arr->capacity) return 0;
    
    size_t new_cap = arr->capacity;
    while (new_cap < min_cap) new_cap *= 2;
    
    int *temp = realloc(arr->data, new_cap * sizeof(int));
    if (!temp) return -1;
    
    arr->data = temp;
    arr->capacity = new_cap;
    return 0;
}

int da_insert(DynArray *arr, size_t index, int value) {
    if (index > arr->size) return -1;
    
    if (da_ensure_capacity(arr, arr->size + 1) != 0) return -1;
    
    /* Shift elements right */
    memmove(&arr->data[index + 1], &arr->data[index], 
            (arr->size - index) * sizeof(int));
    
    arr->data[index] = value;
    arr->size++;
    return 0;
}

int da_remove(DynArray *arr, size_t index) {
    if (index >= arr->size) return -1;
    
    int removed = arr->data[index];
    
    /* Shift elements left */
    memmove(&arr->data[index], &arr->data[index + 1],
            (arr->size - index - 1) * sizeof(int));
    
    arr->size--;
    return removed;
}

void da_push(DynArray *arr, int value) {
    da_insert(arr, arr->size, value);
}

void da_print(DynArray *arr) {
    printf("[");
    for (size_t i = 0; i < arr->size; i++) {
        printf("%d", arr->data[i]);
        if (i < arr->size - 1) printf(", ");
    }
    printf("] (size=%zu, cap=%zu)\n", arr->size, arr->capacity);
}

void example_insert_remove(void) {
    printf("=== Example 7: Dynamic Array with Insert/Remove ===\n\n");
    
    DynArray *arr = da_create();
    if (!arr) return;
    
    /* Build initial array */
    for (int i = 0; i < 5; i++) {
        da_push(arr, i * 10);
    }
    printf("Initial:  ");
    da_print(arr);
    
    /* Insert at beginning */
    da_insert(arr, 0, 99);
    printf("Insert 99 at start:  ");
    da_print(arr);
    
    /* Insert in middle */
    da_insert(arr, 3, 55);
    printf("Insert 55 at index 3:  ");
    da_print(arr);
    
    /* Insert at end */
    da_insert(arr, arr->size, 77);
    printf("Insert 77 at end:  ");
    da_print(arr);
    
    /* Remove from middle */
    int removed = da_remove(arr, 3);
    printf("Remove from index 3 (got %d):  ", removed);
    da_print(arr);
    
    /* Remove from start */
    removed = da_remove(arr, 0);
    printf("Remove from start (got %d):  ", removed);
    da_print(arr);
    printf("\n");
    
    da_destroy(arr);
}

/* ============================================================
 * Example 8: String Array (Dynamic Array of Strings)
 * ============================================================ */

typedef struct {
    char **strings;
    size_t size;
    size_t capacity;
} StringArray;

StringArray *sa_create(void) {
    StringArray *sa = malloc(sizeof(StringArray));
    if (!sa) return NULL;
    
    sa->strings = malloc(4 * sizeof(char *));
    if (!sa->strings) {
        free(sa);
        return NULL;
    }
    
    sa->size = 0;
    sa->capacity = 4;
    return sa;
}

void sa_destroy(StringArray *sa) {
    if (sa) {
        for (size_t i = 0; i < sa->size; i++) {
            free(sa->strings[i]);
        }
        free(sa->strings);
        free(sa);
    }
}

int sa_push(StringArray *sa, const char *str) {
    if (sa->size >= sa->capacity) {
        size_t new_cap = sa->capacity * 2;
        char **temp = realloc(sa->strings, new_cap * sizeof(char *));
        if (!temp) return -1;
        sa->strings = temp;
        sa->capacity = new_cap;
    }
    
    sa->strings[sa->size] = strdup(str);
    if (!sa->strings[sa->size]) return -1;
    
    sa->size++;
    return 0;
}

const char *sa_get(StringArray *sa, size_t index) {
    if (index >= sa->size) return NULL;
    return sa->strings[index];
}

void sa_print(StringArray *sa) {
    printf("StringArray [size=%zu]:\n", sa->size);
    for (size_t i = 0; i < sa->size; i++) {
        printf("  [%zu]: \"%s\"\n", i, sa->strings[i]);
    }
}

void example_string_array(void) {
    printf("=== Example 8: Dynamic String Array ===\n\n");
    
    StringArray *sa = sa_create();
    if (!sa) return;
    
    /* Add strings */
    sa_push(sa, "Hello");
    sa_push(sa, "World");
    sa_push(sa, "Dynamic");
    sa_push(sa, "Arrays");
    sa_push(sa, "in C");
    
    sa_print(sa);
    
    /* Access specific string */
    printf("\nElement at index 2: \"%s\"\n\n", sa_get(sa, 2));
    
    sa_destroy(sa);
}

/* ============================================================
 * Example 9: Growth Strategy Comparison
 * ============================================================ */

void example_growth_strategies(void) {
    printf("=== Example 9: Growth Strategy Comparison ===\n\n");
    
    /* Simulate different growth strategies */
    printf("Inserting 1000 elements with different strategies:\n\n");
    
    /* Strategy 1: Add 10 each time */
    {
        size_t capacity = 10;
        size_t size = 0;
        int reallocations = 0;
        
        for (int i = 0; i < 1000; i++) {
            if (size >= capacity) {
                capacity += 10;  /* Linear growth */
                reallocations++;
            }
            size++;
        }
        printf("Linear (+10): %d reallocations, final capacity: %zu\n",
               reallocations, capacity);
    }
    
    /* Strategy 2: Double each time */
    {
        size_t capacity = 4;
        size_t size = 0;
        int reallocations = 0;
        
        for (int i = 0; i < 1000; i++) {
            if (size >= capacity) {
                capacity *= 2;  /* Doubling */
                reallocations++;
            }
            size++;
        }
        printf("Doubling (2x): %d reallocations, final capacity: %zu\n",
               reallocations, capacity);
    }
    
    /* Strategy 3: Multiply by 1.5 */
    {
        size_t capacity = 4;
        size_t size = 0;
        int reallocations = 0;
        
        for (int i = 0; i < 1000; i++) {
            if (size >= capacity) {
                capacity = capacity + capacity / 2;  /* 1.5x growth */
                reallocations++;
            }
            size++;
        }
        printf("1.5x growth: %d reallocations, final capacity: %zu\n",
               reallocations, capacity);
    }
    
    printf("\n");
}

/* ============================================================
 * Example 10: Memory-Efficient Bit Array
 * ============================================================ */

typedef struct {
    unsigned char *data;
    size_t num_bits;
} BitArray;

BitArray *bitarray_create(size_t num_bits) {
    BitArray *ba = malloc(sizeof(BitArray));
    if (!ba) return NULL;
    
    size_t num_bytes = (num_bits + 7) / 8;
    ba->data = calloc(num_bytes, 1);
    if (!ba->data) {
        free(ba);
        return NULL;
    }
    
    ba->num_bits = num_bits;
    return ba;
}

void bitarray_destroy(BitArray *ba) {
    if (ba) {
        free(ba->data);
        free(ba);
    }
}

void bitarray_set(BitArray *ba, size_t index) {
    if (index >= ba->num_bits) return;
    ba->data[index / 8] |= (1 << (index % 8));
}

void bitarray_clear(BitArray *ba, size_t index) {
    if (index >= ba->num_bits) return;
    ba->data[index / 8] &= ~(1 << (index % 8));
}

int bitarray_get(BitArray *ba, size_t index) {
    if (index >= ba->num_bits) return 0;
    return (ba->data[index / 8] >> (index % 8)) & 1;
}

void bitarray_print(BitArray *ba) {
    printf("BitArray [%zu bits]: ", ba->num_bits);
    for (size_t i = 0; i < ba->num_bits; i++) {
        printf("%d", bitarray_get(ba, i));
        if ((i + 1) % 8 == 0 && i + 1 < ba->num_bits) printf(" ");
    }
    printf("\n");
}

void example_bit_array(void) {
    printf("=== Example 10: Memory-Efficient Bit Array ===\n\n");
    
    BitArray *ba = bitarray_create(16);
    if (!ba) return;
    
    printf("Initial (all zeros):\n");
    bitarray_print(ba);
    
    /* Set some bits */
    bitarray_set(ba, 0);
    bitarray_set(ba, 3);
    bitarray_set(ba, 7);
    bitarray_set(ba, 8);
    bitarray_set(ba, 15);
    
    printf("\nAfter setting bits 0, 3, 7, 8, 15:\n");
    bitarray_print(ba);
    
    /* Clear a bit */
    bitarray_clear(ba, 3);
    printf("\nAfter clearing bit 3:\n");
    bitarray_print(ba);
    
    /* Memory comparison */
    printf("\nMemory usage comparison for 1000 flags:\n");
    printf("  int array: %zu bytes\n", 1000 * sizeof(int));
    printf("  bit array: %zu bytes\n", (1000 + 7) / 8);
    printf("\n");
    
    bitarray_destroy(ba);
}

/* ============================================================
 * Example 11: Circular Buffer
 * ============================================================ */

typedef struct {
    int *data;
    size_t capacity;
    size_t head;
    size_t tail;
    size_t size;
} CircularBuffer;

CircularBuffer *cb_create(size_t capacity) {
    CircularBuffer *cb = malloc(sizeof(CircularBuffer));
    if (!cb) return NULL;
    
    cb->data = malloc(capacity * sizeof(int));
    if (!cb->data) {
        free(cb);
        return NULL;
    }
    
    cb->capacity = capacity;
    cb->head = 0;
    cb->tail = 0;
    cb->size = 0;
    return cb;
}

void cb_destroy(CircularBuffer *cb) {
    if (cb) {
        free(cb->data);
        free(cb);
    }
}

int cb_push(CircularBuffer *cb, int value) {
    if (cb->size >= cb->capacity) return -1;  /* Full */
    
    cb->data[cb->tail] = value;
    cb->tail = (cb->tail + 1) % cb->capacity;
    cb->size++;
    return 0;
}

int cb_pop(CircularBuffer *cb, int *out) {
    if (cb->size == 0) return -1;  /* Empty */
    
    *out = cb->data[cb->head];
    cb->head = (cb->head + 1) % cb->capacity;
    cb->size--;
    return 0;
}

void cb_print(CircularBuffer *cb) {
    printf("CircularBuffer [size=%zu, cap=%zu]: ", cb->size, cb->capacity);
    size_t i = cb->head;
    for (size_t count = 0; count < cb->size; count++) {
        printf("%d ", cb->data[i]);
        i = (i + 1) % cb->capacity;
    }
    printf("\n");
}

void example_circular_buffer(void) {
    printf("=== Example 11: Circular Buffer ===\n\n");
    
    CircularBuffer *cb = cb_create(5);
    if (!cb) return;
    
    /* Fill the buffer */
    printf("Pushing 1, 2, 3, 4, 5:\n");
    for (int i = 1; i <= 5; i++) {
        cb_push(cb, i);
    }
    cb_print(cb);
    
    /* Pop some */
    int val;
    cb_pop(cb, &val);
    printf("\nPopped %d:\n", val);
    cb_print(cb);
    
    cb_pop(cb, &val);
    printf("\nPopped %d:\n", val);
    cb_print(cb);
    
    /* Push more */
    printf("\nPushing 10, 20:\n");
    cb_push(cb, 10);
    cb_push(cb, 20);
    cb_print(cb);
    
    /* Show circular nature */
    printf("\nCircular wrap-around demonstrated!\n");
    printf("(Data wraps around the fixed-size buffer)\n\n");
    
    cb_destroy(cb);
}

/* ============================================================
 * Example 12: Stack Implementation Using Dynamic Array
 * ============================================================ */

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} Stack;

Stack *stack_create(void) {
    Stack *s = malloc(sizeof(Stack));
    if (!s) return NULL;
    
    s->data = malloc(8 * sizeof(int));
    if (!s->data) {
        free(s);
        return NULL;
    }
    
    s->size = 0;
    s->capacity = 8;
    return s;
}

void stack_destroy(Stack *s) {
    if (s) {
        free(s->data);
        free(s);
    }
}

int stack_push(Stack *s, int value) {
    if (s->size >= s->capacity) {
        size_t new_cap = s->capacity * 2;
        int *temp = realloc(s->data, new_cap * sizeof(int));
        if (!temp) return -1;
        s->data = temp;
        s->capacity = new_cap;
    }
    s->data[s->size++] = value;
    return 0;
}

int stack_pop(Stack *s) {
    if (s->size == 0) return 0;
    return s->data[--s->size];
}

int stack_peek(Stack *s) {
    if (s->size == 0) return 0;
    return s->data[s->size - 1];
}

int stack_is_empty(Stack *s) {
    return s->size == 0;
}

void example_stack(void) {
    printf("=== Example 12: Stack Using Dynamic Array ===\n\n");
    
    Stack *s = stack_create();
    if (!s) return;
    
    /* Demonstrate stack operations */
    printf("Pushing: 10, 20, 30, 40, 50\n");
    stack_push(s, 10);
    stack_push(s, 20);
    stack_push(s, 30);
    stack_push(s, 40);
    stack_push(s, 50);
    
    printf("Top element (peek): %d\n", stack_peek(s));
    
    printf("\nPopping all elements: ");
    while (!stack_is_empty(s)) {
        printf("%d ", stack_pop(s));
    }
    printf("\n\n");
    
    stack_destroy(s);
}

/* ============================================================
 * Example 13: Dynamic Array Sorting
 * ============================================================ */

int compare_ints(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

void example_sorting(void) {
    printf("=== Example 13: Sorting Dynamic Arrays ===\n\n");
    
    IntVector *v = ivec_create();
    if (!v) return;
    
    /* Add random-ish values */
    int values[] = {42, 17, 89, 3, 56, 12, 91, 28, 65, 8};
    int n = sizeof(values) / sizeof(values[0]);
    
    for (int i = 0; i < n; i++) {
        ivec_push(v, values[i]);
    }
    
    printf("Before sorting: ");
    ivec_print(v);
    
    /* Sort using qsort */
    qsort(v->data, v->size, sizeof(int), compare_ints);
    
    printf("After sorting:  ");
    ivec_print(v);
    printf("\n");
    
    ivec_destroy(v);
}

/* ============================================================
 * Example 14: Dynamic 3D Array
 * ============================================================ */

typedef struct {
    int *data;
    size_t depth;
    size_t rows;
    size_t cols;
} Array3D;

Array3D *array3d_create(size_t depth, size_t rows, size_t cols) {
    Array3D *a = malloc(sizeof(Array3D));
    if (!a) return NULL;
    
    a->data = calloc(depth * rows * cols, sizeof(int));
    if (!a->data) {
        free(a);
        return NULL;
    }
    
    a->depth = depth;
    a->rows = rows;
    a->cols = cols;
    return a;
}

void array3d_destroy(Array3D *a) {
    if (a) {
        free(a->data);
        free(a);
    }
}

int array3d_get(Array3D *a, size_t z, size_t y, size_t x) {
    return a->data[z * a->rows * a->cols + y * a->cols + x];
}

void array3d_set(Array3D *a, size_t z, size_t y, size_t x, int val) {
    a->data[z * a->rows * a->cols + y * a->cols + x] = val;
}

void example_3d_array(void) {
    printf("=== Example 14: Dynamic 3D Array ===\n\n");
    
    Array3D *cube = array3d_create(2, 3, 4);  /* 2x3x4 cube */
    if (!cube) return;
    
    /* Fill with values based on position */
    int val = 0;
    for (size_t z = 0; z < cube->depth; z++) {
        for (size_t y = 0; y < cube->rows; y++) {
            for (size_t x = 0; x < cube->cols; x++) {
                array3d_set(cube, z, y, x, val++);
            }
        }
    }
    
    /* Print each layer */
    for (size_t z = 0; z < cube->depth; z++) {
        printf("Layer %zu:\n", z);
        for (size_t y = 0; y < cube->rows; y++) {
            printf("  ");
            for (size_t x = 0; x < cube->cols; x++) {
                printf("%3d ", array3d_get(cube, z, y, x));
            }
            printf("\n");
        }
        printf("\n");
    }
    
    array3d_destroy(cube);
}

/* ============================================================
 * Example 15: Shrink-to-Fit and Memory Optimization
 * ============================================================ */

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} OptVector;

OptVector *optvec_create(size_t initial_cap) {
    OptVector *v = malloc(sizeof(OptVector));
    if (!v) return NULL;
    
    v->data = malloc(initial_cap * sizeof(int));
    if (!v->data) {
        free(v);
        return NULL;
    }
    
    v->size = 0;
    v->capacity = initial_cap;
    return v;
}

void optvec_destroy(OptVector *v) {
    if (v) {
        free(v->data);
        free(v);
    }
}

void optvec_push(OptVector *v, int value) {
    if (v->size >= v->capacity) {
        v->capacity *= 2;
        v->data = realloc(v->data, v->capacity * sizeof(int));
    }
    v->data[v->size++] = value;
}

void optvec_pop(OptVector *v) {
    if (v->size > 0) v->size--;
}

/* Shrink capacity to match size */
void optvec_shrink_to_fit(OptVector *v) {
    if (v->size < v->capacity) {
        size_t new_cap = v->size > 0 ? v->size : 1;
        int *temp = realloc(v->data, new_cap * sizeof(int));
        if (temp) {
            v->data = temp;
            v->capacity = new_cap;
        }
    }
}

/* Reserve specific capacity */
void optvec_reserve(OptVector *v, size_t min_cap) {
    if (min_cap > v->capacity) {
        int *temp = realloc(v->data, min_cap * sizeof(int));
        if (temp) {
            v->data = temp;
            v->capacity = min_cap;
        }
    }
}

void example_memory_optimization(void) {
    printf("=== Example 15: Memory Optimization ===\n\n");
    
    OptVector *v = optvec_create(4);
    if (!v) return;
    
    /* Add many elements */
    printf("Adding 100 elements...\n");
    for (int i = 0; i < 100; i++) {
        optvec_push(v, i);
    }
    printf("Size: %zu, Capacity: %zu\n", v->size, v->capacity);
    
    /* Remove most elements */
    printf("\nRemoving 90 elements...\n");
    for (int i = 0; i < 90; i++) {
        optvec_pop(v);
    }
    printf("Size: %zu, Capacity: %zu (wasted space!)\n", v->size, v->capacity);
    
    /* Shrink to fit */
    printf("\nShrinking to fit...\n");
    optvec_shrink_to_fit(v);
    printf("Size: %zu, Capacity: %zu (optimized!)\n", v->size, v->capacity);
    
    /* Pre-reserve for known size */
    printf("\nReserving for 50 elements...\n");
    optvec_reserve(v, 50);
    printf("Size: %zu, Capacity: %zu\n", v->size, v->capacity);
    printf("\n");
    
    optvec_destroy(v);
}

/* ============================================================
 * Main Function
 * ============================================================ */

int main(void) {
    printf("\n");
    printf("╔══════════════════════════════════════════════════════════╗\n");
    printf("║         Dynamic Arrays in C - Examples                   ║\n");
    printf("╚══════════════════════════════════════════════════════════╝\n\n");
    
    example_basic_dynamic_array();
    example_2d_array_pointers();
    example_contiguous_2d_array();
    example_int_vector();
    example_unified_2d_array();
    example_jagged_array();
    example_insert_remove();
    example_string_array();
    example_growth_strategies();
    example_bit_array();
    example_circular_buffer();
    example_stack();
    example_sorting();
    example_3d_array();
    example_memory_optimization();
    
    printf("╔══════════════════════════════════════════════════════════╗\n");
    printf("║                  All examples complete!                   ║\n");
    printf("╚══════════════════════════════════════════════════════════╝\n\n");
    
    return 0;
}