summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorfonsinchen <fonsinchen@openttd.org>2013-10-22 16:13:54 +0000
committerfonsinchen <fonsinchen@openttd.org>2013-10-22 16:13:54 +0000
commit6524849386fa7b24814db93746c2c07c3de8f1c0 (patch)
tree8fd05e9a727286abff1f36c1d69c4411e0c4052a
parent29e987f3fc13dc1e2a90f07556bf033b81a13e36 (diff)
downloadopenttd-6524849386fa7b24814db93746c2c07c3de8f1c0.tar.xz
(svn r25899) -Change: Restrict flows if links are restricted and don't normally pick them anymore.
-rw-r--r--src/linkgraph/linkgraphjob.cpp3
-rw-r--r--src/saveload/saveload.cpp3
-rw-r--r--src/saveload/station_sl.cpp13
-rw-r--r--src/station_base.h46
-rw-r--r--src/station_cmd.cpp119
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.
@@ -80,23 +87,51 @@ 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);
}
@@ -4254,6 +4331,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.
* @return a FlowStat with all flows for 'via' added up.