src/linkgraph/refresh.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 refresh.h Declaration of link refreshing utility. */
   9
  10 #ifndef REFRESH_H
  11 #define REFRESH_H
  12
  13 #include "../cargo_type.h"
  14 #include "../vehicle_base.h"
  15
  16 /**
  17  * Utility to refresh links a consist will visit.
  18  */
  19 class LinkRefresher {
  20 public:
  21         static void Run(Vehicle *v, bool allow_merge = true, bool is_full_loading = false);
  22
  23 protected:
  24         /**
  25          * Various flags about properties of the last examined link that might have
  26          * an influence on the next one.
  27          */
  28         enum RefreshFlags {
  29                 USE_NEXT,     ///< There was a conditional jump. Try to use the given next order when looking for a new one.
  30                 HAS_CARGO,    ///< Consist could leave the last stop where it could interact with cargo carrying cargo (i.e. not an "unload all" + "no loading" order).
  31                 WAS_REFIT,    ///< Consist was refit since the last stop where it could interact with cargo.
  32                 RESET_REFIT,  ///< Consist had a chance to load since the last refit and the refit capacities can be reset.
  33                 IN_AUTOREFIT, ///< Currently doing an autorefit loop. Ignore the first autorefit order.
  34         };
  35
  36         /**
  37          * Simulated cargo type and capacity for prediction of future links.
  38          */
  39         struct RefitDesc {
  40                 CargoID cargo;    ///< Cargo type the vehicle will be carrying.
  41                 uint16_t capacity;  ///< Capacity the vehicle will have.
  42                 uint16_t remaining; ///< Capacity remaining from before the previous refit.
  43                 RefitDesc(CargoID cargo, uint16_t capacity, uint16_t remaining) :
  44                                 cargo(cargo), capacity(capacity), remaining(remaining) {}
  45         };
  46
  47         /**
  48          * A hop the refresh algorithm might evaluate. If the same hop is seen again
  49          * the evaluation is stopped. This of course is a fairly simple heuristic.
  50          * Sequences of refit orders can produce vehicles with all kinds of
  51          * different cargoes and remembering only one can lead to early termination
  52          * of the algorithm. However, as the order language is Turing complete, we
  53          * are facing the halting problem here. At some point we have to draw the
  54          * line.
  55          */
  56         struct Hop {
  57                 OrderID from;  ///< Last order where vehicle could interact with cargo or absolute first order.
  58                 OrderID to;    ///< Next order to be processed.
  59                 CargoID cargo; ///< Cargo the consist is probably carrying or INVALID_CARGO if unknown.
  60
  61                 /**
  62                  * Default constructor should not be called but has to be visible for
  63                  * usage in std::set.
  64                  */
  65                 Hop() {NOT_REACHED();}
  66
  67                 /**
  68                  * Real constructor, only use this one.
  69                  * @param from First order of the hop.
  70                  * @param to Second order of the hop.
  71                  * @param cargo Cargo the consist is probably carrying when passing the hop.
  72                  */
  73                 Hop(OrderID from, OrderID to, CargoID cargo) : from(from), to(to), cargo(cargo) {}
  74                 bool operator<(const Hop &other) const;
  75         };
  76
  77         typedef std::vector<RefitDesc> RefitList;
  78         typedef std::set<Hop> HopSet;
  79
  80         Vehicle *vehicle;           ///< Vehicle for which the links should be refreshed.
  81         uint capacities[NUM_CARGO]; ///< Current added capacities per cargo ID in the consist.
  82         RefitList refit_capacities; ///< Current state of capacity remaining from previous refits versus overall capacity per vehicle in the consist.
  83         HopSet *seen_hops;          ///< Hops already seen. If the same hop is seen twice we stop the algorithm. This is shared between all Refreshers of the same run.
  84         CargoID cargo;              ///< Cargo given in last refit order.
  85         bool allow_merge;           ///< If the refresher is allowed to merge or extend link graphs.
  86         bool is_full_loading;       ///< If the vehicle is full loading.
  87
  88         LinkRefresher(Vehicle *v, HopSet *seen_hops, bool allow_merge, bool is_full_loading);
  89
  90         bool HandleRefit(CargoID refit_cargo);
  91         void ResetRefit();
  92         void RefreshStats(const Order *cur, const Order *next);
  93         const Order *PredictNextOrder(const Order *cur, const Order *next, uint8_t flags, uint num_hops = 0);
  94
  95         void RefreshLinks(const Order *cur, const Order *next, uint8_t flags, uint num_hops = 0);
  96 };
  97
  98 #endif /* REFRESH_H */