First fully working version

3 files changed, 219 insertions, 203 deletions

diff --git a/cover.c b/cover.c
new file mode 100644
index 0000000..b5b1b9c
--- /dev/null
+++ b/cover.c
@@ -0,0 +1,163 @@
+#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;
+        }
+    }
+}
diff --git a/cover.h b/cover.h
new file mode 100644
index 0000000..c8b5163
--- /dev/null
+++ b/cover.h
@@ -0,0 +1,48 @@
+#ifndef COVER_H
+#define COVER_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* insert_element(set* s, int id);
+set* new_set(int id);
+parent* new_parent(element* el);
+void insert_parent(parent** parents, element* el);
+bucket* new_bucket(set* s, int size);
+void insert_set(set* s, bucket* b);
+void remove_bucket(bucket* b);
+void detach_set(set* s);
+void attach_set(set* s, int size, bucket* b);
+void demote(set* s);
+void remove_element(element* el);
+void remove_parents(element* el, parent** parents);
+void greedy(bucket* head, parent** parents);
+#endif
diff --git a/main.c b/main.c
index c8b0e51..9e9f837 100644
--- a/main.c
+++ b/main.c
@@ -1,202 +1,6 @@
 #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(parent* p) {
-    parent* temp;
-    while (temp = p) {
-        remove_element(temp->pos);
-        p = p->next;
-        free(temp);
-    }
-}
-
-void remove_bucket(bucket* b) {
-    if (b->prev) {
-        b->prev->next = b->next;
-    }
-    if (b->next) {
-        b->next->prev = b->prev;
-    }
-    free(b);
-}
-
-void demote(set* s) {
-    detach_set(s);
-    int size = s->bucket->size - 1;
-    bucket *;
-    if (!s->bucket->head) {
-        if(s->bucket->prev) {
-            remove_bucket(s->bucket);
-        } else {
-            attach
-        }
-
-        remove_bucket(s->bucket);
-    }
-
-    if (size == 0) {
-        free(s);
-    }
-
-    bucket* attach_point;
-    lse {
-        if(s->bucket->
-    }
-    if (s->bucket->prev) {
-        attach_point = s->bucket->prev;    
-    } else if (s->bucket->head) {
-        attach_point = s->bucket;
-    } else {
-
-    }
-        remove_bucket(s->bucket);
-    attach_set(s, size, 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;
-    }
-}
-
-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;
-        nb->next->prev = nb;
-    }
-}
-
-void greedy(bucket* head, parent** parents) {
-    bucket* b = head;
-    element* current = b->head->head;
-    element* temp;
-    while (1) {
-        temp = current;
-        if (current->next) {
-            current = current->next;
-        } else if (current->set->next) {
-            current = current->set->next->head;
-        } else if (current->set->bucket->prev) {
-           current = current->set->bucket->prev->head->head; 
-        } else {
-            remove_parents(parents[temp->id]);
-            break;
-        }
-        remove_parents(parents[temp->id]);
-    }
-}
+#include "cover.h"
 
 int main(int argc, char* argv[]) {
     FILE* file = fopen(argv[1], "r");
@@ -218,7 +22,7 @@ int main(int argc, char* argv[]) {
             fscanf(file, "%d", &current_element);
             element* el = insert_element(s, current_element);
             insert_parent(parents, el);
-            if (current_bucket && current_bucket->size < j) {
+            if (current_bucket && current_bucket->size < (j + 1)) {
                current_bucket = current_bucket->next;
             }
         }
@@ -227,6 +31,7 @@ int main(int argc, char* argv[]) {
             b->prev = head;
             if (head) {
                 head->next = b;
+                head = b;
             } else {
                 head = tail = b;
             }
@@ -235,13 +40,13 @@ int main(int argc, char* argv[]) {
         } 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;     
-            }
+            b->prev = current_bucket->prev;
             current_bucket->prev = b;
+            if (!b->prev) {
+                tail = b;
+            }
         }
     }
+    greedy(head, parents);
     return 0;
 }