From 863ff6522b671ce69a1265fe246149b25e83a847 Mon Sep 17 00:00:00 2001
From: rubidium <rubidium@openttd.org>
Date: Wed, 12 May 2010 18:31:39 +0000
Subject: (svn r19798) -Codechange: generalise the waypoint naming method

---
 src/town.h | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 64 insertions(+)

(limited to 'src/town.h')

diff --git a/src/town.h b/src/town.h
index d589d8f1e..b1cae99cc 100644
--- a/src/town.h
+++ b/src/town.h
@@ -258,4 +258,68 @@ static inline uint TileHash2Bit(uint x, uint y)
 	return GB(TileHash(x, y), 0, 2);
 }
 
+/**
+ * Set the default name for a depot/waypoint
+ * @tparam T The type/class to make a default name for
+ * @param obj The object/instance we want to find the name for
+ */
+template <class T>
+void MakeDefaultName(T *obj)
+{
+	/* We only want to set names if it hasn't been set before. */
+	assert(obj->name == NULL);
+
+	obj->town = ClosestTownFromTile(obj->xy, UINT_MAX);
+
+	/* Find first unused number belonging to this town. This can never fail,
+	 * as long as there can be at most 65535 waypoints/depots in total.
+	 *
+	 * This does 'n * m' search, but with 32bit 'used' bitmap, it needs at
+	 * most 'n * (1 + ceil(m / 32))' steps (n - number of waypoints in pool,
+	 * m - number of waypoints near this town).
+	 * Usually, it needs only 'n' steps.
+	 *
+	 * If it wasn't using 'used' and 'idx', it would just search for increasing 'next',
+	 * but this way it is faster */
+
+	uint32 used = 0; // bitmap of used waypoint numbers, sliding window with 'next' as base
+	uint32 next = 0; // first number in the bitmap
+	uint32 idx  = 0; // index where we will stop
+	uint32 cid  = 0; // current index, goes to T::GetPoolSize()-1, then wraps to 0
+
+	do {
+		T *lobj = T::GetIfValid(cid);
+
+		/* check only valid waypoints... */
+		if (lobj != NULL && obj != lobj) {
+			/* only objects with 'generic' name within the same city and with the same type*/
+			if (lobj->name == NULL && lobj->town == obj->town && lobj->IsOfType(obj)) {
+				/* if lobj->town_cn < next, uint will overflow to '+inf' */
+				uint i = (uint)lobj->town_cn - next;
+
+				if (i < 32) {
+					SetBit(used, i); // update bitmap
+					if (i == 0) {
+						/* shift bitmap while the lowest bit is '1';
+						 * increase the base of the bitmap too */
+						do {
+							used >>= 1;
+							next++;
+						} while (HasBit(used, 0));
+						/* when we are at 'idx' again at end of the loop and
+						 * 'next' hasn't changed, then no object had town_cn == next,
+						 * so we can safely use it */
+						idx = cid;
+					}
+				}
+			}
+		}
+
+		cid++;
+		if (cid == T::GetPoolSize()) cid = 0; // wrap to zero...
+	} while (cid != idx);
+
+	obj->town_cn = (uint16)next; // set index...
+}
+
 #endif /* TOWN_H */
-- 
cgit v1.2.3-54-g00ecf