1// [Blend2D]
2// 2D Vector Graphics Powered by a JIT Compiler.
3//
4// [License]
5// Zlib - See LICENSE.md file in the package.
6
7#ifndef BLEND2D_BLARRAYOPS_P_H
8#define BLEND2D_BLARRAYOPS_P_H
9
10#include "./blsupport_p.h"
11
12//! \cond INTERNAL
13//! \addtogroup blend2d_internal
14//! \{
15
16// ============================================================================
17// [BLArrayOps - BinarySearch]
18// ============================================================================
19
20template<typename T, typename V>
21static BL_INLINE size_t blBinarySearch(const T* array, size_t size, const V& value) noexcept {
22 if (!size)
23 return SIZE_MAX;
24
25 const T* lower = array;
26 while (size_t half = size / 2u) {
27 const T* middle = lower + half;
28 size -= half;
29 if (middle[0] <= value)
30 lower = middle;
31 }
32
33 size_t index = size_t(lower - array);
34 BL_ASSUME(index != SIZE_MAX);
35
36 return lower[0] == value ? index : SIZE_MAX;
37}
38
39template<typename T, typename V>
40static BL_INLINE size_t blBinarySearchClosestFirst(const T* array, size_t size, const V& value) noexcept {
41 if (!size)
42 return 0;
43
44 const T* lower = array;
45 while (size_t half = size / 2u) {
46 const T* middle = lower + half;
47 size -= half;
48 if (middle[0] < value)
49 lower = middle;
50 }
51
52 if (lower[0] < value)
53 lower++;
54
55 return size_t(lower - array);
56}
57
58template<typename T, typename V>
59static BL_INLINE size_t blBinarySearchClosestLast(const T* array, size_t size, const V& value) noexcept {
60 if (!size)
61 return 0;
62
63 const T* lower = array;
64 while (size_t half = size / 2u) {
65 const T* middle = lower + half;
66 size -= half;
67 if (middle[0] <= value)
68 lower = middle;
69 }
70
71 return size_t(lower - array);
72}
73
74// ============================================================================
75// [BLArrayOps - InsertionSort | QuickSort]
76// ============================================================================
77
78enum BLSortOrder : uint32_t {
79 BL_SORT_ORDER_ASCENDING = 0,
80 BL_SORT_ORDER_DESCENDING = 1
81};
82
83//! A helper class that provides comparison of any user-defined type that
84//! implements `<` and `>` operators (primitive types are supported as well).
85template<uint32_t Order = BL_SORT_ORDER_ASCENDING>
86struct BLCompare {
87 template<typename A, typename B>
88 BL_INLINE int operator()(const A& a, const B& b) const noexcept {
89 return (Order == BL_SORT_ORDER_ASCENDING) ? (a < b ? -1 : a > b ? 1 : 0)
90 : (a < b ? 1 : a > b ? -1 : 0);
91 }
92};
93
94//! Insertion sort.
95template<typename T, typename Compare = BLCompare<BL_SORT_ORDER_ASCENDING>>
96static BL_INLINE void blInsertionSort(T* base, size_t size, const Compare& cmp = Compare()) noexcept {
97 for (T* pm = base + 1; pm < base + size; pm++)
98 for (T* pl = pm; pl > base && cmp(pl[-1], pl[0]) > 0; pl--)
99 std::swap(pl[-1], pl[0]);
100}
101
102//! Quick-sort implementation.
103template<typename T, class Compare>
104struct BLQuickSortImpl {
105 enum : size_t {
106 kStackSize = 64 * 2,
107 kISortThreshold = 7
108 };
109
110 // Based on "PDCLib - Public Domain C Library" and rewritten to C++.
111 static void sort(T* base, size_t size, const Compare& cmp) noexcept {
112 T* end = base + size;
113 T* stack[kStackSize];
114 T** stackptr = stack;
115
116 for (;;) {
117 if ((size_t)(end - base) > kISortThreshold) {
118 // We work from second to last - first will be pivot element.
119 T* pi = base + 1;
120 T* pj = end - 1;
121 std::swap(base[(size_t)(end - base) / 2], base[0]);
122
123 if (cmp(*pi , *pj ) > 0) std::swap(*pi , *pj );
124 if (cmp(*base, *pj ) > 0) std::swap(*base, *pj );
125 if (cmp(*pi , *base) > 0) std::swap(*pi , *base);
126
127 // Now we have the median for pivot element, entering main loop.
128 for (;;) {
129 while (pi < pj && cmp(*++pi, *base) < 0) continue; // Move `i` right until `*i >= pivot`.
130 while (pj > base && cmp(*--pj, *base) > 0) continue; // Move `j` left until `*j <= pivot`.
131
132 if (pi > pj) break;
133 std::swap(*pi, *pj);
134 }
135
136 // Move pivot into correct place.
137 std::swap(*base, *pj);
138
139 // Larger subfile base / end to stack, sort smaller.
140 if (pj - base > end - pi) {
141 // Left is larger.
142 *stackptr++ = base;
143 *stackptr++ = pj;
144 base = pi;
145 }
146 else {
147 // Right is larger.
148 *stackptr++ = pi;
149 *stackptr++ = end;
150 end = pj;
151 }
152 BL_ASSERT(stackptr <= stack + kStackSize);
153 }
154 else {
155 blInsertionSort(base, (size_t)(end - base), cmp);
156 if (stackptr == stack)
157 break;
158 end = *--stackptr;
159 base = *--stackptr;
160 }
161 }
162 }
163};
164
165//! Quick sort.
166template<typename T, class Compare = BLCompare<BL_SORT_ORDER_ASCENDING>>
167static BL_INLINE void blQuickSort(T* base, size_t size, const Compare& cmp = Compare()) noexcept {
168 BLQuickSortImpl<T, Compare>::sort(base, size, cmp);
169}
170
171//! \}
172//! \endcond
173
174#endif // BLEND2D_BLARRAYOPS_P_H
175