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 | |
20 | template<typename T, typename V> |
21 | static 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 | |
39 | template<typename T, typename V> |
40 | static 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 | |
58 | template<typename T, typename V> |
59 | static 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 | |
78 | enum 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). |
85 | template<uint32_t Order = BL_SORT_ORDER_ASCENDING> |
86 | struct 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. |
95 | template<typename T, typename Compare = BLCompare<BL_SORT_ORDER_ASCENDING>> |
96 | static 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. |
103 | template<typename T, class Compare> |
104 | struct 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. |
166 | template<typename T, class Compare = BLCompare<BL_SORT_ORDER_ASCENDING>> |
167 | static 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 | |