src/linkgraph/linkgraphjob.h

   1 /* $Id$ */
   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
  10 /** @file linkgraphjob.h Declaration of link graph job classes used for cargo distribution. */
  11
  12 #ifndef LINKGRAPHJOB_H
  13 #define LINKGRAPHJOB_H
  14
  15 #include "../thread/thread.h"
  16 #include "linkgraph.h"
  17 #include <list>
  18
  19 class LinkGraphJob;
  20 class Path;
  21 typedef std::list<Path *> PathList;
  22
  23 /** Type of the pool for link graph jobs. */
  24 typedef Pool<LinkGraphJob, LinkGraphJobID, 32, 0xFFFF> LinkGraphJobPool;
  25 /** The actual pool with link graph jobs. */
  26 extern LinkGraphJobPool _link_graph_job_pool;
  27
  28 /**
  29  * Class for calculation jobs to be run on link graphs.
  30  */
  31 class LinkGraphJob : public LinkGraphJobPool::PoolItem<&_link_graph_job_pool>{
  32 private:
  33         /**
  34          * Annotation for a link graph edge.
  35          */
  36         struct EdgeAnnotation {
  37                 uint demand;             ///< Transport demand between the nodes.
  38                 uint unsatisfied_demand; ///< Demand over this edge that hasn't been satisfied yet.
  39                 uint flow;               ///< Planned flow over this edge.
  40                 void Init();
  41         };
  42
  43         /**
  44          * Annotation for a link graph node.
  45          */
  46         struct NodeAnnotation {
  47                 uint undelivered_supply; ///< Amount of supply that hasn't been distributed yet.
  48                 PathList paths;          ///< Paths through this node, sorted so that those with flow == 0 are in the back.
  49                 FlowStatMap flows;       ///< Planned flows to other nodes.
  50                 void Init(uint supply);
  51         };
  52
  53         typedef SmallVector<NodeAnnotation, 16> NodeAnnotationVector;
  54         typedef SmallMatrix<EdgeAnnotation> EdgeAnnotationMatrix;
  55
  56         friend const SaveLoad *GetLinkGraphJobDesc();
  57         friend class LinkGraphSchedule;
  58
  59 protected:
  60         const LinkGraph link_graph;       ///< Link graph to by analyzed. Is copied when job is started and mustn't be modified later.
  61         const LinkGraphSettings settings; ///< Copy of _settings_game.linkgraph at spawn time.
  62         ThreadObject *thread;             ///< Thread the job is running in or NULL if it's running in the main thread.
  63         Date join_date;                   ///< Date when the job is to be joined.
  64         NodeAnnotationVector nodes;       ///< Extra node data necessary for link graph calculation.
  65         EdgeAnnotationMatrix edges;       ///< Extra edge data necessary for link graph calculation.
  66
  67         void EraseFlows(NodeID from);
  68         void JoinThread();
  69         void SpawnThread();
  70
  71 public:
  72
  73         /**
  74          * A job edge. Wraps a link graph edge and an edge annotation. The
  75          * annotation can be modified, the edge is constant.
  76          */
  77         class Edge : public LinkGraph::ConstEdge {
  78         private:
  79                 EdgeAnnotation &anno; ///< Annotation being wrapped.
  80         public:
  81                 /**
  82                  * Constructor.
  83                  * @param edge Link graph edge to be wrapped.
  84                  * @param anno Annotation to be wrapped.
  85                  */
  86                 Edge(const LinkGraph::BaseEdge &edge, EdgeAnnotation &anno) :
  87                                 LinkGraph::ConstEdge(edge), anno(anno) {}
  88
  89                 /**
  90                  * Get the transport demand between end the points of the edge.
  91                  * @return Demand.
  92                  */
  93                 uint Demand() const { return this->anno.demand; }
  94
  95                 /**
  96                  * Get the transport demand that hasn't been satisfied by flows, yet.
  97                  * @return Unsatisfied demand.
  98                  */
  99                 uint UnsatisfiedDemand() const { return this->anno.unsatisfied_demand; }
 100
 101                 /**
 102                  * Get the total flow on the edge.
 103                  * @return Flow.
 104                  */
 105                 uint Flow() const { return this->anno.flow; }
 106
 107                 /**
 108                  * Add some flow.
 109                  * @param flow Flow to be added.
 110                  */
 111                 void AddFlow(uint flow) { this->anno.flow += flow; }
 112
 113                 /**
 114                  * Remove some flow.
 115                  * @param flow Flow to be removed.
 116                  */
 117                 void RemoveFlow(uint flow)
 118                 {
 119                         assert(flow <= this->anno.flow);
 120                         this->anno.flow -= flow;
 121                 }
 122
 123                 /**
 124                  * Add some (not yet satisfied) demand.
 125                  * @param demand Demand to be added.
 126                  */
 127                 void AddDemand(uint demand)
 128                 {
 129                         this->anno.demand += demand;
 130                         this->anno.unsatisfied_demand += demand;
 131                 }
 132
 133                 /**
 134                  * Satisfy some demand.
 135                  * @param demand Demand to be satisfied.
 136                  */
 137                 void SatisfyDemand(uint demand)
 138                 {
 139                         assert(demand <= this->anno.unsatisfied_demand);
 140                         this->anno.unsatisfied_demand -= demand;
 141                 }
 142         };
 143
 144         /**
 145          * Iterator for job edges.
 146          */
 147         class EdgeIterator : public LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator> {
 148                 EdgeAnnotation *base_anno; ///< Array of annotations to be (indirectly) iterated.
 149         public:
 150                 /**
 151                  * Constructor.
 152                  * @param base Array of edges to be iterated.
 153                  * @param base_anno Array of annotations to be iterated.
 154                  * @param current Start offset of iteration.
 155                  */
 156                 EdgeIterator(const LinkGraph::BaseEdge *base, EdgeAnnotation *base_anno, NodeID current) :
 157                                 LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(base, current),
 158                                 base_anno(base_anno) {}
 159
 160                 /**
 161                  * Dereference.
 162                  * @return Pair of the edge currently pointed to and the ID of its
 163                  *         other end.
 164                  */
 165                 SmallPair<NodeID, Edge> operator*() const
 166                 {
 167                         return SmallPair<NodeID, Edge>(this->current, Edge(this->base[this->current], this->base_anno[this->current]));
 168                 }
 169
 170                 /**
 171                  * Dereference. Has to be repeated here as operator* is different than
 172                  * in LinkGraph::EdgeWrapper.
 173                  * @return Fake pointer to pair of NodeID/Edge.
 174                  */
 175                 FakePointer operator->() const {
 176                         return FakePointer(this->operator*());
 177                 }
 178         };
 179
 180         /**
 181          * Link graph job node. Wraps a constant link graph node and a modifiable
 182          * node annotation.
 183          */
 184         class Node : public LinkGraph::ConstNode {
 185         private:
 186                 NodeAnnotation &node_anno;  ///< Annotation being wrapped.
 187                 EdgeAnnotation *edge_annos; ///< Edge annotations belonging to this node.
 188         public:
 189
 190                 /**
 191                  * Constructor.
 192                  * @param lgj Job to take the node from.
 193                  * @param node ID of the node.
 194                  */
 195                 Node (LinkGraphJob *lgj, NodeID node) :
 196                         LinkGraph::ConstNode(&lgj->link_graph, node),
 197                         node_anno(lgj->nodes[node]), edge_annos(lgj->edges[node])
 198                 {}
 199
 200                 /**
 201                  * Retrieve an edge starting at this node. Mind that this returns an
 202                  * object, not a reference.
 203                  * @param to Remote end of the edge.
 204                  * @return Edge between this node and "to".
 205                  */
 206                 Edge operator[](NodeID to) const { return Edge(this->edges[to], this->edge_annos[to]); }
 207
 208                 /**
 209                  * Iterator for the "begin" of the edge array. Only edges with capacity
 210                  * are iterated. The others are skipped.
 211                  * @return Iterator pointing to the first edge.
 212                  */
 213                 EdgeIterator Begin() const { return EdgeIterator(this->edges, this->edge_annos, index); }
 214
 215                 /**
 216                  * Iterator for the "end" of the edge array. Only edges with capacity
 217                  * are iterated. The others are skipped.
 218                  * @return Iterator pointing beyond the last edge.
 219                  */
 220                 EdgeIterator End() const { return EdgeIterator(this->edges, this->edge_annos, INVALID_NODE); }
 221
 222                 /**
 223                  * Get amount of supply that hasn't been delivered, yet.
 224                  * @return Undelivered supply.
 225                  */
 226                 uint UndeliveredSupply() const { return this->node_anno.undelivered_supply; }
 227
 228                 /**
 229                  * Get the flows running through this node.
 230                  * @return Flows.
 231                  */
 232                 FlowStatMap &Flows() { return this->node_anno.flows; }
 233
 234                 /**
 235                  * Get a constant version of the flows running through this node.
 236                  * @return Flows.
 237                  */
 238                 const FlowStatMap &Flows() const { return this->node_anno.flows; }
 239
 240                 /**
 241                  * Get the paths this node is part of. Paths are always expected to be
 242                  * sorted so that those with flow == 0 are in the back of the list.
 243                  * @return Paths.
 244                  */
 245                 PathList &Paths() { return this->node_anno.paths; }
 246
 247                 /**
 248                  * Get a constant version of the paths this node is part of.
 249                  * @return Paths.
 250                  */
 251                 const PathList &Paths() const { return this->node_anno.paths; }
 252
 253                 /**
 254                  * Deliver some supply, adding demand to the respective edge.
 255                  * @param to Destination for supply.
 256                  * @param amount Amount of supply to be delivered.
 257                  */
 258                 void DeliverSupply(NodeID to, uint amount)
 259                 {
 260                         this->node_anno.undelivered_supply -= amount;
 261                         (*this)[to].AddDemand(amount);
 262                 }
 263         };
 264
 265         /**
 266          * Bare constructor, only for save/load. link_graph, join_date and actually
 267          * settings have to be brutally const-casted in order to populate them.
 268          */
 269         LinkGraphJob() : settings(_settings_game.linkgraph), thread(NULL),
 270                         join_date(INVALID_DATE) {}
 271
 272         LinkGraphJob(const LinkGraph &orig);
 273         ~LinkGraphJob();
 274
 275         void Init();
 276
 277         /**
 278          * Check if job is supposed to be finished.
 279          * @return True if job should be finished by now, false if not.
 280          */
 281         inline bool IsFinished() const { return this->join_date <= _date; }
 282
 283         /**
 284          * Get the date when the job should be finished.
 285          * @return Join date.
 286          */
 287         inline Date JoinDate() const { return join_date; }
 288
 289         /**
 290          * Change the join date on date cheating.
 291          * @param interval Number of days to add.
 292          */
 293         inline void ShiftJoinDate(int interval) { this->join_date += interval; }
 294
 295         /**
 296          * Get the link graph settings for this component.
 297          * @return Settings.
 298          */
 299         inline const LinkGraphSettings &Settings() const { return this->settings; }
 300
 301         /**
 302          * Get a node abstraction with the specified id.
 303          * @param num ID of the node.
 304          * @return the Requested node.
 305          */
 306         inline Node operator[](NodeID num) { return Node(this, num); }
 307
 308         /**
 309          * Get the size of the underlying link graph.
 310          * @return Size.
 311          */
 312         inline uint Size() const { return this->link_graph.Size(); }
 313
 314         /**
 315          * Get the cargo of the underlying link graph.
 316          * @return Cargo.
 317          */
 318         inline CargoID Cargo() const { return this->link_graph.Cargo(); }
 319
 320         /**
 321          * Get the date when the underlying link graph was last compressed.
 322          * @return Compression date.
 323          */
 324         inline Date LastCompression() const { return this->link_graph.LastCompression(); }
 325
 326         /**
 327          * Get the ID of the underlying link graph.
 328          * @return Link graph ID.
 329          */
 330         inline LinkGraphID LinkGraphIndex() const { return this->link_graph.index; }
 331
 332         /**
 333          * Get a reference to the underlying link graph. Only use this for save/load.
 334          * @return Link graph.
 335          */
 336         inline const LinkGraph &Graph() const { return this->link_graph; }
 337 };
 338
 339 #define FOR_ALL_LINK_GRAPH_JOBS(var) FOR_ALL_ITEMS_FROM(LinkGraphJob, link_graph_job_index, var, 0)
 340
 341 /**
 342  * A leg of a path in the link graph. Paths can form trees by being "forked".
 343  */
 344 class Path {
 345 public:
 346         static Path *invalid_path;
 347
 348         Path(NodeID n, bool source = false);
 349
 350         /** Get the node this leg passes. */
 351         inline NodeID GetNode() const { return this->node; }
 352
 353         /** Get the overall origin of the path. */
 354         inline NodeID GetOrigin() const { return this->origin; }
 355
 356         /** Get the parent leg of this one. */
 357         inline Path *GetParent() { return this->parent; }
 358
 359         /** Get the overall capacity of the path. */
 360         inline uint GetCapacity() const { return this->capacity; }
 361
 362         /** Get the free capacity of the path. */
 363         inline int GetFreeCapacity() const { return this->free_capacity; }
 364
 365         /**
 366          * Get ratio of free * 16 (so that we get fewer 0) /
 367          * max(total capacity, 1) (so that we don't divide by 0).
 368          * @param free Free capacity.
 369          * @param total Total capacity.
 370          * @return free * 16 / max(total, 1).
 371          */
 372         inline static int GetCapacityRatio(int free, uint total)
 373         {
 374                 return Clamp(free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / max(total, 1U);
 375         }
 376
 377         /**
 378          * Get capacity ratio of this path.
 379          * @return free capacity * 16 / (total capacity + 1).
 380          */
 381         inline int GetCapacityRatio() const
 382         {
 383                 return Path::GetCapacityRatio(this->free_capacity, this->capacity);
 384         }
 385
 386         /** Get the overall distance of the path. */
 387         inline uint GetDistance() const { return this->distance; }
 388
 389         /** Reduce the flow on this leg only by the specified amount. */
 390         inline void ReduceFlow(uint f) { this->flow -= f; }
 391
 392         /** Increase the flow on this leg only by the specified amount. */
 393         inline void AddFlow(uint f) { this->flow += f; }
 394
 395         /** Get the flow on this leg. */
 396         inline uint GetFlow() const { return this->flow; }
 397
 398         /** Get the number of "forked off" child legs of this one. */
 399         inline uint GetNumChildren() const { return this->num_children; }
 400
 401         /**
 402          * Detach this path from its parent.
 403          */
 404         inline void Detach()
 405         {
 406                 if (this->parent != NULL) {
 407                         this->parent->num_children--;
 408                         this->parent = NULL;
 409                 }
 410         }
 411
 412         uint AddFlow(uint f, LinkGraphJob &job, uint max_saturation);
 413         void Fork(Path *base, uint cap, int free_cap, uint dist);
 414
 415 protected:
 416
 417         /**
 418          * Some boundaries to clamp agains in order to avoid integer overflows.
 419          */
 420         enum PathCapacityBoundaries {
 421                 PATH_CAP_MULTIPLIER = 16,
 422                 PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER,
 423                 PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER
 424         };
 425
 426         uint distance;     ///< Sum(distance of all legs up to this one).
 427         uint capacity;     ///< This capacity is min(capacity) fom all edges.
 428         int free_capacity; ///< This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
 429         uint flow;         ///< Flow the current run of the mcf solver assigns.
 430         NodeID node;       ///< Link graph node this leg passes.
 431         NodeID origin;     ///< Link graph node this path originates from.
 432         uint num_children; ///< Number of child legs that have been forked from this path.
 433         Path *parent;      ///< Parent leg of this one.
 434 };
 435
 436 #endif /* LINKGRAPHJOB_H */