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
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
15 static int lg (int n)
\r
18 while (n) { n>>=1; answ++; }
\r
22 results createResults (int n)
\r
25 if (logW != lg(W)-1)
\r
26 { fprintf(stderr,"Error, redefine logW as %i and recompile\n",lg(W)-1);
\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
39 void freeResults (results R)
\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
47 { int t = n+1-(1<<lgn);
\r
48 if (p < t) return p;
\r
52 static int unconv (int p, int n, int lgn)
\r
54 { int t = n+1-(1<<lgn);
\r
55 if (p < t) return p;
\r
59 int readResult (results R, int p) // returns 0 or 1
\r
65 do { if (!getBit(R.tree,pos)) return 0;
\r
67 pos = (pos<<1)+1+(p>>pot);
\r
74 void setResult (results R, int p)
\r
81 do { npos = (pos<<1)+1;
\r
82 if (!getBit(R.tree,pos))
\r
83 { setBit(R.tree,pos);
\r
85 { clearBit(R.tree,npos);
\r
86 clearBit(R.tree,npos+1);
\r
90 pos = npos+(p>>pot);
\r
96 // returns final value of bit at pos
\r
98 static int clearRangeLeft (int *tree, int p1, int n, int pos, int pot)
\r
102 if (!getBit(tree,pos)) return 0; // range already zeroed
\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
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
114 { bit = clearRangeLeft(tree,p1,n,npos+1,pot);
\r
115 if (!bit) bit = getBit(tree,npos);
\r
117 if (!bit) clearBit(tree,pos);
\r
121 static int clearRangeRight (int *tree, int p2, int n, int pos, int pot)
\r
125 if (!getBit(tree,pos)) return 0; // range already zeroed
\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
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
136 { bit = clearRangeRight(tree,p2,n,npos,pot);
\r
137 if (!bit) bit = getBit(tree,npos+1);
\r
139 if (!bit) clearBit(tree,pos);
\r
143 static int clearBoth (int *tree, int n, int p1, int p2, int pos, int pot)
\r
145 { int npos,npos1,npos2;
\r
147 if (!getBit(tree,pos)) return 0; // range is already zeroed
\r
149 // children must exist while the path is unique, as p1<p2
\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
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
161 if (!bit) clearBit(tree,pos);
\r
165 void clearRange (results R, int p1, int p2)
\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
172 static int nextSmallest (int *tree, int n, int pos, int pot)
\r
178 if (pos >= n) return p;
\r
179 if (!getBit(tree,pos)) { pos++; p |= (1<<pot); }
\r
183 static int nextLarger (int *tree, int n, int p, int pos, int pot)
\r
186 if (!getBit(tree,pos)) return -1; // no answer
\r
188 if (pos >= n) return 0; // when n is not a power of 2, missing leaves
\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
197 { answ = nextLarger(tree,n,p&~(1<<pot),pos+1,pot);
\r
198 if (answ != -1) return (1<<pot) | answ;
\r
203 int nextResult (results R, int p) // returns pos of next(p) or -1 if none
\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
212 // Naively implemented by kim
\r
214 unsigned int countResult(results R) {
\r
215 unsigned int result = -1;
\r
217 while ( i != -1 && i < R.n) {
\r
219 i = unconv(nextLarger(R.tree,R.n,conv(i+1,R.n,R.lgn),0,R.lgn),R.n,R.lgn);
\r
226 static void prnspace (int k)
\r
228 { while (k--) putchar(' ');
\r
231 void printTree (results R)
\r
239 prnspace((1<<(pot-1))-1);
\r
240 while (lnum-- && n--)
\r
241 { putchar (getBit(R.tree,pos) ? '1' : '0');
\r
243 prnspace((1<<pot)-1);
\r