(svn r11011) -Fix [FS#1129]: GetFirstVehicleInChain did change the game state while being marked const.

-Codechange: do not brute force determine the first vehicle in the chain or previous vehicle, but do it by properly accounting the previous and first pointers when updating the next pointer. This gives a performance increase of about 15% when there are a lot of vehicles in the game.

10 files changed, 101 insertions, 132 deletions

diff --git a/src/autoreplace_cmd.cpp b/src/autoreplace_cmd.cpp
index 606a60126..08638a903 100644
--- a/src/autoreplace_cmd.cpp
+++ b/src/autoreplace_cmd.cpp
@@ -52,7 +52,7 @@ static void MoveVehicleCargo(Vehicle *dest, Vehicle *source)
 	 * the complete train, which is without the weight of cargo we just
 	 * moved back into some (of the) new wagon(s).
 	 */
-	if (dest->type == VEH_TRAIN) TrainConsistChanged(dest->first);
+	if (dest->type == VEH_TRAIN) TrainConsistChanged(dest->First());
 }
 
 static bool VerifyAutoreplaceRefitForOrders(const Vehicle *v, const EngineID engine_type)
@@ -61,7 +61,7 @@ static bool VerifyAutoreplaceRefitForOrders(const Vehicle *v, const EngineID eng
 	const Vehicle *u;
 
 	if (v->type == VEH_TRAIN) {
-		u = GetFirstVehicleInChain(v);
+		u = v->First();
 	} else {
 		u = v;
 	}
@@ -104,7 +104,7 @@ static CargoID GetNewCargoTypeForReplace(Vehicle *v, EngineID engine_type)
 
 	/* the old engine didn't have cargo capacity, but the new one does
 	 * now we will figure out what cargo the train is carrying and refit to fit this */
-	v = GetFirstVehicleInChain(v);
+	v = v->First();
 	do {
 		if (v->cargo_cap == 0) continue;
 		/* Now we found a cargo type being carried on the train and we will see if it is possible to carry to this one */
@@ -200,9 +200,9 @@ static CommandCost ReplaceVehicle(Vehicle **w, byte flags, Money total_cost)
 			 * sell the old engine in a moment
 			 */
 			/* Get the vehicle in front of the one we move out */
-			Vehicle *front = GetPrevVehicleInChain(old_v);
+			Vehicle *front = old_v->Previous();
 			/* If the vehicle in front is the rear end of a dualheaded engine, then we need to use the one in front of that one */
-			if (IsMultiheaded(front) && !IsTrainEngine(front)) front = GetPrevVehicleInChain(front);
+			if (IsMultiheaded(front) && !IsTrainEngine(front)) front = front->Previous();
 			/* Now we move the old one out of the train */
 			DoCommand(0, (INVALID_VEHICLE << 16) | old_v->index, 0, DC_EXEC, CMD_MOVE_RAIL_VEHICLE);
 			/* Add the new vehicle */
@@ -236,7 +236,7 @@ static CommandCost ReplaceVehicle(Vehicle **w, byte flags, Money total_cost)
 			}
 		}
 		/* We are done setting up the new vehicle. Now we move the cargo from the old one to the new one */
-		MoveVehicleCargo(new_v->type == VEH_TRAIN ? GetFirstVehicleInChain(new_v) : new_v, old_v);
+		MoveVehicleCargo(new_v->type == VEH_TRAIN ? new_v->First() : new_v, old_v);
 
 		// Get the name of the old vehicle if it has a custom name.
 		if (!IsCustomName(old_v->string_id)) {
diff --git a/src/depot_gui.cpp b/src/depot_gui.cpp
index 0ca889b78..318ee3f3d 100644
--- a/src/depot_gui.cpp
+++ b/src/depot_gui.cpp
@@ -359,7 +359,7 @@ static int GetVehicleFromDepotWndPt(const Window *w, int x, int y, Vehicle **veh
 			while (v != NULL && (x -= v->u.rail.cached_veh_length) >= 0) v = v->Next();
 
 			/* if an articulated part was selected, find its parent */
-			while (v != NULL && IsArticulatedPart(v)) v = GetPrevVehicleInChain(v);
+			while (v != NULL && IsArticulatedPart(v)) v = v->Previous();
 
 			d->wagon = v;
 
@@ -398,7 +398,7 @@ static void TrainDepotMoveVehicle(Vehicle *wagon, VehicleID sel, Vehicle *head)
 	if (wagon == NULL) {
 		if (head != NULL) wagon = GetLastVehicleInChain(head);
 	} else  {
-		wagon = GetPrevVehicleInChain(wagon);
+		wagon = wagon->Previous();
 		if (wagon == NULL) return;
 	}
 
@@ -475,7 +475,7 @@ static void HandleCloneVehClick(const Vehicle *v, const Window *w)
 	if (v == NULL) return;
 
 	if (v->HasFront() && !v->IsPrimaryVehicle()) {
-		v = GetFirstVehicleInChain(v);
+		v = v->First();
 		/* Do nothing when clicking on a train in depot with no loc attached */
 		if (v->type == VEH_TRAIN && !IsFrontEngine(v)) return;
 	}
diff --git a/src/newgrf_engine.cpp b/src/newgrf_engine.cpp
index 4f1ef3a05..9272a6d52 100644
--- a/src/newgrf_engine.cpp
+++ b/src/newgrf_engine.cpp
@@ -516,7 +516,7 @@ static uint32 VehicleGetVariable(const ResolverObject *object, byte variable, by
 				byte chain_before = 0;
 				byte chain_after  = 0;
 
-				for (u = GetFirstVehicleInChain(v); u != v; u = u->Next()) {
+				for (u = v->First(); u != v; u = u->Next()) {
 					chain_before++;
 					if (variable == 0x41 && u->engine_type != v->engine_type) chain_before = 0;
 				}
@@ -610,7 +610,7 @@ static uint32 VehicleGetVariable(const ResolverObject *object, byte variable, by
 			 */
 			if (v->type != VEH_TRAIN) return 0;
 
-			const Vehicle *u_p = GetPrevVehicleInChain(v);
+			const Vehicle *u_p = v->Previous();
 			const Vehicle *u_n = v->Next();
 			DirDiff f = (u_p == NULL) ?  DIRDIFF_SAME : DirDifference(u_p->direction, v->direction);
 			DirDiff b = (u_n == NULL) ?  DIRDIFF_SAME : DirDifference(v->direction, u_n->direction);
@@ -758,8 +758,8 @@ static uint32 VehicleGetVariable(const ResolverObject *object, byte variable, by
 				case 0x75: return GB(v->u.rail.cached_power,  8, 24);
 				case 0x76: return GB(v->u.rail.cached_power, 16, 16);
 				case 0x77: return GB(v->u.rail.cached_power, 24,  8);
-				case 0x7C: return v->first->index;
-				case 0x7D: return GB(v->first->index, 8, 8);
+				case 0x7C: return v->First()->index;
+				case 0x7D: return GB(v->First()->index, 8, 8);
 				case 0x7F: return 0; // Used for vehicle reversing hack in TTDP
 			}
 			break;
@@ -804,7 +804,7 @@ static const SpriteGroup *VehicleResolveReal(const ResolverObject *object, const
 	if (v == NULL) return group->g.real.loading[0];
 
 	if (v->type == VEH_TRAIN) {
-		in_motion = GetFirstVehicleInChain(v)->current_order.type != OT_LOADING;
+		in_motion = v->First()->current_order.type != OT_LOADING;
 	} else {
 		in_motion = v->current_order.type != OT_LOADING;
 	}
@@ -832,7 +832,7 @@ static inline void NewVehicleResolver(ResolverObject *res, EngineID engine_type,
 	res->ResolveReal   = &VehicleResolveReal;
 
 	res->u.vehicle.self   = v;
-	res->u.vehicle.parent = (v != NULL && v->HasFront()) ? GetFirstVehicleInChain(v) : v;
+	res->u.vehicle.parent = (v != NULL && v->HasFront()) ? v->First() : v;
 
 	res->u.vehicle.self_type = engine_type;
 
@@ -1033,7 +1033,7 @@ static void DoTriggerVehicle(Vehicle *v, VehicleTrigger trigger, byte base_rando
 			 * i.e.), so we give them all the NEW_CARGO triggered
 			 * vehicle's portion of random bits. */
 			assert(first);
-			DoTriggerVehicle((v->type == VEH_TRAIN) ? GetFirstVehicleInChain(v) : v, VEHICLE_TRIGGER_ANY_NEW_CARGO, new_random_bits, false);
+			DoTriggerVehicle((v->type == VEH_TRAIN) ? v->First() : v, VEHICLE_TRIGGER_ANY_NEW_CARGO, new_random_bits, false);
 			break;
 
 		case VEHICLE_TRIGGER_DEPOT:
diff --git a/src/order_gui.cpp b/src/order_gui.cpp
index c77fe32f0..0bf98f240 100644
--- a/src/order_gui.cpp
+++ b/src/order_gui.cpp
@@ -356,7 +356,7 @@ static bool HandleOrderVehClick(const Vehicle *v, const Vehicle *u, Window *w)
 	if (u->type != v->type) return false;
 
 	if (u->HasFront() && !u->IsPrimaryVehicle()) {
-		u = GetFirstVehicleInChain(u);
+		u = u->First();
 		if (!u->IsPrimaryVehicle()) return false;
 	}
 
diff --git a/src/roadveh_cmd.cpp b/src/roadveh_cmd.cpp
index 53155c8a1..ccb0c6962 100644
--- a/src/roadveh_cmd.cpp
+++ b/src/roadveh_cmd.cpp
@@ -141,8 +141,8 @@ void RoadVehUpdateCache(Vehicle *v)
 	assert(IsRoadVehFront(v));
 
 	for (Vehicle *u = v; u != NULL; u = u->Next()) {
-		/* Update the v->first cache. */
-		if (u->first == NULL) u->first = v;
+		/* Check the v->first cache. */
+		assert(u->First() == v);
 
 		/* Update the 'first engine' */
 		u->u.road.first_engine = (v == u) ? INVALID_ENGINE : v->engine_type;
@@ -259,7 +259,6 @@ CommandCost CmdBuildRoadVeh(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 		v->vehicle_flags = 0;
 		if (e->flags & ENGINE_EXCLUSIVE_PREVIEW) SETBIT(v->vehicle_flags, VF_BUILT_AS_PROTOTYPE);
 
-		v->first = NULL;
 		v->cargo_cap = GetVehicleProperty(v, 0x0F, rvi->capacity);
 
 		AddArticulatedParts(vl, VEH_ROAD);
@@ -868,7 +867,7 @@ static void* EnumCheckRoadVehClose(Vehicle *v, void* data)
 		!v->IsInDepot() &&
 		myabs(v->z_pos - rvf->veh->z_pos) < 6 &&
 		v->direction == rvf->dir &&
-		GetFirstVehicleInChain(rvf->veh) != GetFirstVehicleInChain(v) &&
+		rvf->veh->First() != v->First() &&
 		(dist_x[v->direction] >= 0 || (x_diff > dist_x[v->direction] && x_diff <= 0)) &&
 		(dist_x[v->direction] <= 0 || (x_diff < dist_x[v->direction] && x_diff >= 0)) &&
 		(dist_y[v->direction] >= 0 || (y_diff > dist_y[v->direction] && y_diff <= 0)) &&
diff --git a/src/train_cmd.cpp b/src/train_cmd.cpp
index 97c29a630..caf665cf0 100644
--- a/src/train_cmd.cpp
+++ b/src/train_cmd.cpp
@@ -161,8 +161,8 @@ void TrainConsistChanged(Vehicle* v)
 	for (Vehicle *u = v; u != NULL; u = u->Next()) {
 		const RailVehicleInfo *rvi_u = RailVehInfo(u->engine_type);
 
-		/* Update the v->first cache. This is faster than having to brute force it later. */
-		if (u->first == NULL) u->first = v;
+		/* Check the v->first cache. */
+		assert(u->First() == v);
 
 		/* update the 'first engine' */
 		u->u.rail.first_engine = v == u ? INVALID_ENGINE : first_engine;
@@ -583,8 +583,8 @@ static CommandCost CmdBuildRailWagon(EngineID engine, TileIndex tile, uint32 fla
 			_new_vehicle_id = v->index;
 
 			VehiclePositionChanged(v);
-			TrainConsistChanged(GetFirstVehicleInChain(v));
-			UpdateTrainGroupID(GetFirstVehicleInChain(v));
+			TrainConsistChanged(v->First());
+			UpdateTrainGroupID(v->First());
 
 			InvalidateWindow(WC_VEHICLE_DEPOT, v->tile);
 			if (IsLocalPlayer()) {
@@ -620,6 +620,7 @@ static CommandCost EstimateTrainCost(EngineID engine, const RailVehicleInfo* rvi
 
 static void AddRearEngineToMultiheadedTrain(Vehicle* v, Vehicle* u, bool building)
 {
+	u = new (u) Train();
 	u->direction = v->direction;
 	u->owner = v->owner;
 	u->tile = v->tile;
@@ -628,7 +629,6 @@ static void AddRearEngineToMultiheadedTrain(Vehicle* v, Vehicle* u, bool buildin
 	u->z_pos = v->z_pos;
 	u->u.rail.track = TRACK_BIT_DEPOT;
 	u->vehstatus = v->vehstatus & ~VS_STOPPED;
-	u = new (u) Train();
 	u->subtype = 0;
 	SetMultiheaded(u);
 	u->spritenum = v->spritenum + 1;
@@ -841,7 +841,6 @@ static Vehicle *UnlinkWagon(Vehicle *v, Vehicle *first)
 	Vehicle *u;
 	for (u = first; GetNextVehicle(u) != v; u = GetNextVehicle(u)) {}
 	GetLastEnginePart(u)->SetNext(GetNextVehicle(v));
-	v->first = NULL; // we shouldn't point to the old first, since the vehicle isn't in that chain anymore
 	return first;
 }
 
@@ -872,11 +871,12 @@ static Vehicle *FindGoodVehiclePos(const Vehicle *src)
  */
 static void AddWagonToConsist(Vehicle *v, Vehicle *dest)
 {
-	UnlinkWagon(v, GetFirstVehicleInChain(v));
+	UnlinkWagon(v, v->First());
 	if (dest == NULL) return;
 
-	v->SetNext(dest->Next());
+	Vehicle *next = dest->Next();
 	dest->SetNext(v);
+	v->SetNext(next);
 	ClearFreeWagon(v);
 	ClearFrontEngine(v);
 }
@@ -933,19 +933,19 @@ CommandCost CmdMoveRailVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32 p
 	}
 
 	/* if an articulated part is being handled, deal with its parent vehicle */
-	while (IsArticulatedPart(src)) src = GetPrevVehicleInChain(src);
+	while (IsArticulatedPart(src)) src = src->Previous();
 	if (dst != NULL) {
-		while (IsArticulatedPart(dst)) dst = GetPrevVehicleInChain(dst);
+		while (IsArticulatedPart(dst)) dst = dst->Previous();
 	}
 
 	/* don't move the same vehicle.. */
 	if (src == dst) return CommandCost();
 
 	/* locate the head of the two chains */
-	Vehicle *src_head = GetFirstVehicleInChain(src);
+	Vehicle *src_head = src->First();
 	Vehicle *dst_head;
 	if (dst != NULL) {
-		dst_head = GetFirstVehicleInChain(dst);
+		dst_head = dst->First();
 		if (dst_head->tile != src_head->tile) return CMD_ERROR;
 		/* Now deal with articulated part of destination wagon */
 		dst = GetLastEnginePart(dst);
@@ -1022,10 +1022,6 @@ CommandCost CmdMoveRailVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32 p
 
 	/* do it? */
 	if (flags & DC_EXEC) {
-		/* clear the ->first cache */
-		for (Vehicle *u = src_head; u != NULL; u = u->Next()) u->first = NULL;
-		for (Vehicle *u = dst_head; u != NULL; u = u->Next()) u->first = NULL;
-
 		/* If we move the front Engine and if the second vehicle is not an engine
 		   add the whole vehicle to the DEFAULT_GROUP */
 		if (IsFrontEngine(src) && !IsDefaultGroupID(src->group_id)) {
@@ -1101,13 +1097,12 @@ CommandCost CmdMoveRailVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32 p
 			}
 			dst->SetNext(src);
 		}
+
 		if (src->u.rail.other_multiheaded_part != NULL) {
 			if (src->u.rail.other_multiheaded_part == src_head) {
 				src_head = src_head->Next();
 			}
 			AddWagonToConsist(src->u.rail.other_multiheaded_part, src);
-			/* previous line set the front engine to the old front. We need to clear that */
-			src->u.rail.other_multiheaded_part->first = NULL;
 		}
 
 		/* If there is an engine behind first_engine we moved away, it should become new first_engine
@@ -1218,8 +1213,8 @@ CommandCost CmdSellRailWagon(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 
 	SET_EXPENSES_TYPE(EXPENSES_NEW_VEHICLES);
 
-	while (IsArticulatedPart(v)) v = GetPrevVehicleInChain(v);
-	Vehicle *first = GetFirstVehicleInChain(v);
+	while (IsArticulatedPart(v)) v = v->Previous();
+	Vehicle *first = v->First();
 
 	/* make sure the vehicle is stopped in the depot */
 	if (CheckTrainStoppedInDepot(first) < 0) {
@@ -1262,9 +1257,6 @@ CommandCost CmdSellRailWagon(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
 			if ((flags & DC_EXEC) && v == first) {
 				Vehicle *new_f = GetNextVehicle(first);
 
-				/* 2.1 If the first wagon is sold, update the first-> pointers to NULL */
-				for (Vehicle *tmp = first; tmp != NULL; tmp = tmp->Next()) tmp->first = NULL;
-
 				/* 2.2 If there are wagons present after the deleted front engine, check
 				 * if the second wagon (which will be first) is an engine. If it is one,
 				 * promote it as a new train, retaining the unitnumber, orders */
@@ -1633,7 +1625,7 @@ CommandCost CmdReverseTrainDirection(TileIndex tile, uint32 flags, uint32 p1, ui
 			return_cmd_error(STR_ONLY_TURN_SINGLE_UNIT);
 		}
 
-		Vehicle *front = GetFirstVehicleInChain(v);
+		Vehicle *front = v->First();
 		/* make sure the vehicle is stopped in the depot */
 		if (CheckTrainStoppedInDepot(front) < 0) {
 			return_cmd_error(STR_881A_TRAINS_CAN_ONLY_BE_ALTERED);
@@ -1777,7 +1769,7 @@ CommandCost CmdRefitRailVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32
 	_returned_refit_capacity = num;
 
 	/* Update the train's cached variables */
-	if (flags & DC_EXEC) TrainConsistChanged(GetFirstVehicleInChain(GetVehicle(p1)));
+	if (flags & DC_EXEC) TrainConsistChanged(GetVehicle(p1)->First());
 
 	return cost;
 }
@@ -2718,7 +2710,7 @@ static void *FindTrainCollideEnum(Vehicle *v, void *data)
 			myabs(v->x_pos - tcc->v->x_pos) < 6 &&
 			myabs(v->y_pos - tcc->v->y_pos) < 6 ) {
 
-		Vehicle *coll = GetFirstVehicleInChain(v);
+		Vehicle *coll = v->First();
 
 		/* it can't collide with its own wagons */
 		if (tcc->v == coll ||
@@ -2807,7 +2799,7 @@ static void TrainController(Vehicle *v, bool update_image)
 	Vehicle *prev;
 
 	/* For every vehicle after and including the given vehicle */
-	for (prev = GetPrevVehicleInChain(v); v != NULL; prev = v, v = v->Next()) {
+	for (prev = v->Previous(); v != NULL; prev = v, v = v->Next()) {
 		DiagDirection enterdir = DIAGDIR_BEGIN;
 		bool update_signals = false;
 		BeginVehicleMove(v);
@@ -2945,7 +2937,7 @@ static void TrainController(Vehicle *v, bool update_image)
 					v->tile = gp.new_tile;
 
 					if (GetTileRailType(gp.new_tile) != GetTileRailType(gp.old_tile)) {
-						TrainPowerChanged(GetFirstVehicleInChain(v));
+						TrainPowerChanged(v->First());
 					}
 
 					v->u.rail.track = chosen_track;
diff --git a/src/vehicle.cpp b/src/vehicle.cpp
index 9a2afd4fe..24e80ff67 100644
--- a/src/vehicle.cpp
+++ b/src/vehicle.cpp
@@ -209,6 +209,9 @@ void AfterLoadVehicles()
 	Vehicle *v;
 
 	FOR_ALL_VEHICLES(v) {
+		/* Reinstate the previous pointer */
+		if (v->Next() != NULL) v->Next()->previous = v;
+
 		v->UpdateDeltaXY(v->direction);
 
 		v->fill_percent_te_id = INVALID_TE_ID;
@@ -220,6 +223,17 @@ void AfterLoadVehicles()
 	}
 
 	FOR_ALL_VEHICLES(v) {
+		/* Fill the first pointers */
+		if (v->Previous() == NULL) {
+			for (Vehicle *u = v; u != NULL; u = u->Next()) {
+				u->first = v;
+			}
+		}
+	}
+
+	FOR_ALL_VEHICLES(v) {
+		assert(v->first != NULL);
+
 		if (v->type == VEH_TRAIN && (IsFrontEngine(v) || IsFreeWagon(v))) {
 			TrainConsistChanged(v);
 		} else if (v->type == VEH_ROAD && IsRoadVehFront(v)) {
@@ -269,6 +283,7 @@ Vehicle::Vehicle()
 	this->left_coord         = INVALID_COORD;
 	this->group_id           = DEFAULT_GROUP;
 	this->fill_percent_te_id = INVALID_TE_ID;
+	this->first              = this;
 }
 
 /**
@@ -466,78 +481,6 @@ Vehicle *GetLastVehicleInChain(Vehicle *v)
 	return v;
 }
 
-/** Finds the previous vehicle in a chain, by a brute force search.
- * This old function is REALLY slow because it searches through all vehicles to
- * find the previous vehicle, but if v->first has not been set, then this function
- * will need to be used to find the previous one. This function should never be
- * called by anything but GetFirstVehicleInChain
- */
-static Vehicle *GetPrevVehicleInChain_bruteforce(const Vehicle *v)
-{
-	Vehicle *u;
-
-	FOR_ALL_VEHICLES(u) if (u->type == v->type && u->Next() == v) return u;
-
-	return NULL;
-}
-
-/** Find the previous vehicle in a chain, by using the v->first cache.
- * While this function is fast, it cannot be used in the GetFirstVehicleInChain
- * function, otherwise you'll end up in an infinite loop call
- */
-Vehicle *GetPrevVehicleInChain(const Vehicle *v)
-{
-	Vehicle *u;
-	assert(v != NULL);
-
-	u = GetFirstVehicleInChain(v);
-
-	/* Check to see if this is the first */
-	if (v == u) return NULL;
-
-	for (; u->Next() != v; u = u->Next()) assert(u->Next() != NULL);
-
-	return u;
-}
-
-/** Finds the first vehicle in a chain.
- * This function reads out the v->first cache. Should the cache be dirty,
- * it determines the first vehicle in a chain, and updates the cache.
- */
-Vehicle *GetFirstVehicleInChain(const Vehicle *v)
-{
-	Vehicle* u;
-
-	assert(v != NULL);
-	assert(v->type == VEH_TRAIN || v->type == VEH_ROAD);
-
-	if (v->first != NULL) {
-		if (v->type == VEH_TRAIN) {
-			if (IsFrontEngine(v->first) || IsFreeWagon(v->first)) return v->first;
-		} else {
-			if (IsRoadVehFront(v->first)) return v->first;
-		}
-
-		DEBUG(misc, 0, "v->first cache faulty. We shouldn't be here, rebuilding cache!");
-	}
-
-	/* It is the fact (currently) that newly built vehicles do not have
-	 * their ->first pointer set. When this is the case, go up to the
-	 * first engine and set the pointers correctly. Also the first pointer
-	 * is not saved in a savegame, so this has to be fixed up after loading */
-
-	/* Find the 'locomotive' or the first wagon in a chain */
-	while ((u = GetPrevVehicleInChain_bruteforce(v)) != NULL) v = u;
-
-	/* Set the first pointer of all vehicles in that chain to the first wagon */
-	if ((v->type == VEH_TRAIN && (IsFrontEngine(v) || IsFreeWagon(v))) ||
-			(v->type == VEH_ROAD && IsRoadVehFront(v))) {
-		for (u = (Vehicle *)v; u != NULL; u = u->Next()) u->first = (Vehicle *)v;
-	}
-
-	return (Vehicle*)v;
-}
-
 uint CountVehiclesInChain(const Vehicle* v)
 {
 	uint count = 0;
@@ -2179,14 +2122,14 @@ void VehicleEnterDepot(Vehicle *v)
 	switch (v->type) {
 		case VEH_TRAIN:
 			InvalidateWindowClasses(WC_TRAINS_LIST);
-			if (!IsFrontEngine(v)) v = GetFirstVehicleInChain(v);
+			if (!IsFrontEngine(v)) v = v->First();
 			UpdateSignalsOnSegment(v->tile, GetRailDepotDirection(v->tile));
 			v->load_unload_time_rem = 0;
 			break;
 
 		case VEH_ROAD:
 			InvalidateWindowClasses(WC_ROADVEH_LIST);
-			if (!IsRoadVehFront(v)) v = GetFirstVehicleInChain(v);
+			if (!IsRoadVehFront(v)) v = v->First();
 			break;
 
 		case VEH_SHIP:
@@ -3168,6 +3111,28 @@ void Vehicle::HandleLoading(bool mode)
 	InvalidateVehicleOrder(this);
 }
 
+void Vehicle::SetNext(Vehicle *next)
+{
+	if (this->next != NULL) {
+		/* We had an old next vehicle. Update the first and previous pointers */
+		for (Vehicle *v = this->next; v != NULL; v = v->Next()) {
+			v->first = this->next;
+		}
+		this->next->previous = NULL;
+	}
+
+	this->next = next;
+
+	if (this->next != NULL) {
+		/* A new next vehicle. Update the first and previous pointers */
+		if (this->next->previous != NULL) this->next->previous->next = NULL;
+		this->next->previous = this;
+		for (Vehicle *v = this->next; v != NULL; v = v->Next()) {
+			v->first = this->first;
+		}
+	}
+}
+
 void SpecialVehicle::UpdateDeltaXY(Direction direction)
 {
 	this->x_offs        = 0;
diff --git a/src/vehicle.h b/src/vehicle.h
index ea75423c1..1526c5c9f 100644
--- a/src/vehicle.h
+++ b/src/vehicle.h
@@ -219,7 +219,8 @@ struct Vehicle;
 DECLARE_OLD_POOL(Vehicle, Vehicle, 9, 125)
 
 struct SaveLoad;
-extern const SaveLoad *GetVehicleDescription(VehicleType vt);
+const SaveLoad *GetVehicleDescription(VehicleType vt);
+void AfterLoadVehicles();
 
 struct Vehicle : PoolItem<Vehicle, VehicleID, &_Vehicle_pool> {
 	VehicleTypeByte type;    ///< Type of vehicle
@@ -227,10 +228,12 @@ struct Vehicle : PoolItem<Vehicle, VehicleID, &_Vehicle_pool> {
 
 private:
 	Vehicle *next;           // pointer to the next vehicle in the chain
+	Vehicle *previous;       // NOSAVE: pointer to the previous vehicle in the chain
+	Vehicle *first;          // NOSAVE: pointer to the first vehicle in the chain
 public:
 	friend const SaveLoad *GetVehicleDescription(VehicleType vt); // So we can use private/protected variables in the saveload code
+	friend void AfterLoadVehicles();
 
-	Vehicle *first;          // NOSAVE: pointer to the first vehicle in the chain
 	Vehicle *depot_list;     // NOSAVE: linked list to tell what vehicles entered a depot during the last tick. Used by autoreplace
 
 	StringID string_id;      // Displayed string
@@ -472,7 +475,7 @@ public:
 	 * Set the next vehicle of this vehicle.
 	 * @param next the next vehicle. NULL removes the next vehicle.
 	 */
-	void SetNext(Vehicle *next) { this->next = next; }
+	void SetNext(Vehicle *next);
 
 	/**
 	 * Get the next vehicle of this vehicle.
@@ -480,6 +483,19 @@ public:
 	 * @return the next vehicle or NULL when there isn't a next vehicle.
 	 */
 	inline Vehicle *Next() const { return this->next; }
+
+	/**
+	 * Get the previous vehicle of this vehicle.
+	 * @note articulated parts are also counted as vehicles.
+	 * @return the previous vehicle or NULL when there isn't a previous vehicle.
+	 */
+	inline Vehicle *Previous() const { return this->previous; }
+
+	/**
+	 * Get the first vehicle of this vehicle chain.
+	 * @return the first vehicle of the chain.
+	 */
+	inline Vehicle *First() const { return this->first; }
 };
 
 /**
@@ -556,10 +572,7 @@ typedef void *VehicleFromPosProc(Vehicle *v, void *data);
 
 void VehicleServiceInDepot(Vehicle *v);
 void VehiclePositionChanged(Vehicle *v);
-void AfterLoadVehicles();
 Vehicle *GetLastVehicleInChain(Vehicle *v);
-Vehicle *GetPrevVehicleInChain(const Vehicle *v);
-Vehicle *GetFirstVehicleInChain(const Vehicle *v);
 uint CountVehiclesInChain(const Vehicle *v);
 bool IsEngineCountable(const Vehicle *v);
 void DeleteVehicleChain(Vehicle *v);
diff --git a/src/viewport.cpp b/src/viewport.cpp
index e7a432d36..50297c1c5 100644
--- a/src/viewport.cpp
+++ b/src/viewport.cpp
@@ -1786,13 +1786,13 @@ static void CheckClickOnLandscape(const ViewPort *vp, int x, int y)
 
 static void SafeShowTrainViewWindow(const Vehicle* v)
 {
-	if (!IsFrontEngine(v)) v = GetFirstVehicleInChain(v);
+	if (!IsFrontEngine(v)) v = v->First();
 	ShowVehicleViewWindow(v);
 }
 
 static void SafeShowRoadVehViewWindow(const Vehicle *v)
 {
-	if (!IsRoadVehFront(v)) v = GetFirstVehicleInChain(v);
+	if (!IsRoadVehFront(v)) v = v->First();
 	ShowVehicleViewWindow(v);
 }
 
diff --git a/src/water_cmd.cpp b/src/water_cmd.cpp
index a3e97c734..428cd5f4b 100644
--- a/src/water_cmd.cpp
+++ b/src/water_cmd.cpp
@@ -658,7 +658,7 @@ static void FloodVehicle(Vehicle *v)
 			}
 			Vehicle *u;
 
-			if (v->type != VEH_AIRCRAFT) v = GetFirstVehicleInChain(v);
+			if (v->type != VEH_AIRCRAFT) v = v->First();
 			u = v;
 
 			/* crash all wagons, and count passengers */