(svn r25257) -Add: basic link graph (fonsinchen)

1 files changed, 254 insertions, 0 deletions

diff --git a/src/linkgraph/linkgraph.cpp b/src/linkgraph/linkgraph.cpp
new file mode 100644
index 000000000..dbaa02b41
--- /dev/null
+++ b/src/linkgraph/linkgraph.cpp
@@ -0,0 +1,254 @@
+/* $Id$ */
+
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file linkgraph.cpp Definition of link graph classes used for cargo distribution. */
+
+#include "../stdafx.h"
+#include "../core/pool_func.hpp"
+#include "linkgraph.h"
+
+/* Initialize the link-graph-pool */
+LinkGraphPool _link_graph_pool("LinkGraph");
+INSTANTIATE_POOL_METHODS(LinkGraph)
+
+/**
+ * Create a node or clear it.
+ * @param st ID of the associated station.
+ * @param demand Demand for cargo at the station.
+ */
+inline void LinkGraph::BaseNode::Init(StationID st, uint demand)
+{
+	this->supply = 0;
+	this->demand = demand;
+	this->station = st;
+	this->last_update = INVALID_DATE;
+}
+
+/**
+ * Create an edge.
+ * @param distance Length of the link as manhattan distance.
+ */
+inline void LinkGraph::BaseEdge::Init(uint distance)
+{
+	this->distance = distance;
+	this->capacity = 0;
+	this->usage = 0;
+	this->last_update = INVALID_DATE;
+	this->next_edge = INVALID_NODE;
+}
+
+void LinkGraph::Compress()
+{
+	this->last_compression = (_date + this->last_compression) / 2;
+	for (NodeID node1 = 0; node1 < this->Size(); ++node1) {
+		this->nodes[node1].supply /= 2;
+		for (NodeID node2 = 0; node2 < this->Size(); ++node2) {
+			BaseEdge &edge = this->edges[node1][node2];
+			if (edge.capacity > 0) {
+				edge.capacity = max(1U, edge.capacity / 2);
+				edge.usage /= 2;
+			}
+		}
+	}
+}
+
+/**
+ * Merge a link graph with another one.
+ * @param other LinkGraph to be merged into this one.
+ */
+void LinkGraph::Merge(LinkGraph *other)
+{
+	Date age = _date - this->last_compression + 1;
+	Date other_age = _date - other->last_compression + 1;
+	NodeID first = this->Size();
+	for (NodeID node1 = 0; node1 < other->Size(); ++node1) {
+		Station *st = Station::Get(other->nodes[node1].station);
+		NodeID new_node = this->AddNode(st);
+		this->nodes[new_node].supply = LinkGraph::Scale(other->nodes[node1].supply, age, other_age);
+		st->goods[this->cargo].link_graph = this->index;
+		st->goods[this->cargo].node = new_node;
+		for (NodeID node2 = 0; node2 < node1; ++node2) {
+			BaseEdge &forward = this->edges[new_node][first + node2];
+			BaseEdge &backward = this->edges[first + node2][new_node];
+			forward = other->edges[node1][node2];
+			backward = other->edges[node2][node1];
+			forward.capacity = LinkGraph::Scale(forward.capacity, age, other_age);
+			forward.usage = LinkGraph::Scale(forward.usage, age, other_age);
+			if (forward.next_edge != INVALID_NODE) forward.next_edge += first;
+			backward.capacity = LinkGraph::Scale(backward.capacity, age, other_age);
+			backward.usage = LinkGraph::Scale(backward.usage, age, other_age);
+			if (backward.next_edge != INVALID_NODE) backward.next_edge += first;
+		}
+		BaseEdge &new_start = this->edges[new_node][new_node];
+		new_start = other->edges[node1][node1];
+		if (new_start.next_edge != INVALID_NODE) new_start.next_edge += first;
+	}
+	delete other;
+}
+
+/**
+ * Remove a node from the link graph by overwriting it with the last node.
+ * @param id ID of the node to be removed.
+ */
+void LinkGraph::RemoveNode(NodeID id)
+{
+	assert(id < this->Size());
+
+	NodeID last_node = this->Size() - 1;
+	for (NodeID i = 0; i <= last_node; ++i) {
+		(*this)[i].RemoveEdge(id);
+		BaseEdge *node_edges = this->edges[i];
+		NodeID prev = i;
+		NodeID next = node_edges[i].next_edge;
+		while (next != INVALID_NODE) {
+			if (next == last_node) {
+				node_edges[prev].next_edge = id;
+				break;
+			}
+			prev = next;
+			next = node_edges[prev].next_edge;
+		}
+		node_edges[id] = node_edges[last_node];
+	}
+	Station::Get(this->nodes[last_node].station)->goods[this->cargo].node = id;
+	this->nodes.Erase(this->nodes.Get(id));
+	this->edges.EraseColumn(id);
+	/* Not doing EraseRow here, as having the extra invalid row doesn't hurt
+	 * and removing it would trigger a lot of memmove. The data has already
+	 * been copied around in the loop above. */
+}
+
+/**
+ * Add a node to the component and create empty edges associated with it. Set
+ * the station's last_component to this component. Calculate the distances to all
+ * other nodes. The distances to _all_ nodes are important as the demand
+ * calculator relies on their availability.
+ * @param st New node's station.
+ * @return New node's ID.
+ */
+NodeID LinkGraph::AddNode(const Station *st)
+{
+	const GoodsEntry &good = st->goods[this->cargo];
+
+	NodeID new_node = this->Size();
+	this->nodes.Append();
+	/* Avoid reducing the height of the matrix as that is expensive and we
+	 * most likely will increase it again later which is again expensive. */
+	this->edges.Resize(new_node + 1U,
+			max(new_node + 1U, this->edges.Height()));
+
+	this->nodes[new_node].Init(st->index,
+			HasBit(good.acceptance_pickup, GoodsEntry::GES_ACCEPTANCE));
+
+	BaseEdge *new_edges = this->edges[new_node];
+
+	/* Reset the first edge starting at the new node */
+	new_edges[new_node].next_edge = INVALID_NODE;
+
+	for (NodeID i = 0; i <= new_node; ++i) {
+		uint distance = DistanceManhattan(st->xy, Station::Get(this->nodes[i].station)->xy);
+		new_edges[i].Init(distance);
+		this->edges[i][new_node].Init(distance);
+	}
+	return new_node;
+}
+
+/**
+ * Fill an edge with values from a link.
+ * @param to Destination node of the link.
+ * @param capacity Capacity of the link.
+ */
+void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage)
+{
+	assert(this->index != to);
+	BaseEdge &edge = this->edges[to];
+	BaseEdge &first = this->edges[this->index];
+	edge.capacity = capacity;
+	edge.usage = usage == UINT_MAX ? 0 : usage;
+	edge.next_edge = first.next_edge;
+	first.next_edge = to;
+	edge.last_update = _date;
+}
+
+void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage)
+{
+	assert(capacity > 0);
+	assert(usage <= capacity || usage == UINT_MAX);
+	if (this->edges[to].last_update == INVALID_DATE) {
+		this->AddEdge(to, capacity, usage);
+	} else {
+		(*this)[to].Update(capacity, usage);
+	}
+}
+
+/**
+ * Remove an outgoing edge from this node.
+ * @param to ID of destination node.
+ */
+void LinkGraph::Node::RemoveEdge(NodeID to)
+{
+	if (this->index == to) return;
+	BaseEdge &edge = this->edges[to];
+	edge.capacity = 0;
+	edge.last_update = INVALID_DATE;
+	edge.usage = 0;
+
+	NodeID prev = this->index;
+	NodeID next = this->edges[this->index].next_edge;
+	while (next != INVALID_NODE) {
+		if (next == to) {
+			/* Will be removed, skip it. */
+			this->edges[prev].next_edge = edge.next_edge;
+			edge.next_edge = INVALID_NODE;
+			break;
+		} else {
+			prev = next;
+			next = this->edges[next].next_edge;
+		}
+	}
+}
+
+/**
+ * Create a new edge or update an existing one. If usage is UINT_MAX refresh
+ * the edge to have at least the given capacity, otherwise add the capacity.
+ * @param from Start node of the edge.
+ * @param to End node of the edge.
+ * @param capacity Capacity to be added/updated.
+ * @param usage Usage to be added or UINT_MAX.
+ */
+void LinkGraph::Edge::Update(uint capacity, uint usage)
+{
+	assert(this->edge.capacity > 0);
+	if (usage == UINT_MAX) {
+		this->edge.capacity = max(this->edge.capacity, capacity);
+	} else {
+		assert(capacity >= usage);
+		this->edge.capacity += capacity;
+		this->edge.usage += usage;
+	}
+	this->edge.last_update = _date;
+}
+
+/**
+ * Resize the component and fill it with empty nodes and edges. Used when
+ * loading from save games. The component is expected to be empty before.
+ * @param size New size of the component.
+ */
+void LinkGraph::Init(uint size)
+{
+	assert(this->Size() == 0);
+	this->edges.Resize(size, size);
+	this->nodes.Resize(size);
+
+	for (uint i = 0; i < size; ++i) {
+		this->nodes[i].Init();
+		BaseEdge *column = this->edges[i];
+		for (uint j = 0; j < size; ++j) column[j].Init();
+	}
+}