src/linkgraph/linkgraph.h

   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
   8 /** @file linkgraph.h Declaration of link graph classes used for cargo distribution. */
   9
  10 #ifndef LINKGRAPH_H
  11 #define LINKGRAPH_H
  12
  13 #include "../core/pool_type.hpp"
  14 #include "../station_base.h"
  15 #include "../cargotype.h"
  16 #include "../timer/timer_game_economy.h"
  17 #include "../saveload/saveload.h"
  18 #include "linkgraph_type.h"
  19 #include <utility>
  20
  21 class LinkGraph;
  22
  23 /**
  24  * Type of the pool for link graph components. Each station can be in at up to
  25  * 32 link graphs. So we allow for plenty of them to be created.
  26  */
  27 typedef Pool<LinkGraph, LinkGraphID, 32, 0xFFFF> LinkGraphPool;
  28 /** The actual pool with link graphs. */
  29 extern LinkGraphPool _link_graph_pool;
  30
  31 /**
  32  * A connected component of a link graph. Contains a complete set of stations
  33  * connected by links as nodes and edges. Each component also holds a copy of
  34  * the link graph settings at the time of its creation. The global settings
  35  * might change between the creation and join time so we can't rely on them.
  36  */
  37 class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
  38 public:
  39         /**
  40          * An edge in the link graph. Corresponds to a link between two stations.
  41          */
  42         struct BaseEdge {
  43                 uint capacity;                 ///< Capacity of the link.
  44                 uint usage;                    ///< Usage of the link.
  45                 uint64_t travel_time_sum;        ///< Sum of the travel times of the link, in ticks.
  46                 TimerGameEconomy::Date last_unrestricted_update; ///< When the unrestricted part of the link was last updated.
  47                 TimerGameEconomy::Date last_restricted_update;   ///< When the restricted part of the link was last updated.
  48                 NodeID dest_node;              ///< Destination of the edge.
  49
  50                 BaseEdge(NodeID dest_node = INVALID_NODE);
  51
  52                 /**
  53                  * Get edge's average travel time.
  54                  * @return Travel time, in ticks.
  55                  */
  56                 uint32_t TravelTime() const { return this->travel_time_sum / this->capacity; }
  57
  58                 /**
  59                  * Get the date of the last update to any part of the edge's capacity.
  60                  * @return Last update.
  61                  */
  62                 TimerGameEconomy::Date LastUpdate() const { return std::max(this->last_unrestricted_update, this->last_restricted_update); }
  63
  64                 void Update(uint capacity, uint usage, uint32_t time, EdgeUpdateMode mode);
  65                 void Restrict() { this->last_unrestricted_update = EconomyTime::INVALID_DATE; }
  66                 void Release() { this->last_restricted_update = EconomyTime::INVALID_DATE; }
  67
  68                 /** Comparison operator based on \c dest_node. */
  69                 bool operator <(const BaseEdge &rhs) const
  70                 {
  71                         return this->dest_node < rhs.dest_node;
  72                 }
  73
  74                 bool operator <(NodeID rhs) const
  75                 {
  76                         return this->dest_node < rhs;
  77                 }
  78
  79                 friend inline bool operator <(NodeID lhs, const LinkGraph::BaseEdge &rhs)
  80                 {
  81                         return lhs < rhs.dest_node;
  82                 }
  83         };
  84
  85         /**
  86          * Node of the link graph. contains all relevant information from the associated
  87          * station. It's copied so that the link graph job can work on its own data set
  88          * in a separate thread.
  89          */
  90         struct BaseNode {
  91                 uint supply;             ///< Supply at the station.
  92                 uint demand;             ///< Acceptance at the station.
  93                 StationID station;       ///< Station ID.
  94                 TileIndex xy;            ///< Location of the station referred to by the node.
  95                 TimerGameEconomy::Date last_update;        ///< When the supply was last updated.
  96
  97                 std::vector<BaseEdge> edges; ///< Sorted list of outgoing edges from this node.
  98
  99                 BaseNode(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0);
 100
 101                 /**
 102                  * Update the node's supply and set last_update to the current date.
 103                  * @param supply Supply to be added.
 104                  */
 105                 void UpdateSupply(uint supply)
 106                 {
 107                         this->supply += supply;
 108                         this->last_update = TimerGameEconomy::date;
 109                 }
 110
 111                 /**
 112                  * Update the node's location on the map.
 113                  * @param xy New location.
 114                  */
 115                 void UpdateLocation(TileIndex xy)
 116                 {
 117                         this->xy = xy;
 118                 }
 119
 120                 /**
 121                  * Set the node's demand.
 122                  * @param demand New demand for the node.
 123                  */
 124                 void SetDemand(uint demand)
 125                 {
 126                         this->demand = demand;
 127                 }
 128
 129                 void AddEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateMode mode);
 130                 void UpdateEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateMode mode);
 131                 void RemoveEdge(NodeID to);
 132
 133                 /**
 134                  * Check if an edge to a destination is present.
 135                  * @param dest Wanted edge destination.
 136                  * @return True if an edge is present.
 137                  */
 138                 bool HasEdgeTo(NodeID dest) const
 139                 {
 140                         return std::binary_search(this->edges.begin(), this->edges.end(), dest);
 141                 }
 142
 143                 BaseEdge &operator[](NodeID to)
 144                 {
 145                         assert(this->HasEdgeTo(to));
 146                         return *GetEdge(to);
 147                 }
 148
 149                 const BaseEdge &operator[](NodeID to) const
 150                 {
 151                         assert(this->HasEdgeTo(to));
 152                         return *GetEdge(to);
 153                 }
 154
 155         private:
 156                 std::vector<BaseEdge>::iterator GetEdge(NodeID dest)
 157                 {
 158                         return std::lower_bound(this->edges.begin(), this->edges.end(), dest);
 159                 }
 160
 161                 std::vector<BaseEdge>::const_iterator GetEdge(NodeID dest) const
 162                 {
 163                         return std::lower_bound(this->edges.begin(), this->edges.end(), dest);
 164                 }
 165         };
 166
 167         typedef std::vector<BaseNode> NodeVector;
 168
 169         /** Minimum effective distance for timeout calculation. */
 170         static const uint MIN_TIMEOUT_DISTANCE = 32;
 171
 172         /** Number of days before deleting links served only by vehicles stopped in depot. */
 173         static constexpr TimerGameEconomy::Date STALE_LINK_DEPOT_TIMEOUT = 1024;
 174
 175         /** Minimum number of days between subsequent compressions of a LG. */
 176         static constexpr TimerGameEconomy::Date COMPRESSION_INTERVAL = 256;
 177
 178         /**
 179          * Scale a value from a link graph of age orig_age for usage in one of age
 180          * target_age. Make sure that the value stays > 0 if it was > 0 before.
 181          * @param val Value to be scaled.
 182          * @param target_age Age of the target link graph.
 183          * @param orig_age Age of the original link graph.
 184          * @return scaled value.
 185          */
 186         inline static uint Scale(uint val, TimerGameEconomy::Date target_age, TimerGameEconomy::Date orig_age)
 187         {
 188                 return val > 0 ? std::max(1U, val * target_age.base() / orig_age.base()) : 0;
 189         }
 190
 191         /** Bare constructor, only for save/load. */
 192         LinkGraph() : cargo(INVALID_CARGO), last_compression(0) {}
 193         /**
 194          * Real constructor.
 195          * @param cargo Cargo the link graph is about.
 196          */
 197         LinkGraph(CargoID cargo) : cargo(cargo), last_compression(TimerGameEconomy::date) {}
 198
 199         void Init(uint size);
 200         void ShiftDates(TimerGameEconomy::Date interval);
 201         void Compress();
 202         void Merge(LinkGraph *other);
 203
 204         /* Splitting link graphs is intentionally not implemented.
 205          * The overhead in determining connectedness would probably outweigh the
 206          * benefit of having to deal with smaller graphs. In real world examples
 207          * networks generally grow. Only rarely a network is permanently split.
 208          * Reacting to temporary splits here would obviously create performance
 209          * problems and detecting the temporary or permanent nature of splits isn't
 210          * trivial. */
 211
 212         /**
 213          * Get a node with the specified id.
 214          * @param num ID of the node.
 215          * @return the Requested node.
 216          */
 217         inline BaseNode &operator[](NodeID num) { return this->nodes[num]; }
 218
 219         /**
 220          * Get a const reference to a node with the specified id.
 221          * @param num ID of the node.
 222          * @return the Requested node.
 223          */
 224         inline const BaseNode &operator[](NodeID num) const { return this->nodes[num]; }
 225
 226         /**
 227          * Get the current size of the component.
 228          * @return Size.
 229          */
 230         inline NodeID Size() const { return (NodeID)this->nodes.size(); }
 231
 232         /**
 233          * Get date of last compression.
 234          * @return Date of last compression.
 235          */
 236         inline TimerGameEconomy::Date LastCompression() const { return this->last_compression; }
 237
 238         /**
 239          * Get the cargo ID this component's link graph refers to.
 240          * @return Cargo ID.
 241          */
 242         inline CargoID Cargo() const { return this->cargo; }
 243
 244         /**
 245          * Scale a value to its monthly equivalent, based on last compression.
 246          * @param base Value to be scaled.
 247          * @return Scaled value.
 248          */
 249         inline uint Monthly(uint base) const
 250         {
 251                 return base * 30 / (TimerGameEconomy::date - this->last_compression + 1).base();
 252         }
 253
 254         NodeID AddNode(const Station *st);
 255         void RemoveNode(NodeID id);
 256
 257 protected:
 258         friend SaveLoadTable GetLinkGraphDesc();
 259         friend SaveLoadTable GetLinkGraphJobDesc();
 260         friend class SlLinkgraphNode;
 261         friend class SlLinkgraphEdge;
 262         friend class LinkGraphJob;
 263
 264         CargoID cargo;         ///< Cargo of this component's link graph.
 265         TimerGameEconomy::Date last_compression; ///< Last time the capacities and supplies were compressed.
 266         NodeVector nodes;      ///< Nodes in the component.
 267 };
 268
 269 #endif /* LINKGRAPH_H */