3 #include "ResultSet.h"
\r
8 #define W (8*sizeof(ulong))
\r
10 #if __WORDSIZE == 64
\r
11 #define logW 6lu // 64bit system, code checks = lg(W)-1
\r
13 #define logW 5lu // 32bit system, code checks = lg(W)-1
\r
16 #define divW(p) ((p)>>logW)
\r
17 #define modW(p) ((p)&(W-1))
\r
19 #define setBit(arr,pos) ((arr)[divW(pos)] |= 1lu<<modW(pos))
\r
20 #define clearBit(arr,pos) ((arr)[divW(pos)] &= ~(1lu<<modW(pos)))
\r
21 #define getBit(arr,pos) ((arr)[divW(pos)] & (1lu<<modW(pos))) // 0 or !=0
\r
24 ulong ResultSet::lg (ulong n)
\r
27 while (n) { n>>=1lu; answ++; }
\r
31 ResultSet::ResultSet(ulong n)
\r
33 if (logW != lg(W)-1)
\r
35 std::cerr << "Error, redefine logW as " << lg(W)-1 << " and recompile\n";
\r
40 this->tree = new ulong[(this->n+W-1)/W];
\r
43 std::cerr << "Malloc failed at ResultSet class." << std::endl;
\r
46 clearBit(this->tree,0); // clear all
\r
49 ResultSet::~ResultSet()
\r
54 // to map 1..n to the bottom of the tree when n is not a power of 2
\r
55 ulong ResultSet::conv (ulong p, ulong n, ulong lgn)
\r
57 { ulong t = n+1-(1lu<<lgn);
\r
58 if (p < t) return p;
\r
62 ulong ResultSet::unconv (ulong p, ulong n, ulong lgn)
\r
64 { ulong t = n+1-(1lu<<lgn);
\r
65 if (p < t) return p;
\r
69 bool ResultSet::get (ulong p) // returns 0 or 1
\r
73 ulong pot = this->lgn;
\r
75 do { if (!getBit(this->tree,pos)) return false;
\r
77 pos = (pos<<1lu)+1+(p>>pot);
\r
84 void ResultSet::set (ulong p)
\r
89 ulong pot = this->lgn;
\r
91 do { npos = (pos<<1lu)+1;
\r
92 if (!getBit(this->tree,pos))
\r
93 { setBit(this->tree,pos);
\r
95 { clearBit(this->tree,npos);
\r
96 clearBit(this->tree,npos+1);
\r
100 pos = npos+(p>>pot);
\r
106 // returns final value of bit at pos
\r
108 ulong ResultSet::clearRangeLeft (ulong p1, ulong n, ulong pos, ulong pot)
\r
111 if (!getBit(tree,pos)) return 0; // range already zeroed
\r
113 if (p1 == 0) // full range to clear
\r
114 { clearBit(tree,pos); return 0; }
\r
115 // p1 != 0, there must be children
\r
117 npos = (pos<<1lu)+1;
\r
118 if ((p1>>pot) == 0) // go left, clear right
\r
119 { clearBit(tree,npos+1);
\r
120 bit = clearRangeLeft(p1,n,npos,pot);
\r
123 { bit = clearRangeLeft(p1,n,npos+1,pot);
\r
124 if (!bit) bit = getBit(tree,npos);
\r
126 if (!bit) clearBit(tree,pos);
\r
130 ulong ResultSet::clearRangeRight (ulong p2, ulong n, ulong pos, ulong pot)
\r
134 if (!getBit(tree,pos)) return 0; // range already zeroed
\r
136 if (p2 == 0) return 1; // empty range to clear, and bit is 1 for sure
\r
137 // p2 != 0, there must be children
\r
139 npos = (pos<<1lu)+1;
\r
140 if ((p2>>pot) == 1) // go right, clear left
\r
141 { clearBit(tree,npos);
\r
142 bit = clearRangeRight(p2,n,npos+1,pot);
\r
145 { bit = clearRangeRight(p2,n,npos,pot);
\r
146 if (!bit) bit = getBit(tree,npos+1);
\r
148 if (!bit) clearBit(tree,pos);
\r
152 ulong ResultSet::clearBoth (ulong n, ulong p1, ulong p2, ulong pos, ulong pot)
\r
154 { ulong npos,npos1,npos2;
\r
156 if (!getBit(tree,pos)) return 0; // range is already zeroed
\r
157 npos = (pos<<1lu)+1;
\r
158 // children must exist while the path is unique, as p1<p2
\r
160 npos1 = npos+(p1>>pot);
\r
161 npos2 = npos+(p2>>pot);
\r
162 if (npos1 == npos2) // we're inside npos1=npos2
\r
163 { bit = clearBoth (n,p1&~(1lu<<pot),p2&~(1lu<<pot),npos1,pot);
\r
164 bit |= getBit(tree,npos+1-(p1>>pot)); // the other
\r
166 else // p1 and p2 take different paths here
\r
167 { bit = clearRangeLeft(p1,n,npos1,pot);
\r
168 bit |= clearRangeRight(p2,n,npos2,pot);
\r
170 if (!bit) clearBit(tree,pos);
\r
174 void ResultSet::clearRange (ulong p1, ulong p2)
\r
176 { if ((p2+1)<<1lu > this->n)
\r
177 clearRangeLeft(conv(p1,this->n,this->lgn),this->n,0,this->lgn);
\r
178 else clearBoth(n,conv(p1,n,this->lgn),conv(p2+1,n,lgn),0,lgn);
\r
181 ulong ResultSet::nextSmallest (ulong n, ulong pos, ulong pot)
\r
186 pos = (pos<<1lu)+1;
\r
187 if (pos >= n) return p;
\r
188 if (!getBit(tree,pos)) { pos++; p |= (1lu<<pot); }
\r
192 ulong ResultSet::nextLarger (ulong n, ulong p, ulong pos, ulong pot)
\r
195 if (!getBit(tree,pos)) return ~0lu; // no answer
\r
197 pos = (pos<<1lu)+1;
\r
198 if (pos >= n) return 0; // when n is not a power of 2, missing leaves
\r
199 if ((p>>pot) == 0) // p goes left
\r
200 { answ = nextLarger(n,p&~(1lu<<pot),pos,pot);
\r
201 if (answ != ~0lu) return answ;
\r
202 if (!getBit(tree,pos+1)) return ~0lu; // no answer
\r
203 return (1lu<<pot) | nextSmallest(n,pos+1,pot);
\r
206 { answ = nextLarger(n,p&~(1lu<<pot),pos+1,pot);
\r
207 if (answ != ~0lu) return (1lu<<pot) | answ;
\r
213 void ResultSet::clear()
\r
215 clearBit(this->tree,0);
\r
218 ulong ResultSet::nextResult (ulong p) // returns pos of next(p) or -1 if none
\r
221 if (((p+1)<<1lu) > this->n) return ~0lu; // next(last), p+1 out of bounds
\r
222 answ = nextLarger(this->n,conv(p+1,this->n,this->lgn),0,this->lgn);
\r
223 if (answ == ~0lu) return ~0lu;
\r
224 return unconv(answ,this->n,this->lgn);
\r