diff options
| -rw-r--r-- | src/sortlist_type.h | 248 |
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 */ |