1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/irrXML/heapsort.h	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,73 @@
     1.4 +// Copyright (C) 2002-2005 Nikolaus Gebhardt
     1.5 +// This file is part of the "Irrlicht Engine".
     1.6 +// For conditions of distribution and use, see copyright notice in irrlicht.h
     1.7 +
     1.8 +#ifndef __IRR_HEAPSORT_H_INCLUDED__
     1.9 +#define __IRR_HEAPSORT_H_INCLUDED__
    1.10 +
    1.11 +#include "irrTypes.h"
    1.12 +
    1.13 +namespace irr
    1.14 +{
    1.15 +namespace core
    1.16 +{
    1.17 +
    1.18 +//! Sinks an element into the heap.
    1.19 +template<class T>
    1.20 +inline void heapsink(T*array, s32 element, s32 max)
    1.21 +{
    1.22 +	while ((element<<1) < max)	// there is a left child
    1.23 +	{
    1.24 +		s32 j = (element<<1);
    1.25 +	
    1.26 +		if (j+1 < max && array[j] < array[j+1])
    1.27 +			j = j+1;							// take right child
    1.28 +
    1.29 +		if (array[element] < array[j])
    1.30 +		{
    1.31 +			T t = array[j];						// swap elements
    1.32 +			array[j] = array[element];
    1.33 +			array[element] = t;
    1.34 +			element = j;
    1.35 +		}
    1.36 +		else
    1.37 +			return;
    1.38 +	}
    1.39 +}
    1.40 +
    1.41 +
    1.42 +//! Sorts an array with size 'size' using heapsort.
    1.43 +template<class T>
    1.44 +inline void heapsort(T* array_, s32 size)
    1.45 +{
    1.46 +	// for heapsink we pretent this is not c++, where
    1.47 +	// arrays start with index 0. So we decrease the array pointer,
    1.48 +	// the maximum always +2 and the element always +1
    1.49 +
    1.50 +	T* virtualArray = array_ - 1;
    1.51 +	s32 virtualSize = size + 2;
    1.52 +	s32 i;
    1.53 +
    1.54 +	// build heap
    1.55 +
    1.56 +	for (i=((size-1)/2); i>=0; --i)	
    1.57 +		heapsink(virtualArray, i+1, virtualSize-1);
    1.58 +
    1.59 +	// sort array
    1.60 +
    1.61 +	for (i=size-1; i>=0; --i)	
    1.62 +	{
    1.63 +		T t = array_[0];
    1.64 +		array_[0] = array_[i];
    1.65 +		array_[i] = t;
    1.66 +		heapsink(virtualArray, 1, i + 1);
    1.67 +	}
    1.68 +}
    1.69 +
    1.70 +} // end namespace core
    1.71 +} // end namespace irr
    1.72 +
    1.73 +
    1.74 +
    1.75 +#endif
    1.76 +