<ClCompile Include="..\src\linkgraph\linkgraph.cpp" />

    <ClInclude Include="..\src\linkgraph\linkgraph.h" />

    <ClInclude Include="..\src\linkgraph\linkgraph_type.h" />

    <ClCompile Include="..\src\linkgraph\linkgraph.cpp">

      <Filter>Source Files</Filter>

    </ClCompile>

    <ClInclude Include="..\src\linkgraph\linkgraph.h">

      <Filter>Header Files</Filter>

    </ClInclude>

    <ClInclude Include="..\src\linkgraph\linkgraph_type.h">

      <Filter>Header Files</Filter>

    </ClInclude>

				RelativePath=".\..\src\linkgraph\linkgraph.cpp"

				>

			</File>

			<File

				RelativePath=".\..\src\linkgraph\linkgraph.h"

				>

			</File>

			<File

				RelativePath=".\..\src\linkgraph\linkgraph_type.h"

				>

			</File>

			<File

				RelativePath=".\..\src\linkgraph\linkgraph.cpp"

				>

			</File>

			<File

				RelativePath=".\..\src\linkgraph\linkgraph.h"

				>

			</File>

			<File

				RelativePath=".\..\src\linkgraph\linkgraph_type.h"

				>

			</File>

			<File

linkgraph/linkgraph.cpp

linkgraph/linkgraph.h

linkgraph/linkgraph_base.h

linkgraph/linkgraph_type.h

/* $Id$ */

/*

 * 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.cpp Definition of link graph classes used for cargo distribution. */

#include "../stdafx.h"

#include "../core/pool_func.hpp"

#include "linkgraph.h"

/* Initialize the link-graph-pool */

LinkGraphPool _link_graph_pool("LinkGraph");

INSTANTIATE_POOL_METHODS(LinkGraph)

/**

 * Create a node or clear it.

 * @param st ID of the associated station.

 * @param demand Demand for cargo at the station.

 */

inline void LinkGraph::BaseNode::Init(StationID st, uint demand)

{

	this->supply = 0;

	this->demand = demand;

	this->station = st;

	this->last_update = INVALID_DATE;

}

/**

 * Create an edge.

 * @param distance Length of the link as manhattan distance.

 */

inline void LinkGraph::BaseEdge::Init(uint distance)

{

	this->distance = distance;

	this->capacity = 0;

	this->usage = 0;

	this->last_update = INVALID_DATE;

	this->next_edge = INVALID_NODE;

}

void LinkGraph::Compress()

{

	this->last_compression = (_date + this->last_compression) / 2;

	for (NodeID node1 = 0; node1 < this->Size(); ++node1) {

		this->nodes[node1].supply /= 2;

		for (NodeID node2 = 0; node2 < this->Size(); ++node2) {

			BaseEdge &edge = this->edges[node1][node2];

			if (edge.capacity > 0) {

				edge.capacity = max(1U, edge.capacity / 2);

				edge.usage /= 2;

			}

		}

	}

}

/**

 * Merge a link graph with another one.

 * @param other LinkGraph to be merged into this one.

 */

void LinkGraph::Merge(LinkGraph *other)

{

	Date age = _date - this->last_compression + 1;

	Date other_age = _date - other->last_compression + 1;

	NodeID first = this->Size();

	for (NodeID node1 = 0; node1 < other->Size(); ++node1) {

		Station *st = Station::Get(other->nodes[node1].station);

		NodeID new_node = this->AddNode(st);

		this->nodes[new_node].supply = LinkGraph::Scale(other->nodes[node1].supply, age, other_age);

		st->goods[this->cargo].link_graph = this->index;

		st->goods[this->cargo].node = new_node;

		for (NodeID node2 = 0; node2 < node1; ++node2) {

			BaseEdge &forward = this->edges[new_node][first + node2];

			BaseEdge &backward = this->edges[first + node2][new_node];

			forward = other->edges[node1][node2];

			backward = other->edges[node2][node1];

			forward.capacity = LinkGraph::Scale(forward.capacity, age, other_age);

			forward.usage = LinkGraph::Scale(forward.usage, age, other_age);

			if (forward.next_edge != INVALID_NODE) forward.next_edge += first;

			backward.capacity = LinkGraph::Scale(backward.capacity, age, other_age);

			backward.usage = LinkGraph::Scale(backward.usage, age, other_age);

			if (backward.next_edge != INVALID_NODE) backward.next_edge += first;

		}

		BaseEdge &new_start = this->edges[new_node][new_node];

		new_start = other->edges[node1][node1];

		if (new_start.next_edge != INVALID_NODE) new_start.next_edge += first;

	}

	delete other;

}

/**

 * Remove a node from the link graph by overwriting it with the last node.

 * @param id ID of the node to be removed.

 */

void LinkGraph::RemoveNode(NodeID id)

{

	assert(id < this->Size());

	NodeID last_node = this->Size() - 1;

	for (NodeID i = 0; i <= last_node; ++i) {

		(*this)[i].RemoveEdge(id);

		BaseEdge *node_edges = this->edges[i];

		NodeID prev = i;

		NodeID next = node_edges[i].next_edge;

		while (next != INVALID_NODE) {

			if (next == last_node) {

				node_edges[prev].next_edge = id;

				break;

			}

			prev = next;

			next = node_edges[prev].next_edge;

		}

		node_edges[id] = node_edges[last_node];

	}

	Station::Get(this->nodes[last_node].station)->goods[this->cargo].node = id;

	this->nodes.Erase(this->nodes.Get(id));

	this->edges.EraseColumn(id);

	/* Not doing EraseRow here, as having the extra invalid row doesn't hurt

	 * and removing it would trigger a lot of memmove. The data has already

	 * been copied around in the loop above. */

}

/**

 * Add a node to the component and create empty edges associated with it. Set

 * the station's last_component to this component. Calculate the distances to all

 * other nodes. The distances to _all_ nodes are important as the demand

 * calculator relies on their availability.

 * @param st New node's station.

 * @return New node's ID.

 */

NodeID LinkGraph::AddNode(const Station *st)

{

	const GoodsEntry &good = st->goods[this->cargo];

	NodeID new_node = this->Size();

	this->nodes.Append();

	/* Avoid reducing the height of the matrix as that is expensive and we

	 * most likely will increase it again later which is again expensive. */

	this->edges.Resize(new_node + 1U,

			max(new_node + 1U, this->edges.Height()));

	this->nodes[new_node].Init(st->index,

			HasBit(good.acceptance_pickup, GoodsEntry::GES_ACCEPTANCE));

	BaseEdge *new_edges = this->edges[new_node];

	/* Reset the first edge starting at the new node */

	new_edges[new_node].next_edge = INVALID_NODE;

	for (NodeID i = 0; i <= new_node; ++i) {

		uint distance = DistanceManhattan(st->xy, Station::Get(this->nodes[i].station)->xy);

		new_edges[i].Init(distance);

		this->edges[i][new_node].Init(distance);

	}

	return new_node;

}

/**

 * Fill an edge with values from a link.

 * @param to Destination node of the link.

 * @param capacity Capacity of the link.

 */

void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage)

{

	assert(this->index != to);

	BaseEdge &edge = this->edges[to];

	BaseEdge &first = this->edges[this->index];

	edge.capacity = capacity;

	edge.usage = usage == UINT_MAX ? 0 : usage;

	edge.next_edge = first.next_edge;

	first.next_edge = to;

	edge.last_update = _date;

}

void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage)

{

	assert(capacity > 0);

	assert(usage <= capacity || usage == UINT_MAX);

	if (this->edges[to].last_update == INVALID_DATE) {

		this->AddEdge(to, capacity, usage);

	} else {

		(*this)[to].Update(capacity, usage);

	}

}

/**

 * Remove an outgoing edge from this node.

 * @param to ID of destination node.

 */

void LinkGraph::Node::RemoveEdge(NodeID to)

{

	if (this->index == to) return;

	BaseEdge &edge = this->edges[to];

	edge.capacity = 0;

	edge.last_update = INVALID_DATE;

	edge.usage = 0;

	NodeID prev = this->index;

	NodeID next = this->edges[this->index].next_edge;

	while (next != INVALID_NODE) {

		if (next == to) {

			/* Will be removed, skip it. */

			this->edges[prev].next_edge = edge.next_edge;

			edge.next_edge = INVALID_NODE;

			break;

		} else {

			prev = next;

			next = this->edges[next].next_edge;

		}

	}

}

/**

 * Create a new edge or update an existing one. If usage is UINT_MAX refresh

 * the edge to have at least the given capacity, otherwise add the capacity.

 * @param from Start node of the edge.

 * @param to End node of the edge.

 * @param capacity Capacity to be added/updated.

 * @param usage Usage to be added or UINT_MAX.

 */

void LinkGraph::Edge::Update(uint capacity, uint usage)

{

	assert(this->edge.capacity > 0);

	if (usage == UINT_MAX) {

		this->edge.capacity = max(this->edge.capacity, capacity);

	} else {

		assert(capacity >= usage);

		this->edge.capacity += capacity;

		this->edge.usage += usage;

	}

	this->edge.last_update = _date;

}

/**

 * Resize the component and fill it with empty nodes and edges. Used when

 * loading from save games. The component is expected to be empty before.

 * @param size New size of the component.

 */

void LinkGraph::Init(uint size)

{

	assert(this->Size() == 0);

	this->edges.Resize(size, size);

	this->nodes.Resize(size);

	for (uint i = 0; i < size; ++i) {

		this->nodes[i].Init();

		BaseEdge *column = this->edges[i];

		for (uint j = 0; j < size; ++j) column[j].Init();

	}

}

/* $Id$ */

/*

 * 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 "../core/smallmatrix_type.hpp"

#include "../station_base.h"

#include "../cargotype.h"

#include "../date_func.h"

#include "linkgraph_type.h"

struct SaveLoad;

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, 0xFFFFFF> 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:

	/**

	 * 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.

		Date last_update;        ///< When the supply was last updated.

		void Init(StationID st = INVALID_STATION, uint demand = 0);

	};

	/**

	 * An edge in the link graph. Corresponds to a link between two stations or at

	 * least the distance between them. Edges from one node to itself contain the

	 * ID of the opposite Node of the first active edge (i.e. not just distance) in

	 * the column as next_edge.

	 */

	struct BaseEdge {

		uint distance;    ///< Length of the link.

		uint capacity;    ///< Capacity of the link.

		uint usage;       ///< Usage of the link.

		Date last_update; ///< When the link was last updated.

		NodeID next_edge; ///< Destination of next valid edge starting at the same source node.

		void Init(uint distance = 0);

	};

	/**

	 * Wrapper for an edge (const or not) allowing retrieval, but no modification.

	 * @tparam Tedge Actual edge class, may be "const BaseEdge" or just "BaseEdge".

	 */

	template<typename Tedge>

	class EdgeWrapper {

	protected:

		Tedge &edge; ///< Actual edge to be used.

	public:

		/**

		 * Wrap a an edge.

		 * @param edge Edge to be wrapped.

		 */

		EdgeWrapper (Tedge &edge) : edge(edge) {}

		/**

		 * Get edge's capacity.

		 * @return Capacity.

		 */

		uint Capacity() const { return this->edge.capacity; }

		/**

		 * Get edge's usage.

		 * @return Usage.

		 */

		uint Usage() const { return this->edge.usage; }

		/**

		 * Get edge's distance.

		 * @return Distance.

		 */

		uint Distance() const { return this->edge.distance; }

		/**

		 * Get edge's last update.

		 * @return Last update.

		 */

		Date LastUpdate() const { return this->edge.last_update; }

	};

	/**

	 * Wrapper for a node (const or not) allowing retrieval, but no modification.

	 * @tparam Tedge Actual node class, may be "const BaseNode" or just "BaseNode".

	 * @tparam Tedge Actual edge class, may be "const BaseEdge" or just "BaseEdge".

	 */

	template<typename Tnode, typename Tedge>

	class NodeWrapper {

	protected:

		Tnode &node;  ///< Node being wrapped.

		Tedge *edges; ///< Outgoing edges for wrapped node.

		NodeID index; ///< ID of wrapped node.

	public:

		/**

		 * Wrap a node.

		 * @param node Node to be wrapped.

		 * @param edges Outgoing edges for node to be wrapped.

		 * @param index ID of node to be wrapped.

		 */

		NodeWrapper(Tnode &node, Tedge *edges, NodeID index) : node(node),

			edges(edges), index(index) {}

		/**

		 * Get supply of wrapped node.

		 * @return Supply.

		 */

		uint Supply() const { return this->node.supply; }

		/**

		 * Get demand of wrapped node.

		 * @return Demand.

		 */

		uint Demand() const { return this->node.demand; }

		/**

		 * Get ID of station belonging to wrapped node.

		 * @return ID of node's station.

		 */

		StationID Station() const { return this->node.station; }

		/**

		 * Get node's last update.

		 * @return Last update.

		 */

		Date LastUpdate() const { return this->node.last_update; }

	};

	/**

	 * Base class for iterating across outgoing edges of a node. Only the real

	 * edges (those with capacity) are iterated. The ones with only distance

	 * information are skipped.

	 * @tparam Tedge Actual edge class. May be "BaseEdge" or "const BaseEdge".

	 * @tparam Titer Actual iterator class.

	 */

	template <class Tedge, class Tedge_wrapper, class Titer>

	class BaseEdgeIterator {

	protected:

		Tedge *base;    ///< Array of edges being iterated.

		NodeID current; ///< Current offset in edges array.

		/**

		 * A "fake" pointer to enable operator-> on temporaries. As the objects

		 * returned from operator* aren't references but real objects, we have

		 * to return something that implements operator->, but isn't a pointer

		 * from operator->. A fake pointer.

		 */

		class FakePointer : public SmallPair<NodeID, Tedge_wrapper> {

		public:

			/**

			 * Construct a fake pointer from a pair of NodeID and edge.

			 * @param pair Pair to be "pointed" to (in fact shallow-copied).

			 */

			FakePointer(const SmallPair<NodeID, Tedge_wrapper> &pair) : SmallPair<NodeID, Tedge_wrapper>(pair) {}

			/**

			 * Retrieve the pair by operator->.

			 * @return Pair being "pointed" to.

			 */

			SmallPair<NodeID, Tedge_wrapper> *operator->() { return this; }

		};

	public:

		/**

		 * Constructor.

		 * @param base Array of edges to be iterated.

		 * @param current ID of current node (to locate the first edge).

		 */

		BaseEdgeIterator (Tedge *base, NodeID current) :

			base(base),

			current(current == INVALID_NODE ? current : base[current].next_edge)

		{}

		/**

		 * Prefix-increment.

		 * @return This.

		 */

		Titer &operator++()

		{

			this->current = this->base[this->current].next_edge;

			return static_cast<Titer &>(*this);

		}

		/**

		 * Postfix-increment.

		 * @return Version of this before increment.

		 */

		Titer operator++(int)

		{

			Titer ret(static_cast<Titer &>(*this));

			this->current = this->base[this->current].next_edge;

			return ret;

		}

		/**

		 * Compare with some other edge iterator. The other one may be of a

		 * child class.

		 * @tparam Tother Class of other iterator.

		 * @param other Instance of other iterator.

		 * @return If the iterators have the same edge array and current node.

		 */

		template<class Tother>

		bool operator==(const Tother &other)

		{

			return this->base == other.base && this->current == other.current;

		}

		/**

		 * Compare for inequality with some other edge iterator. The other one

		 * may be of a child class.

		 * @tparam Tother Class of other iterator.

		 * @param other Instance of other iterator.

		 * @return If either the edge arrays or the current nodes differ.

		 */

		template<class Tother>

		bool operator!=(const Tother &other)

		{

			return this->base != other.base || this->current != other.current;

		}

		/**

		 * Dereference with operator*.

		 * @return Pair of current target NodeID and edge object.

		 */

		SmallPair<NodeID, Tedge_wrapper> operator*() const

		{

			return SmallPair<NodeID, Tedge_wrapper>(this->current, Tedge_wrapper(this->base[this->current]));

		}

		/**

		 * Dereference with operator->.

		 * @return Fake pointer to Pair of current target NodeID and edge object.

		 */

		FakePointer operator->() const {

			return FakePointer(this->operator*());

		}

	};

	/**

	 * A constant edge class.

	 */

	typedef EdgeWrapper<const BaseEdge> ConstEdge;

	/**

	 * An updatable edge class.

	 */

	class Edge : public EdgeWrapper<BaseEdge> {

	public:

		/**

		 * Constructor

		 * @param edge Edge to be wrapped.

		 */

		Edge(BaseEdge &edge) : EdgeWrapper<BaseEdge>(edge) {}

		void Update(uint capacity, uint usage);

	};

	/**

	 * An iterator for const edges. Cannot be typedef'ed because of

	 * template-reference to ConstEdgeIterator itself.

	 */

	class ConstEdgeIterator : public BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator> {

	public:

		/**

		 * Constructor.

		 * @param edges Array of edges to be iterated over.

		 * @param current ID of current edge's end node.

		 */

		ConstEdgeIterator(const BaseEdge *edges, NodeID current) :

			BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator>(edges, current) {}

	};

	/**

	 * An iterator for non-const edges. Cannot be typedef'ed because of

	 * template-reference to EdgeIterator itself.

	 */

	class EdgeIterator : public BaseEdgeIterator<BaseEdge, Edge, EdgeIterator> {

	public:

		/**

		 * Constructor.

		 * @param edges Array of edges to be iterated over.

		 * @param current ID of current edge's end node.

		 */

		EdgeIterator(BaseEdge *edges, NodeID current) :

			BaseEdgeIterator<BaseEdge, Edge, EdgeIterator>(edges, current) {}

	};

	/**

	 * Constant node class. Only retrieval operations are allowed on both the

	 * node itself and its edges.

	 */

	class ConstNode : public NodeWrapper<const BaseNode, const BaseEdge> {

	public:

		/**

		 * Constructor.

		 * @param lg LinkGraph to get the node from.

		 * @param node ID of the node.

		 */

		ConstNode(const LinkGraph *lg, NodeID node) :

			NodeWrapper<const BaseNode, const BaseEdge>(lg->nodes[node], lg->edges[node], node)

		{}

		/**

		 * Get a ConstEdge. This is not a reference as the wrapper objects are

		 * not actually persistent.

		 * @param to ID of end node of edge.

		 * @return Constant edge wrapper.

		 */

		ConstEdge operator[](NodeID to) const { return ConstEdge(this->edges[to]); }

		/**

		 * Get an iterator pointing to the start of the edges array.

		 * @return Constant edge iterator.

		 */

		ConstEdgeIterator Begin() const { return ConstEdgeIterator(this->edges, this->index); }

		/**

		 * Get an iterator pointing beyond the end of the edges array.

		 * @return Constant edge iterator.

		 */

		ConstEdgeIterator End() const { return ConstEdgeIterator(this->edges, INVALID_NODE); }

	};

	/**

	 * Updatable node class. The node itself as well as its edges can be modified.

	 */

	class Node : public NodeWrapper<BaseNode, BaseEdge> {

	public:

		/**

		 * Constructor.

		 * @param lg LinkGraph to get the node from.

		 * @param node ID of the node.

		 */

		Node(LinkGraph *lg, NodeID node) :

			NodeWrapper<BaseNode, BaseEdge>(lg->nodes[node], lg->edges[node], node)

		{}

		/**

		 * Get an Edge. This is not a reference as the wrapper objects are not

		 * actually persistent.

		 * @param to ID of end node of edge.

		 * @return Edge wrapper.

		 */

		Edge operator[](NodeID to) { return Edge(this->edges[to]); }

		/**

		 * Get an iterator pointing to the start of the edges array.

		 * @return Edge iterator.

		 */

		EdgeIterator Begin() { return EdgeIterator(this->edges, this->index); }

		/**