Mercurial > molko
changeset 110:d3bc14c1e243
inventory: add sorting algorithms
author | David Demelier <markand@malikania.fr> |
---|---|
date | Thu, 02 Apr 2020 18:22:27 +0200 |
parents | 22014be67057 |
children | f17890fe144b |
files | examples/example-inventory.c src/core/inventory.c src/core/inventory.h src/core/inventory_dialog.c tests/test-inventory.c |
diffstat | 5 files changed, 213 insertions(+), 9 deletions(-) [+] |
line wrap: on
line diff
--- a/examples/example-inventory.c Thu Apr 02 12:10:00 2020 +0200 +++ b/examples/example-inventory.c Thu Apr 02 18:22:27 2020 +0200 @@ -143,9 +143,21 @@ .y = 60 }; - inventory_push(&inv, &items[0].item, 10); /* Potion */ - inventory_push(&inv, &items[1].item, 4); /* Fish */ - inventory_push(&inv, &items[2].item, 1); /* Sword */ + /* Add items manually to be able to sort. */ + inv.items[1][5].item = &items[0].item; + inv.items[1][5].amount = 12; + + inv.items[1][2].item = &items[0].item; + inv.items[1][2].amount = 9; + + inv.items[2][7].item = &items[1].item; + inv.items[2][7].amount = 9; + + inv.items[2][8].item = &items[1].item; + inv.items[2][8].amount = 3; + + inv.items[2][4].item = &items[2].item; + inv.items[2][4].amount = 1; run(&dlg); }
--- a/src/core/inventory.c Thu Apr 02 12:10:00 2020 +0200 +++ b/src/core/inventory.c Thu Apr 02 18:22:27 2020 +0200 @@ -18,11 +18,14 @@ #include <assert.h> #include <stddef.h> +#include <stdlib.h> #include <string.h> #include "inventory.h" #include "item.h" +#define INVENTORY_TOTAL (INVENTORY_ROWS_MAX * INVENTORY_COLS_MAX) + static bool can_be_used(struct inventory_slot *slot, const struct item *item) { @@ -98,6 +101,47 @@ return amount; } +static bool +merge(struct inventory_slot *slot, struct inventory_slot *other) +{ + assert(slot); + assert(slot->item); + assert(other); + + /* Not compatible, return false to let the sorting continue. */ + if (slot->item != other->item) + return false; + + while (slot->amount < slot->item->stackable && other->amount) { + slot->amount++; + other->amount--; + } + + /* No more amount in the other slot, empty it. */ + if (other->amount == 0U) + memset(other, 0, sizeof (*other)); + + return slot->amount >= slot->item->stackable; +} + +static void +sort(struct inventory *iv, struct inventory_slot *slot, int r, int c) +{ + assert(slot); + assert(slot->item); + + /* Merge until the end of thiw row. */ + for (c = c + 1; c < INVENTORY_COLS_MAX; ++c) + if (merge(slot, &iv->items[r][c])) + return; + + /* Merge the next rows. */ + for (r = r + 1; r < INVENTORY_ROWS_MAX; ++r) + for (c = 0; c < INVENTORY_COLS_MAX; ++c) + if (merge(slot, &iv->items[r][c])) + return; +} + unsigned int inventory_push(struct inventory *iv, struct item *item, unsigned int amount) { @@ -117,6 +161,46 @@ return amount; } +static int +compare_slot(const void *v1, const void *v2) +{ + const struct inventory_slot *slot1 = v1; + const struct inventory_slot *slot2 = v2; + int cmp; + + /* Two null slots compare equal. */ + if (!slot1->item && !slot2->item) + return 0; + + /* Null left should be moved after. */ + if (!slot1->item) + return 1; + + /* Null right slots should be moved after. */ + if (!slot2->item) + return -1; + + /* If they are identical, use amount to sort. */ + if ((cmp = strcmp(slot1->item->name, slot2->item->name)) == 0) + return (long long int)slot2->amount - (long long int)slot1->amount; + + return cmp; +} + +void +inventory_sort(struct inventory *iv) +{ + assert(iv); + + for (int r = 0; r < INVENTORY_ROWS_MAX; ++r) + for (int c = 0; c < INVENTORY_COLS_MAX; ++c) + if (iv->items[r][c].item) + sort(iv, &iv->items[r][c], r, c); + + /* Sort by names AND by amount. */ + qsort(iv->items, INVENTORY_TOTAL, sizeof (struct inventory_slot), compare_slot); +} + void inventory_clear(struct inventory *iv) {
--- a/src/core/inventory.h Thu Apr 02 12:10:00 2020 +0200 +++ b/src/core/inventory.h Thu Apr 02 18:22:27 2020 +0200 @@ -73,6 +73,16 @@ inventory_push(struct inventory *iv, struct item *item, unsigned int amount); /** + * Sort the inventory. + * + * \pre iv != NULL + * \pre item != NULL + * \param iv the inventory + */ +void +inventory_sort(struct inventory *iv); + +/** * Clears the inventory. * * \pre iv != NULL
--- a/src/core/inventory_dialog.c Thu Apr 02 12:10:00 2020 +0200 +++ b/src/core/inventory_dialog.c Thu Apr 02 18:22:27 2020 +0200 @@ -279,14 +279,12 @@ break; } -#if 0 - button_handle(&data.sort, event); + button_handle(&dlg->bsort, event); - if (data.sort.state == BUTTON_STATE_ACTIVATED) { - inventory_sort(data.inv); - button_reset(&data.sort); + if (dlg->bsort.state == BUTTON_STATE_ACTIVATED) { + inventory_sort(dlg->inv); + button_reset(&dlg->bsort); } -#endif } void
--- a/tests/test-inventory.c Thu Apr 02 12:10:00 2020 +0200 +++ b/tests/test-inventory.c Thu Apr 02 18:22:27 2020 +0200 @@ -32,6 +32,17 @@ .stackable = 64 }; +static struct item sword = { + .name = "Sword", + .stackable = 1 +}; + +#define SET(iv, r, c, i, a) \ +do { \ + (iv)->items[(r)][(c)].item = (i); \ + (iv)->items[(r)][(c)].amount = (a); \ +} while (0) \ + GREATEST_TEST push_simple(void) { @@ -148,6 +159,94 @@ GREATEST_RUN_TEST(push_other); } +GREATEST_TEST +sort_simple(void) +{ + struct inventory inv = { 0 }; + + /* + * Create this inventory: + * + * 0 1 2 3 4 5 6 7 8 9 + * 0 [ ] [P:10] [ ] [ ] [S: 1] [ ] [ ] [E:24] [ ] [ ] + * 1 [ ] [ ] [P:12] [ ] [ ] [ ] [ ] [ ] [ ] [ ] + * 2 [ ] [ ] [ ] [ ] [E: 8] [ ] [ ] [ ] [P: 5] [ ] + */ + SET(&inv, 0, 1, &potion, 10); + SET(&inv, 0, 4, &sword, 1); + SET(&inv, 0, 7, &elixir, 24); + SET(&inv, 1, 2, &potion, 12); + SET(&inv, 2, 4, &elixir, 8); + SET(&inv, 2, 8, &potion, 5); + + /* + * Should look like this: + * + * 0 1 2 3 4 5 6 7 8 9 + * 0 [E:32] [P:27] [S: 1] [ ] [ ] [ ] [ ] [ ] [ ] [ ] + * 1 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] + * 2 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] + */ + inventory_sort(&inv); + GREATEST_ASSERT_EQ(inv.items[0][0].item, &elixir); + GREATEST_ASSERT_EQ(inv.items[0][0].amount, 32U); + GREATEST_ASSERT_EQ(inv.items[0][1].item, &potion); + GREATEST_ASSERT_EQ(inv.items[0][1].amount, 27U); + GREATEST_ASSERT_EQ(inv.items[0][2].item, &sword); + GREATEST_ASSERT_EQ(inv.items[0][2].amount, 1U); + + GREATEST_PASS(); +} + +GREATEST_TEST +sort_with_full(void) +{ + struct inventory inv = { 0 }; + + /* + * Create this inventory: + * + * 0 1 2 3 4 5 6 7 8 9 + * 0 [ ] [P:62] [ ] [ ] [S: 1] [ ] [ ] [E:64] [ ] [ ] + * 1 [ ] [ ] [P:12] [ ] [ ] [ ] [ ] [ ] [ ] [ ] + * 2 [ ] [ ] [ ] [ ] [E: 8] [ ] [ ] [ ] [P: 5] [ ] + */ + SET(&inv, 0, 1, &potion, 62); + SET(&inv, 0, 4, &sword, 1); + SET(&inv, 0, 7, &elixir, 64); + SET(&inv, 1, 2, &potion, 12); + SET(&inv, 2, 4, &elixir, 8); + SET(&inv, 2, 8, &potion, 5); + + /* + * Should look like this: + * + * 0 1 2 3 4 5 6 7 8 9 + * 0 [E:64] [E: 8] [P:64] [P:10] [S: 1] [ ] [ ] [ ] [ ] [ ] + * 1 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] + * 2 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] + */ + inventory_sort(&inv); + GREATEST_ASSERT_EQ(inv.items[0][0].item, &elixir); + GREATEST_ASSERT_EQ(inv.items[0][0].amount, 64U); + GREATEST_ASSERT_EQ(inv.items[0][1].item, &elixir); + GREATEST_ASSERT_EQ(inv.items[0][1].amount, 8U); + GREATEST_ASSERT_EQ(inv.items[0][2].item, &potion); + GREATEST_ASSERT_EQ(inv.items[0][2].amount, 64U); + GREATEST_ASSERT_EQ(inv.items[0][3].item, &potion); + GREATEST_ASSERT_EQ(inv.items[0][3].amount, 15U); + GREATEST_ASSERT_EQ(inv.items[0][4].item, &sword); + GREATEST_ASSERT_EQ(inv.items[0][4].amount, 1U); + + GREATEST_PASS(); +} + +GREATEST_SUITE(sort) +{ + GREATEST_RUN_TEST(sort_simple); + GREATEST_RUN_TEST(sort_with_full); +} + GREATEST_MAIN_DEFS(); int @@ -155,5 +254,6 @@ { GREATEST_MAIN_BEGIN(); GREATEST_RUN_SUITE(push); + GREATEST_RUN_SUITE(sort); GREATEST_MAIN_END(); }