/* $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 refresh.h Definition of link refreshing utility. */

#include "../stdafx.h"

#include "../core/bitmath_func.hpp"

#include "../station_func.h"

#include "../engine_base.h"

#include "../vehicle_func.h"

#include "refresh.h"

#include "linkgraph.h"

/**

 * Refresh all links the given vehicle will visit.

 * @param v Vehicle to refresh links for.

 */

/* static */ void LinkRefresher::Run(Vehicle *v)

{

	/* If there are no orders we can't predict anything.*/

	if (v->orders.list == NULL) return;

	LinkRefresher refresher(v);

	if (refresher.first == NULL) return;

	refresher.RefreshLinks(refresher.first, refresher.first, v->last_loading_station != INVALID_STATION ? 1 << HAS_CARGO : 0);

}

/**

 * Constructor for link refreshing algorithm.

 * @param vehicle Vehicle to refresh links for.

 */

LinkRefresher::LinkRefresher(Vehicle *vehicle) : vehicle(vehicle), hops(0)

{

	/* Assemble list of capacities and set last loading stations to 0. */

	for (Vehicle *v = this->vehicle; v != NULL; v = v->Next()) {

		this->refit_capacities.push_back(RefitDesc(v->cargo_type, v->cargo_cap, v->refit_cap));

		if (v->refit_cap > 0) this->capacities[v->cargo_type] += v->refit_cap;

	}

	this->first = this->vehicle->GetOrder(this->vehicle->cur_implicit_order_index);

	/* Make sure the first order is a useful order. */

	this->first = this->vehicle->orders.list->GetNextDecisionNode(this->first, 0);

}

/**

 * Handle refit orders by updating capacities and refit_capacities.

 * @param next Order to be processed.

 */

void LinkRefresher::HandleRefit(const Order *next)

{

	CargoID new_cid = next->GetRefitCargo();

	RefitList::iterator refit_it = this->refit_capacities.begin();

	for (Vehicle *v = this->vehicle; v != NULL; v = v->Next()) {

		const Engine *e = Engine::Get(v->engine_type);

		if (!HasBit(e->info.refit_mask, new_cid)) {

			++refit_it;

			continue;

		}

		/* Back up the vehicle's cargo type */

		CargoID temp_cid = v->cargo_type;

		byte temp_subtype = v->cargo_subtype;

		v->cargo_type = new_cid;

		v->cargo_subtype = GetBestFittingSubType(v, v, new_cid);

		uint16 mail_capacity = 0;

		uint amount = e->DetermineCapacity(v, &mail_capacity);

		/* Restore the original cargo type */

		v->cargo_type = temp_cid;

		v->cargo_subtype = temp_subtype;

		/* Skip on next refit. */

		if (new_cid != refit_it->cargo && refit_it->remaining > 0) {

			this->capacities[refit_it->cargo] -= refit_it->remaining;

			refit_it->remaining = 0;

		} else if (amount < refit_it->remaining) {

			this->capacities[refit_it->cargo] -= refit_it->remaining - amount;

			refit_it->remaining = amount;

		}

		refit_it->capacity = amount;

		refit_it->cargo = new_cid;

		++refit_it;

		/* Special case for aircraft with mail. */

		if (v->type == VEH_AIRCRAFT) {

			if (mail_capacity < refit_it->remaining) {

				this->capacities[refit_it->cargo] -= refit_it->remaining - mail_capacity;

				refit_it->remaining = mail_capacity;

			}

			refit_it->capacity = mail_capacity;

			break; // aircraft have only one vehicle

		}

	}

}

/**

 * Restore capacities and refit_capacities as vehicle might have been able to load now.

 */

void LinkRefresher::ResetRefit()

{

	for (RefitList::iterator it(this->refit_capacities.begin()); it != this->refit_capacities.end(); ++it) {

		if (it->remaining == it->capacity) continue;

		this->capacities[it->cargo] += it->capacity - it->remaining;

		it->remaining = it->capacity;

	}

}

/**

 * Predict the next order the vehicle will execute and resolve conditionals by

 * recursion and return next non-conditional order in list.

 * @param cur Current order being evaluated.

 * @param next Next order to be evaluated.

 * @param flags RefreshFlags to give hints about the previous link and state carried over from that.

 * @return new next Order.

 */

const Order *LinkRefresher::PredictNextOrder(const Order *cur, const Order *next, uint8 flags)

{

	do {

		if (HasBit(flags, USE_NEXT)) {

			/* First incrementation has to be skipped if a "real" next hop,

			 * different from cur, was given. */

			ClrBit(flags, USE_NEXT);

		} else {

			const Order *skip_to = NULL;

			if (next->IsType(OT_CONDITIONAL)) {

				skip_to = this->vehicle->orders.list->GetNextDecisionNode(

						this->vehicle->orders.list->GetOrderAt(next->GetConditionSkipToOrder()),

						this->hops / 2);

			}

			/* Reassign next with the following stop. This can be a station or a

			 * depot. Allow the order list to be walked twice so that we can

			 * reassign "first" below without afterwards terminating early here. */

			next = this->vehicle->orders.list->GetNextDecisionNode(

					this->vehicle->orders.list->GetNext(next), ++this->hops / 2);

			if (skip_to != NULL) {

				/* Make copies of capacity tracking lists. There is potential

				 * for optimization here. If the vehicle never refits we don't

				 * need to copy anything. Also, if we've seen the branched link

				 * before we don't need to branch at all. */

				++this->hops;

				LinkRefresher branch(*this);

				branch.RefreshLinks(cur, skip_to, flags | (cur != skip_to ? 1 << USE_NEXT : 0));

				this->hops = branch.hops;

			}

		}

	} while (next != NULL && next->IsType(OT_CONDITIONAL));

	return next;

}

/**

 * Refresh link stats for the given pair of orders.

 * @param cur Last stop where the consist could interact with cargo.

 * @param next Next order to be processed.

 */

void LinkRefresher::RefreshStats(const Order *cur, const Order *next)

{

	StationID next_station = next->GetDestination();

	Station *st = Station::GetIfValid(cur->GetDestination());

	if (st != NULL && next_station != INVALID_STATION && next_station != st->index) {

		for (CapacitiesMap::const_iterator i = this->capacities.begin(); i != this->capacities.end(); ++i) {

			/* Refresh the link and give it a minimum capacity. */

			if (i->second == 0) continue;

			/* A link is at least partly restricted if a

			 * vehicle can't load at its source. */

			IncreaseStats(st, i->first, next_station, i->second,

					(cur->GetLoadType() & OLFB_NO_LOAD) == 0 ? LinkGraph::REFRESH_UNRESTRICTED : LinkGraph::REFRESH_RESTRICTED);

		}

	}

}

/**

 * Iterate over orders starting at \a cur and \a next and refresh links

 * associated with them. \a cur and \a next can be equal. If they're not they

 * must be "neigbours" in their order list, which means \a next must be directly

 * reachable from \a cur without passing any further OT_GOTO_STATION or

 * OT_IMPLICIT orders in between.

 * @param cur Current order being evaluated.

 * @param next Next order to be checked.

 * @param flags RefreshFlags to give hints about the previous link and state carried over from that.

 */

void LinkRefresher::RefreshLinks(const Order *cur, const Order *next, uint8 flags)

{

	while (next != NULL) {

		/* If the refit cargo is CT_AUTO_REFIT, we're optimistic and assume the

		 * cargo will stay the same. The point of this method is to avoid

		 * deadlocks due to vehicles waiting for cargo that isn't being routed,

		 * yet. That situation will not occur if the vehicle is actually

		 * carrying a different cargo in the end. */

		if ((next->IsType(OT_GOTO_DEPOT) || next->IsType(OT_GOTO_STATION)) &&

				next->IsRefit() && !next->IsAutoRefit()) {

			SetBit(flags, WAS_REFIT);

			this->HandleRefit(next);

		}

		/* Only reset the refit capacities if the "previous" next is a station,

		 * meaning that either the vehicle was refit at the previous station or

		 * it wasn't at all refit during the current hop. */

		if (HasBit(flags, WAS_REFIT) && (next->IsType(OT_GOTO_STATION) || next->IsType(OT_IMPLICIT))) {

			SetBit(flags, RESET_REFIT);

		} else {

			ClrBit(flags, RESET_REFIT);

		}

		next = this->PredictNextOrder(cur, next, flags);

		if (next == NULL) break;

		/* Skip resetting and link refreshing if next order won't do anything with cargo. */

		if (!next->IsType(OT_GOTO_STATION) && !next->IsType(OT_IMPLICIT)) continue;

		if (HasBit(flags, RESET_REFIT)) {

			this->ResetRefit();

			ClrBit(flags, RESET_REFIT);

			ClrBit(flags, WAS_REFIT);

		}

		if (cur->IsType(OT_GOTO_STATION) || cur->IsType(OT_IMPLICIT)) {

			if (cur->CanLeaveWithCargo(HasBit(flags, HAS_CARGO))) {

				SetBit(flags, HAS_CARGO);

				this->RefreshStats(cur, next);

			} else {

				ClrBit(flags, HAS_CARGO);

			}

		}

		/* "cur" is only assigned here if the stop is a station so that

		 * whenever stats are to be increased two stations can be found.

		 * However, "first" can be a depot stop. If that is the case

		 * reassign it to make sure we end up with a station for the last

		 * link. */

		cur = next;

		if (cur == this->first) break;

		if (!this->first->IsType(OT_GOTO_STATION) && !this->first->IsType(OT_IMPLICIT)) {

			this->first = cur;

		}

	}

}

/* $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 refresh.h Declaration of link refreshing utility. */

#ifndef REFRESH_H

#define REFRESH_H

#include "../cargo_type.h"

#include "../vehicle_base.h"

#include <list>

#include <map>

/**

 * Utility to refresh links a consist will visit.

 */

class LinkRefresher {

public:

	static void Run(Vehicle *v);

protected:

	/**

	 * Various flags about properties of the last examined link that might have

	 * an influence on the next one.

	 */

	enum RefreshFlags {

		USE_NEXT,   ///< There has been a previous link. Try to use the given next order.

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

		WAS_REFIT,  ///< Consist was refit since the last stop where it could interact with cargo.

		RESET_REFIT ///< Consist had a chance to load since the last refit and the refit capacities can be reset.

	};

	/**

	 * Simulated cargo type and capacity for prediction of future links.

	 */

	struct RefitDesc {

		CargoID cargo;    ///< Cargo type the vehicle will be carrying.

		uint16 capacity;  ///< Capacity the vehicle will have.

		uint16 remaining; ///< Capacity remaining from before the previous refit.

		RefitDesc(CargoID cargo, uint16 capacity, uint16 remaining) :

				cargo(cargo), capacity(capacity), remaining(remaining) {}

	};

	typedef std::list<RefitDesc> RefitList;

	typedef std::map<CargoID, uint> CapacitiesMap;

	Vehicle *vehicle;           ///< Vehicle for which the links should be refreshed.

	const Order *first;         ///< Order to be checked first. If this is encountered again the refreshing is considered finished.

	CapacitiesMap capacities;   ///< Current added capacities per cargo ID in the consist.

	RefitList refit_capacities; ///< Current state of capacity remaining from previous refits versus overall capacity per vehicle in the consist.

	uint hops;                  ///< Number of hops already used up. If more than two times the number of orders in the list have been checked refreshing is stopped.

	LinkRefresher(Vehicle *v);

	void HandleRefit(const Order *next);

	void ResetRefit();

	void RefreshStats(const Order *cur, const Order *next);

	const Order *PredictNextOrder(const Order *cur, const Order *next, uint8 flags);

	void RefreshLinks(const Order *cur, const Order *next, uint8 flags);

};

#endif // REFRESH_H