--- /dev/null
+\r
+#include <iostream> \r
+#include "ResultSet.h"\r
+\r
+namespace SXSI\r
+{\r
+\r
+#define W (8*sizeof(ulong))\r
+\r
+#if __WORDSIZE == 64\r
+#define logW 6lu // 64bit system, code checks = lg(W)-1\r
+#else\r
+#define logW 5lu // 32bit system, code checks = lg(W)-1\r
+#endif\r
+\r
+#define divW(p) ((p)>>logW)\r
+#define modW(p) ((p)&(W-1))\r
+\r
+#define setBit(arr,pos) ((arr)[divW(pos)] |= 1lu<<modW(pos))\r
+#define clearBit(arr,pos) ((arr)[divW(pos)] &= ~(1lu<<modW(pos)))\r
+#define getBit(arr,pos) ((arr)[divW(pos)] & (1lu<<modW(pos))) // 0 or !=0\r
+\r
+\r
+ulong ResultSet::lg (ulong n)\r
+{ \r
+ ulong answ=0;\r
+ while (n) { n>>=1lu; answ++; }\r
+ return answ;\r
+}\r
+\r
+ResultSet::ResultSet(ulong n)\r
+{ \r
+ if (logW != lg(W)-1)\r
+ { \r
+ std::cerr << "Error, redefine logW as " << lg(W)-1 << " and recompile\n";\r
+// exit(1);\r
+ }\r
+ this->n = 2*n-1;\r
+ this->lgn = lg(n);\r
+ this->tree = new ulong[(this->n+W-1)/W];\r
+ if (!this->tree)\r
+ {\r
+ std::cerr << "Malloc failed at ResultSet class." << std::endl;\r
+ // exit(1);\r
+ }\r
+ clearBit(this->tree,0); // clear all\r
+}\r
+\r
+ResultSet::~ResultSet()\r
+{ \r
+ delete [] tree;\r
+}\r
+\r
+// to map 1..n to the bottom of the tree when n is not a power of 2\r
+ulong ResultSet::conv (ulong p, ulong n, ulong lgn)\r
+\r
+ { ulong t = n+1-(1lu<<lgn);\r
+ if (p < t) return p;\r
+ return (p<<1lu)-t;\r
+ }\r
+\r
+ulong ResultSet::unconv (ulong p, ulong n, ulong lgn)\r
+\r
+ { ulong t = n+1-(1lu<<lgn);\r
+ if (p < t) return p;\r
+ return (p+t)>>1lu;\r
+ }\r
+\r
+bool ResultSet::get (ulong p) // returns 0 or 1\r
+\r
+ { \r
+ ulong pos = 0;\r
+ ulong pot = this->lgn;\r
+ p = conv(p,n,pot);\r
+ do { if (!getBit(this->tree,pos)) return false;\r
+ pot--;\r
+ pos = (pos<<1lu)+1+(p>>pot);\r
+ p &= ~(1lu<<pot);\r
+ }\r
+ while (pos < n);\r
+ return true;\r
+ }\r
+\r
+void ResultSet::set (ulong p)\r
+\r
+ { \r
+ ulong pos = 0;\r
+ ulong npos;\r
+ ulong pot = this->lgn;\r
+ p = conv(p,n,pot);\r
+ do { npos = (pos<<1lu)+1;\r
+ if (!getBit(this->tree,pos))\r
+ { setBit(this->tree,pos);\r
+ if (npos < n) \r
+ { clearBit(this->tree,npos);\r
+ clearBit(this->tree,npos+1);\r
+ }\r
+ }\r
+ pot--;\r
+ pos = npos+(p>>pot);\r
+ p &= ~(1lu<<pot);\r
+ }\r
+ while (pos < n);\r
+ }\r
+\r
+ // returns final value of bit at pos\r
+ \r
+ulong ResultSet::clearRangeLeft (ulong p1, ulong n, ulong pos, ulong pot)\r
+ { ulong npos;\r
+ ulong bit;\r
+ if (!getBit(tree,pos)) return 0; // range already zeroed\r
+ p1 &= ~(1lu<<pot);\r
+ if (p1 == 0) // full range to clear\r
+ { clearBit(tree,pos); return 0; }\r
+ // p1 != 0, there must be children\r
+ pot--;\r
+ npos = (pos<<1lu)+1;\r
+ if ((p1>>pot) == 0) // go left, clear right\r
+ { clearBit(tree,npos+1);\r
+ bit = clearRangeLeft(p1,n,npos,pot);\r
+ } \r
+ else // go right\r
+ { bit = clearRangeLeft(p1,n,npos+1,pot);\r
+ if (!bit) bit = getBit(tree,npos);\r
+ }\r
+ if (!bit) clearBit(tree,pos);\r
+ return bit;\r
+ }\r
+\r
+ulong ResultSet::clearRangeRight (ulong p2, ulong n, ulong pos, ulong pot)\r
+\r
+ { ulong npos;\r
+ ulong bit;\r
+ if (!getBit(tree,pos)) return 0; // range already zeroed\r
+ p2 &= ~(1lu<<pot);\r
+ if (p2 == 0) return 1; // empty range to clear, and bit is 1 for sure\r
+ // p2 != 0, there must be children\r
+ pot--;\r
+ npos = (pos<<1lu)+1;\r
+ if ((p2>>pot) == 1) // go right, clear left\r
+ { clearBit(tree,npos);\r
+ bit = clearRangeRight(p2,n,npos+1,pot);\r
+ } \r
+ else // go left\r
+ { bit = clearRangeRight(p2,n,npos,pot);\r
+ if (!bit) bit = getBit(tree,npos+1);\r
+ }\r
+ if (!bit) clearBit(tree,pos);\r
+ return bit;\r
+ }\r
+\r
+ulong ResultSet::clearBoth (ulong n, ulong p1, ulong p2, ulong pos, ulong pot)\r
+\r
+ { ulong npos,npos1,npos2;\r
+ ulong bit;\r
+ if (!getBit(tree,pos)) return 0; // range is already zeroed\r
+ npos = (pos<<1lu)+1;\r
+ // children must exist while the path is unique, as p1<p2\r
+ pot--;\r
+ npos1 = npos+(p1>>pot);\r
+ npos2 = npos+(p2>>pot);\r
+ if (npos1 == npos2) // we're inside npos1=npos2\r
+ { bit = clearBoth (n,p1&~(1lu<<pot),p2&~(1lu<<pot),npos1,pot);\r
+ bit |= getBit(tree,npos+1-(p1>>pot)); // the other\r
+ }\r
+ else // p1 and p2 take different paths here\r
+ { bit = clearRangeLeft(p1,n,npos1,pot); \r
+ bit |= clearRangeRight(p2,n,npos2,pot);\r
+ }\r
+ if (!bit) clearBit(tree,pos);\r
+ return bit;\r
+ }\r
+\r
+void ResultSet::clearRange (ulong p1, ulong p2)\r
+\r
+ { if ((p2+1)<<1lu > this->n) \r
+ clearRangeLeft(conv(p1,this->n,this->lgn),this->n,0,this->lgn);\r
+ else clearBoth(n,conv(p1,n,this->lgn),conv(p2+1,n,lgn),0,lgn);\r
+ }\r
+\r
+ulong ResultSet::nextSmallest (ulong n, ulong pos, ulong pot)\r
+\r
+ { ulong p = 0;\r
+ while (1)\r
+ { pot--;\r
+ pos = (pos<<1lu)+1;\r
+ if (pos >= n) return p;\r
+ if (!getBit(tree,pos)) { pos++; p |= (1lu<<pot); }\r
+ }\r
+ }\r
+\r
+ulong ResultSet::nextLarger (ulong n, ulong p, ulong pos, ulong pot)\r
+\r
+ { ulong answ;\r
+ if (!getBit(tree,pos)) return ~0lu; // no answer\r
+ pot--;\r
+ pos = (pos<<1lu)+1;\r
+ if (pos >= n) return 0; // when n is not a power of 2, missing leaves\r
+ if ((p>>pot) == 0) // p goes left\r
+ { answ = nextLarger(n,p&~(1lu<<pot),pos,pot);\r
+ if (answ != ~0lu) return answ;\r
+ if (!getBit(tree,pos+1)) return ~0lu; // no answer\r
+ return (1lu<<pot) | nextSmallest(n,pos+1,pot);\r
+ }\r
+ else \r
+ { answ = nextLarger(n,p&~(1lu<<pot),pos+1,pot);\r
+ if (answ != ~0lu) return (1lu<<pot) | answ;\r
+ return ~0lu;\r
+ }\r
+ }\r
+\r
+\r
+void ResultSet::clear()\r
+{\r
+ clearBit(this->tree,0);\r
+}\r
+\r
+ulong ResultSet::nextResult (ulong p) // returns pos of next(p) or -1 if none\r
+\r
+ { ulong answ;\r
+ if (((p+1)<<1lu) > this->n) return ~0lu; // next(last), p+1 out of bounds\r
+ answ = nextLarger(this->n,conv(p+1,this->n,this->lgn),0,this->lgn);\r
+ if (answ == ~0lu) return ~0lu;\r
+ return unconv(answ,this->n,this->lgn);\r
+ }\r
+\r
+} // Namespace\r
projects / SXSI / TextCollection.git / blobdiff