aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <[email protected]>2018-01-03 00:38:28 +0100
committerErik Liodden <[email protected]>2018-01-03 00:47:05 +0100
commit3e71367b2b4ff9350ce5e7d7da1837ce93be212d (patch)
treeb3699b46d9ccc3722d244df460bdc4c8bc644920
parent0af0ccdea375ebdb786d6001c94ab75ed194aa7f (diff)
downloadalgdat-3e71367b2b4ff9350ce5e7d7da1837ce93be212d.tar.gz
add oving 2
this is the solution to oving 2. it is a heap of queues and should work(tm).
-rw-r--r--.gitignore1
-rw-r--r--Makefile2
-rw-r--r--oving2.c115
3 files changed, 117 insertions, 1 deletions
diff --git a/.gitignore b/.gitignore
index 06d49d8..0cf5ae3 100644
--- a/.gitignore
+++ b/.gitignore
@@ -205,3 +205,4 @@ src/prog-debug
test/
oving1
+oving2
diff --git a/Makefile b/Makefile
index 05c425e..2b4168d 100644
--- a/Makefile
+++ b/Makefile
@@ -3,7 +3,7 @@ CFLAGS=-O2 -Wall -Wextra -Wvla --std=c99
CC=gcc
AR=ar
-PROG= oving1
+PROG= oving1 oving2
LIB_OBJS=stack.o queue.o llist.o io.o misc.o sort.o heap.o
diff --git a/oving2.c b/oving2.c
new file mode 100644
index 0000000..2e48b3a
--- /dev/null
+++ b/oving2.c
@@ -0,0 +1,115 @@
+/*
+ * oving2.c
+ * implements TDT4120 - AlgDat oving 2
+ *
+ * Erik Liodden
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "structure.h"
+
+struct node {
+ char c;
+ int pos;
+};
+
+void free_q(void *qp)
+{
+ struct queue *q = (struct queue *)qp;
+ queue_dispose(q);
+}
+
+int comp_q(const void *qp1, const void *qp2)
+{
+ struct queue *q1 = (struct queue *)qp1;
+ struct queue *q2 = (struct queue *)qp2;
+ return queue_length(q2) - queue_length(q1);
+}
+
+/* read_input: read from stdin to buffer */
+void read_input(struct heap *h)
+{
+ struct queue q;
+ struct node node;
+ char *buf, *str, *token;
+ size_t len;
+
+ heap_init(h, sizeof(struct queue), &free_q, &comp_q);
+ while (!feof(stdin)) {
+ buf = fgetln(stdin, &len);
+ if (len < 4)
+ continue;
+ queue_init(&q, sizeof(struct node), NULL);
+ node.c = buf[0];
+ str = strndup(buf + 2, len - 2);
+ token = strtok(str, ",");
+ while(token != NULL) {
+ node.pos = atoi(token);
+ queue_enqueue(&q, &node);
+ token = strtok(NULL, ",");
+ }
+ free(str);
+ heap_max_heap_insert(h, &q);
+ }
+}
+
+void merge(struct queue *q, struct queue *p1, struct queue *p2)
+{
+ struct node n1, n2;
+
+ while(queue_length(p1) && queue_length(p2)) {
+ queue_peek(p1, &n1);
+ queue_peek(p2, &n2);
+ if (n1.pos <= n2.pos) {
+ queue_dequeue(p1, &n1);
+ queue_enqueue(q, &n1);
+ } else {
+ queue_dequeue(p2, &n2);
+ queue_enqueue(q, &n2);
+ }
+ }
+ while(queue_length(p1)) {
+ queue_dequeue(p1, &n1);
+ queue_enqueue(q, &n1);
+ }
+ while(queue_length(p2)) {
+ queue_dequeue(p2, &n2);
+ queue_enqueue(q, &n2);
+ }
+}
+
+void merge_lines(struct heap *h)
+{
+ struct queue q, p1, p2;
+
+ while(heap_length(h) > 1) {
+ queue_init(&q, sizeof(struct node), NULL);
+ heap_extract_max(h, &p1);
+ heap_extract_max(h, &p2);
+ merge(&q, &p1, &p2);
+ queue_dispose(&p1);
+ queue_dispose(&p2);
+ heap_max_heap_insert(h, &q);
+ }
+}
+
+int main(void)
+{
+ struct heap h;
+ struct queue q;
+ struct node n;
+
+ read_input(&h);
+ merge_lines(&h);
+ heap_extract_max(&h, &q);
+ while(queue_length(&q)) {
+ queue_dequeue(&q, &n);
+ printf("%c", n.c);
+ }
+ printf("\n");
+ queue_dispose(&q);
+ heap_dispose(&h);
+ return 0;
+}