1

/* $Id$ */

     2

     3

/** @file sortlist_type.h Base types for having sorted lists in GUIs. */

     4

     5

#ifndef SORTLIST_TYPE_H

     6

#define SORTLIST_TYPE_H

     7

     8

#include "misc/smallvec.h"

     9

#include "date_type.h"

    10

    11

enum SortListFlags {

    12

	VL_NONE       = 0,      ///< no sort

    13

	VL_DESC       = 1 << 0, ///< sort descending or ascending

    14

	VL_RESORT     = 1 << 1, ///< instruct the code to resort the list in the next loop

    15

	VL_REBUILD    = 1 << 2, ///< rebuild the sort list

    16

	VL_FIRST_SORT = 1 << 3, ///< sort with qsort first

    17

	VL_END        = 1 << 4,

    18

};

    19

DECLARE_ENUM_AS_BIT_SET(SortListFlags);

    20

    21

struct Listing {

    22

	bool order;    ///< Ascending/descending

    23

	byte criteria; ///< Sorting criteria

    24

};

    25

    26

template <typename T>

    27

class GUIList : public SmallVector<T, 32> {

    28

public:

    30

    31

public: // Temporary: public for conversion only

    32

	SortFunction* const *func_list; ///< The sort criteria functions

    33

	SortListFlags flags;            ///< used to control sorting/resorting/etc.

    34

	uint8 sort_type;                ///< what criteria to sort on

    35

	uint16 resort_timer;            ///< resort list after a given amount of ticks if set

    36

    37

	/**

    38

	 * Check if the list is sortable

    39

	 *

    40

	 * @return true if we can sort the list

    41

	 */

    42

	bool IsSortable() const

    43

	{

    44

		return (this->data != NULL && this->items >= 2);

    45

	}

    46

    47

	/**

    48

	 * Reset the resort timer

    49

	 */

    50

	void ResetResortTimer()

    51

	{

    52

		/* Resort every 10 days */

    53

		this->resort_timer = DAY_TICKS * 10;

    54

	}

    55

    56

	/**

    57

	 * Reverse the list

    58

	 */

    59

	void Reverse()

    60

	{

    61

		assert(this->IsSortable());

    62

    63

		T *a = this->data;

    64

		T *b = a + (this->items - 1);

    65

    66

		do {

    67

			Swap(*a, *b);

    68

		} while (++a < --b);

    69

	}

    70

    71

public:

    72

	GUIList() :

    73

		func_list(NULL),

    74

		flags(VL_FIRST_SORT),

    75

		sort_type(0),

    76

		resort_timer(1)

    77

	{};

    78

    79

	/**

    80

	 * Get the sorttype of the list

    81

	 *

    82

	 * @return The current sorttype

    83

	 */

    84

	uint8 SortType() const

    85

	{

    86

		return this->sort_type;

    87

	}

    88

    89

	/**

    90

	 * Set the sorttype of the list

    91

	 *

    92

	 * @param n_type the new sort type

    93

	 */

    94

	void SetSortType(uint8 n_type)

    95

	{

    96

		if (this->sort_type != n_type) {

    97

			SETBITS(this->flags, VL_RESORT | VL_FIRST_SORT);

    98

			this->sort_type = n_type;

    99

		}

   100

	}

   101

   102

	/**

   103

	 * Export current sort conditions

   104

	 *

   105

	 * @return the current sort conditions

   106

	 */

   107

	Listing GetListing() const

   108

	{

   109

		Listing l;

   110

		l.order = HASBITS(this->flags, VL_DESC);

   111

		l.criteria = this->sort_type;

   112

   113

		return l;

   114

	}

   115

   116

	/**

   117

	 * Import sort conditions

   118

	 *

   119

	 * @param l The sport conditions we want to use

   120

	 */

   121

	void SetListing(Listing l)

   122

	{

   123

		if (l.order) {

   124

			SETBITS(this->flags, VL_DESC);

   125

		} else {

   126

			CLRBITS(this->flags, VL_DESC);

   127

		}

   128

		this->sort_type = l.criteria;

   129

   130

		SETBITS(this->flags, VL_FIRST_SORT);

   131

	}

   132

   133

	/**

   134

	 * Check if a resort is needed next loop

   135

	 *  If used the resort timer will decrease every call

   136

	 *  till 0. If 0 reached the resort bit will be set and

   137

	 *  the timer will be reset.

   138

	 *

   139

	 * @return true if resort bit is set for next loop

   140

	 */

   141

	bool NeedResort()

   142

	{

   143

		if (--this->resort_timer == 0) {

   144

			SETBITS(this->flags, VL_RESORT);

   145

			this->ResetResortTimer();

   146

			return true;

   147

		}

   148

		return false;

   149

	}

   150

   151

	/**

   152

	 * Force a resort next Sort call

   153

	 *  Reset the resort timer if used too.

   154

	 */

   155

	void ForceResort()

   156

	{

   157

		SETBITS(this->flags, VL_RESORT);

   158

	}

   159

   160

	/**

   161

	 * Check if the sort order is descending

   162

	 *

   163

	 * @return true if the sort order is descending

   164

	 */

   165

	bool IsDescSortOrder() const

   166

	{

   167

		return HASBITS(this->flags, VL_DESC);

   168

	}

   169

   170

	/**

   171

	 * Toogle the sort order

   172

	 *  Since that is the worst condition for the sort function

   173

	 *  reverse the list here.

   174

	 */

   175

	FORCEINLINE void ToggleSortOrder()

   176

	{

   177

		this->flags ^= VL_DESC;

   178

   179

		if (this->IsSortable()) this->Reverse();

   180

	}

   181

   182

	/**

   183

	 * GnomeSort algorithm

   184

	 *  This sorting uses a slightly modifyied Gnome search.

   185

	 *  The basic Gnome search trys to sort already sorted

   186

	 *  list parts. The modification skips these. For the first

   187

	 *  sorting we use qsort since it is faster for irregular

   188

	 *  sorted data.

   189

	 *

   190

	 * @param compare The function to compare two list items

   191

	 * */

   193

	{

   194

		/* Do not sort if the resort bit is not set */

   195

		if (!HASBITS(this->flags, VL_RESORT)) return;

   196

   197

		CLRBITS(this->flags, VL_RESORT);

   198

   199

		this->ResetResortTimer();

   200

   201

		/* Do not sort when the list is not sortable */

   202

		if (!this->IsSortable()) return;

   203

   204

		const bool desc = HASBITS(this->flags, VL_DESC);

   205

   206

		if (HASBITS(this->flags, VL_FIRST_SORT)) {

   208

   209

			if (desc) this->Reverse();

   210

			return;

   211

		}

   212

   213

		T *a = this->data;

   214

		T *b = a + 1;

   215

   216

		uint length = this->items;

   217

		uint offset = 0; // Jump variable

   218

   219

		while (length > 1) {

   220

			const int diff = compare(a, b);

   221

			if ((!desc && diff <= 0) || (desc && diff >= 0)) {

   222

				if (offset != 0) {

   223

					/* Jump back to the last direction switch point */

   224

					a += offset;

   225

					b += offset;

   226

					offset = 0;

   227

					continue;

   228

				}

   229

				a++;

   230

				b++;

   231

				length--;

   232

			} else {

   233

				Swap(*a, *b);

   234

				if (a != this->data) {

   235

					offset++;

   236

					a--;

   237

					b--;

   238

				}

   239

			}

   240

		}

   241

	}

   242

   243

	/**

   244

	 * Hand the array of sort function pointers to the sort list

   245

	 *

   246

	 * @param n_funcs The pointer to the first sort func

   247

	 */

   248

	void SetSortFuncs(SortFunction* const* n_funcs)

   249

	{

   250

		this->func_list = n_funcs;

   251

	}

   252

   253

	/**

   254

	 * Overload of Sort()

   255

	 * Overloaded to reduce external code

   256

	 */

   257

	void Sort()

   258

	{

   259

		assert(this->func_list != NULL);

   260

		this->Sort(this->func_list[this->sort_type]);

   261

	}

   262

   263

	/**

   264

	 * Check if a rebuild is needed

   265

	 * @return true if a rebuild is needed

   266

	 */

   267

	bool NeedRebuild() const

   268

	{

   269

		return HASBITS(this->flags, VL_REBUILD);

   270

	}

   271

   272

	/**

   273

	 * Force that a rebuild is needed

   274

	 */

   275

	void ForceRebuild()

   276

	{

   277

		SETBITS(this->flags, VL_REBUILD);

   278

	}

   279

   280

	/**

   281

	 * Notify the sortlist that the rebuild is done

   282

	 *

   283

	 * @note This forces a resort

   284

	 */

   285

	void RebuildDone()

   286

	{

   287

		CLRBITS(this->flags, VL_REBUILD);

   288

		SETBITS(this->flags, VL_RESORT);

   289

	}

   290

};

   291

   292

#endif /* SORTLIST_TYPE_H */