Mercurial > molko

changeset 110:d3bc14c1e243

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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();
 }