1 /*
2 # This file is part of the Astrometry.net suite.
3 # Licensed under a 3-clause BSD style license - see LICENSE
4 */
5
6 /**
7 Defined:
8
9 --nl
10 --number
11 --NL_PRINT(x) prints number 'x'
12
13 Note:
14 --You can't declare multiple "number" variables like this:
15
16 number n1, n2;
17
18 Instead, do:
19
20 number n1;
21 number n2;
22
23 This is because "number" may be a pointer type.
24 */
25
26 #include "bl-nl.ph"
27
28 #define NODE_NUMDATA(node) ((number*)NODE_DATA(node))
29
NLF(to_array)30 number* NLF(to_array)(nl* list) {
31 number* arr;
32 size_t N;
33 if (!list)
34 return NULL;
35 N = NLF(size)(list);
36 arr = malloc(N * sizeof(number));
37 bl_copy(list, 0, N, arr);
38 return arr;
39 }
40
41 #define InlineDefine InlineDefineC
42 #include "bl-nl.inc"
43 #undef InlineDefine
44
NLF(compare_ascending)45 static int NLF(compare_ascending)(const void* v1, const void* v2) {
46 number i1 = *(number*)v1;
47 number i2 = *(number*)v2;
48 if (i1 > i2) return 1;
49 else if (i1 < i2) return -1;
50 else return 0;
51 }
52
NLF(compare_descending)53 static int NLF(compare_descending)(const void* v1, const void* v2) {
54 number i1 = *(number*)v1;
55 number i2 = *(number*)v2;
56 if (i1 > i2) return -1;
57 else if (i1 < i2) return 1;
58 else return 0;
59 }
60
NLF(reverse)61 void NLF(reverse)(nl* list) {
62 bl_reverse(list);
63 }
64
NLF(append_array)65 void NLF(append_array)(nl* list, const number* data, size_t ndata) {
66 size_t i;
67 for (i=0; i<ndata; i++)
68 NLF(append)(list, data[i]);
69 }
70
NLF(merge_ascending)71 nl* NLF(merge_ascending)(nl* list1, nl* list2) {
72 nl* res;
73 size_t i1, i2, N1, N2;
74 number v1 = 0;
75 number v2 = 0;
76 unsigned char getv1, getv2;
77 if (!list1)
78 return NLF(dupe)(list2);
79 if (!list2)
80 return NLF(dupe)(list1);
81 if (!NLF(size)(list1))
82 return NLF(dupe)(list2);
83 if (!NLF(size)(list2))
84 return NLF(dupe)(list1);
85
86 res = NLF(new)(list1->blocksize);
87 N1 = NLF(size)(list1);
88 N2 = NLF(size)(list2);
89 i1 = i2 = 0;
90 getv1 = getv2 = 1;
91 while (i1 < N1 && i2 < N2) {
92 if (getv1) {
93 v1 = NLF(get)(list1, i1);
94 getv1 = 0;
95 }
96 if (getv2) {
97 getv2 = 0;
98 v2 = NLF(get)(list2, i2);
99 }
100 if (v1 <= v2) {
101 NLF(append)(res, v1);
102 i1++;
103 getv1 = 1;
104 } else {
105 NLF(append)(res, v2);
106 i2++;
107 getv2 = 1;
108 }
109 }
110 for (; i1<N1; i1++)
111 NLF(append)(res, NLF(get)(list1, i1));
112 for (; i2<N2; i2++)
113 NLF(append)(res, NLF(get)(list2, i2));
114 return res;
115 }
116
NLF(remove_all_reuse)117 void NLF(remove_all_reuse)(nl* list) {
118 bl_remove_all_but_first(list);
119 }
120
NLF(find_index_ascending)121 ptrdiff_t NLF(find_index_ascending)(nl* list, const number value) {
122 return bl_find_index(list, &value, NLF(compare_ascending));
123 }
124
NLF(check_consistency)125 int NLF(check_consistency)(nl* list) {
126 return bl_check_consistency(list);
127 }
128
NLF(check_sorted_ascending)129 int NLF(check_sorted_ascending)(nl* list,
130 int isunique) {
131 return bl_check_sorted(list, NLF(compare_ascending), isunique);
132 }
133
NLF(check_sorted_descending)134 int NLF(check_sorted_descending)(nl* list,
135 int isunique) {
136 return bl_check_sorted(list, NLF(compare_descending), isunique);
137 }
138
NLF(remove)139 void NLF(remove)(nl* nlist, size_t index) {
140 bl_remove_index(nlist, index);
141 }
142
NLF(pop)143 number NLF(pop)(nl* nlist) {
144 number ret = NLF(get)(nlist, nlist->N-1);
145 bl_remove_index(nlist, nlist->N-1);
146 return ret;
147 }
148
NLF(dupe)149 nl* NLF(dupe)(nl* nlist) {
150 nl* ret = NLF(new)(nlist->blocksize);
151 size_t i;
152 for (i=0; i<nlist->N; i++)
153 NLF(push)(ret, NLF(get)(nlist, i));
154 return ret;
155 }
156
NLF(remove_value)157 ptrdiff_t NLF(remove_value)(nl* nlist, const number value) {
158 bl* list = nlist;
159 bl_node *node, *prev;
160 size_t istart = 0;
161 for (node=list->head, prev=NULL;
162 node;
163 prev=node, node=node->next) {
164 int i;
165 number* idat;
166 idat = NODE_DATA(node);
167 for (i=0; i<node->N; i++)
168 if (idat[i] == value) {
169 bl_remove_from_node(list, node, prev, i);
170 list->last_access = prev;
171 list->last_access_n = istart;
172 return istart + i;
173 }
174 istart += node->N;
175 }
176 return BL_NOT_FOUND;
177 }
178
NLF(remove_all)179 void NLF(remove_all)(nl* list) {
180 bl_remove_all(list);
181 }
182
NLF(remove_index_range)183 void NLF(remove_index_range)(nl* list, size_t start, size_t length) {
184 bl_remove_index_range(list, start, length);
185 }
186
NLF(set)187 void NLF(set)(nl* list, size_t index, const number value) {
188 bl_set(list, index, &value);
189 }
190
191 /*
192 void dl_set(dl* list, int index, double value) {
193 int i;
194 int nadd = (index+1) - list->N;
195 if (nadd > 0) {
196 // enlarge the list to hold 'nadd' more entries.
197 for (i=0; i<nadd; i++) {
198 dl_append(list, 0.0);
199 }
200 }
201 bl_set(list, index, &value);
202 }
203 */
204
NLF(new)205 nl* NLF(new)(int blocksize) {
206 return bl_new(blocksize, sizeof(number));
207 }
208
NLF(new_existing)209 void NLF(new_existing)(nl* list, int blocksize) {
210 bl_init(list, blocksize, sizeof(number));
211 }
212
NLF(init)213 void NLF(init)(nl* list, int blocksize) {
214 bl_init(list, blocksize, sizeof(number));
215 }
216
NLF(free)217 void NLF(free)(nl* list) {
218 bl_free(list);
219 }
220
NLF(push)221 void NLF(push)(nl* list, const number data) {
222 bl_append(list, &data);
223 }
224
NLF(append)225 number* NLF(append)(nl* list, const number data) {
226 return bl_append(list, &data);
227 }
228
NLF(append_list)229 void NLF(append_list)(nl* list, nl* list2) {
230 size_t i, N;
231 N = NLF(size)(list2);
232 for (i=0; i<N; i++)
233 NLF(append)(list, NLF(get)(list2, i));
234 }
235
NLF(merge_lists)236 void NLF(merge_lists)(nl* list1, nl* list2) {
237 bl_append_list(list1, list2);
238 }
239
NLF(binarysearch)240 static ptrdiff_t NLF(binarysearch)(bl_node* node, const number n) {
241 number* iarray = NODE_NUMDATA(node);
242 ptrdiff_t lower = -1;
243 ptrdiff_t upper = node->N;
244 ptrdiff_t mid;
245 while (lower < (upper-1)) {
246 mid = (upper + lower) / 2;
247 if (n >= iarray[mid])
248 lower = mid;
249 else
250 upper = mid;
251 }
252 return lower;
253 }
254
255 // find the first node for which n <= the last element.
NLF(findnodecontainingsorted)256 static bl_node* NLF(findnodecontainingsorted)(const nl* list, const number n,
257 size_t* p_nskipped) {
258 bl_node *node;
259 size_t nskipped;
260 //bl_node *prev;
261 //int prevnskipped;
262
263 // check if we can use the jump accessor or if we have to start at
264 // the beginning...
265 if (list->last_access && list->last_access->N &&
266 // is the value we're looking for >= the first element?
267 (n >= *NODE_NUMDATA(list->last_access))) {
268 node = list->last_access;
269 nskipped = list->last_access_n;
270 } else {
271 node = list->head;
272 nskipped = 0;
273 }
274
275 /*
276 // find the first node for which n < the first element. The
277 // previous node will contain the value (if it exists).
278 for (prev=node, prevnskipped=nskipped;
279 node && (n < *NODE_NUMDATA(node));) {
280 prev=node;
281 prevnskipped=nskipped;
282 nskipped+=node->N;
283 node=node->next;
284 }
285 if (prev && n <= NODE_NUMDATA(prev)[prev->N-1]) {
286 if (p_nskipped)
287 *p_nskipped = prevnskipped;
288 return prev;
289 }
290 if (node && n <= NODE_NUMDATA(node)[node->N-1]) {
291 if (p_nskipped)
292 *p_nskipped = nskipped;
293 return node;
294 }
295 return NULL;
296 */
297 /*
298 if (!node && prev && n > NODE_NUMDATA(prev)[prev->N-1])
299 return NULL;
300 if (p_nskipped)
301 *p_nskipped = prevnskipped;
302 return prev;
303 */
304
305 for (; node && (n > NODE_NUMDATA(node)[node->N-1]); node=node->next)
306 nskipped += node->N;
307 if (p_nskipped)
308 *p_nskipped = nskipped;
309 return node;
310 }
311
NLF(insertascending)312 static ptrdiff_t NLF(insertascending)(nl* list, const number n, int unique) {
313 bl_node *node;
314 size_t ind;
315 size_t nskipped;
316
317 node = NLF(findnodecontainingsorted)(list, n, &nskipped);
318 if (!node) {
319 NLF(append)(list, n);
320 return list->N-1;
321 }
322
323 /*
324 for (; node && (n > NODE_NUMDATA(node)[node->N-1]); node=node->next)
325 nskipped += node->N;
326 if (!node) {
327 // either we're adding the first element, or we're appending since
328 // n is bigger than the largest element in the list.
329 NLF(append)(list, n);
330 return list->N-1;
331 }
332 */
333
334 // find where in the node it should be inserted...
335 ind = 1 + NLF(binarysearch)(node, n);
336
337 // check if it's a duplicate...
338 if (unique && ind > 0 && (n == NODE_NUMDATA(node)[ind-1]))
339 return BL_NOT_FOUND;
340
341 // set the jump accessors...
342 list->last_access = node;
343 list->last_access_n = nskipped;
344 // ... so that this runs in O(1).
345 bl_insert(list, nskipped + ind, &n);
346 return nskipped + ind;
347 }
348
NLF(insert_ascending)349 size_t NLF(insert_ascending)(nl* list, const number n) {
350 return NLF(insertascending)(list, n, 0);
351 }
352
NLF(insert_unique_ascending)353 ptrdiff_t NLF(insert_unique_ascending)(nl* list, const number n) {
354 return NLF(insertascending)(list, n, 1);
355 }
356
NLF(insert_descending)357 size_t NLF(insert_descending)(nl* list, const number n) {
358 return bl_insert_sorted(list, &n, NLF(compare_descending));
359 }
360
NLF(insert)361 void NLF(insert)(nl* list, size_t indx, const number data) {
362 bl_insert(list, indx, &data);
363 }
364
NLF(copy)365 void NLF(copy)(nl* list, size_t start, size_t length, number* vdest) {
366 bl_copy(list, start, length, vdest);
367 }
368
NLF(print)369 void NLF(print)(nl* list) {
370 bl_node* n;
371 for (n=list->head; n; n=n->next) {
372 int i;
373 printf("[ ");
374 for (i=0; i<n->N; i++) {
375 if (i > 0)
376 printf(", ");
377 NL_PRINT(NODE_NUMDATA(n)[i]);
378 }
379 printf("] ");
380 }
381 }
382
NLF(index_of)383 ptrdiff_t NLF(index_of)(nl* list, const number data) {
384 bl_node* n;
385 number* idata;
386 size_t npast = 0;
387 for (n=list->head; n; n=n->next) {
388 int i;
389 idata = NODE_NUMDATA(n);
390 for (i=0; i<n->N; i++)
391 if (idata[i] == data)
392 return npast + i;
393 npast += n->N;
394 }
395 return BL_NOT_FOUND;
396 }
397
NLF(contains)398 int NLF(contains)(nl* list, const number data) {
399 return (NLF(index_of)(list, data) != BL_NOT_FOUND);
400 }
401
NLF(sorted_contains)402 int NLF(sorted_contains)(nl* list, const number n) {
403 return NLF(sorted_index_of)(list, n) != BL_NOT_FOUND;
404 }
405
NLF(sorted_index_of)406 ptrdiff_t NLF(sorted_index_of)(nl* list, const number n) {
407 bl_node *node;
408 ptrdiff_t lower;
409 size_t nskipped;
410
411 node = NLF(findnodecontainingsorted)(list, n, &nskipped);
412 if (!node)
413 return BL_NOT_FOUND;
414 //if (!node && (n > NODE_NUMDATA(prev)[prev->N-1]))
415 //return -1;
416 //node = prev;
417
418 /*
419 // find the first node for which n <= the last element. That node
420 // will contain the value (if it exists)
421 for (; node && (n > NODE_NUMDATA(node)[node->N-1]); node=node->next)
422 nskipped += node->N;
423 if (!node)
424 return -1;
425 */
426
427 // update jump accessors...
428 list->last_access = node;
429 list->last_access_n = nskipped;
430
431 // find within the node...
432 lower = NLF(binarysearch)(node, n);
433 if (lower == BL_NOT_FOUND)
434 return BL_NOT_FOUND;
435 if (n == NODE_NUMDATA(node)[lower])
436 return nskipped + lower;
437 return BL_NOT_FOUND;
438 }
439
440 #undef NLF
441 #undef NODE_NUMDATA
442