Merge branch 'stclib:master' into modifiedHEADmodified

3 files changed, 116 insertions, 0 deletions

diff --git a/misc/examples/priorityqueues/functor.c b/misc/examples/priorityqueues/functor.c
new file mode 100644
index 00000000..e3bde1dd
--- /dev/null
+++ b/misc/examples/priorityqueues/functor.c
@@ -0,0 +1,57 @@
+// Implements c++ example: https://en.cppreference.com/w/cpp/container/priority_queue
+// Example of per-instance less-function on a single priority queue type
+//
+
+#include <stdio.h>
+
+#define i_type IPQue
+#define i_base cpque
+#define i_key int
+#define i_extend bool(*less)(const int*, const int*);
+#define i_less(x, y) c_extend()->less(x, y)
+// Note: i_less: c_extend() accessible for cpque types
+//       i_cmp: c_extend() accessible for csmap and csset types
+//       i_hash/i_eq: c_extend() accessible for cmap and cset types
+#include <stc/extend.h>
+
+void print_queue(const char* name, IPQue_ext q) {
+    // NB: make a clone because there is no way to traverse
+    // priority queue's content without erasing the queue.
+    IPQue_ext copy = {q.less, IPQue_clone(q.get)};
+    
+    for (printf("%s: \t", name); !IPQue_empty(&copy.get); IPQue_pop(&copy.get))
+        printf("%d ", *IPQue_top(&copy.get));
+    puts("");
+
+    IPQue_drop(&copy.get);
+}
+
+static bool int_less(const int* x, const int* y) { return *x < *y; }
+static bool int_greater(const int* x, const int* y) { return *x > *y; }
+static bool int_lambda(const int* x, const int* y) { return (*x ^ 1) < (*y ^ 1); }
+
+int main(void)
+{
+    const int data[] = {1,8,5,6,3,4,0,9,7,2}, n = c_arraylen(data);
+    printf("data: \t");
+    c_forrange (i, n) printf("%d ", data[i]);
+    puts("");
+
+
+    // Max priority queue
+    IPQue_ext q1 = {.less=int_less};
+    IPQue_put_n(&q1.get, data, n);
+    print_queue("q1", q1);
+
+    // Min priority queue
+    IPQue_ext minq1 = {.less=int_greater};
+    IPQue_put_n(&minq1.get, data, n);
+    print_queue("minq1", minq1);
+
+    // Using lambda to compare elements.
+    IPQue_ext q5 = {.less=int_lambda};
+    IPQue_put_n(&q5.get, data, n);
+    print_queue("q5", q5);
+
+    c_drop(IPQue, &q1.get, &minq1.get, &q5.get);
+}
diff --git a/misc/examples/priorityqueues/new_pque.c b/misc/examples/priorityqueues/new_pque.c
new file mode 100644
index 00000000..16823bb6
--- /dev/null
+++ b/misc/examples/priorityqueues/new_pque.c
@@ -0,0 +1,22 @@
+#include <stdio.h>
+
+typedef struct Point { int x, y; } Point;
+
+#define i_type PointQ
+#define i_key Point
+#define i_less(a, b) a->x < b->x || (a->x == b->x && a->y < b->y)
+#include <stc/cpque.h>
+
+
+int main(void)
+{
+    PointQ pque = c_init(PointQ, {{23, 80}, {12, 32}, {54, 74}, {12, 62}});
+    // print
+    for (; !PointQ_empty(&pque); PointQ_pop(&pque))
+    {
+        const Point *v = PointQ_top(&pque);
+        printf(" (%d,%d)", v->x, v->y);
+    }
+    puts("");
+    PointQ_drop(&pque);
+}
diff --git a/misc/examples/priorityqueues/priority.c b/misc/examples/priorityqueues/priority.c
new file mode 100644
index 00000000..18684e73
--- /dev/null
+++ b/misc/examples/priorityqueues/priority.c
@@ -0,0 +1,37 @@
+
+#include <stdio.h>
+#include <time.h>
+#include <stc/crand.h>
+
+#define i_key int64_t
+#define i_cmp -c_default_cmp  // min-heap (increasing values)
+#define i_tag i
+#include <stc/cpque.h>
+
+int main(void) {
+    intptr_t N = 10000000;
+    crand_t rng = crand_init((uint64_t)time(NULL));
+    crand_uniform_t dist = crand_uniform_init(0, N * 10);
+
+    cpque_i heap = {0};
+
+    // Push ten million random numbers to priority queue
+    printf("Push %" c_ZI " numbers\n", N);
+    c_forrange (N)
+        cpque_i_push(&heap, crand_uniform(&rng, &dist));
+
+    // push some negative numbers too.
+    c_forlist (i, int, {-231, -32, -873, -4, -343})
+        cpque_i_push(&heap, *i.ref);
+
+    c_forrange (N)
+        cpque_i_push(&heap, crand_uniform(&rng, &dist));
+
+    puts("Extract the hundred smallest.");
+    c_forrange (100) {
+        printf("%" PRId64 " ", *cpque_i_top(&heap));
+        cpque_i_pop(&heap);
+    }
+
+    cpque_i_drop(&heap);
+}