1 /* $Id$ */

     2 

     3 /** @file ai_abstractlist.cpp Implementation of AIAbstractList */

     4 

     5 #include "ai_abstractlist.hpp"

     6 

     7 /**

     8  * Base class for any AIAbstractList sorter.

     9  */

    10 class AIAbstractListSorter {

    11 protected:

    12 	AIAbstractList *list;

    13 

    14 public:

    15 	/**

    16 	 * Virtual dtor, needed to mute warnings.

    17 	 */

    18 	virtual ~AIAbstractListSorter() { }

    19 

    20 	/**

    21 	 * Get the first item of the sorter.

    22 	 */

    23 	virtual int32 Begin() = 0;

    24 

    25 	/**

    26 	 * Get the next item of the sorter.

    27 	 */

    28 	virtual int32 Next() = 0;

    29 

    30 	/**

    31 	 * See if there is a next item of the sorter.

    32 	 */

    33 	virtual bool HasNext() = 0;

    34 };

    35 

    36 /**

    37  * Sort by value, ascending.

    38  */

    39 class AIAbstractListSorterValueAscending : public AIAbstractListSorter {

    40 private:

    41 	AIAbstractList::AIAbstractListBucket::iterator bucket_iter;

    42 	AIAbstractList::AIItemList *bucket_list;

    43 	AIAbstractList::AIItemList::iterator bucket_list_iter;

    44 

    45 public:

    46 	AIAbstractListSorterValueAscending(AIAbstractList *list)

    47 	{

    48 		this->list = list;

    49 	}

    50 

    51 	int32 Begin()

    52 	{

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

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

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

    56 		return *bucket_list_iter;

    57 	}

    58 

    59 	int32 Next()

    60 	{

    61 		this->bucket_list_iter++;

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

    63 			this->bucket_iter++;

    64 			if (this->bucket_iter == this->list->buckets.end()) return 0;

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

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

    67 		}

    68 		return *bucket_list_iter;

    69 	}

    70 

    71 	bool HasNext()

    72 	{

    73 		return this->bucket_iter != this->list->buckets.end() && this->bucket_list_iter != this->bucket_list->end();

    74 	}

    75 };

    76 

    77 /**

    78  * Sort by value, descending.

    79  */

    80 class AIAbstractListSorterValueDescending : public AIAbstractListSorter {

    81 private:

    82 	AIAbstractList::AIAbstractListBucket::reverse_iterator bucket_iter;

    83 	AIAbstractList::AIItemList *bucket_list;

    84 	AIAbstractList::AIItemList::reverse_iterator bucket_list_iter;

    85 

    86 public:

    87 	AIAbstractListSorterValueDescending(AIAbstractList *list)

    88 	{

    89 		this->list = list;

    90 	}

    91 

    92 	int32 Begin()

    93 	{

    94 		this->bucket_iter = this->list->buckets.rbegin();

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

    96 		this->bucket_list_iter = this->bucket_list->rbegin();

    97 		return *bucket_list_iter;

    98 	}

    99 

   100 	int32 Next()

   101 	{

   102 		this->bucket_list_iter++;

   103 		if (this->bucket_list_iter == this->bucket_list->rend()) {

   104 			this->bucket_iter++;

   105 			if (this->bucket_iter == this->list->buckets.rend()) return 0;

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

   107 			this->bucket_list_iter = this->bucket_list->rbegin();

   108 		}

   109 		return *bucket_list_iter;

   110 	}

   111 

   112 	bool HasNext()

   113 	{

   114 		return this->bucket_iter != this->list->buckets.rend() && this->bucket_list_iter != this->bucket_list->rend();

   115 	}

   116 };

   117 

   118 /**

   119  * Sort by item, ascending.

   120  */

   121 class AIAbstractListSorterItemAscending : public AIAbstractListSorter {

   122 private:

   123 	AIAbstractList::AIAbstractListMap::iterator item_iter;

   124 

   125 public:

   126 	AIAbstractListSorterItemAscending(AIAbstractList *list)

   127 	{

   128 		this->list = list;

   129 	}

   130 

   131 	int32 Begin()

   132 	{

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

   134 		return (*this->item_iter).first;

   135 	}

   136 

   137 	int32 Next()

   138 	{

   139 		this->item_iter++;

   140 		return (*this->item_iter).first;

   141 	}

   142 

   143 	bool HasNext()

   144 	{

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

   146 	}

   147 };

   148 

   149 /**

   150  * Sort by item, descending.

   151  */

   152 class AIAbstractListSorterItemDescending : public AIAbstractListSorter {

   153 private:

   154 	AIAbstractList::AIAbstractListMap::reverse_iterator item_iter;

   155 

   156 public:

   157 	AIAbstractListSorterItemDescending(AIAbstractList *list)

   158 	{

   159 		this->list = list;

   160 	}

   161 

   162 	int32 Begin()

   163 	{

   164 		this->item_iter = this->list->items.rbegin();

   165 		return (*this->item_iter).first;

   166 	}

   167 

   168 	int32 Next()

   169 	{

   170 		this->item_iter++;

   171 		return (*this->item_iter).first;

   172 	}

   173 

   174 	bool HasNext()

   175 	{

   176 		return this->item_iter != this->list->items.rend();

   177 	}

   178 };

   179 

   180 

   181 

   182 AIAbstractList::AIAbstractList()

   183 {

   184 	/* Default sorter */

   185 	this->sorter = new AIAbstractListSorterValueDescending(this);

   186 }

   187 

   188 AIAbstractList::~AIAbstractList()

   189 {

   190 	delete this->sorter;

   191 }

   192 

   193 bool AIAbstractList::HasItem(int32 item)

   194 {

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

   196 }

   197 

   198 void AIAbstractList::Clear()

   199 {

   200 	this->items.clear();

   201 	this->buckets.clear();

   202 }

   203 

   204 void AIAbstractList::AddItem(int32 item)

   205 {

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

   207 

   208 	this->items[item] = 0;

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

   210 }

   211 

   212 void AIAbstractList::RemoveItem(int32 item)

   213 {

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

   215 

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

   217 	this->items.erase(item);

   218 }

   219 

   220 int32 AIAbstractList::Begin()

   221 {

   222 	return this->sorter->Begin();

   223 }

   224 

   225 int32 AIAbstractList::Next()

   226 {

   227 	return this->sorter->Next();

   228 }

   229 

   230 bool AIAbstractList::IsEmpty()

   231 {

   232 	return this->items.empty();

   233 }

   234 

   235 bool AIAbstractList::HasNext()

   236 {

   237 	return this->sorter->HasNext();

   238 }

   239 

   240 int32 AIAbstractList::Count()

   241 {

   242 	return this->items.size();

   243 }

   244 

   245 int32 AIAbstractList::GetValue(int32 item)

   246 {

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

   248 

   249 	return this->items[item];

   250 }

   251 

   252 void AIAbstractList::SortByItem(bool ascending)

   253 {

   254 	delete this->sorter;

   255 	if (ascending) this->sorter = new AIAbstractListSorterItemAscending(this);

   256 	else           this->sorter = new AIAbstractListSorterItemDescending(this);

   257 }

   258 

   259 void AIAbstractList::SortByValue(bool ascending)

   260 {

   261 	delete this->sorter;

   262 	if (ascending) this->sorter = new AIAbstractListSorterValueAscending(this);

   263 	else           this->sorter = new AIAbstractListSorterValueDescending(this);

   264 }

   265 

   266 void AIAbstractList::RemoveAboveValue(int32 value)

   267 {

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

   269 		next_iter = iter; next_iter++;

   270 		if ((*iter).second > value) this->items.erase(iter);

   271 	}

   272 

   273 	for (AIAbstractListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {

   274 		next_iter = iter; next_iter++;

   275 		if ((*iter).first > value) this->buckets.erase(iter);

   276 	}

   277 }

   278 

   279 void AIAbstractList::RemoveBelowValue(int32 value)

   280 {

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

   282 		next_iter = iter; next_iter++;

   283 		if ((*iter).second < value) this->items.erase(iter);

   284 	}

   285 

   286 	for (AIAbstractListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {

   287 		next_iter = iter; next_iter++;

   288 		if ((*iter).first < value) this->buckets.erase(iter);

   289 	}

   290 }

   291 

   292 void AIAbstractList::RemoveBetweenValue(int32 start, int32 end)

   293 {

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

   295 		next_iter = iter; next_iter++;

   296 		if ((*iter).second > start && (*iter).second < end) this->items.erase(iter);

   297 	}

   298 

   299 	for (AIAbstractListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {

   300 		next_iter = iter; next_iter++;

   301 		if ((*iter).first > start && (*iter).first < end) this->buckets.erase(iter);

   302 	}

   303 }

   304 

   305 void AIAbstractList::RemoveValue(int32 value)

   306 {

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

   308 		next_iter = iter; next_iter++;

   309 		if ((*iter).second == value) this->items.erase(iter);

   310 	}

   311 

   312 	for (AIAbstractListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {

   313 		next_iter = iter; next_iter++;

   314 		if ((*iter).first == value) this->buckets.erase(iter);

   315 	}

   316 }

   317 

   318 void AIAbstractList::KeepAboveValue(int32 value)

   319 {

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

   321 		next_iter = iter; next_iter++;

   322 		if ((*iter).second <= value) this->items.erase(iter);

   323 	}

   324 

   325 	for (AIAbstractListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {

   326 		next_iter = iter; next_iter++;

   327 		if ((*iter).first <= value) this->buckets.erase(iter);

   328 	}

   329 }

   330 

   331 void AIAbstractList::KeepBelowValue(int32 value)

   332 {

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

   334 		next_iter = iter; next_iter++;

   335 		if ((*iter).second >= value) this->items.erase(iter);

   336 	}

   337 

   338 	for (AIAbstractListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {

   339 		next_iter = iter; next_iter++;

   340 		if ((*iter).first >= value) this->buckets.erase(iter);

   341 	}

   342 }

   343 

   344 void AIAbstractList::KeepBetweenValue(int32 start, int32 end)

   345 {

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

   347 		next_iter = iter; next_iter++;

   348 		if ((*iter).second <= start || (*iter).second >= end) this->items.erase(iter);

   349 	}

   350 

   351 	for (AIAbstractListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {

   352 		next_iter = iter; next_iter++;

   353 		if ((*iter).first <= start || (*iter).first >= end) this->buckets.erase(iter);

   354 	}

   355 }

   356 

   357 void AIAbstractList::KeepValue(int32 value)

   358 {

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

   360 		next_iter = iter; next_iter++;

   361 		if ((*iter).second != value) this->items.erase(iter);

   362 	}

   363 

   364 	for (AIAbstractListBucket::iterator next_iter, iter = this->buckets.begin(); iter != this->buckets.end(); iter = next_iter) {

   365 		next_iter = iter; next_iter++;

   366 		if ((*iter).first != value) this->buckets.erase(iter);

   367 	}

   368 }

   369 

   370 void AIAbstractList::Valuate(const AIAbstractList::Valuator &proc)

   371 {

   372 	this->buckets.clear();

   373 	for (AIAbstractListMap::iterator iter = this->items.begin(); iter != this->items.end(); iter++) {

   374 		int32 value = proc.Valuate((*iter).first);

   375 		(*iter).second = value;

   376 		this->buckets[value].insert((*iter).first);

   377 	}

   378 }