From 99bb129812e6fb830a05dd7f789987ba11f69b96 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 24 Mar 2021 20:10:44 +0100 Subject: Added valueCompare parameter to cpque. --- docs/cpque_api.md | 12 +++++++----- examples/cpque.c | 56 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ stc/carray.h | 4 ++-- stc/cpque.h | 29 ++++++++++++++++++---------- 4 files changed, 84 insertions(+), 17 deletions(-) create mode 100644 examples/cpque.c diff --git a/docs/cpque_api.md b/docs/cpque_api.md index e2439c56..313a0e92 100644 --- a/docs/cpque_api.md +++ b/docs/cpque_api.md @@ -10,15 +10,17 @@ See the c++ class [std::priority_queue](https://en.cppreference.com/w/cpp/contai ```c #include -using_cpque(X, ctype, direction) +using_cpque(X, ctype); // default dir = `<` : max-heap +using_cpque(X, ctype, dir); // uses valueCompare from ctype +using_cpque(X, ctype, dir, 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 *direction* must be given as +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. -Note that the function *`ctype`_value_compare(x, y)* defined by the underlying vector type is used to -compare values (priorities). `X` is a type tag name and will affect the names of all cpque types and methods. -Declaring `using_cpque(i, cvec_i, >)`, `X` should be replaced by `i` in the following documentation. +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. +When declaring `using_cpque(i, cvec_i)`, `X` should be replaced by `i` in the following documentation. ## Methods diff --git a/examples/cpque.c b/examples/cpque.c new file mode 100644 index 00000000..ae869832 --- /dev/null +++ b/examples/cpque.c @@ -0,0 +1,56 @@ +#include +#include + +// 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 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); + +#define PRINT_Q(Q) \ + void print_##Q(Q q) { \ + Q copy = Q##_clone(q); \ + while (!Q##_empty(copy)) { \ + printf("%d ", *Q##_top(©)); \ + Q##_pop(©); \ + } \ + puts(""); \ + Q##_del(©); \ + } + +PRINT_Q(cpque_imin) +PRINT_Q(cpque_imax) +PRINT_Q(cpque_imix) + + +int main() { + cpque_imax q = cpque_imax_init(); + + const int data[] = {1,8,5,6,3,4,0,9,7,2}; + + c_forrange (n, c_arraylen(data)) + cpque_imax_push(&q, n); + + print_cpque_imax(q); + + 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(); + + c_forrange (n, c_arraylen(data)) + cpque_imix_push(&q3, n); + + print_cpque_imix(q3); + + cpque_imin_del(&q); + cpque_imax_del(&q2); + cpque_imix_del(&q3); +} \ No newline at end of file diff --git a/stc/carray.h b/stc/carray.h index aca632d6..f1c90b1d 100644 --- a/stc/carray.h +++ b/stc/carray.h @@ -52,8 +52,6 @@ int main() { } */ -// carray2: - #define using_carray2(...) c_MACRO_OVERLOAD(using_carray2, __VA_ARGS__) #define using_carray2_2(X, Value) \ @@ -164,6 +162,8 @@ int main() { c_free(self->at); \ } +// carray3 impl. + #define _c_implement_carray3_4(X, Value, valueDel, valueClone) \ \ STC_DEF carray3##X carray3##X##_from(carray3##X##_value_t* block, size_t xdim, size_t ydim, size_t zdim) { \ diff --git a/stc/cpque.h b/stc/cpque.h index b07497bf..abb14565 100644 --- a/stc/cpque.h +++ b/stc/cpque.h @@ -49,7 +49,15 @@ #include "cvec.h" -#define using_cpque(X, ctype, cmpOpr) /* cmpOpr: < or > */ \ +#define using_cpque(...) c_MACRO_OVERLOAD(using_cpque, __VA_ARGS__) + +#define using_cpque_2(X, ctype) \ + using_cpque_3(X, ctype, <) + +#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) \ typedef ctype##_t cpque_##X; \ typedef ctype##_value_t cpque_##X##_value_t; \ typedef ctype##_rawvalue_t cpque_##X##_rawvalue_t; \ @@ -86,19 +94,22 @@ STC_API void \ cpque_##X##_emplace_n(cpque_##X *self, const cpque_##X##_rawvalue_t arr[], size_t size); \ \ - implement_cpque(X, ctype, cmpOpr) + _c_implement_cpque(X, ctype, cmpOpr, valueCompare) \ + typedef cpque_##X cpque_##X##_t + /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_cpque(X, ctype, cmpOpr) \ + +#define _c_implement_cpque(X, ctype, cmpOpr, 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 && ctype##_value_compare(&arr[c], &arr[c + 1]) cmpOpr 0); \ - if (ctype##_value_compare(&arr[r], &arr[c]) cmpOpr 0) { \ + c += (c < n && valueCompare(&arr[c], &arr[c + 1]) cmpOpr 0); \ + if (valueCompare(&arr[r], &arr[c]) cmpOpr 0) { \ cpque_##X##_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp; \ } else \ return; \ @@ -127,19 +138,17 @@ 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 && ctype##_value_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ + for (; c > 1 && valueCompare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ arr[c] = arr[c >> 1]; \ if (c != n) arr[c] = value; \ } \ STC_API void \ cpque_##X##_emplace_n(cpque_##X *self, const cpque_##X##_rawvalue_t arr[], size_t size) { \ for (size_t i=0; i