From fb25143685df32ed91b84da9fb7f2e821ed7daaf Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 26 Mar 2021 07:11:32 +0100 Subject: Changed cpque declaration to using_cpque(X, Value, valueCompare), and valueCompare optional: more consistent with STC conventions. --- examples/cpque.c | 16 ++++----- examples/inits.c | 4 +-- examples/priority.c | 2 +- examples/stc_astar.c | 92 ++++++++++++++++++++++++++-------------------------- 4 files changed, 57 insertions(+), 57 deletions(-) (limited to 'examples') diff --git a/examples/cpque.c b/examples/cpque.c index ae869832..f9de44f1 100644 --- a/examples/cpque.c +++ b/examples/cpque.c @@ -4,12 +4,12 @@ // Implements c++ example: https://en.cppreference.com/w/cpp/container/priority_queue using_cvec(i, int); -using_cpque(imax, cvec_i); -using_cpque(imin, cvec_i, >); +#define imix_less(x, y) ((*(x) ^ 1) < (*(y) ^ 1)) +#define imix_cmp(x, y) c_less_compare(imix_less, x, y) -#define myless(left, right) ((left ^ 1) < (right ^ 1)) -static int cmp(const int *x, const int *y) { return myless(*y, *x) - myless(*x, *y); } -using_cpque(imix, cvec_i, <, cmp); +using_cpque(imax, cvec_i); +using_cpque(imin, cvec_i, -c_default_compare); +using_cpque(imix, cvec_i, imix_cmp); #define PRINT_Q(Q) \ void print_##Q(Q q) { \ @@ -37,13 +37,13 @@ int main() { print_cpque_imax(q); - cpque_imin q2 = cpque_imin_init(); + cpque_imin q2 = cpque_imin_init(); cpque_imin_emplace_n(&q2, data, c_arraylen(data)); print_cpque_imin(q2); - // Using myless cmp to compare elements. - cpque_imix q3 = cpque_imix_init(); + // Using imix_less to compare elements. + cpque_imix q3 = cpque_imix_init(); c_forrange (n, c_arraylen(data)) cpque_imix_push(&q3, n); diff --git a/examples/inits.c b/examples/inits.c index 23c7b551..26518e33 100644 --- a/examples/inits.c +++ b/examples/inits.c @@ -17,7 +17,7 @@ inline static int ipair_compare(const ipair_t* a, const ipair_t* b) { using_cvec(ip, ipair_t, ipair_compare); using_clist(ip, ipair_t, ipair_compare); using_cvec(f, float); -using_cpque(f, cvec_f, >); +using_cpque(f, cvec_f); int main(void) { @@ -34,7 +34,7 @@ int main(void) cpque_f_make_heap(&floats); c_emplace_items(&floats, cpque_f, {40.0f, 20.0f, 50.0f, 30.0f, 10.0f}); - // sorted: + puts("\npop and show high priorites first:"); while (! cpque_f_empty(floats)) { printf("%.1f ", *cpque_f_top(&floats)); cpque_f_pop(&floats); diff --git a/examples/priority.c b/examples/priority.c index 10e2f32a..ed7db584 100644 --- a/examples/priority.c +++ b/examples/priority.c @@ -7,7 +7,7 @@ #include using_cvec(i, int64_t); -using_cpque(i, cvec_i, >); // min-heap (increasing values) +using_cpque(i, cvec_i, -c_default_compare); // min-heap (increasing values) int main() { size_t N = 10000000; diff --git a/examples/stc_astar.c b/examples/stc_astar.c index d096c9fc..c22af8a8 100644 --- a/examples/stc_astar.c +++ b/examples/stc_astar.c @@ -17,42 +17,42 @@ typedef struct { } MazePoint; MazePoint -mpoint_init(int x, int y, int width) +mpnt_init(int x, int y, int width) { MazePoint p = { x, y, 0, width }; return p; } int -mpoint_compare_priority(const MazePoint* a, const MazePoint* b) +mpnt_compare_priority(const MazePoint* a, const MazePoint* b) { //return 0; // NB! gives 14 steps shorter path!? hmm.. - return (a->priorty > b->priorty) - (a->priorty < b->priorty); + return c_default_compare(&b->priorty, &a->priorty); // note: high priority is low cost } int -mpoint_equal(MazePoint* a, MazePoint* b) +mpnt_equal(MazePoint* a, MazePoint* b) { return a->x == b->x && a->y == b->y; } MazePoint -mpoint_from(cstr maze, const char* c, int width) +mpnt_from(cstr maze, const char* c, int width) { int index = cstr_find(maze, c); - return mpoint_init(index % width, index / width, width); + return mpnt_init(index % width, index / width, width); } int -mpoint_index(const MazePoint* p) +mpnt_index(const MazePoint* p) { return p->x + p->width * p->y; } int -mpoint_key_compare(const MazePoint* a, const MazePoint* b) +mpnt_key_compare(const MazePoint* a, const MazePoint* b) { - int i = mpoint_index(a); - int j = mpoint_index(b); + int i = mpnt_index(a); + int j = mpnt_index(b); return (i > j) - (i < j); } @@ -66,29 +66,29 @@ typedef struct { MazePoint b; } MazeStep; -using_cdeq(mp, MazePoint, mpoint_compare_priority); -using_cpque(mp, cdeq_mp, >); -using_csmap(ms, MazePoint, MazePoint, mpoint_key_compare); // step -using_csmap(mc, MazePoint, int, mpoint_key_compare); // cost +using_cdeq(pnt, MazePoint, c_no_compare); +using_cpque(pnt, cdeq_pnt, mpnt_compare_priority); +using_csmap(step, MazePoint, MazePoint, mpnt_key_compare); +using_csmap(cost, MazePoint, int, mpnt_key_compare); -cdeq_mp +cdeq_pnt astar(cstr maze, int width) { - MazePoint start = mpoint_from(maze, "@", width); - MazePoint goal = mpoint_from(maze, "!", width); - cpque_mp frontier = cpque_mp_init(); - csmap_ms came_from = csmap_ms_init(); - csmap_mc cost_so_far = csmap_mc_init(); + MazePoint start = mpnt_from(maze, "@", width); + MazePoint goal = mpnt_from(maze, "!", width); + cpque_pnt frontier = cpque_pnt_init(); + csmap_step came_from = csmap_step_init(); + csmap_cost cost_so_far = csmap_cost_init(); - cpque_mp_push(&frontier, start); - csmap_mc_emplace(&cost_so_far, start, 0); + cpque_pnt_push(&frontier, start); + csmap_cost_insert(&cost_so_far, start, 0); - while (!cpque_mp_empty(frontier)) + while (!cpque_pnt_empty(frontier)) { - MazePoint current = *cpque_mp_top(&frontier); - cpque_mp_pop(&frontier); - if (mpoint_equal(¤t, &goal)) + MazePoint current = *cpque_pnt_top(&frontier); + cpque_pnt_pop(&frontier); + if (mpnt_equal(¤t, &goal)) break; MazePoint deltas[] = { { -1, +1, 0, width }, { 0, +1, 0, width }, { 1, +1, 0, width }, @@ -99,33 +99,33 @@ astar(cstr maze, int width) c_forrange (i, c_arraylen(deltas)) { MazePoint delta = deltas[i]; - MazePoint next = mpoint_init(current.x + delta.x, current.y + delta.y, width); - int new_cost = *csmap_mc_at(&cost_so_far, current); - if (maze.str[mpoint_index(&next)] != '#') + MazePoint next = mpnt_init(current.x + delta.x, current.y + delta.y, width); + int new_cost = *csmap_cost_at(&cost_so_far, current); + if (maze.str[mpnt_index(&next)] != '#') { - csmap_mc_value_t* cost = csmap_mc_find(&cost_so_far, next).ref; + csmap_cost_value_t* cost = csmap_cost_find(&cost_so_far, next).ref; if (!cost || new_cost < cost->second) { - csmap_mc_emplace_or_assign(&cost_so_far, next, new_cost); // update (put) + csmap_cost_put(&cost_so_far, next, new_cost); // update next.priorty = new_cost + abs(goal.x - next.x) + abs(goal.y - next.y); - cpque_mp_push(&frontier, next); - csmap_ms_emplace_or_assign(&came_from, next, current); + cpque_pnt_push(&frontier, next); + csmap_step_put(&came_from, next, current); } } } } MazePoint current = goal; - cdeq_mp path = cdeq_mp_init(); + cdeq_pnt path = cdeq_pnt_init(); - while(!mpoint_equal(¤t, &start)) + while(!mpnt_equal(¤t, &start)) { - cdeq_mp_push_front(&path, current); - current = *csmap_ms_at(&came_from, current); + cdeq_pnt_push_front(&path, current); + current = *csmap_step_at(&came_from, current); } - cdeq_mp_push_front(&path, start); - cpque_mp_del(&frontier); - csmap_ms_del(&came_from); - csmap_mc_del(&cost_so_far); + cdeq_pnt_push_front(&path, start); + cpque_pnt_del(&frontier); + csmap_step_del(&came_from); + csmap_cost_del(&cost_so_far); return path; } @@ -157,14 +157,14 @@ main(void) "# # # # # # #\n" "#########################################################################\n"); int width = cstr_find(maze, "\n") + 1; - cdeq_mp path = astar(maze, width); + cdeq_pnt path = astar(maze, width); - printf("length: %zu\n", cdeq_mp_size(path)); + printf("length: %zu\n", cdeq_pnt_size(path)); - c_foreach (it, cdeq_mp, path) - maze.str[mpoint_index(it.ref)] = 'o'; + c_foreach (it, cdeq_pnt, path) + maze.str[mpnt_index(it.ref)] = 'x'; printf("%s", maze.str); cstr_del(&maze); - cdeq_mp_del(&path); + cdeq_pnt_del(&path); } \ No newline at end of file -- cgit v1.2.3