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 <http://www.gnu.org/licenses/>.
 */
 
#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.h"
#include "linkgraph_type.h"
#include <utility>
 
class LinkGraph;
 
typedef Pool<LinkGraph, LinkGraphID, 32, 0xFFFF> LinkGraphPool;
extern LinkGraphPool _link_graph_pool;
 
class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
public:
  struct BaseEdge {
    uint capacity;                 
    uint usage;                    
    uint64_t travel_time_sum;        
    TimerGameEconomy::Date last_unrestricted_update; 
    TimerGameEconomy::Date last_restricted_update;   
    NodeID dest_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, EdgeUpdateMode mode);
    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;             
    uint demand;             
    StationID station;       
    TileIndex xy;            
    TimerGameEconomy::Date last_update;        
 
    std::vector<BaseEdge> edges; 
 
    BaseNode(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, 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, EdgeUpdateMode mode);
    void UpdateEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateMode mode);
    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;
 
  inline static 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() : cargo(INVALID_CARGO), last_compression(0) {}
  LinkGraph(CargoID cargo) : 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 CargoID 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;
 
  CargoID cargo;         
  TimerGameEconomy::Date last_compression; 
  NodeVector nodes;      
};
 
#endif /* LINKGRAPH_H */