From 512086cdf69bbfadd794fb5e751fb681222a4adf Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 17 Dec 2020 13:13:11 +0100 Subject: Renamed cpqueue (priority queue) container to cpque. --- stc/cpqueue.h | 142 ---------------------------------------------------------- 1 file changed, 142 deletions(-) delete mode 100644 stc/cpqueue.h (limited to 'stc/cpqueue.h') 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 - #include - 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