/* $Id$ */

/** @file ai_list.cpp Implementation of AIList */

#include "ai_list.hpp"

/**
 * Base class for any AIList sorter.
 */
class AIListSorter {
protected:
	AIList *list;

public:
	/**
	 * Virtual dtor, needed to mute warnings.
	 */
	virtual ~AIListSorter() { }

	/**
	 * Get the first item of the sorter.
	 */
	virtual int32 Begin() = 0;

	/**
	 * Get the next item of the sorter.
	 */
	virtual int32 Next() = 0;

	/**
	 * See if there is a next item of the sorter.
	 */
	virtual bool HasNext() = 0;
};

/**
 * Sort by value, ascending.
 */
class AIListSorterValueAscending : public AIListSorter {
private:
	AIList::AIListBucket::iterator bucket_iter;
	AIList::AIItemList *bucket_list;
	AIList::AIItemList::iterator bucket_list_iter;

public:
	AIListSorterValueAscending(AIList *list)
	{
		this->list = list;
	}

	int32 Begin()
	{
		this->bucket_iter = this->list->buckets.begin();
		this->bucket_list = &(*this->bucket_iter).second;
		this->bucket_list_iter = this->bucket_list->begin();
		return *bucket_list_iter;
	}

	int32 Next()
	{
		this->bucket_list_iter++;
		if (this->bucket_list_iter == this->bucket_list->end()) {
			this->bucket_iter++;
			if (this->bucket_iter == this->list->buckets.end()) return 0;
			this->bucket_list = &(*this->bucket_iter).second;
			this->bucket_list_iter = this->bucket_list->begin();
		}
		return *bucket_list_iter;
	}

	bool HasNext()
	{
		return this->bucket_iter != this->list->buckets.end() && this->bucket_list_iter != this->bucket_list->end();
	}
};

/**
 * Sort by value, descending.
 */
class AIListSorterValueDescending : public AIListSorter {
private:
	AIList::AIListBucket::reverse_iterator bucket_iter;
	AIList::AIItemList *bucket_list;
	AIList::AIItemList::reverse_iterator bucket_list_iter;

public:
	AIListSorterValueDescending(AIList *list)
	{
		this->list = list;
	}

	int32 Begin()
	{
		this->bucket_iter = this->list->buckets.rbegin();
		this->bucket_list = &(*this->bucket_iter).second;
		this->bucket_list_iter = this->bucket_list->rbegin();
		return *bucket_list_iter;
	}

	int32 Next()
	{
		this->bucket_list_iter++;
		if (this->bucket_list_iter == this->bucket_list->rend()) {
			this->bucket_iter++;
			if (this->bucket_iter == this->list->buckets.rend()) return 0;
			this->bucket_list = &(*this->bucket_iter).second;
			this->bucket_list_iter = this->bucket_list->rbegin();
		}
		return *bucket_list_iter;
	}

	bool HasNext()
	{
		return this->bucket_iter != this->list->buckets.rend() && this->bucket_list_iter != this->bucket_list->rend();
	}
};

/**
 * Sort by item, ascending.
 */
class AIListSorterItemAscending : public AIListSorter {
private:
	AIList::AIListMap::iterator item_iter;

public:
	AIListSorterItemAscending(AIList *list)
	{
		this->list = list;
	}

	int32 Begin()
	{
		this->item_iter = this->list->items.begin();
		return (*this->item_iter).first;
	}

	int32 Next()
	{
		this->item_iter++;
		return (*this->item_iter).first;
	}

	bool HasNext()
	{
		return this->item_iter != this->list->items.end();
	}
};

/**
 * Sort by item, descending.
 */
class AIListSorterItemDescending : public AIListSorter {
private:
	AIList::AIListMap::reverse_iterator item_iter;

public:
	AIListSorterItemDescending(AIList *list)
	{
		this->list = list;
	}

	int32 Begin()
	{
		this->item_iter = this->list->items.rbegin();
		return (*this->item_iter).first;
	}

	int32 Next()
	{
		this->item_iter++;
		return (*this->item_iter).first;
	}

	bool HasNext()
	{
		return this->item_iter != this->list->items.rend();
	}
};



AIList::AIList()
{
	/* Default sorter */
	this->sorter = new AIListSorterValueDescending(this);
}

AIList::~AIList()
{
	delete this->sorter;
}

bool AIList::HasItem(int32 item)
{
	return this->items.count(item) == 1;
}

void AIList::Clear()
{
	this->items.clear();
	this->buckets.clear();
}

void AIList::AddItem(int32 item)
{
	if (this->HasItem(item)) return;

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

void AIList::RemoveItem(int32 item)
{
	if (!this->HasItem(item)) return;

	this->buckets[this->GetValue(item)].erase(item);
	this->items.erase(item);
}

int32 AIList::Begin()
{
	return this->sorter->Begin();
}

int32 AIList::Next()
{
	return this->sorter->Next();
}

bool AIList::IsEmpty()
{
	return this->items.empty();
}

bool AIList::HasNext()
{
	return this->sorter->HasNext();
}

int32 AIList::Count()
{
	return this->items.size();
}

int32 AIList::GetValue(int32 item)
{
	if (!this->HasItem(item)) return 0;

	return this->items[item];
}

void AIList::SortByItem(bool ascending)
{
	delete this->sorter;
	if (ascending) this->sorter = new AIListSorterItemAscending(this);
	else           this->sorter = new AIListSorterItemDescending(this);
}

void AIList::SortByValue(bool ascending)
{
	delete this->sorter;
	if (ascending) this->sorter = new AIListSorterValueAscending(this);
	else           this->sorter = new AIListSorterValueDescending(this);
}

void AIList::RemoveAboveValue(int32 value)
{
	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).second > value) this->items.erase(iter);
	}

	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).first > value) this->buckets.erase(iter);
	}
}

void AIList::RemoveBelowValue(int32 value)
{
	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).second < value) this->items.erase(iter);
	}

	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).first < value) this->buckets.erase(iter);
	}
}

void AIList::RemoveBetweenValue(int32 start, int32 end)
{
	for (AIListMap::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->items.erase(iter);
	}

	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).first > start && (*iter).first < end) this->buckets.erase(iter);
	}
}

void AIList::RemoveValue(int32 value)
{
	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).second == value) this->items.erase(iter);
	}

	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).first == value) this->buckets.erase(iter);
	}
}

void AIList::KeepAboveValue(int32 value)
{
	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).second <= value) this->items.erase(iter);
	}

	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).first <= value) this->buckets.erase(iter);
	}
}

void AIList::KeepBelowValue(int32 value)
{
	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).second >= value) this->items.erase(iter);
	}

	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).first >= value) this->buckets.erase(iter);
	}
}

void AIList::KeepBetweenValue(int32 start, int32 end)
{
	for (AIListMap::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->items.erase(iter);
	}

	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).first <= start || (*iter).first >= end) this->buckets.erase(iter);
	}
}

void AIList::KeepValue(int32 value)
{
	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).second != value) this->items.erase(iter);
	}

	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
		next_iter = iter; next_iter++;
		if ((*iter).first != value) this->buckets.erase(iter);
	}
}

void AIList::Valuate(const AIList::Valuator &proc)
{
	this->buckets.clear();
	for (AIListMap::iterator iter = this->items.begin(); iter != this->items.end(); iter++) {
		int32 value = proc.Valuate((*iter).first);
		(*iter).second = value;
		this->buckets[value].insert((*iter).first);
	}
}