From 6524849386fa7b24814db93746c2c07c3de8f1c0 Mon Sep 17 00:00:00 2001 From: fonsinchen Date: Tue, 22 Oct 2013 16:13:54 +0000 Subject: (svn r25899) -Change: Restrict flows if links are restricted and don't normally pick them anymore. --- src/linkgraph/linkgraphjob.cpp | 3 ++ src/saveload/saveload.cpp | 3 +- src/saveload/station_sl.cpp | 13 +++-- src/station_base.h | 46 ++++++++++++++-- src/station_cmd.cpp | 119 +++++++++++++++++++++++++++++++++++++---- 5 files changed, 164 insertions(+), 20 deletions(-) diff --git a/src/linkgraph/linkgraphjob.cpp b/src/linkgraph/linkgraphjob.cpp index 242689e8d..ac22a38a4 100644 --- a/src/linkgraph/linkgraphjob.cpp +++ b/src/linkgraph/linkgraphjob.cpp @@ -69,6 +69,9 @@ LinkGraphJob::~LinkGraphJob() (*lg)[node_id][it->first].LastUpdate() == INVALID_DATE) { /* Edge has been removed. Delete flows. */ flows.DeleteFlows(to); + } else if ((*lg)[node_id][it->first].LastUnrestrictedUpdate() == INVALID_DATE) { + /* Edge is fully restricted. */ + flows.RestrictFlows(to); } } diff --git a/src/saveload/saveload.cpp b/src/saveload/saveload.cpp index a4ad9059b..88f812097 100644 --- a/src/saveload/saveload.cpp +++ b/src/saveload/saveload.cpp @@ -252,8 +252,9 @@ * 184 25508 * 185 25620 * 186 25833 + * 187 ????? */ -extern const uint16 SAVEGAME_VERSION = 186; ///< Current savegame version of OpenTTD. +extern const uint16 SAVEGAME_VERSION = 187; ///< Current savegame version of OpenTTD. SavegameType _savegame_type; ///< type of savegame we are loading diff --git a/src/saveload/station_sl.cpp b/src/saveload/station_sl.cpp index 8193bf623..d01c0f3c6 100644 --- a/src/saveload/station_sl.cpp +++ b/src/saveload/station_sl.cpp @@ -245,13 +245,15 @@ struct FlowSaveLoad { StationID source; StationID via; uint32 share; + bool restricted; }; static const SaveLoad _flow_desc[] = { - SLE_VAR(FlowSaveLoad, source, SLE_UINT16), - SLE_VAR(FlowSaveLoad, via, SLE_UINT16), - SLE_VAR(FlowSaveLoad, share, SLE_UINT32), - SLE_END() + SLE_VAR(FlowSaveLoad, source, SLE_UINT16), + SLE_VAR(FlowSaveLoad, via, SLE_UINT16), + SLE_VAR(FlowSaveLoad, share, SLE_UINT32), + SLE_CONDVAR(FlowSaveLoad, restricted, SLE_BOOL, 187, SL_MAX_VERSION), + SLE_END() }; /** @@ -481,6 +483,7 @@ static void RealSave_STNN(BaseStation *bst) for (FlowStat::SharesMap::const_iterator inner_it(shares->begin()); inner_it != shares->end(); ++inner_it) { flow.via = inner_it->second; flow.share = inner_it->first - sum_shares; + flow.restricted = inner_it->first > outer_it->second.GetUnrestricted(); sum_shares = inner_it->first; assert(flow.share > 0); SlObject(&flow, _flow_desc); @@ -538,7 +541,7 @@ static void Load_STNN() if (fs == NULL || prev_source != flow.source) { fs = &(st->goods[i].flows.insert(std::make_pair(flow.source, FlowStat(flow.via, flow.share))).first->second); } else { - fs->AppendShare(flow.via, flow.share); + fs->AppendShare(flow.via, flow.share, flow.restricted); } prev_source = flow.source; } diff --git a/src/station_base.h b/src/station_base.h index 7d5179128..1c3375a26 100644 --- a/src/station_base.h +++ b/src/station_base.h @@ -53,6 +53,7 @@ public: { assert(flow > 0); this->shares[flow] = st; + this->unrestricted = flow; } /** @@ -61,17 +62,23 @@ public: * inconsistencies. * @param st Remote station. * @param flow Amount of flow to be added. + * @param restricted If the flow to be added is restricted. */ - inline void AppendShare(StationID st, uint flow) + inline void AppendShare(StationID st, uint flow, bool restricted = false) { assert(flow > 0); this->shares[(--this->shares.end())->first + flow] = st; + if (!restricted) this->unrestricted += flow; } uint GetShare(StationID st) const; void ChangeShare(StationID st, int flow); + void RestrictShare(StationID st); + + void ReleaseShare(StationID st); + /** * Get the actual shares as a const pointer so that they can be iterated * over. @@ -79,24 +86,52 @@ public: */ inline const SharesMap *GetShares() const { return &this->shares; } + /** + * Return total amount of unrestricted shares. + * @return Amount of unrestricted shares. + */ + inline uint GetUnrestricted() const { return this->unrestricted; } + /** * Swap the shares maps, and thus the content of this FlowStat with the * other one. * @param other FlowStat to swap with. */ - inline void SwapShares(FlowStat &other) { this->shares.swap(other.shares); } + inline void SwapShares(FlowStat &other) + { + this->shares.swap(other.shares); + Swap(this->unrestricted, other.unrestricted); + } + + /** + * Get a station a package can be routed to. This done by drawing a + * random number between 0 and sum_shares and then looking that up in + * the map with lower_bound. So each share gets selected with a + * probability dependent on its flow. Do include restricted flows here. + * @param is_restricted Output if a restricted flow was chosen. + * @return A station ID from the shares map. + */ + inline StationID GetViaWithRestricted(bool &is_restricted) const + { + assert(!this->shares.empty()); + uint rand = RandomRange((--this->shares.end())->first); + is_restricted = rand >= this->unrestricted; + return this->shares.upper_bound(rand)->second; + } /** * Get a station a package can be routed to. This done by drawing a * random number between 0 and sum_shares and then looking that up in * the map with lower_bound. So each share gets selected with a - * probability dependent on its flow. + * probability dependent on its flow. Don't include restricted flows. * @return A station ID from the shares map. */ inline StationID GetVia() const { assert(!this->shares.empty()); - return this->shares.upper_bound(RandomRange((--this->shares.end())->first))->second; + return this->unrestricted > 0 ? + this->shares.upper_bound(RandomRange(this->unrestricted))->second : + INVALID_STATION; } StationID GetVia(StationID excluded, StationID excluded2 = INVALID_STATION) const; @@ -105,6 +140,7 @@ public: private: SharesMap shares; ///< Shares of flow to be sent via specified station (or consumed locally). + uint unrestricted; ///< Limit for unrestricted shares. }; /** Flow descriptions by origin stations. */ @@ -113,6 +149,8 @@ public: void AddFlow(StationID origin, StationID via, uint amount); void PassOnFlow(StationID origin, StationID via, uint amount); void DeleteFlows(StationID via); + void RestrictFlows(StationID via); + void ReleaseFlows(StationID via); void FinalizeLocalConsumption(StationID self); }; diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp index f8bf61968..477f761b4 100644 --- a/src/station_cmd.cpp +++ b/src/station_cmd.cpp @@ -3426,6 +3426,7 @@ void DeleteStaleLinks(Station *from) RerouteCargo(from, c, to->index, from->index); } else if (edge.LastUnrestrictedUpdate() != INVALID_DATE && (uint)(_date - edge.LastUnrestrictedUpdate()) > timeout) { edge.Restrict(); + ge.flows.RestrictFlows(to->index); RerouteCargo(from, c, to->index, from->index); } else if (edge.LastRestrictedUpdate() != INVALID_DATE && (uint)(_date - edge.LastRestrictedUpdate()) > timeout) { edge.Release(); @@ -4069,10 +4070,10 @@ uint FlowStat::GetShare(StationID st) const */ StationID FlowStat::GetVia(StationID excluded, StationID excluded2) const { + if (this->unrestricted == 0) return INVALID_STATION; assert(!this->shares.empty()); - uint max = (--this->shares.end())->first; - SharesMap::const_iterator it = this->shares.upper_bound(RandomRange(max)); - assert(it != this->shares.end()); + SharesMap::const_iterator it = this->shares.upper_bound(RandomRange(this->unrestricted)); + assert(it != this->shares.end() && it->first <= this->unrestricted); if (it->second != excluded && it->second != excluded2) return it->second; /* We've hit one of the excluded stations. @@ -4081,12 +4082,12 @@ StationID FlowStat::GetVia(StationID excluded, StationID excluded2) const uint end = it->first; uint begin = (it == this->shares.begin() ? 0 : (--it)->first); uint interval = end - begin; - if (interval >= max) return INVALID_STATION; // Only one station in the map. - uint new_max = max - interval; + if (interval >= this->unrestricted) return INVALID_STATION; // Only one station in the map. + uint new_max = this->unrestricted - interval; uint rand = RandomRange(new_max); SharesMap::const_iterator it2 = (rand < begin) ? this->shares.upper_bound(rand) : this->shares.upper_bound(rand + interval); - assert(it2 != this->shares.end()); + assert(it2 != this->shares.end() && it2->first <= this->unrestricted); if (it2->second != excluded && it2->second != excluded2) return it2->second; /* We've hit the second excluded station. @@ -4103,7 +4104,7 @@ StationID FlowStat::GetVia(StationID excluded, StationID excluded2) const Swap(interval, interval2); } rand = RandomRange(new_max); - SharesMap::const_iterator it3 = this->shares.end(); + SharesMap::const_iterator it3 = this->shares.upper_bound(this->unrestricted); if (rand < begin) { it3 = this->shares.upper_bound(rand); } else if (rand < begin2 - interval) { @@ -4111,7 +4112,7 @@ StationID FlowStat::GetVia(StationID excluded, StationID excluded2) const } else { it3 = this->shares.upper_bound(rand + interval + interval2); } - assert(it3 != this->shares.end()); + assert(it3 != this->shares.end() && it3->first <= this->unrestricted); return it3->second; } @@ -4125,8 +4126,11 @@ void FlowStat::Invalidate() assert(!this->shares.empty()); SharesMap new_shares; uint i = 0; + uint orig = 0; for (SharesMap::iterator it(this->shares.begin()); it != this->shares.end(); ++it) { new_shares[++i] = it->second; + orig += it->first; + if (orig == this->unrestricted) this->unrestricted = orig; } this->shares.swap(new_shares); assert(!this->shares.empty()); @@ -4134,7 +4138,7 @@ void FlowStat::Invalidate() /** * Change share for specified station. By specifing INT_MIN as parameter you - * can erase a share. + * can erase a share. Newly added flows will be unrestricted. * @param st Next Hop to be removed. * @param flow Share to be added or removed. */ @@ -4154,6 +4158,7 @@ void FlowStat::ChangeShare(StationID st, int flow) uint share = it->first - last_share; if (flow == INT_MIN || (uint)(-flow) >= share) { removed_shares += share; + if (it->first <= this->unrestricted) this->unrestricted -= share; if (flow != INT_MIN) flow += share; last_share = it->first; continue; // remove the whole share @@ -4162,6 +4167,7 @@ void FlowStat::ChangeShare(StationID st, int flow) } else { added_shares += (uint)(flow); } + if (it->first <= this->unrestricted) this->unrestricted += flow; /* If we don't continue above the whole flow has been added or * removed. */ @@ -4170,7 +4176,78 @@ void FlowStat::ChangeShare(StationID st, int flow) new_shares[it->first + added_shares - removed_shares] = it->second; last_share = it->first; } - if (flow > 0) new_shares[last_share + (uint)flow] = st; + if (flow > 0) { + new_shares[last_share + (uint)flow] = st; + if (this->unrestricted < last_share) { + this->ReleaseShare(st); + } else { + this->unrestricted += flow; + } + } + this->shares.swap(new_shares); +} + +/** + * Restrict a flow by moving it to the end of the map and decreasing the amount + * of unrestricted flow. + * @param st Station of flow to be restricted. + */ +void FlowStat::RestrictShare(StationID st) +{ + uint flow = 0; + uint last_share = 0; + SharesMap new_shares; + for (SharesMap::iterator it(this->shares.begin()); it != this->shares.end(); ++it) { + if (flow == 0) { + if (it->first > this->unrestricted) return; // Not present or already restricted. + if (it->second == st) { + flow = it->first - last_share; + this->unrestricted -= flow; + } else { + new_shares[it->first] = it->second; + } + } else { + new_shares[it->first - flow] = it->second; + } + last_share = it->first; + } + if (flow == 0) return; + new_shares[last_share + flow] = st; + this->shares.swap(new_shares); +} + +/** + * Release ("unrestrict") a flow by moving it to the begin of the map and + * increasing the amount of unrestricted flow. + * @param st Station of flow to be released. + */ +void FlowStat::ReleaseShare(StationID st) +{ + uint flow = 0; + uint next_share = 0; + bool found = false; + for (SharesMap::reverse_iterator it(this->shares.rbegin()); it != this->shares.rend(); ++it) { + if (it->first < this->unrestricted) return; // Note: not <= as the share may hit the limit. + if (found) { + flow = next_share - it->first; + this->unrestricted += flow; + break; + } else { + if (it->first == this->unrestricted) return; // !found -> Limit not hit. + if (it->second == st) found = true; + } + next_share = it->first; + } + if (flow == 0) return; + SharesMap new_shares; + new_shares[flow] = st; + for (SharesMap::iterator it(this->shares.begin()); it != this->shares.end(); ++it) { + if (it->second != st) { + new_shares[flow + it->first] = it->second; + } else { + flow = 0; + } + } this->shares.swap(new_shares); } @@ -4253,6 +4330,28 @@ void FlowStatMap::DeleteFlows(StationID via) } } +/** + * Restrict all flows at a station for specific cargo and destination. + * @param via Remote station of flows to be restricted. + */ +void FlowStatMap::RestrictFlows(StationID via) +{ + for (FlowStatMap::iterator it = this->begin(); it != this->end(); ++it) { + it->second.RestrictShare(via); + } +} + +/** + * Release all flows at a station for specific cargo and destination. + * @param via Remote station of flows to be released. + */ +void FlowStatMap::ReleaseFlows(StationID via) +{ + for (FlowStatMap::iterator it = this->begin(); it != this->end(); ++it) { + it->second.ReleaseShare(via); + } +} + /** * Get the sum of flows via a specific station from this GoodsEntry. * @param via Remote station to look for. -- cgit v1.2.3-54-g00ecf