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 return (p < t) ? p : (p<<1)-t;
\r
51 static int unconv (int p, int n, int lgn)
\r
53 { int t = n+1-(1<<lgn);
\r
54 return (p < t) ? p : (p+t)>>1;
\r
57 int readResult (results R, int p) // returns 0 or 1
\r
63 do { if (!getBit(R.tree,pos)) return 0;
\r
65 pos = (pos<<1)+1+(p>>pot);
\r
72 void setResult (results R, int p)
\r
79 do { npos = (pos<<1)+1;
\r
80 if (!getBit(R.tree,pos))
\r
81 { setBit(R.tree,pos);
\r
83 { clearBit(R.tree,npos);
\r
84 clearBit(R.tree,npos+1);
\r
88 pos = npos+(p>>pot);
\r
94 // returns final value of bit at pos
\r
96 static int clearRangeLeft (int *tree, int p1, int n, int pos, int pot)
\r
100 if (!getBit(tree,pos)) return 0; // range already zeroed
\r
102 if (p1 == 0) // full range to clear
\r
103 { clearBit(tree,pos); return 0; }
\r
104 // p1 != 0, there must be children
\r
107 if ((p1>>pot) == 0) // go left, clear right
\r
108 { clearBit(tree,npos+1);
\r
109 bit = clearRangeLeft(tree,p1,n,npos,pot);
\r
112 { bit = clearRangeLeft(tree,p1,n,npos+1,pot);
\r
113 if (!bit) bit = getBit(tree,npos);
\r
115 if (!bit) clearBit(tree,pos);
\r
119 static int clearRangeRight (int *tree, int p2, int n, int pos, int pot)
\r
123 if (!getBit(tree,pos)) return 0; // range already zeroed
\r
125 if (p2 == 0) return 1; // empty range to clear, and bit is 1 for sure
\r
126 // p2 != 0, there must be children
\r
129 if ((p2>>pot) == 1) // go right, clear left
\r
130 { clearBit(tree,npos);
\r
131 bit = clearRangeRight(tree,p2,n,npos+1,pot);
\r
134 { bit = clearRangeRight(tree,p2,n,npos,pot);
\r
135 if (!bit) bit = getBit(tree,npos+1);
\r
137 if (!bit) clearBit(tree,pos);
\r
141 static int clearBoth (int *tree, int n, int p1, int p2, int pos, int pot)
\r
143 { int npos,npos1,npos2;
\r
145 if (!getBit(tree,pos)) return 0; // range is already zeroed
\r
147 // children must exist while the path is unique, as p1<p2
\r
149 npos1 = npos+(p1>>pot);
\r
150 npos2 = npos+(p2>>pot);
\r
151 if (npos1 == npos2) // we're inside npos1=npos2
\r
152 { bit = clearBoth (tree,n,p1&~(1<<pot),p2&~(1<<pot),npos1,pot);
\r
153 bit |= getBit(tree,npos+1-(p1>>pot)); // the other
\r
155 else // p1 and p2 take different paths here
\r
156 { bit = clearRangeLeft(tree,p1,n,npos1,pot);
\r
157 bit |= clearRangeRight(tree,p2,n,npos2,pot);
\r
159 if (!bit) clearBit(tree,pos);
\r
163 void clearRange (results R, int p1, int p2)
\r
165 { if ((p2+1)<<1 > R.n)
\r
166 clearRangeLeft(R.tree,conv(p1,R.n,R.lgn),R.n,0,R.lgn);
\r
167 else clearBoth(R.tree,R.n,conv(p1,R.n,R.lgn),conv(p2+1,R.n,R.lgn),0,R.lgn);
\r
170 static int nextSmallest (int *tree, int n, int pos, int pot)
\r
176 if (pos >= n) return p;
\r
177 if (!getBit(tree,pos)) { pos++; p |= (1<<pot); }
\r
181 static int nextLarger (int *tree, int n, int p, int pos, int pot)
\r
184 if (!getBit(tree,pos)) return -1; // no answer
\r
186 if (pos >= n) return 0; // when n is not a power of 2, missing leaves
\r
188 if ((p>>pot) == 0) // p goes left
\r
189 { answ = nextLarger(tree,n,p&~(1<<pot),pos,pot);
\r
190 if (answ != -1) return answ;
\r
191 if (!getBit(tree,pos+1)) return -1; // no answer
\r
192 return (1<<pot) | nextSmallest(tree,n,pos+1,pot);
\r
195 { answ = nextLarger(tree,n,p&~(1<<pot),pos+1,pot);
\r
196 if (answ != -1) return (1<<pot) | answ;
\r
201 int nextResult (results R, int p) // returns pos of next(p) or -1 if none
\r
204 if (((p+1)<<1) > R.n) return -1; // next(last), p+1 out of bounds
\r
205 answ = nextLarger(R.tree,R.n,conv(p+1,R.n,R.lgn),0,R.lgn);
\r
206 return (answ == -1) ? -1 : unconv(answ,R.n,R.lgn);
\r
209 // Naively implemented by kim
\r
211 unsigned int countResult(results R) {
\r
212 unsigned int result = -1;
\r
214 while ( i != -1 && i < R.n) {
\r
216 i = unconv(nextLarger(R.tree,R.n,conv(i+1,R.n,R.lgn),0,R.lgn),R.n,R.lgn);
\r
223 static void prnspace (int k)
\r
225 { while (k--) putchar(' ');
\r
228 void printTree (results R)
\r
236 prnspace((1<<(pot-1))-1);
\r
237 while (lnum-- && n--)
\r
238 { putchar (getBit(R.tree,pos) ? '1' : '0');
\r
240 prnspace((1<<pot)-1);
\r