// q1a readints.c
int *read_ints(int *len) {
    int *read = NULL, capacity = *len = 0, tmp;

    while (scanf("%d", &tmp) == 1) {
        if (*len == capacity) {
            capacity += !capacity ? 1 : capacity;
            read = realloc(read, capacity * sizeof(int));
        }

        read[(*len)++] = tmp;
    }

    return !*len ? NULL : realloc(read, *len * sizeof(int));  // compress
}

// q1b linesplit.c
char **split_lines(const char *s, int *len) {
    assert(len);
    const int n = strlen(s);  // O(n)

    int breaks[n];  // at most there will be n lines, *len counts how many
    for (int i = *len = 0; i <= n; i++)  // O(n) again,
        if (s[i] == '\n' || !s[i])
            breaks[(*len)++] = i;

    if (!*len)  // *len <= n
        return NULL;

    char **lines = malloc(*len * sizeof(char *));

    strncpy(lines[0] = malloc(sizeof(char) * (breaks[0] + 1)), s, breaks[0]);
    s += breaks[0] + 1;

    for (int i = 1; i < *len; i++) {  // O(n), *len is bounded by n
        lines[i] = malloc(sizeof(char) * (breaks[i] - breaks[i - 1]));
        strncpy(lines[i], s, breaks[i] - (breaks[i - 1] + 1));
        // printf("lines[%d]%s(%d)\n", i, lines[i], strlen(lines[i]));
        s += (breaks[i] - (breaks[i - 1]));
    }

    return lines;
}

// q2 sequence.c
struct sequence {
    int *elements, n, capacity;
};

struct sequence *sequence_create(void) {
    struct sequence *s = malloc(sizeof(struct sequence));
    s->elements = NULL, s->n = s->capacity = 0;
    return s;
}

void sequence_destroy(struct sequence *seq) {
    assert(seq);
    free(seq->elements);
    seq->n = seq->capacity = 0;
    free(seq);
}

int sequence_length(const struct sequence *seq) {
    assert(seq);
    return seq->n;
}

int sequence_item_at(const struct sequence *seq, int pos) {
    assert(0 <= pos && pos < sequence_length(seq));
    return seq->elements[pos];
}

void sequence_insert_at(struct sequence *seq, int pos, int val) {
    assert(0 <= pos && pos <= sequence_length(seq));
    printf("inserting at %d]=%d\n", pos, val);
    printf("n=%d, cap=%d\n", sequence_length(seq), seq->capacity);

    if (sequence_length(seq) >= seq->capacity) {
        seq->capacity += !seq->capacity ? 1 : seq->capacity;  // make room
        seq->elements = realloc(seq->elements, seq->capacity * sizeof(int));
    }

    for (int j = seq->n++; j > 0 && j > pos; j--)
        seq->elements[j] = seq->elements[j - 1];
    seq->elements[pos] = val;
}

int sequence_remove_at(struct sequence *seq, int pos) {
    assert(0 <= pos && pos < sequence_length(seq));

    const int n = sequence_length(seq), extracted = seq->elements[pos];

    for (int i = pos; i < n - 1; i++)
        seq->elements[i] = seq->elements[i + 1];
    seq->n--;
    return extracted;
}

void sequence_print(const struct sequence *seq) {
    const int n = sequence_length(seq);
    if (printf("[") && !n && printf("empty]\n"))
        return;

    for (int i = 0; i < n; i++)
        printf("%d%s", seq->elements[i], i < n - 1 ? "," : "]\n");
}

// q3 set.c
struct set {
    int *elements, n, capacity;
};

struct set *set_create(void) {
    struct set *s = malloc(sizeof(struct set));
    s->elements = NULL, s->n = s->capacity = 0;
    return s;
}

void set_destroy(struct set *s) {
    assert(s);
    free(s->elements);
    s->elements = NULL, s->n = s->capacity = 0;
    free(s);
}

int set_size(const struct set *s) {
    assert(s);
    return s->n;
}

// O(log n)
static bool binsearch(const int arr[], const int n, const int key, int *at) {
    int start = 0, middle, end = n - 1;

    while (start <= end)
        if (arr[middle = start + (end - start) / 2] == key)
            return (*at = middle, true);
        else if (key > arr[middle])
            start = middle + 1;
        else if (key < arr[middle])
            end = middle - 1;

    return false;
}

bool set_member(const struct set *s, int i) {
    assert(s);
    int location;
    return binsearch(s->elements, set_size(s), i, &location);  // O(log n)
}

void set_add(struct set *s, int i) {
    assert(s);
    int location;
    if (!binsearch(s->elements, set_size(s), i, &location)) {
        if (set_size(s) >= s->capacity) {
            s->capacity += !s->capacity ? 1 : s->capacity;  // orig/double space
            s->elements = realloc(s->elements, s->capacity * sizeof(int));
        }

        for (int j = s->n++; j > 0 && j > location; j--)
            s->elements[j] = s->elements[j - 1];
        s->elements[location] = i;
    }
}

void set_remove(struct set *s, int i) {
    const int n = set_size(s);
    int location;
    if (binsearch(s->elements, n, i, &location)) {
        for (int j = location; j < n - 1; j++)
            s->elements[j] = s->elements[j + 1];
        s->n--;
    }
}

struct set *set_union(const struct set *s1, const struct set *s2) {
    const int len1 = set_size(s1), len2 = set_size(s2), total = len1 + len2;
    int arr[total], i = 0, j = 0, k = 0, prev;  // k is a counter <= total

    while (i < len1 && j < len2)  // merge, like in mergesort
        if (s1->elements[i] < s2->elements[j]) {
            if (s1->elements[i] != prev)
                arr[k++] = prev = s1->elements[i];
            i++;
        } else {
            if (s2->elements[j] != prev)
                arr[k++] = prev = s2->elements[j];
            j++;
        }

    while (i < len1) {
        if (s1->elements[i] != prev)
            arr[k++] = s1->elements[i];
        i++;
    }
    while (j < len2) {
        if (s2->elements[j] != prev)
            arr[k++] = s2->elements[j];
        j++;
    }

    struct set *u = set_create();
    u->elements = !k ? NULL : malloc(k * sizeof(int)), u->n = u->capacity = k;
    for (int i = 0; i < k; i++)
        u->elements[i] = arr[i];  // k <= total
    return u;
}

struct set *set_intersect(const struct set *s1, const struct set *s2) {
    const int len1 = set_size(s1), len2 = set_size(s2), total = len1 + len2;
    int arr[total], i = 0, j = 0, k = 0;

    while (i < len1 && j < len2)  // merge, like in mergesort
        if (s1->elements[i] < s2->elements[j])
            i++;
        else if (s1->elements[i] > s2->elements[j])
            j++;
        else
            arr[k++] = s1->elements[i], i++, j++;

    struct set *s = set_create();
    s->elements = !k ? NULL : malloc(k * sizeof(int)), s->n = s->capacity = k;
    for (int i = 0; i < k; i++)
        s->elements[i] = arr[i];
    return s;
}

struct set *array_to_set(const int a[], int len) {
    assert(len);

    int tmp[len], count = 0;  // tmp holds sorted version of a[], O(n)
    for (int i = 0; i < len; i++)
        tmp[i] = a[i];
    merge_sort(tmp, len);

    struct set *s = set_create();
    s->elements = !len ? NULL : malloc(sizeof(int) * len);
    if (!len)
        return s;

    s->elements[count++] = tmp[0];
    for (int i = 1, prev = tmp[0]; i < len; i++)
        if (tmp[i] != prev)  // count is len elements at most
            s->elements[count++] = prev = tmp[i];

    s->elements = realloc(s->elements, sizeof(int) * count);  // compress
    s->n = s->capacity = count;
    return s;
}

int *set_to_array(const struct set *s) {
    const int n = set_size(s);
    int *arr = !n ? NULL : malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++)
        arr[i] = s->elements[i];

    return arr;
}

void set_print(const struct set *s) {
    const int n = set_size(s);

    if (printf("[") && !n && printf("empty]\n"))
        return;

    for (int i = 0; i < n; i++)
        printf("%d%s", s->elements[i], i < n - 1 ? "," : "]\n");
}

// q4 inventory.c
struct inventory {
    char **names;
    int *amount, n, capacity;
};

struct inventory *inventory_create(void) {
    struct inventory *inv = malloc(sizeof(struct inventory));
    inv->names = NULL, inv->amount = NULL, inv->n = inv->capacity = 0;
    return inv;
}

void inventory_destroy(struct inventory *inv) {
    assert(inv);

    for (int i = 0; i < inv->n; i++) {
        assert(inv->names[i]);
        free(inv->names[i]);
        inv->names[i] = NULL;
    }
    free(inv->names);

    free(inv->amount);
    inv->names = NULL, inv->amount = NULL, inv->n = inv->capacity = 0;
    free(inv);
}

// O(log n)
static bool binsearch(const char *arr[], const int n, const char *s, int *at) {
    int start = 0, middle, end = n - 1;

    while (start <= end)
        if (!strcmp(arr[middle = start + (end - start) / 2], s))
            return (*at = middle, true);
        else if (strcmp(arr[middle], s) < 0)
            start = middle + 1;
        else  // strcmp(arr[middle], s) > 0)
            end = middle - 1;

    return (*at = start), false;
}

int inventory_lookup(const struct inventory *inv, const char *item) {
    assert(inv && item);

    int location;
    return binsearch(inv->names, inv->n, item, &location) ?
               inv->amount[location] :
               -1;
}

void inventory_add(struct inventory *inv, const char *item, int qty) {
    assert(inv && item && qty >= 0);

    int location;
    if (binsearch(inv->names, inv->n, item, &location))
        inv->amount[location] += qty;
    else {
        if (inv->n == inv->capacity) {  // amortized: conditional capacity incr
            inv->capacity += !inv->capacity ? 1 : inv->capacity;
            inv->names = realloc(inv->names, inv->capacity * sizeof(char *));
            inv->amount = realloc(inv->amount, inv->capacity * sizeof(int));
        }

        for (int i = inv->n++; i > 0 && i > location; i--) {
            inv->names[i] = inv->names[i - 1];  // copy char pointers
            inv->amount[i] = inv->amount[i - 1];  // and amounts
        }
        inv->names[location] = malloc((strlen(item) + 1) * sizeof(char));
        strcpy(inv->names[location], item), inv->amount[location] = qty;
    }
}

void inventory_remove(struct inventory *inv, const char *item, int qty) {
    assert(inv && item && qty > 0);

    int location, availability = -1;
    if (binsearch(inv->names, inv->n, item, &location))
        availability = inv->amount[location];

    assert(qty <= availability);
    inv->amount[location] -= qty;
}

// q5 llfun.c
void print_llist(const struct llist *lst) {
    const int n = length(lst);
    if (printf("[") && !n && printf("empty]\n"))
        return;

    struct llnode *curr = lst->front;
    while (curr)
        printf("%d%s", curr->item, curr->next ? "->" : "]\n"),
            curr = curr->next;
}

struct llist *array_to_llist(const int a[], int len) {
    struct llist *l = list_create();
    for (int i = len - 1; i >= 0; i--)
        add_front(a[i], l);
    return l;
}

int *llist_to_array(const struct llist *lst) {
    const int n = length(lst);  // O(#nodes)
    int *arr = !n ? NULL : malloc(sizeof(int) * n), i;
    struct llnode *curr = lst->front;

    while (curr)  // O(#nodes) again
        arr[i++] = curr->item, curr = curr->next;
    return arr;
}

void map(int (*f)(int), struct llist *lst) {
    assert(lst);

    struct llnode *curr = lst->front;
    while (curr)
        curr->item = f(curr->item), curr = curr->next;
}

// iterative version
// void filter(bool (*f)(int), struct llist *lst) {  // iterative version
//     assert(lst);

//     struct llnode *curr = lst->front, *prev = NULL, *next;
//     while (curr) {
//         if (!f(curr->item)) {
//             if (!prev)
//                 lst->front = curr->next;
//             else
//                 prev->next = curr->next;

//             next = curr->next;
//             free(curr);
//         } else {
//             prev = curr;
//             next = curr->next;
//         }

//         curr = next;
//     }
// }

void filter(bool (*f)(int), struct llist *lst) {  // recursive version
    assert(lst);

    static struct llnode *head, *prev = NULL, *next;
    static bool beginning = true;

    // initialization
    if (beginning)  // needed because static initializations need to be constant
        beginning = false, head = lst->front;  // front mostly stays constant

    struct llnode *curr = lst->front;

    if (!curr)  // base case, fall through return to end recursion
        lst->front = head, prev = NULL, beginning = true;

    else {
        if (!f(curr->item)) {
            if (!prev)
                head = curr->next;
            else
                prev->next = curr->next;

            next = curr->next;
            free(curr);
        } else {
            prev = curr;
            next = curr->next;
        }

        lst->front = next;
        filter(f, lst);
    }
}