# sort_func.hpp

Go to the documentation of this file.

    00001 /* $Id: sort_func.hpp 17530 2009-09-13 17:47:07Z rubidium $ */
    00002
    00003 /*
    00004  * This file is part of OpenTTD.
    00005  * 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.
    00006  * 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.
    00007  * 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/>.
    00008  */
    00009
    00012 #ifndef SORT_FUNC_HPP
    00013 #define SORT_FUNC_HPP
    00014
    00015 #include <stdlib.h>
    00016 #include "math_func.hpp"
    00017 #include "mem_func.hpp"
    00018
    00029 template <typename T>
    00030 static FORCEINLINE void QSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
    00031 {
    00032   if (num < 2) return;
    00033
    00034   qsort(base, num, sizeof(T), (int (CDECL *)(const void *, const void *))comparator);
    00035
    00036   if (desc) MemReverseT(base, num);
    00037 }
    00038
    00053 template <typename T>
    00054 static inline void GSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
    00055 {
    00056   if (num < 2) return;
    00057
    00058   assert(base != NULL);
    00059   assert(comparator != NULL);
    00060
    00061   T *a = base;
    00062   T *b = base + 1;
    00063   uint offset = 0;
    00064
    00065   while (num > 1) {
    00066     const int diff = comparator(a, b);
    00067     if ((!desc && diff <= 0) || (desc && diff >= 0)) {
    00068       if (offset != 0) {
    00069         /* Jump back to the last direction switch point */
    00070         a += offset;
    00071         b += offset;
    00072         offset = 0;
    00073         continue;
    00074       }
    00075
    00076       a++;
    00077       b++;
    00078       num--;
    00079     } else {
    00080       Swap(*a, *b);
    00081
    00082       if (a == base) continue;
    00083
    00084       a--;
    00085       b--;
    00086       offset++;
    00087     }
    00088   }
    00089 }
    00090
    00091 #endif /* SORT_FUNC_HPP */