Changed cpque declaration to using_cpque(X, Value, valueCompare), and valueCompare optional: more consistent with STC conventions.

9 files changed, 77 insertions, 79 deletions

diff --git a/README.md b/README.md
index 9c26dc70..1af76f2f 100644
--- a/README.md
+++ b/README.md
@@ -1,7 +1,7 @@
 ![Standard Template Containers](docs/pics/containers.jpg)

 

-STC - Standard Template Containers

-==================================

+STC - Standard Template Containers for C

+========================================

 

 Introduction

 ------------

diff --git a/benchmarks/cpque_benchmark.cpp b/benchmarks/cpque_benchmark.cpp
index d3c00803..c8d327ff 100644
--- a/benchmarks/cpque_benchmark.cpp
+++ b/benchmarks/cpque_benchmark.cpp
@@ -5,7 +5,7 @@
 #include <stc/cpque.h>

 

 using_cvec(f, float);

-using_cpque(f, cvec_f, >);

+using_cpque(f, cvec_f, -c_default_compare);

 

 int main()

 {

diff --git a/docs/cpque_api.md b/docs/cpque_api.md
index 313a0e92..822b4ad5 100644
--- a/docs/cpque_api.md
+++ b/docs/cpque_api.md
@@ -10,13 +10,12 @@ See the c++ class [std::priority_queue](https://en.cppreference.com/w/cpp/contai
 ```c
 #include <stc/cpque.h>
 
-using_cpque(X, ctype);                     // default dir = `<` : max-heap
-using_cpque(X, ctype, dir);                // uses valueCompare from ctype
-using_cpque(X, ctype, dir, valueCompare);
+using_cpque(X, ctype);                // uses valueCompare from ctype
+using_cpque(X, ctype, valueCompare);
 ```
 The macro `using_cpque()` must be instantiated in the global scope. **cpque** uses normally **cvec_X**
-or **cdeq_X** as underlying implementation, specified as `ctype`. The *dir* must be given as
-`<` or `>`, specifying *max-heap* or *min-heap* for the priority queue.
+or **cdeq_X** as underlying implementation, specified as `ctype`. The *valueCompare* can be specified
+to control the order in the priority queue.
 
 By default, the function *`ctype`_value_compare(x, y)* from the underlying vector type is used for
 comparing values (priorities). `X` is a type tag name and will affect the names of all cpque types and methods.
@@ -61,7 +60,7 @@ cpque_X_value_t         cpque_X_value_clone(cpque_X_value_t val);
 #include <stdio.h>
 
 using_cvec(i, int64_t);
-using_cpque(i, cvec_i, >); // adaptor type, '>' = min-heap
+using_cpque(i, cvec_i, -c_default_compare); // min-heap
 
 int main()
 {
diff --git a/examples/cpque.c b/examples/cpque.c
index ae869832..f9de44f1 100644
--- a/examples/cpque.c
+++ b/examples/cpque.c
@@ -4,12 +4,12 @@
 // Implements c++ example: https://en.cppreference.com/w/cpp/container/priority_queue

 

 using_cvec(i, int);

-using_cpque(imax, cvec_i);

-using_cpque(imin, cvec_i, >);

+#define imix_less(x, y) ((*(x) ^ 1) < (*(y) ^ 1))

+#define imix_cmp(x, y) c_less_compare(imix_less, x, y)

 

-#define myless(left, right) ((left ^ 1) < (right ^ 1))

-static int cmp(const int *x, const int *y) { return myless(*y, *x) - myless(*x, *y); }

-using_cpque(imix, cvec_i, <, cmp);

+using_cpque(imax, cvec_i);

+using_cpque(imin, cvec_i, -c_default_compare);

+using_cpque(imix, cvec_i, imix_cmp);

 

 #define PRINT_Q(Q) \

     void print_##Q(Q q) { \

@@ -37,13 +37,13 @@ int main() {
 

     print_cpque_imax(q);

 

-    cpque_imin q2 = cpque_imin_init(); 

+    cpque_imin q2 = cpque_imin_init();

     cpque_imin_emplace_n(&q2, data, c_arraylen(data));

 

     print_cpque_imin(q2);

 

-    // Using myless cmp to compare elements.

-    cpque_imix q3 = cpque_imix_init(); 

+    // Using imix_less to compare elements.

+    cpque_imix q3 = cpque_imix_init();

 

     c_forrange (n, c_arraylen(data))

         cpque_imix_push(&q3, n);

diff --git a/examples/inits.c b/examples/inits.c
index 23c7b551..26518e33 100644
--- a/examples/inits.c
+++ b/examples/inits.c
@@ -17,7 +17,7 @@ inline static int ipair_compare(const ipair_t* a, const ipair_t* b) {
 using_cvec(ip, ipair_t, ipair_compare);

 using_clist(ip, ipair_t, ipair_compare);

 using_cvec(f, float);

-using_cpque(f, cvec_f, >);

+using_cpque(f, cvec_f);

 

 int main(void)

 {

@@ -34,7 +34,7 @@ int main(void)
     cpque_f_make_heap(&floats);

     c_emplace_items(&floats, cpque_f, {40.0f, 20.0f, 50.0f, 30.0f, 10.0f});

 

-    // sorted:

+    puts("\npop and show high priorites first:");

     while (! cpque_f_empty(floats)) {

         printf("%.1f ", *cpque_f_top(&floats));

         cpque_f_pop(&floats);

diff --git a/examples/priority.c b/examples/priority.c
index 10e2f32a..ed7db584 100644
--- a/examples/priority.c
+++ b/examples/priority.c
@@ -7,7 +7,7 @@
 #include <stc/crandom.h>

 

 using_cvec(i, int64_t);

-using_cpque(i, cvec_i, >); // min-heap (increasing values)

+using_cpque(i, cvec_i, -c_default_compare); // min-heap (increasing values)

 

 int main() {

     size_t N = 10000000;

diff --git a/examples/stc_astar.c b/examples/stc_astar.c
index d096c9fc..c22af8a8 100644
--- a/examples/stc_astar.c
+++ b/examples/stc_astar.c
@@ -17,42 +17,42 @@ typedef struct {
 } MazePoint;

 

 MazePoint

-mpoint_init(int x, int y, int width)

+mpnt_init(int x, int y, int width)

 {

     MazePoint p = { x, y, 0, width }; return p;

 }

 

 int

-mpoint_compare_priority(const MazePoint* a, const MazePoint* b)

+mpnt_compare_priority(const MazePoint* a, const MazePoint* b)

 {

     //return 0; // NB! gives 14 steps shorter path!? hmm..

-    return (a->priorty > b->priorty) - (a->priorty < b->priorty);

+    return c_default_compare(&b->priorty, &a->priorty); // note: high priority is low cost

 }

 

 int

-mpoint_equal(MazePoint* a, MazePoint* b)

+mpnt_equal(MazePoint* a, MazePoint* b)

 {

     return a->x == b->x && a->y == b->y;

 }

 

 MazePoint

-mpoint_from(cstr maze, const char* c, int width)

+mpnt_from(cstr maze, const char* c, int width)

 {

     int index = cstr_find(maze, c);

-    return mpoint_init(index % width, index / width, width);

+    return mpnt_init(index % width, index / width, width);

 }

 

 int

-mpoint_index(const MazePoint* p)

+mpnt_index(const MazePoint* p)

 {

     return p->x + p->width * p->y;

 }

 

 int

-mpoint_key_compare(const MazePoint* a, const MazePoint* b)

+mpnt_key_compare(const MazePoint* a, const MazePoint* b)

 {

-    int i = mpoint_index(a);

-    int j = mpoint_index(b);

+    int i = mpnt_index(a);

+    int j = mpnt_index(b);

     return (i > j) - (i < j);

 }

 

@@ -66,29 +66,29 @@ typedef struct {
     MazePoint b;

 } MazeStep;

 

-using_cdeq(mp, MazePoint, mpoint_compare_priority);

-using_cpque(mp, cdeq_mp, >);

-using_csmap(ms, MazePoint, MazePoint, mpoint_key_compare); // step

-using_csmap(mc, MazePoint, int, mpoint_key_compare); // cost

+using_cdeq(pnt, MazePoint, c_no_compare);

+using_cpque(pnt, cdeq_pnt, mpnt_compare_priority);

+using_csmap(step, MazePoint, MazePoint, mpnt_key_compare);

+using_csmap(cost, MazePoint, int, mpnt_key_compare);

 

 

-cdeq_mp

+cdeq_pnt

 astar(cstr maze, int width)

 {

-    MazePoint start = mpoint_from(maze, "@", width);

-    MazePoint goal = mpoint_from(maze, "!", width);

-    cpque_mp frontier = cpque_mp_init();

-    csmap_ms came_from = csmap_ms_init();

-    csmap_mc cost_so_far = csmap_mc_init();

+    MazePoint start = mpnt_from(maze, "@", width);

+    MazePoint goal = mpnt_from(maze, "!", width);

+    cpque_pnt frontier = cpque_pnt_init();

+    csmap_step came_from = csmap_step_init();

+    csmap_cost cost_so_far = csmap_cost_init();

 

-    cpque_mp_push(&frontier, start);

-    csmap_mc_emplace(&cost_so_far, start, 0);

+    cpque_pnt_push(&frontier, start);

+    csmap_cost_insert(&cost_so_far, start, 0);

 

-    while (!cpque_mp_empty(frontier))

+    while (!cpque_pnt_empty(frontier))

     {

-        MazePoint current = *cpque_mp_top(&frontier);

-        cpque_mp_pop(&frontier);

-        if (mpoint_equal(&current, &goal))

+        MazePoint current = *cpque_pnt_top(&frontier);

+        cpque_pnt_pop(&frontier);

+        if (mpnt_equal(&current, &goal))

             break;

         MazePoint deltas[] = {

             { -1, +1, 0, width }, { 0, +1, 0, width }, { 1, +1, 0, width },

@@ -99,33 +99,33 @@ astar(cstr maze, int width)
         c_forrange (i, c_arraylen(deltas))

         {

             MazePoint delta = deltas[i];

-            MazePoint next = mpoint_init(current.x + delta.x, current.y + delta.y, width);

-            int new_cost = *csmap_mc_at(&cost_so_far, current);

-            if (maze.str[mpoint_index(&next)] != '#')

+            MazePoint next = mpnt_init(current.x + delta.x, current.y + delta.y, width);

+            int new_cost = *csmap_cost_at(&cost_so_far, current);

+            if (maze.str[mpnt_index(&next)] != '#')

             {

-                csmap_mc_value_t* cost = csmap_mc_find(&cost_so_far, next).ref;

+                csmap_cost_value_t* cost = csmap_cost_find(&cost_so_far, next).ref;

                 if (!cost || new_cost < cost->second)

                 {

-                    csmap_mc_emplace_or_assign(&cost_so_far, next, new_cost); // update (put)

+                    csmap_cost_put(&cost_so_far, next, new_cost); // update

                     next.priorty = new_cost + abs(goal.x - next.x) + abs(goal.y - next.y);

-                    cpque_mp_push(&frontier, next);

-                    csmap_ms_emplace_or_assign(&came_from, next, current);

+                    cpque_pnt_push(&frontier, next);

+                    csmap_step_put(&came_from, next, current);

                 }

             }

         }

     }

     MazePoint current = goal;

-    cdeq_mp path = cdeq_mp_init();

+    cdeq_pnt path = cdeq_pnt_init();

 

-    while(!mpoint_equal(&current, &start))

+    while(!mpnt_equal(&current, &start))

     {

-        cdeq_mp_push_front(&path, current);

-        current = *csmap_ms_at(&came_from, current);

+        cdeq_pnt_push_front(&path, current);

+        current = *csmap_step_at(&came_from, current);

     }

-    cdeq_mp_push_front(&path, start);

-    cpque_mp_del(&frontier);

-    csmap_ms_del(&came_from);

-    csmap_mc_del(&cost_so_far);

+    cdeq_pnt_push_front(&path, start);

+    cpque_pnt_del(&frontier);

+    csmap_step_del(&came_from);

+    csmap_cost_del(&cost_so_far);

     return path;

 }

 

@@ -157,14 +157,14 @@ main(void)
         "#   #                   #           #               #               #   #\n"

         "#########################################################################\n");

     int width = cstr_find(maze, "\n") + 1;

-    cdeq_mp path = astar(maze, width);

+    cdeq_pnt path = astar(maze, width);

 

-    printf("length: %zu\n", cdeq_mp_size(path));

+    printf("length: %zu\n", cdeq_pnt_size(path));

 

-    c_foreach (it, cdeq_mp, path)

-        maze.str[mpoint_index(it.ref)] = 'o';

+    c_foreach (it, cdeq_pnt, path)

+        maze.str[mpnt_index(it.ref)] = 'x';

 

     printf("%s", maze.str);

     cstr_del(&maze);

-    cdeq_mp_del(&path);

+    cdeq_pnt_del(&path);

 }
\ No newline at end of file
diff --git a/stc/ccommon.h b/stc/ccommon.h
index 29790333..ec01d731 100644
--- a/stc/ccommon.h
+++ b/stc/ccommon.h
@@ -65,6 +65,7 @@
 #define c_container_of(ptr, type, member) \

         ((type *)((char *)(ptr) - offsetof(type, member)))

 

+#define c_struct(S)             typedef struct S S; struct S

 #define c_new(...)              c_MACRO_OVERLOAD(c_new, __VA_ARGS__)

 #define c_new_1(T)              ((T *) c_malloc(sizeof(T)))

 #define c_new_2(T, n)           ((T *) c_malloc(sizeof(T)*(n)))

@@ -78,9 +79,10 @@
 #define c_swap(T, x, y)         do { T _c_t = x; x = y; y = _c_t; } while (0)

 #define c_arraylen(a)           (sizeof (a)/sizeof (a)[0])

 

-#define c_default_compare(x, y) (c_default_less(y, x) - c_default_less(x, y))

+#define c_default_compare(x, y) c_less_compare(c_default_less, x, y)

 #define c_default_less(x, y)    (*(x) < *(y))

 #define c_no_compare(x, y)      (assert(!"c_no_compare() called"), 0)

+#define c_less_compare(less, x, y) (less(y, x) - less(x, y))

 

 #define c_default_equals(x, y)  (*(x) == *(y))

 #define c_trivial_equals(x, y)  (memcmp(x, y, sizeof *(x)) == 0)

diff --git a/stc/cpque.h b/stc/cpque.h
index abb14565..8e08724f 100644
--- a/stc/cpque.h
+++ b/stc/cpque.h
@@ -26,7 +26,7 @@
     #include <stc/crandom.h>

     #include <stc/cpque.h>

     using_cvec(f, float);

-    using_cpque(f, cvec_f, >); // min-heap (increasing values)

+    using_cpque(f, cvec_f, -c_default_compare); // min-heap (increasing values)

 

     int main() {

         stc64_t rng = stc64_init(1234);

@@ -52,12 +52,9 @@
 #define using_cpque(...) c_MACRO_OVERLOAD(using_cpque, __VA_ARGS__)

 

 #define using_cpque_2(X, ctype) \

-    using_cpque_3(X, ctype, <)

+    using_cpque_3(X, ctype, ctype##_value_compare)

 

-#define using_cpque_3(X, ctype, cmpOpr) /* cmpOpr: < or > */ \

-    using_cpque_4(X, ctype, cmpOpr, ctype##_value_compare)

-

-#define using_cpque_4(X, ctype, cmpOpr, valueCompare) \

+#define using_cpque_3(X, ctype, valueCompare) \

     typedef ctype##_t cpque_##X; \

     typedef ctype##_value_t cpque_##X##_value_t; \

     typedef ctype##_rawvalue_t cpque_##X##_rawvalue_t; \

@@ -94,7 +91,7 @@
     STC_API void \

     cpque_##X##_emplace_n(cpque_##X *self, const cpque_##X##_rawvalue_t arr[], size_t size); \

 \

-    _c_implement_cpque(X, ctype, cmpOpr, valueCompare) \

+    _c_implement_cpque(X, ctype, valueCompare) \

     typedef cpque_##X cpque_##X##_t

 

 

@@ -102,14 +99,14 @@
 

 #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)

 

-#define _c_implement_cpque(X, ctype, cmpOpr, valueCompare) \

+#define _c_implement_cpque(X, ctype, valueCompare) \

 \

     STC_INLINE void \

     _cpque_##X##_sift_down(cpque_##X##_value_t* arr, size_t i, size_t n) { \

         size_t r = i, c = i << 1; \

         while (c <= n) { \

-            c += (c < n && valueCompare(&arr[c], &arr[c + 1]) cmpOpr 0); \

-            if (valueCompare(&arr[r], &arr[c]) cmpOpr 0) { \

+            c += (c < n && valueCompare(&arr[c], &arr[c + 1]) < 0); \

+            if (valueCompare(&arr[r], &arr[c]) < 0) { \

                 cpque_##X##_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp; \

             } else \

                 return; \

@@ -138,7 +135,7 @@
         ctype##_push_back(self, value); /* sift-up the value */ \

         size_t n = cpque_##X##_size(*self), c = n; \

         cpque_##X##_value_t *arr = self->data - 1; \

-        for (; c > 1 && valueCompare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \

+        for (; c > 1 && valueCompare(&arr[c >> 1], &value) < 0; c >>= 1) \

             arr[c] = arr[c >> 1]; \

         if (c != n) arr[c] = value; \

     } \

@@ -148,7 +145,7 @@
     }

 

 #else

-#define _c_implement_cpque(X, ctype, cmpOpr, valueCompare)

+#define _c_implement_cpque(X, ctype, valueCompare)

 #endif

 

 #endif