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:
{
return a < b;
}
};
...
Int array1[100];
...
Sort1 sort1;
sort1.Sort(&array1[0], &array1[100]);
sort1.Sort(array1, 100);
- 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:
{
return a < b;
}
};
...
...
Sort2 sort2;
sort2.Sort(array2.Begin(), array2.End());
sort2.Sort(array2);
Example for arbitrary structures with multiple sort criteria:
class MyStruct
{
public:
};
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;
}
};
...
BlockArray<MyStruct> array3;
...
Sort3 sort3;
sort3.Sort(array3);
Searching Example:
class MyStruct
{
public:
};
class MySearch : public BaseSort <MySearch, BlockArray<MyStruct>::Iterator>
{
public:
static inline Bool LessThan(
const MyStruct& a,
const MyStruct& b)
{
}
{
return weight < b._weight;
}
{
return weight == b._weight;
}
};
...
BlockArray<MyStruct> array4;
...
MySearch search;
search.Sort(array4);
...
MyStruct* result = search.Find(5.0, array4);
|
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 |
|