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