1 /*
2 # Fast methods for sorted integers (where the first argument is a range)
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,r) i=r[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,r) (i < r[0])
31 #define STILL_A(i,r) (i >= r[0])
32 #define A(i)(-i)
33 #else
34 #define INIT_A(i,r) i=r[0]
35 #define A_INC(i) i++
36 #define INC_A(i) ++i
37 #define A_MINUS -
38 #define A_PLUS +
39 #define DONE_A(i,r) (i > r[1])
40 #define STILL_A(i,r) (i <= r[1])
41 #define A(i)i
42 #endif
43
44 #ifdef REV_B
45 #define INIT_B(i,n) i=n-1
46 #define B_INC(i) i--
47 #define INC_B(i) --i
48 #define B_MINUS +
49 #define B_PLUS -
50 #define DONE_B(i,n) (i < 0)
51 #define STILL_B(i,n) (i >= 0)
52 #define B(i)(-b[i])
53 #else
54 #define INIT_B(i,n) i=0
55 #define B_INC(i) i++
56 #define INC_B(i) ++i
57 #define B_MINUS -
58 #define B_PLUS +
59 #define DONE_B(i,n) (i >= nb)
60 #define STILL_B(i,n) (i < nb)
61 #define B(i)b[i]
62 #endif
63
64
FUNCNAME(int_merge_firstin)65 ValueT FUNCNAME(int_merge_firstin)(IndexT *ra, ValueT *b, IndexT nb){
66 IndexT INIT_A(ia, ra), INIT_B(ib, nb), c=NA_INTEGER;
67 if (ra[0]<=ra[1] && nb>0) for (;;){
68 if(LT(A(ia), B(ib))){
69 A_INC(ia);
70 if DONE_A(ia, ra)
71 break;
72 }else{
73 if(LT(B(ib), A(ia))){
74 B_INC(ib);
75 }else{
76 c = A(ia);
77 break;
78 }
79 if DONE_B(ib, nb)
80 break;
81 }
82 }
83 return c;
84 }
85
FUNCNAME(int_merge_firstnotin)86 ValueT FUNCNAME(int_merge_firstnotin)(IndexT *ra, ValueT *b, IndexT nb){
87 IndexT INIT_A(ia, ra), INIT_B(ib, nb), c=NA_INTEGER;
88 if (ra[0]<=ra[1] && nb>0) for (;;){
89 if(LT(A(ia), B(ib))){
90 c = A(ia);
91 goto done;
92 }else{
93 if(LT(B(ib), A(ia))){
94 B_INC(ib);
95 }else{
96 B_INC(ib);
97 A_INC(ia);
98 if DONE_A(ia, ra)
99 goto done;
100 }
101 if DONE_B(ib, nb){
102 break;
103 }
104 }
105 }
106 if STILL_A(ia, ra){
107 c = A(ia);
108 }
109 done:
110 return c;
111 }
112
FUNCNAME(int_merge_rangesect)113 int FUNCNAME(int_merge_rangesect)(IndexT *ra, ValueT *b, IndexT nb, ValueT *c){
114 IndexT INIT_A(ia, ra), INIT_B(ib, nb), ic=0;
115 if (ra[0]<=ra[1] && nb>0) for (;;){
116 if(LT(A(ia), B(ib))){
117 A_INC(ia);
118 if DONE_A(ia, ra)
119 break;
120 }else{
121 if(LT(B(ib), A(ia))){
122 B_INC(ib);
123 }else{
124 c[ic++] = A(ia);
125 B_INC(ib);
126 A_INC(ia);
127 if DONE_A(ia, ra)
128 break;
129 }
130 if DONE_B(ib, nb)
131 break;
132 }
133 }
134 return ic;
135 }
136
137
FUNCNAME(int_merge_rangediff)138 int FUNCNAME(int_merge_rangediff)(IndexT *ra, ValueT *b, IndexT nb, ValueT *c){
139 IndexT INIT_A(ia, ra), INIT_B(ib, nb), ic=0;
140 if (ra[0]<=ra[1] && nb>0) for (;;){
141 if(LT(A(ia), B(ib))){
142 c[ic++] = A(A_INC(ia));
143 if DONE_A(ia, ra)
144 break;
145 }else{
146 if(LT(B(ib), A(ia))){
147 B_INC(ib);
148 }else{
149 B_INC(ib);
150 A_INC(ia);
151 if DONE_A(ia, ra)
152 break;
153 }
154 if DONE_B(ib, nb)
155 break;
156 }
157 }
158 while STILL_A(ia, ra){
159 c[ic++] = A(A_INC(ia));
160 }
161 return ic;
162 }
163
164
FUNCNAME(int_merge_rangein)165 void FUNCNAME(int_merge_rangein)(ValueT *ra, ValueT *b, IndexT nb, ValueT *c){
166 IndexT INIT_A(ia, ra), INIT_B(ib, nb), ic=0;
167 if (ra[0]<=ra[1] && nb>0) for (;;){
168 if(LT(B(ib), A(ia))){
169 B_INC(ib);
170 if DONE_B(ib, nb)
171 break;
172 }else{
173 if(LT(A(ia), B(ib))){
174 c[ic++] = FALSE;
175 }else{
176 c[ic++] = TRUE;
177 }
178 A_INC(ia);
179 if DONE_A(ia, ra)
180 break;
181 }
182 }
183 while STILL_A(ia, ra){
184 c[ic++] = FALSE;
185 A_INC(ia);
186 }
187 }
188
189
FUNCNAME(int_merge_rangenotin)190 void FUNCNAME(int_merge_rangenotin)(ValueT *ra, ValueT *b, IndexT nb, ValueT *c){
191 IndexT INIT_A(ia, ra), INIT_B(ib, nb), ic=0;
192 if (ra[0]<=ra[1] && nb>0) for (;;){
193 if(LT(B(ib), A(ia))){
194 B_INC(ib);
195 if DONE_B(ib, nb)
196 break;
197 }else{
198 if(LT(A(ia), B(ib))){
199 c[ic++] = TRUE;
200 }else{
201 c[ic++] = FALSE;
202 }
203 A_INC(ia);
204 if DONE_A(ia, ra)
205 break;
206 }
207 }
208 while STILL_A(ia, ra){
209 c[ic++] = TRUE;
210 A_INC(ia);
211 }
212 }
213
214 #undef INIT_A
215 #undef A_INC
216 #undef INC_A
217 #undef A_MINUS
218 #undef A_PLUS
219 #undef DONE_A
220 #undef STILL_A
221 #undef A
222
223 #undef INIT_B
224 #undef B_INC
225 #undef INC_B
226 #undef B_MINUS
227 #undef B_PLUS
228 #undef DONE_B
229 #undef STILL_B
230 #undef B
231
232 #undef FUNCNAME
233
234