src/ai/api/ai_abstractlist.cpp
branchnoai
changeset 11058 3305a425f55b
parent 10957 7a140b4cd91d
child 11059 b1751c5973cc
equal deleted inserted replaced
11057:188a9ca6d8de 11058:3305a425f55b
    32 
    32 
    33 	/**
    33 	/**
    34 	 * See if there is a next item of the sorter.
    34 	 * See if there is a next item of the sorter.
    35 	 */
    35 	 */
    36 	virtual bool HasNext() = 0;
    36 	virtual bool HasNext() = 0;
       
    37 
       
    38 	/**
       
    39 	 * Callback from the list if an item gets removed.
       
    40 	 */
       
    41 	virtual void Remove(int item) = 0;
    37 };
    42 };
    38 
    43 
    39 /**
    44 /**
    40  * Sort by value, ascending.
    45  * Sort by value, ascending.
    41  */
    46  */
    42 class AIAbstractListSorterValueAscending : public AIAbstractListSorter {
    47 class AIAbstractListSorterValueAscending : public AIAbstractListSorter {
    43 private:
    48 private:
    44 	AIAbstractList::AIAbstractListBucket::iterator bucket_iter;
    49 	AIAbstractList::AIAbstractListBucket::iterator bucket_iter;
    45 	AIAbstractList::AIItemList *bucket_list;
    50 	AIAbstractList::AIItemList *bucket_list;
    46 	AIAbstractList::AIItemList::iterator bucket_list_iter;
    51 	AIAbstractList::AIItemList::iterator bucket_list_iter;
       
    52 	bool has_no_more_items;
       
    53 	int32 item_next;
    47 
    54 
    48 public:
    55 public:
    49 	AIAbstractListSorterValueAscending(AIAbstractList *list)
    56 	AIAbstractListSorterValueAscending(AIAbstractList *list)
    50 	{
    57 	{
    51 		this->list = list;
    58 		this->list = list;
    52 		this->bucket_list = NULL;
    59 		this->bucket_list = NULL;
       
    60 		this->has_no_more_items = true;
       
    61 
       
    62 		this->item_next = 0;
    53 	}
    63 	}
    54 
    64 
    55 	int32 Begin()
    65 	int32 Begin()
    56 	{
    66 	{
    57 		if (this->list->buckets.empty()) return 0;
    67 		if (this->list->buckets.empty()) return 0;
       
    68 		this->has_no_more_items = false;
    58 
    69 
    59 		this->bucket_iter = this->list->buckets.begin();
    70 		this->bucket_iter = this->list->buckets.begin();
    60 		this->bucket_list = &(*this->bucket_iter).second;
    71 		this->bucket_list = &(*this->bucket_iter).second;
    61 		this->bucket_list_iter = this->bucket_list->begin();
    72 		this->bucket_list_iter = this->bucket_list->begin();
    62 		return *bucket_list_iter;
    73 		this->item_next = *this->bucket_list_iter;
    63 	}
    74 
    64 
    75 		int32 item_current = this->item_next;
    65 	int32 Next()
    76 		FindNext();
    66 	{
    77 		return item_current;
    67 		if (this->list->buckets.empty() || this->bucket_list == NULL) return 0;
    78 	}
       
    79 
       
    80 	void FindNext()
       
    81 	{
       
    82 		if (this->bucket_list == NULL) {
       
    83 			this->has_no_more_items = true;
       
    84 			return;
       
    85 		}
    68 
    86 
    69 		this->bucket_list_iter++;
    87 		this->bucket_list_iter++;
    70 		if (this->bucket_list_iter == this->bucket_list->end()) {
    88 		if (this->bucket_list_iter == this->bucket_list->end()) {
    71 			this->bucket_iter++;
    89 			this->bucket_iter++;
    72 			if (this->bucket_iter == this->list->buckets.end()) return 0;
    90 			if (this->bucket_iter == this->list->buckets.end()) {
       
    91 				this->bucket_list = NULL;
       
    92 				return;
       
    93 			}
    73 			this->bucket_list = &(*this->bucket_iter).second;
    94 			this->bucket_list = &(*this->bucket_iter).second;
    74 			this->bucket_list_iter = this->bucket_list->begin();
    95 			this->bucket_list_iter = this->bucket_list->begin();
    75 		}
    96 		}
    76 		return *bucket_list_iter;
    97 		this->item_next = *this->bucket_list_iter;
       
    98 	}
       
    99 
       
   100 	int32 Next()
       
   101 	{
       
   102 		if (!this->HasNext()) return 0;
       
   103 
       
   104 		int32 item_current = this->item_next;
       
   105 		FindNext();
       
   106 		return item_current;
       
   107 	}
       
   108 
       
   109 	void Remove(int item)
       
   110 	{
       
   111 		if (!this->HasNext()) return;
       
   112 
       
   113 		/* If we remove the 'next' item, skip to the next */
       
   114 		if (item == this->item_next) {
       
   115 			FindNext();
       
   116 			return;
       
   117 		}
    77 	}
   118 	}
    78 
   119 
    79 	bool HasNext()
   120 	bool HasNext()
    80 	{
   121 	{
    81 		if (this->list->buckets.empty() || this->bucket_list == NULL) return false;
   122 		return !(this->list->buckets.empty() || this->has_no_more_items);
    82 
       
    83 		return this->bucket_iter != this->list->buckets.end() && this->bucket_list_iter != this->bucket_list->end();
       
    84 	}
   123 	}
    85 };
   124 };
    86 
   125 
    87 /**
   126 /**
    88  * Sort by value, descending.
   127  * Sort by value, descending.
    89  */
   128  */
    90 class AIAbstractListSorterValueDescending : public AIAbstractListSorter {
   129 class AIAbstractListSorterValueDescending : public AIAbstractListSorter {
    91 private:
   130 private:
    92 	AIAbstractList::AIAbstractListBucket::reverse_iterator bucket_iter;
   131 	AIAbstractList::AIAbstractListBucket::iterator bucket_iter;
    93 	AIAbstractList::AIItemList *bucket_list;
   132 	AIAbstractList::AIItemList *bucket_list;
    94 	AIAbstractList::AIItemList::reverse_iterator bucket_list_iter;
   133 	AIAbstractList::AIItemList::iterator bucket_list_iter;
       
   134 	bool has_no_more_items;
       
   135 	int32 item_next;
    95 
   136 
    96 public:
   137 public:
    97 	AIAbstractListSorterValueDescending(AIAbstractList *list)
   138 	AIAbstractListSorterValueDescending(AIAbstractList *list)
    98 	{
   139 	{
    99 		this->list = list;
   140 		this->list = list;
   100 		this->bucket_list = NULL;
   141 		this->bucket_list = NULL;
       
   142 		this->has_no_more_items = true;
       
   143 
       
   144 		this->item_next = 0;
   101 	}
   145 	}
   102 
   146 
   103 	int32 Begin()
   147 	int32 Begin()
   104 	{
   148 	{
   105 		if (this->list->buckets.empty()) return 0;
   149 		if (this->list->buckets.empty()) return 0;
   106 
   150 		this->has_no_more_items = false;
   107 		this->bucket_iter = this->list->buckets.rbegin();
   151 
       
   152 		/* Go to the end of the bucket-list */
       
   153 		this->bucket_iter = this->list->buckets.begin();
       
   154 		for (int i = this->list->buckets.size(); i > 1; i--) this->bucket_iter++;
   108 		this->bucket_list = &(*this->bucket_iter).second;
   155 		this->bucket_list = &(*this->bucket_iter).second;
   109 		this->bucket_list_iter = this->bucket_list->rbegin();
   156 
   110 		return *bucket_list_iter;
   157 		/* Go to the end of the items in the bucket */
       
   158 		this->bucket_list_iter = this->bucket_list->begin();
       
   159 		for (int i = this->bucket_list->size(); i > 1; i--) this->bucket_list_iter++;
       
   160 		this->item_next = *this->bucket_list_iter;
       
   161 
       
   162 		int32 item_current = this->item_next;
       
   163 		FindNext();
       
   164 		return item_current;
       
   165 	}
       
   166 
       
   167 	void FindNext()
       
   168 	{
       
   169 		if (this->bucket_list == NULL) {
       
   170 			this->has_no_more_items = true;
       
   171 			return;
       
   172 		}
       
   173 
       
   174 		if (this->bucket_list_iter == this->bucket_list->begin()) {
       
   175 			if (this->bucket_iter == this->list->buckets.begin()) {
       
   176 				this->bucket_list = NULL;
       
   177 				return;
       
   178 			}
       
   179 			this->bucket_iter--;
       
   180 			this->bucket_list = &(*this->bucket_iter).second;
       
   181 			/* Go to the end of the items in the bucket */
       
   182 			this->bucket_list_iter = this->bucket_list->begin();
       
   183 			for (int i = this->bucket_list->size(); i > 1; i--) this->bucket_list_iter++;
       
   184 		} else {
       
   185 			this->bucket_list_iter--;
       
   186 		}
       
   187 		this->item_next = *this->bucket_list_iter;
   111 	}
   188 	}
   112 
   189 
   113 	int32 Next()
   190 	int32 Next()
   114 	{
   191 	{
   115 		if (this->list->buckets.empty() || this->bucket_list == NULL) return 0;
   192 		if (!this->HasNext()) return 0;
   116 
   193 
   117 		this->bucket_list_iter++;
   194 		int32 item_current = this->item_next;
   118 		if (this->bucket_list_iter == this->bucket_list->rend()) {
   195 		FindNext();
   119 			this->bucket_iter++;
   196 		return item_current;
   120 			if (this->bucket_iter == this->list->buckets.rend()) return 0;
   197 	}
   121 			this->bucket_list = &(*this->bucket_iter).second;
   198 
   122 			this->bucket_list_iter = this->bucket_list->rbegin();
   199 	void Remove(int item)
   123 		}
   200 	{
   124 		return *bucket_list_iter;
   201 		if (!this->HasNext()) return;
       
   202 
       
   203 		/* If we remove the 'next' item, skip to the next */
       
   204 		if (item == this->item_next) {
       
   205 			FindNext();
       
   206 			return;
       
   207 		}
   125 	}
   208 	}
   126 
   209 
   127 	bool HasNext()
   210 	bool HasNext()
   128 	{
   211 	{
   129 		if (this->list->buckets.empty() || this->bucket_list == NULL) return false;
   212 		return !(this->list->buckets.empty() || this->has_no_more_items);
   130 
       
   131 		return this->bucket_iter != this->list->buckets.rend() && this->bucket_list_iter != this->bucket_list->rend();
       
   132 	}
   213 	}
   133 };
   214 };
   134 
   215 
   135 /**
   216 /**
   136  * Sort by item, ascending.
   217  * Sort by item, ascending.
   137  */
   218  */
   138 class AIAbstractListSorterItemAscending : public AIAbstractListSorter {
   219 class AIAbstractListSorterItemAscending : public AIAbstractListSorter {
   139 private:
   220 private:
   140 	AIAbstractList::AIAbstractListMap::iterator item_iter;
   221 	AIAbstractList::AIAbstractListMap::iterator item_iter;
       
   222 	bool has_no_more_items;
       
   223 	int32 item_next;
   141 
   224 
   142 public:
   225 public:
   143 	AIAbstractListSorterItemAscending(AIAbstractList *list)
   226 	AIAbstractListSorterItemAscending(AIAbstractList *list)
   144 	{
   227 	{
   145 		this->list = list;
   228 		this->list = list;
       
   229 		this->has_no_more_items = true;
   146 	}
   230 	}
   147 
   231 
   148 	int32 Begin()
   232 	int32 Begin()
   149 	{
   233 	{
   150 		if (this->list->items.empty()) return 0;
   234 		if (this->list->items.empty()) return 0;
       
   235 		this->has_no_more_items = false;
   151 
   236 
   152 		this->item_iter = this->list->items.begin();
   237 		this->item_iter = this->list->items.begin();
   153 		return (*this->item_iter).first;
   238 		this->item_next = (*this->item_iter).first;
       
   239 
       
   240 		int32 item_current = this->item_next;
       
   241 		FindNext();
       
   242 		return item_current;
       
   243 	}
       
   244 
       
   245 	void FindNext()
       
   246 	{
       
   247 		if (this->item_iter == this->list->items.end()) {
       
   248 			this->has_no_more_items = true;
       
   249 			return;
       
   250 		}
       
   251 		this->item_iter++;
       
   252 		if (this->item_iter != this->list->items.end()) item_next = (*this->item_iter).first;
   154 	}
   253 	}
   155 
   254 
   156 	int32 Next()
   255 	int32 Next()
   157 	{
   256 	{
   158 		if (this->list->items.empty()) return 0;
   257 		if (!this->HasNext()) return 0;
   159 
   258 
   160 		this->item_iter++;
   259 		int32 item_current = this->item_next;
   161 		return (*this->item_iter).first;
   260 		FindNext();
       
   261 		return item_current;
       
   262 	}
       
   263 
       
   264 	void Remove(int item) {
       
   265 		if (!this->HasNext()) return;
       
   266 
       
   267 		/* If we remove the 'next' item, skip to the next */
       
   268 		if (item == this->item_next) {
       
   269 			FindNext();
       
   270 			return;
       
   271 		}
   162 	}
   272 	}
   163 
   273 
   164 	bool HasNext()
   274 	bool HasNext()
   165 	{
   275 	{
   166 		if (this->list->items.empty()) return false;
   276 		return !(this->list->items.empty() || this->has_no_more_items);
   167 
       
   168 		return this->item_iter != this->list->items.end();
       
   169 	}
   277 	}
   170 };
   278 };
   171 
   279 
   172 /**
   280 /**
   173  * Sort by item, descending.
   281  * Sort by item, descending.
   174  */
   282  */
   175 class AIAbstractListSorterItemDescending : public AIAbstractListSorter {
   283 class AIAbstractListSorterItemDescending : public AIAbstractListSorter {
   176 private:
   284 private:
   177 	AIAbstractList::AIAbstractListMap::reverse_iterator item_iter;
   285 	AIAbstractList::AIAbstractListMap::reverse_iterator item_iter;
       
   286 	bool has_no_more_items;
       
   287 	int32 item_next;
   178 
   288 
   179 public:
   289 public:
   180 	AIAbstractListSorterItemDescending(AIAbstractList *list)
   290 	AIAbstractListSorterItemDescending(AIAbstractList *list)
   181 	{
   291 	{
   182 		this->list = list;
   292 		this->list = list;
       
   293 		this->has_no_more_items = true;
   183 	}
   294 	}
   184 
   295 
   185 	int32 Begin()
   296 	int32 Begin()
   186 	{
   297 	{
   187 		if (this->list->items.empty()) return 0;
   298 		if (this->list->items.empty()) return 0;
       
   299 		this->has_no_more_items = false;
   188 
   300 
   189 		this->item_iter = this->list->items.rbegin();
   301 		this->item_iter = this->list->items.rbegin();
   190 		return (*this->item_iter).first;
   302 		this->item_next = (*this->item_iter).first;
       
   303 
       
   304 		int32 item_current = this->item_next;
       
   305 		FindNext();
       
   306 		return item_current;
       
   307 	}
       
   308 
       
   309 	void FindNext()
       
   310 	{
       
   311 		if (this->item_iter == this->list->items.rend()) {
       
   312 			this->has_no_more_items = true;
       
   313 			return;
       
   314 		}
       
   315 		this->item_iter++;
       
   316 		if (this->item_iter != this->list->items.rend()) item_next = (*this->item_iter).first;
   191 	}
   317 	}
   192 
   318 
   193 	int32 Next()
   319 	int32 Next()
   194 	{
   320 	{
   195 		if (this->list->items.empty()) return 0;
   321 		if (!this->HasNext()) return 0;
   196 
   322 
   197 		this->item_iter++;
   323 		int32 item_current = this->item_next;
   198 		return (*this->item_iter).first;
   324 		FindNext();
       
   325 		return item_current;
       
   326 	}
       
   327 
       
   328 	void Remove(int item)
       
   329 	{
       
   330 		if (!this->HasNext()) return;
       
   331 
       
   332 		/* If we remove the 'next' item, skip to the next */
       
   333 		if (item == this->item_next) {
       
   334 			FindNext();
       
   335 			return;
       
   336 		}
   199 	}
   337 	}
   200 
   338 
   201 	bool HasNext()
   339 	bool HasNext()
   202 	{
   340 	{
   203 		if (this->list->items.empty()) return false;
   341 		return !(this->list->items.empty() || this->has_no_more_items);
   204 
       
   205 		return this->item_iter != this->list->items.rend();
       
   206 	}
   342 	}
   207 };
   343 };
   208 
   344 
   209 
   345 
   210 
   346 
   243 
   379 
   244 void AIAbstractList::RemoveItem(int32 item)
   380 void AIAbstractList::RemoveItem(int32 item)
   245 {
   381 {
   246 	if (!this->HasItem(item)) return;
   382 	if (!this->HasItem(item)) return;
   247 
   383 
   248 	this->buckets[this->GetValue(item)].erase(item);
   384 	int32 value = this->GetValue(item);
   249 	if (this->buckets[this->GetValue(item)].empty()) this->buckets.erase(this->GetValue(item));
   385 
       
   386 	this->sorter->Remove(item);
       
   387 	this->buckets[value].erase(item);
       
   388 	if (this->buckets[value].empty()) this->buckets.erase(value);
   250 	this->items.erase(item);
   389 	this->items.erase(item);
   251 }
   390 }
   252 
   391 
   253 int32 AIAbstractList::Begin()
   392 int32 AIAbstractList::Begin()
   254 {
   393 {
   293 
   432 
   294 bool AIAbstractList::SetValue(int32 item, int32 value)
   433 bool AIAbstractList::SetValue(int32 item, int32 value)
   295 {
   434 {
   296 	if (!this->HasItem(item)) return false;
   435 	if (!this->HasItem(item)) return false;
   297 
   436 
   298 	this->buckets[this->GetValue(item)].erase(item);
   437 	int32 value_old = this->GetValue(item);
   299 	if (this->buckets[this->GetValue(item)].empty()) this->buckets.erase(this->GetValue(item));
   438 
       
   439 	this->sorter->Remove(item);
       
   440 	this->buckets[value_old].erase(item);
       
   441 	if (this->buckets[value_old].empty()) this->buckets.erase(value_old);
   300 	this->items[item] = value;
   442 	this->items[item] = value;
   301 	this->buckets[value].insert(item);
   443 	this->buckets[value].insert(item);
   302 
   444 
   303 	return true;
   445 	return true;
   304 }
   446 }
   537 
   679 
   538 	tmp.RemoveList(list);
   680 	tmp.RemoveList(list);
   539 	this->RemoveList(&tmp);
   681 	this->RemoveList(&tmp);
   540 }
   682 }
   541 
   683 
       
   684 SQInteger AIAbstractList::_get(HSQUIRRELVM vm) {
       
   685 	if (sq_gettype(vm, 2) != OT_INTEGER) return SQ_ERROR;
       
   686 
       
   687 	SQInteger idx;
       
   688 	sq_getinteger(vm, 2, &idx);
       
   689 
       
   690 	if (!this->HasItem(idx)) return SQ_ERROR;
       
   691 
       
   692 	sq_pushinteger(vm, this->GetValue(idx));
       
   693 	return 1;
       
   694 }
       
   695 
       
   696 SQInteger AIAbstractList::_nexti(HSQUIRRELVM vm) {
       
   697 	if (sq_gettype(vm, 2) == OT_NULL) {
       
   698 		sq_pushinteger(vm, this->Begin());
       
   699 		return 1;
       
   700 	}
       
   701 
       
   702 	SQInteger idx;
       
   703 	sq_getinteger(vm, 2, &idx);
       
   704 
       
   705 	int val = this->Next();
       
   706 	if (!this->HasNext()) {
       
   707 		sq_pushnull(vm);
       
   708 		return 1;
       
   709 	}
       
   710 
       
   711 	sq_pushinteger(vm, val);
       
   712 	return 1;
       
   713 }
       
   714 
   542 SQInteger AIAbstractList::Valuate(HSQUIRRELVM vm) {
   715 SQInteger AIAbstractList::Valuate(HSQUIRRELVM vm) {
   543 	int nparam = sq_gettop(vm) - 2;
   716 	int nparam = sq_gettop(vm) - 2;
   544 
   717 
   545 	/* Get the list instance and the function to call */
   718 	/* Get the list instance and the function to call */
   546 	HSQOBJECT obj_list, obj_func;
   719 	HSQOBJECT obj_list, obj_func;
   547 	sq_getstackobj(vm, 1, &obj_list);
   720 	sq_getstackobj(vm, 1, &obj_list);
   548 	sq_getstackobj(vm, 2, &obj_func);
   721 	sq_getstackobj(vm, 2, &obj_func);
   549 
   722 
   550 	if (sq_isclass(obj_list)) {
   723 	if (sq_isclass(obj_list)) {
   551 		sq_throwerror(vm, _SC("parameter 1 has an invalid type (expected instance)"));
   724 		return sq_throwerror(vm, _SC("parameter 1 has an invalid type (expected instance)"));
   552 		return -1;
       
   553 	}
   725 	}
   554 	if (sq_isfunction(obj_func)) {
   726 	if (sq_isfunction(obj_func)) {
   555 		sq_throwerror(vm, _SC("parameter 2 has an invalid type (expected function)"));
   727 		return sq_throwerror(vm, _SC("parameter 2 has an invalid type (expected function)"));
   556 		return -1;
       
   557 	}
   728 	}
   558 
   729 
   559 	sq_addref(vm, &obj_func);
   730 	sq_addref(vm, &obj_func);
   560 
   731 
   561 	/* Read the params */
   732 	/* Read the params */
   580 		for (int i = 0; i < nparam; i++) {
   751 		for (int i = 0; i < nparam; i++) {
   581 			sq_pushobject(vm, obj_params[i]);
   752 			sq_pushobject(vm, obj_params[i]);
   582 		}
   753 		}
   583 
   754 
   584 		/* Call the function */
   755 		/* Call the function */
   585 		if (SQ_FAILED(sq_call(vm, nparam + 2, SQTrue, SQTrue))) return -1;
   756 		if (SQ_FAILED(sq_call(vm, nparam + 2, SQTrue, SQTrue))) return SQ_ERROR;
   586 
   757 
   587 		/* Retreive the return value */
   758 		/* Retreive the return value */
   588 		SQInteger value;
   759 		SQInteger value;
   589 		switch (sq_gettype(vm, -1)) {
   760 		switch (sq_gettype(vm, -1)) {
   590 			case OT_INTEGER: {
   761 			case OT_INTEGER: {
   600 			default: {
   771 			default: {
   601 				sq_pop(vm, 3);
   772 				sq_pop(vm, 3);
   602 				sq_release(vm, &obj_func);
   773 				sq_release(vm, &obj_func);
   603 				for (int i = 0; i < nparam; i++) sq_release(vm, &obj_params[i]);
   774 				for (int i = 0; i < nparam; i++) sq_release(vm, &obj_params[i]);
   604 
   775 
   605 				sq_throwerror(vm, _SC("return value of valuator is not valid (not integer/bool)"));
   776 				return sq_throwerror(vm, _SC("return value of valuator is not valid (not integer/bool)"));
   606 				return -1;
       
   607 			}
   777 			}
   608 		}
   778 		}
   609 		/* Remove junk */
   779 		/* Remove junk */
   610 		sq_pop(vm, 2);
   780 		sq_pop(vm, 2);
   611 
   781