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