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