# HG changeset patch
# User frosch <frosch@openttd.org>
# Date 2018-03-11 13:21:27
# Node ID 59be1e5ea50d82d157b82f5e2b036ef660ed25dc
# Parent  8ffd1846f871f82554abcd65dba089e0fadcee0f

(svn r27985) -Codechange: Convert VA2 switches into ones with non-overlapping ranges, sort them and resolve them using binary search. Speedup sprite resolving by about 7 percent.

diff --git a/src/newgrf.cpp b/src/newgrf.cpp
--- a/src/newgrf.cpp
+++ b/src/newgrf.cpp
@@ -12,6 +12,7 @@
 #include "stdafx.h"
 
 #include <stdarg.h>
+#include <algorithm>
 
 #include "debug.h"
 #include "fileio_func.h"
@@ -4687,16 +4688,60 @@ static void NewSpriteGroup(ByteReader *b
 			group->adjusts = MallocT<DeterministicSpriteGroupAdjust>(group->num_adjusts);
 			MemCpyT(group->adjusts, adjusts.Begin(), group->num_adjusts);
 
-			group->num_ranges = buf->ReadByte();
-			if (group->num_ranges > 0) group->ranges = CallocT<DeterministicSpriteGroupRange>(group->num_ranges);
-
-			for (uint i = 0; i < group->num_ranges; i++) {
-				group->ranges[i].group = GetGroupFromGroupID(setid, type, buf->ReadWord());
-				group->ranges[i].low   = buf->ReadVarSize(varsize);
-				group->ranges[i].high  = buf->ReadVarSize(varsize);
+			std::vector<DeterministicSpriteGroupRange> ranges;
+			ranges.resize(buf->ReadByte());
+			for (uint i = 0; i < ranges.size(); i++) {
+				ranges[i].group = GetGroupFromGroupID(setid, type, buf->ReadWord());
+				ranges[i].low   = buf->ReadVarSize(varsize);
+				ranges[i].high  = buf->ReadVarSize(varsize);
 			}
 
 			group->default_group = GetGroupFromGroupID(setid, type, buf->ReadWord());
+			group->error_group = ranges.size() > 0 ? ranges[0].group : group->default_group;
+
+			/* Sort ranges ascending. When ranges overlap, this may required clamping or splitting them */
+			std::vector<uint32> bounds;
+			for (uint i = 0; i < ranges.size(); i++) {
+				bounds.push_back(ranges[i].low);
+				if (ranges[i].high != UINT32_MAX) bounds.push_back(ranges[i].high + 1);
+			}
+			std::sort(bounds.begin(), bounds.end());
+			bounds.erase(std::unique(bounds.begin(), bounds.end()), bounds.end());
+
+			std::vector<const SpriteGroup *> target;
+			for (uint j = 0; j < bounds.size(); ++j) {
+				uint32 v = bounds[j];
+				const SpriteGroup *t = NULL;
+				for (uint i = 0; i < ranges.size(); i++) {
+					if (ranges[i].low <= v && v <= ranges[i].high) {
+						t = ranges[i].group;
+					}
+				}
+				target.push_back(t);
+			}
+			assert(target.size() == bounds.size());
+
+			std::vector<DeterministicSpriteGroupRange> optimised;
+			for (uint j = 0; j < bounds.size(); ) {
+				if (target[j]) {
+					DeterministicSpriteGroupRange r;
+					r.group = target[j];
+					r.low = bounds[j];
+					while (j < bounds.size() && target[j] == r.group) {
+						j++;
+					}
+					r.high = j < bounds.size() ? bounds[j] - 1 : UINT32_MAX;
+					optimised.push_back(r);
+				} else {
+					j++;
+				}
+			}
+
+			group->num_ranges = optimised.size();
+			if (group->num_ranges > 0) {
+				group->ranges = MallocT<DeterministicSpriteGroupRange>(group->num_ranges);
+				MemCpyT(group->ranges, &optimised.front(), group->num_ranges);
+			}
 			break;
 		}
 
diff --git a/src/newgrf_spritegroup.cpp b/src/newgrf_spritegroup.cpp
--- a/src/newgrf_spritegroup.cpp
+++ b/src/newgrf_spritegroup.cpp
@@ -10,6 +10,7 @@
 /** @file newgrf_spritegroup.cpp Handling of primarily NewGRF action 2. */
 
 #include "stdafx.h"
+#include <algorithm>
 #include "debug.h"
 #include "newgrf_spritegroup.h"
 #include "core/pool_func.hpp"
@@ -201,6 +202,11 @@ static U EvalAdjustT(const Deterministic
 }
 
 
+static bool RangeHighComparator(const DeterministicSpriteGroupRange& range, uint32 value)
+{
+	return range.high < value;
+}
+
 const SpriteGroup *DeterministicSpriteGroup::Resolve(ResolverObject &object) const
 {
 	uint32 last_value = 0;
@@ -232,7 +238,7 @@ const SpriteGroup *DeterministicSpriteGr
 		if (!available) {
 			/* Unsupported variable: skip further processing and return either
 			 * the group from the first range or the default group. */
-			return SpriteGroup::Resolve(this->num_ranges > 0 ? this->ranges[0].group : this->default_group, object, false);
+			return SpriteGroup::Resolve(this->error_group, object, false);
 		}
 
 		switch (this->size) {
@@ -254,9 +260,17 @@ const SpriteGroup *DeterministicSpriteGr
 		return &nvarzero;
 	}
 
-	for (i = 0; i < this->num_ranges; i++) {
-		if (this->ranges[i].low <= value && value <= this->ranges[i].high) {
-			return SpriteGroup::Resolve(this->ranges[i].group, object, false);
+	if (this->num_ranges > 4) {
+		DeterministicSpriteGroupRange *lower = std::lower_bound(this->ranges + 0, this->ranges + this->num_ranges, value, RangeHighComparator);
+		if (lower != this->ranges + this->num_ranges && lower->low <= value) {
+			assert(lower->low <= value && value <= lower->high);
+			return SpriteGroup::Resolve(lower->group, object, false);
+		}
+	} else {
+		for (i = 0; i < this->num_ranges; i++) {
+			if (this->ranges[i].low <= value && value <= this->ranges[i].high) {
+				return SpriteGroup::Resolve(this->ranges[i].group, object, false);
+			}
 		}
 	}
 
diff --git a/src/newgrf_spritegroup.h b/src/newgrf_spritegroup.h
--- a/src/newgrf_spritegroup.h
+++ b/src/newgrf_spritegroup.h
@@ -181,6 +181,8 @@ struct DeterministicSpriteGroup : Sprite
 	/* Dynamically allocated, this is the sole owner */
 	const SpriteGroup *default_group;
 
+	const SpriteGroup *error_group; // was first range, before sorting ranges
+
 protected:
 	const SpriteGroup *Resolve(ResolverObject &object) const;
 };