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

diff --git a/src/others/irrlicht-1.8.1/include/heapsort.h b/src/others/irrlicht-1.8.1/include/heapsort.h new file mode 100644 index 0000000..6f87665 --- /dev/null +++ b/src/others/irrlicht-1.8.1/include/heapsort.h
@@ -0,0 +1,70 @@
	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