src/script/api/script_list.cpp

   1 /* $Id: script_list.cpp 26072 2013-11-23 18:13:30Z rubidium $ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * 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.
   6  * 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.
   7  * 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/>.
   8  */
   9
  10 /** @file script_list.cpp Implementation of ScriptList. */
  11
  12 #include "../../stdafx.h"
  13 #include "script_list.hpp"
  14 #include "script_controller.hpp"
  15 #include "../../debug.h"
  16 #include "../../script/squirrel.hpp"
  17
  18 #include "../../safeguards.h"
  19
  20 /**
  21  * Base class for any ScriptList sorter.
  22  */
  23 class ScriptListSorter {
  24 protected:
  25         ScriptList *list;       ///< The list that's being sorted.
  26         bool has_no_more_items; ///< Whether we have more items to iterate over.
  27         int64 item_next;        ///< The next item we will show.
  28
  29 public:
  30         /**
  31          * Virtual dtor, needed to mute warnings.
  32          */
  33         virtual ~ScriptListSorter() { }
  34
  35         /**
  36          * Get the first item of the sorter.
  37          */
  38         virtual int64 Begin() = 0;
  39
  40         /**
  41          * Stop iterating a sorter.
  42          */
  43         virtual void End() = 0;
  44
  45         /**
  46          * Get the next item of the sorter.
  47          */
  48         virtual int64 Next() = 0;
  49
  50         /**
  51          * See if the sorter has reached the end.
  52          */
  53         bool IsEnd()
  54         {
  55                 return this->list->buckets.empty() || this->has_no_more_items;
  56         }
  57
  58         /**
  59          * Callback from the list if an item gets removed.
  60          */
  61         virtual void Remove(int item) = 0;
  62
  63         /**
  64          * Attach the sorter to a new list. This assumes the content of the old list has been moved to
  65          * the new list, too, so that we don't have to invalidate any iterators. Note that std::swap
  66          * doesn't invalidate iterators on lists and maps, so that should be safe.
  67          * @param target New list to attach to.
  68          */
  69         virtual void Retarget(ScriptList *new_list)
  70         {
  71                 this->list = new_list;
  72         }
  73 };
  74
  75 /**
  76  * Sort by value, ascending.
  77  */
  78 class ScriptListSorterValueAscending : public ScriptListSorter {
  79 private:
  80         ScriptList::ScriptListBucket::iterator bucket_iter;    ///< The iterator over the list to find the buckets.
  81         ScriptList::ScriptItemList *bucket_list;               ///< The current bucket list we're iterator over.
  82         ScriptList::ScriptItemList::iterator bucket_list_iter; ///< The iterator over the bucket list.
  83
  84 public:
  85         /**
  86          * Create a new sorter.
  87          * @param list The list to sort.
  88          */
  89         ScriptListSorterValueAscending(ScriptList *list)
  90         {
  91                 this->list = list;
  92                 this->End();
  93         }
  94
  95         int64 Begin()
  96         {
  97                 if (this->list->buckets.empty()) return 0;
  98                 this->has_no_more_items = false;
  99
 100                 this->bucket_iter = this->list->buckets.begin();
 101                 this->bucket_list = &(*this->bucket_iter).second;
 102                 this->bucket_list_iter = this->bucket_list->begin();
 103                 this->item_next = *this->bucket_list_iter;
 104
 105                 int64 item_current = this->item_next;
 106                 FindNext();
 107                 return item_current;
 108         }
 109
 110         void End()
 111         {
 112                 this->bucket_list = NULL;
 113                 this->has_no_more_items = true;
 114                 this->item_next = 0;
 115         }
 116
 117         /**
 118          * Find the next item, and store that information.
 119          */
 120         void FindNext()
 121         {
 122                 if (this->bucket_list == NULL) {
 123                         this->has_no_more_items = true;
 124                         return;
 125                 }
 126
 127                 this->bucket_list_iter++;
 128                 if (this->bucket_list_iter == this->bucket_list->end()) {
 129                         this->bucket_iter++;
 130                         if (this->bucket_iter == this->list->buckets.end()) {
 131                                 this->bucket_list = NULL;
 132                                 return;
 133                         }
 134                         this->bucket_list = &(*this->bucket_iter).second;
 135                         this->bucket_list_iter = this->bucket_list->begin();
 136                 }
 137                 this->item_next = *this->bucket_list_iter;
 138         }
 139
 140         int64 Next()
 141         {
 142                 if (this->IsEnd()) return 0;
 143
 144                 int64 item_current = this->item_next;
 145                 FindNext();
 146                 return item_current;
 147         }
 148
 149         void Remove(int item)
 150         {
 151                 if (this->IsEnd()) return;
 152
 153                 /* If we remove the 'next' item, skip to the next */
 154                 if (item == this->item_next) {
 155                         FindNext();
 156                         return;
 157                 }
 158         }
 159 };
 160
 161 /**
 162  * Sort by value, descending.
 163  */
 164 class ScriptListSorterValueDescending : public ScriptListSorter {
 165 private:
 166         /* Note: We cannot use reverse_iterator.
 167          *       The iterators must only be invalidated when the element they are pointing to is removed.
 168          *       This only holds for forward iterators. */
 169         ScriptList::ScriptListBucket::iterator bucket_iter;    ///< The iterator over the list to find the buckets.
 170         ScriptList::ScriptItemList *bucket_list;               ///< The current bucket list we're iterator over.
 171         ScriptList::ScriptItemList::iterator bucket_list_iter; ///< The iterator over the bucket list.
 172
 173 public:
 174         /**
 175          * Create a new sorter.
 176          * @param list The list to sort.
 177          */
 178         ScriptListSorterValueDescending(ScriptList *list)
 179         {
 180                 this->list = list;
 181                 this->End();
 182         }
 183
 184         int64 Begin()
 185         {
 186                 if (this->list->buckets.empty()) return 0;
 187                 this->has_no_more_items = false;
 188
 189                 /* Go to the end of the bucket-list */
 190                 this->bucket_iter = this->list->buckets.end();
 191                 --this->bucket_iter;
 192                 this->bucket_list = &(*this->bucket_iter).second;
 193
 194                 /* Go to the end of the items in the bucket */
 195                 this->bucket_list_iter = this->bucket_list->end();
 196                 --this->bucket_list_iter;
 197                 this->item_next = *this->bucket_list_iter;
 198
 199                 int64 item_current = this->item_next;
 200                 FindNext();
 201                 return item_current;
 202         }
 203
 204         void End()
 205         {
 206                 this->bucket_list = NULL;
 207                 this->has_no_more_items = true;
 208                 this->item_next = 0;
 209         }
 210
 211         /**
 212          * Find the next item, and store that information.
 213          */
 214         void FindNext()
 215         {
 216                 if (this->bucket_list == NULL) {
 217                         this->has_no_more_items = true;
 218                         return;
 219                 }
 220
 221                 if (this->bucket_list_iter == this->bucket_list->begin()) {
 222                         if (this->bucket_iter == this->list->buckets.begin()) {
 223                                 this->bucket_list = NULL;
 224                                 return;
 225                         }
 226                         this->bucket_iter--;
 227                         this->bucket_list = &(*this->bucket_iter).second;
 228                         /* Go to the end of the items in the bucket */
 229                         this->bucket_list_iter = this->bucket_list->end();
 230                         --this->bucket_list_iter;
 231                 } else {
 232                         this->bucket_list_iter--;
 233                 }
 234                 this->item_next = *this->bucket_list_iter;
 235         }
 236
 237         int64 Next()
 238         {
 239                 if (this->IsEnd()) return 0;
 240
 241                 int64 item_current = this->item_next;
 242                 FindNext();
 243                 return item_current;
 244         }
 245
 246         void Remove(int item)
 247         {
 248                 if (this->IsEnd()) return;
 249
 250                 /* If we remove the 'next' item, skip to the next */
 251                 if (item == this->item_next) {
 252                         FindNext();
 253                         return;
 254                 }
 255         }
 256 };
 257
 258 /**
 259  * Sort by item, ascending.
 260  */
 261 class ScriptListSorterItemAscending : public ScriptListSorter {
 262 private:
 263         ScriptList::ScriptListMap::iterator item_iter; ///< The iterator over the items in the map.
 264
 265 public:
 266         /**
 267          * Create a new sorter.
 268          * @param list The list to sort.
 269          */
 270         ScriptListSorterItemAscending(ScriptList *list)
 271         {
 272                 this->list = list;
 273                 this->End();
 274         }
 275
 276         int64 Begin()
 277         {
 278                 if (this->list->items.empty()) return 0;
 279                 this->has_no_more_items = false;
 280
 281                 this->item_iter = this->list->items.begin();
 282                 this->item_next = (*this->item_iter).first;
 283
 284                 int64 item_current = this->item_next;
 285                 FindNext();
 286                 return item_current;
 287         }
 288
 289         void End()
 290         {
 291                 this->has_no_more_items = true;
 292         }
 293
 294         /**
 295          * Find the next item, and store that information.
 296          */
 297         void FindNext()
 298         {
 299                 if (this->item_iter == this->list->items.end()) {
 300                         this->has_no_more_items = true;
 301                         return;
 302                 }
 303                 this->item_iter++;
 304                 if (this->item_iter != this->list->items.end()) item_next = (*this->item_iter).first;
 305         }
 306
 307         int64 Next()
 308         {
 309                 if (this->IsEnd()) return 0;
 310
 311                 int64 item_current = this->item_next;
 312                 FindNext();
 313                 return item_current;
 314         }
 315
 316         void Remove(int item)
 317         {
 318                 if (this->IsEnd()) return;
 319
 320                 /* If we remove the 'next' item, skip to the next */
 321                 if (item == this->item_next) {
 322                         FindNext();
 323                         return;
 324                 }
 325         }
 326 };
 327
 328 /**
 329  * Sort by item, descending.
 330  */
 331 class ScriptListSorterItemDescending : public ScriptListSorter {
 332 private:
 333         /* Note: We cannot use reverse_iterator.
 334          *       The iterators must only be invalidated when the element they are pointing to is removed.
 335          *       This only holds for forward iterators. */
 336         ScriptList::ScriptListMap::iterator item_iter; ///< The iterator over the items in the map.
 337
 338 public:
 339         /**
 340          * Create a new sorter.
 341          * @param list The list to sort.
 342          */
 343         ScriptListSorterItemDescending(ScriptList *list)
 344         {
 345                 this->list = list;
 346                 this->End();
 347         }
 348
 349         int64 Begin()
 350         {
 351                 if (this->list->items.empty()) return 0;
 352                 this->has_no_more_items = false;
 353
 354                 this->item_iter = this->list->items.end();
 355                 --this->item_iter;
 356                 this->item_next = (*this->item_iter).first;
 357
 358                 int64 item_current = this->item_next;
 359                 FindNext();
 360                 return item_current;
 361         }
 362
 363         void End()
 364         {
 365                 this->has_no_more_items = true;
 366         }
 367
 368         /**
 369          * Find the next item, and store that information.
 370          */
 371         void FindNext()
 372         {
 373                 if (this->item_iter == this->list->items.end()) {
 374                         this->has_no_more_items = true;
 375                         return;
 376                 }
 377                 if (this->item_iter == this->list->items.begin()) {
 378                         /* Use 'end' as marker for 'beyond begin' */
 379                         this->item_iter = this->list->items.end();
 380                 } else {
 381                         this->item_iter--;
 382                 }
 383                 if (this->item_iter != this->list->items.end()) item_next = (*this->item_iter).first;
 384         }
 385
 386         int64 Next()
 387         {
 388                 if (this->IsEnd()) return 0;
 389
 390                 int64 item_current = this->item_next;
 391                 FindNext();
 392                 return item_current;
 393         }
 394
 395         void Remove(int item)
 396         {
 397                 if (this->IsEnd()) return;
 398
 399                 /* If we remove the 'next' item, skip to the next */
 400                 if (item == this->item_next) {
 401                         FindNext();
 402                         return;
 403                 }
 404         }
 405 };
 406
 407
 408
 409 ScriptList::ScriptList()
 410 {
 411         /* Default sorter */
 412         this->sorter         = new ScriptListSorterValueDescending(this);
 413         this->sorter_type    = SORT_BY_VALUE;
 414         this->sort_ascending = false;
 415         this->initialized    = false;
 416         this->modifications  = 0;
 417 }
 418
 419 ScriptList::~ScriptList()
 420 {
 421         delete this->sorter;
 422 }
 423
 424 bool ScriptList::HasItem(int64 item)
 425 {
 426         return this->items.count(item) == 1;
 427 }
 428
 429 void ScriptList::Clear()
 430 {
 431         this->modifications++;
 432
 433         this->items.clear();
 434         this->buckets.clear();
 435         this->sorter->End();
 436 }
 437
 438 void ScriptList::AddItem(int64 item, int64 value)
 439 {
 440         this->modifications++;
 441
 442         if (this->HasItem(item)) return;
 443
 444         this->items[item] = value;
 445         this->buckets[value].insert(item);
 446 }
 447
 448 void ScriptList::RemoveItem(int64 item)
 449 {
 450         this->modifications++;
 451
 452         ScriptListMap::iterator item_iter = this->items.find(item);
 453         if (item_iter == this->items.end()) return;
 454
 455         int64 value = item_iter->second;
 456
 457         this->sorter->Remove(item);
 458         ScriptListBucket::iterator bucket_iter = this->buckets.find(value);
 459         assert(bucket_iter != this->buckets.end());
 460         bucket_iter->second.erase(item);
 461         if (bucket_iter->second.empty()) this->buckets.erase(bucket_iter);
 462         this->items.erase(item_iter);
 463 }
 464
 465 int64 ScriptList::Begin()
 466 {
 467         this->initialized = true;
 468         return this->sorter->Begin();
 469 }
 470
 471 int64 ScriptList::Next()
 472 {
 473         if (this->initialized == false) {
 474                 DEBUG(script, 0, "Next() is invalid as Begin() is never called");
 475                 return 0;
 476         }
 477         return this->sorter->Next();
 478 }
 479
 480 bool ScriptList::IsEmpty()
 481 {
 482         return this->items.empty();
 483 }
 484
 485 bool ScriptList::IsEnd()
 486 {
 487         if (this->initialized == false) {
 488                 DEBUG(script, 0, "IsEnd() is invalid as Begin() is never called");
 489                 return true;
 490         }
 491         return this->sorter->IsEnd();
 492 }
 493
 494 int32 ScriptList::Count()
 495 {
 496         return (int32)this->items.size();
 497 }
 498
 499 int64 ScriptList::GetValue(int64 item)
 500 {
 501         ScriptListMap::const_iterator item_iter = this->items.find(item);
 502         return item_iter == this->items.end() ? 0 : item_iter->second;
 503 }
 504
 505 bool ScriptList::SetValue(int64 item, int64 value)
 506 {
 507         this->modifications++;
 508
 509         ScriptListMap::iterator item_iter = this->items.find(item);
 510         if (item_iter == this->items.end()) return false;
 511
 512         int64 value_old = item_iter->second;
 513         if (value_old == value) return true;
 514
 515         this->sorter->Remove(item);
 516         ScriptListBucket::iterator bucket_iter = this->buckets.find(value_old);
 517         assert(bucket_iter != this->buckets.end());
 518         bucket_iter->second.erase(item);
 519         if (bucket_iter->second.empty()) this->buckets.erase(bucket_iter);
 520         item_iter->second = value;
 521         this->buckets[value].insert(item);
 522
 523         return true;
 524 }
 525
 526 void ScriptList::Sort(SorterType sorter, bool ascending)
 527 {
 528         this->modifications++;
 529
 530         if (sorter != SORT_BY_VALUE && sorter != SORT_BY_ITEM) return;
 531         if (sorter == this->sorter_type && ascending == this->sort_ascending) return;
 532
 533         delete this->sorter;
 534         switch (sorter) {
 535                 case SORT_BY_ITEM:
 536                         if (ascending) {
 537                                 this->sorter = new ScriptListSorterItemAscending(this);
 538                         } else {
 539                                 this->sorter = new ScriptListSorterItemDescending(this);
 540                         }
 541                         break;
 542
 543                 case SORT_BY_VALUE:
 544                         if (ascending) {
 545                                 this->sorter = new ScriptListSorterValueAscending(this);
 546                         } else {
 547                                 this->sorter = new ScriptListSorterValueDescending(this);
 548                         }
 549                         break;
 550
 551                 default: NOT_REACHED();
 552         }
 553         this->sorter_type    = sorter;
 554         this->sort_ascending = ascending;
 555         this->initialized    = false;
 556 }
 557
 558 void ScriptList::AddList(ScriptList *list)
 559 {
 560         if (list == this) return;
 561
 562         ScriptListMap *list_items = &list->items;
 563         for (ScriptListMap::iterator iter = list_items->begin(); iter != list_items->end(); iter++) {
 564                 this->AddItem((*iter).first);
 565                 this->SetValue((*iter).first, (*iter).second);
 566         }
 567 }
 568
 569 void ScriptList::SwapList(ScriptList *list)
 570 {
 571         if (list == this) return;
 572
 573         this->items.swap(list->items);
 574         this->buckets.swap(list->buckets);
 575         Swap(this->sorter, list->sorter);
 576         Swap(this->sorter_type, list->sorter_type);
 577         Swap(this->sort_ascending, list->sort_ascending);
 578         Swap(this->initialized, list->initialized);
 579         Swap(this->modifications, list->modifications);
 580         this->sorter->Retarget(this);
 581         list->sorter->Retarget(list);
 582 }
 583
 584 void ScriptList::RemoveAboveValue(int64 value)
 585 {
 586         this->modifications++;
 587
 588         for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
 589                 next_iter = iter; next_iter++;
 590                 if ((*iter).second > value) this->RemoveItem((*iter).first);
 591         }
 592 }
 593
 594 void ScriptList::RemoveBelowValue(int64 value)
 595 {
 596         this->modifications++;
 597
 598         for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
 599                 next_iter = iter; next_iter++;
 600                 if ((*iter).second < value) this->RemoveItem((*iter).first);
 601         }
 602 }
 603
 604 void ScriptList::RemoveBetweenValue(int64 start, int64 end)
 605 {
 606         this->modifications++;
 607
 608         for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
 609                 next_iter = iter; next_iter++;
 610                 if ((*iter).second > start && (*iter).second < end) this->RemoveItem((*iter).first);
 611         }
 612 }
 613
 614 void ScriptList::RemoveValue(int64 value)
 615 {
 616         this->modifications++;
 617
 618         for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
 619                 next_iter = iter; next_iter++;
 620                 if ((*iter).second == value) this->RemoveItem((*iter).first);
 621         }
 622 }
 623
 624 void ScriptList::RemoveTop(int32 count)
 625 {
 626         this->modifications++;
 627
 628         if (!this->sort_ascending) {
 629                 this->Sort(this->sorter_type, !this->sort_ascending);
 630                 this->RemoveBottom(count);
 631                 this->Sort(this->sorter_type, !this->sort_ascending);
 632                 return;
 633         }
 634
 635         switch (this->sorter_type) {
 636                 default: NOT_REACHED();
 637                 case SORT_BY_VALUE:
 638                         for (ScriptListBucket::iterator iter = this->buckets.begin(); iter != this->buckets.end(); iter = this->buckets.begin()) {
 639                                 ScriptItemList *items = &(*iter).second;
 640                                 size_t size = items->size();
 641                                 for (ScriptItemList::iterator iter = items->begin(); iter != items->end(); iter = items->begin()) {
 642                                         if (--count < 0) return;
 643                                         this->RemoveItem(*iter);
 644                                         /* When the last item is removed from the bucket, the bucket itself is removed.
 645                                          * This means that the iterators can be invalid after a call to RemoveItem.
 646                                          */
 647                                         if (--size == 0) break;
 648                                 }
 649                         }
 650                         break;
 651
 652                 case SORT_BY_ITEM:
 653                         for (ScriptListMap::iterator iter = this->items.begin(); iter != this->items.end(); iter = this->items.begin()) {
 654                                 if (--count < 0) return;
 655                                 this->RemoveItem((*iter).first);
 656                         }
 657                         break;
 658         }
 659 }
 660
 661 void ScriptList::RemoveBottom(int32 count)
 662 {
 663         this->modifications++;
 664
 665         if (!this->sort_ascending) {
 666                 this->Sort(this->sorter_type, !this->sort_ascending);
 667                 this->RemoveTop(count);
 668                 this->Sort(this->sorter_type, !this->sort_ascending);
 669                 return;
 670         }
 671
 672         switch (this->sorter_type) {
 673                 default: NOT_REACHED();
 674                 case SORT_BY_VALUE:
 675                         for (ScriptListBucket::reverse_iterator iter = this->buckets.rbegin(); iter != this->buckets.rend(); iter = this->buckets.rbegin()) {
 676                                 ScriptItemList *items = &(*iter).second;
 677                                 size_t size = items->size();
 678                                 for (ScriptItemList::reverse_iterator iter = items->rbegin(); iter != items->rend(); iter = items->rbegin()) {
 679                                         if (--count < 0) return;
 680                                         this->RemoveItem(*iter);
 681                                         /* When the last item is removed from the bucket, the bucket itself is removed.
 682                                          * This means that the iterators can be invalid after a call to RemoveItem.
 683                                          */
 684                                         if (--size == 0) break;
 685                                 }
 686                         }
 687                         break;
 688
 689                 case SORT_BY_ITEM:
 690                         for (ScriptListMap::reverse_iterator iter = this->items.rbegin(); iter != this->items.rend(); iter = this->items.rbegin()) {
 691                                 if (--count < 0) return;
 692                                 this->RemoveItem((*iter).first);
 693                         }
 694                         break;
 695         }
 696 }
 697
 698 void ScriptList::RemoveList(ScriptList *list)
 699 {
 700         this->modifications++;
 701
 702         if (list == this) {
 703                 Clear();
 704         } else {
 705                 ScriptListMap *list_items = &list->items;
 706                 for (ScriptListMap::iterator iter = list_items->begin(); iter != list_items->end(); iter++) {
 707                         this->RemoveItem((*iter).first);
 708                 }
 709         }
 710 }
 711
 712 void ScriptList::KeepAboveValue(int64 value)
 713 {
 714         this->modifications++;
 715
 716         for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
 717                 next_iter = iter; next_iter++;
 718                 if ((*iter).second <= value) this->RemoveItem((*iter).first);
 719         }
 720 }
 721
 722 void ScriptList::KeepBelowValue(int64 value)
 723 {
 724         this->modifications++;
 725
 726         for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
 727                 next_iter = iter; next_iter++;
 728                 if ((*iter).second >= value) this->RemoveItem((*iter).first);
 729         }
 730 }
 731
 732 void ScriptList::KeepBetweenValue(int64 start, int64 end)
 733 {
 734         this->modifications++;
 735
 736         for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
 737                 next_iter = iter; next_iter++;
 738                 if ((*iter).second <= start || (*iter).second >= end) this->RemoveItem((*iter).first);
 739         }
 740 }
 741
 742 void ScriptList::KeepValue(int64 value)
 743 {
 744         this->modifications++;
 745
 746         for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
 747                 next_iter = iter; next_iter++;
 748                 if ((*iter).second != value) this->RemoveItem((*iter).first);
 749         }
 750 }
 751
 752 void ScriptList::KeepTop(int32 count)
 753 {
 754         this->modifications++;
 755
 756         this->RemoveBottom(this->Count() - count);
 757 }
 758
 759 void ScriptList::KeepBottom(int32 count)
 760 {
 761         this->modifications++;
 762
 763         this->RemoveTop(this->Count() - count);
 764 }
 765
 766 void ScriptList::KeepList(ScriptList *list)
 767 {
 768         if (list == this) return;
 769
 770         this->modifications++;
 771
 772         ScriptList tmp;
 773         tmp.AddList(this);
 774         tmp.RemoveList(list);
 775         this->RemoveList(&tmp);
 776 }
 777
 778 SQInteger ScriptList::_get(HSQUIRRELVM vm)
 779 {
 780         if (sq_gettype(vm, 2) != OT_INTEGER) return SQ_ERROR;
 781
 782         SQInteger idx;
 783         sq_getinteger(vm, 2, &idx);
 784
 785         ScriptListMap::const_iterator item_iter = this->items.find(idx);
 786         if (item_iter == this->items.end()) return SQ_ERROR;
 787
 788         sq_pushinteger(vm, item_iter->second);
 789         return 1;
 790 }
 791
 792 SQInteger ScriptList::_set(HSQUIRRELVM vm)
 793 {
 794         if (sq_gettype(vm, 2) != OT_INTEGER) return SQ_ERROR;
 795         if (sq_gettype(vm, 3) != OT_INTEGER && sq_gettype(vm, 3) != OT_NULL) {
 796                 return sq_throwerror(vm, "you can only assign integers to this list");
 797         }
 798
 799         SQInteger idx, val;
 800         sq_getinteger(vm, 2, &idx);
 801         if (sq_gettype(vm, 3) == OT_NULL) {
 802                 this->RemoveItem(idx);
 803                 return 0;
 804         }
 805
 806         sq_getinteger(vm, 3, &val);
 807         if (!this->HasItem(idx)) {
 808                 this->AddItem(idx, val);
 809                 return 0;
 810         }
 811
 812         this->SetValue(idx, val);
 813         return 0;
 814 }
 815
 816 SQInteger ScriptList::_nexti(HSQUIRRELVM vm)
 817 {
 818         if (sq_gettype(vm, 2) == OT_NULL) {
 819                 if (this->IsEmpty()) {
 820                         sq_pushnull(vm);
 821                         return 1;
 822                 }
 823                 sq_pushinteger(vm, this->Begin());
 824                 return 1;
 825         }
 826
 827         SQInteger idx;
 828         sq_getinteger(vm, 2, &idx);
 829
 830         int val = this->Next();
 831         if (this->IsEnd()) {
 832                 sq_pushnull(vm);
 833                 return 1;
 834         }
 835
 836         sq_pushinteger(vm, val);
 837         return 1;
 838 }
 839
 840 SQInteger ScriptList::Valuate(HSQUIRRELVM vm)
 841 {
 842         this->modifications++;
 843
 844         /* The first parameter is the instance of ScriptList. */
 845         int nparam = sq_gettop(vm) - 1;
 846
 847         if (nparam < 1) {
 848                 return sq_throwerror(vm, "You need to give a least a Valuator as parameter to ScriptList::Valuate");
 849         }
 850
 851         /* Make sure the valuator function is really a function, and not any
 852          * other type. It's parameter 2 for us, but for the user it's the
 853          * first parameter they give. */
 854         SQObjectType valuator_type = sq_gettype(vm, 2);
 855         if (valuator_type != OT_CLOSURE && valuator_type != OT_NATIVECLOSURE) {
 856                 return sq_throwerror(vm, "parameter 1 has an invalid type (expected function)");
 857         }
 858
 859         /* Don't allow docommand from a Valuator, as we can't resume in
 860          * mid C++-code. */
 861         bool backup_allow = ScriptObject::GetAllowDoCommand();
 862         ScriptObject::SetAllowDoCommand(false);
 863
 864         /* Push the function to call */
 865         sq_push(vm, 2);
 866
 867         for (ScriptListMap::iterator iter = this->items.begin(); iter != this->items.end(); iter++) {
 868                 /* Check for changing of items. */
 869                 int previous_modification_count = this->modifications;
 870
 871                 /* Push the root table as instance object, this is what squirrel does for meta-functions. */
 872                 sq_pushroottable(vm);
 873                 /* Push all arguments for the valuator function. */
 874                 sq_pushinteger(vm, (*iter).first);
 875                 for (int i = 0; i < nparam - 1; i++) {
 876                         sq_push(vm, i + 3);
 877                 }
 878
 879                 /* Call the function. Squirrel pops all parameters and pushes the return value. */
 880                 if (SQ_FAILED(sq_call(vm, nparam + 1, SQTrue, SQTrue))) {
 881                         ScriptObject::SetAllowDoCommand(backup_allow);
 882                         return SQ_ERROR;
 883                 }
 884
 885                 /* Retrieve the return value */
 886                 SQInteger value;
 887                 switch (sq_gettype(vm, -1)) {
 888                         case OT_INTEGER: {
 889                                 sq_getinteger(vm, -1, &value);
 890                                 break;
 891                         }
 892
 893                         case OT_BOOL: {
 894                                 SQBool v;
 895                                 sq_getbool(vm, -1, &v);
 896                                 value = v ? 1 : 0;
 897                                 break;
 898                         }
 899
 900                         default: {
 901                                 /* See below for explanation. The extra pop is the return value. */
 902                                 sq_pop(vm, nparam + 4);
 903
 904                                 ScriptObject::SetAllowDoCommand(backup_allow);
 905                                 return sq_throwerror(vm, "return value of valuator is not valid (not integer/bool)");
 906                         }
 907                 }
 908
 909                 /* Kill the script when the valuator call takes way too long.
 910                  * Triggered by nesting valuators, which then take billions of iterations. */
 911                 if (ScriptController::GetOpsTillSuspend() < -1000000) {
 912                         /* See below for explanation. The extra pop is the return value. */
 913                         sq_pop(vm, nparam + 4);
 914
 915                         ScriptObject::SetAllowDoCommand(backup_allow);
 916                         return sq_throwerror(vm, "excessive CPU usage in valuator function");
 917                 }
 918
 919                 /* Was something changed? */
 920                 if (previous_modification_count != this->modifications) {
 921                         /* See below for explanation. The extra pop is the return value. */
 922                         sq_pop(vm, nparam + 4);
 923
 924                         ScriptObject::SetAllowDoCommand(backup_allow);
 925                         return sq_throwerror(vm, "modifying valuated list outside of valuator function");
 926                 }
 927
 928                 this->SetValue((*iter).first, value);
 929
 930                 /* Pop the return value. */
 931                 sq_poptop(vm);
 932
 933                 Squirrel::DecreaseOps(vm, 5);
 934         }
 935         /* Pop from the squirrel stack:
 936          * 1. The root stable (as instance object).
 937          * 2. The valuator function.
 938          * 3. The parameters given to this function.
 939          * 4. The ScriptList instance object. */
 940         sq_pop(vm, nparam + 3);
 941
 942         ScriptObject::SetAllowDoCommand(backup_allow);
 943         return 0;
 944 }