From 88fd2f2edde7946579f18bca85240d67cce9bc2b Mon Sep 17 00:00:00 2001
From: Tyge Løvset <tylo@norceresearch.no>
Date: Sun, 19 Jul 2020 00:30:52 +0200
Subject: Changed some API

---
 stc/cvecheap.h | 56 ++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 34 insertions(+), 22 deletions(-)

diff --git a/stc/cvecheap.h b/stc/cvecheap.h
index 7867557f..059de727 100644
--- a/stc/cvecheap.h
+++ b/stc/cvecheap.h
@@ -21,24 +21,38 @@
  * SOFTWARE.
  */
 
-/* Priority queue using CVec as heap. */
+/*  Priority queue using CVec as heap.
+
+    #include <stc/cvecheap.h>
+    #include <stc/crandom.h>
+    declare_CVec(i, int);
+    declare_CVec_heap(i, >); // min-heap (increasing values)
+    int main() {
+        pcg32_random_t pcg = pcg32_seed(1234, 0);
+        CVec_i heap = cvec_init;
+        for (int i=0; i<100; ++i) cvec_i_heapPush(&heap, pcg32_random(&pcg));
+        for (int i=0; i<5; ++i) {
+            printf("%d ", cvec_i_heapTop(&heap, pcg32_random(&pcg)));
+            cvec_i_heapPop(&heap, pcg32_random(&pcg));
+        }
+    }
+ */
 
 #ifndef CVECHEAP__H__
 #define CVECHEAP__H__
 
 #include "cvec.h"
 
-/* Requires declare_CVec(tag, ...) to be declared. cmpOpr is '<' (max-heap) or '>' (min-heap) */
-#define declare_CVec_heap(tag, cmpOpr) \
+#define declare_CVec_heap(tag, cmpOpr) /* < or > */ \
  \
 STC_API void \
 cvec_##tag##_heapify(CVec_##tag* self); \
-STC_API CVecValue_##tag \
+STC_API void \
 cvec_##tag##_heapErase(CVec_##tag* self, size_t i); \
 STC_INLINE CVecValue_##tag \
 cvec_##tag##_heapTop(CVec_##tag* self) {return self->data[0];} \
-STC_INLINE CVecValue_##tag \
-cvec_##tag##_heapPop(CVec_##tag* self) {return cvec_##tag##_heapErase(self, 0);} \
+STC_INLINE void \
+cvec_##tag##_heapPop(CVec_##tag* self) {cvec_##tag##_heapErase(self, 0);} \
 STC_API void \
 cvec_##tag##_heapPush(CVec_##tag* self, CVecValue_##tag value); \
  \
@@ -52,43 +66,41 @@ typedef CVec_##tag CVecHeap_##tag
  \
 STC_INLINE void \
 _cvec_##tag##_siftDown(CVecValue_##tag* arr, size_t i, size_t n) { \
-    size_t r = i, j = i << 1; \
-    while (j <= n) { \
-        if (j < n && cvec_##tag##_sortCompare(&arr[j], &arr[j + 1]) cmpOpr 0) \
-            ++j; \
-        if (cvec_##tag##_sortCompare(&arr[r], &arr[j]) cmpOpr 0) { \
-            CVecValue_##tag t = arr[r]; arr[r] = arr[j]; arr[r = j] = t; \
+    size_t r = i, c = i << 1; \
+    while (c <= n) { \
+        if (c < n && cvec_##tag##_sortCompare(&arr[c], &arr[c + 1]) cmpOpr 0) \
+            ++c; \
+        if (cvec_##tag##_sortCompare(&arr[r], &arr[c]) cmpOpr 0) { \
+            CVecValue_##tag t = arr[r]; arr[r] = arr[c]; arr[r = c] = t; \
         } else \
             return; \
-        j <<= 1; \
+        c <<= 1; \
     } \
 } \
  \
-STC_API CVecValue_##tag \
+STC_API void \
 cvec_##tag##_heapErase(CVec_##tag* self, size_t i) { \
-    CVecValue_##tag ret = self->data[i]; \
     self->data[i] = cvec_##tag##_back(*self); \
     cvec_##tag##_popBack(self); \
     _cvec_##tag##_siftDown(self->data - 1, i + 1, cvec_size(*self)); \
-    return ret; \
 } \
  \
 STC_API void \
 cvec_##tag##_heapPush(CVec_##tag* self, CVecValue_##tag value) { \
     cvec_##tag##_pushBack(self, value); \
-    size_t n = cvec_size(*self), j = n; \
+    size_t n = cvec_size(*self), c = n; \
     CVecValue_##tag *arr = self->data - 1; \
-    for (; j > 1 && cvec_##tag##_sortCompare(&arr[j >> 1], &value) cmpOpr 0; j >>= 1) \
-        arr[j] = arr[j >> 1]; \
-    arr[j] = value; \
+    for (; c > 1 && cvec_##tag##_sortCompare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \
+        arr[c] = arr[c >> 1]; \
+    arr[c] = value; \
 } \
  \
 STC_API void \
 cvec_##tag##_heapify(CVec_##tag* self) { \
     size_t n = cvec_size(*self);  \
     CVecValue_##tag *arr = self->data - 1; \
-    for (size_t m = n >> 1; m; --m) \
-        _cvec_##tag##_siftDown(arr, m, n); \
+    for (size_t k = n >> 1; k != 0; --k) \
+        _cvec_##tag##_siftDown(arr, k, n); \
 }
 
 #else
-- 
cgit v1.2.3