summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--projects/openttd_vs100.vcxproj3
-rw-r--r--projects/openttd_vs100.vcxproj.filters9
-rw-r--r--projects/openttd_vs80.vcproj12
-rw-r--r--projects/openttd_vs90.vcproj12
-rw-r--r--source.list4
-rw-r--r--src/linkgraph/linkgraph.cpp254
-rw-r--r--src/linkgraph/linkgraph.h516
-rw-r--r--src/linkgraph/linkgraph_base.h26
-rw-r--r--src/linkgraph/linkgraph_type.h24
-rw-r--r--src/station_base.h8
10 files changed, 867 insertions, 1 deletions
diff --git a/projects/openttd_vs100.vcxproj b/projects/openttd_vs100.vcxproj
index 9ac4fdbf5..e8048fe01 100644
--- a/projects/openttd_vs100.vcxproj
+++ b/projects/openttd_vs100.vcxproj
@@ -331,6 +331,7 @@
<ClCompile Include="..\src\ini.cpp" />
<ClCompile Include="..\src\ini_load.cpp" />
<ClCompile Include="..\src\landscape.cpp" />
+ <ClCompile Include="..\src\linkgraph\linkgraph.cpp" />
<ClCompile Include="..\src\map.cpp" />
<ClCompile Include="..\src\misc.cpp" />
<ClCompile Include="..\src\mixer.cpp" />
@@ -469,6 +470,8 @@
<ClInclude Include="..\src\landscape.h" />
<ClInclude Include="..\src\landscape_type.h" />
<ClInclude Include="..\src\language.h" />
+ <ClInclude Include="..\src\linkgraph\linkgraph.h" />
+ <ClInclude Include="..\src\linkgraph\linkgraph_type.h" />
<ClInclude Include="..\src\livery.h" />
<ClInclude Include="..\src\map_func.h" />
<ClInclude Include="..\src\map_type.h" />
diff --git a/projects/openttd_vs100.vcxproj.filters b/projects/openttd_vs100.vcxproj.filters
index be2ef3586..59d6993e1 100644
--- a/projects/openttd_vs100.vcxproj.filters
+++ b/projects/openttd_vs100.vcxproj.filters
@@ -222,6 +222,9 @@
<ClCompile Include="..\src\landscape.cpp">
<Filter>Source Files</Filter>
</ClCompile>
+ <ClCompile Include="..\src\linkgraph\linkgraph.cpp">
+ <Filter>Source Files</Filter>
+ </ClCompile>
<ClCompile Include="..\src\map.cpp">
<Filter>Source Files</Filter>
</ClCompile>
@@ -636,6 +639,12 @@
<ClInclude Include="..\src\language.h">
<Filter>Header Files</Filter>
</ClInclude>
+ <ClInclude Include="..\src\linkgraph\linkgraph.h">
+ <Filter>Header Files</Filter>
+ </ClInclude>
+ <ClInclude Include="..\src\linkgraph\linkgraph_type.h">
+ <Filter>Header Files</Filter>
+ </ClInclude>
<ClInclude Include="..\src\livery.h">
<Filter>Header Files</Filter>
</ClInclude>
diff --git a/projects/openttd_vs80.vcproj b/projects/openttd_vs80.vcproj
index 1e62a5daa..4e2cb1c72 100644
--- a/projects/openttd_vs80.vcproj
+++ b/projects/openttd_vs80.vcproj
@@ -595,6 +595,10 @@
>
</File>
<File
+ RelativePath=".\..\src\linkgraph\linkgraph.cpp"
+ >
+ </File>
+ <File
RelativePath=".\..\src\map.cpp"
>
</File>
@@ -1151,6 +1155,14 @@
>
</File>
<File
+ RelativePath=".\..\src\linkgraph\linkgraph.h"
+ >
+ </File>
+ <File
+ RelativePath=".\..\src\linkgraph\linkgraph_type.h"
+ >
+ </File>
+ <File
RelativePath=".\..\src\livery.h"
>
</File>
diff --git a/projects/openttd_vs90.vcproj b/projects/openttd_vs90.vcproj
index e5bc489ab..a5af31edb 100644
--- a/projects/openttd_vs90.vcproj
+++ b/projects/openttd_vs90.vcproj
@@ -592,6 +592,10 @@
>
</File>
<File
+ RelativePath=".\..\src\linkgraph\linkgraph.cpp"
+ >
+ </File>
+ <File
RelativePath=".\..\src\map.cpp"
>
</File>
@@ -1148,6 +1152,14 @@
>
</File>
<File
+ RelativePath=".\..\src\linkgraph\linkgraph.h"
+ >
+ </File>
+ <File
+ RelativePath=".\..\src\linkgraph\linkgraph_type.h"
+ >
+ </File>
+ <File
RelativePath=".\..\src\livery.h"
>
</File>
diff --git a/source.list b/source.list
index 09f78a963..16f55b42d 100644
--- a/source.list
+++ b/source.list
@@ -39,6 +39,7 @@ hotkeys.cpp
ini.cpp
ini_load.cpp
landscape.cpp
+linkgraph/linkgraph.cpp
map.cpp
misc.cpp
mixer.cpp
@@ -202,6 +203,9 @@ ini_type.h
landscape.h
landscape_type.h
language.h
+linkgraph/linkgraph.h
+linkgraph/linkgraph_base.h
+linkgraph/linkgraph_type.h
livery.h
map_func.h
map_type.h
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();
+ }
+}
diff --git a/src/linkgraph/linkgraph.h b/src/linkgraph/linkgraph.h
new file mode 100644
index 000000000..8dfe3f8ea
--- /dev/null
+++ b/src/linkgraph/linkgraph.h
@@ -0,0 +1,516 @@
+/* $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.h Declaration of link graph classes used for cargo distribution. */
+
+#ifndef LINKGRAPH_H
+#define LINKGRAPH_H
+
+#include "../core/pool_type.hpp"
+#include "../core/smallmap_type.hpp"
+#include "../core/smallmatrix_type.hpp"
+#include "../station_base.h"
+#include "../cargotype.h"
+#include "../date_func.h"
+#include "linkgraph_type.h"
+
+struct SaveLoad;
+class LinkGraph;
+
+/**
+ * Type of the pool for link graph components. Each station can be in at up to
+ * 32 link graphs. So we allow for plenty of them to be created.
+ */
+typedef Pool<LinkGraph, LinkGraphID, 32, 0xFFFFFF> LinkGraphPool;
+/** The actual pool with link graphs. */
+extern LinkGraphPool _link_graph_pool;
+
+/**
+ * A connected component of a link graph. Contains a complete set of stations
+ * connected by links as nodes and edges. Each component also holds a copy of
+ * the link graph settings at the time of its creation. The global settings
+ * might change between the creation and join time so we can't rely on them.
+ */
+class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
+public:
+
+ /**
+ * Node of the link graph. contains all relevant information from the associated
+ * station. It's copied so that the link graph job can work on its own data set
+ * in a separate thread.
+ */
+ struct BaseNode {
+ uint supply; ///< Supply at the station.
+ uint demand; ///< Acceptance at the station.
+ StationID station; ///< Station ID.
+ Date last_update; ///< When the supply was last updated.
+ void Init(StationID st = INVALID_STATION, uint demand = 0);
+ };
+
+ /**
+ * An edge in the link graph. Corresponds to a link between two stations or at
+ * least the distance between them. Edges from one node to itself contain the
+ * ID of the opposite Node of the first active edge (i.e. not just distance) in
+ * the column as next_edge.
+ */
+ struct BaseEdge {
+ uint distance; ///< Length of the link.
+ uint capacity; ///< Capacity of the link.
+ uint usage; ///< Usage of the link.
+ Date last_update; ///< When the link was last updated.
+ NodeID next_edge; ///< Destination of next valid edge starting at the same source node.
+ void Init(uint distance = 0);
+ };
+
+ /**
+ * Wrapper for an edge (const or not) allowing retrieval, but no modification.
+ * @tparam Tedge Actual edge class, may be "const BaseEdge" or just "BaseEdge".
+ */
+ template<typename Tedge>
+ class EdgeWrapper {
+ protected:
+ Tedge &edge; ///< Actual edge to be used.
+
+ public:
+
+ /**
+ * Wrap a an edge.
+ * @param edge Edge to be wrapped.
+ */
+ EdgeWrapper (Tedge &edge) : edge(edge) {}
+
+ /**
+ * Get edge's capacity.
+ * @return Capacity.
+ */
+ uint Capacity() const { return this->edge.capacity; }
+
+ /**
+ * Get edge's usage.
+ * @return Usage.
+ */
+ uint Usage() const { return this->edge.usage; }
+
+ /**
+ * Get edge's distance.
+ * @return Distance.
+ */
+ uint Distance() const { return this->edge.distance; }
+
+ /**
+ * Get edge's last update.
+ * @return Last update.
+ */
+ Date LastUpdate() const { return this->edge.last_update; }
+ };
+
+ /**
+ * Wrapper for a node (const or not) allowing retrieval, but no modification.
+ * @tparam Tedge Actual node class, may be "const BaseNode" or just "BaseNode".
+ * @tparam Tedge Actual edge class, may be "const BaseEdge" or just "BaseEdge".
+ */
+ template<typename Tnode, typename Tedge>
+ class NodeWrapper {
+ protected:
+ Tnode &node; ///< Node being wrapped.
+ Tedge *edges; ///< Outgoing edges for wrapped node.
+ NodeID index; ///< ID of wrapped node.
+
+ public:
+
+ /**
+ * Wrap a node.
+ * @param node Node to be wrapped.
+ * @param edges Outgoing edges for node to be wrapped.
+ * @param index ID of node to be wrapped.
+ */
+ NodeWrapper(Tnode &node, Tedge *edges, NodeID index) : node(node),
+ edges(edges), index(index) {}
+
+ /**
+ * Get supply of wrapped node.
+ * @return Supply.
+ */
+ uint Supply() const { return this->node.supply; }
+
+ /**
+ * Get demand of wrapped node.
+ * @return Demand.
+ */
+ uint Demand() const { return this->node.demand; }
+
+ /**
+ * Get ID of station belonging to wrapped node.
+ * @return ID of node's station.
+ */
+ StationID Station() const { return this->node.station; }
+
+ /**
+ * Get node's last update.
+ * @return Last update.
+ */
+ Date LastUpdate() const { return this->node.last_update; }
+ };
+
+ /**
+ * Base class for iterating across outgoing edges of a node. Only the real
+ * edges (those with capacity) are iterated. The ones with only distance
+ * information are skipped.
+ * @tparam Tedge Actual edge class. May be "BaseEdge" or "const BaseEdge".
+ * @tparam Titer Actual iterator class.
+ */
+ template <class Tedge, class Tedge_wrapper, class Titer>
+ class BaseEdgeIterator {
+ protected:
+ Tedge *base; ///< Array of edges being iterated.
+ NodeID current; ///< Current offset in edges array.
+
+ /**
+ * A "fake" pointer to enable operator-> on temporaries. As the objects
+ * returned from operator* aren't references but real objects, we have
+ * to return something that implements operator->, but isn't a pointer
+ * from operator->. A fake pointer.
+ */
+ class FakePointer : public SmallPair<NodeID, Tedge_wrapper> {
+ public:
+
+ /**
+ * Construct a fake pointer from a pair of NodeID and edge.
+ * @param pair Pair to be "pointed" to (in fact shallow-copied).
+ */
+ FakePointer(const SmallPair<NodeID, Tedge_wrapper> &pair) : SmallPair<NodeID, Tedge_wrapper>(pair) {}
+
+ /**
+ * Retrieve the pair by operator->.
+ * @return Pair being "pointed" to.
+ */
+ SmallPair<NodeID, Tedge_wrapper> *operator->() { return this; }
+ };
+
+ public:
+ /**
+ * Constructor.
+ * @param base Array of edges to be iterated.
+ * @param current ID of current node (to locate the first edge).
+ */
+ BaseEdgeIterator (Tedge *base, NodeID current) :
+ base(base),
+ current(current == INVALID_NODE ? current : base[current].next_edge)
+ {}
+
+ /**
+ * Prefix-increment.
+ * @return This.
+ */
+ Titer &operator++()
+ {
+ this->current = this->base[this->current].next_edge;
+ return static_cast<Titer &>(*this);
+ }
+
+ /**
+ * Postfix-increment.
+ * @return Version of this before increment.
+ */
+ Titer operator++(int)
+ {
+ Titer ret(static_cast<Titer &>(*this));
+ this->current = this->base[this->current].next_edge;
+ return ret;
+ }
+
+ /**
+ * Compare with some other edge iterator. The other one may be of a
+ * child class.
+ * @tparam Tother Class of other iterator.
+ * @param other Instance of other iterator.
+ * @return If the iterators have the same edge array and current node.
+ */
+ template<class Tother>
+ bool operator==(const Tother &other)
+ {
+ return this->base == other.base && this->current == other.current;
+ }
+
+ /**
+ * Compare for inequality with some other edge iterator. The other one
+ * may be of a child class.
+ * @tparam Tother Class of other iterator.
+ * @param other Instance of other iterator.
+ * @return If either the edge arrays or the current nodes differ.
+ */
+ template<class Tother>
+ bool operator!=(const Tother &other)
+ {
+ return this->base != other.base || this->current != other.current;
+ }
+
+ /**
+ * Dereference with operator*.
+ * @return Pair of current target NodeID and edge object.
+ */
+ SmallPair<NodeID, Tedge_wrapper> operator*() const
+ {
+ return SmallPair<NodeID, Tedge_wrapper>(this->current, Tedge_wrapper(this->base[this->current]));
+ }
+
+ /**
+ * Dereference with operator->.
+ * @return Fake pointer to Pair of current target NodeID and edge object.
+ */
+ FakePointer operator->() const {
+ return FakePointer(this->operator*());
+ }
+ };
+
+ /**
+ * A constant edge class.
+ */
+ typedef EdgeWrapper<const BaseEdge> ConstEdge;
+
+ /**
+ * An updatable edge class.
+ */
+ class Edge : public EdgeWrapper<BaseEdge> {
+ public:
+ /**
+ * Constructor
+ * @param edge Edge to be wrapped.
+ */
+ Edge(BaseEdge &edge) : EdgeWrapper<BaseEdge>(edge) {}
+ void Update(uint capacity, uint usage);
+ };
+
+ /**
+ * An iterator for const edges. Cannot be typedef'ed because of
+ * template-reference to ConstEdgeIterator itself.
+ */
+ class ConstEdgeIterator : public BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator> {
+ public:
+ /**
+ * Constructor.
+ * @param edges Array of edges to be iterated over.
+ * @param current ID of current edge's end node.
+ */
+ ConstEdgeIterator(const BaseEdge *edges, NodeID current) :
+ BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator>(edges, current) {}
+ };
+
+ /**
+ * An iterator for non-const edges. Cannot be typedef'ed because of
+ * template-reference to EdgeIterator itself.
+ */
+ class EdgeIterator : public BaseEdgeIterator<BaseEdge, Edge, EdgeIterator> {
+ public:
+ /**
+ * Constructor.
+ * @param edges Array of edges to be iterated over.
+ * @param current ID of current edge's end node.
+ */
+ EdgeIterator(BaseEdge *edges, NodeID current) :
+ BaseEdgeIterator<BaseEdge, Edge, EdgeIterator>(edges, current) {}
+ };
+
+ /**
+ * Constant node class. Only retrieval operations are allowed on both the
+ * node itself and its edges.
+ */
+ class ConstNode : public NodeWrapper<const BaseNode, const BaseEdge> {
+ public:
+ /**
+ * Constructor.
+ * @param lg LinkGraph to get the node from.
+ * @param node ID of the node.
+ */
+ ConstNode(const LinkGraph *lg, NodeID node) :
+ NodeWrapper<const BaseNode, const BaseEdge>(lg->nodes[node], lg->edges[node], node)
+ {}
+
+ /**
+ * Get a ConstEdge. This is not a reference as the wrapper objects are
+ * not actually persistent.
+ * @param to ID of end node of edge.
+ * @return Constant edge wrapper.
+ */
+ ConstEdge operator[](NodeID to) const { return ConstEdge(this->edges[to]); }
+
+ /**
+ * Get an iterator pointing to the start of the edges array.
+ * @return Constant edge iterator.
+ */
+ ConstEdgeIterator Begin() const { return ConstEdgeIterator(this->edges, this->index); }
+
+ /**
+ * Get an iterator pointing beyond the end of the edges array.
+ * @return Constant edge iterator.
+ */
+ ConstEdgeIterator End() const { return ConstEdgeIterator(this->edges, INVALID_NODE); }
+ };
+
+ /**
+ * Updatable node class. The node itself as well as its edges can be modified.
+ */
+ class Node : public NodeWrapper<BaseNode, BaseEdge> {
+ public:
+ /**
+ * Constructor.
+ * @param lg LinkGraph to get the node from.
+ * @param node ID of the node.
+ */
+ Node(LinkGraph *lg, NodeID node) :
+ NodeWrapper<BaseNode, BaseEdge>(lg->nodes[node], lg->edges[node], node)
+ {}
+
+ /**
+ * Get an Edge. This is not a reference as the wrapper objects are not
+ * actually persistent.
+ * @param to ID of end node of edge.
+ * @return Edge wrapper.
+ */
+ Edge operator[](NodeID to) { return Edge(this->edges[to]); }
+
+ /**
+ * Get an iterator pointing to the start of the edges array.
+ * @return Edge iterator.
+ */
+ EdgeIterator Begin() { return EdgeIterator(this->edges, this->index); }
+
+ /**
+ * Get an iterator pointing beyond the end of the edges array.
+ * @return Constant edge iterator.
+ */
+ EdgeIterator End() { return EdgeIterator(this->edges, INVALID_NODE); }
+
+ /**
+ * Update the node's supply and set last_update to the current date.
+ * @param supply Supply to be added.
+ */
+ void UpdateSupply(uint supply)
+ {
+ this->node.supply += supply;
+ this->node.last_update = _date;
+ }
+
+ /**
+ * Set the node's demand.
+ * @param demand New demand for the node.
+ */
+ void SetDemand(uint demand)
+ {
+ this->node.demand = demand;
+ }
+
+ void AddEdge(NodeID to, uint capacity, uint usage = 0);
+ void UpdateEdge(NodeID to, uint capacity, uint usage = 0);
+ void RemoveEdge(NodeID to);
+ };
+
+ typedef SmallVector<BaseNode, 16> NodeVector;
+ typedef SmallMatrix<BaseEdge> EdgeMatrix;
+
+ /** Minimum effective distance for timeout calculation. */
+ static const uint MIN_TIMEOUT_DISTANCE = 48;
+
+ /** Minimum number of days between subsequent compressions of a LG. */
+ static const uint COMPRESSION_INTERVAL = 256;
+
+ /**
+ * Scale a value from a link graph of age orig_age for usage in one of age
+ * target_age. Make sure that the value stays > 0 if it was > 0 before.
+ * @param val Value to be scaled.
+ * @param target_age Age of the target link graph.
+ * @param orig_age Age of the original link graph.
+ * @return scaled value.
+ */
+ inline static uint Scale(uint val, uint target_age, uint orig_age)
+ {
+ return val > 0 ? max(1U, val * target_age / orig_age) : 0;
+ }
+
+ /** Bare constructor, only for save/load. */
+ LinkGraph() : cargo(INVALID_CARGO), last_compression(0) {}
+ /**
+ * Real constructor.
+ * @param cargo Cargo the link graph is about.
+ */
+ LinkGraph(CargoID cargo) : cargo(cargo), last_compression(_date) {}
+
+ void Init(uint size);
+ void Compress();
+ void Merge(LinkGraph *other);
+
+ /* Splitting link graphs is intentionally not implemented.
+ * The overhead in determining connectedness would probably outweigh the
+ * benefit of having to deal with smaller graphs. In real world examples
+ * networks generally grow. Only rarely a network is permanently split.
+ * Reacting to temporary splits here would obviously create performance
+ * problems and detecting the temporary or permanent nature of splits isn't
+ * trivial. */
+
+ /**
+ * Get a node with the specified id.
+ * @param num ID of the node.
+ * @return the Requested node.
+ */
+ inline Node operator[](NodeID num) { return Node(this, num); }
+
+ /**
+ * Get a const reference to a node with the specified id.
+ * @param num ID of the node.
+ * @return the Requested node.
+ */
+ inline ConstNode operator[](NodeID num) const { return ConstNode(this, num); }
+
+ /**
+ * Get the current size of the component.
+ * @return Size.
+ */
+ inline uint Size() const { return this->nodes.Length(); }
+
+ /**
+ * Get date of last compression.
+ * @return Date of last compression.
+ */
+ inline Date LastCompression() const { return this->last_compression; }
+
+ /**
+ * Get the cargo ID this component's link graph refers to.
+ * @return Cargo ID.
+ */
+ inline CargoID Cargo() const { return this->cargo; }
+
+ /**
+ * Scale a value to its monthly equivalent, based on last compression.
+ * @param base Value to be scaled.
+ * @return Scaled value.
+ */
+ inline uint Monthly(uint base) const
+ {
+ return base * 30 / (_date - this->last_compression + 1);
+ }
+
+ NodeID AddNode(const Station *st);
+ void RemoveNode(NodeID id);
+
+protected:
+ friend class LinkGraph::ConstNode;
+ friend class LinkGraph::Node;
+ friend const SaveLoad *GetLinkGraphDesc();
+ friend const SaveLoad *GetLinkGraphJobDesc();
+ friend void SaveLoad_LinkGraph(LinkGraph &lg);
+
+ CargoID cargo; ///< Cargo of this component's link graph.
+ Date last_compression; ///< Last time the capacities and supplies were compressed.
+ NodeVector nodes; ///< Nodes in the component.
+ EdgeMatrix edges; ///< Edges in the component.
+};
+
+#define FOR_ALL_LINK_GRAPHS(var) FOR_ALL_ITEMS_FROM(LinkGraph, link_graph_index, var, 0)
+
+#endif /* LINKGRAPH_H */
diff --git a/src/linkgraph/linkgraph_base.h b/src/linkgraph/linkgraph_base.h
new file mode 100644
index 000000000..1878b1368
--- /dev/null
+++ b/src/linkgraph/linkgraph_base.h
@@ -0,0 +1,26 @@
+/* $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_base.h Some typedefs for the main game. */
+
+#ifndef LINKGRAPH_BASE_H
+#define LINKGRAPH_BASE_H
+
+#include "linkgraph.h"
+
+typedef LinkGraph::Node Node;
+typedef LinkGraph::Edge Edge;
+typedef LinkGraph::EdgeIterator EdgeIterator;
+
+typedef LinkGraph::ConstNode ConstNode;
+typedef LinkGraph::ConstEdge ConstEdge;
+typedef LinkGraph::ConstEdgeIterator ConstEdgeIterator;
+
+
+#endif /* LINKGRAPH_BASE_H */
diff --git a/src/linkgraph/linkgraph_type.h b/src/linkgraph/linkgraph_type.h
new file mode 100644
index 000000000..13411a707
--- /dev/null
+++ b/src/linkgraph/linkgraph_type.h
@@ -0,0 +1,24 @@
+/* $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_type.h Declaration of link graph types used for cargo distribution. */
+
+#ifndef LINKGRAPH_TYPE_H
+#define LINKGRAPH_TYPE_H
+
+typedef uint16 LinkGraphID;
+static const LinkGraphID INVALID_LINK_GRAPH = UINT16_MAX;
+
+typedef uint16 LinkGraphJobID;
+static const LinkGraphID INVALID_LIN_KGRAPH_JOB = UINT16_MAX;
+
+typedef uint16 NodeID;
+static const NodeID INVALID_NODE = UINT16_MAX;
+
+#endif /* LINKGRAPH_TYPE_H */
diff --git a/src/station_base.h b/src/station_base.h
index 322a7dc8e..7a3d3a885 100644
--- a/src/station_base.h
+++ b/src/station_base.h
@@ -16,6 +16,7 @@
#include "newgrf_airport.h"
#include "cargopacket.h"
#include "industry_type.h"
+#include "linkgraph/linkgraph_type.h"
#include "newgrf_storage.h"
typedef Pool<BaseStation, StationID, 32, 64000> StationPool;
@@ -74,7 +75,9 @@ struct GoodsEntry {
time_since_pickup(255),
rating(INITIAL_STATION_RATING),
last_speed(0),
- last_age(255)
+ last_age(255),
+ link_graph(INVALID_LINK_GRAPH),
+ node(INVALID_NODE)
{}
byte acceptance_pickup; ///< Status of this cargo, see #GoodsEntryStatus.
@@ -108,6 +111,9 @@ struct GoodsEntry {
byte amount_fract; ///< Fractional part of the amount in the cargo list
StationCargoList cargo; ///< The cargo packets of cargo waiting in this station
+ LinkGraphID link_graph; ///< Link graph this station belongs to.
+ NodeID node; ///< ID of node in link graph referring to this goods entry.
+
/**
* Reports whether a vehicle has ever tried to load the cargo at this station.
* This does not imply that there was cargo available for loading. Refer to GES_PICKUP for that.
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-23 07:30:01 +0000