82013cb6218e9896d4256a97b49f513eba57b640
[SXSI/xpathcomp.git] / results.c
1 \r
2 #include <stdio.h> \r
3 #include <stdlib.h> \r
4 #include "results.h"\r
5 \r
6 #define W (8*sizeof(int))\r
7 #define logW 5 // code checks = lg(W)-1\r
8 #define divW(p) ((p)>>logW)\r
9 #define modW(p) ((p)&(W-1))\r
10 \r
11 #define setBit(arr,pos) ((arr)[divW(pos)] |= 1<<modW(pos))\r
12 #define clearBit(arr,pos) ((arr)[divW(pos)] &= ~(1<<modW(pos)))\r
13 #define getBit(arr,pos) ((arr)[divW(pos)] & (1<<modW(pos))) // 0 or !=0\r
14 \r
15 static int lg (int n)\r
16 \r
17   { int answ=0;\r
18     while (n) { n>>=1; answ++; }\r
19     return answ;\r
20   }\r
21 \r
22 results createResults (int n)\r
23 \r
24   { results R;\r
25     if (logW != lg(W)-1)\r
26        { fprintf(stderr,"Error, redefine logW as %i and recompile\n",lg(W)-1);\r
27          exit(1);\r
28        }\r
29 \r
30     R.n = 2*n-1;\r
31     R.lgn = lg(n);\r
32     //fprintf(stderr,"Size of the result set : %i elements, %li kB\n", n,\r
33     //(((R.n+W-1)/W)*sizeof(int)/1024));\r
34     R.tree = (int*) malloc (((R.n+W-1)/W)*sizeof(int));\r
35     clearBit(R.tree,0); // clear all\r
36     return R;\r
37   }\r
38 \r
39 void freeResults (results R)\r
40 \r
41   { free (R.tree);\r
42   }\r
43 \r
44         // to map 1..n to the bottom of the tree when n is not a power of 2\r
45 static int conv (int p, int n, int lgn)\r
46 \r
47   { int t = n+1-(1<<lgn);\r
48     if (p < t) return p;\r
49     return (p<<1)-t;\r
50   }\r
51 \r
52 static int unconv (int p, int n, int lgn)\r
53 \r
54   { int t = n+1-(1<<lgn);\r
55     if (p < t) return p;\r
56     return (p+t)>>1;\r
57   }\r
58 \r
59 int readResult (results R, int p) // returns 0 or 1\r
60 \r
61   { int n = R.n;\r
62     int pos = 0;\r
63     int pot = R.lgn;\r
64     p = conv(p,n,pot);\r
65     do { if (!getBit(R.tree,pos)) return 0;\r
66           pot--;\r
67           pos = (pos<<1)+1+(p>>pot);\r
68           p &= ~(1<<pot);\r
69         }\r
70     while (pos < n);\r
71     return 1;\r
72   }\r
73 \r
74 void setResult (results R, int p)\r
75 \r
76   { int n = R.n;\r
77     int pos = 0;\r
78     int npos;\r
79     int pot = R.lgn;\r
80     p = conv(p,n,pot);\r
81     do { npos = (pos<<1)+1;\r
82          if (!getBit(R.tree,pos))\r
83             { setBit(R.tree,pos);\r
84               if (npos < n) \r
85                  { clearBit(R.tree,npos);\r
86                    clearBit(R.tree,npos+1);\r
87                  }\r
88             }\r
89           pot--;\r
90           pos = npos+(p>>pot);\r
91           p &= ~(1<<pot);\r
92         }\r
93     while (pos < n);\r
94   }\r
95 \r
96         // returns final value of bit at pos\r
97         \r
98 static int clearRangeLeft (int *tree, int p1, int n, int pos, int pot)\r
99 \r
100   { int npos;\r
101     int bit;\r
102     if (!getBit(tree,pos)) return 0; // range already zeroed\r
103     p1 &= ~(1<<pot);\r
104     if (p1 == 0) // full range to clear\r
105        { clearBit(tree,pos); return 0; }\r
106         // p1 != 0, there must be children\r
107     pot--;\r
108     npos = (pos<<1)+1;\r
109     if ((p1>>pot) == 0) // go left, clear right\r
110        { clearBit(tree,npos+1);\r
111          bit = clearRangeLeft(tree,p1,n,npos,pot);\r
112        } \r
113     else // go right\r
114        { bit = clearRangeLeft(tree,p1,n,npos+1,pot);\r
115          if (!bit) bit = getBit(tree,npos);\r
116        }\r
117     if (!bit) clearBit(tree,pos);\r
118     return bit;\r
119   }\r
120 \r
121 static int clearRangeRight (int *tree, int p2, int n, int pos, int pot)\r
122 \r
123   { int npos;\r
124     int bit;\r
125     if (!getBit(tree,pos)) return 0; // range already zeroed\r
126     p2 &= ~(1<<pot);\r
127     if (p2 == 0) return 1; // empty range to clear, and bit is 1 for sure\r
128         // p2 != 0, there must be children\r
129     pot--;\r
130     npos = (pos<<1)+1;\r
131     if ((p2>>pot) == 1) // go right, clear left\r
132        { clearBit(tree,npos);\r
133          bit = clearRangeRight(tree,p2,n,npos+1,pot);\r
134        } \r
135     else // go left\r
136        { bit = clearRangeRight(tree,p2,n,npos,pot);\r
137          if (!bit) bit = getBit(tree,npos+1);\r
138        }\r
139     if (!bit) clearBit(tree,pos);\r
140     return bit;\r
141   }\r
142 \r
143 static int clearBoth (int *tree, int n, int p1, int p2, int pos, int pot)\r
144 \r
145   { int npos,npos1,npos2;\r
146     int bit;\r
147     if (!getBit(tree,pos)) return 0; // range is already zeroed\r
148     npos = (pos<<1)+1;\r
149         // children must exist while the path is unique, as p1<p2\r
150     pot--;\r
151     npos1 = npos+(p1>>pot);\r
152     npos2 = npos+(p2>>pot);\r
153     if (npos1 == npos2) // we're inside npos1=npos2\r
154        { bit = clearBoth (tree,n,p1&~(1<<pot),p2&~(1<<pot),npos1,pot);\r
155          bit |= getBit(tree,npos+1-(p1>>pot)); // the other\r
156        }\r
157      else  // p1 and p2 take different paths here\r
158         { bit  = clearRangeLeft(tree,p1,n,npos1,pot); \r
159           bit |= clearRangeRight(tree,p2,n,npos2,pot);\r
160         }\r
161      if (!bit) clearBit(tree,pos);\r
162      return bit;\r
163   }\r
164 \r
165 void clearRange (results R, int p1, int p2)\r
166 \r
167   { if ((p2+1)<<1 > R.n) \r
168          clearRangeLeft(R.tree,conv(p1,R.n,R.lgn),R.n,0,R.lgn);\r
169     else clearBoth(R.tree,R.n,conv(p1,R.n,R.lgn),conv(p2+1,R.n,R.lgn),0,R.lgn);\r
170   }\r
171 \r
172 static int nextSmallest (int *tree, int n, int pos, int pot)\r
173 \r
174   { int p = 0;\r
175     while (1)\r
176        { pot--;\r
177          pos = (pos<<1)+1;\r
178          if (pos >= n) return p;\r
179          if (!getBit(tree,pos)) { pos++; p |= (1<<pot); }\r
180        }\r
181   }\r
182 \r
183 static int nextLarger (int *tree, int n, int p, int pos, int pot)\r
184 \r
185   { int answ;\r
186     if (!getBit(tree,pos)) return -1; // no answer\r
187     pos = (pos<<1)+1;\r
188     if (pos >= n) return 0; // when n is not a power of 2, missing leaves\r
189     pot--;\r
190     if ((p>>pot) == 0) // p goes left\r
191        { answ = nextLarger(tree,n,p&~(1<<pot),pos,pot);\r
192          if (answ != -1) return answ;\r
193          if (!getBit(tree,pos+1)) return -1; // no answer\r
194          return (1<<pot) | nextSmallest(tree,n,pos+1,pot);\r
195        }\r
196     else \r
197        { answ = nextLarger(tree,n,p&~(1<<pot),pos+1,pot);\r
198          if (answ != -1) return (1<<pot) | answ;\r
199          return -1;\r
200        }\r
201   }\r
202 \r
203 int nextResult (results R, int p) // returns pos of next(p) or -1 if none\r
204 \r
205   { int answ;\r
206     if (((p+1)<<1) > R.n) return -1; // next(last), p+1 out of bounds\r
207     answ = nextLarger(R.tree,R.n,conv(p+1,R.n,R.lgn),0,R.lgn);\r
208     if (answ == -1) return -1;\r
209     return unconv(answ,R.n,R.lgn);\r
210   }\r
211 \r
212 // Naively implemented by kim\r
213 \r
214 unsigned int countResult(results R) {\r
215   unsigned int result = -1;\r
216   int i = 0;\r
217   while ( i != -1 && i < R.n) {\r
218     result ++; \r
219     i = unconv(nextLarger(R.tree,R.n,conv(i+1,R.n,R.lgn),0,R.lgn),R.n,R.lgn);\r
220   };\r
221   return result;\r
222    \r
223 }\r
224 \r
225 \r
226 static void prnspace (int k)\r
227 \r
228   { while (k--) putchar(' ');\r
229   }\r
230 \r
231 void printTree (results R)\r
232 \r
233   { int n = R.n;\r
234     int pot = lg(R.n);\r
235     int pos = 0;\r
236     int num = 1;\r
237     while (pot)\r
238       { int lnum = num;\r
239         prnspace((1<<(pot-1))-1);\r
240         while (lnum-- && n--)\r
241             { putchar (getBit(R.tree,pos) ? '1' : '0');\r
242               pos++;\r
243               prnspace((1<<pot)-1); \r
244             }\r
245         putchar('\n');\r
246         num <<= 1;\r
247         pot--;\r
248       }\r
249   }\r
250 \r