Plasma Engine  2.0
Loading...
Searching...
No Matches
Sorting.h
1
2#pragma once
3
4#include <Foundation/Basics.h>
5
6#include <Foundation/Algorithm/Comparer.h>
7#include <Foundation/Math/Math.h>
8#include <Foundation/Types/ArrayPtr.h>
9
11class plSorting
12{
13public:
15 template <typename Container, typename Comparer>
16 static void QuickSort(Container& inout_container, const Comparer& comparer = Comparer()); // [tested]
17
19 template <typename T, typename Comparer>
20 static void QuickSort(plArrayPtr<T>& inout_arrayPtr, const Comparer& comparer = Comparer()); // [tested]
21
22
24 template <typename Container, typename Comparer>
25 static void InsertionSort(Container& inout_container, const Comparer& comparer = Comparer()); // [tested]
26
28 template <typename T, typename Comparer>
29 static void InsertionSort(plArrayPtr<T>& inout_arrayPtr, const Comparer& comparer = Comparer()); // [tested]
30
31private:
32 enum
33 {
34 INSERTION_THRESHOLD = 16
35 };
36
37 // Perform comparison either with "Less(a,b)" (prefered) or with operator ()(a,b)
38 template <typename Element, typename Comparer>
39 PL_ALWAYS_INLINE constexpr static auto DoCompare(const Comparer& comparer, const Element& a, const Element& b, int) -> decltype(comparer.Less(a, b))
40 {
41 return comparer.Less(a, b);
42 }
43 template <typename Element, typename Comparer>
44 PL_ALWAYS_INLINE constexpr static auto DoCompare(const Comparer& comparer, const Element& a, const Element& b, long) -> decltype(comparer(a, b))
45 {
46 return comparer(a, b);
47 }
48 template <typename Element, typename Comparer>
49 PL_ALWAYS_INLINE constexpr static bool DoCompare(const Comparer& comparer, const Element& a, const Element& b)
50 {
51 // Int/long is used to prefer the int version if both are available.
52 // (Kudos to http://stackoverflow.com/a/9154394/5347927 where I've learned this trick)
53 return DoCompare(comparer, a, b, 0);
54 }
55
56
57 template <typename Container, typename Comparer>
58 static void QuickSort(Container& inout_container, plUInt32 uiStartIndex, plUInt32 uiEndIndex, const Comparer& comparer);
59
60 template <typename Container, typename Comparer>
61 static plUInt32 Partition(Container& inout_container, plUInt32 uiLeft, plUInt32 uiRight, const Comparer& comparer);
62
63
64 template <typename T, typename Comparer>
65 static void QuickSort(plArrayPtr<T>& inout_arrayPtr, plUInt32 uiStartIndex, plUInt32 uiEndIndex, const Comparer& comparer);
66
67 template <typename T, typename Comparer>
68 static plUInt32 Partition(T* pPtr, plUInt32 uiLeft, plUInt32 uiRight, const Comparer& comparer);
69
70
71 template <typename Container, typename Comparer>
72 static void InsertionSort(Container& container, plUInt32 uiStartIndex, plUInt32 uiEndIndex, const Comparer& comparer);
73
74 template <typename T, typename Comparer>
75 static void InsertionSort(plArrayPtr<T>& inout_arrayPtr, plUInt32 uiStartIndex, plUInt32 uiEndIndex, const Comparer& comparer);
76};
77
78#include <Foundation/Algorithm/Implementation/Sorting_inl.h>
plArrayPtr
This class encapsulates an array and it's size. It is recommended to use this class instead of plain ...
Definition ArrayPtr.h:37
plSorting
This class provides implementations of different sorting algorithms.
Definition Sorting.h:12
plSorting::QuickSort
static void QuickSort(Container &inout_container, const Comparer &comparer=Comparer())
Sorts the elements in container using a in-place quick sort implementation (not stable).
Definition Sorting_inl.h:3
plSorting::InsertionSort
static void InsertionSort(Container &inout_container, const Comparer &comparer=Comparer())
Sorts the elements in container using insertion sort (stable and in-place).
Definition Sorting_inl.h:21