spreadsheet.c

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

struct position {
    short col, row;
    struct position *next;
};

struct position *position(short col, short row, struct position *next)
{
    struct position *cell = malloc(sizeof(struct position));
    if (cell == NULL)
        abort();
    cell->col = col;
    cell->row = row;
    cell->next = next;
    return cell;
}

inline void position_free(struct position *p)
{
    free(p);  // fully abstract allocation
}

struct position *position_parse(const char **s)
{
    struct position *out = position(0, 0, NULL);
    while (isalnum(**s)) {
        if (isalpha(**s))
            out->col = out->col * 26 + (**s - 'A') + 1;
        else
            out->row = out->row * 10 + (**s - '0');
        (*s)++;
    }
    out->col--;
    out->row--;
    return out;
}

int position_cmp(const void *a, const void *b)
{
    struct position **pa = (struct position **) a,
                    **pb = (struct position **) b;
    if ((**pa).col == (**pb).col)
        return (**pa).row - (**pb).row;
    else
        return (**pa).col - (**pb).col;
}

void selection_free(struct position *selection)
{
    while (selection) {
        struct position *last = selection;
        selection = selection->next;
        position_free(last);
    }
}

struct position *selection_range(struct position *start, struct position *end)
{
    struct position *head = start;
    for (int col = start->col; col <= end->col; col++) {
        for (int row = start->row; row <= end->row; row++) {
            if (row == end->row && col == end->col)
                head = head->next = end;
            else if (row != start->row || col != start->col)
                head = head->next = position(col, row, NULL);
        }
    }
    return start;
}

struct position *selection_last(struct position *selection)
{
    if (selection == NULL)
        return NULL;
    while (selection->next)
        selection = selection->next;
    return selection;
}

size_t selection_size(const struct position * selection)
{
    size_t size;
    for (size = 0; selection; selection = selection->next, size++);
    return size;
}

struct position *selection_sort(struct position *selection)
{
    if (selection == NULL)
        return NULL;
    size_t size = selection_size(selection);
    struct position *positions[size];
    struct position *fill = selection;
    for (size_t i = 0; i < size; fill = fill->next, i++)
        positions[i] = fill;
    qsort(positions, size, sizeof(struct position *), position_cmp);
    for (size_t i = 0; i < size - 1; i++)
        positions[i]->next = positions[i + 1];  // relink
    positions[size - 1]->next = NULL;
    return positions[0];
}

struct position *selection_uniq(struct position *selection)
{
    if (selection == NULL)
        return NULL;
    struct position *head = selection = selection_sort(selection);
    while (head->next) {
        struct position *next = head->next;
        if (position_cmp(&head, &next) == 0) {
            head->next = next->next;
            position_free(next);
        } else {
            head = next;
        }
    }
    return selection;
}

struct position *selection_diff(struct position *a, struct position *b)
{
    struct position head = { 0, 0, a };
    a = &head;
    while (a->next && b) {
        int cmp = position_cmp(&a->next, &b);
        if (cmp == 0) {
            struct position *dup = a->next;
            a->next = a->next->next;
            b = b->next;
            position_free(dup);
        } else if (cmp < 0) {
            a = a->next;
        } else if (cmp > 0) {
            b = b->next;
        }
    }
    return head.next;
}

struct position *selection(const char *code)
{
    struct position *head = NULL, *start = NULL;
    while (*code) {
        struct position *next = position_parse(&code);
        switch (*code) {
        case ':':
            code++;
            start = next;
            break;
        case '&':
            code++;  // fallthrough
        case '~':
        case '\0':
            if (start) {
                next->next = head;
                head = selection_range(start, next);
                start = NULL;
            } else {
                next->next = head;
                head = next;
            }
            break;
        }
        if (*code == '~') {
            struct position *diff = selection(++code);
            head = selection_diff(selection_uniq(head), diff);
            selection_free(diff);
            return head;
        }
    }
    return selection_uniq(head);
}

void selection_print(const struct position *s)
{
    putchar('(');
    for (; s; s = s->next) {
        printf("[%d %d]%s", s->col, s->row, s->next ? " " : "");
    }
    putchar(')');
}

int main(int argc, char **argv)
{
    struct position *s = selection(argc > 1 ? argv[1] : "");
    printf("%zu\n", selection_size(s));
    for (struct position * p = s; p; p = p->next)
        printf("%d, %d\n", p->col, p->row);
    selection_free(s);
    return 0;
}