|
|
/*
|
|
|
* 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/>.
|
|
|
*/
|
|
|
|
|
|
/** @file linkgraph.h Declaration of link graph classes used for cargo distribution. */
|
|
|
|
|
|
#ifndef LINKGRAPH_H
|
|
|
#define LINKGRAPH_H
|
|
|
|
|
|
#include "../core/pool_type.hpp"
|
|
|
#include "../core/smallmap_type.hpp"
|
|
|
#include "../station_base.h"
|
|
|
#include "../cargotype.h"
|
|
|
#include "../date_func.h"
|
|
|
#include "../timer/timer_game_calendar.h"
|
|
|
#include "../saveload/saveload.h"
|
|
|
#include "linkgraph_type.h"
|
|
|
#include <utility>
|
|
|
|
|
|
class LinkGraph;
|
|
|
|
|
|
/**
|
|
|
* Type of the pool for link graph components. Each station can be in at up to
|
|
|
* 32 link graphs. So we allow for plenty of them to be created.
|
|
|
*/
|
|
|
typedef Pool<LinkGraph, LinkGraphID, 32, 0xFFFF> LinkGraphPool;
|
|
|
/** The actual pool with link graphs. */
|
|
|
extern LinkGraphPool _link_graph_pool;
|
|
|
|
|
|
/**
|
|
|
* A connected component of a link graph. Contains a complete set of stations
|
|
|
* connected by links as nodes and edges. Each component also holds a copy of
|
|
|
* the link graph settings at the time of its creation. The global settings
|
|
|
* might change between the creation and join time so we can't rely on them.
|
|
|
*/
|
|
|
class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
|
|
|
public:
|
|
|
/**
|
|
|
* An edge in the link graph. Corresponds to a link between two stations.
|
|
@@ -85,49 +85,49 @@ public:
|
|
|
|
|
|
/**
|
|
|
* Node of the link graph. contains all relevant information from the associated
|
|
|
* station. It's copied so that the link graph job can work on its own data set
|
|
|
* in a separate thread.
|
|
|
*/
|
|
|
struct BaseNode {
|
|
|
uint supply; ///< Supply at the station.
|
|
|
uint demand; ///< Acceptance at the station.
|
|
|
StationID station; ///< Station ID.
|
|
|
TileIndex xy; ///< Location of the station referred to by the node.
|
|
|
Date last_update; ///< When the supply was last updated.
|
|
|
|
|
|
std::vector<BaseEdge> edges; ///< Sorted list of outgoing edges from this node.
|
|
|
|
|
|
BaseNode(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0);
|
|
|
|
|
|
/**
|
|
|
* Update the node's supply and set last_update to the current date.
|
|
|
* @param supply Supply to be added.
|
|
|
*/
|
|
|
void UpdateSupply(uint supply)
|
|
|
{
|
|
|
this->supply += supply;
|
|
|
this->last_update = _date;
|
|
|
this->last_update = TimerGameCalendar::date;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Update the node's location on the map.
|
|
|
* @param xy New location.
|
|
|
*/
|
|
|
void UpdateLocation(TileIndex xy)
|
|
|
{
|
|
|
this->xy = xy;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Set the node's demand.
|
|
|
* @param demand New demand for the node.
|
|
|
*/
|
|
|
void SetDemand(uint demand)
|
|
|
{
|
|
|
this->demand = demand;
|
|
|
}
|
|
|
|
|
|
void AddEdge(NodeID to, uint capacity, uint usage, uint32 time, EdgeUpdateMode mode);
|
|
|
void UpdateEdge(NodeID to, uint capacity, uint usage, uint32 time, EdgeUpdateMode mode);
|
|
|
void RemoveEdge(NodeID to);
|
|
|
|
|
@@ -174,49 +174,49 @@ public:
|
|
|
static const uint STALE_LINK_DEPOT_TIMEOUT = 1024;
|
|
|
|
|
|
/** Minimum number of days between subsequent compressions of a LG. */
|
|
|
static const uint COMPRESSION_INTERVAL = 256;
|
|
|
|
|
|
/**
|
|
|
* Scale a value from a link graph of age orig_age for usage in one of age
|
|
|
* target_age. Make sure that the value stays > 0 if it was > 0 before.
|
|
|
* @param val Value to be scaled.
|
|
|
* @param target_age Age of the target link graph.
|
|
|
* @param orig_age Age of the original link graph.
|
|
|
* @return scaled value.
|
|
|
*/
|
|
|
inline static uint Scale(uint val, uint target_age, uint orig_age)
|
|
|
{
|
|
|
return val > 0 ? std::max(1U, val * target_age / orig_age) : 0;
|
|
|
}
|
|
|
|
|
|
/** Bare constructor, only for save/load. */
|
|
|
LinkGraph() : cargo(INVALID_CARGO), last_compression(0) {}
|
|
|
/**
|
|
|
* Real constructor.
|
|
|
* @param cargo Cargo the link graph is about.
|
|
|
*/
|
|
|
LinkGraph(CargoID cargo) : cargo(cargo), last_compression(_date) {}
|
|
|
LinkGraph(CargoID cargo) : cargo(cargo), last_compression(TimerGameCalendar::date) {}
|
|
|
|
|
|
void Init(uint size);
|
|
|
void ShiftDates(int 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. */
|
|
|
|
|
|
/**
|
|
|
* Get a node with the specified id.
|
|
|
* @param num ID of the node.
|
|
|
* @return the Requested node.
|
|
|
*/
|
|
|
inline BaseNode &operator[](NodeID num) { return this->nodes[num]; }
|
|
|
|
|
|
/**
|
|
|
* Get a const reference to a node with the specified id.
|
|
|
* @param num ID of the node.
|
|
@@ -228,43 +228,43 @@ public:
|
|
|
* Get the current size of the component.
|
|
|
* @return Size.
|
|
|
*/
|
|
|
inline NodeID Size() const { return (NodeID)this->nodes.size(); }
|
|
|
|
|
|
/**
|
|
|
* Get date of last compression.
|
|
|
* @return Date of last compression.
|
|
|
*/
|
|
|
inline Date LastCompression() const { return this->last_compression; }
|
|
|
|
|
|
/**
|
|
|
* Get the cargo ID this component's link graph refers to.
|
|
|
* @return Cargo ID.
|
|
|
*/
|
|
|
inline CargoID Cargo() const { return this->cargo; }
|
|
|
|
|
|
/**
|
|
|
* Scale a value to its monthly equivalent, based on last compression.
|
|
|
* @param base Value to be scaled.
|
|
|
* @return Scaled value.
|
|
|
*/
|
|
|
inline uint Monthly(uint base) const
|
|
|
{
|
|
|
return base * 30 / (_date - this->last_compression + 1);
|
|
|
return base * 30 / (TimerGameCalendar::date - this->last_compression + 1);
|
|
|
}
|
|
|
|
|
|
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; ///< Cargo of this component's link graph.
|
|
|
Date last_compression; ///< Last time the capacities and supplies were compressed.
|
|
|
NodeVector nodes; ///< Nodes in the component.
|
|
|
};
|
|
|
|
|
|
#endif /* LINKGRAPH_H */
|