vrshoot
annotate libs/assimp/irrXML/heapsort.h @ 0:b2f14e535253
initial commit
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sat, 01 Feb 2014 19:58:19 +0200 |
| parents | |
| children |
| rev | line source |
|---|---|
| nuclear@0 | 1 // Copyright (C) 2002-2005 Nikolaus Gebhardt |
| nuclear@0 | 2 // This file is part of the "Irrlicht Engine". |
| nuclear@0 | 3 // For conditions of distribution and use, see copyright notice in irrlicht.h |
| nuclear@0 | 4 |
| nuclear@0 | 5 #ifndef __IRR_HEAPSORT_H_INCLUDED__ |
| nuclear@0 | 6 #define __IRR_HEAPSORT_H_INCLUDED__ |
| nuclear@0 | 7 |
| nuclear@0 | 8 #include "irrTypes.h" |
| nuclear@0 | 9 |
| nuclear@0 | 10 namespace irr |
| nuclear@0 | 11 { |
| nuclear@0 | 12 namespace core |
| nuclear@0 | 13 { |
| nuclear@0 | 14 |
| nuclear@0 | 15 //! Sinks an element into the heap. |
| nuclear@0 | 16 template<class T> |
| nuclear@0 | 17 inline void heapsink(T*array, s32 element, s32 max) |
| nuclear@0 | 18 { |
| nuclear@0 | 19 while ((element<<1) < max) // there is a left child |
| nuclear@0 | 20 { |
| nuclear@0 | 21 s32 j = (element<<1); |
| nuclear@0 | 22 |
| nuclear@0 | 23 if (j+1 < max && array[j] < array[j+1]) |
| nuclear@0 | 24 j = j+1; // take right child |
| nuclear@0 | 25 |
| nuclear@0 | 26 if (array[element] < array[j]) |
| nuclear@0 | 27 { |
| nuclear@0 | 28 T t = array[j]; // swap elements |
| nuclear@0 | 29 array[j] = array[element]; |
| nuclear@0 | 30 array[element] = t; |
| nuclear@0 | 31 element = j; |
| nuclear@0 | 32 } |
| nuclear@0 | 33 else |
| nuclear@0 | 34 return; |
| nuclear@0 | 35 } |
| nuclear@0 | 36 } |
| nuclear@0 | 37 |
| nuclear@0 | 38 |
| nuclear@0 | 39 //! Sorts an array with size 'size' using heapsort. |
| nuclear@0 | 40 template<class T> |
| nuclear@0 | 41 inline void heapsort(T* array_, s32 size) |
| nuclear@0 | 42 { |
| nuclear@0 | 43 // for heapsink we pretent this is not c++, where |
| nuclear@0 | 44 // arrays start with index 0. So we decrease the array pointer, |
| nuclear@0 | 45 // the maximum always +2 and the element always +1 |
| nuclear@0 | 46 |
| nuclear@0 | 47 T* virtualArray = array_ - 1; |
| nuclear@0 | 48 s32 virtualSize = size + 2; |
| nuclear@0 | 49 s32 i; |
| nuclear@0 | 50 |
| nuclear@0 | 51 // build heap |
| nuclear@0 | 52 |
| nuclear@0 | 53 for (i=((size-1)/2); i>=0; --i) |
| nuclear@0 | 54 heapsink(virtualArray, i+1, virtualSize-1); |
| nuclear@0 | 55 |
| nuclear@0 | 56 // sort array |
| nuclear@0 | 57 |
| nuclear@0 | 58 for (i=size-1; i>=0; --i) |
| nuclear@0 | 59 { |
| nuclear@0 | 60 T t = array_[0]; |
| nuclear@0 | 61 array_[0] = array_[i]; |
| nuclear@0 | 62 array_[i] = t; |
| nuclear@0 | 63 heapsink(virtualArray, 1, i + 1); |
| nuclear@0 | 64 } |
| nuclear@0 | 65 } |
| nuclear@0 | 66 |
| nuclear@0 | 67 } // end namespace core |
| nuclear@0 | 68 } // end namespace irr |
| nuclear@0 | 69 |
| nuclear@0 | 70 |
| nuclear@0 | 71 |
| nuclear@0 | 72 #endif |
| nuclear@0 | 73 |