[Suggested addition]heapsort with custom compare function

[CuteAlien]

Currently irrArrays can't be sorted with different operators as they always use the operator< which certainly can't be overloaded more than once.

I realized that when I tried to simplify (and make faster) GUITable::orderRows.

The following implementation is identical to the old heapsort, it just offers an additional parameter for a custom compare function. I also added two function objects (Less, Greater) for typical sorting operations. Calling the new heapsort with 'Less' as compare function will work like the old heapsort. That means, it could also replace it, though I'm not sure if I would trust compilers enough to inline that stuff good enough to get the same speed in the end. So I would probably just add the new heapsort additionally to heapsort.h even if this leads to some code duplication. But certainly it's up to the engine programmers what they prefer :-)

Code: Select all

//! Function object which can be used for sorting
template<class T>
bool Less(const T& a, const T& b)
{
	return a < b;
}

//! Function object which can be used for sorting
template<class T>
bool Greater(const T& a, const T& b)
{
	return a > b;
}

//! Sinks an element into the heap with a custom compare function
template<class T, class Compare>
inline void heapsink(T*array, s32 element, s32 max, Compare cmp)
{
	while ((element<<1) < max)	// there is a left child
	{
		s32 j = (element<<1);
	
		if (j+1 < max && cmp(array[j],array[j+1]) )
			j = j+1;							// take right child

		if ( cmp( 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 with a custom compare function
template<class T, class Compare>
inline void heapsort(T* array_, s32 size, Compare cmp)
{
	// 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, cmp);

	// sort array

	for (i=size-1; i>=0; --i)	
	{
		T t = array_[0];
		array_[0] = array_[i];
		array_[i] = t;
		heapsink(virtualArray, 1, i + 1, cmp);
	}
}

Usage example:

Code: Select all

	irr::core::array<int> mytest;
	irr::core::stringc str;
	mytest.push_back(1);
	mytest.push_back(11);
	mytest.push_back(4);
	mytest.push_back(2);
	mytest.push_back(7);
	mytest.push_back(3);
	mytest.push_back(5);
	mytest.push_back(7);
	mytest.push_back(1);

	str = "";
	for ( u32 i=0; i < mytest.size(); ++i )
	{
		str += irr::core::stringc(mytest[i]);
		str += ' ';
	}

	heapsort(mytest.pointer(), mytest.size(), irr::core::Greater<int> );
	str = "";
	for ( u32 i=0; i < mytest.size(); ++i )
	{
		str += irr::core::stringc(mytest[i]);
		str += ' ';
	}

	heapsort(mytest.pointer(), mytest.size(), irr::core::Less<int> );
	str = "";
	for ( u32 i=0; i < mytest.size(); ++i )
	{
		str += irr::core::stringc(mytest[i]);
		str += ' ';
	}

[Saturn]

A useful addition, though I'd prefer real function objects over template functions. With this I mean structs/classes that override operator(). These are more flexible as they can be used together with adaptors from STL and boost.

Actually you already can sort an irr::core::array anyway you like.

Code: Select all

std::sort(myArray.getPointer(), myArray.getPointer() + array.getSize(), MyComparator());

Both the std::sort way and your proposal break binary_search though, unless the same comparator is used here too.

And where we are at this, not only sort should have this overload, linear_search and reverse_linear_search should too. Often you're not looking for an identity, but for the first element satisfying a certain requirement.

[vitek]

A useful addition, though I'd prefer real function objects over template functions.

The above implementation of heapsink and heapsort are both compatible with function objects. If you have a peek at std::sort, you will see that the declaration is similar, the difference being that it uses iterators instead of a pointer and a length.

With this I mean structs/classes that override operator(). These are more flexible as they can be used together with adaptors from STL and boost.

Again, his code is fully compatible with function objects. The only requirement it has is that the type Compare be callable. For objects they need to implement operator(), and functions don't need anything.

And where we are at this, not only sort should have this overload, linear_search and reverse_linear_search should too. Often you're not looking for an identity, but for the first element satisfying a certain requirement.

Actually, the best solution would be to switch over to using the C++ Standard Library containers and algorithms. Unfortunately the Irrlicht development staff [mostly Niko I think] has been resistant to making this change.

Travis

[Saturn]

Oops, you're right of course.