BaseSort< SORTCLASS, FLAGS > Class Template Reference

#include <sort.h>

Detailed Description

template<typename SORTCLASS, BASESORTFLAGS FLAGS = BASESORTFLAGS::NONE>
class maxon::BaseSort< SORTCLASS, FLAGS >

Template for sorting arrays and searching in sorted arrays

To use this template derive a class from it and define the member 'LessThan' that implements an element comparison. If you do searching the member 'IsEqual' needs to be implemented that does an element comparison with the search key as the first argument. If the search key is different from the element type a second LessThan routine is needed (comparing SEARCHKEY to an element).

Template Parameters

SORTCLASS	The class itself. This has to be a derived class of BaseSort.
FLAGS	See BASESORTFLAGS.

Note

Note that the classes that will be sorted have special requirements regarding copy and move constructors .

Note that the comparison must fulfill the condition (a < b) == !(b < a). If this is not the case the sort algorithm will crash. To avoid mistakes when comparing tuples use LexicographicalCompare.

Example for traditional C-style arrays:

class Sort1 : public BaseSort<Sort1>
{
public:
  static inline Bool LessThan(Int a, Int b)
  {
    return a < b;
  }
};
 
...
 
Int array1[100];
 
...
 
Sort1 sort1;
sort1.Sort(&array1[0], &array1[100]); // note that the 'end' iterator is the last element + 1 and not the last element!
sort1.Sort(array1, 100); // even easier

Note

LessThan can be a member of the sort class itself (not static), but needs to be const in that case.

Example for arrays:

class Sort2 : public BaseSort<Sort2>
{
public:
  static inline Bool LessThan(Int a, Int b)
  {
    return a < b;
  }
};
 
...
 
BlockArray<Int> array2;
 
...
 
Sort2  sort2;
sort2.Sort(array2.Begin(), array2.End()); // do not write Sort(&array2[0], &array2[array2.GetCount()]) as this will create a debug assert (the second array access is illegal)
sort2.Sort(array2); // any arrays derived from BaseArray can be passed directly

Example for arbitrary structures with multiple sort criteria:

class MyStruct
{
public:
  String _str;
  Int    _index;
  Float  _weight;
};
 
class Sort3 : public BaseSort<Sort3>
{
public:
  static inline Bool LessThan(const MyStruct& a, const MyStruct& b)
  {
    if (a._weight < b._weight) return true;
    if (a._weight > b._weight) return false;
    return a._index < b._index; // if weights are identical sort by index
  }
};
 
...
 
BlockArray<MyStruct> array3;
 
...
 
Sort3  sort3;
sort3.Sort(array3);

Searching Example:

class MyStruct
{
public:
  String _str;
  Int    _index;
  Float  _weight;
};
 
class MySearch : public BaseSort <MySearch, BlockArray<MyStruct>::Iterator>
{
public:
  // for sorting: compare array element to array element
  static inline Bool LessThan(const MyStruct& a, const MyStruct& b)
  {
    return LexicographicalCompare(a._weight, b._weight, a._index, b._index);
  }
 
  // for searching: compare search key to array element
  static inline Bool LessThan(Float weight, const MyStruct& b)
  {
    return weight < b._weight;
  }
 
  // for searching: compare search key to array element
  static inline Bool IsEqual(Float weight, const MyStruct& b)
  {
    return weight == b._weight;
  }
};
 
...
 
BlockArray<MyStruct> array4;
 
...
 
MySearch search;
search.Sort(array4);
 
...
 
// array is now sorted, we can search it
MyStruct* result = search.Find(5.0, array4);

Public Member Functions
template<typename ITERATOR >
void	Sort (ITERATOR start, ITERATOR end) const
template<typename ITERATOR >
void	Sort (ITERATOR start, Int count) const
template<typename ARRAY >
void	Sort (ARRAY &arr) const
template<typename SEARCHTYPE , typename ITERATOR >
Int	FindIndex (const SEARCHTYPE &key, ITERATOR arr, Int count) const
template<typename SEARCHTYPE , typename ITERATOR >
ITERATOR	Find (const SEARCHTYPE &key, ITERATOR arr, Int count) const
template<typename ARRAY , typename SEARCHTYPE >
ARRAY::ValueType *	Find (const SEARCHTYPE &key, const ARRAY &arr) const
template<typename SEARCHTYPE , typename ITERATOR >
ITERATOR	FindInsertionIndex (const SEARCHTYPE &key, ITERATOR arr, Int count, Int &insertionIndex) const
template<typename ARRAY , typename SEARCHTYPE >
ARRAY::ValueType *	FindInsertionIndex (const SEARCHTYPE &key, const ARRAY &arr, Int &insertionIndex) const

Private Member Functions
Int	Log2 (Int n) const
template<typename ITERATOR , typename CONTENT >
void	ISort (ITERATOR start, Int count, const CONTENT &valType) const

Member Function Documentation

Sort() [1/3]

void Sort	(	ITERATOR	start,
		ITERATOR	end
	)		const

Sort elements of an array, so that the smallest element comes first. Note that the sorting is not guaranteed to be stable (elements with the same sort value may change their order). The time for sorting is O(n * log(n))

Parameters

[in]	start	The start iterator of an array.
[in]	end	The end iterator of an array. Note that this is not the last element! It needs to be the boundary (which is last element + 1). See in the BaseSort class description for examples.

Sort() [2/3]

void Sort	(	ITERATOR	start,
		Int	count
	)		const

Sort elements of an array, so that the smallest element comes first. Note that the sorting is not guaranteed to be stable (elements with the same sort value may change their order). The time for sorting is O(n * log(n))

Parameters

[in]	start	The start iterator of an array.
[in]	count	The number of elements to be sorted.

Sort() [3/3]

void Sort

(

ARRAY &

arr

)

const

Sort elements of an array, so that the smallest element comes first. Note that the sorting is not guaranteed to be stable (elements with the same sort value may change their order). The time for sorting is O(n * log(n))

Parameters

[in]

arr

The array to be sorted.

FindIndex()

Int FindIndex	(	const SEARCHTYPE &	key,
		ITERATOR	arr,
		Int	count
	)		const

Find an element in an array. The array must be in a sorted state. The time for searching will be O(log(n))

Parameters

[in]	key	The key that the array is searched for.
[in]	arr	The array to be searched.
[in]	count	The number of elements of the array.

Returns

If an element is found its index will be returned, otherwise the result is the bitwise inverse of the index where key would be inserted (which is always negative). If multiple elements have the same key value the index of the first of those elements will be returned.

Find() [1/2]

ITERATOR Find	(	const SEARCHTYPE &	key,
		ITERATOR	arr,
		Int	count
	)		const

Find an element in an array. The array must be in a sorted state. The time for searching will be O(log(n))

Parameters

[in]	key	The key that the array is searched for.
[in]	arr	The array to be searched.
[in]	count	The number of elements of the array.

Returns

If an element is found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

Find() [2/2]

ARRAY::ValueType* Find	(	const SEARCHTYPE &	key,
		const ARRAY &	arr
	)		const

Find an element in an array derived from BaseArray. The array must be in a sorted state. The time for searching will be O(log(n))

Parameters

[in]	key	The key that the array is searched for.
[in]	arr	The array to be searched.

Returns

If an element is found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

FindInsertionIndex() [1/2]

ITERATOR FindInsertionIndex	(	const SEARCHTYPE &	key,
		ITERATOR	arr,
		Int	count,
		Int &	insertionIndex
	)		const

Find an element in an array and return the insertion index if the element was not found. The array must be in a sorted state. The time for searching will be O(log(n))

Parameters

[in]	key	The key that the array is searched for.
[in]	arr	The array to be searched.
[in]	count	The number of elements of the array.
[out]	insertionIndex	The index an element needs to be inserted at if it does not exist in the array. Inserting at the designated place ensures that the array stays sorted.

Returns

If an element was found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

FindInsertionIndex() [2/2]

ARRAY::ValueType* FindInsertionIndex	(	const SEARCHTYPE &	key,
		const ARRAY &	arr,
		Int &	insertionIndex
	)		const

Find an element in an array derived from BaseArray and return the insertion index if the element was not found. The array must be in a sorted state. The time for searching will be O(log(n))

Parameters

[in]	key	The key that the array is searched for.
[in]	arr	The array to be searched.
[out]	insertionIndex	The index an element needs to be inserted at if it does not exist in the array. Inserting at the designated place ensures that the array stays sorted.

Returns

If an element was found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

Log2()

Int Log2 ( Int  n ) const

private

ISort()

void ISort ( ITERATOR  start, Int  count, const CONTENT &  valType  ) const

private