summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/bx/include/bx/sort.h
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/bx/include/bx/sort.h')
-rw-r--r--3rdparty/bx/include/bx/sort.h277
1 files changed, 275 insertions, 2 deletions
diff --git a/3rdparty/bx/include/bx/sort.h b/3rdparty/bx/include/bx/sort.h
index 1506fb8307b..cee84bfdb63 100644
--- a/3rdparty/bx/include/bx/sort.h
+++ b/3rdparty/bx/include/bx/sort.h
@@ -1,18 +1,52 @@
/*
- * Copyright 2010-2018 Branimir Karadzic. All rights reserved.
- * License: https://github.com/bkaradzic/bx#license-bsd-2-clause
+ * Copyright 2010-2022 Branimir Karadzic. All rights reserved.
+ * License: https://github.com/bkaradzic/bx/blob/master/LICENSE
*/
#ifndef BX_SORT_H_HEADER_GUARD
#define BX_SORT_H_HEADER_GUARD
#include "bx.h"
+#include "math.h"
+#include "string.h"
namespace bx
{
+ /// The function compares the `_lhs` and `_rhs` values.
+ ///
+ /// @returns Returns value:
+ /// - less than zero if `_lhs` is less than `_rhs`
+ /// - zero if `_lhs` is equivalent to `_rhs`
+ /// - greater than zero if `_lhs` is greater than `_rhs`
///
typedef int32_t (*ComparisonFn)(const void* _lhs, const void* _rhs);
+ /// The function compares the `_lhs` and `_rhs` values.
+ ///
+ /// @returns Returns value:
+ /// - less than zero if `_lhs` is less than `_rhs`
+ /// - zero if `_lhs` is equivalent to `_rhs`
+ /// - greater than zero if `_lhs` is greater than `_rhs`
+ ///
+ template<typename Ty>
+ int32_t compareAscending(const void* _lhs, const void* _rhs);
+
+ /// The function compares the `_lhs` and `_rhs` values.
+ ///
+ /// @returns Returns value:
+ /// - less than zero if `_lhs` is greated than `_rhs`
+ /// - zero if `_lhs` is equivalent to `_rhs`
+ /// - greater than zero if `_lhs` is less than `_rhs`
+ ///
+ template<typename Ty>
+ int32_t compareDescending(const void* _lhs, const void* _rhs);
+
+ /// Performs sort (Quick Sort algorithm).
+ ///
+ /// @param _data Pointer to array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
///
void quickSort(
void* _data
@@ -21,6 +55,245 @@ namespace bx
, const ComparisonFn _fn
);
+ /// Performs sort (Quick Sort algorithm).
+ ///
+ /// @param _data Pointer to array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ template<typename Ty>
+ void quickSort(void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Performs sort (Quick Sort algorithm).
+ ///
+ /// @param _data Pointer to array data.
+ /// @param _num Number of elements.
+ /// @param _fn Comparison function.
+ ///
+ template<typename Ty>
+ void quickSort(Ty* _data, uint32_t _num, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Performs reordering of duplicate elements in the array in the way that unique elements
+ /// are sorted to the front of array, and duplicates are after the return value index.
+ ///
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns the count of unique elements.
+ ///
+ uint32_t unique(void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn);
+
+ /// Performs reordering of duplicate elements in the array in the way that unique elements
+ /// are sorted to the front of array, and duplicates are after the return value index.
+ ///
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns the count of unique elements.
+ ///
+ template<typename Ty>
+ uint32_t unique(void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Performs reordering of duplicate elements in the array in the way that unique elements
+ /// are sorted to the front of array, and duplicates are after the return value index.
+ ///
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns the count of unique elements.
+ ///
+ template<typename Ty>
+ uint32_t unique(Ty* _data, uint32_t _num, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Performs check if array is sorted.
+ ///
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @returns Returns `true` if array is sorted, otherwise returns `false`.
+ ///
+ bool isSorted(
+ const void* _data
+ , uint32_t _num
+ , uint32_t _stride
+ , const ComparisonFn _fn
+ );
+
+ /// Performs check if array is sorted.
+ ///
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @returns Returns `true` if array is sorted, otherwise returns `false`.
+ ///
+ template<typename Ty>
+ bool isSorted(const void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Performs check if array is sorted.
+ ///
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _fn Comparison function.
+ ///
+ /// @returns Returns `true` if array is sorted, otherwise returns `false`.
+ ///
+ template<typename Ty>
+ bool isSorted(const Ty* _data, uint32_t _num, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Returns an index to the first element greater or equal than the `_key` value.
+ ///
+ /// @param _key Pointer to the key to search for.
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns an index to the first element greater or equal than the `_key` value.
+ ///
+ uint32_t lowerBound(const void* _key, const void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn);
+
+ /// Returns an index to the first element greater or equal than the `_key` value.
+ ///
+ /// @param _key Pointer to the key to search for.
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns an index to the first element greater or equal than the `_key` value.
+ ///
+ template<typename Ty>
+ uint32_t lowerBound(const Ty& _key, const Ty* _data, uint32_t _num, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Returns an index to the first element greater or equal than the `_key` value.
+ ///
+ /// @param _key Pointer to the key to search for.
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns an index to the first element greater or equal than the `_key` value.
+ ///
+ template<typename Ty>
+ uint32_t lowerBound(const Ty& _key, const void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Returns an index to the first element greater than the `_key` value.
+ ///
+ /// @param _key Pointer to the key to search for.
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns an index to the first element greater than the `_key` value.
+ ///
+ uint32_t upperBound(const void* _key, const void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn);
+
+ /// Returns an index to the first element greater than the `_key` value.
+ ///
+ /// @param _key Pointer to the key to search for.
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns an index to the first element greater than the `_key` value.
+ ///
+ template<typename Ty>
+ uint32_t upperBound(const Ty& _key, const Ty* _data, uint32_t _num, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Returns an index to the first element greater than the `_key` value.
+ ///
+ /// @param _key Pointer to the key to search for.
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns an index to the first element greater than the `_key` value.
+ ///
+ template<typename Ty>
+ uint32_t upperBound(const Ty& _key, const void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Performs binary search of a sorted array.
+ ///
+ /// @param _key Pointer to the key to search for.
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns positive value index of element if found, or negative number that is bitwise
+ /// complement (~) of the index of the next element that's larger than item.
+ ///
+ int32_t binarySearch(
+ const void* _key
+ , const void* _data
+ , uint32_t _num
+ , uint32_t _stride
+ , const ComparisonFn _fn
+ );
+
+ /// Performs binary search of a sorted array.
+ ///
+ /// @param _key Pointer to the key to search for.
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns positive value index of element if found, or negative number that is bitwise
+ /// complement (~) of the index of the next element that's larger than item.
+ ///
+ template<typename Ty>
+ int32_t binarySearch(const Ty& _key, const Ty* _data, uint32_t _num, const ComparisonFn _fn = compareAscending<Ty>);
+
+ /// Performs binary search of a sorted array.
+ ///
+ /// @param _key Pointer to the key to search for.
+ /// @param _data Pointer to sorted array data.
+ /// @param _num Number of elements.
+ /// @param _stride Element stride in bytes.
+ /// @param _fn Comparison function.
+ ///
+ /// @remarks Array must be sorted!
+ ///
+ /// @returns Returns positive value index of element if found, or negative number that is bitwise
+ /// complement (~) of the index of the next element that's larger than item.
+ ///
+ template<typename Ty>
+ int32_t binarySearch(const Ty& _key, const void* _data, uint32_t _num, uint32_t _stride = sizeof(Ty), const ComparisonFn _fn = compareAscending<Ty>);
+
///
void radixSort(
uint32_t* _keys