/**

 * Base class for any ScriptList sorter.

 */

class ScriptListSorter {

protected:

	bool has_no_more_items; ///< Whether we have more items to iterate over.

public:

	/**

	 * Virtual dtor, needed to mute warnings.

	 */

	virtual ~ScriptListSorter() { }

	/**

	 * Get the first item of the sorter.

	 */

	/**

	 * Stop iterating a sorter.

	 */

	virtual void End() = 0;

	/**

	 * Get the next item of the sorter.

	 */

	/**

	 * See if the sorter has reached the end.

	 */

	bool IsEnd()

	{

	ScriptListSorterValueAscending(ScriptList *list)

	{

		this->list = list;

		this->End();

	}

	{

		if (this->list->buckets.empty()) return 0;

		this->has_no_more_items = false;

		this->bucket_iter = this->list->buckets.begin();

		this->bucket_list = &(*this->bucket_iter).second;

		this->bucket_list_iter = this->bucket_list->begin();

		this->item_next = *this->bucket_list_iter;

		FindNext();

		return item_current;

	}

	void End()

	{

			this->bucket_list = &(*this->bucket_iter).second;

			this->bucket_list_iter = this->bucket_list->begin();

		}

		this->item_next = *this->bucket_list_iter;

	}

	{

		if (this->IsEnd()) return 0;

		FindNext();

		return item_current;

	}

	void Remove(int item)

	{

	ScriptListSorterValueDescending(ScriptList *list)

	{

		this->list = list;

		this->End();

	}

	{

		if (this->list->buckets.empty()) return 0;

		this->has_no_more_items = false;

		/* Go to the end of the bucket-list */

		this->bucket_iter = this->list->buckets.end();

		/* Go to the end of the items in the bucket */

		this->bucket_list_iter = this->bucket_list->end();

		--this->bucket_list_iter;

		this->item_next = *this->bucket_list_iter;

		FindNext();

		return item_current;

	}

	void End()

	{

		} else {

			this->bucket_list_iter--;

		}

		this->item_next = *this->bucket_list_iter;

	}

	{

		if (this->IsEnd()) return 0;

		FindNext();

		return item_current;

	}

	void Remove(int item)

	{

	ScriptListSorterItemAscending(ScriptList *list)

	{

		this->list = list;

		this->End();

	}

	{

		if (this->list->items.empty()) return 0;

		this->has_no_more_items = false;

		this->item_iter = this->list->items.begin();

		this->item_next = (*this->item_iter).first;

		FindNext();

		return item_current;

	}

	void End()

	{

			return;

		}

		this->item_iter++;

		if (this->item_iter != this->list->items.end()) item_next = (*this->item_iter).first;

	}

	{

		if (this->IsEnd()) return 0;

		FindNext();

		return item_current;

	}

	void Remove(int item)

	{

	ScriptListSorterItemDescending(ScriptList *list)

	{

		this->list = list;

		this->End();

	}

	{

		if (this->list->items.empty()) return 0;

		this->has_no_more_items = false;

		this->item_iter = this->list->items.end();

		--this->item_iter;

		this->item_next = (*this->item_iter).first;

		FindNext();

		return item_current;

	}

	void End()

	{

		} else {

			this->item_iter--;

		}

		if (this->item_iter != this->list->items.end()) item_next = (*this->item_iter).first;

	}

	{

		if (this->IsEnd()) return 0;

		FindNext();

		return item_current;

	}

	void Remove(int item)

	{

ScriptList::~ScriptList()

{

	delete this->sorter;

}

{

	return this->items.count(item) == 1;

}

void ScriptList::Clear()

{

	this->items.clear();

	this->buckets.clear();

	this->sorter->End();

}

{

	this->modifications++;

	if (this->HasItem(item)) return;

	this->items[item] = 0;

	this->buckets[0].insert(item);

	this->SetValue(item, value);

}

{

	this->modifications++;

	if (!this->HasItem(item)) return;

	this->sorter->Remove(item);

	this->buckets[value].erase(item);

	if (this->buckets[value].empty()) this->buckets.erase(value);

	this->items.erase(item);

}

{

	this->initialized = true;

	return this->sorter->Begin();

}

{

	if (this->initialized == false) {

		DEBUG(script, 0, "Next() is invalid as Begin() is never called");

		return 0;

	}

	return this->sorter->Next();

int32 ScriptList::Count()

{

	return (int32)this->items.size();

}

{

	if (!this->HasItem(item)) return 0;

	return this->items[item];

}

{

	this->modifications++;

	if (!this->HasItem(item)) return false;

	if (value_old == value) return true;

	this->sorter->Remove(item);

	this->buckets[value_old].erase(item);

	if (this->buckets[value_old].empty()) this->buckets.erase(value_old);

	this->items[item] = value;

	Swap(this->initialized, list->initialized);

	Swap(this->modifications, list->modifications);

	this->sorter->Retarget(this);

	list->sorter->Retarget(list);

}

{

	this->modifications++;

	for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {

		next_iter = iter; next_iter++;

		if ((*iter).second > value) this->RemoveItem((*iter).first);

	}

}

{

	this->modifications++;

	for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {

		next_iter = iter; next_iter++;

		if ((*iter).second < value) this->RemoveItem((*iter).first);

	}

}

{

	this->modifications++;

	for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {

		next_iter = iter; next_iter++;

		if ((*iter).second > start && (*iter).second < end) this->RemoveItem((*iter).first);

	}

}

{

	this->modifications++;

	for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {

		next_iter = iter; next_iter++;

		if ((*iter).second == value) this->RemoveItem((*iter).first);

	ScriptListMap *list_items = &list->items;

	for (ScriptListMap::iterator iter = list_items->begin(); iter != list_items->end(); iter++) {

		this->RemoveItem((*iter).first);

	}

}

{

	this->modifications++;

	for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {

		next_iter = iter; next_iter++;

		if ((*iter).second <= value) this->RemoveItem((*iter).first);

	}

}

{

	this->modifications++;

	for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {

		next_iter = iter; next_iter++;

		if ((*iter).second >= value) this->RemoveItem((*iter).first);

	}

}

{

	this->modifications++;

	for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {

		next_iter = iter; next_iter++;

		if ((*iter).second <= start || (*iter).second >= end) this->RemoveItem((*iter).first);

	}

}

{

	this->modifications++;

	for (ScriptListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {

		next_iter = iter; next_iter++;

		if ((*iter).second != value) this->RemoveItem((*iter).first);

	SorterType sorter_type;       ///< Sorting type

	bool sort_ascending;          ///< Whether to sort ascending or descending

	bool initialized;             ///< Whether an iteration has been started

	int modifications;            ///< Number of modification that has been done. To prevent changing data while valuating.

public:

	ScriptListMap items;           ///< The items in the list

	ScriptListBucket buckets;      ///< The items in the list, sorted by value

	ScriptList();

	~ScriptList();

#ifdef DOXYGEN_API

	/**

	 * Add a single item to the list.

	 * @param item the item to add. Should be unique, otherwise it is ignored.

	 * @param value the value to assign.

	 */

#else

#endif /* DOXYGEN_API */

	/**

	 * Remove a single item from the list.

	 * @param item the item to remove. If not existing, it is ignored.

	 */

	/**

	 * Clear the list, making Count() returning 0 and IsEmpty() returning true.

	 */

	void Clear();

	/**

	 * Check if an item is in the list.

	 * @param item the item to check for.

	 * @return true if the item is in the list.

	 */

	/**

	 * Go to the beginning of the list and return the item. To get the value use list.GetValue(list.Begin()).

	 * @return the first item.

	 * @note returns 0 if beyond end-of-list. Use IsEnd() to check for end-of-list.

	 */

	/**

	 * Go to the next item in the list and return the item. To get the value use list.GetValue(list.Next()).

	 * @return the next item.

	 * @note returns 0 if beyond end-of-list. Use IsEnd() to check for end-of-list.

	 */

	/**

	 * Check if a list is empty.

	 * @return true if the list is empty.

	 */

	bool IsEmpty();

	/**

	 * Get the value that belongs to this item.

	 * @param item the item to get the value from

	 * @return the value that belongs to this item.

	 */

	/**

	 * Set a value of an item directly.

	 * @param item the item to set the value for.

	 * @param value the value to give to the item

	 * @return true if we could set the item to value, false otherwise.

	 * @note Changing values of items while looping through a list might cause

	 *  entries to be skipped. Be very careful with such operations.

	 */

	/**

	 * Sort this list by the given sorter and direction.

	 * @param sorter    the type of sorter to use

	 * @param ascending if true, lowest value is on top, else at bottom.

	 * @note the current item stays at the same place.

	void SwapList(ScriptList *list);

	/**

	 * Removes all items with a higher value than 'value'.

	 * @param value the value above which all items are removed.

	 */

	/**

	 * Removes all items with a lower value than 'value'.

	 * @param value the value below which all items are removed.

	 */

	/**

	 * Removes all items with a value above start and below end.

	 * @param start the lower bound of the to be removed values (exclusive).

	 * @param end   the upper bound of the to be removed values (exclusive).

	 */

	/**

	 * Remove all items with this value.

	 * @param value the value to remove.

	 */

	/**

	 * Remove the first count items.

	 * @param count the amount of items to remove.

	 */

	void RemoveTop(int32 count);

	void RemoveList(ScriptList *list);

	/**

	 * Keep all items with a higher value than 'value'.

	 * @param value the value above which all items are kept.

	 */

	/**

	 * Keep all items with a lower value than 'value'.

	 * @param value the value below which all items are kept.

	 */

	/**

	 * Keep all items with a value above start and below end.

	 * @param start the lower bound of the to be kept values (exclusive).

	 * @param end   the upper bound of the to be kept values (exclusive).

	 */

	/**

	 * Keep all items with this value.

	 * @param value the value to keep.

	 */

	/**

	 * Keep the first count items, i.e. remove everything except the first count items.

	 * @param count the amount of items to keep.

	 */

	void KeepTop(int32 count);