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

#include "../../core/alloc_func.hpp"

     9

    10

/**

    11

 * Base class for any AIAbstractList sorter.

    12

 */

    13

class AIAbstractListSorter {

    14

protected:

    15

	AIAbstractList *list;

    16

    17

public:

    18

	/**

    19

	 * Virtual dtor, needed to mute warnings.

    20

	 */

    21

	virtual ~AIAbstractListSorter() { }

    22

    23

	/**

    24

	 * Get the first item of the sorter.

    25

	 */

    26

	virtual int32 Begin() = 0;

    27

    28

	/**

    29

	 * Get the next item of the sorter.

    30

	 */

    31

	virtual int32 Next() = 0;

    32

    33

	/**

    34

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

    35

	 */

    36

	virtual bool HasNext() = 0;

    37

};

    38

    39

/**

    40

 * Sort by value, ascending.

    41

 */

    42

class AIAbstractListSorterValueAscending : public AIAbstractListSorter {

    43

private:

    44

	AIAbstractList::AIAbstractListBucket::iterator bucket_iter;

    45

	AIAbstractList::AIItemList *bucket_list;

    46

	AIAbstractList::AIItemList::iterator bucket_list_iter;

    47

    48

public:

    49

	AIAbstractListSorterValueAscending(AIAbstractList *list)

    50

	{

    51

		this->list = list;

    52

		this->bucket_list = NULL;

    53

	}

    54

    55

	int32 Begin()

    56

	{

    57

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

    58

    59

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

    60

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

    61

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

    62

		return *bucket_list_iter;

    63

	}

    64

    65

	int32 Next()

    66

	{

    67

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

    68

    69

		this->bucket_list_iter++;

    70

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

    71

			this->bucket_iter++;

    72

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

    73

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

    74

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

    75

		}

    76

		return *bucket_list_iter;

    77

	}

    78

    79

	bool HasNext()

    80

	{

    81

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

    82

    83

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

    84

	}

    85

};

    86

    87

/**

    88

 * Sort by value, descending.

    89

 */

    90

class AIAbstractListSorterValueDescending : public AIAbstractListSorter {

    91

private:

    92

	AIAbstractList::AIAbstractListBucket::reverse_iterator bucket_iter;

    93

	AIAbstractList::AIItemList *bucket_list;

    94

	AIAbstractList::AIItemList::reverse_iterator bucket_list_iter;

    95

    96

public:

    97

	AIAbstractListSorterValueDescending(AIAbstractList *list)

    98

	{

    99

		this->list = list;

   100

		this->bucket_list = NULL;

   101

	}

   102

   103

	int32 Begin()

   104

	{

   105

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

   106

   107

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

   108

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

   109

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

   110

		return *bucket_list_iter;

   111

	}

   112

   113

	int32 Next()

   114

	{

   115

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

   116

   117

		this->bucket_list_iter++;

   118

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

   119

			this->bucket_iter++;

   120

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

   121

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

   122

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

   123

		}

   124

		return *bucket_list_iter;

   125

	}

   126

   127

	bool HasNext()

   128

	{

   129

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

   130

   131

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

   132

	}

   133

};

   134

   135

/**

   136

 * Sort by item, ascending.

   137

 */

   138

class AIAbstractListSorterItemAscending : public AIAbstractListSorter {

   139

private:

   140

	AIAbstractList::AIAbstractListMap::iterator item_iter;

   141

   142

public:

   143

	AIAbstractListSorterItemAscending(AIAbstractList *list)

   144

	{

   145

		this->list = list;

   146

	}

   147

   148

	int32 Begin()

   149

	{

   150

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

   151

   152

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

   153

		return (*this->item_iter).first;

   154

	}

   155

   156

	int32 Next()

   157

	{

   158

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

   159

   160

		this->item_iter++;

   161

		return (*this->item_iter).first;

   162

	}

   163

   164

	bool HasNext()

   165

	{

   166

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

   167

   168

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

   169

	}

   170

};

   171

   172

/**

   173

 * Sort by item, descending.

   174

 */

   175

class AIAbstractListSorterItemDescending : public AIAbstractListSorter {

   176

private:

   177

	AIAbstractList::AIAbstractListMap::reverse_iterator item_iter;

   178

   179

public:

   180

	AIAbstractListSorterItemDescending(AIAbstractList *list)

   181

	{

   182

		this->list = list;

   183

	}

   184

   185

	int32 Begin()

   186

	{

   187

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

   188

   189

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

   190

		return (*this->item_iter).first;

   191

	}

   192

   193

	int32 Next()

   194

	{

   195

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

   196

   197

		this->item_iter++;

   198

		return (*this->item_iter).first;

   199

	}

   200

   201

	bool HasNext()

   202

	{

   203

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

   204

   205

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

   206

	}

   207

};

   208

   209

   210

   211

AIAbstractList::AIAbstractList()

   212

{

   213

	/* Default sorter */

   214

	this->sorter         = new AIAbstractListSorterValueDescending(this);

   215

	this->sorter_type    = SORT_BY_VALUE;

   216

	this->sort_ascending = false;

   217

	this->initialized    = false;

   218

}

   219

   220

AIAbstractList::~AIAbstractList()

   221

{

   222

	delete this->sorter;

   223

}

   224

   225

bool AIAbstractList::HasItem(int32 item)

   226

{

   227

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

   228

}

   229

   230

void AIAbstractList::Clear()

   231

{

   232

	this->items.clear();

   233

	this->buckets.clear();

   234

}

   235

   236

void AIAbstractList::AddItem(int32 item)

   237

{

   238

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

   239

   240

	this->items[item] = 0;

   241

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

   242

}

   243

   244

void AIAbstractList::RemoveItem(int32 item)

   245

{

   246

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

   247

   248

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

   249

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

   250

	this->items.erase(item);

   251

}

   252

   253

int32 AIAbstractList::Begin()

   254

{

   255

	this->initialized = true;

   256

	return this->sorter->Begin();

   257

}

   258

   259

int32 AIAbstractList::Next()

   260

{

   261

	if (this->initialized == false) {

   262

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

   263

		return false;

   264

	}

   265

	return this->sorter->Next();

   266

}

   267

   268

bool AIAbstractList::IsEmpty()

   269

{

   270

	return this->items.empty();

   271

}

   272

   273

bool AIAbstractList::HasNext()

   274

{

   275

	if (this->initialized == false) {

   276

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

   277

		return false;

   278

	}

   279

	return this->sorter->HasNext();

   280

}

   281

   282

int32 AIAbstractList::Count()

   283

{

   284

	return this->items.size();

   285

}

   286

   287

int32 AIAbstractList::GetValue(int32 item)

   288

{

   289

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

   290

   291

	return this->items[item];

   292

}

   293

   294

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

   295

{

   296

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

   297

   298

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

   299

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

   300

	this->items[item] = value;

   301

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

   302

   303

	return true;

   304

}

   305

   306

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

   307

{

   308

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

   309

   310

	delete this->sorter;

   311

	switch (sorter) {

   312

		case SORT_BY_ITEM:

   313

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

   314

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

   315

			break;

   316

   317

		case SORT_BY_VALUE:

   318

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

   319

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

   320

			break;

   321

   322

		default:

   323

			this->Sort(SORT_BY_ITEM, false);

   324

			return;

   325

	}

   326

	this->sorter_type    = sorter;

   327

	this->sort_ascending = ascending;

   328

}

   329

   330

void AIAbstractList::AddList(AIAbstractList *list)

   331

{

   332

	AIAbstractListMap *list_items = &list->items;

   333

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

   334

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

   335

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

   336

	}

   337

}

   338

   339

void AIAbstractList::RemoveAboveValue(int32 value)

   340

{

   341

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

   342

		next_iter = iter; next_iter++;

   343

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

   344

	}

   345

   346

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

   347

		next_iter = iter; next_iter++;

   348

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

   349

	}

   350

}

   351

   352

void AIAbstractList::RemoveBelowValue(int32 value)

   353

{

   354

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

   355

		next_iter = iter; next_iter++;

   356

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

   357

	}

   358

   359

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

   360

		next_iter = iter; next_iter++;

   361

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

   362

	}

   363

}

   364

   365

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

   366

{

   367

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

   368

		next_iter = iter; next_iter++;

   369

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

   370

	}

   371

   372

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

   373

		next_iter = iter; next_iter++;

   374

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

   375

	}

   376

}

   377

   378

void AIAbstractList::RemoveValue(int32 value)

   379

{

   380

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

   381

		next_iter = iter; next_iter++;

   382

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

   383

	}

   384

   385

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

   386

		next_iter = iter; next_iter++;

   387

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

   388

	}

   389

}

   390

   391

void AIAbstractList::RemoveTop(int32 count)

   392

{

   393

	if (!this->sort_ascending) {

   394

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

   395

		this->RemoveBottom(count);

   396

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

   397

		return;

   398

	}

   399

   400

	switch (this->sorter_type) {

   401

		default: NOT_REACHED();

   402

		case SORT_BY_VALUE:

   403

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

   404

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

   405

				size_t size = items->size();

   406

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

   407

					if (--count < 0) return;

   408

					this->RemoveItem(*iter);

   409

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

   410

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

   411

					 */

   412

					if (--size == 0) break;

   413

				}

   414

			}

   415

			break;

   416

   417

		case SORT_BY_ITEM:

   418

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

   419

				if (--count < 0) return;

   420

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

   421

			}

   422

			break;

   423

	}

   424

}

   425

   426

void AIAbstractList::RemoveBottom(int32 count)

   427

{

   428

	if (!this->sort_ascending) {

   429

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

   430

		this->RemoveTop(count);

   431

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

   432

		return;

   433

	}

   434

   435

	switch (this->sorter_type) {

   436

		default: NOT_REACHED();

   437

		case SORT_BY_VALUE:

   438

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

   439

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

   440

				size_t size = items->size();

   441

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

   442

					if (--count < 0) return;

   443

					this->RemoveItem(*iter);

   444

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

   445

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

   446

					 */

   447

					if (--size == 0) break;

   448

				}

   449

			}

   450

   451

		case SORT_BY_ITEM:

   452

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

   453

				if (--count < 0) return;

   454

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

   455

			}

   456

			break;

   457

	}

   458

}

   459

   460

void AIAbstractList::RemoveList(AIAbstractList *list)

   461

{

   462

	AIAbstractListMap *list_items = &list->items;

   463

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

   464

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

   465

	}

   466

}

   467

   468

void AIAbstractList::KeepAboveValue(int32 value)

   469

{

   470

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

   471

		next_iter = iter; next_iter++;

   472

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

   473

	}

   474

   475

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

   476

		next_iter = iter; next_iter++;

   477

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

   478

	}

   479

}

   480

   481

void AIAbstractList::KeepBelowValue(int32 value)

   482

{

   483

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

   484

		next_iter = iter; next_iter++;

   485

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

   486

	}

   487

   488

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

   489

		next_iter = iter; next_iter++;

   490

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

   491

	}

   492

}

   493

   494

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

   495

{

   496

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

   497

		next_iter = iter; next_iter++;

   498

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

   499

	}

   500

   501

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