1

/* $Id$ */

     2

     3

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

     4

     5

#include <squirrel.h>

     6

#include "ai_abstractlist.hpp"

     7

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

     8

     9

/**

    10

 * Base class for any AIAbstractList sorter.

    11

 */

    12

class AIAbstractListSorter {

    13

protected:

    14

	AIAbstractList *list;

    15

    16

public:

    17

	/**

    18

	 * Virtual dtor, needed to mute warnings.

    19

	 */

    20

	virtual ~AIAbstractListSorter() { }

    21

    22

	/**

    23

	 * Get the first item of the sorter.

    24

	 */

    25

	virtual int32 Begin() = 0;

    26

    27

	/**

    28

	 * Get the next item of the sorter.

    29

	 */

    30

	virtual int32 Next() = 0;

    31

    32

	/**

    33

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

    34

	 */

    35

	virtual bool HasNext() = 0;

    36

};

    37

    38

/**

    39

 * Sort by value, ascending.

    40

 */

    41

class AIAbstractListSorterValueAscending : public AIAbstractListSorter {

    42

private:

    43

	AIAbstractList::AIAbstractListBucket::iterator bucket_iter;

    44

	AIAbstractList::AIItemList *bucket_list;

    45

	AIAbstractList::AIItemList::iterator bucket_list_iter;

    46

    47

public:

    48

	AIAbstractListSorterValueAscending(AIAbstractList *list)

    49

	{

    50

		this->list = list;

    51

		this->bucket_list = NULL;

    52

	}

    53

    54

	int32 Begin()

    55

	{

    56

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

    57

    58

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

    59

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

    60

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

    61

		return *bucket_list_iter;

    62

	}

    63

    64

	int32 Next()

    65

	{

    66

		if (this->list->buckets.empty() || this->bucket_list == NULL) return 0;

    67

    68

		this->bucket_list_iter++;

    69

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

    70

			this->bucket_iter++;

    71

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

    72

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

    73

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

    74

		}

    75

		return *bucket_list_iter;

    76

	}

    77

    78

	bool HasNext()

    79

	{

    80

		if (this->list->buckets.empty() || this->bucket_list == NULL) return false;

    81

    82

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

    83

	}

    84

};

    85

    86

/**

    87

 * Sort by value, descending.

    88

 */

    89

class AIAbstractListSorterValueDescending : public AIAbstractListSorter {

    90

private:

    91

	AIAbstractList::AIAbstractListBucket::reverse_iterator bucket_iter;

    92

	AIAbstractList::AIItemList *bucket_list;

    93

	AIAbstractList::AIItemList::reverse_iterator bucket_list_iter;

    94

    95

public:

    96

	AIAbstractListSorterValueDescending(AIAbstractList *list)

    97

	{

    98

		this->list = list;

    99

		this->bucket_list = NULL;

   100

	}

   101

   102

	int32 Begin()

   103

	{

   104

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

   105

   106

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

   107

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

   108

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

   109

		return *bucket_list_iter;

   110

	}

   111

   112

	int32 Next()

   113

	{

   114

		if (this->list->buckets.empty() || this->bucket_list == NULL) return 0;

   115

   116

		this->bucket_list_iter++;

   117

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

   118

			this->bucket_iter++;

   119

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

   120

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

   121

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

   122

		}

   123

		return *bucket_list_iter;

   124

	}

   125

   126

	bool HasNext()

   127

	{

   128

		if (this->list->buckets.empty() || this->bucket_list == NULL) return false;

   129

   130

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

   131

	}

   132

};

   133

   134

/**

   135

 * Sort by item, ascending.

   136

 */

   137

class AIAbstractListSorterItemAscending : public AIAbstractListSorter {

   138

private:

   139

	AIAbstractList::AIAbstractListMap::iterator item_iter;

   140

   141

public:

   142

	AIAbstractListSorterItemAscending(AIAbstractList *list)

   143

	{

   144

		this->list = list;

   145

	}

   146

   147

	int32 Begin()

   148

	{

   149

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

   150

   151

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

   152

		return (*this->item_iter).first;

   153

	}

   154

   155

	int32 Next()

   156

	{

   157

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

   158

   159

		this->item_iter++;

   160

		return (*this->item_iter).first;

   161

	}

   162

   163

	bool HasNext()

   164

	{

   165

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

   166

   167

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

   168

	}

   169

};

   170

   171

/**

   172

 * Sort by item, descending.

   173

 */

   174

class AIAbstractListSorterItemDescending : public AIAbstractListSorter {

   175

private:

   176

	AIAbstractList::AIAbstractListMap::reverse_iterator item_iter;

   177

   178

public:

   179

	AIAbstractListSorterItemDescending(AIAbstractList *list)

   180

	{

   181

		this->list = list;

   182

	}

   183

   184

	int32 Begin()

   185

	{

   186

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

   187

   188

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

   189

		return (*this->item_iter).first;

   190

	}

   191

   192

	int32 Next()

   193

	{

   194

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

   195

   196

		this->item_iter++;

   197

		return (*this->item_iter).first;

   198

	}

   199

   200

	bool HasNext()

   201

	{

   202

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

   203

   204

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

   205

	}

   206

};

   207

   208

   209

   210

AIAbstractList::AIAbstractList()

   211

{

   212

	/* Default sorter */

   213

	this->sorter         = new AIAbstractListSorterValueDescending(this);

   214

	this->sorter_type    = SORT_BY_VALUE;

   215

	this->sort_ascending = false;

   216

	this->initialized    = false;

   217

}

   218

   219

AIAbstractList::~AIAbstractList()

   220

{

   221

	delete this->sorter;

   222

}

   223

   224

bool AIAbstractList::HasItem(int32 item)

   225

{

   226

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

   227

}

   228

   229

void AIAbstractList::Clear()

   230

{

   231

	this->items.clear();

   232

	this->buckets.clear();

   233

}

   234

   235

void AIAbstractList::AddItem(int32 item)

   236

{

   237

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

   238

   239

	this->items[item] = 0;

   240

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

   241

}

   242

   243

void AIAbstractList::RemoveItem(int32 item)

   244

{

   245

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

   246

   247

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

   248

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

   249

	this->items.erase(item);

   250

}

   251

   252

int32 AIAbstractList::Begin()

   253

{

   254

	this->initialized = true;

   255

	return this->sorter->Begin();

   256

}

   257

   258

int32 AIAbstractList::Next()

   259

{

   260

	if (this->initialized == false) {

   261

		DEBUG(ai, 0, "ERROR: Next() is invalid as Begin() is never called");

   262

		return false;

   263

	}

   264

	return this->sorter->Next();

   265

}

   266

   267

bool AIAbstractList::IsEmpty()

   268

{

   269

	return this->items.empty();

   270

}

   271

   272

bool AIAbstractList::HasNext()

   273

{

   274

	if (this->initialized == false) {

   275

		DEBUG(ai, 0, "ERROR: HasNext() is invalid as Begin() is never called");

   276

		return false;

   277

	}

   278

	return this->sorter->HasNext();

   279

}

   280

   281

int32 AIAbstractList::Count()

   282

{

   283

	return this->items.size();

   284

}

   285

   286

int32 AIAbstractList::GetValue(int32 item)

   287

{

   288

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

   289

   290

	return this->items[item];

   291

}

   292

   293

bool AIAbstractList::SetValue(int32 item, int32 value)

   294

{

   295

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

   296

   297

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

   298

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

   299

	this->items[item] = value;

   300

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

   301

   302

	return true;

   303

}

   304

   305

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

   306

{

   307

	if (sorter == this->sorter_type && ascending == this->sort_ascending) return;

   308

   309

	delete this->sorter;

   310

	switch (sorter) {

   311

		case SORT_BY_ITEM:

   312

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

   313

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

   314

			break;

   315

   316

		case SORT_BY_VALUE:

   317

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

   318

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

   319

			break;

   320

   321

		default:

   322

			this->Sort(SORT_BY_ITEM, false);

   323

			return;

   324

	}

   325

	this->sorter_type    = sorter;

   326

	this->sort_ascending = ascending;

   327

}

   328

   329

void AIAbstractList::AddList(AIAbstractList *list)

   330

{

   331

	AIAbstractListMap *list_items = &list->items;

   332

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

   333

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

   334

		this->SetValue((*iter).first, (*iter).second);

   335

	}

   336

}

   337

   338

void AIAbstractList::RemoveAboveValue(int32 value)

   339

{

   340

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

   341

		next_iter = iter; next_iter++;

   342

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

   343

	}

   344

   345

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

   346

		next_iter = iter; next_iter++;

   347

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

   348

	}

   349

}

   350

   351

void AIAbstractList::RemoveBelowValue(int32 value)

   352

{

   353

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

   354

		next_iter = iter; next_iter++;

   355

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

   356

	}

   357

   358

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

   359

		next_iter = iter; next_iter++;

   360

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

   361

	}

   362

}

   363

   364

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

   365

{

   366

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

   367

		next_iter = iter; next_iter++;

   368

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

   369

	}

   370

   371

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

   372

		next_iter = iter; next_iter++;

   373

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

   374

	}

   375

}

   376

   377

void AIAbstractList::RemoveValue(int32 value)

   378

{

   379

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

   380

		next_iter = iter; next_iter++;

   381

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

   382

	}

   383

   384

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

   385

		next_iter = iter; next_iter++;

   386

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

   387

	}

   388

}

   389

   390

void AIAbstractList::RemoveTop(int32 count)

   391

{

   392

	if (!this->sort_ascending) {

   393

		this->Sort(this->sorter_type, !this->sort_ascending);

   394

		this->RemoveBottom(count);

   395

		this->Sort(this->sorter_type, !this->sort_ascending);

   396

		return;

   397

	}

   398

   399

	switch (this->sorter_type) {

   400

		default: NOT_REACHED();

   401

		case SORT_BY_VALUE:

   402

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

   403

				AIItemList *items = &(*iter).second;

   404

				size_t size = items->size();

   405

				for (AIItemList::iterator iter = items->begin(); iter != items->end(); iter = items->begin()) {

   406

					if (--count < 0) return;

   407

					this->RemoveItem(*iter);

   408

					/* When the last item is removed from the bucket, the bucket itself is removed.

   409

					 * This means that the iterators can be invalid after a call to RemoveItem.

   410

					 */

   411

					if (--size == 0) break;

   412

				}

   413

			}

   414

			break;

   415

   416

		case SORT_BY_ITEM:

   417

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

   418

				if (--count < 0) return;

   419

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

   420

			}

   421

			break;

   422

	}

   423

}

   424

   425

void AIAbstractList::RemoveBottom(int32 count)

   426

{

   427

	if (!this->sort_ascending) {

   428

		this->Sort(this->sorter_type, !this->sort_ascending);

   429

		this->RemoveTop(count);

   430

		this->Sort(this->sorter_type, !this->sort_ascending);

   431

		return;

   432

	}

   433

   434

	switch (this->sorter_type) {

   435

		default: NOT_REACHED();

   436

		case SORT_BY_VALUE:

   437

			for (AIAbstractListBucket::reverse_iterator iter = this->buckets.rbegin(); iter != this->buckets.rend(); iter = this->buckets.rbegin()) {

   438

				AIItemList *items = &(*iter).second;

   439

				size_t size = items->size();

   440

				for (AIItemList::reverse_iterator iter = items->rbegin(); iter != items->rend(); iter = items->rbegin()) {

   441

					if (--count < 0) return;

   442

					this->RemoveItem(*iter);

   443

					/* When the last item is removed from the bucket, the bucket itself is removed.

   444

					 * This means that the iterators can be invalid after a call to RemoveItem.

   445

					 */

   446

					if (--size == 0) break;

   447

				}

   448

			}

   449

   450

		case SORT_BY_ITEM:

   451

			for (AIAbstractListMap::reverse_iterator iter = this->items.rbegin(); iter != this->items.rend(); iter = this->items.rbegin()) {

   452

				if (--count < 0) return;

   453

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

   454

			}

   455

			break;

   456

	}

   457

}

   458

   459

void AIAbstractList::RemoveList(AIAbstractList *list)

   460

{

   461

	AIAbstractListMap *list_items = &list->items;

   462

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

   463

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

   464

	}

   465

}

   466

   467

void AIAbstractList::KeepAboveValue(int32 value)

   468

{

   469

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

   470

		next_iter = iter; next_iter++;

   471

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

   472

	}

   473

   474

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

   475

		next_iter = iter; next_iter++;

   476

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

   477

	}

   478

}

   479

   480

void AIAbstractList::KeepBelowValue(int32 value)

   481

{

   482

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

   483

		next_iter = iter; next_iter++;

   484

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

   485

	}

   486

   487

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

   488

		next_iter = iter; next_iter++;

   489

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

   490

	}

   491

}

   492

   493

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

   494

{

   495

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

   496

		next_iter = iter; next_iter++;

   497

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

   498

	}

   499

   500

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

   501

		next_iter = iter; next_iter++;