src/script/api/script_list.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_list.hpp A list which can keep item/value pairs, which you can walk. */
   9 /** @defgroup ScriptList Classes that create a list of items. */
  10
  11 #ifndef SCRIPT_LIST_HPP
  12 #define SCRIPT_LIST_HPP
  13
  14 #include "script_object.hpp"
  15
  16 /** Maximum number of operations allowed for valuating a list. */
  17 static const int MAX_VALUATE_OPS = 1000000;
  18
  19 class ScriptListSorter;
  20
  21 /**
  22  * Class that creates a list which can keep item/value pairs, which you can walk.
  23  * @api ai game
  24  */
  25 class ScriptList : public ScriptObject {
  26 public:
  27         /** Type of sorter */
  28         enum SorterType {
  29                 SORT_BY_VALUE, ///< Sort the list based on the value of the item.
  30                 SORT_BY_ITEM,  ///< Sort the list based on the item itself.
  31         };
  32
  33         /** Sort ascending */
  34         static const bool SORT_ASCENDING = true;
  35         /** Sort descending */
  36         static const bool SORT_DESCENDING = false;
  37
  38 private:
  39         ScriptListSorter *sorter;     ///< Sorting algorithm
  40         SorterType sorter_type;       ///< Sorting type
  41         bool sort_ascending;          ///< Whether to sort ascending or descending
  42         bool initialized;             ///< Whether an iteration has been started
  43         int modifications;            ///< Number of modification that has been done. To prevent changing data while valuating.
  44
  45 protected:
  46         template <typename T, class ItemValid, class ItemFilter>
  47         static void FillList(ScriptList *list, ItemValid item_valid, ItemFilter item_filter)
  48         {
  49                 for (const T *item : T::Iterate()) {
  50                         if (!item_valid(item)) continue;
  51                         if (!item_filter(item)) continue;
  52                         list->AddItem(item->index);
  53                 }
  54         }
  55
  56         template <typename T, class ItemValid>
  57         static void FillList(ScriptList *list, ItemValid item_valid)
  58         {
  59                 ScriptList::FillList<T>(list, item_valid, [](const T *) { return true; });
  60         }
  61
  62         template <typename T>
  63         static void FillList(ScriptList *list)
  64         {
  65                 ScriptList::FillList<T>(list, [](const T *) { return true; });
  66         }
  67
  68         template <typename T, class ItemValid>
  69         static void FillList(HSQUIRRELVM vm, ScriptList *list, ItemValid item_valid)
  70         {
  71                 int nparam = sq_gettop(vm) - 1;
  72                 if (nparam >= 1) {
  73                         /* Make sure the filter function is really a function, and not any
  74                          * other type. It's parameter 2 for us, but for the user it's the
  75                          * first parameter they give. */
  76                         SQObjectType valuator_type = sq_gettype(vm, 2);
  77                         if (valuator_type != OT_CLOSURE && valuator_type != OT_NATIVECLOSURE) {
  78                                 throw sq_throwerror(vm, "parameter 1 has an invalid type (expected function)");
  79                         }
  80
  81                         /* Push the function to call */
  82                         sq_push(vm, 2);
  83                 }
  84
  85                 /* Don't allow docommand from a Valuator, as we can't resume in
  86                  * mid C++-code. */
  87                 bool backup_allow = ScriptObject::GetAllowDoCommand();
  88                 ScriptObject::SetAllowDoCommand(false);
  89
  90
  91                 if (nparam < 1) {
  92                         ScriptList::FillList<T>(list, item_valid);
  93                 } else {
  94                         /* Limit the total number of ops that can be consumed by a filter operation, if a filter function is present */
  95                         SQOpsLimiter limiter(vm, MAX_VALUATE_OPS, "list filter function");
  96
  97                         ScriptList::FillList<T>(list, item_valid,
  98                                 [vm, nparam, backup_allow](const T *item) {
  99                                         /* Push the root table as instance object, this is what squirrel does for meta-functions. */
 100                                         sq_pushroottable(vm);
 101                                         /* Push all arguments for the valuator function. */
 102                                         sq_pushinteger(vm, item->index);
 103                                         for (int i = 0; i < nparam - 1; i++) {
 104                                                 sq_push(vm, i + 3);
 105                                         }
 106
 107                                         /* Call the function. Squirrel pops all parameters and pushes the return value. */
 108                                         if (SQ_FAILED(sq_call(vm, nparam + 1, SQTrue, SQTrue))) {
 109                                                 ScriptObject::SetAllowDoCommand(backup_allow);
 110                                                 throw sq_throwerror(vm, "failed to run filter");
 111                                         }
 112
 113                                         SQBool add = SQFalse;
 114
 115                                         /* Retrieve the return value */
 116                                         switch (sq_gettype(vm, -1)) {
 117                                                 case OT_BOOL:
 118                                                         sq_getbool(vm, -1, &add);
 119                                                         break;
 120
 121                                                 default:
 122                                                         ScriptObject::SetAllowDoCommand(backup_allow);
 123                                                         throw sq_throwerror(vm, "return value of filter is not valid (not bool)");
 124                                         }
 125
 126                                         /* Pop the return value. */
 127                                         sq_poptop(vm);
 128
 129                                         return add;
 130                                 }
 131                         );
 132
 133                         /* Pop the filter function */
 134                         sq_poptop(vm);
 135                 }
 136
 137                 ScriptObject::SetAllowDoCommand(backup_allow);
 138         }
 139
 140         template <typename T>
 141         static void FillList(HSQUIRRELVM vm, ScriptList *list)
 142         {
 143                 ScriptList::FillList<T>(vm, list, [](const T *) { return true; });
 144         }
 145
 146 public:
 147         typedef std::set<SQInteger> ScriptItemList;                   ///< The list of items inside the bucket
 148         typedef std::map<SQInteger, ScriptItemList> ScriptListBucket; ///< The bucket list per value
 149         typedef std::map<SQInteger, SQInteger> ScriptListMap;         ///< List per item
 150
 151         ScriptListMap items;           ///< The items in the list
 152         ScriptListBucket buckets;      ///< The items in the list, sorted by value
 153
 154         ScriptList();
 155         ~ScriptList();
 156
 157 #ifdef DOXYGEN_API
 158         /**
 159          * Add a single item to the list.
 160          * @param item the item to add. Should be unique, otherwise it is ignored.
 161          * @param value the value to assign.
 162          */
 163         void AddItem(SQInteger item, SQInteger value);
 164 #else
 165         void AddItem(SQInteger item, SQInteger value = 0);
 166 #endif /* DOXYGEN_API */
 167
 168         /**
 169          * Remove a single item from the list.
 170          * @param item the item to remove. If not existing, it is ignored.
 171          */
 172         void RemoveItem(SQInteger item);
 173
 174         /**
 175          * Clear the list, making Count() returning 0 and IsEmpty() returning true.
 176          */
 177         void Clear();
 178
 179         /**
 180          * Check if an item is in the list.
 181          * @param item the item to check for.
 182          * @return true if the item is in the list.
 183          */
 184         bool HasItem(SQInteger item);
 185
 186         /**
 187          * Go to the beginning of the list and return the item. To get the value use list.GetValue(list.Begin()).
 188          * @return the first item.
 189          * @note returns 0 if beyond end-of-list. Use IsEnd() to check for end-of-list.
 190          */
 191         SQInteger Begin();
 192
 193         /**
 194          * Go to the next item in the list and return the item. To get the value use list.GetValue(list.Next()).
 195          * @return the next item.
 196          * @note returns 0 if beyond end-of-list. Use IsEnd() to check for end-of-list.
 197          */
 198         SQInteger Next();
 199
 200         /**
 201          * Check if a list is empty.
 202          * @return true if the list is empty.
 203          */
 204         bool IsEmpty();
 205
 206         /**
 207          * Check if there is a element left. In other words, if this is false,
 208          * the last call to Begin() or Next() returned a valid item.
 209          * @return true if the current item is beyond end-of-list.
 210          */
 211         bool IsEnd();
 212
 213         /**
 214          * Returns the amount of items in the list.
 215          * @return amount of items in the list.
 216          */
 217         SQInteger Count();
 218
 219         /**
 220          * Get the value that belongs to this item.
 221          * @param item the item to get the value from
 222          * @return the value that belongs to this item.
 223          */
 224         SQInteger GetValue(SQInteger item);
 225
 226         /**
 227          * Set a value of an item directly.
 228          * @param item the item to set the value for.
 229          * @param value the value to give to the item
 230          * @return true if we could set the item to value, false otherwise.
 231          * @note Changing values of items while looping through a list might cause
 232          *  entries to be skipped. Be very careful with such operations.
 233          */
 234         bool SetValue(SQInteger item, SQInteger value);
 235
 236         /**
 237          * Sort this list by the given sorter and direction.
 238          * @param sorter    the type of sorter to use
 239          * @param ascending if true, lowest value is on top, else at bottom.
 240          * @note the current item stays at the same place.
 241          * @see SORT_ASCENDING SORT_DESCENDING
 242          */
 243         void Sort(SorterType sorter, bool ascending);
 244
 245         /**
 246          * Add one list to another one.
 247          * @param list The list that will be added to the caller.
 248          * @post The list to be added ('list') stays unmodified.
 249          * @note All added items keep their value as it was in 'list'.
 250          * @note If the item already exists inside the caller, the value of the
 251          *  list that is added is set on the item.
 252          */
 253         void AddList(ScriptList *list);
 254
 255         /**
 256          * Swap the contents of two lists.
 257          * @param list The list that will be swapped with.
 258          */
 259         void SwapList(ScriptList *list);
 260
 261         /**
 262          * Removes all items with a higher value than 'value'.
 263          * @param value the value above which all items are removed.
 264          */
 265         void RemoveAboveValue(SQInteger value);
 266
 267         /**
 268          * Removes all items with a lower value than 'value'.
 269          * @param value the value below which all items are removed.
 270          */
 271         void RemoveBelowValue(SQInteger value);
 272
 273         /**
 274          * Removes all items with a value above start and below end.
 275          * @param start the lower bound of the to be removed values (exclusive).
 276          * @param end   the upper bound of the to be removed values (exclusive).
 277          */
 278         void RemoveBetweenValue(SQInteger start, SQInteger end);
 279
 280         /**
 281          * Remove all items with this value.
 282          * @param value the value to remove.
 283          */
 284         void RemoveValue(SQInteger value);
 285
 286         /**
 287          * Remove the first count items.
 288          * @param count the amount of items to remove.
 289          */
 290         void RemoveTop(SQInteger count);
 291
 292         /**
 293          * Remove the last count items.
 294          * @param count the amount of items to remove.
 295          */
 296         void RemoveBottom(SQInteger count);
 297
 298         /**
 299          * Remove everything that is in the given list from this list (same item index that is).
 300          * @param list the list of items to remove.
 301          * @pre list != null
 302          */
 303         void RemoveList(ScriptList *list);
 304
 305         /**
 306          * Keep all items with a higher value than 'value'.
 307          * @param value the value above which all items are kept.
 308          */
 309         void KeepAboveValue(SQInteger value);
 310
 311         /**
 312          * Keep all items with a lower value than 'value'.
 313          * @param value the value below which all items are kept.
 314          */
 315         void KeepBelowValue(SQInteger value);
 316
 317         /**
 318          * Keep all items with a value above start and below end.
 319          * @param start the lower bound of the to be kept values (exclusive).
 320          * @param end   the upper bound of the to be kept values (exclusive).
 321          */
 322         void KeepBetweenValue(SQInteger start, SQInteger end);
 323
 324         /**
 325          * Keep all items with this value.
 326          * @param value the value to keep.
 327          */
 328         void KeepValue(SQInteger value);
 329
 330         /**
 331          * Keep the first count items, i.e. remove everything except the first count items.
 332          * @param count the amount of items to keep.
 333          */
 334         void KeepTop(SQInteger count);
 335
 336         /**
 337          * Keep the last count items, i.e. remove everything except the last count items.
 338          * @param count the amount of items to keep.
 339          */
 340         void KeepBottom(SQInteger count);
 341
 342         /**
 343          * Keeps everything that is in the given list from this list (same item index that is).
 344          * @param list the list of items to keep.
 345          * @pre list != null
 346          */
 347         void KeepList(ScriptList *list);
 348
 349 #ifndef DOXYGEN_API
 350         /**
 351          * Used for 'foreach()' and [] get from Squirrel.
 352          */
 353         SQInteger _get(HSQUIRRELVM vm);
 354
 355         /**
 356          * Used for [] set from Squirrel.
 357          */
 358         SQInteger _set(HSQUIRRELVM vm);
 359
 360         /**
 361          * Used for 'foreach()' from Squirrel.
 362          */
 363         SQInteger _nexti(HSQUIRRELVM vm);
 364
 365         /**
 366          * The Valuate() wrapper from Squirrel.
 367          */
 368         SQInteger Valuate(HSQUIRRELVM vm);
 369 #else
 370         /**
 371          * Give all items a value defined by the valuator you give.
 372          * @param valuator_function The function which will be doing the valuation.
 373          * @param ... The params to give to the valuators (minus the first param,
 374          *  which is always the index-value we are valuating).
 375          * @note You may not add, remove or change (setting the value of) items while
 376          *  valuating. You may also not (re)sort while valuating.
 377          * @note You can write your own valuators and use them. Just remember that
 378          *  the first parameter should be the index-value, and it should return
 379          *  an integer.
 380          * @note Example:
 381          * @code
 382          *  list.Valuate(ScriptBridge.GetPrice, 5);
 383          *  list.Valuate(ScriptBridge.GetMaxLength);
 384          *  function MyVal(bridge_id, myparam)
 385          *  {
 386          *    return myparam * bridge_id; // This is silly
 387          *  }
 388          *  list.Valuate(MyVal, 12);
 389          * @endcode
 390          */
 391         void Valuate(function valuator_function, ...);
 392 #endif /* DOXYGEN_API */
 393 };
 394
 395 #endif /* SCRIPT_LIST_HPP */