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

struct node {
    struct node *next;
    int value;
};

typedef int (*remove_fn) (const struct node *n);

void remove_if_twostar (struct node **first, remove_fn cond, int *count)
{
    struct node **prev_next = first;
    struct node *cur = *first;
    
    while (cur) {
        if (cond(cur)) {
            (*count)++;
            *prev_next = cur->next;
            cur = cur->next;
        } else {
            prev_next = &cur->next;
            cur = cur->next;
        }
    }
}

void remove_if_onestar (struct node **first, remove_fn cond, int *count)
{
    struct node *prev = NULL;
    struct node *cur = *first;
    
    while (cur) {
        if (cond(cur)) {
            (*count)++;
            if (prev) {
                prev->next = cur->next;
            } else {
                *first = cur->next;
            }
            cur = cur->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
}

void build_twostar (struct node **first, struct node *nodes, size_t num_nodes)
{
    struct node **prev_next = first;
    
    for (size_t i = 0; i < num_nodes; i++) {
        *prev_next = &nodes[i];
        prev_next = &nodes[i].next;
    }
    
    *prev_next = NULL;
}

void build_onestar (struct node **first, struct node *nodes, size_t num_nodes)
{
    if (num_nodes == 0) {
        *first = NULL;
    } else {
        *first = &nodes[0];
        
        for (size_t i = 0; i < num_nodes - 1; i++) {
            nodes[i].next = &nodes[i + 1];
        }
        
        nodes[num_nodes - 1].next = NULL;
    }
}

int remove_func (const struct node *n)
{
    return rand() > RAND_MAX / 2;
}

int main (int argc, char *argv[])
{
    if (argc != 3) {
        printf("Need two arguments.\n");
        return 1;
    }
    
    size_t num_nodes = atoi(argv[1]);
    int num_iter = atoi(argv[2]);
    
    struct node *nodes = malloc(num_nodes * sizeof(nodes[0]));
    
    int all_count = 0;
    
    for (int i = 0; i < num_iter; i++) {
        struct node *first;
        build_onestar(&first, nodes, num_nodes);
        remove_if_onestar(&first, remove_func, &all_count);
    }
    
    printf("Total removed: %d\n", all_count);
    
    return 0;
}