1
/* -*- c -*- */
2
#define NPY_NO_DEPRECATED_API NPY_API_VERSION
3

4
#include "npy_sort.h"
5
#include "npysort_common.h"
6
#include "npy_binsearch.h"
7

8
#define NOT_USED NPY_UNUSED(unused)
9

10
/*
11
 *****************************************************************************
12
 **                            NUMERIC SEARCHES                             **
13
 *****************************************************************************
14
 */
15

16
/**begin repeat
17
 *
18
 * #TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
19
 *         LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE,
20
 *         CFLOAT, CDOUBLE, CLONGDOUBLE, DATETIME, TIMEDELTA#
21
 * #suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
22
 *         longlong, ulonglong, half, float, double, longdouble,
23
 *         cfloat, cdouble, clongdouble, datetime, timedelta#
24
 * #type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int,
25
 *         npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong,
26
 *         npy_ushort, npy_float, npy_double, npy_longdouble, npy_cfloat,
27
 *         npy_cdouble, npy_clongdouble, npy_datetime, npy_timedelta#
28
 */
29

30
#define @TYPE@_LTE(a, b) (!@TYPE@_LT((b), (a)))
31

32
/**begin repeat1
33
 *
34
 * #side = left, right#
35
 * #CMP  = LT, LTE#
36
 */
37

38
NPY_NO_EXPORT void
39 1
binsearch_@side@_@suff@(const char *arr, const char *key, char *ret,
40
                        npy_intp arr_len, npy_intp key_len,
41
                        npy_intp arr_str, npy_intp key_str, npy_intp ret_str,
42
                        PyArrayObject *NOT_USED)
43
{
44 1
    npy_intp min_idx = 0;
45 1
    npy_intp max_idx = arr_len;
46
    @type@ last_key_val;
47

48 1
    if (key_len == 0) {
49 1
        return;
50
    }
51 1
    last_key_val = *(const @type@ *)key;
52

53 1
    for (; key_len > 0; key_len--, key += key_str, ret += ret_str) {
54 1
        const @type@ key_val = *(const @type@ *)key;
55
        /*
56
         * Updating only one of the indices based on the previous key
57
         * gives the search a big boost when keys are sorted, but slightly
58
         * slows down things for purely random ones.
59
         */
60 1
        if (@TYPE@_LT(last_key_val, key_val)) {
61
            max_idx = arr_len;
62
        }
63
        else {
64 1
            min_idx = 0;
65 1
            max_idx = (max_idx < arr_len) ? (max_idx + 1) : arr_len;
66
        }
67

68 1
        last_key_val = key_val;
69

70 1
        while (min_idx < max_idx) {
71 1
            const npy_intp mid_idx = min_idx + ((max_idx - min_idx) >> 1);
72 1
            const @type@ mid_val = *(const @type@ *)(arr + mid_idx*arr_str);
73 1
            if (@TYPE@_@CMP@(mid_val, key_val)) {
74 1
                min_idx = mid_idx + 1;
75
            }
76
            else {
77
                max_idx = mid_idx;
78
            }
79
        }
80 1
        *(npy_intp *)ret = min_idx;
81
    }
82
}
83

84
NPY_NO_EXPORT int
85 1
argbinsearch_@side@_@suff@(const char *arr, const char *key,
86
                           const char *sort, char *ret,
87
                           npy_intp arr_len, npy_intp key_len,
88
                           npy_intp arr_str, npy_intp key_str,
89
                           npy_intp sort_str, npy_intp ret_str,
90
                           PyArrayObject *NOT_USED)
91
{
92 1
    npy_intp min_idx = 0;
93 1
    npy_intp max_idx = arr_len;
94
    @type@ last_key_val;
95

96 1
    if (key_len == 0) {
97
        return 0;
98
    }
99 1
    last_key_val = *(const @type@ *)key;
100

101 1
    for (; key_len > 0; key_len--, key += key_str, ret += ret_str) {
102 1
        const @type@ key_val = *(const @type@ *)key;
103
        /*
104
         * Updating only one of the indices based on the previous key
105
         * gives the search a big boost when keys are sorted, but slightly
106
         * slows down things for purely random ones.
107
         */
108 1
        if (@TYPE@_LT(last_key_val, key_val)) {
109
            max_idx = arr_len;
110
        }
111
        else {
112 1
            min_idx = 0;
113 1
            max_idx = (max_idx < arr_len) ? (max_idx + 1) : arr_len;
114
        }
115

116 1
        last_key_val = key_val;
117

118 1
        while (min_idx < max_idx) {
119 1
            const npy_intp mid_idx = min_idx + ((max_idx - min_idx) >> 1);
120 1
            const npy_intp sort_idx = *(npy_intp *)(sort + mid_idx*sort_str);
121
            @type@ mid_val;
122

123 1
            if (sort_idx < 0 || sort_idx >= arr_len) {
124 0
                return -1;
125
            }
126

127 1
            mid_val = *(const @type@ *)(arr + sort_idx*arr_str);
128

129 1
            if (@TYPE@_@CMP@(mid_val, key_val)) {
130 1
                min_idx = mid_idx + 1;
131
            }
132
            else {
133
                max_idx = mid_idx;
134
            }
135
        }
136 1
        *(npy_intp *)ret = min_idx;
137
    }
138
    return 0;
139
}
140

141
/**end repeat1**/
142
/**end repeat**/
143

144
/*
145
 *****************************************************************************
146
 **                             GENERIC SEARCH                              **
147
 *****************************************************************************
148
 */
149

150
 /**begin repeat
151
 *
152
 * #side = left, right#
153
 * #CMP  = <, <=#
154
 */
155

156
NPY_NO_EXPORT void
157 1
npy_binsearch_@side@(const char *arr, const char *key, char *ret,
158
                     npy_intp arr_len, npy_intp key_len,
159
                     npy_intp arr_str, npy_intp key_str, npy_intp ret_str,
160
                     PyArrayObject *cmp)
161
{
162 1
    PyArray_CompareFunc *compare = PyArray_DESCR(cmp)->f->compare;
163 1
    npy_intp min_idx = 0;
164 1
    npy_intp max_idx = arr_len;
165 1
    const char *last_key = key;
166

167 1
    for (; key_len > 0; key_len--, key += key_str, ret += ret_str) {
168
        /*
169
         * Updating only one of the indices based on the previous key
170
         * gives the search a big boost when keys are sorted, but slightly
171
         * slows down things for purely random ones.
172
         */
173 1
        if (compare(last_key, key, cmp) @CMP@ 0) {
174
            max_idx = arr_len;
175
        }
176
        else {
177 1
            min_idx = 0;
178 1
            max_idx = (max_idx < arr_len) ? (max_idx + 1) : arr_len;
179
        }
180

181
        last_key = key;
182

183 1
        while (min_idx < max_idx) {
184 1
            const npy_intp mid_idx = min_idx + ((max_idx - min_idx) >> 1);
185 1
            const char *arr_ptr = arr + mid_idx*arr_str;
186

187 1
            if (compare(arr_ptr, key, cmp) @CMP@ 0) {
188 1
                min_idx = mid_idx + 1;
189
            }
190
            else {
191
                max_idx = mid_idx;
192
            }
193
        }
194 1
        *(npy_intp *)ret = min_idx;
195
    }
196 1
}
197

198
NPY_NO_EXPORT int
199 1
npy_argbinsearch_@side@(const char *arr, const char *key,
200
                        const char *sort, char *ret,
201
                        npy_intp arr_len, npy_intp key_len,
202
                        npy_intp arr_str, npy_intp key_str,
203
                        npy_intp sort_str, npy_intp ret_str,
204
                        PyArrayObject *cmp)
205
{
206 1
    PyArray_CompareFunc *compare = PyArray_DESCR(cmp)->f->compare;
207 1
    npy_intp min_idx = 0;
208 1
    npy_intp max_idx = arr_len;
209 1
    const char *last_key = key;
210

211 1
    for (; key_len > 0; key_len--, key += key_str, ret += ret_str) {
212
        /*
213
         * Updating only one of the indices based on the previous key
214
         * gives the search a big boost when keys are sorted, but slightly
215
         * slows down things for purely random ones.
216
         */
217 1
        if (compare(last_key, key, cmp) @CMP@ 0) {
218
            max_idx = arr_len;
219
        }
220
        else {
221 1
            min_idx = 0;
222 1
            max_idx = (max_idx < arr_len) ? (max_idx + 1) : arr_len;
223
        }
224

225
        last_key = key;
226

227 1
        while (min_idx < max_idx) {
228 1
            const npy_intp mid_idx = min_idx + ((max_idx - min_idx) >> 1);
229 1
            const npy_intp sort_idx = *(npy_intp *)(sort + mid_idx*sort_str);
230
            const char *arr_ptr;
231

232 1
            if (sort_idx < 0 || sort_idx >= arr_len) {
233
                return -1;
234
            }
235

236 1
            arr_ptr = arr + sort_idx*arr_str;
237

238 1
            if (compare(arr_ptr, key, cmp) @CMP@ 0) {
239 1
                min_idx = mid_idx + 1;
240
            }
241
            else {
242
                max_idx = mid_idx;
243
            }
244
        }
245 1
        *(npy_intp *)ret = min_idx;
246
    }
247
    return 0;
248
}
249

250
/**end repeat**/

Read our documentation on viewing source code .

Loading