/* C11. teaching example. Logical length is separate from capacity. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

static bool insert(int a[], size_t *n, size_t cap, size_t pos, int value)
{
    if (*n > cap || *n == cap || pos > *n) return false;
    for (size_t i = *n; i > pos; --i) a[i] = a[i - 1];
    a[pos] = value;
    ++*n;
    return true;
}
static bool erase(int a[], size_t *n, size_t pos, int *removed)
{
    if (pos >= *n) return false;
    *removed = a[pos];
    for (size_t i = pos; i + 1 < *n; ++i) a[i] = a[i + 1];
    --*n;
    return true;
}
/* Return n if the value is absent. */
static size_t linear_search(const int a[], size_t n, int key)
{
    for (size_t i = 0; i < n; ++i) if (a[i] == key) return i;
    return n;
}
/* Precondition: a[0..n) is in nondecreasing order. Returns first match. */
static size_t binary_search(const int a[], size_t n, int key)
{
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo < n && a[lo] == key ? lo : n;
}
int main(void)
{
    int a[5] = {10, 30, 40}, removed = 0;
    size_t n = 3;
    assert(insert(a, &n, 5, 1, 20));
    assert(insert(a, &n, 5, 4, 50));
    assert(!insert(a, &n, 5, 5, 60));
    assert(!insert(a, &n, 5, 6, 60));
    assert(binary_search(a, n, 30) == 2);
    assert(binary_search(a, n, 99) == n);
    assert(linear_search(a, n, 50) == 4);
    assert(erase(a, &n, 2, &removed) && removed == 30);
    assert(!erase(a, &n, 4, &removed));
    printf("After deletion:");
    for (size_t i = 0; i < n; ++i) printf(" %d", a[i]);
    putchar('\n');
    int duplicate[] = {1, 2, 2, 2, 3};
    assert(binary_search(duplicate, 5, 2) == 1);
    assert(binary_search(a, 0, 10) == 0);
    assert(linear_search(a, 0, 10) == 0);
    n = 0;
    assert(!erase(a, &n, 0, &removed));
    assert(insert(a, &n, 5, 0, -1) && a[0] == -1);
    puts("arrays/search tests passed");
    return 0;
}