linkgraph.h

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * 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.
 * 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.
 * 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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */

 
#ifndef LINKGRAPH_H
#define LINKGRAPH_H
 
#include "../core/pool_type.hpp"
#include "../station_base.h"
#include "../cargotype.h"
#include "../timer/timer_game_economy.h"
#include "../saveload/saveload_type.h"
#include "linkgraph_type.h"
#include <utility>
 
class LinkGraph;

using LinkGraphPool = Pool<LinkGraph, LinkGraphID, 32>;
extern LinkGraphPool _link_graph_pool;

class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
public:
  struct BaseEdge {
    uint capacity = 0; 
    uint usage = 0; 
    uint64_t travel_time_sum = 0; 
    TimerGameEconomy::Date last_unrestricted_update{}; 
    TimerGameEconomy::Date last_restricted_update{}; 
    NodeID dest_node = INVALID_NODE; 
 
    BaseEdge(NodeID dest_node = INVALID_NODE);

    uint32_t TravelTime() const { return this->travel_time_sum / this->capacity; }

    TimerGameEconomy::Date LastUpdate() const { return std::max(this->last_unrestricted_update, this->last_restricted_update); }
 
    void Update(uint capacity, uint usage, uint32_t time, EdgeUpdateModes modes);
    void Restrict() { this->last_unrestricted_update = EconomyTime::INVALID_DATE; }
    void Release() { this->last_restricted_update = EconomyTime::INVALID_DATE; }

    bool operator <(const BaseEdge &rhs) const
    {
      return this->dest_node < rhs.dest_node;
    }
 
    bool operator <(NodeID rhs) const
    {
      return this->dest_node < rhs;
    }
 
    friend inline bool operator <(NodeID lhs, const LinkGraph::BaseEdge &rhs)
    {
      return lhs < rhs.dest_node;
    }
  };

  struct BaseNode {
    uint supply = 0; 
    uint demand = 0; 
    StationID station = StationID::Invalid(); 
    TileIndex xy = INVALID_TILE; 
    TimerGameEconomy::Date last_update{}; 
 
    std::vector<BaseEdge> edges; 
 
    BaseNode(TileIndex xy = INVALID_TILE, StationID st = StationID::Invalid(), uint demand = 0);

    void UpdateSupply(uint supply)
    {
      this->supply += supply;
      this->last_update = TimerGameEconomy::date;
    }

    void UpdateLocation(TileIndex xy)
    {
      this->xy = xy;
    }

    void SetDemand(uint demand)
    {
      this->demand = demand;
    }
 
    void AddEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateModes modes);
    void UpdateEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateModes modes);
    void RemoveEdge(NodeID to);

    bool HasEdgeTo(NodeID dest) const
    {
      return std::binary_search(this->edges.begin(), this->edges.end(), dest);
    }
 
    BaseEdge &operator[](NodeID to)
    {
      assert(this->HasEdgeTo(to));
      return *GetEdge(to);
    }
 
    const BaseEdge &operator[](NodeID to) const
    {
      assert(this->HasEdgeTo(to));
      return *GetEdge(to);
    }
 
  private:
    std::vector<BaseEdge>::iterator GetEdge(NodeID dest)
    {
      return std::lower_bound(this->edges.begin(), this->edges.end(), dest);
    }
 
    std::vector<BaseEdge>::const_iterator GetEdge(NodeID dest) const
    {
      return std::lower_bound(this->edges.begin(), this->edges.end(), dest);
    }
  };
 
  typedef std::vector<BaseNode> NodeVector;

  static const uint MIN_TIMEOUT_DISTANCE = 32;

  static constexpr TimerGameEconomy::Date STALE_LINK_DEPOT_TIMEOUT{1024};

  static constexpr TimerGameEconomy::Date COMPRESSION_INTERVAL{256};

  static inline uint Scale(uint val, TimerGameEconomy::Date target_age, TimerGameEconomy::Date orig_age)
  {
    return val > 0 ? std::max(1U, val * target_age.base() / orig_age.base()) : 0;
  }

  LinkGraph(LinkGraphID index, CargoType cargo = INVALID_CARGO) :
    LinkGraphPool::PoolItem<&_link_graph_pool>(index), cargo(cargo), last_compression(TimerGameEconomy::date) {}
 
  void Init(uint size);
  void ShiftDates(TimerGameEconomy::Date interval);
  void Compress();
  void Merge(LinkGraph *other);
 
  /* Splitting link graphs is intentionally not implemented.
   * The overhead in determining connectedness would probably outweigh the
   * benefit of having to deal with smaller graphs. In real world examples
   * networks generally grow. Only rarely a network is permanently split.
   * Reacting to temporary splits here would obviously create performance
   * problems and detecting the temporary or permanent nature of splits isn't
   * trivial. */

  inline BaseNode &operator[](NodeID num) { return this->nodes[num]; }

  inline const BaseNode &operator[](NodeID num) const { return this->nodes[num]; }

  inline NodeID Size() const { return (NodeID)this->nodes.size(); }

  inline TimerGameEconomy::Date LastCompression() const { return this->last_compression; }

  inline CargoType Cargo() const { return this->cargo; }

  inline uint Monthly(uint base) const
  {
    return base * 30 / (TimerGameEconomy::date - this->last_compression + 1).base();
  }
 
  NodeID AddNode(const Station *st);
  void RemoveNode(NodeID id);
 
protected:
  friend SaveLoadTable GetLinkGraphDesc();
  friend SaveLoadTable GetLinkGraphJobDesc();
  friend class SlLinkgraphNode;
  friend class SlLinkgraphEdge;
  friend class LinkGraphJob;
 
  CargoType cargo = INVALID_CARGO; 
  TimerGameEconomy::Date last_compression{}; 
  NodeVector nodes{}; 
};
 
#endif /* LINKGRAPH_H */