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, ///< create sort-listing to use for qsort and friends

    16

	VL_END     = 1 << 3,

    17

};

    18

DECLARE_ENUM_AS_BIT_SET(SortListFlags);

    19

    20

struct Listing {

    21

	bool order;    ///< Ascending/descending

    22

	byte criteria; ///< Sorting criteria

    23

};

    24

    25

template <typename T>

    26

class GUIList : public SmallVector<T, 32> {

    27

public:

    28

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

    29

    30

public: // Temporary: public for conversion only

    31

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

    32

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

    33

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

    34

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

    35

    36

	/**

    37

	 * Check if the list is sortable

    38

	 *

    39

	 * @return true if we can sort the list

    40

	 */

    41

	bool IsSortable() const

    42

	{

    44

	}

    45

    46

	/**

    47

	 * Reset the resort timer

    48

	 */

    49

	void ResetResortTimer()

    50

	{

    51

		/* Resort every 10 days */

    52

		this->resort_timer = DAY_TICKS * 10;

    53

	}

    54

    55

public:

    56

	GUIList() :

    57

		func_list(NULL),

    58

		flags(VL_NONE),

    59

		sort_type(0),

    60

		resort_timer(1)

    61

	{};

    62

    63

	/**

    64

	 * Get the sorttype of the list

    65

	 *

    66

	 * @return The current sorttype

    67

	 */

    68

	uint8 SortType() const

    69

	{

    70

		return this->sort_type;

    71

	}

    72

    73

	/**

    74

	 * Set the sorttype of the list

    75

	 *

    76

	 * @param n_type the new sort type

    77

	 */

    78

	void SetSortType(uint8 n_type)

    79

	{

    80

		if (this->sort_type != n_type) {

    81

			SETBITS(this->flags, VL_RESORT);

    82

			this->sort_type = n_type;

    83

		}

    84

	}

    85

    86

	/**

    87

	 * Export current sort conditions

    88

	 *

    89

	 * @return the current sort conditions

    90

	 */

    91

	Listing GetListing() const

    92

	{

    93

		Listing l;

    94

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

    95

		l.criteria = this->sort_type;

    96

    97

		return l;

    98

	}

    99

   100

	/**

   101

	 * Import sort conditions

   102

	 *

   103

	 * @param l The sport conditions we want to use

   104

	 */

   105

	void SetListing(Listing l)

   106

	{

   107

		if (l.order) {

   108

			SETBITS(this->flags, VL_DESC);

   109

		} else {

   110

			CLRBITS(this->flags, VL_DESC);

   111

		}

   112

		this->sort_type = l.criteria;

   113

	}

   114

   115

	/**

   116

	 * Check if a resort is needed next loop

   117

	 *  If used the resort timer will decrease every call

   118

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

   119

	 *  the timer will be reset.

   120

	 *

   121

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

   122

	 */

   123

	bool NeedResort()

   124

	{

   125

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

   126

			SETBITS(this->flags, VL_RESORT);

   127

			this->ResetResortTimer();

   128

			return true;

   129

		}

   130

		return false;

   131

	}

   132

   133

	/**

   134

	 * Force a resort next Sort call

   135

	 *  Reset the resort timer if used too.

   136

	 */

   137

	void ForceResort()

   138

	{

   139

		SETBITS(this->flags, VL_RESORT);

   140

	}

   141

   142

	/**

   143

	 * Check if the sort order is descending

   144

	 *

   145

	 * @return true if the sort order is descending

   146

	 */

   147

	bool IsDescSortOrder() const

   148

	{

   149

		return HASBITS(this->flags, VL_DESC);

   150

	}

   151

   152

	/**

   153

	 * Toogle the sort order

   154

	 *  Since that is the worst condition for the sort function

   155

	 *  reverse the list here.

   156

	 */

   157

	FORCEINLINE void ToggleSortOrder()

   158

	{

   159

		this->flags ^= VL_DESC;

   160

   161

		if (this->IsSortable()) {

   162

			T *a = this->data;

   163

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

   164

   165

			do {

   166

				Swap(*a, *b);

   167

			} while (((a + 1) != b) && (++a != --b));

   168

		}

   169

	}

   170

   171

	/**

   172

	 * GnomeSort algorithm

   173

	 *  This sorting uses a slightly modifyied Gnome search.

   174

	 *  The basic Gnome search trys to sort already sorted

   175

	 *  list parts. The modification skips these.

   176

	 *

   177

	 * @param compare The function to compare two list items

   178

	 * */

   179

	FORCEINLINE void Sort(SortFunction compare)

   180

	{

   188

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

   189

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

   190

   191

		T *a = this->data;

   192

		T *b = a + 1;

   193

   194

		uint length = this->items;

   195

		uint offset = 0; // Jump variable

   196

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

   197

   198

		while (length > 1) {

   199

			const int diff = compare(a, b);

   200

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

   201

				if (offset != 0) {

   202

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

   203

					a += offset;

   204

					b += offset;

   205

					offset = 0;

   206

					continue;

   207

				}

   208

				a++;

   209

				b++;

   210

				length--;

   211

			} else {

   212

				Swap(*a, *b);

   213

				if (a != this->data) {

   214

					offset++;

   215

					a--;

   216

					b--;

   217

				}

   218

			}

   219

		}

   220

	}

   221

   222

	/**

   223

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

   224

	 *

   225

	 * @param n_funcs The pointer to the first sort func

   226

	 */

   227

	void SetSortFuncs(SortFunction* const* n_funcs)

   228

	{

   229

		this->func_list = n_funcs;

   230

	}

   231

   232

	/**

   233

	 * Overload of Sort()

   234

	 * Overloaded to reduce external code

   235

	 */

   236

	void Sort()

   237

	{

   238

		assert(this->func_list != NULL);

   239

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

   240

	}

   241

   242

	/**

   243

	 * Check if a rebuild is needed

   244

	 * @return true if a rebuild is needed

   245

	 */

   246

	bool NeedRebuild() const

   247

	{

   248

		return HASBITS(this->flags, VL_REBUILD);

   249

	}

   250

   251

	/**

   252

	 * Force that a rebuild is needed

   253

	 */

   254

	void ForceRebuild()

   255

	{

   256

		SETBITS(this->flags, VL_REBUILD);

   257

	}

   258

   259

	/**

   260

	 * Notify the sortlist that the rebuild is done

   261

	 *

   262

	 * @note This forces a resort

   263

	 */

   264

	void RebuildDone()

   265

	{

   266

		CLRBITS(this->flags, VL_REBUILD);

   267

		SETBITS(this->flags, VL_RESORT);

   268

	}

   269

};

   270

   271

#endif /* SORTLIST_TYPE_H */