1 /* 2 * This file is part of OpenTTD. 3 * 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. 4 * 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. 5 * 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/>. 6 */ 7 8 /** @file script_priorityqueue.hpp A queue that keeps a list of items sorted by a priority. */ 9 /** @defgroup ScriptPriorityQueue Classes that create a priority queue of items. */ 10 11 #ifndef SCRIPT_PRIORITYQUEUE_HPP 12 #define SCRIPT_PRIORITYQUEUE_HPP 13 14 #include "script_object.hpp" 15 #include <utility> 16 #include <vector> 17 18 /** 19 * Class that creates a queue which keeps its items ordered by an item priority. 20 * @api ai game 21 */ 22 class ScriptPriorityQueue : public ScriptObject { 23 public: 24 typedef std::pair<int64, HSQOBJECT> PriorityItem; 25 private: 26 struct PriorityComparator { operator ()ScriptPriorityQueue::PriorityComparator27 bool operator()(const PriorityItem &lhs, const PriorityItem &rhs) const noexcept 28 { 29 return lhs.first > rhs.first; 30 } 31 }; 32 33 PriorityComparator comp; 34 std::vector<PriorityItem> queue; ///< The priority list 35 36 public: 37 ~ScriptPriorityQueue(); 38 39 #ifdef DOXYGEN_API 40 /** 41 * Add a single item to the queue. 42 * @param item The item to add. Can be any Squirrel type. Should be unique, otherwise it is ignored. 43 * @param priority The priority to assign the item. 44 * @return True if the item was inserted, false if it was already in the queue. 45 */ 46 bool Insert(void *item, int64 priority); 47 48 /** 49 * Remove and return the item with the lowest priority. 50 * @return The item with the lowest priority, removed from the queue. Returns null on an empty queue. 51 * @pre !IsEmpty() 52 */ 53 void *Pop(); 54 55 /** 56 * Get the item with the lowest priority, keeping it in the queue. 57 * @return The item with the lowest priority. Returns null on an empty queue. 58 * @pre !IsEmpty() 59 */ 60 void *Peek(); 61 62 /** 63 * Check if an items is already included in the queue. 64 * @return true if the items is already in the queue. 65 * @note Performance is O(n), use only when absolutely required. 66 */ 67 bool Exists(void *item); 68 69 /** 70 * Clear the queue, making Count() returning 0 and IsEmpty() returning true. 71 */ 72 void Clear(); 73 #else 74 SQInteger Insert(HSQUIRRELVM vm); 75 SQInteger Pop(HSQUIRRELVM vm); 76 SQInteger Peek(HSQUIRRELVM vm); 77 SQInteger Exists(HSQUIRRELVM vm); 78 SQInteger Clear(HSQUIRRELVM vm); 79 #endif /* DOXYGEN_API */ 80 81 /** 82 * Check if the queue is empty. 83 * @return true if the queue is empty. 84 */ 85 bool IsEmpty(); 86 87 /** 88 * Returns the amount of items in the queue. 89 * @return amount of items in the queue. 90 */ 91 SQInteger Count(); 92 }; 93 94 #endif /* SCRIPT_PRIORITYQUEUE_HPP */ 95