diff options
Diffstat (limited to 'pqueue.h')
| -rw-r--r-- | pqueue.h | 80 |
1 files changed, 42 insertions, 38 deletions
@@ -3,17 +3,19 @@ #include "vec.h" -#define PQUEUE_DEF(T) \ +#define PQUEUE_DEF_AS(T, TV, A) \ typedef struct { \ - T##Vector vec; \ - } T##PQueue; \ - void T##PQueue_init(T##PQueue *self); \ - T##PQueue T##PQueue_create(); \ - void T##PQueue_push(T##PQueue *self, T elem); \ - void T##PQueue_pop(T##PQueue *self); \ - T* T##PQueue_top(T##PQueue *self); \ - T##PQueue T##PQueue_move(T##PQueue *self); \ - void T##PQueue_free(T##PQueue *self); \ + TV vec; \ + } A; \ + void A##_init(A *self); \ + A A##_create(); \ + void A##_push(A *self, T elem); \ + void A##_pop(A *self); \ + T* A##_top(A *self); \ + A A##_move(A *self); \ + void A##_free(A *self); + +#define PQUEUE_DEF(T) PQUEUE_DEF_AS(T, T##Vector, T##PQueue) PQUEUE_DEF(Int); PQUEUE_DEF(Bool); @@ -26,60 +28,62 @@ PQUEUE_DEF(Float); PQUEUE_DEF(String); PQUEUE_DEF(VoidPtr); -#define PQUEUE_IMPL(T) \ - static int T##PQueue_cmp(T##PQueue *self, int a, int b) { \ - return T##_cmp(*T##Vector_ref(&self->vec, a), *T##Vector_ref(&self->vec, b)); \ +#define PQUEUE_IMPL_AS(T, TV, A) \ + static int A##_cmp(A *self, int a, int b) { \ + return T##_cmp(*TV##_ref(&self->vec, a), *TV##_ref(&self->vec, b)); \ } \ - void T##PQueue_init(T##PQueue *self) { \ - T##Vector_init(&self->vec); \ + void A##_init(A *self) { \ + TV##_init(&self->vec); \ } \ - T##PQueue T##PQueue_create() { \ - T##PQueue self; \ - T##PQueue_init(&self); \ + A A##_create() { \ + A self; \ + A##_init(&self); \ return self; \ } \ - void T##PQueue_push(T##PQueue *self, T elem) { \ - T##Vector_push_back(&self->vec, elem); \ + void A##_push(A *self, T elem) { \ + TV##_push_back(&self->vec, elem); \ int i = self->vec.size - 1; \ - while (i > 0 && T##PQueue_cmp(self, i, i / 2) > 0) { \ - T##Vector_swap(&self->vec, i, i / 2); \ + while (i > 0 && A##_cmp(self, i, i / 2) > 0) { \ + TV##_swap(&self->vec, i, i / 2); \ i /= 2; \ } \ } \ - static void T##PQueue_heapify(T##PQueue *self, int idx) { \ + static void A##_heapify(A *self, int idx) { \ int left, right, largest; \ left = 2 * idx + 1; \ right = 2 * idx + 2; \ - if (left < self->vec.size && T##PQueue_cmp(self, left, idx) > 0) { \ + if (left < self->vec.size && A##_cmp(self, left, idx) > 0) { \ largest = left; \ } else { \ largest = idx; \ } \ - if (right < self->vec.size && T##PQueue_cmp(self, right, largest) > 0) { \ + if (right < self->vec.size && A##_cmp(self, right, largest) > 0) { \ largest = right; \ } \ if (largest != idx) { \ - T##Vector_swap(&self->vec, largest, idx); \ - T##PQueue_heapify(self, largest); \ + TV##_swap(&self->vec, largest, idx); \ + A##_heapify(self, largest); \ } \ } \ - void T##PQueue_pop(T##PQueue *self) { \ + void A##_pop(A *self) { \ if (self->vec.size == 0) return; \ - memcpy(T##Vector_ref(&self->vec, 0), T##Vector_ref(&self->vec, self->vec.size - 1), sizeof(T)); \ - T##Vector_pop(&self->vec); \ - T##PQueue_heapify(self, 0); \ + memcpy(TV##_ref(&self->vec, 0), TV##_ref(&self->vec, self->vec.size - 1), sizeof(T)); \ + TV##_pop(&self->vec); \ + A##_heapify(self, 0); \ } \ - T* T##PQueue_top(T##PQueue *self) { \ + T* A##_top(A *self) { \ if (self->vec.size == 0) return NULL; \ return self->vec.buffer; \ } \ - T##PQueue T##PQueue_move(T##PQueue *self) { \ - T##PQueue dup; \ - dup.vec = T##Vector_move(&self->vec); \ + A A##_move(A *self) { \ + A dup; \ + dup.vec = TV##_move(&self->vec); \ return dup; \ } \ - void T##PQueue_free(T##PQueue *self) { \ - T##Vector_free(&self->vec); \ - } \ + void A##_free(A *self) { \ + TV##_free(&self->vec); \ + } + +#define PQUEUE_IMPL(T) PQUEUE_IMPL_AS(T, T##Vector, T##PQueue) #endif |