OpenTTD
linkgraph.h
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * 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.
4  * 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.
5  * 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/>.
6  */
7 
10 #ifndef LINKGRAPH_H
11 #define LINKGRAPH_H
12 
13 #include "../core/pool_type.hpp"
14 #include "../core/smallmap_type.hpp"
15 #include "../core/smallmatrix_type.hpp"
16 #include "../station_base.h"
17 #include "../cargotype.h"
18 #include "../date_func.h"
19 #include "linkgraph_type.h"
20 
21 struct SaveLoad;
22 class LinkGraph;
23 
31 
38 class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
39 public:
40 
46  struct BaseNode {
47  uint supply;
48  uint demand;
49  StationID station;
52  void Init(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0);
53  };
54 
61  struct BaseEdge {
62  uint capacity;
63  uint usage;
66  NodeID next_edge;
67  void Init();
68  };
69 
74  template<typename Tedge>
75  class EdgeWrapper {
76  protected:
77  Tedge &edge;
78 
79  public:
80 
85  EdgeWrapper (Tedge &edge) : edge(edge) {}
86 
91  uint Capacity() const { return this->edge.capacity; }
92 
97  uint Usage() const { return this->edge.usage; }
98 
103  Date LastUnrestrictedUpdate() const { return this->edge.last_unrestricted_update; }
104 
109  Date LastRestrictedUpdate() const { return this->edge.last_restricted_update; }
110 
115  Date LastUpdate() const { return max(this->edge.last_unrestricted_update, this->edge.last_restricted_update); }
116  };
117 
123  template<typename Tnode, typename Tedge>
124  class NodeWrapper {
125  protected:
126  Tnode &node;
127  Tedge *edges;
128  NodeID index;
129 
130  public:
131 
138  NodeWrapper(Tnode &node, Tedge *edges, NodeID index) : node(node),
139  edges(edges), index(index) {}
140 
145  uint Supply() const { return this->node.supply; }
146 
151  uint Demand() const { return this->node.demand; }
152 
157  StationID Station() const { return this->node.station; }
158 
163  Date LastUpdate() const { return this->node.last_update; }
164 
169  TileIndex XY() const { return this->node.xy; }
170  };
171 
179  template <class Tedge, class Tedge_wrapper, class Titer>
181  protected:
182  Tedge *base;
183  NodeID current;
184 
191  class FakePointer : public SmallPair<NodeID, Tedge_wrapper> {
192  public:
193 
198  FakePointer(const SmallPair<NodeID, Tedge_wrapper> &pair) : SmallPair<NodeID, Tedge_wrapper>(pair) {}
199 
205  };
206 
207  public:
213  BaseEdgeIterator (Tedge *base, NodeID current) :
214  base(base),
215  current(current == INVALID_NODE ? current : base[current].next_edge)
216  {}
217 
222  Titer &operator++()
223  {
224  this->current = this->base[this->current].next_edge;
225  return static_cast<Titer &>(*this);
226  }
227 
232  Titer operator++(int)
233  {
234  Titer ret(static_cast<Titer &>(*this));
235  this->current = this->base[this->current].next_edge;
236  return ret;
237  }
238 
246  template<class Tother>
247  bool operator==(const Tother &other)
248  {
249  return this->base == other.base && this->current == other.current;
250  }
251 
259  template<class Tother>
260  bool operator!=(const Tother &other)
261  {
262  return this->base != other.base || this->current != other.current;
263  }
264 
270  {
271  return SmallPair<NodeID, Tedge_wrapper>(this->current, Tedge_wrapper(this->base[this->current]));
272  }
273 
278  FakePointer operator->() const {
279  return FakePointer(this->operator*());
280  }
281  };
282 
287 
291  class Edge : public EdgeWrapper<BaseEdge> {
292  public:
297  Edge(BaseEdge &edge) : EdgeWrapper<BaseEdge>(edge) {}
298  void Update(uint capacity, uint usage, EdgeUpdateMode mode);
299  void Restrict() { this->edge.last_unrestricted_update = INVALID_DATE; }
300  void Release() { this->edge.last_restricted_update = INVALID_DATE; }
301  };
302 
307  class ConstEdgeIterator : public BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator> {
308  public:
314  ConstEdgeIterator(const BaseEdge *edges, NodeID current) :
315  BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator>(edges, current) {}
316  };
317 
322  class EdgeIterator : public BaseEdgeIterator<BaseEdge, Edge, EdgeIterator> {
323  public:
329  EdgeIterator(BaseEdge *edges, NodeID current) :
330  BaseEdgeIterator<BaseEdge, Edge, EdgeIterator>(edges, current) {}
331  };
332 
337  class ConstNode : public NodeWrapper<const BaseNode, const BaseEdge> {
338  public:
344  ConstNode(const LinkGraph *lg, NodeID node) :
345  NodeWrapper<const BaseNode, const BaseEdge>(lg->nodes[node], lg->edges[node], node)
346  {}
347 
354  ConstEdge operator[](NodeID to) const { return ConstEdge(this->edges[to]); }
355 
360  ConstEdgeIterator Begin() const { return ConstEdgeIterator(this->edges, this->index); }
361 
366  ConstEdgeIterator End() const { return ConstEdgeIterator(this->edges, INVALID_NODE); }
367  };
368 
372  class Node : public NodeWrapper<BaseNode, BaseEdge> {
373  public:
379  Node(LinkGraph *lg, NodeID node) :
380  NodeWrapper<BaseNode, BaseEdge>(lg->nodes[node], lg->edges[node], node)
381  {}
382 
389  Edge operator[](NodeID to) { return Edge(this->edges[to]); }
390 
395  EdgeIterator Begin() { return EdgeIterator(this->edges, this->index); }
396 
401  EdgeIterator End() { return EdgeIterator(this->edges, INVALID_NODE); }
402 
407  void UpdateSupply(uint supply)
408  {
409  this->node.supply += supply;
410  this->node.last_update = _date;
411  }
412 
418  {
419  this->node.xy = xy;
420  }
421 
426  void SetDemand(uint demand)
427  {
428  this->node.demand = demand;
429  }
430 
431  void AddEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode);
432  void UpdateEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode);
433  void RemoveEdge(NodeID to);
434  };
435 
436  typedef std::vector<BaseNode> NodeVector;
438 
440  static const uint MIN_TIMEOUT_DISTANCE = 32;
441 
443  static const uint COMPRESSION_INTERVAL = 256;
444 
453  inline static uint Scale(uint val, uint target_age, uint orig_age)
454  {
455  return val > 0 ? max(1U, val * target_age / orig_age) : 0;
456  }
457 
465 
466  void Init(uint size);
467  void ShiftDates(int interval);
468  void Compress();
469  void Merge(LinkGraph *other);
470 
471  /* Splitting link graphs is intentionally not implemented.
472  * The overhead in determining connectedness would probably outweigh the
473  * benefit of having to deal with smaller graphs. In real world examples
474  * networks generally grow. Only rarely a network is permanently split.
475  * Reacting to temporary splits here would obviously create performance
476  * problems and detecting the temporary or permanent nature of splits isn't
477  * trivial. */
478 
484  inline Node operator[](NodeID num) { return Node(this, num); }
485 
491  inline ConstNode operator[](NodeID num) const { return ConstNode(this, num); }
492 
497  inline uint Size() const { return (uint)this->nodes.size(); }
498 
503  inline Date LastCompression() const { return this->last_compression; }
504 
509  inline CargoID Cargo() const { return this->cargo; }
510 
516  inline uint Monthly(uint base) const
517  {
518  return base * 30 / (_date - this->last_compression + 1);
519  }
520 
521  NodeID AddNode(const Station *st);
522  void RemoveNode(NodeID id);
523 
524 protected:
525  friend class LinkGraph::ConstNode;
526  friend class LinkGraph::Node;
527  friend const SaveLoad *GetLinkGraphDesc();
528  friend const SaveLoad *GetLinkGraphJobDesc();
529  friend void SaveLoad_LinkGraph(LinkGraph &lg);
530 
533  NodeVector nodes;
534  EdgeMatrix edges;
535 };
536 
537 #endif /* LINKGRAPH_H */
Constant node class.
Definition: linkgraph.h:337
ConstNode operator[](NodeID num) const
Get a const reference to a node with the specified id.
Definition: linkgraph.h:491
uint Demand() const
Get demand of wrapped node.
Definition: linkgraph.h:151
TileIndex xy
Location of the station referred to by the node.
Definition: linkgraph.h:50
void Init(TileIndex xy=INVALID_TILE, StationID st=INVALID_STATION, uint demand=0)
Create a node or clear it.
Definition: linkgraph.cpp:26
EdgeIterator Begin()
Get an iterator pointing to the start of the edges array.
Definition: linkgraph.h:395
SmallPair< NodeID, Tedge_wrapper > operator*() const
Dereference with operator*.
Definition: linkgraph.h:269
NodeID AddNode(const Station *st)
Add a node to the component and create empty edges associated with it.
Definition: linkgraph.cpp:158
static const uint COMPRESSION_INTERVAL
Minimum number of days between subsequent compressions of a LG.
Definition: linkgraph.h:443
NodeID index
ID of wrapped node.
Definition: linkgraph.h:128
Pool< LinkGraph, LinkGraphID, 32, 0xFFFF > LinkGraphPool
Type of the pool for link graph components.
Definition: linkgraph.h:22
An edge in the link graph.
Definition: linkgraph.h:61
Date LastUnrestrictedUpdate() const
Get the date of the last update to the edge&#39;s unrestricted capacity.
Definition: linkgraph.h:103
BaseEdgeIterator(Tedge *base, NodeID current)
Constructor.
Definition: linkgraph.h:213
Titer & operator++()
Prefix-increment.
Definition: linkgraph.h:222
Edge operator[](NodeID to)
Get an Edge.
Definition: linkgraph.h:389
Date LastUpdate() const
Get node&#39;s last update.
Definition: linkgraph.h:163
uint Supply() const
Get supply of wrapped node.
Definition: linkgraph.h:145
CargoID Cargo() const
Get the cargo ID this component&#39;s link graph refers to.
Definition: linkgraph.h:509
Tnode & node
Node being wrapped.
Definition: linkgraph.h:126
uint demand
Acceptance at the station.
Definition: linkgraph.h:48
uint Usage() const
Get edge&#39;s usage.
Definition: linkgraph.h:97
uint supply
Supply at the station.
Definition: linkgraph.h:47
friend const SaveLoad * GetLinkGraphJobDesc()
Get a SaveLoad array for a link graph job.
ConstEdgeIterator(const BaseEdge *edges, NodeID current)
Constructor.
Definition: linkgraph.h:314
ConstNode(const LinkGraph *lg, NodeID node)
Constructor.
Definition: linkgraph.h:344
Tindex index
Index of this pool item.
Definition: pool_type.hpp:189
void ShiftDates(int interval)
Shift all dates by given interval.
Definition: linkgraph.cpp:52
LinkGraphPool _link_graph_pool
The actual pool with link graphs.
CargoID cargo
Cargo of this component&#39;s link graph.
Definition: linkgraph.h:531
A "fake" pointer to enable operator-> on temporaries.
Definition: linkgraph.h:191
uint usage
Usage of the link.
Definition: linkgraph.h:63
static T max(const T a, const T b)
Returns the maximum of two values.
Definition: math_func.hpp:24
StationID Station() const
Get ID of station belonging to wrapped node.
Definition: linkgraph.h:157
EdgeWrapper(Tedge &edge)
Wrap a an edge.
Definition: linkgraph.h:85
Edge(BaseEdge &edge)
Constructor.
Definition: linkgraph.h:297
A connected component of a link graph.
Definition: linkgraph.h:38
NodeID next_edge
Destination of next valid edge starting at the same source node.
Definition: linkgraph.h:66
Date last_update
When the supply was last updated.
Definition: linkgraph.h:51
static uint Scale(uint val, uint target_age, uint orig_age)
Scale a value from a link graph of age orig_age for usage in one of age target_age.
Definition: linkgraph.h:453
SmallPair< NodeID, Tedge_wrapper > * operator->()
Retrieve the pair by operator->.
Definition: linkgraph.h:204
uint Size() const
Get the current size of the component.
Definition: linkgraph.h:497
EdgeIterator End()
Get an iterator pointing beyond the end of the edges array.
Definition: linkgraph.h:401
Updatable node class.
Definition: linkgraph.h:372
Simple pair of data.
void UpdateSupply(uint supply)
Update the node&#39;s supply and set last_update to the current date.
Definition: linkgraph.h:407
LinkGraph()
Bare constructor, only for save/load.
Definition: linkgraph.h:459
EdgeWrapper< const BaseEdge > ConstEdge
A constant edge class.
Definition: linkgraph.h:286
void SetDemand(uint demand)
Set the node&#39;s demand.
Definition: linkgraph.h:426
static const Date INVALID_DATE
Representation of an invalid date.
Definition: date_type.h:108
uint Monthly(uint base) const
Scale a value to its monthly equivalent, based on last compression.
Definition: linkgraph.h:516
static const uint MIN_TIMEOUT_DISTANCE
Minimum effective distance for timeout calculation.
Definition: linkgraph.h:440
Tedge & edge
Actual edge to be used.
Definition: linkgraph.h:77
ConstEdge operator[](NodeID to) const
Get a ConstEdge.
Definition: linkgraph.h:354
friend const SaveLoad * GetLinkGraphDesc()
Get a SaveLoad array for a link graph.
EdgeMatrix edges
Edges in the component.
Definition: linkgraph.h:534
Date last_restricted_update
When the restricted part of the link was last updated.
Definition: linkgraph.h:65
Date LastRestrictedUpdate() const
Get the date of the last update to the edge&#39;s restricted capacity.
Definition: linkgraph.h:109
An iterator for const edges.
Definition: linkgraph.h:307
Declaration of link graph types used for cargo distribution.
An updatable edge class.
Definition: linkgraph.h:291
Wrapper for an edge (const or not) allowing retrieval, but no modification.
Definition: linkgraph.h:75
Date LastCompression() const
Get date of last compression.
Definition: linkgraph.h:503
Base class for all PoolItems.
Definition: pool_type.hpp:188
EdgeIterator(BaseEdge *edges, NodeID current)
Constructor.
Definition: linkgraph.h:329
Base class for iterating across outgoing edges of a node.
Definition: linkgraph.h:180
Date LastUpdate() const
Get the date of the last update to any part of the edge&#39;s capacity.
Definition: linkgraph.h:115
void RemoveNode(NodeID id)
Remove a node from the link graph by overwriting it with the last node.
Definition: linkgraph.cpp:119
TileIndex XY() const
Get the location of the station associated with the node.
Definition: linkgraph.h:169
Base class for all pools.
Definition: pool_type.hpp:82
void UpdateLocation(TileIndex xy)
Update the node&#39;s location on the map.
Definition: linkgraph.h:417
EdgeUpdateMode
Special modes for updating links.
uint capacity
Capacity of the link.
Definition: linkgraph.h:62
FakePointer(const SmallPair< NodeID, Tedge_wrapper > &pair)
Construct a fake pointer from a pair of NodeID and edge.
Definition: linkgraph.h:198
friend void SaveLoad_LinkGraph(LinkGraph &lg)
Save/load a link graph.
Titer operator++(int)
Postfix-increment.
Definition: linkgraph.h:232
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:78
bool operator==(const Tother &other)
Compare with some other edge iterator.
Definition: linkgraph.h:247
Node of the link graph.
Definition: linkgraph.h:46
LinkGraph(CargoID cargo)
Real constructor.
Definition: linkgraph.h:464
static const byte INVALID_CARGO
Constant representing invalid cargo.
Definition: cargotype.h:52
ConstEdgeIterator End() const
Get an iterator pointing beyond the end of the edges array.
Definition: linkgraph.h:366
Date last_compression
Last time the capacities and supplies were compressed.
Definition: linkgraph.h:532
bool operator!=(const Tother &other)
Compare for inequality with some other edge iterator.
Definition: linkgraph.h:260
int32 Date
The type to store our dates in.
Definition: date_type.h:14
SaveLoad type struct.
Definition: saveload.h:496
Tedge * edges
Outgoing edges for wrapped node.
Definition: linkgraph.h:127
static const TileIndex INVALID_TILE
The very nice invalid tile marker.
Definition: tile_type.h:83
StationID station
Station ID.
Definition: linkgraph.h:49
byte CargoID
Cargo slots to indicate a cargo type within a game.
Definition: cargo_type.h:20
An iterator for non-const edges.
Definition: linkgraph.h:322
NodeID current
Current offset in edges array.
Definition: linkgraph.h:183
Node operator[](NodeID num)
Get a node with the specified id.
Definition: linkgraph.h:484
ConstEdgeIterator Begin() const
Get an iterator pointing to the start of the edges array.
Definition: linkgraph.h:360
FakePointer operator->() const
Dereference with operator->.
Definition: linkgraph.h:278
NodeVector nodes
Nodes in the component.
Definition: linkgraph.h:533
uint Capacity() const
Get edge&#39;s capacity.
Definition: linkgraph.h:91
NodeWrapper(Tnode &node, Tedge *edges, NodeID index)
Wrap a node.
Definition: linkgraph.h:138
Date _date
Current date in days (day counter)
Definition: date.cpp:26
void Merge(LinkGraph *other)
Merge a link graph with another one.
Definition: linkgraph.cpp:85
Station data structure.
Definition: station_base.h:450
Wrapper for a node (const or not) allowing retrieval, but no modification.
Definition: linkgraph.h:124
Node(LinkGraph *lg, NodeID node)
Constructor.
Definition: linkgraph.h:379
Date last_unrestricted_update
When the unrestricted part of the link was last updated.
Definition: linkgraph.h:64
Tedge * base
Array of edges being iterated.
Definition: linkgraph.h:182