OpenTTD
sort_func.hpp
Go to the documentation of this file.
1 /* $Id: sort_func.hpp 24900 2013-01-08 22:46:42Z planetmaker $ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
8  */
9 
12 #ifndef SORT_FUNC_HPP
13 #define SORT_FUNC_HPP
14 
15 #include "mem_func.hpp"
16 
27 template <typename T>
28 static inline void QSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
29 {
30  if (num < 2) return;
31 
32  qsort(base, num, sizeof(T), (int (CDECL *)(const void *, const void *))comparator);
33 
34  if (desc) MemReverseT(base, num);
35 }
36 
51 template <typename T>
52 static inline void GSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
53 {
54  if (num < 2) return;
55 
56  assert(base != NULL);
57  assert(comparator != NULL);
58 
59  T *a = base;
60  T *b = base + 1;
61  uint offset = 0;
62 
63  while (num > 1) {
64  const int diff = comparator(a, b);
65  if ((!desc && diff <= 0) || (desc && diff >= 0)) {
66  if (offset != 0) {
67  /* Jump back to the last direction switch point */
68  a += offset;
69  b += offset;
70  offset = 0;
71  continue;
72  }
73 
74  a++;
75  b++;
76  num--;
77  } else {
78  Swap(*a, *b);
79 
80  if (a == base) continue;
81 
82  a--;
83  b--;
84  offset++;
85  }
86  }
87 }
88 
89 #endif /* SORT_FUNC_HPP */
static void Swap(T &a, T &b)
Type safe swap operation.
Definition: math_func.hpp:277
static void GSortT(T *base, uint num, int(CDECL *comparator)(const T *, const T *), bool desc=false)
Type safe Gnome Sort.
Definition: sort_func.hpp:52
static void MemReverseT(T *ptr1, T *ptr2)
Type safe memory reverse operation.
Definition: mem_func.hpp:79
Functions related to memory operations.
static void QSortT(T *base, uint num, int(CDECL *comparator)(const T *, const T *), bool desc=false)
Type safe qsort()
Definition: sort_func.hpp:28