summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorskidd13 <skidd13@openttd.org>2008-05-26 16:44:48 +0000
committerskidd13 <skidd13@openttd.org>2008-05-26 16:44:48 +0000
commitf202f1dda6105fdf4ceb57b60780295eff95f119 (patch)
treef50b341afc61845a2bda6640aa407afe7bb96d65
parent781b90ac91b071f407aa32b3bbea1d94a07912b7 (diff)
downloadopenttd-f202f1dda6105fdf4ceb57b60780295eff95f119.tar.xz
(svn r13267) -Codechange: extend GUIList with a GnomeSort
-rw-r--r--src/sortlist_type.h248
1 files changed, 244 insertions, 4 deletions
diff --git a/src/sortlist_type.h b/src/sortlist_type.h
index fc325754c..3a8d2f0b9 100644
--- a/src/sortlist_type.h
+++ b/src/sortlist_type.h
@@ -6,6 +6,7 @@
#define SORTLIST_TYPE_H
#include "misc/smallvec.h"
+#include "date_type.h"
enum SortListFlags {
VL_NONE = 0, ///< no sort
@@ -22,10 +23,249 @@ struct Listing {
};
template <typename T>
-struct GUIList : public SmallVector<T, 32> {
- SortListFlags flags; ///< used to control sorting/resorting/etc.
- uint16 resort_timer; ///< resort list after a given amount of ticks if set
- byte sort_type; ///< what criteria to sort on
+class GUIList : public SmallVector<T, 32> {
+public:
+ typedef int SortFunction(const T*, const T*);
+
+public: // Temporary: public for conversion only
+ SortFunction* const *func_list; ///< The sort criteria functions
+ SortListFlags flags; ///< used to control sorting/resorting/etc.
+ uint8 sort_type; ///< what criteria to sort on
+ uint16 resort_timer; ///< resort list after a given amount of ticks if set
+
+ /**
+ * Check if the list is sortable
+ *
+ * @return true if we can sort the list
+ */
+ bool IsSortable() const
+ {
+ return (this->data != NULL && this->items > 2);
+ }
+
+ /**
+ * Reset the resort timer
+ */
+ void ResetResortTimer()
+ {
+ /* Resort every 10 days */
+ this->resort_timer = DAY_TICKS * 10;
+ }
+
+public:
+ GUIList() :
+ func_list(NULL),
+ flags(VL_NONE),
+ sort_type(0),
+ resort_timer(1)
+ {};
+
+ /**
+ * Get the sorttype of the list
+ *
+ * @return The current sorttype
+ */
+ uint8 SortType() const
+ {
+ return this->sort_type;
+ }
+
+ /**
+ * Set the sorttype of the list
+ *
+ * @param n_type the new sort type
+ */
+ void SetSortType(uint8 n_type)
+ {
+ if (this->sort_type != n_type) {
+ SETBITS(this->flags, VL_RESORT);
+ this->sort_type = n_type;
+ }
+ }
+
+ /**
+ * Export current sort conditions
+ *
+ * @return the current sort conditions
+ */
+ Listing GetListing() const
+ {
+ Listing l;
+ l.order = HASBITS(this->flags, VL_DESC);
+ l.criteria = this->sort_type;
+
+ return l;
+ }
+
+ /**
+ * Import sort conditions
+ *
+ * @param l The sport conditions we want to use
+ */
+ void SetListing(Listing l)
+ {
+ if (l.order) {
+ SETBITS(this->flags, VL_DESC);
+ } else {
+ CLRBITS(this->flags, VL_DESC);
+ }
+ this->sort_type = l.criteria;
+ }
+
+ /**
+ * Check if a resort is needed next loop
+ * If used the resort timer will decrease every call
+ * till 0. If 0 reached the resort bit will be set and
+ * the timer will be reset.
+ *
+ * @return true if resort bit is set for next loop
+ */
+ bool NeedResort()
+ {
+ if (--this->resort_timer == 0) {
+ SETBITS(this->flags, VL_RESORT);
+ this->ResetResortTimer();
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Force a resort next Sort call
+ * Reset the resort timer if used too.
+ */
+ void ForceResort()
+ {
+ SETBITS(this->flags, VL_RESORT);
+ }
+
+ /**
+ * Check if the sort order is descending
+ *
+ * @return true if the sort order is descending
+ */
+ bool IsDescSortOrder() const
+ {
+ return HASBITS(this->flags, VL_DESC);
+ }
+
+ /**
+ * Toogle the sort order
+ * Since that is the worst condition for the sort function
+ * reverse the list here.
+ */
+ FORCEINLINE void ToggleSortOrder()
+ {
+ this->flags ^= VL_DESC;
+
+ if (this->IsSortable()) {
+ T *a = this->data;
+ T *b = a + (this->items - 1);
+
+ do {
+ Swap(*a, *b);
+ } while (((a + 1) != b) && (++a != --b));
+ }
+ }
+
+ /**
+ * GnomeSort algorithm
+ * This sorting uses a slightly modifyied Gnome search.
+ * The basic Gnome search trys to sort already sorted
+ * list parts. The modification skips these.
+ *
+ * @param compare The function to compare two list items
+ * */
+ FORCEINLINE void Sort(SortFunction compare)
+ {
+ /* Do not sort when the list is not sortable */
+ if (!this->IsSortable()) return;
+
+ /* Do not sort if the resort bit is not set */
+ if (!HASBITS(this->flags, VL_RESORT)) return;
+
+ T *a = this->data;
+ T *b = a + 1;
+
+ uint length = this->items;
+ uint offset = 0; // Jump variable
+ const bool desc = HASBITS(this->flags, VL_DESC);
+
+ while (length > 1) {
+ const int diff = compare(a, b);
+ if ((!desc && diff <= 0) || (desc && diff >= 0)) {
+ if (offset != 0) {
+ /* Jump back to the last direction switch point */
+ a += offset;
+ b += offset;
+ offset = 0;
+ continue;
+ }
+ a++;
+ b++;
+ length--;
+ } else {
+ Swap(*a, *b);
+ if (a != this->data) {
+ offset++;
+ a--;
+ b--;
+ }
+ }
+ }
+
+ this->ResetResortTimer();
+
+ CLRBITS(this->flags, VL_RESORT);
+ }
+
+ /**
+ * Hand the array of sort function pointers to the sort list
+ *
+ * @param n_funcs The pointer to the first sort func
+ */
+ void SetSortFuncs(SortFunction* const* n_funcs)
+ {
+ this->func_list = n_funcs;
+ }
+
+ /**
+ * Overload of Sort()
+ * Overloaded to reduce external code
+ */
+ void Sort()
+ {
+ assert(this->func_list != NULL);
+ this->Sort(this->func_list[this->sort_type]);
+ }
+
+ /**
+ * Check if a rebuild is needed
+ * @return true if a rebuild is needed
+ */
+ bool NeedRebuild() const
+ {
+ return HASBITS(this->flags, VL_REBUILD);
+ }
+
+ /**
+ * Force that a rebuild is needed
+ */
+ void ForceRebuild()
+ {
+ SETBITS(this->flags, VL_REBUILD);
+ }
+
+ /**
+ * Notify the sortlist that the rebuild is done
+ *
+ * @note This forces a resort
+ */
+ void RebuildDone()
+ {
+ CLRBITS(this->flags, VL_REBUILD);
+ SETBITS(this->flags, VL_RESORT);
+ }
};
#endif /* SORTLIST_TYPE_H */