aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--cover.c163
-rw-r--r--cover.h48
-rw-r--r--main.c211
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;
}
generated by cgit v1.2.3-70-g09d2 (git 2.52.0) at 2025-12-21 11:54:07 +0000