# HG changeset patch
# User rubidium <rubidium@openttd.org>
# Date 2007-08-30 21:11:12
# Node ID 84fb92567fc7f220231f8913b6624b7c187217ff
# Parent  599894acf9bcc677994c4b53f0404b7228cc8d4f

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

diff --git a/src/autoreplace_cmd.cpp b/src/autoreplace_cmd.cpp
--- a/src/autoreplace_cmd.cpp
+++ b/src/autoreplace_cmd.cpp
@@ -52,7 +52,7 @@ static void MoveVehicleCargo(Vehicle *de
 	 * 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 VerifyAutoreplaceRefitForOrd
 	const Vehicle *u;
 
 	if (v->type == VEH_TRAIN) {
-		u = GetFirstVehicleInChain(v);
+		u = v->First();
 	} else {
 		u = v;
 	}
@@ -104,7 +104,7 @@ static CargoID GetNewCargoTypeForReplace
 
 	/* 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(Vehicl
 			 * 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(Vehicl
 			}
 		}
 		/* 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
--- a/src/depot_gui.cpp
+++ b/src/depot_gui.cpp
@@ -359,7 +359,7 @@ static int GetVehicleFromDepotWndPt(cons
 			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(Vehicl
 	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 Ve
 	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
--- a/src/newgrf_engine.cpp
+++ b/src/newgrf_engine.cpp
@@ -516,7 +516,7 @@ static uint32 VehicleGetVariable(const R
 				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 R
 			 */
 			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 R
 				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 *VehicleResolve
 	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(Re
 	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,
 			 * 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
--- a/src/order_gui.cpp
+++ b/src/order_gui.cpp
@@ -356,7 +356,7 @@ static bool HandleOrderVehClick(const Ve
 	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
--- 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 ti
 		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(Vehic
 		!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
--- 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(Eng
 			_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(Eng
 
 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 AddRearEngineToMultiheadedTr
 	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 *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
  */
 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
 	}
 
 	/* 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
 
 	/* 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
 			}
 			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 t
 
 	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 t
 			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(Til
 			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(TileInde
 	_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(Vehicl
 			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, 
 	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, 
 					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
--- 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 *
 	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
--- 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, Vehic
 
 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
 
 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
--- a/src/viewport.cpp
+++ b/src/viewport.cpp
@@ -1786,13 +1786,13 @@ static void CheckClickOnLandscape(const 
 
 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
--- 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 */