1 files changed, 148 insertions, 0 deletions
diff --git a/engines/glk/archetype/heap_sort.cpp b/engines/glk/archetype/heap_sort.cpp
new file mode 100644
index 0000000000..98753ccc70
--- /dev/null
+++ b/engines/glk/archetype/heap_sort.cpp
@@ -0,0 +1,148 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ */
+
+#include "glk/archetype/heap_sort.h"
+#include "glk/archetype/archetype.h"
+#include "glk/archetype/misc.h"
+
+namespace Glk {
+namespace Archetype {
+
+const char *const CANT_PEEK = "Internal error:  cannot peek into heap";
+const char *const CANT_POKE = "Internal error:  cannot poke into heap";
+
+HeapType H;
+
+void heap_sort_init() {
+	new_xarray(H);
+}
+
+static bool lighter(const Element one, const Element two) {
+	return *static_cast<StringPtr>(one) < *static_cast<StringPtr>(two);
+}
+
+static void heapup() {
+	int L, parent;
+	Element Lp, parentp = nullptr;
+	Element temp;
+
+	L = H.size();
+	while (L > 0) {
+		if ((L % 2) == 0)
+			parent = L / 2;
+		else
+			parent = (L - 1) / 2;
+	
+		if (!(access_xarray(H, L, Lp, PEEK_ACCESS) && access_xarray(H, parent, parentp, PEEK_ACCESS)))
+			g_vm->writeln(CANT_PEEK);
+		
+		if (lighter(Lp, parentp)) {
+			temp = parentp;
+			if (!(access_xarray(H, parent, Lp, POKE_ACCESS) && access_xarray(H, L, temp, POKE_ACCESS)))
+				g_vm->writeln(CANT_POKE);
+			L = parent;
+		} else {
+			L = 0;
+		}
+	}
+}
+
+static void heapdown() {
+	uint L, compare, lc, rc;
+	Element lp;
+	Element lcp, rcp;
+	Element comparep;
+	Element temp;
+
+	L = 0;
+	while (L < H.size()) {
+		lc = L * 2;
+		if (lc >= H.size()) {
+			L = lc;
+		} else {
+			rc = lc + 1;
+			if (!access_xarray(H, lc, lcp, PEEK_ACCESS))
+				g_vm->writeln(CANT_PEEK);
+			
+			if (rc >= H.size()) {
+				compare = lc;
+				comparep = lcp;
+			} else {
+				if (!access_xarray(H, rc, rcp, PEEK_ACCESS))
+					g_vm->writeln(CANT_PEEK);
+				if (lighter(lcp, rcp)) {
+					compare = lc;
+					comparep = lcp;
+				} else {
+					compare = rc;
+					comparep = rcp;
+				}
+			}
+			
+			if (!access_xarray(H, L, lp, PEEK_ACCESS))
+				g_vm->writeln(CANT_PEEK);
+			if (!lighter(comparep, lp)) {
+				temp = comparep;
+				if (!(access_xarray(H, compare, lp, POKE_ACCESS) && access_xarray(H, L, temp, POKE_ACCESS)))
+					g_vm->writeln(CANT_POKE);
+				L = compare;
+			} else {
+				L = H.size();
+			}
+		}
+	}
+}
+
+bool pop_heap(Element &e) {
+	Element temp;
+
+	if (H.empty()) {
+		return false;
+	} else {
+		if (!(access_xarray(H, 0, e, PEEK_ACCESS) && access_xarray(H, H.size() - 1, temp, PEEK_ACCESS)
+				&&  access_xarray(H, 0, temp, POKE_ACCESS)))
+			g_vm->writeln(CANT_PEEK);
+		
+		shrink_xarray(H);
+		heapdown();
+		return true;
+	}
+}
+
+void drop_on_heap(Element e) {
+	append_to_xarray(H, e);
+	heapup();
+}
+
+void drop_str_on_heap(const String &s) {
+	StringPtr sp = NewDynStr(s);
+	void *p = (void *)sp;
+	drop_on_heap(p);
+}
+
+void reinit_heap() {
+	dispose_xarray(H);
+	new_xarray(H);
+}
+
+} // End of namespace Archetype
+} // End of namespace Glk