truelight@9579: /* $Id$ */
truelight@9579: 
truelight@9579: /** @file ai_list.cpp Implementation of AIList */
truelight@9579: 
truelight@9579: #include "ai_list.hpp"
truelight@9579: 
truelight@9579: /**
truelight@9579:  * Base class for any AIList sorter.
truelight@9579:  */
truelight@9579: class AIListSorter {
truelight@9579: protected:
truelight@9579: 	AIList *list;
truelight@9579: 
truelight@9579: public:
truelight@9579: 	/**
truelight@9579: 	 * Virtual dtor, needed to mute warnings.
truelight@9579: 	 */
truelight@9579: 	virtual ~AIListSorter() { }
truelight@9579: 
truelight@9579: 	/**
truelight@9579: 	 * Get the first item of the sorter.
truelight@9579: 	 */
truelight@9579: 	virtual int32 Begin() = 0;
truelight@9579: 
truelight@9579: 	/**
truelight@9579: 	 * Get the next item of the sorter.
truelight@9579: 	 */
truelight@9579: 	virtual int32 Next() = 0;
truelight@9579: 
truelight@9579: 	/**
truelight@9579: 	 * See if there is a next item of the sorter.
truelight@9579: 	 */
truelight@9579: 	virtual bool HasNext() = 0;
truelight@9579: };
truelight@9579: 
truelight@9579: /**
truelight@9579:  * Sort by value, ascending.
truelight@9579:  */
truelight@9579: class AIListSorterValueAscending : public AIListSorter {
truelight@9579: private:
truelight@9579: 	AIList::AIListBucket::iterator bucket_iter;
truelight@9579: 	AIList::AIItemList *bucket_list;
truelight@9579: 	AIList::AIItemList::iterator bucket_list_iter;
truelight@9579: 
truelight@9579: public:
truelight@9579: 	AIListSorterValueAscending(AIList *list)
truelight@9579: 	{
truelight@9579: 		this->list = list;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	int32 Begin()
truelight@9579: 	{
truelight@9579: 		this->bucket_iter = this->list->buckets.begin();
truelight@9579: 		this->bucket_list = &(*this->bucket_iter).second;
truelight@9579: 		this->bucket_list_iter = this->bucket_list->begin();
truelight@9579: 		return *bucket_list_iter;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	int32 Next()
truelight@9579: 	{
truelight@9579: 		this->bucket_list_iter++;
truelight@9579: 		if (this->bucket_list_iter == this->bucket_list->end()) {
truelight@9579: 			this->bucket_iter++;
truelight@9579: 			if (this->bucket_iter == this->list->buckets.end()) return 0;
truelight@9579: 			this->bucket_list = &(*this->bucket_iter).second;
truelight@9579: 			this->bucket_list_iter = this->bucket_list->begin();
truelight@9579: 		}
truelight@9579: 		return *bucket_list_iter;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	bool HasNext()
truelight@9579: 	{
truelight@9579: 		return this->bucket_iter != this->list->buckets.end() && this->bucket_list_iter != this->bucket_list->end();
truelight@9579: 	}
truelight@9579: };
truelight@9579: 
truelight@9579: /**
truelight@9579:  * Sort by value, descending.
truelight@9579:  */
truelight@9579: class AIListSorterValueDescending : public AIListSorter {
truelight@9579: private:
truelight@9579: 	AIList::AIListBucket::reverse_iterator bucket_iter;
truelight@9579: 	AIList::AIItemList *bucket_list;
truelight@9579: 	AIList::AIItemList::reverse_iterator bucket_list_iter;
truelight@9579: 
truelight@9579: public:
truelight@9579: 	AIListSorterValueDescending(AIList *list)
truelight@9579: 	{
truelight@9579: 		this->list = list;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	int32 Begin()
truelight@9579: 	{
truelight@9579: 		this->bucket_iter = this->list->buckets.rbegin();
truelight@9579: 		this->bucket_list = &(*this->bucket_iter).second;
truelight@9579: 		this->bucket_list_iter = this->bucket_list->rbegin();
truelight@9579: 		return *bucket_list_iter;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	int32 Next()
truelight@9579: 	{
truelight@9579: 		this->bucket_list_iter++;
truelight@9579: 		if (this->bucket_list_iter == this->bucket_list->rend()) {
truelight@9579: 			this->bucket_iter++;
truelight@9579: 			if (this->bucket_iter == this->list->buckets.rend()) return 0;
truelight@9579: 			this->bucket_list = &(*this->bucket_iter).second;
truelight@9579: 			this->bucket_list_iter = this->bucket_list->rbegin();
truelight@9579: 		}
truelight@9579: 		return *bucket_list_iter;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	bool HasNext()
truelight@9579: 	{
truelight@9579: 		return this->bucket_iter != this->list->buckets.rend() && this->bucket_list_iter != this->bucket_list->rend();
truelight@9579: 	}
truelight@9579: };
truelight@9579: 
truelight@9579: /**
truelight@9579:  * Sort by item, ascending.
truelight@9579:  */
truelight@9579: class AIListSorterItemAscending : public AIListSorter {
truelight@9579: private:
truelight@9579: 	AIList::AIListMap::iterator item_iter;
truelight@9579: 
truelight@9579: public:
truelight@9579: 	AIListSorterItemAscending(AIList *list)
truelight@9579: 	{
truelight@9579: 		this->list = list;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	int32 Begin()
truelight@9579: 	{
truelight@9579: 		this->item_iter = this->list->items.begin();
truelight@9579: 		return (*this->item_iter).first;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	int32 Next()
truelight@9579: 	{
truelight@9579: 		this->item_iter++;
truelight@9579: 		return (*this->item_iter).first;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	bool HasNext()
truelight@9579: 	{
truelight@9579: 		return this->item_iter != this->list->items.end();
truelight@9579: 	}
truelight@9579: };
truelight@9579: 
truelight@9579: /**
truelight@9579:  * Sort by item, descending.
truelight@9579:  */
truelight@9579: class AIListSorterItemDescending : public AIListSorter {
truelight@9579: private:
truelight@9579: 	AIList::AIListMap::reverse_iterator item_iter;
truelight@9579: 
truelight@9579: public:
truelight@9579: 	AIListSorterItemDescending(AIList *list)
truelight@9579: 	{
truelight@9579: 		this->list = list;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	int32 Begin()
truelight@9579: 	{
truelight@9579: 		this->item_iter = this->list->items.rbegin();
truelight@9579: 		return (*this->item_iter).first;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	int32 Next()
truelight@9579: 	{
truelight@9579: 		this->item_iter++;
truelight@9579: 		return (*this->item_iter).first;
truelight@9579: 	}
truelight@9579: 
truelight@9579: 	bool HasNext()
truelight@9579: 	{
truelight@9579: 		return this->item_iter != this->list->items.rend();
truelight@9579: 	}
truelight@9579: };
truelight@9579: 
truelight@9579: 
truelight@9579: 
truelight@9579: AIList::AIList()
truelight@9579: {
truelight@9579: 	/* Default sorter */
truelight@9580: 	this->sorter = new AIListSorterValueDescending(this);
truelight@9579: }
truelight@9579: 
truelight@9579: AIList::~AIList()
truelight@9579: {
truelight@9579: 	delete this->sorter;
truelight@9579: }
truelight@9579: 
truelight@9579: bool AIList::HasItem(int32 item)
truelight@9579: {
truelight@9579: 	return this->items.count(item) == 1;
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::Clear()
truelight@9579: {
truelight@9579: 	this->items.clear();
truelight@9579: 	this->buckets.clear();
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::AddItem(int32 item)
truelight@9579: {
truelight@9579: 	if (this->HasItem(item)) return;
truelight@9579: 
truelight@9579: 	this->items[item] = 0;
truelight@9579: 	this->buckets[0].insert(item);
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::RemoveItem(int32 item)
truelight@9579: {
truelight@9579: 	if (!this->HasItem(item)) return;
truelight@9579: 
truelight@9579: 	this->buckets[this->GetValue(item)].erase(item);
truelight@9579: 	this->items.erase(item);
truelight@9579: }
truelight@9579: 
truelight@9579: int32 AIList::Begin()
truelight@9579: {
truelight@9579: 	return this->sorter->Begin();
truelight@9579: }
truelight@9579: 
truelight@9579: int32 AIList::Next()
truelight@9579: {
truelight@9579: 	return this->sorter->Next();
truelight@9579: }
truelight@9579: 
truelight@9579: bool AIList::IsEmpty()
truelight@9579: {
truelight@9579: 	return this->items.empty();
truelight@9579: }
truelight@9579: 
truelight@9579: bool AIList::HasNext()
truelight@9579: {
truelight@9579: 	return this->sorter->HasNext();
truelight@9579: }
truelight@9579: 
truelight@9579: int32 AIList::Count()
truelight@9579: {
truelight@9579: 	return this->items.size();
truelight@9579: }
truelight@9579: 
truelight@9579: int32 AIList::GetValue(int32 item)
truelight@9579: {
truelight@9579: 	if (!this->HasItem(item)) return 0;
truelight@9579: 
truelight@9579: 	return this->items[item];
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::SortByItem(bool ascending)
truelight@9579: {
truelight@9579: 	delete this->sorter;
truelight@9579: 	if (ascending) this->sorter = new AIListSorterItemAscending(this);
truelight@9579: 	else           this->sorter = new AIListSorterItemDescending(this);
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::SortByValue(bool ascending)
truelight@9579: {
truelight@9579: 	delete this->sorter;
truelight@9579: 	if (ascending) this->sorter = new AIListSorterValueAscending(this);
truelight@9579: 	else           this->sorter = new AIListSorterValueDescending(this);
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::RemoveAboveValue(int32 value)
truelight@9579: {
truelight@9581: 	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).second > value) this->items.erase(iter);
truelight@9579: 	}
truelight@9579: 
truelight@9581: 	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).first > value) this->buckets.erase(iter);
truelight@9579: 	}
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::RemoveBelowValue(int32 value)
truelight@9579: {
truelight@9581: 	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).second < value) this->items.erase(iter);
truelight@9579: 	}
truelight@9579: 
truelight@9581: 	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).first < value) this->buckets.erase(iter);
truelight@9579: 	}
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::RemoveBetweenValue(int32 start, int32 end)
truelight@9579: {
truelight@9581: 	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).second > start && (*iter).second < end) this->items.erase(iter);
truelight@9579: 	}
truelight@9579: 
truelight@9581: 	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).first > start && (*iter).first < end) this->buckets.erase(iter);
truelight@9579: 	}
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::RemoveValue(int32 value)
truelight@9579: {
truelight@9581: 	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).second == value) this->items.erase(iter);
truelight@9579: 	}
truelight@9579: 
truelight@9581: 	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).first == value) this->buckets.erase(iter);
truelight@9579: 	}
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::KeepAboveValue(int32 value)
truelight@9579: {
truelight@9581: 	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).second <= value) this->items.erase(iter);
truelight@9579: 	}
truelight@9579: 
truelight@9581: 	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).first <= value) this->buckets.erase(iter);
truelight@9579: 	}
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::KeepBelowValue(int32 value)
truelight@9579: {
truelight@9581: 	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).second >= value) this->items.erase(iter);
truelight@9579: 	}
truelight@9579: 
truelight@9581: 	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).first >= value) this->buckets.erase(iter);
truelight@9579: 	}
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::KeepBetweenValue(int32 start, int32 end)
truelight@9579: {
truelight@9581: 	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).second <= start || (*iter).second >= end) this->items.erase(iter);
truelight@9579: 	}
truelight@9579: 
truelight@9581: 	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).first <= start || (*iter).first >= end) this->buckets.erase(iter);
truelight@9579: 	}
truelight@9579: }
truelight@9579: 
truelight@9579: void AIList::KeepValue(int32 value)
truelight@9579: {
truelight@9581: 	for (AIListMap::iterator next_iter, iter = this->items.begin(); iter != this->items.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).second != value) this->items.erase(iter);
truelight@9579: 	}
truelight@9579: 
truelight@9581: 	for (AIListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {
truelight@9581: 		next_iter = iter; next_iter++;
truelight@9579: 		if ((*iter).first != value) this->buckets.erase(iter);
truelight@9579: 	}
truelight@9579: }
truelight@9579: 
truelight@9589: void AIList::Valuate(const AIList::Valuator &proc)
truelight@9579: {
truelight@9579: 	this->buckets.clear();
truelight@9579: 	for (AIListMap::iterator iter = this->items.begin(); iter != this->items.end(); iter++) {
truelight@9589: 		int32 value = proc.Valuate((*iter).first);
truelight@9579: 		(*iter).second = value;
truelight@9579: 		this->buckets[value].insert((*iter).first);
truelight@9579: 	}
truelight@9579: }