cpp/openttd-patchpack/source Changeset - r20332:287acb1cd994

Changeset - r20332:287acb1cd994

Parent rev.

Child rev.

[Not reviewed]

master

0 2 0

fonsinchen - 11 years ago 2013-06-09 12:48:42
fonsinchen@openttd.org

(svn r25345) -Add: implementation of SharesMap and FlowStatMap

2 files changed with 264 insertions and 0 deletions:

src/station_base.h

src/station_cmd.cpp

181

0 comments (0 inline, 0 general)

src/station_base.h

➞

Show inline comments

@@ @@ -12,12 +12,14 @@ @@
 #ifndef STATION_BASE_H
 #define STATION_BASE_H
 #include "core/random_func.hpp"
 #include "base_station_base.h"
 #include "newgrf_airport.h"
 #include "cargopacket.h"
 #include "industry_type.h"
 #include "linkgraph/linkgraph_type.h"
 #include "newgrf_storage.h"
 #include <map>
 typedef Pool<BaseStation, StationID, 32, 64000> StationPool;
 extern StationPool _station_pool;
@@ @@ -25,6 +27,87 @@ extern StationPool _station_pool; @@
 static const byte INITIAL_STATION_RATING = 175;
 /**
  * Flow statistics telling how much flow should be sent along a link. This is
  * done by creating "flow shares" and using std::map's upper_bound() method to
  * look them up with a random number. A flow share is the difference between a
  * key in a map and the previous key. So one key in the map doesn't actually
  * mean anything by itself.
  */
 class FlowStat {
 public:
 	typedef std::map<uint32, StationID> SharesMap;
 	/**
 	 * Invalid constructor. This can't be called as a FlowStat must not be
 	 * empty. However, the constructor must be defined and reachable for
 	 * FlwoStat to be used in a std::map.
 	 */
 	inline FlowStat() {NOT_REACHED();}
 	/**
 	 * Create a FlowStat with an initial entry.
 	 * @param st Station the initial entry refers to.
 	 * @param flow Amount of flow for the initial entry.
 	 */
 	inline FlowStat(StationID st, uint flow)
+	{
 		assert(flow > 0);
 		this->shares[flow] = st;
+	}
 	/**
 	 * Add some flow to the end of the shares map. Only do that if you know
 	 * that the station isn't in the map yet. Anything else may lead to
 	 * inconsistencies.
 	 * @param st Remote station.
 	 * @param flow Amount of flow to be added.
 	 */
 	inline void AppendShare(StationID st, uint flow)
+	{
 		assert(flow > 0);
 		this->shares[(--this->shares.end())->first + flow] = st;
+	}
 	uint GetShare(StationID st) const;
 	void ChangeShare(StationID st, int flow);
 	/**
 	 * Get the actual shares as a const pointer so that they can be iterated
 	 * over.
 	 * @return Actual shares.
 	 */
 	inline const SharesMap *GetShares() const { return &this->shares; }
 	/**
 	 * 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.
 	 * @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 - 1))->second;
+	}
 	StationID GetVia(StationID excluded, StationID excluded2 = INVALID_STATION) const;
 private:
 	SharesMap shares;  ///< Shares of flow to be sent via specified station (or consumed locally).
 };
 /** Flow descriptions by origin stations. */
 class FlowStatMap : public std::map<StationID, FlowStat> {
 public:
 	void AddFlow(StationID origin, StationID via, uint amount);
 	void PassOnFlow(StationID origin, StationID via, uint amount);
 	void DeleteFlows(StationID via);
 	void FinalizeLocalConsumption(StationID self);
 };
 /**
  * Stores station stats for a single cargo.
  */
 struct GoodsEntry {

src/station_cmd.cpp

➞

Show inline comments

@@ @@ -3979,6 +3979,187 @@ static CommandCost TerraformTile_Station @@
 	return DoCommand(tile, 0, 0, flags, CMD_LANDSCAPE_CLEAR);
+}
 /**
  * Get flow for a station.
  * @param st Station to get flow for.
  * @return Flow for st.
  */
 uint FlowStat::GetShare(StationID st) const
+{
 	uint32 prev = 0;
 	for (SharesMap::const_iterator it = this->shares.begin(); it != this->shares.end(); ++it) {
 		if (it->second == st) {
 			return it->first - prev;
 		} else {
 			prev = it->first;
+		}
+	}
 	return 0;
+}
 /**
  * Get a station a package can be routed to, but exclude the given one.
  * @param excluded StationID not to be selected.
  * @return A station ID from the shares map.
  */
 StationID FlowStat::GetVia(StationID excluded, StationID excluded2) const
+{
 	assert(!this->shares.empty());
 	uint max = (--this->shares.end())->first - 1;
 	SharesMap::const_iterator it = this->shares.upper_bound(RandomRange(max));
 	assert(it != this->shares.end());
 	if (it->second != excluded && it->second != excluded2) return it->second;
 	/* We've hit one of the excluded stations.
 	 * Draw another share, from outside its range. */
 	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;
 	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());
 	if (it2->second != excluded && it2->second != excluded2) return it2->second;
 	/* We've hit the second excluded station.
 	 * Same as before, only a bit more complicated. */
 	uint end2 = it2->first;
 	uint begin2 = (it2 == this->shares.begin() ? 0 : (--it2)->first);
 	uint interval2 = end2 - begin2;
 	if (interval2 > new_max) return INVALID_STATION; // Only the two excluded stations in the map.
 	new_max -= interval2;
 	if (begin > begin2) {
 		Swap(begin, begin2);
 		Swap(end, end2);
 		Swap(interval, interval2);
+	}
 	rand = RandomRange(new_max);
 	SharesMap::const_iterator it3 = this->shares.end();
 	if (rand < begin) {
 		it3 = this->shares.upper_bound(rand);
 	} else if (rand < begin2 - interval) {
 		it3 = this->shares.upper_bound(rand + interval);
 	} else {
 		it3 = this->shares.upper_bound(rand + interval + interval2);
+	}
 	assert(it3 != this->shares.end());
 	return it3->second;
+}
 /**
  * Change share for specified station. By specifing INT_MIN as parameter you
  * can erase a share.
  * @param st Next Hop to be removed.
  * @param flow Share to be added or removed.
  */
 void FlowStat::ChangeShare(StationID st, int flow)
+{
 	/* We assert only before changing as afterwards the shares can actually
 	 * be empty. In that case the whole flow stat must be deleted then. */
 	assert(!this->shares.empty());
 	int32 added_shares = 0;
 	uint32 last_share = 0;
 	SharesMap new_shares;
 	for (SharesMap::iterator it(this->shares.begin()); it != this->shares.end(); ++it) {
 		if (it->second == st) {
 			uint share = it->first - last_share;
 			int change = flow - added_shares;
 			uint new_share = (change < 0 && (uint)(-change) > share) ? 0 : share + change;
 			added_shares -= share;
 			added_shares += new_share;
 			if (new_share > 0) {
 				new_shares[it->first + added_shares] = it->second;
+			}
 		} else {
 			new_shares[it->first + added_shares] = it->second;
+		}
 		last_share = it->first;
+	}
 	if (flow > added_shares) {
 		new_shares[last_share + flow - added_shares] = st;
+	}
 	this->shares.swap(new_shares);
+}
 /**
  * Add some flow from "origin", going via "via".
  * @param origin Origin of the flow.
  * @param via Next hop.
  * @param flow Amount of flow to be added.
  */
 void FlowStatMap::AddFlow(StationID origin, StationID via, uint flow)
+{
 	FlowStatMap::iterator origin_it = this->find(origin);
 	if (origin_it == this->end()) {
 		this->insert(std::make_pair(origin, FlowStat(via, flow)));
 	} else {
 		origin_it->second.ChangeShare(via, flow);
 		assert(!origin_it->second.GetShares()->empty());
+	}
+}
 /**
  * Pass on some flow, remembering it as invalid, for later subtraction from
  * locally consumed flow. This is necessary because we can't have negative
  * flows and we don't want to sort the flows before adding them up.
  * @param origin Origin of the flow.
  * @param via Next hop.
  * @param flow Amount of flow to be passed.
  */
 void FlowStatMap::PassOnFlow(StationID origin, StationID via, uint flow)
+{
 	FlowStatMap::iterator prev_it = this->find(origin);
 	if (prev_it == this->end()) {
 		FlowStat fs(via, flow);
 		fs.AppendShare(INVALID_STATION, flow);
 		this->insert(std::make_pair(origin, fs));
 	} else {
 		prev_it->second.ChangeShare(via, flow);
 		prev_it->second.ChangeShare(INVALID_STATION, flow);
 		assert(!prev_it->second.GetShares()->empty());
+	}
+}
 /**
  * Subtract invalid flows from locally consumed flow.
  * @param self ID of own station.
  */
 void FlowStatMap::FinalizeLocalConsumption(StationID self)
+{
 	for (FlowStatMap::iterator i = this->begin(); i != this->end(); ++i) {
 		FlowStat &fs = i->second;
 		uint local = fs.GetShare(INVALID_STATION);
 		fs.ChangeShare(self, -local);
 		fs.ChangeShare(INVALID_STATION, -local);
 		/* If the local share is used up there must be a share for some
 		 * remote station. */
 		assert(!fs.GetShares()->empty());
+	}
+}
 /**
  * Delete all flows at a station for specific cargo and destination.
  * @param via Remote station of flows to be deleted.
  */
 void FlowStatMap::DeleteFlows(StationID via)
+{
 	for (FlowStatMap::iterator f_it = this->begin(); f_it != this->end();) {
 		FlowStat &s_flows = f_it->second;
 		s_flows.ChangeShare(via, INT_MIN);
 		if (s_flows.GetShares()->empty()) {
 			this->erase(f_it++);
 		} else {
 			++f_it;
+		}
+	}
+}
 extern const TileTypeProcs _tile_type_station_procs = {
 	DrawTile_Station,           // draw_tile_proc

0 comments (0 inline, 0 general)