generic pq

3 files changed, 128 insertions, 21 deletions

diff --git a/tests/test_pque.c b/tests/test_pque.c
index a6565bd..6503174 100644
--- a/tests/test_pque.c
+++ b/tests/test_pque.c
@@ -1,41 +1,64 @@
 #include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
-#include "priority_queue.h"
+#include "pqueue.h"
+#include "basic_traits.h"
 
-int intcmp(void *_a, void *_b) {
-    int a = *(int *)_a;
-    int b = *(int *)_b;
-    if (a < b) return 1;
-    if (a > b) return -1;
-    return 0;
+typedef Int MinInt;
+
+int MinInt_cmp(Int *lhs, Int *rhs) {
+    return -Int_cmp(lhs, rhs);
 }
 
+VECTOR_DEF(MinInt);
+VECTOR_IMPL(MinInt);
+
+PQUEUE_DEF(MinInt);
+PQUEUE_IMPL(MinInt);
+
 int main() {
-    printf("[TEST] pque\n");
-    priority_queue_t pq;
-    init_priority_queue(&pq, 3, sizeof(int), intcmp);
+    printf("[TEST] pqueue\n");
+
+    IntPQueue pq;
+    IntPQueue_init(&pq);
     int elems[10] = {1, 3, 2, 4, 6, 5, 9, 7, 8, 10};
     for (int i = 0; i < 10; i++) {
         int e = elems[i];
-        priority_queue_push(&pq, &e);
+        IntPQueue_push(&pq, &e);
     }
-    for (int i = 1; i < 11; i++) {
-        int *top = priority_queue_top(&pq);
+    for (int i = 10; i >= 1; i--) {
+        int *top = IntPQueue_top(&pq);
         assert(i == *top);
-        priority_queue_pop(&pq);
+        IntPQueue_pop(&pq);
     }
-    assert(priority_queue_top(&pq) == NULL);
-    int elems2[10] = {10, 8, 7, 9, 5, 6, 4, 2, 3, 1};
-    int expected[10] = {10, 8, 7, 7, 5, 5, 4, 2, 2, 1};
+    assert(IntPQueue_top(&pq) == NULL);
+
+
+    MinIntPQueue minpq;
+    MinIntPQueue_init(&minpq);
+    for (int i = 0; i < 10; i++) {
+        int e = elems[i];
+        MinIntPQueue_push(&minpq, &e);
+    }
+    for (int i = 1; i <= 10; i++) {
+        int *top = MinIntPQueue_top(&minpq);
+        assert(i == *top);
+        MinIntPQueue_pop(&minpq);
+    }
+    assert(MinIntPQueue_top(&minpq) == NULL);
+    MinIntVector_free(&minpq.vec);
+
+    int elems2[10] = {-10, -8, -7, -9, -5, -6, -4, -2, -3, -1};
+    int expected[10] = {-10, -8, -7, -7, -5, -5, -4, -2, -2, -1};
     for (int i = 0; i < 10; i++) {
         int e = elems2[i];
-        priority_queue_push(&pq, &e);
-        int *top = priority_queue_top(&pq);
+        IntPQueue_push(&pq, &e);
+        int *top = IntPQueue_top(&pq);
         assert(*top == expected[i]);
     }
-    free(pq.buf);
-    printf("[PASS] pque\n");
+    IntVector_free(&pq.vec);
+    printf("[PASS] pqueue\n");
     return 0;
 }
diff --git a/tests/test_pqueue.c b/tests/test_pqueue.c
new file mode 100644
index 0000000..6503174
--- /dev/null
+++ b/tests/test_pqueue.c
@@ -0,0 +1,64 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "pqueue.h"
+#include "basic_traits.h"
+
+typedef Int MinInt;
+
+int MinInt_cmp(Int *lhs, Int *rhs) {
+    return -Int_cmp(lhs, rhs);
+}
+
+VECTOR_DEF(MinInt);
+VECTOR_IMPL(MinInt);
+
+PQUEUE_DEF(MinInt);
+PQUEUE_IMPL(MinInt);
+
+int main() {
+    printf("[TEST] pqueue\n");
+
+    IntPQueue pq;
+    IntPQueue_init(&pq);
+    int elems[10] = {1, 3, 2, 4, 6, 5, 9, 7, 8, 10};
+    for (int i = 0; i < 10; i++) {
+        int e = elems[i];
+        IntPQueue_push(&pq, &e);
+    }
+    for (int i = 10; i >= 1; i--) {
+        int *top = IntPQueue_top(&pq);
+        assert(i == *top);
+        IntPQueue_pop(&pq);
+    }
+    assert(IntPQueue_top(&pq) == NULL);
+
+
+    MinIntPQueue minpq;
+    MinIntPQueue_init(&minpq);
+    for (int i = 0; i < 10; i++) {
+        int e = elems[i];
+        MinIntPQueue_push(&minpq, &e);
+    }
+    for (int i = 1; i <= 10; i++) {
+        int *top = MinIntPQueue_top(&minpq);
+        assert(i == *top);
+        MinIntPQueue_pop(&minpq);
+    }
+    assert(MinIntPQueue_top(&minpq) == NULL);
+    MinIntVector_free(&minpq.vec);
+
+    int elems2[10] = {-10, -8, -7, -9, -5, -6, -4, -2, -3, -1};
+    int expected[10] = {-10, -8, -7, -7, -5, -5, -4, -2, -2, -1};
+    for (int i = 0; i < 10; i++) {
+        int e = elems2[i];
+        IntPQueue_push(&pq, &e);
+        int *top = IntPQueue_top(&pq);
+        assert(*top == expected[i]);
+    }
+    IntVector_free(&pq.vec);
+    printf("[PASS] pqueue\n");
+    return 0;
+}
diff --git a/tests/test_sort.c b/tests/test_sort.c
new file mode 100644
index 0000000..d996df2
--- /dev/null
+++ b/tests/test_sort.c
@@ -0,0 +1,20 @@
+#include "sort.c"
+
+#include <assert.h>
+#include <stdio.h>
+
+int main() {
+    printf("[TEST] sort\n");
+
+    int arr[] = {2,4,5,7,4,6,7,8,8,5,4};
+    int arrlen = sizeof(arr) / sizeof(int);
+    Int_qsort(arr, arrlen);
+    for (int i = 0; i < arrlen - 1; i++) {
+        assert(arr[i] <= arr[i+1]);
+    }
+    Int_qsort(arr, arrlen);
+    for (int i = 0; i < arrlen - 1; i++) {
+        assert(arr[i] <= arr[i+1]);
+    }
+    printf("[PASS] sort\n");
+}