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);
maxon::Bool Bool
Definition: ge_sys_math.h:55
maxon::Int Int
Definition: ge_sys_math.h:64
Bool LessThan(UInt a1, UInt a2, UInt b1, UInt b2)
Definition: integer.h:151
- 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);
Definition: c4d_string.h:39
maxon::Float Float
Definition: ge_sys_math.h:66
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);
PyObject PyObject * result
Definition: abstract.h:43
COMPARERESULT LexicographicalCompare()
Definition: compare.h:670
MAXON_ATTRIBUTE_FORCE_INLINE Bool IsEqual(PREDICATE &&predicate, const T1 &a, const T2 &b)
Definition: collection.h:102
