From b26e0e9556a2331e99090857fdd02fa0775e53b9 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sat, 18 Jul 2020 20:19:20 +0200 Subject: Some API changes on vec heap. --- examples/geek7.c | 14 +++++++++----- stc/clist.h | 4 ++-- stc/cvecque.h | 44 ++++++++++++++++++++++---------------------- 3 files changed, 33 insertions(+), 29 deletions(-) diff --git a/examples/geek7.c b/examples/geek7.c index b2bda51c..4bf57174 100644 --- a/examples/geek7.c +++ b/examples/geek7.c @@ -22,9 +22,11 @@ After inserting all the elements excluding the ones which are to be deleted, Pop #include #include #include -#include +#include declare_CMap(ii, int, int); +declare_CVec(i, int); +declare_CVec_heap(i); // Find k minimum element from arr[0..m-1] after deleting // elements from del[0..n-1] @@ -39,7 +41,7 @@ void findElementsAfterDel(int arr[], int m, int del[], cmap_ii_at(&mp, del[i], 0)->value++; } - priority_queue, greater > heap; + CVec_i heap = CVec_init; for (int i = 0; i < m; ++i) { @@ -58,15 +60,17 @@ void findElementsAfterDel(int arr[], int m, int del[], // Else push it in the min heap else - heap.push(arr[i]); + cvecheap_i_push(&heap, arr[i]); + + CVecHeap_i Text } // Print top k elements in the min heap for (int i = 0; i < k; ++i) { - cout << heap.top() << " "; + printf("%d ", cvecque_i_top(&heap)); // Pop the top element - heap.pop(); + cvecque_i_pop(&heap); } } diff --git a/stc/clist.h b/stc/clist.h index 8577fc40..bfd90e34 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -215,14 +215,14 @@ } \ \ static inline int \ - clist_##tag##_sortCmp(const void* x, const void* y) { \ + clist_##tag##_sortCompare(const void* x, const void* y) { \ RawValue a = valueGetRaw(&((CListNode_##tag *) x)->value); \ RawValue b = valueGetRaw(&((CListNode_##tag *) y)->value); \ return valueCompareRaw(&a, &b); \ } \ STC_API void \ clist_##tag##_sort(CList_##tag* self) { \ - CListNode__base* last = _clist_mergesort((CListNode__base *) self->last->next, clist_##tag##_sortCmp); \ + CListNode__base* last = _clist_mergesort((CListNode__base *) self->last->next, clist_##tag##_sortCompare); \ self->last = (CListNode_##tag *) last; \ } diff --git a/stc/cvecque.h b/stc/cvecque.h index 7b0175e4..26174a5c 100644 --- a/stc/cvecque.h +++ b/stc/cvecque.h @@ -23,40 +23,40 @@ /* Priority queue using CVec as heap. */ -#ifndef CVECQUE__H__ -#define CVECQUE__H__ +#ifndef CVECHEAP__H__ +#define CVECHEAP__H__ #include "cvec.h" -/* Requires declare_CVec(tag, ...) to be declared */ -#define declare_CVecque(tag) \ +/* Requires declare_CVec(tag, ...) to be declared. cmpOpr is '<' (max-heap) or '>' (min-heap) */ +#define declare_CVec_heap(tag, cmpOpr) \ \ STC_API void \ -cvec_##tag##_queueify(CVec_##tag* self); \ +cvec_##tag##_heapify(CVec_##tag* self); \ STC_API CVecValue_##tag \ -cvecque_##tag##_erase(CVec_##tag* self, size_t i); \ +cvec_##tag##_heapErase(CVec_##tag* self, size_t i); \ STC_INLINE CVecValue_##tag \ -cvecque_##tag##_top(CVec_##tag* self) {return self->data[0];} \ +cvec_##tag##_heapTop(CVec_##tag* self) {return self->data[0];} \ STC_INLINE CVecValue_##tag \ -cvecque_##tag##_pop(CVec_##tag* self) {return cvecque_##tag##_erase(self, 0);} \ +cvec_##tag##_heapPop(CVec_##tag* self) {return cvec_##tag##_heapErase(self, 0);} \ STC_API void \ -cvecque_##tag##_push(CVec_##tag* self, CVecValue_##tag value); \ +cvec_##tag##_heapPush(CVec_##tag* self, CVecValue_##tag value); \ \ -implement_CVecque(tag) \ -typedef CVec_##tag CVecdeque_##tag +implement_CVec_heap(tag, cmpOpr) \ +typedef CVec_##tag CVecHeap_##tag /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_CVecque(tag) \ +#define implement_CVec_heap(tag, cmpOpr) \ \ STC_INLINE void \ -_cvecque_##tag##_siftDown(CVecValue_##tag* arr, size_t i, size_t n) { \ +_cvec_##tag##_siftDown(CVecValue_##tag* arr, size_t i, size_t n) { \ size_t r = i, c = i << 1; \ while (c <= n) { \ - if (c < n && arr[c] > arr[c + 1]) \ + if (c < n && cvec_##tag##_sortCompare(&arr[c], &arr[c + 1]) cmpOpr 0) \ ++c; \ - if (arr[r] > arr[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; \ @@ -65,34 +65,34 @@ _cvecque_##tag##_siftDown(CVecValue_##tag* arr, size_t i, size_t n) { \ } \ \ STC_API CVecValue_##tag \ -cvecque_##tag##_erase(CVec_##tag* self, size_t i) { \ +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); \ - _cvecque_##tag##_siftDown(self->data - 1, i + 1, cvec_size(*self)); \ + _cvec_##tag##_siftDown(self->data - 1, i + 1, cvec_size(*self)); \ return ret; \ } \ \ STC_API void \ -cvecque_##tag##_push(CVec_##tag* self, CVecValue_##tag value) { \ +cvec_##tag##_heapPush(CVec_##tag* self, CVecValue_##tag value) { \ cvec_##tag##_pushBack(self, value); \ size_t n = cvec_size(*self), i = n; \ CVecValue_##tag *arr = self->data - 1; \ - for (; i > 1 && arr[i >> 1] > value; i >>= 1) \ + for (; i > 1 && cvec_##tag##_sortCompare(&arr[i >> 1], &value) cmpOpr 0; i >>= 1) \ arr[i] = arr[i >> 1]; \ arr[i] = value; \ } \ \ STC_API void \ -cvec_##tag##_queueify(CVec_##tag* self) { \ +cvec_##tag##_heapify(CVec_##tag* self) { \ size_t n = cvec_size(*self); \ CVecValue_##tag *arr = self->data - 1; \ for (size_t i = n >> 1; i; --i) \ - _cvecque_##tag##_siftDown(arr, i, n); \ + _cvec_##tag##_siftDown(arr, i, n); \ } #else -#define implement_CVecque(tag) +#define implement_CVec_heap(tag, cmpOpr) #endif #endif -- cgit v1.2.3