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:

    29

	typedef int CDECL SortFunction(const T*, const T*);

    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

   192

	 * */

   194

	{

   195

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

   197

   198

		CLRBITS(this->flags, VL_RESORT);

   199

   200

		this->ResetResortTimer();

   201

   202

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

   204

   205

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

   206

   207

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

   208

			qsort(this->data, this->items, sizeof(T), (int (CDECL *)(const void *, const void *))compare);

   209

   210

			if (desc) this->Reverse();

   212

		}

   213

   214

		T *a = this->data;

   215

		T *b = a + 1;

   216

   217

		uint length = this->items;

   218

		uint offset = 0; // Jump variable

   219

   220

		while (length > 1) {

   221

			const int diff = compare(a, b);

   222

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

   223

				if (offset != 0) {

   224

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

   225

					a += offset;

   226

					b += offset;

   227

					offset = 0;

   228

					continue;

   229

				}

   230

				a++;

   231

				b++;

   232

				length--;

   233

			} else {

   234

				Swap(*a, *b);

   235

				if (a != this->data) {

   236

					offset++;

   237

					a--;

   238

					b--;

   239

				}

   240

			}

   241

		}

   243

	}

   244

   245

	/**

   246

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

   247

	 *

   248

	 * @param n_funcs The pointer to the first sort func

   249

	 */

   250

	void SetSortFuncs(SortFunction* const* n_funcs)

   251

	{

   252

		this->func_list = n_funcs;

   253

	}

   254

   255

	/**

   256

	 * Overload of Sort()

   257

	 * Overloaded to reduce external code

   260

	 */

   262

	{

   263

		assert(this->func_list != NULL);

   265

	}

   266

   267

	/**

   268

	 * Check if a rebuild is needed

   269

	 * @return true if a rebuild is needed

   270

	 */

   271

	bool NeedRebuild() const

   272

	{

   273

		return HASBITS(this->flags, VL_REBUILD);

   274

	}

   275

   276

	/**

   277

	 * Force that a rebuild is needed

   278

	 */

   279

	void ForceRebuild()

   280

	{

   281

		SETBITS(this->flags, VL_REBUILD);

   282

	}

   283

   284

	/**

   285

	 * Notify the sortlist that the rebuild is done

   286

	 *

   287

	 * @note This forces a resort

   288

	 */

   289

	void RebuildDone()

   290

	{

   291

		CLRBITS(this->flags, VL_REBUILD);

   292

		SETBITS(this->flags, VL_RESORT);

   293

	}

   294

};

   295

   296

#endif /* SORTLIST_TYPE_H */