From 1c0ba07c3cb4f393b56063e2d631fbb2d73219b1 Mon Sep 17 00:00:00 2001 From: Michael Lutz Date: Sun, 19 Apr 2020 00:53:30 +0200 Subject: Add: [Script] Native priority queue; useful e.g. for pathfinders. --- src/script/api/ai/ai_priorityqueue.hpp.sq | 31 ++++++ src/script/api/ai_changelog.hpp | 3 + src/script/api/game/game_priorityqueue.hpp.sq | 31 ++++++ src/script/api/game_changelog.hpp | 1 + src/script/api/script_priorityqueue.cpp | 107 +++++++++++++++++++++ src/script/api/script_priorityqueue.hpp | 94 ++++++++++++++++++ .../api/template/template_priorityqueue.hpp.sq | 19 ++++ 7 files changed, 286 insertions(+) create mode 100644 src/script/api/ai/ai_priorityqueue.hpp.sq create mode 100644 src/script/api/game/game_priorityqueue.hpp.sq create mode 100644 src/script/api/script_priorityqueue.cpp create mode 100644 src/script/api/script_priorityqueue.hpp create mode 100644 src/script/api/template/template_priorityqueue.hpp.sq (limited to 'src/script/api') 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 . + */ + +/* THIS FILE IS AUTO-GENERATED; PLEASE DO NOT ALTER MANUALLY */ + +#include "../script_priorityqueue.hpp" +#include "../template/template_priorityqueue.hpp.sq" + + +template <> const char *GetClassName() { return "AIPriorityQueue"; } + +void SQAIPriorityQueue_Register(Squirrel *engine) +{ + DefSQClass SQAIPriorityQueue("AIPriorityQueue"); + SQAIPriorityQueue.PreRegister(engine); + SQAIPriorityQueue.AddConstructor(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 . + */ + +/* THIS FILE IS AUTO-GENERATED; PLEASE DO NOT ALTER MANUALLY */ + +#include "../script_priorityqueue.hpp" +#include "../template/template_priorityqueue.hpp.sq" + + +template <> const char *GetClassName() { return "GSPriorityQueue"; } + +void SQGSPriorityQueue_Register(Squirrel *engine) +{ + DefSQClass SQGSPriorityQueue("GSPriorityQueue"); + SQGSPriorityQueue.PreRegister(engine); + SQGSPriorityQueue.AddConstructor(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 . + */ + +/** @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 + +#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(&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(&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 . + */ + +/** @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 +#include + +/** + * 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 PriorityItem; +private: + struct PriorityComparator { + bool operator()(const PriorityItem &lhs, const PriorityItem &rhs) const noexcept + { + return lhs.first > rhs.first; + } + }; + + PriorityComparator comp; + std::vector 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 . + */ + +/* 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, HSQUIRRELVM vm, int index, SQAutoFreePointers *ptr) { SQUserPointer instance; sq_getinstanceup(vm, index, &instance, 0); return (ScriptPriorityQueue *)instance; } + template <> inline ScriptPriorityQueue &GetParam(ForceType, HSQUIRRELVM vm, int index, SQAutoFreePointers *ptr) { SQUserPointer instance; sq_getinstanceup(vm, index, &instance, 0); return *(ScriptPriorityQueue *)instance; } + template <> inline const ScriptPriorityQueue *GetParam(ForceType, HSQUIRRELVM vm, int index, SQAutoFreePointers *ptr) { SQUserPointer instance; sq_getinstanceup(vm, index, &instance, 0); return (ScriptPriorityQueue *)instance; } + template <> inline const ScriptPriorityQueue &GetParam(ForceType, HSQUIRRELVM vm, int index, SQAutoFreePointers *ptr) { SQUserPointer instance; sq_getinstanceup(vm, index, &instance, 0); return *(ScriptPriorityQueue *)instance; } + template <> inline int Return(HSQUIRRELVM vm, ScriptPriorityQueue *res) { if (res == nullptr) { sq_pushnull(vm); return 1; } res->AddRef(); Squirrel::CreateClassInstanceVM(vm, "PriorityQueue", res, nullptr, DefSQDestructorCallback, true); return 1; } +} // namespace SQConvert -- cgit v1.2.3-70-g09d2