# ai_abstractlist.cpp

Go to the documentation of this file.

    00001 /* $Id: ai_abstractlist.cpp 19300 2010-03-02 00:38:01Z rubidium $ */
    00002
    00003 /*
    00004  * This file is part of OpenTTD.
    00005  * 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.
    00006  * 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.
    00007  * 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/>.
    00008  */
    00009
    00012 #include "ai_abstractlist.hpp"
    00013 #include "../../debug.h"
    00014 #include "../../script/squirrel.hpp"
    00015
    00019 class AIAbstractListSorter {
    00020 protected:
    00021   AIAbstractList *list;
    00022
    00023 public:
    00027   virtual ~AIAbstractListSorter() { }
    00028
    00032   virtual int32 Begin() = 0;
    00033
    00037   virtual void End() = 0;
    00038
    00042   virtual int32 Next() = 0;
    00043
    00047   virtual bool HasNext() = 0;
    00048
    00052   virtual void Remove(int item) = 0;
    00053 };
    00054
    00058 class AIAbstractListSorterValueAscending : public AIAbstractListSorter {
    00059 private:
    00060   AIAbstractList::AIAbstractListBucket::iterator bucket_iter;
    00061   AIAbstractList::AIItemList *bucket_list;
    00062   AIAbstractList::AIItemList::iterator bucket_list_iter;
    00063   bool has_no_more_items;
    00064   int32 item_next;
    00065
    00066 public:
    00067   AIAbstractListSorterValueAscending(AIAbstractList *list)
    00068   {
    00069     this->list = list;
    00070     this->End();
    00071   }
    00072
    00073   int32 Begin()
    00074   {
    00075     if (this->list->buckets.empty()) return 0;
    00076     this->has_no_more_items = false;
    00077
    00078     this->bucket_iter = this->list->buckets.begin();
    00079     this->bucket_list = &(*this->bucket_iter).second;
    00080     this->bucket_list_iter = this->bucket_list->begin();
    00081     this->item_next = *this->bucket_list_iter;
    00082
    00083     int32 item_current = this->item_next;
    00084     FindNext();
    00085     return item_current;
    00086   }
    00087
    00088   void End()
    00089   {
    00090     this->bucket_list = NULL;
    00091     this->has_no_more_items = true;
    00092     this->item_next = 0;
    00093   }
    00094
    00095   void FindNext()
    00096   {
    00097     if (this->bucket_list == NULL) {
    00098       this->has_no_more_items = true;
    00099       return;
    00100     }
    00101
    00102     this->bucket_list_iter++;
    00103     if (this->bucket_list_iter == this->bucket_list->end()) {
    00104       this->bucket_iter++;
    00105       if (this->bucket_iter == this->list->buckets.end()) {
    00106         this->bucket_list = NULL;
    00107         return;
    00108       }
    00109       this->bucket_list = &(*this->bucket_iter).second;
    00110       this->bucket_list_iter = this->bucket_list->begin();
    00111     }
    00112     this->item_next = *this->bucket_list_iter;
    00113   }
    00114
    00115   int32 Next()
    00116   {
    00117     if (!this->HasNext()) return 0;
    00118
    00119     int32 item_current = this->item_next;
    00120     FindNext();
    00121     return item_current;
    00122   }
    00123
    00124   void Remove(int item)
    00125   {
    00126     if (!this->HasNext()) return;
    00127
    00128     /* If we remove the 'next' item, skip to the next */
    00129     if (item == this->item_next) {
    00130       FindNext();
    00131       return;
    00132     }
    00133   }
    00134
    00135   bool HasNext()
    00136   {
    00137     return !(this->list->buckets.empty() || this->has_no_more_items);
    00138   }
    00139 };
    00140
    00144 class AIAbstractListSorterValueDescending : public AIAbstractListSorter {
    00145 private:
    00146   AIAbstractList::AIAbstractListBucket::iterator bucket_iter;
    00147   AIAbstractList::AIItemList *bucket_list;
    00148   AIAbstractList::AIItemList::iterator bucket_list_iter;
    00149   bool has_no_more_items;
    00150   int32 item_next;
    00151
    00152 public:
    00153   AIAbstractListSorterValueDescending(AIAbstractList *list)
    00154   {
    00155     this->list = list;
    00156     this->End();
    00157   }
    00158
    00159   int32 Begin()
    00160   {
    00161     if (this->list->buckets.empty()) return 0;
    00162     this->has_no_more_items = false;
    00163
    00164     /* Go to the end of the bucket-list */
    00165     this->bucket_iter = this->list->buckets.begin();
    00166     for (size_t i = this->list->buckets.size(); i > 1; i--) this->bucket_iter++;
    00167     this->bucket_list = &(*this->bucket_iter).second;
    00168
    00169     /* Go to the end of the items in the bucket */
    00170     this->bucket_list_iter = this->bucket_list->begin();
    00171     for (size_t i = this->bucket_list->size(); i > 1; i--) this->bucket_list_iter++;
    00172     this->item_next = *this->bucket_list_iter;
    00173
    00174     int32 item_current = this->item_next;
    00175     FindNext();
    00176     return item_current;
    00177   }
    00178
    00179   void End()
    00180   {
    00181     this->bucket_list = NULL;
    00182     this->has_no_more_items = true;
    00183     this->item_next = 0;
    00184   }
    00185
    00186   void FindNext()
    00187   {
    00188     if (this->bucket_list == NULL) {
    00189       this->has_no_more_items = true;
    00190       return;
    00191     }
    00192
    00193     if (this->bucket_list_iter == this->bucket_list->begin()) {
    00194       if (this->bucket_iter == this->list->buckets.begin()) {
    00195         this->bucket_list = NULL;
    00196         return;
    00197       }
    00198       this->bucket_iter--;
    00199       this->bucket_list = &(*this->bucket_iter).second;
    00200       /* Go to the end of the items in the bucket */
    00201       this->bucket_list_iter = this->bucket_list->begin();
    00202       for (size_t i = this->bucket_list->size(); i > 1; i--) this->bucket_list_iter++;
    00203     } else {
    00204       this->bucket_list_iter--;
    00205     }
    00206     this->item_next = *this->bucket_list_iter;
    00207   }
    00208
    00209   int32 Next()
    00210   {
    00211     if (!this->HasNext()) return 0;
    00212
    00213     int32 item_current = this->item_next;
    00214     FindNext();
    00215     return item_current;
    00216   }
    00217
    00218   void Remove(int item)
    00219   {
    00220     if (!this->HasNext()) return;
    00221
    00222     /* If we remove the 'next' item, skip to the next */
    00223     if (item == this->item_next) {
    00224       FindNext();
    00225       return;
    00226     }
    00227   }
    00228
    00229   bool HasNext()
    00230   {
    00231     return !(this->list->buckets.empty() || this->has_no_more_items);
    00232   }
    00233 };
    00234
    00238 class AIAbstractListSorterItemAscending : public AIAbstractListSorter {
    00239 private:
    00240   AIAbstractList::AIAbstractListMap::iterator item_iter;
    00241   bool has_no_more_items;
    00242   int32 item_next;
    00243
    00244 public:
    00245   AIAbstractListSorterItemAscending(AIAbstractList *list)
    00246   {
    00247     this->list = list;
    00248     this->End();
    00249   }
    00250
    00251   int32 Begin()
    00252   {
    00253     if (this->list->items.empty()) return 0;
    00254     this->has_no_more_items = false;
    00255
    00256     this->item_iter = this->list->items.begin();
    00257     this->item_next = (*this->item_iter).first;
    00258
    00259     int32 item_current = this->item_next;
    00260     FindNext();
    00261     return item_current;
    00262   }
    00263
    00264   void End()
    00265   {
    00266     this->has_no_more_items = true;
    00267   }
    00268
    00269   void FindNext()
    00270   {
    00271     if (this->item_iter == this->list->items.end()) {
    00272       this->has_no_more_items = true;
    00273       return;
    00274     }
    00275     this->item_iter++;
    00276     if (this->item_iter != this->list->items.end()) item_next = (*this->item_iter).first;
    00277   }
    00278
    00279   int32 Next()
    00280   {
    00281     if (!this->HasNext()) return 0;
    00282
    00283     int32 item_current = this->item_next;
    00284     FindNext();
    00285     return item_current;
    00286   }
    00287
    00288   void Remove(int item)
    00289   {
    00290     if (!this->HasNext()) return;
    00291
    00292     /* If we remove the 'next' item, skip to the next */
    00293     if (item == this->item_next) {
    00294       FindNext();
    00295       return;
    00296     }
    00297   }
    00298
    00299   bool HasNext()
    00300   {
    00301     return !(this->list->items.empty() || this->has_no_more_items);
    00302   }
    00303 };
    00304
    00308 class AIAbstractListSorterItemDescending : public AIAbstractListSorter {
    00309 private:
    00310   AIAbstractList::AIAbstractListMap::iterator item_iter;
    00311   bool has_no_more_items;
    00312   int32 item_next;
    00313
    00314 public:
    00315   AIAbstractListSorterItemDescending(AIAbstractList *list)
    00316   {
    00317     this->list = list;
    00318     this->End();
    00319   }
    00320
    00321   int32 Begin()
    00322   {
    00323     if (this->list->items.empty()) return 0;
    00324     this->has_no_more_items = false;
    00325
    00326     this->item_iter = this->list->items.begin();
    00327     for (size_t i = this->list->items.size(); i > 1; i--) this->item_iter++;
    00328     this->item_next = (*this->item_iter).first;
    00329
    00330     int32 item_current = this->item_next;
    00331     FindNext();
    00332     return item_current;
    00333   }
    00334
    00335   void End()
    00336   {
    00337     this->has_no_more_items = true;
    00338   }
    00339
    00340   void FindNext()
    00341   {
    00342     if (this->item_iter == this->list->items.end()) {
    00343       this->has_no_more_items = true;
    00344       return;
    00345     }
    00346     this->item_iter--;
    00347     if (this->item_iter != this->list->items.end()) item_next = (*this->item_iter).first;
    00348   }
    00349
    00350   int32 Next()
    00351   {
    00352     if (!this->HasNext()) return 0;
    00353
    00354     int32 item_current = this->item_next;
    00355     FindNext();
    00356     return item_current;
    00357   }
    00358
    00359   void Remove(int item)
    00360   {
    00361     if (!this->HasNext()) return;
    00362
    00363     /* If we remove the 'next' item, skip to the next */
    00364     if (item == this->item_next) {
    00365       FindNext();
    00366       return;
    00367     }
    00368   }
    00369
    00370   bool HasNext()
    00371   {
    00372     return !(this->list->items.empty() || this->has_no_more_items);
    00373   }
    00374 };
    00375
    00376
    00377
    00378 AIAbstractList::AIAbstractList()
    00379 {
    00380   /* Default sorter */
    00381   this->sorter         = new AIAbstractListSorterValueDescending(this);
    00382   this->sorter_type    = SORT_BY_VALUE;
    00383   this->sort_ascending = false;
    00384   this->initialized    = false;
    00385   this->modifications  = 0;
    00386 }
    00387
    00388 AIAbstractList::~AIAbstractList()
    00389 {
    00390   delete this->sorter;
    00391 }
    00392
    00393 bool AIAbstractList::HasItem(int32 item)
    00394 {
    00395   return this->items.count(item) == 1;
    00396 }
    00397
    00398 void AIAbstractList::Clear()
    00399 {
    00400   this->modifications++;
    00401
    00402   this->items.clear();
    00403   this->buckets.clear();
    00404   this->sorter->End();
    00405 }
    00406
    00407 void AIAbstractList::AddItem(int32 item)
    00408 {
    00409   this->modifications++;
    00410
    00411   if (this->HasItem(item)) return;
    00412
    00413   this->items[item] = 0;
    00414   this->buckets[0].insert(item);
    00415 }
    00416
    00417 void AIAbstractList::RemoveItem(int32 item)
    00418 {
    00419   this->modifications++;
    00420
    00421   if (!this->HasItem(item)) return;
    00422
    00423   int32 value = this->GetValue(item);
    00424
    00425   this->sorter->Remove(item);
    00426   this->buckets[value].erase(item);
    00427   if (this->buckets[value].empty()) this->buckets.erase(value);
    00428   this->items.erase(item);
    00429 }
    00430
    00431 int32 AIAbstractList::Begin()
    00432 {
    00433   this->initialized = true;
    00434   return this->sorter->Begin();
    00435 }
    00436
    00437 int32 AIAbstractList::Next()
    00438 {
    00439   if (this->initialized == false) {
    00440     DEBUG(ai, 0, "Next() is invalid as Begin() is never called");
    00441     return 0;
    00442   }
    00443   return this->sorter->Next();
    00444 }
    00445
    00446 bool AIAbstractList::IsEmpty()
    00447 {
    00448   return this->items.empty();
    00449 }
    00450
    00451 bool AIAbstractList::HasNext()
    00452 {
    00453   if (this->initialized == false) {
    00454     DEBUG(ai, 0, "HasNext() is invalid as Begin() is never called");
    00455     return false;
    00456   }
    00457   return this->sorter->HasNext();
    00458 }
    00459
    00460 int32 AIAbstractList::Count()
    00461 {
    00462   return (int32)this->items.size();
    00463 }
    00464
    00465 int32 AIAbstractList::GetValue(int32 item)
    00466 {
    00467   if (!this->HasItem(item)) return 0;
    00468
    00469   return this->items[item];
    00470 }
    00471
    00472 bool AIAbstractList::SetValue(int32 item, int32 value)
    00473 {
    00474   this->modifications++;
    00475
    00476   if (!this->HasItem(item)) return false;
    00477
    00478   int32 value_old = this->GetValue(item);
    00479
    00480   this->sorter->Remove(item);
    00481   this->buckets[value_old].erase(item);
    00482   if (this->buckets[value_old].empty()) this->buckets.erase(value_old);
    00483   this->items[item] = value;
    00484   this->buckets[value].insert(item);
    00485
    00486   return true;
    00487 }
    00488
    00489 void AIAbstractList::Sort(SorterType sorter, bool ascending)
    00490 {
    00491   this->modifications++;
    00492
    00493   if (sorter != SORT_BY_VALUE && sorter != SORT_BY_ITEM) return;
    00494   if (sorter == this->sorter_type && ascending == this->sort_ascending) return;
    00495
    00496   delete this->sorter;
    00497   switch (sorter) {
    00498     case SORT_BY_ITEM:
    00499       if (ascending) {
    00500         this->sorter = new AIAbstractListSorterItemAscending(this);
    00501       } else {
    00502         this->sorter = new AIAbstractListSorterItemDescending(this);
    00503       }
    00504       break;
    00505
    00506     case SORT_BY_VALUE:
    00507       if (ascending) {
    00508         this->sorter = new AIAbstractListSorterValueAscending(this);
    00509       } else {
    00510         this->sorter = new AIAbstractListSorterValueDescending(this);
    00511       }
    00512       break;
    00513
    00514     default:
    00515       this->Sort(SORT_BY_ITEM, false);
    00516       return;
    00517   }
    00518   this->sorter_type    = sorter;
    00519   this->sort_ascending = ascending;
    00520   this->initialized    = false;
    00521 }
    00522
    00523 void AIAbstractList::AddList(AIAbstractList *list)
    00524 {
    00525   AIAbstractListMap *list_items = &list->items;
    00526   for (AIAbstractListMap::iterator iter = list_items->begin(); iter != list_items->end(); iter++) {
    00527     this->AddItem((*iter).first);
    00528     this->SetValue((*iter).first, (*iter).second);
    00529   }
    00530 }
    00531
    00532 void AIAbstractList::RemoveAboveValue(int32 value)
    00533 {
    00534   this->modifications++;
    00535
    00536   for (AIAbstractListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
    00537     next_iter = iter; next_iter++;
    00538     if ((*iter).second > value) this->RemoveItem((*iter).first);
    00539   }
    00540 }
    00541
    00542 void AIAbstractList::RemoveBelowValue(int32 value)
    00543 {
    00544   this->modifications++;
    00545
    00546   for (AIAbstractListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
    00547     next_iter = iter; next_iter++;
    00548     if ((*iter).second < value) this->RemoveItem((*iter).first);
    00549   }
    00550 }
    00551
    00552 void AIAbstractList::RemoveBetweenValue(int32 start, int32 end)
    00553 {
    00554   this->modifications++;
    00555
    00556   for (AIAbstractListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
    00557     next_iter = iter; next_iter++;
    00558     if ((*iter).second > start && (*iter).second < end) this->RemoveItem((*iter).first);
    00559   }
    00560 }
    00561
    00562 void AIAbstractList::RemoveValue(int32 value)
    00563 {
    00564   this->modifications++;
    00565
    00566   for (AIAbstractListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
    00567     next_iter = iter; next_iter++;
    00568     if ((*iter).second == value) this->RemoveItem((*iter).first);
    00569   }
    00570 }
    00571
    00572 void AIAbstractList::RemoveTop(int32 count)
    00573 {
    00574   this->modifications++;
    00575
    00576   if (!this->sort_ascending) {
    00577     this->Sort(this->sorter_type, !this->sort_ascending);
    00578     this->RemoveBottom(count);
    00579     this->Sort(this->sorter_type, !this->sort_ascending);
    00580     return;
    00581   }
    00582
    00583   switch (this->sorter_type) {
    00584     default: NOT_REACHED();
    00585     case SORT_BY_VALUE:
    00586       for (AIAbstractListBucket::iterator iter = this->buckets.begin(); iter != this->buckets.end(); iter = this->buckets.begin()) {
    00587         AIItemList *items = &(*iter).second;
    00588         size_t size = items->size();
    00589         for (AIItemList::iterator iter = items->begin(); iter != items->end(); iter = items->begin()) {
    00590           if (--count < 0) return;
    00591           this->RemoveItem(*iter);
    00592           /* When the last item is removed from the bucket, the bucket itself is removed.
    00593            * This means that the iterators can be invalid after a call to RemoveItem.
    00594            */
    00595           if (--size == 0) break;
    00596         }
    00597       }
    00598       break;
    00599
    00600     case SORT_BY_ITEM:
    00601       for (AIAbstractListMap::iterator iter = this->items.begin(); iter != this->items.end(); iter = this->items.begin()) {
    00602         if (--count < 0) return;
    00603         this->RemoveItem((*iter).first);
    00604       }
    00605       break;
    00606   }
    00607 }
    00608
    00609 void AIAbstractList::RemoveBottom(int32 count)
    00610 {
    00611   this->modifications++;
    00612
    00613   if (!this->sort_ascending) {
    00614     this->Sort(this->sorter_type, !this->sort_ascending);
    00615     this->RemoveTop(count);
    00616     this->Sort(this->sorter_type, !this->sort_ascending);
    00617     return;
    00618   }
    00619
    00620   switch (this->sorter_type) {
    00621     default: NOT_REACHED();
    00622     case SORT_BY_VALUE:
    00623       for (AIAbstractListBucket::reverse_iterator iter = this->buckets.rbegin(); iter != this->buckets.rend(); iter = this->buckets.rbegin()) {
    00624         AIItemList *items = &(*iter).second;
    00625         size_t size = items->size();
    00626         for (AIItemList::reverse_iterator iter = items->rbegin(); iter != items->rend(); iter = items->rbegin()) {
    00627           if (--count < 0) return;
    00628           this->RemoveItem(*iter);
    00629           /* When the last item is removed from the bucket, the bucket itself is removed.
    00630            * This means that the iterators can be invalid after a call to RemoveItem.
    00631            */
    00632           if (--size == 0) break;
    00633         }
    00634       }
    00635
    00636     case SORT_BY_ITEM:
    00637       for (AIAbstractListMap::reverse_iterator iter = this->items.rbegin(); iter != this->items.rend(); iter = this->items.rbegin()) {
    00638         if (--count < 0) return;
    00639         this->RemoveItem((*iter).first);
    00640       }
    00641       break;
    00642   }
    00643 }
    00644
    00645 void AIAbstractList::RemoveList(AIAbstractList *list)
    00646 {
    00647   this->modifications++;
    00648
    00649   AIAbstractListMap *list_items = &list->items;
    00650   for (AIAbstractListMap::iterator iter = list_items->begin(); iter != list_items->end(); iter++) {
    00651     this->RemoveItem((*iter).first);
    00652   }
    00653 }
    00654
    00655 void AIAbstractList::KeepAboveValue(int32 value)
    00656 {
    00657   this->modifications++;
    00658
    00659   for (AIAbstractListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
    00660     next_iter = iter; next_iter++;
    00661     if ((*iter).second <= value) this->RemoveItem((*iter).first);
    00662   }
    00663 }
    00664
    00665 void AIAbstractList::KeepBelowValue(int32 value)
    00666 {
    00667   this->modifications++;
    00668
    00669   for (AIAbstractListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
    00670     next_iter = iter; next_iter++;
    00671     if ((*iter).second >= value) this->RemoveItem((*iter).first);
    00672   }
    00673 }
    00674
    00675 void AIAbstractList::KeepBetweenValue(int32 start, int32 end)
    00676 {
    00677   this->modifications++;
    00678
    00679   for (AIAbstractListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
    00680     next_iter = iter; next_iter++;
    00681     if ((*iter).second <= start || (*iter).second >= end) this->RemoveItem((*iter).first);
    00682   }
    00683 }
    00684
    00685 void AIAbstractList::KeepValue(int32 value)
    00686 {
    00687   this->modifications++;
    00688
    00689   for (AIAbstractListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
    00690     next_iter = iter; next_iter++;
    00691     if ((*iter).second != value) this->RemoveItem((*iter).first);
    00692   }
    00693 }
    00694
    00695 void AIAbstractList::KeepTop(int32 count)
    00696 {
    00697   this->modifications++;
    00698
    00699   this->RemoveBottom(this->Count() - count);
    00700 }
    00701
    00702 void AIAbstractList::KeepBottom(int32 count)
    00703 {
    00704   this->modifications++;
    00705
    00706   this->RemoveTop(this->Count() - count);
    00707 }
    00708
    00709 void AIAbstractList::KeepList(AIAbstractList *list)
    00710 {
    00711   this->modifications++;
    00712
    00713   AIAbstractList tmp;
    00714   for (AIAbstractListMap::iterator iter = this->items.begin(); iter != this->items.end(); iter++) {
    00715     tmp.AddItem((*iter).first);
    00716     tmp.SetValue((*iter).first, (*iter).second);
    00717   }
    00718
    00719   tmp.RemoveList(list);
    00720   this->RemoveList(&tmp);
    00721 }
    00722
    00723 SQInteger AIAbstractList::_get(HSQUIRRELVM vm)
    00724 {
    00725   if (sq_gettype(vm, 2) != OT_INTEGER) return SQ_ERROR;
    00726
    00727   SQInteger idx;
    00728   sq_getinteger(vm, 2, &idx);
    00729
    00730   if (!this->HasItem(idx)) return SQ_ERROR;
    00731
    00732   sq_pushinteger(vm, this->GetValue(idx));
    00733   return 1;
    00734 }
    00735
    00736 SQInteger AIAbstractList::_nexti(HSQUIRRELVM vm)
    00737 {
    00738   if (sq_gettype(vm, 2) == OT_NULL) {
    00739     if (this->IsEmpty()) {
    00740       sq_pushnull(vm);
    00741       return 1;
    00742     }
    00743     sq_pushinteger(vm, this->Begin());
    00744     return 1;
    00745   }
    00746
    00747   SQInteger idx;
    00748   sq_getinteger(vm, 2, &idx);
    00749
    00750   int val = this->Next();
    00751   if (!this->HasNext()) {
    00752     sq_pushnull(vm);
    00753     return 1;
    00754   }
    00755
    00756   sq_pushinteger(vm, val);
    00757   return 1;
    00758 }
    00759
    00760 SQInteger AIAbstractList::Valuate(HSQUIRRELVM vm)
    00761 {
    00762   this->modifications++;
    00763
    00764   /* The first parameter is the instance of AIAbstractList. */
    00765   int nparam = sq_gettop(vm) - 1;
    00766
    00767   if (nparam < 1) {
    00768     return sq_throwerror(vm, _SC("You need to give a least a Valuator as parameter to AIAbstractList::Valuate"));
    00769   }
    00770
    00771   /* Make sure the valuator function is really a function, and not any
    00772    * other type. It's parameter 2 for us, but for the user it's the
    00773    * first parameter they give. */
    00774   SQObjectType valuator_type = sq_gettype(vm, 2);
    00775   if (valuator_type != OT_CLOSURE && valuator_type != OT_NATIVECLOSURE) {
    00776     return sq_throwerror(vm, _SC("parameter 1 has an invalid type (expected function)"));
    00777   }
    00778
    00779   /* Don't allow docommand from a Valuator, as we can't resume in
    00780    * mid C++-code. */
    00781   bool backup_allow = AIObject::GetAllowDoCommand();
    00782   AIObject::SetAllowDoCommand(false);
    00783
    00784   /* Push the function to call */
    00785   sq_push(vm, 2);
    00786
    00787   /* Walk all items, and query the result */
    00788   this->buckets.clear();
    00789
    00790   /* Check for changing of items. */
    00791   int begin_modification_count = this->modifications;
    00792
    00793   for (AIAbstractListMap::iterator iter = this->items.begin(); iter != this->items.end(); iter++) {
    00794     /* Push the root table as instance object, this is what squirrel does for meta-functions. */
    00795     sq_pushroottable(vm);
    00796     /* Push all arguments for the valuator function. */
    00797     sq_pushinteger(vm, (*iter).first);
    00798     for (int i = 0; i < nparam - 1; i++) {
    00799       sq_push(vm, i + 3);
    00800     }
    00801
    00802     /* Call the function. Squirrel pops all parameters and pushes the return value. */
    00803     if (SQ_FAILED(sq_call(vm, nparam + 1, SQTrue, SQTrue))) {
    00804       AIObject::SetAllowDoCommand(backup_allow);
    00805       return SQ_ERROR;
    00806     }
    00807
    00808     /* Retreive the return value */
    00809     SQInteger value;
    00810     switch (sq_gettype(vm, -1)) {
    00811       case OT_INTEGER: {
    00812         sq_getinteger(vm, -1, &value);
    00813       } break;
    00814
    00815       case OT_BOOL: {
    00816         SQBool v;
    00817         sq_getbool(vm, -1, &v);
    00818         value = v ? 1 : 0;
    00819       } break;
    00820
    00821       default: {
    00822         /* See below for explanation. The extra pop is the return value. */
    00823         sq_pop(vm, nparam + 4);
    00824
    00825         AIObject::SetAllowDoCommand(backup_allow);
    00826         return sq_throwerror(vm, _SC("return value of valuator is not valid (not integer/bool)"));
    00827       }
    00828     }
    00829
    00830     /* Was something changed? */
    00831     if (begin_modification_count != this->modifications) {
    00832       /* See below for explanation. The extra pop is the return value. */
    00833       sq_pop(vm, nparam + 4);
    00834
    00835       AIObject::SetAllowDoCommand(backup_allow);
    00836       return sq_throwerror(vm, _SC("modifying valuated list outside of valuator function"));
    00837     }
    00838
    00839     (*iter).second = (int32)value;
    00840     this->buckets[(int32)value].insert((*iter).first);
    00841
    00842     /* Pop the return value. */
    00843     sq_poptop(vm);
    00844
    00845     Squirrel::DecreaseOps(vm, 5);
    00846   }
    00847   /* Pop from the squirrel stack:
    00848    * 1. The root stable (as instance object).
    00849    * 2. The valuator function.
    00850    * 3. The parameters given to this function.
    00851    * 4. The AIAbstractList instance object. */
    00852   sq_pop(vm, nparam + 3);
    00853
    00854   AIObject::SetAllowDoCommand(backup_allow);
    00855   return 0;
    00856 }