src/script/api/script_priorityqueue.hpp

   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
  17 /**
  18  * Class that creates a queue which keeps its items ordered by an item priority.
  19  * @api ai game
  20  */
  21 class ScriptPriorityQueue : public ScriptObject {
  22 public:
  23         typedef std::pair<SQInteger, HSQOBJECT> PriorityItem;
  24 private:
  25         struct PriorityComparator {
  26                 bool operator()(const PriorityItem &lhs, const PriorityItem &rhs) const noexcept
  27                 {
  28                         return lhs.first > rhs.first;
  29                 }
  30         };
  31
  32         PriorityComparator        comp;
  33         std::vector<PriorityItem> queue;  ///< The priority list
  34
  35 public:
  36         ~ScriptPriorityQueue();
  37
  38 #ifdef DOXYGEN_API
  39         /**
  40          * Add a single item to the queue.
  41          * @param item The item to add. Can be any Squirrel type. Should be unique, otherwise it is ignored.
  42          * @param priority The priority to assign the item.
  43          * @return True if the item was inserted, false if it was already in the queue.
  44          */
  45         bool Insert(object item, SQInteger priority);
  46
  47         /**
  48          * Remove and return the item with the lowest priority.
  49          * @return The item with the lowest priority, removed from the queue. Returns null on an empty queue.
  50          * @pre !IsEmpty()
  51          */
  52         object Pop();
  53
  54         /**
  55          * Get the item with the lowest priority, keeping it in the queue.
  56          * @return The item with the lowest priority. Returns null on an empty queue.
  57          * @pre !IsEmpty()
  58          */
  59         object Peek();
  60
  61         /**
  62          * Check if an items is already included in the queue.
  63          * @param item The item to check whether it's already in this 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(object 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 */