git.mutantstargoat.com Git - summerhack/blob - src/3dengfx/src/common/psort.hpp

   1 /*
   2 Copyright (C) 2005 John Tsiombikas <nuclear@siggraph.org>
   3
   4 This program is free software; you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation; either version 2 of the License, or
   7 (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17 */
  18
  19 /* Priority sort template function
  20  *
  21  * Author: Mihalis Georgoulopoulos 2005
  22  */
  23
  24 #include <cstring>
  25 #include <algorithm>
  26
  27 #ifndef _PSORT_HEADER_
  28 #define _PSORT_HEADER_
  29
  30 #define SORT_LOHI       false
  31 #define SORT_HILO       true
  32
  33 template <class T> int less(const T* a, const T* b)
  34 {
  35         return (*a < *b);
  36 }
  37
  38 template <class T> int greater(const T* a, const T* b)
  39 {
  40         return !(*a < *b);
  41 }
  42
  43 template <class T, class P> void sort(T *elements, P *priorities, unsigned int n, bool hilo)
  44 {
  45         int (*criterion)(const P*, const P*);
  46
  47         if (hilo)
  48                 criterion = greater;
  49         else
  50                 criterion = less;
  51
  52         P **pointers = new P*[n];
  53         for (unsigned int i=0; i<n; i++)
  54                 pointers[i] = priorities + i;
  55
  56         // sort priority pointers
  57         std::sort(pointers, pointers + n, criterion);
  58
  59         // collect sorted items
  60         T *sorted_el = new T[n];
  61         P *sorted_pr = new P[n];
  62         for (unsigned int i=0; i<n; i++)
  63         {
  64                 sorted_el[i] = elements[pointers[i] - priorities];
  65                 sorted_pr[i] = *pointers[i];
  66         }
  67
  68         memcpy(elements, sorted_el, n * sizeof(T));
  69         memcpy(priorities, sorted_pr, n * sizeof(P));
  70
  71         // cleanup
  72         delete [] pointers;
  73         delete [] sorted_el;
  74         delete [] sorted_pr;
  75 }
  76
  77 #endif // ndef _PSORT_HEADER_