1 /* $Id$ */

     2 

     3 /** @file sort_func.hpp Functions related to sorting operations. */

     4 

     5 #ifndef SORT_FUNC_HPP

     6 #define SORT_FUNC_HPP

     7 

     8 #include <stdlib.h>

     9 #include "math_func.hpp"

    10 #include "mem_func.hpp"

    11 

    12 /**

    13  * Type safe qsort()

    14  *

    15  * @todo replace the normal qsort with this one

    16  * @note Use this sort for irregular sorted data.

    17  *

    18  * @param base Pointer to the first element of the array to be sorted.

    19  * @param num Number of elements in the array pointed by base.

    20  * @param comparator Function that compares two elements.

    21  * @param desc Sort descending.

    22  */

    23 template<typename T>

    24 FORCEINLINE void QSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)

    25 {

    26 	if (num < 2) return;

    27 

    28 	qsort(base, num, sizeof(T), (int (CDECL *)(const void *, const void *))comparator);

    29 

    30 	if (desc) MemReverseT(base, num);

    31 }

    32 

    33 /**

    34  * Type safe Gnome Sort.

    35  *

    36  * This is a slightly modifyied Gnome search. The basic

    37  * Gnome search trys to sort already sorted list parts.

    38  * The modification skips these.

    39  *

    40  * @note Use this sort for presorted / regular sorted data.

    41  *

    42  * @param base Pointer to the first element of the array to be sorted.

    43  * @param num Number of elements in the array pointed by base.

    44  * @param comparator Function that compares two elements.

    45  * @param desc Sort descending.

    46  */

    47 template<typename T>

    48 FORCEINLINE void GSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)

    49 {

    50 	if (num < 2) return;

    51 

    52 	assert(base != NULL);

    53 	assert(comparator != NULL);

    54 

    55 	T *a = base;

    56 	T *b = base + 1;

    57 	uint offset = 0;

    58 

    59 	while (num > 1) {

    60 		const int diff = comparator(a, b);

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

    62 			if (offset != 0) {

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

    64 				a += offset;

    65 				b += offset;

    66 				offset = 0;

    67 				continue;

    68 			}

    69 

    70 			a++;

    71 			b++;

    72 			num--;

    73 		} else {

    74 			Swap(*a, *b);

    75 

    76 			if (a == base) continue;

    77 

    78 			a--;

    79 			b--;

    80 			offset++;

    81 		}

    82 	}

    83 }

    84 

    85 #endif /* SORT_FUNC_HPP */