src/core/sort_func.hpp

   1 /* $Id$ */
   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
  10 /** @file sort_func.hpp Functions related to sorting operations. */
  11
  12 #ifndef SORT_FUNC_HPP
  13 #define SORT_FUNC_HPP
  14
  15 #include "mem_func.hpp"
  16
  17 /**
  18  * Type safe qsort()
  19  *
  20  * @note Use this sort for irregular sorted data.
  21  *
  22  * @param base Pointer to the first element of the array to be sorted.
  23  * @param num Number of elements in the array pointed by base.
  24  * @param comparator Function that compares two elements.
  25  * @param desc Sort descending.
  26  */
  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
  37 /**
  38  * Type safe Gnome Sort.
  39  *
  40  * This is a slightly modified Gnome search. The basic
  41  * Gnome search tries to sort already sorted list parts.
  42  * The modification skips these.
  43  *
  44  * @note Use this sort for presorted / regular sorted data.
  45  *
  46  * @param base Pointer to the first element of the array to be sorted.
  47  * @param num Number of elements in the array pointed by base.
  48  * @param comparator Function that compares two elements.
  49  * @param desc Sort descending.
  50  */
  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 */