misc/examples/priorityqueues/functor.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

// Implements c++ example: https://en.cppreference.com/w/cpp/container/priority_queue
// Example of per-instance less-function on a single priority queue type
//

#include <stdio.h>

#define i_type IPQue
#define i_base cpque
#define i_key int
#define i_extend bool(*less)(const int*, const int*);
#define i_less(x, y) c_extend()->less(x, y)
// Note: i_less: c_extend() accessible for cpque types
//       i_cmp: c_extend() accessible for csmap and csset types
//       i_hash/i_eq: c_extend() accessible for cmap and cset types
#include <stc/extend.h>

void print_queue(const char* name, IPQue_ext q) {
    // NB: make a clone because there is no way to traverse
    // priority queue's content without erasing the queue.
    IPQue_ext copy = {q.less, IPQue_clone(q.get)};
    
    for (printf("%s: \t", name); !IPQue_empty(&copy.get); IPQue_pop(&copy.get))
        printf("%d ", *IPQue_top(&copy.get));
    puts("");

    IPQue_drop(&copy.get);
}

static bool int_less(const int* x, const int* y) { return *x < *y; }
static bool int_greater(const int* x, const int* y) { return *x > *y; }
static bool int_lambda(const int* x, const int* y) { return (*x ^ 1) < (*y ^ 1); }

int main(void)
{
    const int data[] = {1,8,5,6,3,4,0,9,7,2}, n = c_arraylen(data);
    printf("data: \t");
    c_forrange (i, n) printf("%d ", data[i]);
    puts("");


    // Max priority queue
    IPQue_ext q1 = {.less=int_less};
    IPQue_put_n(&q1.get, data, n);
    print_queue("q1", q1);

    // Min priority queue
    IPQue_ext minq1 = {.less=int_greater};
    IPQue_put_n(&minq1.get, data, n);
    print_queue("minq1", minq1);

    // Using lambda to compare elements.
    IPQue_ext q5 = {.less=int_lambda};
    IPQue_put_n(&q5.get, data, n);
    print_queue("q5", q5);

    c_drop(IPQue, &q1.get, &minq1.get, &q5.get);
}