skidd13@10962: /* $Id$ */
skidd13@10962: 
skidd13@10962: /** @file sort_func.hpp Functions related to sorting operations. */
skidd13@10962: 
skidd13@10962: #ifndef SORT_FUNC_HPP
skidd13@10962: #define SORT_FUNC_HPP
skidd13@10962: 
skidd13@10962: #include <stdlib.h>
skidd13@10962: #include "math_func.hpp"
skidd13@10962: #include "mem_func.hpp"
skidd13@10962: 
skidd13@10962: /**
skidd13@10962:  * Type safe qsort()
skidd13@10962:  *
skidd13@10962:  * @todo replace the normal qsort with this one
skidd13@10962:  * @note Use this sort for irregular sorted data.
skidd13@10962:  *
skidd13@10962:  * @param base Pointer to the first element of the array to be sorted.
skidd13@10962:  * @param num Number of elements in the array pointed by base.
skidd13@10962:  * @param comparator Function that compares two elements.
skidd13@10962:  * @param desc Sort descending.
skidd13@10962:  */
skidd13@11049: template <typename T>
skidd13@11049: static FORCEINLINE void QSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
skidd13@10962: {
skidd13@10962: 	if (num < 2) return;
skidd13@10962: 
skidd13@10962: 	qsort(base, num, sizeof(T), (int (CDECL *)(const void *, const void *))comparator);
skidd13@10962: 
skidd13@10962: 	if (desc) MemReverseT(base, num);
skidd13@10962: }
skidd13@10962: 
skidd13@10962: /**
skidd13@10962:  * Type safe Gnome Sort.
skidd13@10962:  *
skidd13@10962:  * This is a slightly modifyied Gnome search. The basic
skidd13@10962:  * Gnome search trys to sort already sorted list parts.
skidd13@10962:  * The modification skips these.
skidd13@10962:  *
skidd13@10962:  * @note Use this sort for presorted / regular sorted data.
skidd13@10962:  *
skidd13@10962:  * @param base Pointer to the first element of the array to be sorted.
skidd13@10962:  * @param num Number of elements in the array pointed by base.
skidd13@10962:  * @param comparator Function that compares two elements.
skidd13@10962:  * @param desc Sort descending.
skidd13@10962:  */
skidd13@11049: template <typename T>
skidd13@11049: static inline void GSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
skidd13@10962: {
skidd13@10962: 	if (num < 2) return;
skidd13@10962: 
skidd13@10962: 	assert(base != NULL);
skidd13@10962: 	assert(comparator != NULL);
skidd13@10962: 
skidd13@10962: 	T *a = base;
skidd13@10962: 	T *b = base + 1;
skidd13@10962: 	uint offset = 0;
skidd13@10962: 
skidd13@10962: 	while (num > 1) {
skidd13@10962: 		const int diff = comparator(a, b);
skidd13@10962: 		if ((!desc && diff <= 0) || (desc && diff >= 0)) {
skidd13@10962: 			if (offset != 0) {
skidd13@10962: 				/* Jump back to the last direction switch point */
skidd13@10962: 				a += offset;
skidd13@10962: 				b += offset;
skidd13@10962: 				offset = 0;
skidd13@10962: 				continue;
skidd13@10962: 			}
skidd13@10962: 
skidd13@10962: 			a++;
skidd13@10962: 			b++;
skidd13@10962: 			num--;
skidd13@10962: 		} else {
skidd13@10962: 			Swap(*a, *b);
skidd13@10962: 
skidd13@10962: 			if (a == base) continue;
skidd13@10962: 
skidd13@10962: 			a--;
skidd13@10962: 			b--;
skidd13@10962: 			offset++;
skidd13@10962: 		}
skidd13@10962: 	}
skidd13@10962: }
skidd13@10962: 
skidd13@10962: #endif /* SORT_FUNC_HPP */