OpenTTD
linkgraph.h
Go to the documentation of this file.
1 /* $Id: linkgraph.h 26646 2014-06-14 13:35:39Z fonsinchen $ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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/>.
8  */
9 
12 #ifndef LINKGRAPH_H
13 #define LINKGRAPH_H
14 
15 #include "../core/pool_type.hpp"
16 #include "../core/smallmap_type.hpp"
17 #include "../core/smallmatrix_type.hpp"
18 #include "../station_base.h"
19 #include "../cargotype.h"
20 #include "../date_func.h"
21 #include "linkgraph_type.h"
22 
23 struct SaveLoad;
24 class LinkGraph;
25 
33 
40 class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
41 public:
42 
48  struct BaseNode {
49  uint supply;
50  uint demand;
51  StationID station;
54  void Init(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0);
55  };
56 
63  struct BaseEdge {
64  uint capacity;
65  uint usage;
68  NodeID next_edge;
69  void Init();
70  };
71 
76  template<typename Tedge>
77  class EdgeWrapper {
78  protected:
79  Tedge &edge;
80 
81  public:
82 
87  EdgeWrapper (Tedge &edge) : edge(edge) {}
88 
93  uint Capacity() const { return this->edge.capacity; }
94 
99  uint Usage() const { return this->edge.usage; }
100 
105  Date LastUnrestrictedUpdate() const { return this->edge.last_unrestricted_update; }
106 
111  Date LastRestrictedUpdate() const { return this->edge.last_restricted_update; }
112 
117  Date LastUpdate() const { return max(this->edge.last_unrestricted_update, this->edge.last_restricted_update); }
118  };
119 
125  template<typename Tnode, typename Tedge>
126  class NodeWrapper {
127  protected:
128  Tnode &node;
129  Tedge *edges;
130  NodeID index;
131 
132  public:
133 
140  NodeWrapper(Tnode &node, Tedge *edges, NodeID index) : node(node),
141  edges(edges), index(index) {}
142 
147  uint Supply() const { return this->node.supply; }
148 
153  uint Demand() const { return this->node.demand; }
154 
159  StationID Station() const { return this->node.station; }
160 
165  Date LastUpdate() const { return this->node.last_update; }
166 
171  TileIndex XY() const { return this->node.xy; }
172  };
173 
181  template <class Tedge, class Tedge_wrapper, class Titer>
183  protected:
184  Tedge *base;
185  NodeID current;
186 
193  class FakePointer : public SmallPair<NodeID, Tedge_wrapper> {
194  public:
195 
200  FakePointer(const SmallPair<NodeID, Tedge_wrapper> &pair) : SmallPair<NodeID, Tedge_wrapper>(pair) {}
201 
207  };
208 
209  public:
215  BaseEdgeIterator (Tedge *base, NodeID current) :
216  base(base),
217  current(current == INVALID_NODE ? current : base[current].next_edge)
218  {}
219 
224  Titer &operator++()
225  {
226  this->current = this->base[this->current].next_edge;
227  return static_cast<Titer &>(*this);
228  }
229 
234  Titer operator++(int)
235  {
236  Titer ret(static_cast<Titer &>(*this));
237  this->current = this->base[this->current].next_edge;
238  return ret;
239  }
240 
248  template<class Tother>
249  bool operator==(const Tother &other)
250  {
251  return this->base == other.base && this->current == other.current;
252  }
253 
261  template<class Tother>
262  bool operator!=(const Tother &other)
263  {
264  return this->base != other.base || this->current != other.current;
265  }
266 
272  {
273  return SmallPair<NodeID, Tedge_wrapper>(this->current, Tedge_wrapper(this->base[this->current]));
274  }
275 
280  FakePointer operator->() const {
281  return FakePointer(this->operator*());
282  }
283  };
284 
289 
293  class Edge : public EdgeWrapper<BaseEdge> {
294  public:
299  Edge(BaseEdge &edge) : EdgeWrapper<BaseEdge>(edge) {}
300  void Update(uint capacity, uint usage, EdgeUpdateMode mode);
301  void Restrict() { this->edge.last_unrestricted_update = INVALID_DATE; }
302  void Release() { this->edge.last_restricted_update = INVALID_DATE; }
303  };
304 
309  class ConstEdgeIterator : public BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator> {
310  public:
316  ConstEdgeIterator(const BaseEdge *edges, NodeID current) :
317  BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator>(edges, current) {}
318  };
319 
324  class EdgeIterator : public BaseEdgeIterator<BaseEdge, Edge, EdgeIterator> {
325  public:
331  EdgeIterator(BaseEdge *edges, NodeID current) :
332  BaseEdgeIterator<BaseEdge, Edge, EdgeIterator>(edges, current) {}
333  };
334 
339  class ConstNode : public NodeWrapper<const BaseNode, const BaseEdge> {
340  public:
346  ConstNode(const LinkGraph *lg, NodeID node) :
347  NodeWrapper<const BaseNode, const BaseEdge>(lg->nodes[node], lg->edges[node], node)
348  {}
349 
356  ConstEdge operator[](NodeID to) const { return ConstEdge(this->edges[to]); }
357 
362  ConstEdgeIterator Begin() const { return ConstEdgeIterator(this->edges, this->index); }
363 
368  ConstEdgeIterator End() const { return ConstEdgeIterator(this->edges, INVALID_NODE); }
369  };
370 
374  class Node : public NodeWrapper<BaseNode, BaseEdge> {
375  public:
381  Node(LinkGraph *lg, NodeID node) :
382  NodeWrapper<BaseNode, BaseEdge>(lg->nodes[node], lg->edges[node], node)
383  {}
384 
391  Edge operator[](NodeID to) { return Edge(this->edges[to]); }
392 
397  EdgeIterator Begin() { return EdgeIterator(this->edges, this->index); }
398 
403  EdgeIterator End() { return EdgeIterator(this->edges, INVALID_NODE); }
404 
409  void UpdateSupply(uint supply)
410  {
411  this->node.supply += supply;
412  this->node.last_update = _date;
413  }
414 
420  {
421  this->node.xy = xy;
422  }
423 
428  void SetDemand(uint demand)
429  {
430  this->node.demand = demand;
431  }
432 
433  void AddEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode);
434  void UpdateEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode);
435  void RemoveEdge(NodeID to);
436  };
437 
440 
442  static const uint MIN_TIMEOUT_DISTANCE = 32;
443 
445  static const uint COMPRESSION_INTERVAL = 256;
446 
455  inline static uint Scale(uint val, uint target_age, uint orig_age)
456  {
457  return val > 0 ? max(1U, val * target_age / orig_age) : 0;
458  }
459 
467 
468  void Init(uint size);
469  void ShiftDates(int interval);
470  void Compress();
471  void Merge(LinkGraph *other);
472 
473  /* Splitting link graphs is intentionally not implemented.
474  * The overhead in determining connectedness would probably outweigh the
475  * benefit of having to deal with smaller graphs. In real world examples
476  * networks generally grow. Only rarely a network is permanently split.
477  * Reacting to temporary splits here would obviously create performance
478  * problems and detecting the temporary or permanent nature of splits isn't
479  * trivial. */
480 
486  inline Node operator[](NodeID num) { return Node(this, num); }
487 
493  inline ConstNode operator[](NodeID num) const { return ConstNode(this, num); }
494 
499  inline uint Size() const { return this->nodes.Length(); }
500 
505  inline Date LastCompression() const { return this->last_compression; }
506 
511  inline CargoID Cargo() const { return this->cargo; }
512 
518  inline uint Monthly(uint base) const
519  {
520  return base * 30 / (_date - this->last_compression + 1);
521  }
522 
523  NodeID AddNode(const Station *st);
524  void RemoveNode(NodeID id);
525 
526 protected:
527  friend class LinkGraph::ConstNode;
528  friend class LinkGraph::Node;
529  friend const SaveLoad *GetLinkGraphDesc();
530  friend const SaveLoad *GetLinkGraphJobDesc();
531  friend void SaveLoad_LinkGraph(LinkGraph &lg);
532 
535  NodeVector nodes;
536  EdgeMatrix edges;
537 };
538 
539 #define FOR_ALL_LINK_GRAPHS(var) FOR_ALL_ITEMS_FROM(LinkGraph, link_graph_index, var, 0)
540 
541 #endif /* LINKGRAPH_H */
Constant node class.
Definition: linkgraph.h:339
ConstNode operator[](NodeID num) const
Get a const reference to a node with the specified id.
Definition: linkgraph.h:493
uint Demand() const
Get demand of wrapped node.
Definition: linkgraph.h:153
TileIndex xy
Location of the station referred to by the node.
Definition: linkgraph.h:52
void Init(TileIndex xy=INVALID_TILE, StationID st=INVALID_STATION, uint demand=0)
Create a node or clear it.
Definition: linkgraph.cpp:28
EdgeIterator Begin()
Get an iterator pointing to the start of the edges array.
Definition: linkgraph.h:397
SmallPair< NodeID, Tedge_wrapper > operator*() const
Dereference with operator*.
Definition: linkgraph.h:271
NodeID AddNode(const Station *st)
Add a node to the component and create empty edges associated with it.
Definition: linkgraph.cpp:157
static const uint COMPRESSION_INTERVAL
Minimum number of days between subsequent compressions of a LG.
Definition: linkgraph.h:445
NodeID index
ID of wrapped node.
Definition: linkgraph.h:130
Pool< LinkGraph, LinkGraphID, 32, 0xFFFF > LinkGraphPool
Type of the pool for link graph components.
Definition: linkgraph.h:24
An edge in the link graph.
Definition: linkgraph.h:63
Date LastUnrestrictedUpdate() const
Get the date of the last update to the edge&#39;s unrestricted capacity.
Definition: linkgraph.h:105
BaseEdgeIterator(Tedge *base, NodeID current)
Constructor.
Definition: linkgraph.h:215
Titer & operator++()
Prefix-increment.
Definition: linkgraph.h:224
Edge operator[](NodeID to)
Get an Edge.
Definition: linkgraph.h:391
Date LastUpdate() const
Get node&#39;s last update.
Definition: linkgraph.h:165
uint Supply() const
Get supply of wrapped node.
Definition: linkgraph.h:147
CargoID Cargo() const
Get the cargo ID this component&#39;s link graph refers to.
Definition: linkgraph.h:511
Tnode & node
Node being wrapped.
Definition: linkgraph.h:128
uint demand
Acceptance at the station.
Definition: linkgraph.h:50
uint Usage() const
Get edge&#39;s usage.
Definition: linkgraph.h:99
uint supply
Supply at the station.
Definition: linkgraph.h:49
friend const SaveLoad * GetLinkGraphJobDesc()
Get a SaveLoad array for a link graph job.
ConstEdgeIterator(const BaseEdge *edges, NodeID current)
Constructor.
Definition: linkgraph.h:316
ConstNode(const LinkGraph *lg, NodeID node)
Constructor.
Definition: linkgraph.h:346
Tindex index
Index of this pool item.
Definition: pool_type.hpp:147
void ShiftDates(int interval)
Shift all dates by given interval.
Definition: linkgraph.cpp:54
LinkGraphPool _link_graph_pool
The actual pool with link graphs.
CargoID cargo
Cargo of this component&#39;s link graph.
Definition: linkgraph.h:533
A "fake" pointer to enable operator-> on temporaries.
Definition: linkgraph.h:193
uint usage
Usage of the link.
Definition: linkgraph.h:65
static T max(const T a, const T b)
Returns the maximum of two values.
Definition: math_func.hpp:26
StationID Station() const
Get ID of station belonging to wrapped node.
Definition: linkgraph.h:159
EdgeWrapper(Tedge &edge)
Wrap a an edge.
Definition: linkgraph.h:87
Edge(BaseEdge &edge)
Constructor.
Definition: linkgraph.h:299
A connected component of a link graph.
Definition: linkgraph.h:40
NodeID next_edge
Destination of next valid edge starting at the same source node.
Definition: linkgraph.h:68
Date last_update
When the supply was last updated.
Definition: linkgraph.h:53
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:455
SmallPair< NodeID, Tedge_wrapper > * operator->()
Retrieve the pair by operator->.
Definition: linkgraph.h:206
uint Size() const
Get the current size of the component.
Definition: linkgraph.h:499
EdgeIterator End()
Get an iterator pointing beyond the end of the edges array.
Definition: linkgraph.h:403
Updatable node class.
Definition: linkgraph.h:374
uint Length() const
Get the number of items in the list.
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:409
LinkGraph()
Bare constructor, only for save/load.
Definition: linkgraph.h:461
EdgeWrapper< const BaseEdge > ConstEdge
A constant edge class.
Definition: linkgraph.h:288
void SetDemand(uint demand)
Set the node&#39;s demand.
Definition: linkgraph.h:428
static const Date INVALID_DATE
Representation of an invalid date.
Definition: date_type.h:110
uint Monthly(uint base) const
Scale a value to its monthly equivalent, based on last compression.
Definition: linkgraph.h:518
static const uint MIN_TIMEOUT_DISTANCE
Minimum effective distance for timeout calculation.
Definition: linkgraph.h:442
Tedge & edge
Actual edge to be used.
Definition: linkgraph.h:79
ConstEdge operator[](NodeID to) const
Get a ConstEdge.
Definition: linkgraph.h:356
friend const SaveLoad * GetLinkGraphDesc()
Get a SaveLoad array for a link graph.
EdgeMatrix edges
Edges in the component.
Definition: linkgraph.h:536
Date last_restricted_update
When the restricted part of the link was last updated.
Definition: linkgraph.h:67
Date LastRestrictedUpdate() const
Get the date of the last update to the edge&#39;s restricted capacity.
Definition: linkgraph.h:111
An iterator for const edges.
Definition: linkgraph.h:309
Declaration of link graph types used for cargo distribution.
An updatable edge class.
Definition: linkgraph.h:293
Wrapper for an edge (const or not) allowing retrieval, but no modification.
Definition: linkgraph.h:77
Date LastCompression() const
Get date of last compression.
Definition: linkgraph.h:505
Base class for all PoolItems.
Definition: pool_type.hpp:146
EdgeIterator(BaseEdge *edges, NodeID current)
Constructor.
Definition: linkgraph.h:331
Base class for iterating across outgoing edges of a node.
Definition: linkgraph.h:182
Date LastUpdate() const
Get the date of the last update to any part of the edge&#39;s capacity.
Definition: linkgraph.h:117
void RemoveNode(NodeID id)
Remove a node from the link graph by overwriting it with the last node.
Definition: linkgraph.cpp:121
TileIndex XY() const
Get the location of the station associated with the node.
Definition: linkgraph.h:171
Base class for all pools.
Definition: pool_type.hpp:83
void UpdateLocation(TileIndex xy)
Update the node&#39;s location on the map.
Definition: linkgraph.h:419
EdgeUpdateMode
Special modes for updating links.
uint capacity
Capacity of the link.
Definition: linkgraph.h:64
FakePointer(const SmallPair< NodeID, Tedge_wrapper > &pair)
Construct a fake pointer from a pair of NodeID and edge.
Definition: linkgraph.h:200
friend void SaveLoad_LinkGraph(LinkGraph &lg)
Save/load a link graph.
Titer operator++(int)
Postfix-increment.
Definition: linkgraph.h:234
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:80
bool operator==(const Tother &other)
Compare with some other edge iterator.
Definition: linkgraph.h:249
Node of the link graph.
Definition: linkgraph.h:48
LinkGraph(CargoID cargo)
Real constructor.
Definition: linkgraph.h:466
static const byte INVALID_CARGO
Constant representing invalid cargo.
Definition: cargotype.h:53
ConstEdgeIterator End() const
Get an iterator pointing beyond the end of the edges array.
Definition: linkgraph.h:368
Date last_compression
Last time the capacities and supplies were compressed.
Definition: linkgraph.h:534
bool operator!=(const Tother &other)
Compare for inequality with some other edge iterator.
Definition: linkgraph.h:262
int32 Date
The type to store our dates in.
Definition: date_type.h:16
SaveLoad type struct.
Definition: saveload.h:208
Tedge * edges
Outgoing edges for wrapped node.
Definition: linkgraph.h:129
static const TileIndex INVALID_TILE
The very nice invalid tile marker.
Definition: tile_type.h:85
StationID station
Station ID.
Definition: linkgraph.h:51
byte CargoID
Cargo slots to indicate a cargo type within a game.
Definition: cargo_type.h:22
An iterator for non-const edges.
Definition: linkgraph.h:324
NodeID current
Current offset in edges array.
Definition: linkgraph.h:185
Node operator[](NodeID num)
Get a node with the specified id.
Definition: linkgraph.h:486
ConstEdgeIterator Begin() const
Get an iterator pointing to the start of the edges array.
Definition: linkgraph.h:362
FakePointer operator->() const
Dereference with operator->.
Definition: linkgraph.h:280
NodeVector nodes
Nodes in the component.
Definition: linkgraph.h:535
uint Capacity() const
Get edge&#39;s capacity.
Definition: linkgraph.h:93
NodeWrapper(Tnode &node, Tedge *edges, NodeID index)
Wrap a node.
Definition: linkgraph.h:140
Date _date
Current date in days (day counter)
Definition: date.cpp:28
void Merge(LinkGraph *other)
Merge a link graph with another one.
Definition: linkgraph.cpp:87
Station data structure.
Definition: station_base.h:446
Wrapper for a node (const or not) allowing retrieval, but no modification.
Definition: linkgraph.h:126
Node(LinkGraph *lg, NodeID node)
Constructor.
Definition: linkgraph.h:381
Date last_unrestricted_update
When the unrestricted part of the link was last updated.
Definition: linkgraph.h:66
Tedge * base
Array of edges being iterated.
Definition: linkgraph.h:184