Add: [Script] Native priority queue; useful e.g. for pathfinders.

9 files changed, 306 insertions, 0 deletions

diff --git a/src/script/api/ai/ai_priorityqueue.hpp.sq b/src/script/api/ai/ai_priorityqueue.hpp.sq
new file mode 100644
index 000000000..6e5fcf82e
--- /dev/null
+++ b/src/script/api/ai/ai_priorityqueue.hpp.sq
@@ -0,0 +1,31 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD 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, version 2.
+ * OpenTTD 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 OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* THIS FILE IS AUTO-GENERATED; PLEASE DO NOT ALTER MANUALLY */
+
+#include "../script_priorityqueue.hpp"
+#include "../template/template_priorityqueue.hpp.sq"
+
+
+template <> const char *GetClassName<ScriptPriorityQueue, ST_AI>() { return "AIPriorityQueue"; }
+
+void SQAIPriorityQueue_Register(Squirrel *engine)
+{
+	DefSQClass<ScriptPriorityQueue, ST_AI> SQAIPriorityQueue("AIPriorityQueue");
+	SQAIPriorityQueue.PreRegister(engine);
+	SQAIPriorityQueue.AddConstructor<void (ScriptPriorityQueue::*)(), 1>(engine, "x");
+
+	SQAIPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Insert, "Insert");
+	SQAIPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Pop, "Pop");
+	SQAIPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Peek, "Peek");
+	SQAIPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Exists, "Exists");
+	SQAIPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Clear, "Clear");
+	SQAIPriorityQueue.DefSQMethod(engine, &ScriptPriorityQueue::IsEmpty, "IsEmpty", 1, "x");
+	SQAIPriorityQueue.DefSQMethod(engine, &ScriptPriorityQueue::Count,   "Count",   1, "x");
+
+	SQAIPriorityQueue.PostRegister(engine);
+}
diff --git a/src/script/api/ai_changelog.hpp b/src/script/api/ai_changelog.hpp
index bcb7df67f..a579bb27b 100644
--- a/src/script/api/ai_changelog.hpp
+++ b/src/script/api/ai_changelog.hpp
@@ -17,6 +17,9 @@
  *
  * This version is not yet released. The following changes are not set in stone yet.
  *
+ * API additions:
+ * \li AIPriorityQueue
+ *
  * \b 1.10.0
  *
  * API additions:
diff --git a/src/script/api/game/game_priorityqueue.hpp.sq b/src/script/api/game/game_priorityqueue.hpp.sq
new file mode 100644
index 000000000..fade5e2a1
--- /dev/null
+++ b/src/script/api/game/game_priorityqueue.hpp.sq
@@ -0,0 +1,31 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD 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, version 2.
+ * OpenTTD 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 OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* THIS FILE IS AUTO-GENERATED; PLEASE DO NOT ALTER MANUALLY */
+
+#include "../script_priorityqueue.hpp"
+#include "../template/template_priorityqueue.hpp.sq"
+
+
+template <> const char *GetClassName<ScriptPriorityQueue, ST_GS>() { return "GSPriorityQueue"; }
+
+void SQGSPriorityQueue_Register(Squirrel *engine)
+{
+	DefSQClass<ScriptPriorityQueue, ST_GS> SQGSPriorityQueue("GSPriorityQueue");
+	SQGSPriorityQueue.PreRegister(engine);
+	SQGSPriorityQueue.AddConstructor<void (ScriptPriorityQueue::*)(), 1>(engine, "x");
+
+	SQGSPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Insert, "Insert");
+	SQGSPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Pop, "Pop");
+	SQGSPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Peek, "Peek");
+	SQGSPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Exists, "Exists");
+	SQGSPriorityQueue.DefSQAdvancedMethod(engine, &ScriptPriorityQueue::Clear, "Clear");
+	SQGSPriorityQueue.DefSQMethod(engine, &ScriptPriorityQueue::IsEmpty, "IsEmpty", 1, "x");
+	SQGSPriorityQueue.DefSQMethod(engine, &ScriptPriorityQueue::Count,   "Count",   1, "x");
+
+	SQGSPriorityQueue.PostRegister(engine);
+}
diff --git a/src/script/api/game_changelog.hpp b/src/script/api/game_changelog.hpp
index 69c4d971a..fc917a012 100644
--- a/src/script/api/game_changelog.hpp
+++ b/src/script/api/game_changelog.hpp
@@ -24,6 +24,7 @@
  * \li GSStoryPage::MakePushButtonReference
  * \li GSStoryPage::MakeTileButtonReference
  * \li GSStoryPage::MakeVehicleButtonReference
+ * \li GSPriorityQueue
  *
  * \b 1.10.0
  *
diff --git a/src/script/api/script_priorityqueue.cpp b/src/script/api/script_priorityqueue.cpp
new file mode 100644
index 000000000..313008412
--- /dev/null
+++ b/src/script/api/script_priorityqueue.cpp
@@ -0,0 +1,107 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD 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, version 2.
+ * OpenTTD 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 OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file script_priorityqueue.cpp Implementation of ScriptPriorityQueue. */
+
+#include "../../stdafx.h"
+#include "script_priorityqueue.hpp"
+#include "script_error.hpp"
+#include "../squirrel_helper.hpp"
+#include "../script_instance.hpp"
+#include "../../debug.h"
+#include <algorithm>
+
+#include "../../safeguards.h"
+
+
+static bool operator==(const ScriptPriorityQueue::PriorityItem &lhs, const HSQOBJECT &rhs)
+{
+	return lhs.second._type == rhs._type && lhs.second._unVal.raw == rhs._unVal.raw;
+}
+
+
+ScriptPriorityQueue::~ScriptPriorityQueue()
+{
+	/* Release reference to stored objects. */
+	auto inst = ScriptObject::GetActiveInstance();
+	if (!inst->InShutdown()) {
+		for (auto &i : this->queue) inst->ReleaseSQObject(const_cast<HSQOBJECT *>(&i.second));
+	}
+}
+
+SQInteger ScriptPriorityQueue::Insert(HSQUIRRELVM vm)
+{
+	HSQOBJECT item;
+	int64 priority;
+	sq_resetobject(&item);
+	sq_getstackobj(vm, 2, &item);
+	sq_getinteger(vm, 3, &priority);
+
+	sq_addref(vm, &item); // Keep object alive.
+
+	this->queue.emplace_back(priority, item);
+	std::push_heap(this->queue.begin(), this->queue.end(), this->comp);
+
+	return SQConvert::Return(vm, true);
+}
+
+SQInteger ScriptPriorityQueue::Pop(HSQUIRRELVM vm)
+{
+	if (this->IsEmpty()) {
+		ScriptObject::SetLastError(ScriptError::ERR_PRECONDITION_FAILED);
+		sq_pushnull(vm);
+		return 1;
+	}
+
+	HSQOBJECT item = this->queue.front().second;
+	std::pop_heap(this->queue.begin(), this->queue.end(), this->comp);
+	this->queue.pop_back();
+
+	/* Store the object on the Squirrel stack before releasing it to make sure the ref count can't drop to zero. */
+	auto ret = SQConvert::Return(vm, item);
+	sq_release(vm, &item);
+	return ret;
+}
+
+SQInteger ScriptPriorityQueue::Peek(HSQUIRRELVM vm)
+{
+	if (this->IsEmpty()) {
+		ScriptObject::SetLastError(ScriptError::ERR_PRECONDITION_FAILED);
+		sq_pushnull(vm);
+		return 1;
+	}
+
+	return SQConvert::Return(vm, this->queue.front().second);
+}
+
+SQInteger ScriptPriorityQueue::Exists(HSQUIRRELVM vm)
+{
+	HSQOBJECT item;
+	sq_resetobject(&item);
+	sq_getstackobj(vm, 2, &item);
+
+	return SQConvert::Return(vm, std::find(this->queue.cbegin(), this->queue.cend(), item) != this->queue.cend());
+}
+
+SQInteger ScriptPriorityQueue::Clear(HSQUIRRELVM vm)
+{
+	/* Release reference to stored objects. */
+	for (auto &i : this->queue) sq_release(vm, const_cast<HSQOBJECT *>(&i.second));
+	this->queue.clear();
+
+	return 0;
+}
+
+bool ScriptPriorityQueue::IsEmpty()
+{
+	return this->queue.empty();
+}
+
+SQInteger ScriptPriorityQueue::Count()
+{
+	return (SQInteger)this->queue.size();
+}
diff --git a/src/script/api/script_priorityqueue.hpp b/src/script/api/script_priorityqueue.hpp
new file mode 100644
index 000000000..5f8718e42
--- /dev/null
+++ b/src/script/api/script_priorityqueue.hpp
@@ -0,0 +1,94 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD 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, version 2.
+ * OpenTTD 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 OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file script_priorityqueue.hpp A queue that keeps a list of items sorted by a priority. */
+/** @defgroup ScriptPriorityQueue Classes that create a priority queue of items. */
+
+#ifndef SCRIPT_PRIORITYQUEUE_HPP
+#define SCRIPT_PRIORITYQUEUE_HPP
+
+#include "script_object.hpp"
+#include <utility>
+#include <vector>
+
+/**
+ * Class that creates a queue which keeps its items ordered by an item priority.
+ * @api ai game
+ */
+class ScriptPriorityQueue : public ScriptObject {
+public:
+	typedef std::pair<int64, HSQOBJECT> PriorityItem;
+private:
+	struct PriorityComparator {
+		bool operator()(const PriorityItem &lhs, const PriorityItem &rhs) const noexcept
+		{
+			return lhs.first > rhs.first;
+		}
+	};
+
+	PriorityComparator        comp;
+	std::vector<PriorityItem> queue;  ///< The priority list
+
+public:
+	~ScriptPriorityQueue();
+
+#ifdef DOXYGEN_API
+	/**
+	 * Add a single item to the queue.
+	 * @param item The item to add. Can be any Squirrel type. Should be unique, otherwise it is ignored.
+	 * @param priority The priority to assign the item.
+	 * @return True if the item was inserted, false if it was already in the queue.
+	 */
+	bool Insert(void *item, int64 priority);
+
+	/**
+	 * Remove and return the item with the lowest priority.
+	 * @return The item with the lowest priority, removed from the queue. Returns null on an empty queue.
+	 * @pre !IsEmpty()
+	 */
+	void *Pop();
+
+	/**
+	 * Get the item with the lowest priority, keeping it in the queue.
+	 * @return The item with the lowest priority. Returns null on an empty queue.
+	 * @pre !IsEmpty()
+	 */
+	void *Peek();
+
+	/**
+	 * Check if an items is already included in the queue.
+	 * @return true if the items is already in the queue.
+	 * @note Performance is O(n), use only when absolutely required.
+	 */
+	bool Exists(void *item);
+
+	/**
+	 * Clear the queue, making Count() returning 0 and IsEmpty() returning true.
+	 */
+	void Clear();
+#else
+	SQInteger Insert(HSQUIRRELVM vm);
+	SQInteger Pop(HSQUIRRELVM vm);
+	SQInteger Peek(HSQUIRRELVM vm);
+	SQInteger Exists(HSQUIRRELVM vm);
+	SQInteger Clear(HSQUIRRELVM vm);
+#endif
+
+	/**
+	 * Check if the queue is empty.
+	 * @return true if the queue is empty.
+	 */
+	bool IsEmpty();
+
+	/**
+	 * Returns the amount of items in the queue.
+	 * @return amount of items in the queue.
+	 */
+	SQInteger Count();
+};
+
+#endif /* SCRIPT_PRIORITYQUEUE_HPP */
diff --git a/src/script/api/template/template_priorityqueue.hpp.sq b/src/script/api/template/template_priorityqueue.hpp.sq
new file mode 100644
index 000000000..14c63324f
--- /dev/null
+++ b/src/script/api/template/template_priorityqueue.hpp.sq
@@ -0,0 +1,19 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD 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, version 2.
+ * OpenTTD 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 OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* THIS FILE IS AUTO-GENERATED; PLEASE DO NOT ALTER MANUALLY */
+
+#include "../script_priorityqueue.hpp"
+
+namespace SQConvert {
+	/* Allow ScriptPriorityQueue to be used as Squirrel parameter */
+	template <> inline ScriptPriorityQueue *GetParam(ForceType<ScriptPriorityQueue *>, HSQUIRRELVM vm, int index, SQAutoFreePointers *ptr) { SQUserPointer instance; sq_getinstanceup(vm, index, &instance, 0); return  (ScriptPriorityQueue *)instance; }
+	template <> inline ScriptPriorityQueue &GetParam(ForceType<ScriptPriorityQueue &>, HSQUIRRELVM vm, int index, SQAutoFreePointers *ptr) { SQUserPointer instance; sq_getinstanceup(vm, index, &instance, 0); return *(ScriptPriorityQueue *)instance; }
+	template <> inline const ScriptPriorityQueue *GetParam(ForceType<const ScriptPriorityQueue *>, HSQUIRRELVM vm, int index, SQAutoFreePointers *ptr) { SQUserPointer instance; sq_getinstanceup(vm, index, &instance, 0); return  (ScriptPriorityQueue *)instance; }
+	template <> inline const ScriptPriorityQueue &GetParam(ForceType<const ScriptPriorityQueue &>, HSQUIRRELVM vm, int index, SQAutoFreePointers *ptr) { SQUserPointer instance; sq_getinstanceup(vm, index, &instance, 0); return *(ScriptPriorityQueue *)instance; }
+	template <> inline int Return<ScriptPriorityQueue *>(HSQUIRRELVM vm, ScriptPriorityQueue *res) { if (res == nullptr) { sq_pushnull(vm); return 1; } res->AddRef(); Squirrel::CreateClassInstanceVM(vm, "PriorityQueue", res, nullptr, DefSQDestructorCallback<ScriptPriorityQueue>, true); return 1; }
+} // namespace SQConvert
diff --git a/src/script/script_instance.cpp b/src/script/script_instance.cpp
index a38a315ff..81283cb77 100644
--- a/src/script/script_instance.cpp
+++ b/src/script/script_instance.cpp
@@ -58,6 +58,7 @@ ScriptInstance::ScriptInstance(const char *APIName) :
 	is_save_data_on_stack(false),
 	suspend(0),
 	is_paused(false),
+	in_shutdown(false),
 	callback(nullptr)
 {
 	this->storage = new ScriptStorage();
@@ -136,6 +137,7 @@ bool ScriptInstance::LoadCompatibilityScripts(const char *api_version, Subdirect
 ScriptInstance::~ScriptInstance()
 {
 	ScriptObject::ActiveInstance active(this);
+	this->in_shutdown = true;
 
 	if (instance != nullptr) this->engine->ReleaseObject(this->instance);
 	if (engine != nullptr) delete this->engine;
@@ -154,6 +156,7 @@ void ScriptInstance::Died()
 {
 	DEBUG(script, 0, "The script died unexpectedly.");
 	this->is_dead = true;
+	this->in_shutdown = true;
 
 	this->last_allocated_memory = this->GetAllocatedMemory(); // Update cache
 
@@ -718,3 +721,8 @@ size_t ScriptInstance::GetAllocatedMemory() const
 	if (this->engine == nullptr) return this->last_allocated_memory;
 	return this->engine->GetAllocatedMemory();
 }
+
+void ScriptInstance::ReleaseSQObject(HSQOBJECT *obj)
+{
+	if (!this->in_shutdown) this->engine->ReleaseObject(obj);
+}
diff --git a/src/script/script_instance.hpp b/src/script/script_instance.hpp
index e5024c80b..c097e0eb7 100644
--- a/src/script/script_instance.hpp
+++ b/src/script/script_instance.hpp
@@ -200,6 +200,17 @@ public:
 
 	size_t GetAllocatedMemory() const;
 
+	/**
+	 * Indicate whether this instance is currently being destroyed.
+	 */
+	inline bool InShutdown() const { return this->in_shutdown; }
+
+	/**
+	 * Decrease the ref count of a squirrel object.
+	 * @param obj The object to release.
+	 **/
+	void ReleaseSQObject(HSQOBJECT *obj);
+
 protected:
 	class Squirrel *engine;               ///< A wrapper around the squirrel vm.
 	const char *versionAPI;               ///< Current API used by this script.
@@ -242,6 +253,7 @@ private:
 	bool is_save_data_on_stack;           ///< Is the save data still on the squirrel stack?
 	int suspend;                          ///< The amount of ticks to suspend this script before it's allowed to continue.
 	bool is_paused;                       ///< Is the script paused? (a paused script will not be executed until unpaused)
+	bool in_shutdown;                     ///< Is this instance currently being destructed?
 	Script_SuspendCallbackProc *callback; ///< Callback that should be called in the next tick the script runs.
 	size_t last_allocated_memory;         ///< Last known allocated memory value (for display for crashed scripts)