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

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

    54

    55

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

    56

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

    57

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

    58

		return *bucket_list_iter;

    59

	}

    60

    61

	int32 Next()

    62

	{

    63

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

    64

    65

		this->bucket_list_iter++;

    66

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

    67

			this->bucket_iter++;

    68

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

    69

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

    70

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

    71

		}

    72

		return *bucket_list_iter;

    73

	}

    74

    75

	bool HasNext()

    76

	{

    77

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

    78

    79

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

    80

	}

    81

};

    82

    83

/**

    84

 * Sort by value, descending.

    85

 */

    86

class AIAbstractListSorterValueDescending : public AIAbstractListSorter {

    87

private:

    88

	AIAbstractList::AIAbstractListBucket::reverse_iterator bucket_iter;

    89

	AIAbstractList::AIItemList *bucket_list;

    90

	AIAbstractList::AIItemList::reverse_iterator bucket_list_iter;

    91

    92

public:

    93

	AIAbstractListSorterValueDescending(AIAbstractList *list)

    94

	{

    95

		this->list = list;

    96

	}

    97

    98

	int32 Begin()

    99

	{

   100

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

   101

   102

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

   103

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

   104

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

   105

		return *bucket_list_iter;

   106

	}

   107

   108

	int32 Next()

   109

	{

   110

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

   111

   112

		this->bucket_list_iter++;

   113

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

   114

			this->bucket_iter++;

   115

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

   116

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

   117

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

   118

		}

   119

		return *bucket_list_iter;

   120

	}

   121

   122

	bool HasNext()

   123

	{

   124

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

   125

   126

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

   127

	}

   128

};

   129

   130

/**

   131

 * Sort by item, ascending.

   132

 */

   133

class AIAbstractListSorterItemAscending : public AIAbstractListSorter {

   134

private:

   135

	AIAbstractList::AIAbstractListMap::iterator item_iter;

   136

   137

public:

   138

	AIAbstractListSorterItemAscending(AIAbstractList *list)

   139

	{

   140

		this->list = list;

   141

	}

   142

   143

	int32 Begin()

   144

	{

   145

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

   146

   147

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

   148

		return (*this->item_iter).first;

   149

	}

   150

   151

	int32 Next()

   152

	{

   153

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

   154

   155

		this->item_iter++;

   156

		return (*this->item_iter).first;

   157

	}

   158

   159

	bool HasNext()

   160

	{

   161

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

   162

   163

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

   164

	}

   165

};

   166

   167

/**

   168

 * Sort by item, descending.

   169

 */

   170

class AIAbstractListSorterItemDescending : public AIAbstractListSorter {

   171

private:

   172

	AIAbstractList::AIAbstractListMap::reverse_iterator item_iter;

   173

   174

public:

   175

	AIAbstractListSorterItemDescending(AIAbstractList *list)

   176

	{

   177

		this->list = list;

   178

	}

   179

   180

	int32 Begin()

   181

	{

   182

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

   183

   184

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

   185

		return (*this->item_iter).first;

   186

	}

   187

   188

	int32 Next()

   189

	{

   190

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

   191

   192

		this->item_iter++;

   193

		return (*this->item_iter).first;

   194

	}

   195

   196

	bool HasNext()

   197

	{

   198

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

   199

   200

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

   201

	}

   202

};

   203

   204

   205

   206

AIAbstractList::AIAbstractList()

   207

{

   208

	/* Default sorter */

   209

	this->sorter         = new AIAbstractListSorterValueDescending(this);

   210

	this->sorter_type    = SORT_BY_VALUE;

   211

	this->sort_ascending = false;

   212

}

   213

   214

AIAbstractList::~AIAbstractList()

   215

{

   216

	delete this->sorter;

   217

}

   218

   219

bool AIAbstractList::HasItem(int32 item)

   220

{

   221

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

   222

}

   223

   224

void AIAbstractList::Clear()

   225

{

   226

	this->items.clear();

   227

	this->buckets.clear();

   228

}

   229

   230

void AIAbstractList::AddItem(int32 item)

   231

{

   232

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

   233

   234

	this->items[item] = 0;

   235

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

   236

}

   237

   238

void AIAbstractList::RemoveItem(int32 item)

   239

{

   240

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

   241

   242

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

   243

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

   244

	this->items.erase(item);

   245

}

   246

   247

int32 AIAbstractList::Begin()

   248

{

   249

	return this->sorter->Begin();

   250

}

   251

   252

int32 AIAbstractList::Next()

   253

{

   254

	return this->sorter->Next();

   255

}

   256

   257

bool AIAbstractList::IsEmpty()

   258

{

   259

	return this->items.empty();

   260

}

   261

   262

bool AIAbstractList::HasNext()

   263

{

   264

	return this->sorter->HasNext();

   265

}

   266

   267

int32 AIAbstractList::Count()

   268

{

   269

	return this->items.size();

   270

}

   271

   272

int32 AIAbstractList::GetValue(int32 item)

   273

{

   274

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

   275

   276

	return this->items[item];

   277

}

   278

   279

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

   280

{

   281

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

   282

   283

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

   284

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

   285

	this->items[item] = value;

   286

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

   287

   288

	return true;

   289

}

   290

   291

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

   292

{

   293

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

   294

   295

	delete this->sorter;

   296

	switch (sorter) {

   297

		case SORT_BY_ITEM:

   298

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

   299

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

   300

			break;

   301

   302

		case SORT_BY_VALUE:

   303

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

   304

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

   305

			break;

   306

   307

		default:

   308

			this->Sort(SORT_BY_ITEM, false);

   309

			return;

   310

	}

   311

	this->sorter_type    = sorter;

   312

	this->sort_ascending = ascending;

   313

}

   314

   315

void AIAbstractList::RemoveAboveValue(int32 value)

   316

{

   317

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

   318

		next_iter = iter; next_iter++;

   319

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

   320

	}

   321

   322

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

   323

		next_iter = iter; next_iter++;

   324

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

   325

	}

   326

}

   327

   328

void AIAbstractList::RemoveBelowValue(int32 value)

   329

{

   330

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

   331

		next_iter = iter; next_iter++;

   332

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

   333

	}

   334

   335

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

   336

		next_iter = iter; next_iter++;

   337

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

   338

	}

   339

}

   340

   341

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

   342

{

   343

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

   344

		next_iter = iter; next_iter++;

   345

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

   346

	}

   347

   348

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

   349

		next_iter = iter; next_iter++;

   350

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

   351

	}

   352

}

   353

   354

void AIAbstractList::RemoveValue(int32 value)

   355

{

   356

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

   357

		next_iter = iter; next_iter++;

   358

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

   359

	}

   360

   361

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

   362

		next_iter = iter; next_iter++;

   363

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

   364

	}

   365

}

   366

   367

void AIAbstractList::RemoveTop(int32 count)

   368

{

   369

	if (!this->sort_ascending) {

   370

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

   371

		this->RemoveBottom(count);

   372

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

   373

		return;

   374

	}

   375

   376

	switch (this->sorter_type) {

   377

		default: NOT_REACHED();

   378

		case SORT_BY_VALUE:

   379

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

   380

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

   381

				size_t size = items->size();

   382

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

   383

					if (--count < 0) return;

   384

					this->RemoveItem(*iter);

   385

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

   386

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

   387

					 */

   388

					if (--size == 0) break;

   389

				}

   390

			}

   391

			break;

   392

   393

		case SORT_BY_ITEM:

   394

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

   395

				if (--count < 0) return;

   396

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

   397

			}

   398

			break;

   399

	}

   400

}

   401

   402

void AIAbstractList::RemoveBottom(int32 count)

   403

{

   404

	if (!this->sort_ascending) {

   405

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

   406

		this->RemoveTop(count);

   407

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

   408

		return;

   409

	}

   410

   411

	switch (this->sorter_type) {

   412

		default: NOT_REACHED();

   413

		case SORT_BY_VALUE:

   414

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

   415

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

   416

				size_t size = items->size();

   417

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

   418

					if (--count < 0) return;

   419

					this->RemoveItem(*iter);

   420

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

   421

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

   422

					 */

   423

					if (--size == 0) break;

   424

				}

   425

			}

   426

   427

		case SORT_BY_ITEM:

   428

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

   429

				if (--count < 0) return;

   430

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

   431

			}

   432

			break;

   433

	}

   434

}

   435

   436

void AIAbstractList::RemoveList(AIAbstractList *list)

   437

{

   438

	AIAbstractListMap *list_items = &list->items;

   439

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

   440

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

   441

	}

   442

}

   443

   444

void AIAbstractList::KeepAboveValue(int32 value)

   445

{

   446

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

   447

		next_iter = iter; next_iter++;

   448

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

   449

	}

   450

   451

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

   452

		next_iter = iter; next_iter++;

   453

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

   454

	}

   455

}

   456

   457

void AIAbstractList::KeepBelowValue(int32 value)

   458

{

   459

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

   460

		next_iter = iter; next_iter++;

   461

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

   462

	}

   463

   464

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

   465

		next_iter = iter; next_iter++;

   466

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

   467

	}

   468

}

   469

   470

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

   471

{

   472

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

   473

		next_iter = iter; next_iter++;

   474

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

   475

	}

   476

   477

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

   478

		next_iter = iter; next_iter++;

   479

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

   480

	}

   481

}

   482

   483

void AIAbstractList::KeepValue(int32 value)

   484

{

   485

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

   486

		next_iter = iter; next_iter++;

   487

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

   488

	}

   489

   490

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

   491

		next_iter = iter; next_iter++;

   492

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

   493

	}

   494

}

   495

   496

void AIAbstractList::KeepTop(int32 count)

   497

{

   498

	this->RemoveBottom(this->Count() - count);

   499

}

   500

   501

void AIAbstractList::KeepBottom(int32 count)

   502

{

   503