Initial commit

1 files changed, 168 insertions, 0 deletions

diff --git a/main.c b/main.c
new file mode 100644
index 0000000..cf21b4d
--- /dev/null
+++ b/main.c
@@ -0,0 +1,168 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef struct set set;
+typedef struct element element;
+typedef struct bucket bucket;
+typedef struct parent parent;
+
+struct element {
+    int id;
+    element* next;
+    element* prev;
+    set* set;
+};
+
+struct bucket {
+    int size;
+    bucket* prev;
+    bucket* next;
+    set* head;
+};
+
+struct set {
+    int id;
+    set* next;
+    set* prev;
+    element* head;
+    bucket* bucket;
+};
+
+struct parent {
+    element* pos;
+    parent* next;
+};
+
+element* new_element(int id, set* s) {
+    element* el = malloc(sizeof(element));
+    el->id = id;
+    el->set = s;
+    el->prev = el->next = NULL;
+    return el;
+}
+
+element* insert_element(set* s, int id) {
+    element* el = new_element(id, s);
+    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;
+    return b;
+}
+
+void insert_set(set* s, bucket* b) {
+    s->next = b->head;
+    b->head->prev = s;
+    b->head = s;
+}
+
+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(int id, parent** parents) {
+    for(parent* p=parents[id]; p != NULL; p = p->next) {
+        remove_element(p->pos);
+        free(p);
+    }
+}
+
+void greedy(bucket* head, parent** parents) {
+    bucket* b = head;
+    for(set* s=b->head; s != NULL; s = s->next) {
+        for (element* el = s->head; el != NULL; el = el->next) {
+            remove_parents(el->id, parents);
+        }
+    }
+}
+
+int main(int argc, char* argv[]) {
+    FILE* file = fopen(argv[1], "r");
+    int n_sets, n_elements = 0;
+    int current_element = 0;
+    bucket *tail, *head = NULL;
+    fscanf(file, "%d %d", &n_sets, &n_elements);
+    parent** parents = malloc(n_elements*sizeof(parent*));
+    for (int element_id = 0; element_id < n_elements; element_id++) {
+        parents[element_id] = NULL;
+    }
+
+    for(int current_set = 0; current_set < n_sets; current_set++) {
+        fscanf(file, "%d", &n_elements);
+        set* s = new_set(current_set);
+        bucket* current_bucket = tail;
+        int j;
+        for(j = 0; j < n_elements; j++) {
+            fscanf(file, "%d", &current_element);
+            element* el = insert_element(s, current_element);
+            insert_parent(parents, el);
+            if (current_bucket && current_bucket->size < j) {
+               current_bucket = current_bucket->next;
+            }
+        }
+        if (!current_bucket) {
+            bucket* b = new_bucket(s, j);
+            b->prev = head;
+            if (head) {
+                head->next = b;
+            } else {
+                head = tail = b;
+            }
+        } else if (current_bucket->size == j) {
+            insert_set(s, current_bucket);
+        } else if (current_bucket->size > j) {
+            bucket* b =  new_bucket(s, j);
+            b->next = current_bucket;
+            if (current_bucket->prev) {
+                b->prev = current_bucket->prev;
+            } else {
+                tail = b;     
+            }
+            current_bucket->prev = b;
+        }
+    }
+    return 0;
+}