Public Member Functions | Private Member Functions | List of all members
BaseSort< SORTCLASS, FLAGS > Class Template Reference
Data Structures

#include <sort.h>

Inheritance diagram for BaseSort< SORTCLASS, FLAGS >:
Inheritance graph
[legend]

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
SORTCLASSThe class itself. This has to be a derived class of BaseSort.
FLAGSSee 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
maxon::Int
Int64 Int
signed 32/64 bit int, size depends on the platform
Definition: apibase.h:187
maxon::Bool
bool Bool
boolean type, possible values are only false/true, 8 bit
Definition: apibase.h:180
maxon::LessThan
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:
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);
maxon::Float
Float64 Float
Definition: apibase.h:196

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);
result
PyObject PyObject * result
Definition: abstract.h:43
maxon::LexicographicalCompare
COMPARERESULT LexicographicalCompare()
Definition: compare.h:668
maxon::IsEqual
MAXON_ATTRIBUTE_FORCE_INLINE Bool IsEqual(PREDICATE &&predicate, const T1 &a, const T2 &b)
Definition: collection.h:102

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]startThe start iterator of an array.
[in]endThe 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]startThe start iterator of an array.
[in]countThe 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]arrThe 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]keyThe key that the array is searched for.
[in]arrThe array to be searched.
[in]countThe 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]keyThe key that the array is searched for.
[in]arrThe array to be searched.
[in]countThe 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]keyThe key that the array is searched for.
[in]arrThe 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]keyThe key that the array is searched for.
[in]arrThe array to be searched.
[in]countThe number of elements of the array.
[out]insertionIndexThe 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]keyThe key that the array is searched for.
[in]arrThe array to be searched.
[out]insertionIndexThe 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