# ai_abstractlist.cpp

Go to the documentation of this file.

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