1 #include "stdio.h"
2 #include "idx-opt.h"
3
4 /*-------------------------------------------------------------------------
5 *
6 * Binary search functions
7 *
8 *-------------------------------------------------------------------------
9 */
10
11
12 /*-------------------------------------------------------------------------
13 * Function: bisect_{left,right}_optim_*
14 *
15 * Purpose: Look-up for a value in sorted arrays
16 *
17 * Return: The index of the value in array
18 *
19 * Programmer: Francesc Alted
20 *
21 * Date: August, 2005
22 *
23 * Comments:
24 *
25 * Modifications:
26 *
27 *-------------------------------------------------------------------------
28 */
29
30
31 /* Optimised version for left/int8 */
bisect_left_b(npy_int8 * a,long x,int hi,int offset)32 int bisect_left_b(npy_int8 *a, long x, int hi, int offset) {
33 int lo = 0;
34 int mid;
35
36 if (x <= a[offset]) return 0;
37 if (a[hi-1+offset] < x) return hi;
38 while (lo < hi) {
39 mid = lo + (hi-lo)/2;
40 if (a[mid+offset] < x) lo = mid+1;
41 else hi = mid;
42 }
43 return lo;
44 }
45
46 /* Optimised version for left/uint8 */
bisect_left_ub(npy_uint8 * a,long x,int hi,int offset)47 int bisect_left_ub(npy_uint8 *a, long x, int hi, int offset) {
48 int lo = 0;
49 int mid;
50
51 if (x <= a[offset]) return 0;
52 if (a[hi-1+offset] < x) return hi;
53 while (lo < hi) {
54 mid = lo + (hi-lo)/2;
55 if (a[mid+offset] < x) lo = mid+1;
56 else hi = mid;
57 }
58 return lo;
59 }
60
61 /* Optimised version for right/int8 */
bisect_right_b(npy_int8 * a,long x,int hi,int offset)62 int bisect_right_b(npy_int8 *a, long x, int hi, int offset) {
63 int lo = 0;
64 int mid;
65
66 if (x < a[offset]) return 0;
67 if (a[hi-1+offset] <= x) return hi;
68 while (lo < hi) {
69 mid = lo + (hi-lo)/2;
70 if (x < a[mid+offset]) hi = mid;
71 else lo = mid+1;
72 }
73 return lo;
74 }
75
76 /* Optimised version for right/uint8 */
bisect_right_ub(npy_uint8 * a,long x,int hi,int offset)77 int bisect_right_ub(npy_uint8 *a, long x, int hi, int offset) {
78 int lo = 0;
79 int mid;
80
81 if (x < a[offset]) return 0;
82 if (a[hi-1+offset] <= x) return hi;
83 while (lo < hi) {
84 mid = lo + (hi-lo)/2;
85 if (x < a[mid+offset]) hi = mid;
86 else lo = mid+1;
87 }
88 return lo;
89 }
90
91 /* Optimised version for left/int16 */
bisect_left_s(npy_int16 * a,long x,int hi,int offset)92 int bisect_left_s(npy_int16 *a, long x, int hi, int offset) {
93 int lo = 0;
94 int mid;
95
96 if (x <= a[offset]) return 0;
97 if (a[hi-1+offset] < x) return hi;
98 while (lo < hi) {
99 mid = lo + (hi-lo)/2;
100 if (a[mid+offset] < x) lo = mid+1;
101 else hi = mid;
102 }
103 return lo;
104 }
105
106 /* Optimised version for left/uint16 */
bisect_left_us(npy_uint16 * a,long x,int hi,int offset)107 int bisect_left_us(npy_uint16 *a, long x, int hi, int offset) {
108 int lo = 0;
109 int mid;
110
111 if (x <= a[offset]) return 0;
112 if (a[hi-1+offset] < x) return hi;
113 while (lo < hi) {
114 mid = lo + (hi-lo)/2;
115 if (a[mid+offset] < x) lo = mid+1;
116 else hi = mid;
117 }
118 return lo;
119 }
120
121 /* Optimised version for right/int16 */
bisect_right_s(npy_int16 * a,long x,int hi,int offset)122 int bisect_right_s(npy_int16 *a, long x, int hi, int offset) {
123 int lo = 0;
124 int mid;
125
126 if (x < a[offset]) return 0;
127 if (a[hi-1+offset] <= x) return hi;
128 while (lo < hi) {
129 mid = lo + (hi-lo)/2;
130 if (x < a[mid+offset]) hi = mid;
131 else lo = mid+1;
132 }
133 return lo;
134 }
135
136 /* Optimised version for right/uint16 */
bisect_right_us(npy_uint16 * a,long x,int hi,int offset)137 int bisect_right_us(npy_uint16 *a, long x, int hi, int offset) {
138 int lo = 0;
139 int mid;
140
141 if (x < a[offset]) return 0;
142 if (a[hi-1+offset] <= x) return hi;
143 while (lo < hi) {
144 mid = lo + (hi-lo)/2;
145 if (x < a[mid+offset]) hi = mid;
146 else lo = mid+1;
147 }
148 return lo;
149 }
150
151 /* Optimised version for left/int32 */
bisect_left_i(npy_int32 * a,long x,int hi,int offset)152 int bisect_left_i(npy_int32 *a, long x, int hi, int offset) {
153 int lo = 0;
154 int mid;
155
156 if (x <= a[offset]) return 0;
157 if (a[hi-1+offset] < x) return hi;
158 while (lo < hi) {
159 mid = lo + (hi-lo)/2;
160 if (a[mid+offset] < x) lo = mid+1;
161 else hi = mid;
162 }
163 return lo;
164 }
165
166 /* Optimised version for left/uint32 */
bisect_left_ui(npy_uint32 * a,npy_uint32 x,int hi,int offset)167 int bisect_left_ui(npy_uint32 *a, npy_uint32 x, int hi, int offset) {
168 int lo = 0;
169 int mid;
170
171 if (x <= a[offset]) return 0;
172 if (a[hi-1+offset] < x) return hi;
173 while (lo < hi) {
174 mid = lo + (hi-lo)/2;
175 if (a[mid+offset] < x) lo = mid+1;
176 else hi = mid;
177 }
178 return lo;
179 }
180
181 /* Optimised version for right/int32 */
bisect_right_i(npy_int32 * a,long x,int hi,int offset)182 int bisect_right_i(npy_int32 *a, long x, int hi, int offset) {
183 int lo = 0;
184 int mid;
185
186 if (x < a[offset]) return 0;
187 if (a[hi-1+offset] <= x) return hi;
188 while (lo < hi) {
189 mid = lo + (hi-lo)/2;
190 if (x < a[mid+offset]) hi = mid;
191 else lo = mid+1;
192 }
193 return lo;
194 }
195
196 /* Optimised version for right/uint32 */
bisect_right_ui(npy_uint32 * a,npy_uint32 x,int hi,int offset)197 int bisect_right_ui(npy_uint32 *a, npy_uint32 x, int hi, int offset) {
198 int lo = 0;
199 int mid;
200
201 if (x < a[offset]) return 0;
202 if (a[hi-1+offset] <= x) return hi;
203 while (lo < hi) {
204 mid = lo + (hi-lo)/2;
205 if (x < a[mid+offset]) hi = mid;
206 else lo = mid+1;
207 }
208 return lo;
209 }
210
211 /* Optimised version for left/int64 */
bisect_left_ll(npy_int64 * a,npy_int64 x,int hi,int offset)212 int bisect_left_ll(npy_int64 *a, npy_int64 x, int hi, int offset) {
213 int lo = 0;
214 int mid;
215
216 if (x <= a[offset]) return 0;
217 if (a[hi-1+offset] < x) return hi;
218 while (lo < hi) {
219 mid = lo + (hi-lo)/2;
220 if (a[mid+offset] < x) lo = mid+1;
221 else hi = mid;
222 }
223 return lo;
224 }
225
226 /* Optimised version for left/uint64 */
bisect_left_ull(npy_uint64 * a,npy_uint64 x,int hi,int offset)227 int bisect_left_ull(npy_uint64 *a, npy_uint64 x, int hi, int offset) {
228 int lo = 0;
229 int mid;
230
231 if (x <= a[offset]) return 0;
232 if (a[hi-1+offset] < x) return hi;
233 while (lo < hi) {
234 mid = lo + (hi-lo)/2;
235 if (a[mid+offset] < x) lo = mid+1;
236 else hi = mid;
237 }
238 return lo;
239 }
240
241 /* Optimised version for right/int64 */
bisect_right_ll(npy_int64 * a,npy_int64 x,int hi,int offset)242 int bisect_right_ll(npy_int64 *a, npy_int64 x, int hi, int offset) {
243 int lo = 0;
244 int mid;
245
246 if (x < a[offset]) return 0;
247 if (a[hi-1+offset] <= x) return hi;
248 while (lo < hi) {
249 mid = lo + (hi-lo)/2;
250 if (x < a[mid+offset]) hi = mid;
251 else lo = mid+1;
252 }
253 return lo;
254 }
255
256 /* Optimised version for right/uint64 */
bisect_right_ull(npy_uint64 * a,npy_uint64 x,int hi,int offset)257 int bisect_right_ull(npy_uint64 *a, npy_uint64 x, int hi, int offset) {
258 int lo = 0;
259 int mid;
260
261 if (x < a[offset]) return 0;
262 if (a[hi-1+offset] <= x) return hi;
263 while (lo < hi) {
264 mid = lo + (hi-lo)/2;
265 if (x < a[mid+offset]) hi = mid;
266 else lo = mid+1;
267 }
268 return lo;
269 }
270
271 /* Optimised version for left/float16 */
bisect_left_e(npy_float16 * a,npy_float64 x,int hi,int offset)272 int bisect_left_e(npy_float16 *a, npy_float64 x, int hi, int offset) {
273 int lo = 0;
274 int mid;
275
276 if (x <= a[offset]) return 0;
277 if (a[hi-1+offset] < x) return hi;
278 while (lo < hi) {
279 mid = lo + (hi-lo)/2;
280 if (a[mid+offset] < x) lo = mid+1;
281 else hi = mid;
282 }
283 return lo;
284 }
285
286 /* Optimised version for right/float16 */
bisect_right_e(npy_float16 * a,npy_float64 x,int hi,int offset)287 int bisect_right_e(npy_float16 *a, npy_float64 x, int hi, int offset) {
288 int lo = 0;
289 int mid;
290
291 if (x < a[offset]) return 0;
292 if (a[hi-1+offset] <= x) return hi;
293 while (lo < hi) {
294 mid = lo + (hi-lo)/2;
295 if (x < a[mid+offset]) hi = mid;
296 else lo = mid+1;
297 }
298 return lo;
299 }
300
301 /* Optimised version for left/float32 */
bisect_left_f(npy_float32 * a,npy_float64 x,int hi,int offset)302 int bisect_left_f(npy_float32 *a, npy_float64 x, int hi, int offset) {
303 int lo = 0;
304 int mid;
305
306 if (x <= a[offset]) return 0;
307 if (a[hi-1+offset] < x) return hi;
308 while (lo < hi) {
309 mid = lo + (hi-lo)/2;
310 if (a[mid+offset] < x) lo = mid+1;
311 else hi = mid;
312 }
313 return lo;
314 }
315
316 /* Optimised version for right/float32 */
bisect_right_f(npy_float32 * a,npy_float64 x,int hi,int offset)317 int bisect_right_f(npy_float32 *a, npy_float64 x, int hi, int offset) {
318 int lo = 0;
319 int mid;
320
321 if (x < a[offset]) return 0;
322 if (a[hi-1+offset] <= x) return hi;
323 while (lo < hi) {
324 mid = lo + (hi-lo)/2;
325 if (x < a[mid+offset]) hi = mid;
326 else lo = mid+1;
327 }
328 return lo;
329 }
330
331 /* Optimised version for left/float64 */
bisect_left_d(npy_float64 * a,npy_float64 x,int hi,int offset)332 int bisect_left_d(npy_float64 *a, npy_float64 x, int hi, int offset) {
333 int lo = 0;
334 int mid;
335
336 if (x <= a[offset]) return 0;
337 if (a[hi-1+offset] < x) return hi;
338 while (lo < hi) {
339 mid = lo + (hi-lo)/2;
340 if (a[mid+offset] < x) lo = mid+1;
341 else hi = mid;
342 }
343 return lo;
344 }
345
346 /* Optimised version for right/float64 */
bisect_right_d(npy_float64 * a,npy_float64 x,int hi,int offset)347 int bisect_right_d(npy_float64 *a, npy_float64 x, int hi, int offset) {
348 int lo = 0;
349 int mid;
350
351 if (x < a[offset]) return 0;
352 if (a[hi-1+offset] <= x) return hi;
353 while (lo < hi) {
354 mid = lo + (hi-lo)/2;
355 if (x < a[mid+offset]) hi = mid;
356 else lo = mid+1;
357 }
358 return lo;
359 }
360
361 /* Optimised version for left/longdouble */
bisect_left_g(npy_longdouble * a,npy_longdouble x,int hi,int offset)362 int bisect_left_g(npy_longdouble *a, npy_longdouble x, int hi, int offset) {
363 int lo = 0;
364 int mid;
365
366 if (x <= a[offset]) return 0;
367 if (a[hi-1+offset] < x) return hi;
368 while (lo < hi) {
369 mid = lo + (hi-lo)/2;
370 if (a[mid+offset] < x) lo = mid+1;
371 else hi = mid;
372 }
373 return lo;
374 }
375
376 /* Optimised version for right/longdouble */
bisect_right_g(npy_longdouble * a,npy_longdouble x,int hi,int offset)377 int bisect_right_g(npy_longdouble *a, npy_longdouble x, int hi, int offset) {
378 int lo = 0;
379 int mid;
380
381 if (x < a[offset]) return 0;
382 if (a[hi-1+offset] <= x) return hi;
383 while (lo < hi) {
384 mid = lo + (hi-lo)/2;
385 if (x < a[mid+offset]) hi = mid;
386 else lo = mid+1;
387 }
388 return lo;
389 }
390
391