2 Copyright (C) 2005 John Tsiombikas <nuclear@siggraph.org>
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.
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.
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
19 /* Priority sort template function
21 * Author: Mihalis Georgoulopoulos 2005
27 #ifndef _PSORT_HEADER_
28 #define _PSORT_HEADER_
30 #define SORT_LOHI false
31 #define SORT_HILO true
33 template <class T> int less(const T* a, const T* b)
38 template <class T> int greater(const T* a, const T* b)
43 template <class T, class P> void sort(T *elements, P *priorities, unsigned int n, bool hilo)
45 int (*criterion)(const P*, const P*);
52 P **pointers = new P*[n];
53 for (unsigned int i=0; i<n; i++)
54 pointers[i] = priorities + i;
56 // sort priority pointers
57 std::sort(pointers, pointers + n, criterion);
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++)
64 sorted_el[i] = elements[pointers[i] - priorities];
65 sorted_pr[i] = *pointers[i];
68 memcpy(elements, sorted_el, n * sizeof(T));
69 memcpy(priorities, sorted_pr, n * sizeof(P));
77 #endif // ndef _PSORT_HEADER_