diff options
Diffstat (limited to 'libraries/irrlicht-1.8/include/heapsort.h')
-rw-r--r-- | libraries/irrlicht-1.8/include/heapsort.h | 70 |
1 files changed, 0 insertions, 70 deletions
diff --git a/libraries/irrlicht-1.8/include/heapsort.h b/libraries/irrlicht-1.8/include/heapsort.h deleted file mode 100644 index a2e2c38..0000000 --- a/libraries/irrlicht-1.8/include/heapsort.h +++ /dev/null | |||
@@ -1,70 +0,0 @@ | |||
1 | // Copyright (C) 2002-2012 Nikolaus Gebhardt | ||
2 | // This file is part of the "Irrlicht Engine". | ||
3 | // For conditions of distribution and use, see copyright notice in irrlicht.h | ||
4 | |||
5 | #ifndef __IRR_HEAPSORT_H_INCLUDED__ | ||
6 | #define __IRR_HEAPSORT_H_INCLUDED__ | ||
7 | |||
8 | #include "irrTypes.h" | ||
9 | |||
10 | namespace irr | ||
11 | { | ||
12 | namespace core | ||
13 | { | ||
14 | |||
15 | //! Sinks an element into the heap. | ||
16 | template<class T> | ||
17 | inline void heapsink(T*array, s32 element, s32 max) | ||
18 | { | ||
19 | while ((element<<1) < max) // there is a left child | ||
20 | { | ||
21 | s32 j = (element<<1); | ||
22 | |||
23 | if (j+1 < max && array[j] < array[j+1]) | ||
24 | j = j+1; // take right child | ||
25 | |||
26 | if (array[element] < array[j]) | ||
27 | { | ||
28 | T t = array[j]; // swap elements | ||
29 | array[j] = array[element]; | ||
30 | array[element] = t; | ||
31 | element = j; | ||
32 | } | ||
33 | else | ||
34 | return; | ||
35 | } | ||
36 | } | ||
37 | |||
38 | |||
39 | //! Sorts an array with size 'size' using heapsort. | ||
40 | template<class T> | ||
41 | inline void heapsort(T* array_, s32 size) | ||
42 | { | ||
43 | // for heapsink we pretent this is not c++, where | ||
44 | // arrays start with index 0. So we decrease the array pointer, | ||
45 | // the maximum always +2 and the element always +1 | ||
46 | |||
47 | T* virtualArray = array_ - 1; | ||
48 | s32 virtualSize = size + 2; | ||
49 | s32 i; | ||
50 | |||
51 | // build heap | ||
52 | |||
53 | for (i=((size-1)/2); i>=0; --i) | ||
54 | heapsink(virtualArray, i+1, virtualSize-1); | ||
55 | |||
56 | // sort array, leave out the last element (0) | ||
57 | for (i=size-1; i>0; --i) | ||
58 | { | ||
59 | T t = array_[0]; | ||
60 | array_[0] = array_[i]; | ||
61 | array_[i] = t; | ||
62 | heapsink(virtualArray, 1, i + 1); | ||
63 | } | ||
64 | } | ||
65 | |||
66 | } // end namespace core | ||
67 | } // end namespace irr | ||
68 | |||
69 | #endif | ||
70 | |||