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

element* insert_element(set* s, int id) {
    element* el = malloc(sizeof(element));
    el->id = id;
    el->set = s;
    el->prev = el->next = NULL;
    if (s->head) {
        el->next = s->head;
        s->head->prev = el;
    }
    s->head = el;
    return el;
}

set* new_set(int id) {
    set* s = malloc(sizeof(set));
    s->id = id;
    s->prev = s->next = NULL;
    s->head = NULL;
    s->bucket = NULL;
    return s;
}

parent* new_parent(element* el) {
    parent* p = malloc(sizeof(parent));
    p->pos = el;
    p->next = NULL;
    return p;
}

void insert_parent(parent** parents, element* el) {
    int id = el->id;
    parent* p  = new_parent(el);
    if (parents[id]) {
        p->next = parents[id];
    }
    parents[id] = p;
}

bucket* new_bucket(set* s, int size) {
    bucket* b = malloc(sizeof(bucket));
    b->size = size;
    b->prev = b->next = NULL;
    b->head = s;
    s->bucket = b;
    s->prev = s->next = NULL;
    return b;
}

void insert_set(set* s, bucket* b) {
    s->next = b->head;
    s->prev = NULL;
    s->bucket = b;
    b->head->prev = s;
    b->head = s;
}

void remove_bucket(bucket* b) {
    if (b->prev) {
        b->prev->next = b->next;
    }
    if (b->next) {
        b->next->prev = b->prev;
    }
    free(b);
}

void detach_set(set* s) {
    if (s->next) {
        s->next->prev = s->prev;
    }
    if (s->prev) {
        s->prev->next = s->next;
    } else {
        s->bucket->head = s->next;
    }
    s->prev = s->next = NULL;
    s->bucket = NULL;
}

void attach_set(set* s, int size, bucket* b) {
    if (b->size == size) {
        insert_set(s, b);
    } else {
        bucket* nb =  new_bucket(s, size);
        nb->prev = b;
        nb->next = b->next;
        nb->prev->next = nb;
        if (nb->next) {
            nb->next->prev = nb;
        }
    }
}

void demote(set* s) {
    bucket* b = s->bucket;
    detach_set(s);
    int size = b->size - 1;
    if (size == 0) {
        free(s);
    } else if (!b->prev) {
        bucket* nb = new_bucket(s, size);
        nb->next = b;
        b->prev = nb;
    } else {
        attach_set(s, size, b->prev);
    }
    if (!b->head) {
        remove_bucket(b);
    }
}

void remove_element(element* el) {
    if (el->next) {
        el->next->prev = el->prev;
    }
    if (el->prev) {
        el->prev->next = el->next;
    } else {
        el->set->head = el->next;
    }
    demote(el->set);
    free(el);
}

void remove_parents(element* el, parent** parents) {
    parent* current = parents[el->id];
    parent* temp;
    while (current) {
        temp = current;
        if (current->pos != el) {
            remove_element(current->pos);
        }
        current = current->next; 
        free(temp);
    }

}

void greedy(bucket* head, parent** parents) {
    bucket* b = head;
    element* current = b->head->head;
    printf("%d\n", current->set->id);
    element* temp;
    while (1) {
        temp = current;
        remove_parents(current, parents);
        if (current->next) {
            current = current->next;
        } else if (current->set->next) {
            current = current->set->next->head;
            printf("%d\n", current->set->id);
        } else if (current->set->bucket->prev) {
            current = current->set->bucket->prev->head->head;
            printf("%d\n", current->set->id);
        } else {
            break;
        }
    }
}