From 863ff6522b671ce69a1265fe246149b25e83a847 Mon Sep 17 00:00:00 2001 From: rubidium Date: Wed, 12 May 2010 18:31:39 +0000 Subject: (svn r19798) -Codechange: generalise the waypoint naming method --- src/town.h | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/waypoint_base.h | 11 +++++++++ src/waypoint_cmd.cpp | 66 ++++------------------------------------------------ 3 files changed, 79 insertions(+), 62 deletions(-) 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 +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 */ diff --git a/src/waypoint_base.h b/src/waypoint_base.h index 3f8a48db9..7dc7a5753 100644 --- a/src/waypoint_base.h +++ b/src/waypoint_base.h @@ -49,6 +49,17 @@ struct Waypoint : SpecializedStation { { return (this->facilities & FACIL_TRAIN) != 0 && this->train_station.w == 1 && this->train_station.h == 1; } + + /** + * Is the "type" of waypoint the same as the given waypoint, + * i.e. are both a rail waypoint or are both a buoy? + * @param wp The waypoint to compare to. + * @return true iff their types are equal. + */ + FORCEINLINE bool IsOfType(const Waypoint *wp) const + { + return this->string_id == wp->string_id; + } }; #define FOR_ALL_WAYPOINTS(var) FOR_ALL_BASE_STATIONS_OF_TYPE(Waypoint, var) diff --git a/src/waypoint_cmd.cpp b/src/waypoint_cmd.cpp index 5e8ce29bd..cf333f4ed 100644 --- a/src/waypoint_cmd.cpp +++ b/src/waypoint_cmd.cpp @@ -43,65 +43,6 @@ void Waypoint::UpdateVirtCoord() InvalidateWindowData(WC_WAYPOINT_VIEW, this->index); } -/** - * Set the default name for a waypoint - * @param wp Waypoint to work on - */ -static void MakeDefaultWaypointName(Waypoint *wp) -{ - uint32 used = 0; // bitmap of used waypoint numbers, sliding window with 'next' as base - uint32 next = 0; // first waypoint number in the bitmap - StationID idx = 0; // index where we will stop - - wp->town = ClosestTownFromTile(wp->xy, UINT_MAX); - - /* Find first unused waypoint number belonging to this town. This can never fail, - * as long as there can be at most 65535 waypoints 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 */ - - StationID cid = 0; // current index, goes to Waypoint::GetPoolSize()-1, then wraps to 0 - do { - Waypoint *lwp = Waypoint::GetIfValid(cid); - - /* check only valid waypoints... */ - if (lwp != NULL && wp != lwp) { - /* only waypoints with 'generic' name within the same city */ - if (lwp->name == NULL && lwp->town == wp->town && lwp->string_id == wp->string_id) { - /* if lwp->town_cn < next, uint will overflow to '+inf' */ - uint i = (uint)lwp->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 waypoint had town_cn == next, - * so we can safely use it */ - idx = cid; - } - } - } - } - - cid++; - if (cid == Waypoint::GetPoolSize()) cid = 0; // wrap to zero... - } while (cid != idx); - - wp->town_cn = (uint16)next; // set index... - wp->name = NULL; // ... and use generic name -} - /** * Find a deleted waypoint close to a tile. * @param tile to search from @@ -295,7 +236,7 @@ CommandCost CmdBuildRailWaypoint(TileIndex start_tile, DoCommandFlag flags, uint wp->string_id = STR_SV_STNAME_WAYPOINT; wp->train_station = new_location; - if (wp->town == NULL) MakeDefaultWaypointName(wp); + if (wp->town == NULL) MakeDefaultName(wp); wp->UpdateVirtCoord(); @@ -365,7 +306,7 @@ CommandCost CmdBuildBuoy(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 wp->build_date = _date; - if (wp->town == NULL) MakeDefaultWaypointName(wp); + if (wp->town == NULL) MakeDefaultName(wp); MakeBuoy(tile, wp->index, GetWaterClass(tile)); @@ -459,7 +400,8 @@ CommandCost CmdRenameWaypoint(TileIndex tile, DoCommandFlag flags, uint32 p1, ui free(wp->name); if (reset) { - MakeDefaultWaypointName(wp); // sets wp->name = NULL + wp->name = NULL; + MakeDefaultName(wp); } else { wp->name = strdup(text); } -- cgit v1.2.3-54-g00ecf