Renamed cpqueue (priority queue) container to cpque.

8 files changed, 257 insertions, 257 deletions

diff --git a/README.md b/README.md
index a57740d0..f03ac200 100644
--- a/README.md
+++ b/README.md
@@ -14,7 +14,7 @@ An elegant, fully typesafe, generic, customizable, user-friendly, consistent, an
 - [***cvec*** - Generic dynamic **vector** type](docs/cvec_api.md)

 - [***cstack*** - A **stack** adapter type](docs/cstack_api.md)

 - [***cqueue*** - A **queue** adapter type](docs/cqueue_api.md)

-- [***cpqueue*** - A **priority queue** adapter type](docs/cpqueue_api.md)

+- [***cpque*** - A **priority queue** adapter type](docs/cpque_api.md)

 - [***cptr*** - Support for pointers and shared pointers in containers](docs/cptr_api.md)

 - [***copt*** - Implements *copt_get()*, a **getopt_long**-like function](docs/copt_api.md)

 - [***crand*** - A few very efficent modern **random number generators**](docs/crand_api.md)

diff --git a/docs/cpque_api.md b/docs/cpque_api.md
new file mode 100644
index 00000000..92b84a27
--- /dev/null
+++ b/docs/cpque_api.md
@@ -0,0 +1,86 @@
+# Container [cpque](../stc/cpque.h): Priority Queue
+
+This describes the API of the queue type **cpque**. Implemented as a heap.
+
+## Declaration
+
+```c
+#define using_cpque(X, ctype, heap_variant)
+```
+The macro `using_cpque()` must be instantiated in the global scope.
+**cpque** uses normally a **cvec** type as underlying implementation, specified as `ctype`.
+The `heap_variant` 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(my, cvec_my, >);`, `X` should be replaced by `my` in the following documentation.
+
+## Types
+
+| Type name              | Type definition                         | Used to represent...      |
+|:-----------------------|:----------------------------------------|:--------------------------|
+| `cpque_X`            | `struct {cpque_X_value_t* data; ...}` | The cpque type          |
+| `cpque_X_value_t`    | Depends on underlying container type    | The cpque element type  |
+| `cpque_X_input_t`    |                   "                     | cpque input type        |
+| `cpque_X_rawvalue_t` |                   "                     | cpque raw value type    |
+
+## Header file
+
+All cpque definitions and prototypes may be included in your C source file by including a single header file.
+
+```c
+#include "stc/cpque.h"
+```
+
+## Methods
+
+```c
+cpque_X               cpque_X_init(void);
+cpque_X               cpque_X_clone(cpque_X pq);
+void                    cpque_X_make_heap(cpque_X* self);
+void                    cpque_X_del(cpque_X* self);
+
+size_t                  cpque_X_size(cpque_X pq);
+bool                    cpque_X_empty(cpque_X pq);
+const
+cpque_X_value_t*      cpque_X_top(const cpque_X* self);
+
+void                    cpque_X_push_n(cpque_X *self, const cpque_X_input_t arr[], size_t size);
+void                    cpque_X_emplace(cpque_X* self, cpque_X_rawvalue_t raw);
+void                    cpque_X_push(cpque_X* self, cpque_X_value_t value);
+void                    cpque_X_pop(cpque_X* self);
+void                    cpque_X_erase_at(cpque_X* self, size_t idx);
+```
+
+## Example
+```c
+#include <stdio.h>
+#include "stc/cpque.h"
+#include "stc/crand.h"
+
+using_cvec(i, int64_t);
+using_cpque(i, cvec_i, >); // adaptor type, '>' = min-heap
+
+int main()
+{
+    size_t N = 10000000;
+    crand_t rng = crand_init(1234);
+    crand_uniform_t dist = crand_uniform_init(0, N * 10);
+
+    cpque_i heap = cpque_i_init();
+    // Push ten million random numbers to priority queue, plus some negative ones.
+    c_forrange (N)
+        cpque_i_push(&heap, crand_uniform(&rng, &dist));
+    c_push_items(&heap, cpque_i, {-231, -32, -873, -4, -343});
+
+    // Extract and display the fifty smallest.
+    c_forrange (50) {
+        printf("%zd ", *cpque_i_top(&heap));
+        cpque_i_pop(&heap);
+    }
+    cpque_i_del(&heap);
+}
+```
+Output:
+```
+ -873 -343 -231 -32 -4 3 5 6 18 23 31 54 68 87 99 105 107 125 128 147 150 155 167 178 181 188 213 216 272 284 287 302 306 311 313 326 329 331 344 348 363 367 374 385 396 399 401 407 412 477
+```
\ No newline at end of file
diff --git a/docs/cpqueue_api.md b/docs/cpqueue_api.md
deleted file mode 100644
index d0fa61cb..00000000
--- a/docs/cpqueue_api.md
+++ /dev/null
@@ -1,86 +0,0 @@
-# Container [cpqueue](../stc/cpqueue.h): Priority Queue
-
-This describes the API of the queue type **cpqueue**. Implemented as a heap.
-
-## Declaration
-
-```c
-#define using_cpqueue(X, ctype, heap_variant)
-```
-The macro `using_cpqueue()` must be instantiated in the global scope.
-**cpqueue** uses normally a **cvec** type as underlying implementation, specified as `ctype`.
-The `heap_variant` 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 cpqueue types and methods.
-Declaring `using_cpqueue(my, cvec_my, >);`, `X` should be replaced by `my` in the following documentation.
-
-## Types
-
-| Type name              | Type definition                         | Used to represent...      |
-|:-----------------------|:----------------------------------------|:--------------------------|
-| `cpqueue_X`            | `struct {cpqueue_X_value_t* data; ...}` | The cpqueue type          |
-| `cpqueue_X_value_t`    | Depends on underlying container type    | The cpqueue element type  |
-| `cpqueue_X_input_t`    |                   "                     | cpqueue input type        |
-| `cpqueue_X_rawvalue_t` |                   "                     | cpqueue raw value type    |
-
-## Header file
-
-All cpqueue definitions and prototypes may be included in your C source file by including a single header file.
-
-```c
-#include "stc/cpqueue.h"
-```
-
-## Methods
-
-```c
-cpqueue_X               cpqueue_X_init(void);
-cpqueue_X               cpqueue_X_clone(cpqueue_X pq);
-void                    cpqueue_X_make_heap(cpqueue_X* self);
-void                    cpqueue_X_del(cpqueue_X* self);
-
-size_t                  cpqueue_X_size(cpqueue_X pq);
-bool                    cpqueue_X_empty(cpqueue_X pq);
-const
-cpqueue_X_value_t*      cpqueue_X_top(const cpqueue_X* self);
-
-void                    cpqueue_X_push_n(cpqueue_X *self, const cpqueue_X_input_t arr[], size_t size);
-void                    cpqueue_X_emplace(cpqueue_X* self, cpqueue_X_rawvalue_t raw);
-void                    cpqueue_X_push(cpqueue_X* self, cpqueue_X_value_t value);
-void                    cpqueue_X_pop(cpqueue_X* self);
-void                    cpqueue_X_erase_at(cpqueue_X* self, size_t idx);
-```
-
-## Example
-```c
-#include <stdio.h>
-#include "stc/cpqueue.h"
-#include "stc/crand.h"
-
-using_cvec(i, int64_t);
-using_cpqueue(i, cvec_i, >); // adaptor type, '>' = min-heap
-
-int main()
-{
-    size_t N = 10000000;
-    crand_t rng = crand_init(1234);
-    crand_uniform_t dist = crand_uniform_init(0, N * 10);
-
-    cpqueue_i heap = cpqueue_i_init();
-    // Push ten million random numbers to priority queue, plus some negative ones.
-    c_forrange (N)
-        cpqueue_i_push(&heap, crand_uniform(&rng, &dist));
-    c_push_items(&heap, cpqueue_i, {-231, -32, -873, -4, -343});
-
-    // Extract and display the fifty smallest.
-    c_forrange (50) {
-        printf("%zd ", *cpqueue_i_top(&heap));
-        cpqueue_i_pop(&heap);
-    }
-    cpqueue_i_del(&heap);
-}
-```
-Output:
-```
- -873 -343 -231 -32 -4 3 5 6 18 23 31 54 68 87 99 105 107 125 128 147 150 155 167 178 181 188 213 216 272 284 287 302 306 311 313 326 329 331 344 348 363 367 374 385 396 399 401 407 412 477
-```
\ No newline at end of file
diff --git a/examples/heap.c b/examples/heap.c
index b45e5ada..c7292d2e 100644
--- a/examples/heap.c
+++ b/examples/heap.c
@@ -2,10 +2,10 @@
 #include <time.h>

 #include <stc/crand.h>

 #include <stc/cvec.h>

-#include <stc/cpqueue.h>

+#include <stc/cpque.h>

 

 using_cvec(f, float);

-using_cpqueue(f, cvec_f, >);

+using_cpque(f, cvec_f, >);

 

 int main()

 {

@@ -13,36 +13,36 @@ int main()
     crand_t rng;

     int N = 3000000, M = 100;

 

-    cpqueue_f pq = cpqueue_f_init();

+    cpque_f pq = cpque_f_init();

 

     rng = crand_init(seed);

     clock_t start = clock();

     c_forrange (i, int, N)

         cvec_f_push_back(&pq, (float) crand_nextf(&rng)*100000);

 

-    cpqueue_f_make_heap(&pq);

+    cpque_f_make_heap(&pq);

     printf("Built priority queue: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC);

 

     c_forrange (i, int, M) {

-        printf("%g ", *cpqueue_f_top(&pq));

-        cpqueue_f_pop(&pq);

+        printf("%g ", *cpque_f_top(&pq));

+        cpque_f_pop(&pq);

     }

 

     start = clock();

     c_forrange (i, int, M, N)

-        cpqueue_f_pop(&pq);

+        cpque_f_pop(&pq);

     printf("\n\npopped PQ: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC);

 

     start = clock();

     c_forrange (i, int, N)

-        cpqueue_f_push(&pq, (float) crand_nextf(&rng)*100000);

+        cpque_f_push(&pq, (float) crand_nextf(&rng)*100000);

     printf("pushed PQ: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC);

 

     c_forrange (i, int, M) {

-        printf("%g ", *cpqueue_f_top(&pq));

-        cpqueue_f_pop(&pq);

+        printf("%g ", *cpque_f_top(&pq));

+        cpque_f_pop(&pq);

     }

     puts("");

 

-    cpqueue_f_del(&pq);

+    cpque_f_del(&pq);

 }

diff --git a/examples/inits.c b/examples/inits.c
index 4ce1421a..28b54835 100644
--- a/examples/inits.c
+++ b/examples/inits.c
@@ -2,7 +2,7 @@
 #include <stc/cstr.h>

 #include <stc/cmap.h>

 #include <stc/cvec.h>

-#include <stc/cpqueue.h>

+#include <stc/cpque.h>

 #include <stc/clist.h>

 

 using_cmap(id, int, cstr_t, cstr_del); // Map of int -> cstr_t

@@ -17,7 +17,7 @@ inline static int ipair_compare(const ipair_t* a, const ipair_t* b) {
 using_cvec(ip, ipair_t, c_default_del, ipair_compare);

 using_clist(ip, ipair_t, c_default_del, ipair_compare);

 using_cvec(f, float);

-using_cpqueue(f, cvec_f, >);

+using_cpque(f, cvec_f, >);

 

 int main(void)

 {

@@ -31,16 +31,16 @@ int main(void)
 

     // CVEC PRIORITY QUEUE

 

-    cpqueue_f_make_heap(&floats);

-    c_push_items(&floats, cpqueue_f, {40.0f, 20.0f, 50.0f, 30.0f, 10.0f});

+    cpque_f_make_heap(&floats);

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

 

     // sorted:

-    while (! cpqueue_f_empty(floats)) {

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

-        cpqueue_f_pop(&floats);

+    while (! cpque_f_empty(floats)) {

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

+        cpque_f_pop(&floats);

     }

     puts("\n");

-    cpqueue_f_del(&floats);

+    cpque_f_del(&floats);

 

     // CMAP ID

 

diff --git a/examples/priority.c b/examples/priority.c
index 40fb395e..4eb762ec 100644
--- a/examples/priority.c
+++ b/examples/priority.c
@@ -2,34 +2,34 @@
 #include <stdio.h>

 #include <time.h>

 #include <stc/cvec.h>

-#include <stc/cpqueue.h>

+#include <stc/cpque.h>

 #include <stc/cmap.h>

 #include <stc/crand.h>

 

 using_cvec(i, int64_t);

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

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

 

 int main() {

     size_t N = 10000000;

     crand_t rng = crand_init(time(NULL));

     crand_uniform_t dist = crand_uniform_init(0, N * 10);

-    cpqueue_i heap = cpqueue_i_init();

+    cpque_i heap = cpque_i_init();

 

     // Push ten million random numbers to priority queue

     c_forrange (N)

-        cpqueue_i_push(&heap, crand_uniform(&rng, &dist));

+        cpque_i_push(&heap, crand_uniform(&rng, &dist));

 

     // push some negative numbers too.

-    c_push_items(&heap, cpqueue_i, {-231, -32, -873, -4, -343});

+    c_push_items(&heap, cpque_i, {-231, -32, -873, -4, -343});

 

     c_forrange (N)

-        cpqueue_i_push(&heap, crand_uniform(&rng, &dist));

+        cpque_i_push(&heap, crand_uniform(&rng, &dist));

 

 

     // Extract the hundred smallest.

     c_forrange (100) {

-        printf("%zd ", *cpqueue_i_top(&heap));

-        cpqueue_i_pop(&heap);

+        printf("%zd ", *cpque_i_top(&heap));

+        cpque_i_pop(&heap);

     }

-    cpqueue_i_del(&heap);

+    cpque_i_del(&heap);

 }

diff --git a/stc/cpque.h b/stc/cpque.h
new file mode 100644
index 00000000..394b85c3
--- /dev/null
+++ b/stc/cpque.h
@@ -0,0 +1,142 @@
+/* MIT License

+ *

+ * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no

+ *

+ * Permission is hereby granted, free of charge, to any person obtaining a copy

+ * of this software and associated documentation files (the "Software"), to deal

+ * in the Software without restriction, including without limitation the rights

+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

+ * copies of the Software, and to permit persons to whom the Software is

+ * furnished to do so, subject to the following conditions:

+ *

+ * The above copyright notice and this permission notice shall be included in all

+ * copies or substantial portions of the Software.

+ *

+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

+ * SOFTWARE.

+ */

+

+/*  Priority-Queue adapter (implemented as heap), default uses cvec.

+

+    #include <stc/crand.h>

+    #include <stc/cpque.h>

+    using_cvec(f, float);

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

+

+    int main() {

+        crand_t rng = crand_init(1234);

+        crand_uniformf_t dist = crand_uniformf_init(10.0f, 100.0f);

+

+        cpque_f queue = cpque_f_init();

+        // Push ten million random numbers onto the queue.

+        for (int i=0; i<10000000; ++i)

+            cpque_f_push(&queue, crand_uniformf(&rng, dist));

+        // Extract the 100 smallest.

+        for (int i=0; i<100; ++i) {

+            printf("%f ", *cpque_f_top(queue));

+            cpque_f_pop(&queue);

+        }

+        cpque_f_del(&queue);

+    }

+*/

+#ifndef CPQUEUE__H__

+#define CPQUEUE__H__

+

+#include "cvec.h"

+

+#define using_cpque(X, ctype, cmpOpr) /* cmpOpr: < or > */ \

+\

+    typedef ctype##_t cpque_##X; \

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

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

+    typedef ctype##_input_t cpque_##X##_input_t; \

+    STC_INLINE cpque_##X \

+    cpque_##X##_init(void) {return ctype##_init();} \

+    STC_INLINE cpque_##X \

+    cpque_##X##_clone(cpque_##X pq) {return ctype##_clone(pq);} \

+    STC_INLINE size_t \

+    cpque_##X##_size(cpque_##X pq) {return ctype##_size(pq);} \

+    STC_INLINE bool \

+    cpque_##X##_empty(cpque_##X pq) {return ctype##_empty(pq);} \

+    STC_INLINE void \

+    cpque_##X##_del(cpque_##X* self) {ctype##_del(self);} \

+    STC_API void \

+    cpque_##X##_make_heap(cpque_##X* self); \

+    STC_API void \

+    cpque_##X##_erase_at(cpque_##X* self, size_t i); \

+    STC_INLINE const cpque_##X##_value_t* \

+    cpque_##X##_top(const cpque_##X* self) {return &self->data[0];} \

+    STC_INLINE void \

+    cpque_##X##_pop(cpque_##X* self) {cpque_##X##_erase_at(self, 0);} \

+    STC_API void \

+    cpque_##X##_push(cpque_##X* self, cpque_##X##_value_t value); \

+    STC_INLINE void \

+    cpque_##X##_emplace(cpque_##X* self, cpque_##X##_rawvalue_t rawValue) { \

+        cpque_##X##_push(self, ctype##_value_from_raw(rawValue)); \

+    } \

+    STC_API void \

+    cpque_##X##_push_n(cpque_##X *self, const cpque_##X##_input_t in[], size_t size); \

+\

+    implement_cpque(X, ctype, cmpOpr)

+

+/* -------------------------- IMPLEMENTATION ------------------------- */

+

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

+#define implement_cpque(X, ctype, cmpOpr) \

+\

+    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) { \

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

+            } else \

+                return; \

+            c <<= 1; \

+        } \

+    } \

+\

+    STC_API void \

+    cpque_##X##_make_heap(cpque_##X* self) { \

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

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

+        for (size_t k = n >> 1; k != 0; --k) \

+            _cpque_##X##_sift_down(arr, k, n); \

+    } \

+\

+    STC_API void \

+    cpque_##X##_erase_at(cpque_##X* self, size_t i) { \

+        size_t n = cpque_##X##_size(*self) - 1; \

+        self->data[i] = self->data[n]; \

+        ctype##_pop_back(self); \

+        _cpque_##X##_sift_down(self->data - 1, i + 1, n); \

+    } \

+\

+    STC_API void \

+    cpque_##X##_push(cpque_##X* self, cpque_##X##_value_t value) { \

+        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) \

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

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

+    } \

+    STC_API void \

+    cpque_##X##_push_n(cpque_##X *self, const cpque_##X##_input_t in[], size_t size) { \

+        ctype##_reserve(self, cpque_##X##_size(*self) + size); \

+        for (size_t i=0; i<size; ++i) cpque_##X##_push(self, in[i]); \

+    } \

+\

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

+

+#else

+#define implement_cpque(X, ctype, cmpOpr)

+#endif

+

+#endif

diff --git a/stc/cpqueue.h b/stc/cpqueue.h
deleted file mode 100644
index 12834a47..00000000
--- a/stc/cpqueue.h
+++ /dev/null
@@ -1,142 +0,0 @@
-/* MIT License

- *

- * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no

- *

- * Permission is hereby granted, free of charge, to any person obtaining a copy

- * of this software and associated documentation files (the "Software"), to deal

- * in the Software without restriction, including without limitation the rights

- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

- * copies of the Software, and to permit persons to whom the Software is

- * furnished to do so, subject to the following conditions:

- *

- * The above copyright notice and this permission notice shall be included in all

- * copies or substantial portions of the Software.

- *

- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

- * SOFTWARE.

- */

-

-/*  Priority-Queue adapter (implemented as heap), default uses cvec.

-

-    #include <stc/crand.h>

-    #include <stc/cpqueue.h>

-    using_cvec(f, float);

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

-

-    int main() {

-        crand_t rng = crand_init(1234);

-        crand_uniformf_t dist = crand_uniformf_init(10.0f, 100.0f);

-

-        cpqueue_f queue = cpqueue_f_init();

-        // Push ten million random numbers onto the queue.

-        for (int i=0; i<10000000; ++i)

-            cpqueue_f_push(&queue, crand_uniformf(&rng, dist));

-        // Extract the 100 smallest.

-        for (int i=0; i<100; ++i) {

-            printf("%f ", *cpqueue_f_top(queue));

-            cpqueue_f_pop(&queue);

-        }

-        cpqueue_f_del(&queue);

-    }

-*/

-#ifndef CPQUEUE__H__

-#define CPQUEUE__H__

-

-#include "cvec.h"

-

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

-\

-    typedef ctype##_t cpqueue_##X; \

-    typedef ctype##_value_t cpqueue_##X##_value_t; \

-    typedef ctype##_rawvalue_t cpqueue_##X##_rawvalue_t; \

-    typedef ctype##_input_t cpqueue_##X##_input_t; \

-    STC_INLINE cpqueue_##X \

-    cpqueue_##X##_init(void) {return ctype##_init();} \

-    STC_INLINE cpqueue_##X \

-    cpqueue_##X##_clone(cpqueue_##X pq) {return ctype##_clone(pq);} \

-    STC_INLINE size_t \

-    cpqueue_##X##_size(cpqueue_##X pq) {return ctype##_size(pq);} \

-    STC_INLINE bool \

-    cpqueue_##X##_empty(cpqueue_##X pq) {return ctype##_empty(pq);} \

-    STC_INLINE void \

-    cpqueue_##X##_del(cpqueue_##X* self) {ctype##_del(self);} \

-    STC_API void \

-    cpqueue_##X##_make_heap(cpqueue_##X* self); \

-    STC_API void \

-    cpqueue_##X##_erase_at(cpqueue_##X* self, size_t i); \

-    STC_INLINE const cpqueue_##X##_value_t* \

-    cpqueue_##X##_top(const cpqueue_##X* self) {return &self->data[0];} \

-    STC_INLINE void \

-    cpqueue_##X##_pop(cpqueue_##X* self) {cpqueue_##X##_erase_at(self, 0);} \

-    STC_API void \

-    cpqueue_##X##_push(cpqueue_##X* self, cpqueue_##X##_value_t value); \

-    STC_INLINE void \

-    cpqueue_##X##_emplace(cpqueue_##X* self, cpqueue_##X##_rawvalue_t rawValue) { \

-        cpqueue_##X##_push(self, ctype##_value_from_raw(rawValue)); \

-    } \

-    STC_API void \

-    cpqueue_##X##_push_n(cpqueue_##X *self, const cpqueue_##X##_input_t in[], size_t size); \

-\

-    implement_cpqueue(X, ctype, cmpOpr)

-

-/* -------------------------- IMPLEMENTATION ------------------------- */

-

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

-#define implement_cpqueue(X, ctype, cmpOpr) \

-\

-    STC_INLINE void \

-    _cpqueue_##X##_sift_down(cpqueue_##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) { \

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

-            } else \

-                return; \

-            c <<= 1; \

-        } \

-    } \

-\

-    STC_API void \

-    cpqueue_##X##_make_heap(cpqueue_##X* self) { \

-        size_t n = cpqueue_##X##_size(*self); \

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

-        for (size_t k = n >> 1; k != 0; --k) \

-            _cpqueue_##X##_sift_down(arr, k, n); \

-    } \

-\

-    STC_API void \

-    cpqueue_##X##_erase_at(cpqueue_##X* self, size_t i) { \

-        size_t n = cpqueue_##X##_size(*self) - 1; \

-        self->data[i] = self->data[n]; \

-        ctype##_pop_back(self); \

-        _cpqueue_##X##_sift_down(self->data - 1, i + 1, n); \

-    } \

-\

-    STC_API void \

-    cpqueue_##X##_push(cpqueue_##X* self, cpqueue_##X##_value_t value) { \

-        ctype##_push_back(self, value); /* sift-up the value */ \

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

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

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

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

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

-    } \

-    STC_API void \

-    cpqueue_##X##_push_n(cpqueue_##X *self, const cpqueue_##X##_input_t in[], size_t size) { \

-        ctype##_reserve(self, cpqueue_##X##_size(*self) + size); \

-        for (size_t i=0; i<size; ++i) cpqueue_##X##_push(self, in[i]); \

-    } \

-\

-    typedef cpqueue_##X cpqueue_##X##_t

-

-#else

-#define implement_cpqueue(X, ctype, cmpOpr)

-#endif

-

-#endif