From 7028cbe09c688437910a25623098762bf0fa592d Mon Sep 17 00:00:00 2001
From: David Walter Seikel
Date: Mon, 28 Mar 2016 22:28:34 +1000
Subject: Move Irrlicht to src/others.

---
 src/others/irrlicht-1.8.1/include/heapsort.h | 70 ++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)
 create mode 100644 src/others/irrlicht-1.8.1/include/heapsort.h

(limited to 'src/others/irrlicht-1.8.1/include/heapsort.h')

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
+
-- 
cgit v1.1