nuclear@0: // Copyright (C) 2002-2005 Nikolaus Gebhardt
nuclear@0: // This file is part of the "Irrlicht Engine".
nuclear@0: // For conditions of distribution and use, see copyright notice in irrlicht.h
nuclear@0: 
nuclear@0: #ifndef __IRR_HEAPSORT_H_INCLUDED__
nuclear@0: #define __IRR_HEAPSORT_H_INCLUDED__
nuclear@0: 
nuclear@0: #include "irrTypes.h"
nuclear@0: 
nuclear@0: namespace irr
nuclear@0: {
nuclear@0: namespace core
nuclear@0: {
nuclear@0: 
nuclear@0: //! Sinks an element into the heap.
nuclear@0: template<class T>
nuclear@0: inline void heapsink(T*array, s32 element, s32 max)
nuclear@0: {
nuclear@0: 	while ((element<<1) < max)	// there is a left child
nuclear@0: 	{
nuclear@0: 		s32 j = (element<<1);
nuclear@0: 	
nuclear@0: 		if (j+1 < max && array[j] < array[j+1])
nuclear@0: 			j = j+1;							// take right child
nuclear@0: 
nuclear@0: 		if (array[element] < array[j])
nuclear@0: 		{
nuclear@0: 			T t = array[j];						// swap elements
nuclear@0: 			array[j] = array[element];
nuclear@0: 			array[element] = t;
nuclear@0: 			element = j;
nuclear@0: 		}
nuclear@0: 		else
nuclear@0: 			return;
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: 
nuclear@0: //! Sorts an array with size 'size' using heapsort.
nuclear@0: template<class T>
nuclear@0: inline void heapsort(T* array_, s32 size)
nuclear@0: {
nuclear@0: 	// for heapsink we pretent this is not c++, where
nuclear@0: 	// arrays start with index 0. So we decrease the array pointer,
nuclear@0: 	// the maximum always +2 and the element always +1
nuclear@0: 
nuclear@0: 	T* virtualArray = array_ - 1;
nuclear@0: 	s32 virtualSize = size + 2;
nuclear@0: 	s32 i;
nuclear@0: 
nuclear@0: 	// build heap
nuclear@0: 
nuclear@0: 	for (i=((size-1)/2); i>=0; --i)	
nuclear@0: 		heapsink(virtualArray, i+1, virtualSize-1);
nuclear@0: 
nuclear@0: 	// sort array
nuclear@0: 
nuclear@0: 	for (i=size-1; i>=0; --i)	
nuclear@0: 	{
nuclear@0: 		T t = array_[0];
nuclear@0: 		array_[0] = array_[i];
nuclear@0: 		array_[i] = t;
nuclear@0: 		heapsink(virtualArray, 1, i + 1);
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: } // end namespace core
nuclear@0: } // end namespace irr
nuclear@0: 
nuclear@0: 
nuclear@0: 
nuclear@0: #endif
nuclear@0: