From 705615fd914c51daacf4adb2aed9e21e6698e755 Mon Sep 17 00:00:00 2001
From: rubidium <rubidium@openttd.org>
Date: Wed, 7 Oct 2009 08:25:12 +0000
Subject: (svn r17735) -Codechange: update the cache one inserting/removing
 CargoPackets from the CargoList via Append/Truncate instead of rebuilding the
 whole cache. For Append this changes the O(n) cache rebuild into a O(1) cache
 update. For Truncate no temporary list is needed anymore (based on patch by
 fonsinchen)

---
 src/cargopacket.cpp | 66 +++++++++++++++++++++++++++++++++--------------------
 src/cargopacket.h   | 14 ++++++++++++
 2 files changed, 55 insertions(+), 25 deletions(-)

diff --git a/src/cargopacket.cpp b/src/cargopacket.cpp
index e5a636bb4..829ef588f 100644
--- a/src/cargopacket.cpp
+++ b/src/cargopacket.cpp
@@ -76,6 +76,20 @@ CargoList::~CargoList()
 	}
 }
 
+void CargoList::RemoveFromCache(const CargoPacket *cp)
+{
+	this->count                 -= cp->count;
+	this->feeder_share          -= cp->feeder_share;
+	this->cargo_days_in_transit -= cp->days_in_transit * cp->count;
+}
+
+void CargoList::AddToCache(const CargoPacket *cp)
+{
+	this->count                 += cp->count;
+	this->feeder_share          += cp->feeder_share;
+	this->cargo_days_in_transit += cp->days_in_transit * cp->count;
+}
+
 void CargoList::AgeCargo()
 {
 	for (List::const_iterator it = this->packets.begin(); it != this->packets.end(); it++) {
@@ -92,43 +106,47 @@ void CargoList::Append(CargoPacket *cp)
 	assert(cp != NULL);
 
 	for (List::iterator it = this->packets.begin(); it != this->packets.end(); it++) {
-		if ((*it)->SameSource(cp) && (*it)->count + cp->count <= CargoPacket::MAX_COUNT) {
-			(*it)->count        += cp->count;
-			(*it)->feeder_share += cp->feeder_share;
-			delete cp;
+		CargoPacket *icp = *it;
+		if (icp->SameSource(cp) && icp->count + cp->count <= CargoPacket::MAX_COUNT) {
+			icp->count        += cp->count;
+			icp->feeder_share += cp->feeder_share;
 
-			this->InvalidateCache();
+			this->AddToCache(cp);
+			delete cp;
 			return;
 		}
 	}
 
 	/* The packet could not be merged with another one */
 	this->packets.push_back(cp);
-	this->InvalidateCache();
+	this->AddToCache(cp);
 }
 
 
-void CargoList::Truncate(uint count)
+void CargoList::Truncate(uint max_remaining)
 {
-	for (List::iterator it = this->packets.begin(); it != this->packets.end(); it++) {
-		uint local_count = (*it)->count;
-		if (local_count <= count) {
-			count -= local_count;
+	for (List::iterator it = packets.begin(); it != packets.end(); /* done during loop*/) {
+		CargoPacket *cp = *it;
+		if (max_remaining == 0) {
+			/* Nothing should remain, just remove the packets. */
+			packets.erase(it++);
+			this->RemoveFromCache(cp);
+			delete cp;
 			continue;
 		}
 
-		(*it)->count = count;
-		count = 0;
-	}
-
-	while (!this->packets.empty()) {
-		CargoPacket *cp = this->packets.back();
-		if (cp->count != 0) break;
-		delete cp;
-		this->packets.pop_back();
+		uint local_count = cp->count;
+		if (local_count > max_remaining) {
+			uint diff = local_count - max_remaining;
+			this->count -= diff;
+			this->cargo_days_in_transit -= cp->days_in_transit * diff;
+			cp->count = max_remaining;
+			max_remaining = 0;
+		} else {
+			max_remaining -= local_count;
+		}
+		++it;
 	}
-
-	this->InvalidateCache();
 }
 
 bool CargoList::MoveTo(CargoList *dest, uint count, CargoList::MoveToAction mta, CargoPayment *payment, uint data)
@@ -218,8 +236,6 @@ void CargoList::InvalidateCache()
 	this->cargo_days_in_transit = 0;
 
 	for (List::const_iterator it = this->packets.begin(); it != this->packets.end(); it++) {
-		this->count                 += (*it)->count;
-		this->cargo_days_in_transit += (*it)->days_in_transit * (*it)->count;
-		this->feeder_share          += (*it)->feeder_share;
+		this->AddToCache(*it);
 	}
 }
diff --git a/src/cargopacket.h b/src/cargopacket.h
index bbad42bff..9d8251550 100644
--- a/src/cargopacket.h
+++ b/src/cargopacket.h
@@ -169,6 +169,20 @@ private:
 
 	List packets;               ///< The cargo packets in this list
 
+	/**
+	 * Update the cache to reflect adding of this packet.
+	 * Increases count, feeder share and days_in_transit
+	 * @param cp a new packet to be inserted
+	 */
+	void AddToCache(const CargoPacket *cp);
+
+	/**
+	 * Update the cached values to reflect the removal of this packet.
+	 * Decreases count, feeder share and days_in_transit
+	 * @param cp Packet to be removed from cache
+	 */
+	void RemoveFromCache(const CargoPacket *cp);
+
 public:
 	/** The stations, via GoodsEntry, have a CargoList. */
 	friend const struct SaveLoad *GetGoodsDesc();
-- 
cgit v1.2.3-54-g00ecf