ResultSet.cpp

   1 \r
   2 #include <iostream> \r
   3 #include "ResultSet.h"\r
   4 \r
   5 namespace SXSI\r
   6 {\r
   7 \r
   8 #define W (8*sizeof(ulong))\r
   9 \r
  10 #if __WORDSIZE == 64\r
  11 #define logW 6lu // 64bit system, code checks = lg(W)-1\r
  12 #else\r
  13 #define logW 5lu // 32bit system, code checks = lg(W)-1\r
  14 #endif\r
  15 \r
  16 #define divW(p) ((p)>>logW)\r
  17 #define modW(p) ((p)&(W-1))\r
  18 \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
  22 \r
  23 \r
  24 ulong ResultSet::lg (ulong n)\r
  25 { \r
  26     ulong answ=0;\r
  27     while (n) { n>>=1lu; answ++; }\r
  28     return answ;\r
  29 }\r
  30 \r
  31 ResultSet::ResultSet(ulong n)\r
  32 { \r
  33     if (logW != lg(W)-1)\r
  34     { \r
  35         std::cerr << "Error, redefine logW as " << lg(W)-1 << " and recompile\n";\r
  36 //        exit(1);\r
  37     }\r
  38     this->n = 2*n-1;\r
  39     this->lgn = lg(n);\r
  40     this->tree = new ulong[(this->n+W-1)/W];\r
  41     if (!this->tree)\r
  42     {\r
  43         std::cerr << "Malloc failed at ResultSet class." << std::endl;\r
  44         //      exit(1);\r
  45     }\r
  46     clearBit(this->tree,0); // clear all\r
  47 }\r
  48 \r
  49 ResultSet::~ResultSet()\r
  50 { \r
  51     delete [] tree;\r
  52 }\r
  53 \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
  56 \r
  57   { ulong t = n+1-(1lu<<lgn);\r
  58     if (p < t) return p;\r
  59     return (p<<1lu)-t;\r
  60   }\r
  61 \r
  62 ulong ResultSet::unconv (ulong p, ulong n, ulong lgn)\r
  63 \r
  64   { ulong t = n+1-(1lu<<lgn);\r
  65     if (p < t) return p;\r
  66     return (p+t)>>1lu;\r
  67   }\r
  68 \r
  69 bool ResultSet::get (ulong p) // returns 0 or 1\r
  70 \r
  71   { \r
  72     ulong pos = 0;\r
  73     ulong pot = this->lgn;\r
  74     p = conv(p,n,pot);\r
  75     do { if (!getBit(this->tree,pos)) return false;\r
  76           pot--;\r
  77           pos = (pos<<1lu)+1+(p>>pot);\r
  78           p &= ~(1lu<<pot);\r
  79         }\r
  80     while (pos < n);\r
  81     return true;\r
  82   }\r
  83 \r
  84 void ResultSet::set (ulong p)\r
  85 \r
  86   { \r
  87     ulong pos = 0;\r
  88     ulong npos;\r
  89     ulong pot = this->lgn;\r
  90     p = conv(p,n,pot);\r
  91     do { npos = (pos<<1lu)+1;\r
  92          if (!getBit(this->tree,pos))\r
  93             { setBit(this->tree,pos);\r
  94               if (npos < n) \r
  95                  { clearBit(this->tree,npos);\r
  96                    clearBit(this->tree,npos+1);\r
  97                  }\r
  98             }\r
  99           pot--;\r
 100           pos = npos+(p>>pot);\r
 101           p &= ~(1lu<<pot);\r
 102         }\r
 103     while (pos < n);\r
 104   }\r
 105 \r
 106         // returns final value of bit at pos\r
 107         \r
 108 ulong ResultSet::clearRangeLeft (ulong p1, ulong n, ulong pos, ulong pot)\r
 109  { ulong npos;\r
 110     ulong bit;\r
 111     if (!getBit(tree,pos)) return 0; // range already zeroed\r
 112     p1 &= ~(1lu<<pot);\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
 116     pot--;\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
 121        } \r
 122     else // go right\r
 123        { bit = clearRangeLeft(p1,n,npos+1,pot);\r
 124          if (!bit) bit = getBit(tree,npos);\r
 125        }\r
 126     if (!bit) clearBit(tree,pos);\r
 127     return bit;\r
 128   }\r
 129 \r
 130 ulong ResultSet::clearRangeRight (ulong p2, ulong n, ulong pos, ulong pot)\r
 131 \r
 132   { ulong npos;\r
 133     ulong bit;\r
 134     if (!getBit(tree,pos)) return 0; // range already zeroed\r
 135     p2 &= ~(1lu<<pot);\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
 138     pot--;\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
 143        } \r
 144     else // go left\r
 145        { bit = clearRangeRight(p2,n,npos,pot);\r
 146          if (!bit) bit = getBit(tree,npos+1);\r
 147        }\r
 148     if (!bit) clearBit(tree,pos);\r
 149     return bit;\r
 150   }\r
 151 \r
 152 ulong ResultSet::clearBoth (ulong n, ulong p1, ulong p2, ulong pos, ulong pot)\r
 153 \r
 154   { ulong npos,npos1,npos2;\r
 155     ulong bit;\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
 159     pot--;\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
 165        }\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
 169         }\r
 170      if (!bit) clearBit(tree,pos);\r
 171      return bit;\r
 172   }\r
 173 \r
 174 void ResultSet::clearRange (ulong p1, ulong p2)\r
 175 \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
 179   }\r
 180 \r
 181 ulong ResultSet::nextSmallest (ulong n, ulong pos, ulong pot)\r
 182 \r
 183   { ulong p = 0;\r
 184     while (1)\r
 185        { 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
 189        }\r
 190   }\r
 191 \r
 192 ulong ResultSet::nextLarger (ulong n, ulong p, ulong pos, ulong pot)\r
 193 \r
 194   { ulong answ;\r
 195     if (!getBit(tree,pos)) return ~0lu; // no answer\r
 196     pot--;\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
 204        }\r
 205     else \r
 206        { answ = nextLarger(n,p&~(1lu<<pot),pos+1,pot);\r
 207          if (answ != ~0lu) return (1lu<<pot) | answ;\r
 208          return ~0lu;\r
 209        }\r
 210   }\r
 211 \r
 212 \r
 213 void  ResultSet::clear()\r
 214 {\r
 215     clearBit(this->tree,0);\r
 216 }\r
 217 \r
 218 ulong ResultSet::nextResult (ulong p) // returns pos of next(p) or -1 if none\r
 219 \r
 220   { ulong answ;\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
 225   }\r
 226 \r
 227 } // Namespace\r