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

}

   211

   212

AIAbstractList::~AIAbstractList()

   213

{

   214

	delete this->sorter;

   215

}

   216

   217

bool AIAbstractList::HasItem(int32 item)

   218

{

   219

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

   220

}

   221

   222

void AIAbstractList::Clear()

   223

{

   224

	this->items.clear();

   225

	this->buckets.clear();

   226

}

   227

   228

void AIAbstractList::AddItem(int32 item)

   229

{

   230

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

   231

   232

	this->items[item] = 0;

   233

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

   234

}

   235

   236

void AIAbstractList::RemoveItem(int32 item)

   237

{

   238

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

   239

   240

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

   241

	this->items.erase(item);

   242

}

   243

   244

int32 AIAbstractList::Begin()

   245

{

   246

	return this->sorter->Begin();

   247

}

   248

   249

int32 AIAbstractList::Next()

   250

{

   251

	return this->sorter->Next();

   252

}

   253

   254

bool AIAbstractList::IsEmpty()

   255

{

   256

	return this->items.empty();

   257

}

   258

   259

bool AIAbstractList::HasNext()

   260

{

   261

	return this->sorter->HasNext();

   262

}

   263

   264

int32 AIAbstractList::Count()

   265

{

   266

	return this->items.size();

   267

}

   268

   269

int32 AIAbstractList::GetValue(int32 item)

   270

{

   271

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

   272

   273

	return this->items[item];

   274

}

   275

   276

void AIAbstractList::SortByItem(bool ascending)

   277

{

   278

	delete this->sorter;

   279

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

   280

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

   281

}

   282

   283

void AIAbstractList::SortByValue(bool ascending)

   284

{

   285

	delete this->sorter;

   286

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

   287

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

   288

}

   289

   290

void AIAbstractList::RemoveAboveValue(int32 value)

   291

{

   292

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

   293

		next_iter = iter; next_iter++;

   294

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

   295

	}

   296

   297

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

   298

		next_iter = iter; next_iter++;

   299

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

   300

	}

   301

}

   302

   303

void AIAbstractList::RemoveBelowValue(int32 value)

   304

{

   305

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

   306

		next_iter = iter; next_iter++;

   307

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

   308

	}

   309

   310

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

   311

		next_iter = iter; next_iter++;

   312

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

   313

	}

   314

}

   315

   316

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

   317

{

   318

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

   319

		next_iter = iter; next_iter++;

   320

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

   321

	}

   322

   323

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

   324

		next_iter = iter; next_iter++;

   325

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

   326

	}

   327

}

   328

   329

void AIAbstractList::RemoveValue(int32 value)

   330

{

   331

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

   332

		next_iter = iter; next_iter++;

   333

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

   334

	}

   335

   336

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

   337

		next_iter = iter; next_iter++;

   338

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

   339

	}

   340

}

   341

   342

void AIAbstractList::KeepAboveValue(int32 value)

   343

{

   344

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

   345

		next_iter = iter; next_iter++;

   346

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

   347

	}

   348

   349

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

   350

		next_iter = iter; next_iter++;

   351

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

   352

	}

   353

}

   354

   355

void AIAbstractList::KeepBelowValue(int32 value)

   356

{

   357

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

   358

		next_iter = iter; next_iter++;

   359

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

   360

	}

   361

   362

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

   363

		next_iter = iter; next_iter++;

   364

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

   365

	}

   366

}

   367

   368

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

   369

{

   370

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

   371

		next_iter = iter; next_iter++;

   372

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

   373

	}

   374

   375

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

   376

		next_iter = iter; next_iter++;

   377

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

   378

	}

   379

}

   380

   381

void AIAbstractList::KeepValue(int32 value)

   382

{

   383

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

   384

		next_iter = iter; next_iter++;

   385

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

   386

	}

   387

   388

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

   389

		next_iter = iter; next_iter++;

   390

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

   391

	}

   392

}

   393

   394

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

   395

{

   396

	this->buckets.clear();

   397

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

   398

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

   399

		(*iter).second = value;

   400

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

   401

	}

   402

}