#include "../../stdafx.h"

#include "script_list.hpp"

#include "../../debug.h"

#include "../../script/squirrel.hpp"

#include "../../safeguards.h"

/**

 * 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()

	{

		return this->list->buckets.empty() || this->has_no_more_items;

	}

	/**

	 * Callback from the list if an item gets removed.

	 */

public:

	/**

	 * Create a new sorter.

	 * @param list The list to sort.

	 */

	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 = NULL;

		this->has_no_more_items = true;

		this->item_next = 0;

	}

	/**

		if (this->bucket_list_iter == this->bucket_list->end()) {

			this->bucket_iter++;

			if (this->bucket_iter == this->list->buckets.end()) {

				this->bucket_list = NULL;

				return;

			}

			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)

	{

		if (this->IsEnd()) return;

		/* If we remove the 'next' item, skip to the next */

		if (item == this->item_next) {

			FindNext();

			return;

public:

	/**

	 * Create a new sorter.

	 * @param list The list to sort.

	 */

	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();

		--this->bucket_iter;

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

		/* 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()

	{

		this->bucket_list = NULL;

		this->has_no_more_items = true;

		this->item_next = 0;

	}

	/**

			}

			this->bucket_iter--;

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

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

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

			--this->bucket_list_iter;

		} 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)

	{

		if (this->IsEnd()) return;

		/* If we remove the 'next' item, skip to the next */

		if (item == this->item_next) {

			FindNext();

			return;

public:

	/**

	 * Create a new sorter.

	 * @param list The list to sort.

	 */

	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()

	{

		this->has_no_more_items = true;

	}

	/**

	 * Find the next item, and store that information.

	 */

	void FindNext()

	{

		if (this->item_iter == this->list->items.end()) {

			this->has_no_more_items = true;

			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)

	{

		if (this->IsEnd()) return;

		/* If we remove the 'next' item, skip to the next */

		if (item == this->item_next) {

			FindNext();

			return;

public:

	/**

	 * Create a new sorter.

	 * @param list The list to sort.

	 */

	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()

	{

		this->has_no_more_items = true;

	}

	/**

	 * Find the next item, and store that information.

	 */

			this->has_no_more_items = true;

			return;

		}

		if (this->item_iter == this->list->items.begin()) {

			/* Use 'end' as marker for 'beyond begin' */

			this->item_iter = this->list->items.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)

	{

		if (this->IsEnd()) return;

		/* If we remove the 'next' item, skip to the next */

		if (item == this->item_next) {

			FindNext();

			return;

	this->sorter         = new ScriptListSorterValueDescending(this);

	this->sorter_type    = SORT_BY_VALUE;

	this->sort_ascending = false;

	this->initialized    = false;

	this->modifications  = 0;

}

ScriptList::~ScriptList()

{

	delete this->sorter;

}

{

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

}

void ScriptList::Clear()

{

	this->modifications++;

	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();

}

bool ScriptList::IsEmpty()

{

	return this->items.empty();

}

	if (this->initialized == false) {

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

		return true;

	}

	return this->sorter->IsEnd();

}

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;

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

	return true;

}

void ScriptList::Sort(SorterType sorter, bool ascending)

{

	this->items.swap(list->items);

	this->buckets.swap(list->buckets);

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

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

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

	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);

	}

}

void ScriptList::RemoveTop(int32 count)

{

	this->modifications++;

}

void ScriptList::RemoveList(ScriptList *list)

{

	this->modifications++;

	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);

	}

}

void ScriptList::KeepTop(int32 count)

{

	this->modifications++;

	static const bool SORT_ASCENDING = true;

	/** Sort descending */

	static const bool SORT_DESCENDING = false;

private:

	ScriptListSorter *sorter;     ///< Sorting algorithm

	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();

	/**

	 * Check if there is a element left. In other words, if this is false,

	 * the last call to Begin() or Next() returned a valid item.

	 * @return true if the current item is beyond end-of-list.

	 */

	/**

	 * Returns the amount of items in the list.

	 * @return amount of items in the list.

	 */

	int32 Count();

	/**

	 * 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.

	 * @see SORT_ASCENDING SORT_DESCENDING

	 */

	void Sort(SorterType sorter, bool ascending);

	/**

	 * Add one list to another one.

	void AddList(ScriptList *list);

	/**

	 * Swap the contents of two lists.

	 * @param list The list that will be swapped with.

	 */

	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);

	/**

	 * Remove the last count items.

	 * @param count the amount of items to remove.

	 */

	void RemoveBottom(int32 count);

	/**

	 * Remove everything that is in the given list from this list (same item index that is).

	 * @param list the list of items to remove.

	 * @pre list != NULL

	 */

	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.