1 /*
2 # Fast methods for sorted integers
3 # (c) 2016 - 2017 Jens Oehlschägel
4 # Licence: GPL2
5 # Provided 'as is', use at your own risk
6 */
7
8 #include "merge.h"
9
10 #ifdef REV_B
11 #ifdef REV_A
12 #define FUNCNAME(NAME)NAME##_revab
13 #else
14 #define FUNCNAME(NAME)NAME##_revb
15 #endif
16 #else
17 #ifdef REV_A
18 #define FUNCNAME(NAME)NAME##_reva
19 #else
20 #define FUNCNAME(NAME)NAME
21 #endif
22 #endif
23
24 #ifdef REV_A
25 #define INIT_A(i,n) i=n-1
26 #define A_INC(i) i--
27 #define INC_A(i) --i
28 #define A_MINUS +
29 #define A_PLUS -
30 #define DONE_A(i,n) (i < 0)
31 #define STILL_A(i,n) (i >= 0)
32 #define A(i)(-a[i])
33 #define POS_A(i,n)(n-i+1)
34 #else
35 #define INIT_A(i,n) i=0
36 #define A_INC(i) i++
37 #define INC_A(i) ++i
38 #define A_MINUS -
39 #define A_PLUS +
40 #define DONE_A(i,n) (i >= n)
41 #define STILL_A(i,n) (i < n)
42 #define A(i)a[i]
43 #define POS_A(i,n)i
44 #endif
45
46 #ifdef REV_B
47 #define INIT_B(i,n) i=n-1
48 #define B_INC(i) i--
49 #define INC_B(i) --i
50 #define B_MINUS +
51 #define B_PLUS -
52 #define DONE_B(i,n) (i < 0)
53 #define STILL_B(i,n) (i >= 0)
54 #define B(i)(-b[i])
55 #define POS_B(i,n)(n-i)
56 #else
57 #define INIT_B(i,n) i=0
58 #define B_INC(i) i++
59 #define INC_B(i) ++i
60 #define B_MINUS -
61 #define B_PLUS +
62 #define DONE_B(i,n) (i >= n)
63 #define STILL_B(i,n) (i < n)
64 #define B(i)b[i]
65 #define POS_B(i,n)(i+1)
66 #endif
67
68 #define NEXT_A \
69 for(;;){ \
70 if DONE_A(INC_A(ia),na) \
71 goto finb; \
72 if (NE(A(ia), A(ia A_MINUS 1))) \
73 break; \
74 }
75
76 #define NEXT_B \
77 for(;;){ \
78 if DONE_B(INC_B(ib), nb) \
79 goto fina; \
80 if (NE(B(ib), B(ib B_MINUS 1))) \
81 break; \
82 }
83
84 #define NEXT_AB { \
85 for(;;){ \
86 if DONE_A(INC_A(ia), na){ \
87 NEXT_B \
88 goto finb; \
89 } \
90 if (NE(A(ia), A(ia A_MINUS 1))) \
91 break; \
92 } \
93 for(;;){ \
94 if DONE_B(INC_B(ib), nb) \
95 goto fina; \
96 if (NE(B(ib), B(ib B_MINUS 1))) \
97 break; \
98 } \
99 }
100
101
102 #define FIN_A fina: \
103 if STILL_A(ia, na) \
104 c[ic++] = A(A_INC(ia)); \
105 while STILL_A(ia, na){ \
106 if (NE(A(ia), A(ia A_MINUS 1))) \
107 c[ic++] = A(ia); \
108 A_INC(ia); \
109 } \
110 goto fin;
111
112 #define FIN_B finb: \
113 if STILL_B(ib, nb) \
114 c[ic++] = B(B_INC(ib)); \
115 while STILL_B(ib, nb){ \
116 if (NE(B(ib), B(ib B_MINUS 1))) \
117 c[ic++] = B(ib); \
118 B_INC(ib); \
119 } \
120 goto fin;
121
122
123
124
125 #ifndef REV_B
FUNCNAME(int_merge_unique)126 int FUNCNAME(int_merge_unique)(ValueT *a, IndexT na, ValueT *c){
127 IndexT INIT_A(ia, na), ic=0;
128 for (;;){
129 c[ic++] = A(ia);
130 NEXT_A
131 }
132 finb:
133 return ic;
134 }
135
FUNCNAME(int_merge_duplicated)136 void FUNCNAME(int_merge_duplicated)(ValueT *a, IndexT na, ValueT *c){
137 IndexT INIT_A(ia, na); IndexT ic=0;
138 ValueT lastvalue;
139 while STILL_A(ia, na){
140 lastvalue = a[ia];
141 c[ic++] = FALSE;
142 A_INC(ia);
143 while (STILL_A(ia, na) && a[ia] == lastvalue){
144 c[ic++] = TRUE;
145 A_INC(ia);
146 }
147 }
148 }
149
FUNCNAME(int_merge_anyDuplicated)150 Rboolean FUNCNAME(int_merge_anyDuplicated)(ValueT *a, IndexT na){
151 IndexT INIT_A(ia, na);
152 ValueT lastvalue;
153 while STILL_A(ia, na){
154 lastvalue = a[ia];
155 A_INC(ia);
156 if (STILL_A(ia, na) && a[ia] == lastvalue){
157 return(TRUE);
158 }
159 }
160 return(FALSE);
161 }
162
FUNCNAME(int_merge_sumDuplicated)163 int FUNCNAME(int_merge_sumDuplicated)(ValueT *a, IndexT na){
164 IndexT INIT_A(ia, na); IndexT ic=0;
165 ValueT lastvalue;
166 while STILL_A(ia, na){
167 lastvalue = a[ia];
168 A_INC(ia);
169 while (STILL_A(ia, na) && a[ia] == lastvalue){
170 ic++;
171 A_INC(ia);
172 }
173 }
174 return(ic);
175 }
176 #endif
177
178
179
FUNCNAME(int_merge_match)180 void FUNCNAME(int_merge_match)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c, IndexT nomatch){
181 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
182 if (na>0 && nb>0) for (;;){
183 if(LT(B(ib), A(ia))){
184 B_INC(ib);
185 if DONE_B(ib, nb)
186 break;
187 }else{
188 if(LT(A(ia), B(ib))){
189 c[ic++] = nomatch;
190 }else{
191 c[ic++] = POS_B(ib,nb);
192 }
193 if DONE_A(INC_A(ia), na)
194 break;
195 }
196 }
197 while STILL_A(A_INC(ia), na){
198 c[ic++] = nomatch;
199 }
200 }
201
FUNCNAME(int_merge_in)202 void FUNCNAME(int_merge_in)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
203 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
204 if (na>0 && nb>0) for (;;){
205 if(LT(B(ib), A(ia))){
206 B_INC(ib);
207 if DONE_B(ib, nb)
208 break;
209 }else{
210 if(LT(A(ia), B(ib))){
211 c[ic++] = FALSE;
212 }else{
213 c[ic++] = TRUE;
214 }
215 if DONE_A(INC_A(ia), na)
216 break;
217 }
218 }
219 while STILL_A(A_INC(ia), na){
220 c[ic++] = FALSE;
221 }
222 }
223
FUNCNAME(int_merge_notin)224 void FUNCNAME(int_merge_notin)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
225 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
226 if (na>0 && nb>0) for (;;){
227 if(LT(B(ib), A(ia))){
228 B_INC(ib);
229 if DONE_B(ib, nb)
230 break;
231 }else{
232 if(LT(A(ia), B(ib))){
233 c[ic++] = TRUE;
234 }else{
235 c[ic++] = FALSE;
236 }
237 if DONE_A(INC_A(ia), na)
238 break;
239 }
240 }
241 while STILL_A(A_INC(ia), na){
242 c[ic++] = TRUE;
243 }
244 }
245
246
247
248 // this is the classical stable merge
249 // which takes from a instead of b in case of ties
FUNCNAME(int_merge_union_all)250 void FUNCNAME(int_merge_union_all)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
251 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
252 if (na>0 && nb>0) for (;;){
253 if(LT(B(ib), A(ia))){
254 c[ic++] = B(B_INC(ib));
255 if DONE_B(ib, nb)
256 break;
257 }else{
258 c[ic++] = A(A_INC(ia));
259 if DONE_A(ia, na)
260 break;
261 }
262 }
263 while STILL_A(ia, na){
264 c[ic++] = A(A_INC(ia));
265 }
266 while STILL_B(ib, nb){
267 c[ic++] = B(B_INC(ib));
268 }
269 }
270
FUNCNAME(int_merge_union_exact)271 int FUNCNAME(int_merge_union_exact)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
272 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
273 if (na>0 && nb>0) for (;;){
274 if(LT(B(ib), A(ia))){
275 c[ic++] = B(B_INC(ib));
276 if DONE_B(ib, nb)
277 break;
278 }else{
279 c[ic++] = A(ia);
280 if(LT(A(ia), B(ib))){
281 A_INC(ia);
282 }else{
283 A_INC(ia);
284 B_INC(ib);
285 if DONE_B(ib, nb)
286 break;
287 }
288 if DONE_A(ia, na)
289 break;
290 }
291 }
292 while STILL_A(ia, na){
293 c[ic++] = A(A_INC(ia));
294 }
295 while STILL_B(ib, nb){
296 c[ic++] = B(B_INC(ib));
297 }
298 return ic;
299 }
300
FUNCNAME(int_merge_union_unique)301 int FUNCNAME(int_merge_union_unique)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
302 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
303 for (;;){
304 if(LT(B(ib), A(ia))){
305 c[ic++] = B(ib);
306 NEXT_B
307 }else{
308 c[ic++] = A(ia);
309 if(LT(A(ia), B(ib)))
310 NEXT_A
311 else
312 NEXT_AB
313 }
314 }
315 FIN_A
316 FIN_B
317 fin:
318 return ic;
319 }
320
321
322
FUNCNAME(int_merge_setdiff_exact)323 int FUNCNAME(int_merge_setdiff_exact)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
324 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
325 if (na>0 && nb>0) for (;;){
326 if(LT(A(ia), B(ib))){
327 c[ic++] = A(A_INC(ia));
328 if DONE_A(ia, na)
329 break;
330 }else{
331 if(LT(B(ib), A(ia))){
332 B_INC(ib);
333 }else{
334 B_INC(ib);
335 A_INC(ia);
336 if DONE_A(ia, na)
337 break;
338 }
339 if DONE_B(ib, nb)
340 break;
341 }
342 }
343 while STILL_A(ia, na){
344 c[ic++] = A(A_INC(ia));
345 }
346 return ic;
347 }
348
FUNCNAME(int_merge_setdiff_unique)349 int FUNCNAME(int_merge_setdiff_unique)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
350 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
351 if (na>0 && nb>0) for (;;){
352 if(LT(A(ia), B(ib))){
353 c[ic++] = A(ia);
354 NEXT_A
355 }else{
356 if (LT(B(ib),A(ia)))
357 NEXT_B
358 else
359 NEXT_AB
360 }
361 }
362 FIN_A
363 finb:
364 fin:
365 return ic;
366 }
367
368
FUNCNAME(int_merge_setequal_exact)369 int FUNCNAME(int_merge_setequal_exact)(ValueT *a, IndexT na, ValueT *b, IndexT nb){
370 if (na!=nb)
371 return FALSE;
372 IndexT INIT_A(ia, na), INIT_B(ib, nb);
373 if (na>0) for (;;){
374 if(EQ(A(ia), B(ib))){
375 A_INC(ia);
376 if DONE_A(ia, na)
377 break;
378 B_INC(ib);
379 }else{
380 return FALSE;
381 }
382 }
383 return TRUE;
384 }
385
386
FUNCNAME(int_merge_setequal_unique)387 int FUNCNAME(int_merge_setequal_unique)(ValueT *a, IndexT na, ValueT *b, IndexT nb){
388 IndexT INIT_A(ia, na), INIT_B(ib, nb);
389 if (na>0 && nb>0) for (;;){
390 if(EQ(A(ia), B(ib))){
391 NEXT_AB
392 }else{
393 return FALSE;
394 }
395 }
396 fina:
397 finb:
398 if (DONE_A(ia, na)==DONE_A(ib, nb))
399 return TRUE;
400 else
401 return FALSE;
402 }
403
404
FUNCNAME(int_merge_intersect_exact)405 int FUNCNAME(int_merge_intersect_exact)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
406 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
407 if (na>0 && nb>0) for (;;){
408 if(LT(B(ib), A(ia))){
409 B_INC(ib);
410 if DONE_B(ib, nb)
411 break;
412 }else{
413 if (LT(A(ia),B(ib))){
414 A_INC(ia);
415 }else{
416 c[ic++] = A(A_INC(ia));
417 B_INC(ib);
418 if DONE_B(ib, nb)
419 break;
420 }
421 if DONE_A(ia, na)
422 break;
423 }
424 }
425 return ic;
426 }
427
428
FUNCNAME(int_merge_intersect_unique)429 int FUNCNAME(int_merge_intersect_unique)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
430 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
431 if (na>0 && nb>0) for (;;){
432 if(LT(B(ib), A(ia))){
433 NEXT_B
434 }else{
435 if (LT(A(ia),B(ib))){
436 NEXT_A
437 }else{
438 c[ic++] = A(ia);
439 NEXT_AB
440 }
441 }
442 }
443 fina:
444 finb:
445 return ic;
446 }
447
FUNCNAME(int_merge_symdiff_exact)448 int FUNCNAME(int_merge_symdiff_exact)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
449 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
450 if (na>0 && nb>0) for (;;){
451 if(LT(B(ib), A(ia))){
452 c[ic++] = B(B_INC(ib));
453 if DONE_B(ib, nb)
454 goto fina;
455 }else if (LT(A(ia),B(ib))){
456 c[ic++] = A(A_INC(ia));
457 if DONE_A(ia, na)
458 goto finb;
459 }else{
460 A_INC(ia);
461 B_INC(ib);
462 if DONE_A(ia, na)
463 goto finb;
464 if DONE_B(ib, nb)
465 goto fina;
466 }
467 }
468 fina:
469 while STILL_A(ia, na){
470 c[ic++] = A(A_INC(ia));
471 }
472 goto fin;
473 finb:
474 while STILL_B(ib, nb){
475 c[ic++] = B(B_INC(ib));
476 }
477 fin:
478 return ic;
479 }
480
481
FUNCNAME(int_merge_symdiff_unique)482 int FUNCNAME(int_merge_symdiff_unique)(ValueT *a, IndexT na, ValueT *b, IndexT nb, ValueT *c){
483 IndexT INIT_A(ia, na), INIT_B(ib, nb), ic=0;
484 for (;;){
485 if(LT(B(ib), A(ia))){
486 c[ic++] = B(ib);
487 NEXT_B
488 }else if (LT(A(ia),B(ib))){
489 c[ic++] = A(ia);
490 NEXT_A
491 }else{
492 NEXT_AB
493 }
494 }
495 FIN_A
496 FIN_B
497 fin:
498 return ic;
499 }
500
501 #undef INIT_A
502 #undef A_INC
503 #undef INC_A
504 #undef A_MINUS
505 #undef A_PLUS
506 #undef DONE_A
507 #undef STILL_A
508 #undef POS_A
509 #undef A
510
511 #undef INIT_B
512 #undef B_INC
513 #undef INC_B
514 #undef B_MINUS
515 #undef B_PLUS
516 #undef DONE_B
517 #undef STILL_B
518 #undef POS_B
519 #undef B
520
521 #undef NEXT_A
522 #undef NEXT_B
523 #undef NEXT_AB
524 #undef FIN_A
525 #undef FIN_B
526
527 #undef FUNCNAME
528