SCI32: Implement engine-accurate screen item list sorting

It seems highly probable that there are later SCI games that use
the "hi res" rendering path, so sorting and unsorting of
ScreenItemLists needs to be accurate.

2 files changed, 52 insertions, 16 deletions

diff --git a/engines/sci/graphics/screen_item32.cpp b/engines/sci/graphics/screen_item32.cpp
index d2673d40b3..c1644a5ea3 100644
--- a/engines/sci/graphics/screen_item32.cpp
+++ b/engines/sci/graphics/screen_item32.cpp
@@ -657,23 +657,43 @@ ScreenItem *ScreenItemList::findByObject(const reg_t object) const {
 	return *screenItemIt;
 }
 void ScreenItemList::sort() {
-	// TODO: SCI engine used _unsorted as an array of indexes into the
-	// list itself and then performed the same swap operations on the
-	// _unsorted array as the _storage array during sorting, but the
-	// only reason to do this would be if some of the pointers in the
-	// list were replaced so the pointer values themselves couldn’t
-	// simply be recorded and then restored later. It is not yet
-	// verified whether this simplification of the sort/unsort is
-	// safe.
+	if (size() < 2) {
+		return;
+	}
+
 	for (size_type i = 0; i < size(); ++i) {
-		_unsorted[i] = (*this)[i];
+		_unsorted[i] = i;
 	}
 
-	Common::sort(begin(), end(), sortHelper);
+	for (size_type i = size() - 1; i > 0; --i) {
+		bool swap = false;
+
+		for (size_type j = 0; j < i; ++j)  {
+			value_type &a = operator[](j);
+			value_type &b = operator[](j + 1);
+
+			if (a == nullptr || *a > *b) {
+				SWAP(a, b);
+				SWAP(_unsorted[j], _unsorted[j + 1]);
+				swap = true;
+			}
+		}
+
+		if (!swap) {
+			break;
+		}
+	}
 }
 void ScreenItemList::unsort() {
+	if (size() < 2) {
+		return;
+	}
+
 	for (size_type i = 0; i < size(); ++i) {
-		(*this)[i] = _unsorted[i];
+		while (_unsorted[i] != i) {
+			SWAP(operator[](_unsorted[i]), operator[](i));
+			SWAP(_unsorted[_unsorted[i]], _unsorted[i]);
+		}
 	}
 }
 
diff --git a/engines/sci/graphics/screen_item32.h b/engines/sci/graphics/screen_item32.h
index eef2f488a5..2e44e418ce 100644
--- a/engines/sci/graphics/screen_item32.h
+++ b/engines/sci/graphics/screen_item32.h
@@ -236,6 +236,24 @@ public:
 		return false;
 	}
 
+	inline bool operator>(const ScreenItem &other) const {
+		if (_priority > other._priority) {
+			return true;
+		}
+
+		if (_priority == other._priority) {
+			if (_position.y + _z > other._position.y + other._z) {
+				return true;
+			}
+
+			if (_position.y + _z == other._position.y + other._z) {
+				return _object > other._object;
+			}
+		}
+
+		return false;
+	}
+
 	/**
 	 * Calculates the dimensions and scaling parameters for
 	 * the screen item, using the given plane as the parent
@@ -279,12 +297,10 @@ public:
 
 typedef StablePointerArray<ScreenItem, 250> ScreenItemListBase;
 class ScreenItemList : public ScreenItemListBase {
-	inline static bool sortHelper(const ScreenItem *a, const ScreenItem *b) {
-		return *a < *b;
-	}
-public:
-	ScreenItem *_unsorted[250];
+private:
+	size_type _unsorted[250];
 
+public:
 	ScreenItem *findByObject(const reg_t object) const;
 	void sort();
 	void unsort();