← Back to branch summary

~ubuntu-branches/debian/squeeze/openttd/squeeze

« back to all changes in this revision

Viewing changes to src/core/sort_func.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Jordi Mallach, Matthijs Kooijman, Jordi Mallach
  • Date: 2009-04-15 18:22:10 UTC
  • mfrom: (1.1.6 upstream) (2.1.3 squeeze)
  • Revision ID: james.westby@ubuntu.com-20090415182210-22ktb8kdbp2tf3bm
[ Matthijs Kooijman ]
* New upstream release.
* Remove Debian specific desktop file, upstream provides one now. 
* Add debian/watch file.

[ Jordi Mallach ]
* Bump Standards-Version to 3.8.1, with no changes required.
* Move to debhelper compat 7. Bump Build-Depends accordingly.
* Use dh_prep.
* Add "set -e" to config script.
* Remove a few extra doc files that get installed by upstream Makefile.
* Add more complete copyright information.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/sort_func.hpp
 
1
/* $Id: sort_func.hpp 13606 2008-06-22 15:21:51Z skidd13 $ */
 
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
static 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
static inline 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 */