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 */