src/results.c

   1 \r
   2 #include <stdio.h> \r
   3 #include <stdlib.h> \r
   4 #include "results.h"\r
   5 \r
   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
  10 \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
  14 \r
  15 static int lg (int n)\r
  16 \r
  17   { int answ=0;\r
  18     while (n) { n>>=1; answ++; }\r
  19     return answ;\r
  20   }\r
  21 \r
  22 results createResults (int n)\r
  23 \r
  24   { results R;\r
  25     if (logW != lg(W)-1)\r
  26        { fprintf(stderr,"Error, redefine logW as %i and recompile\n",lg(W)-1);\r
  27          exit(1);\r
  28        }\r
  29 \r
  30     R.n = 2*n-1;\r
  31     R.lgn = lg(n);\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
  36     return R;\r
  37   }\r
  38 \r
  39 void freeResults (results R)\r
  40 \r
  41   { free (R.tree);\r
  42   }\r
  43 \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
  46 \r
  47   { int t = n+1-(1<<lgn);\r
  48     return (p < t) ? p : (p<<1)-t;\r
  49   }\r
  50 \r
  51 static int unconv (int p, int n, int lgn)\r
  52 \r
  53   { int t = n+1-(1<<lgn);\r
  54     return (p < t) ? p : (p+t)>>1;\r
  55   }\r
  56 \r
  57 int readResult (results R, int p) // returns 0 or 1\r
  58 \r
  59   { int n = R.n;\r
  60     int pos = 0;\r
  61     int pot = R.lgn;\r
  62     p = conv(p,n,pot);\r
  63     do { if (!getBit(R.tree,pos)) return 0;\r
  64           pot--;\r
  65           pos = (pos<<1)+1+(p>>pot);\r
  66           p &= ~(1<<pot);\r
  67         }\r
  68     while (pos < n);\r
  69     return 1;\r
  70   }\r
  71 \r
  72 void setResult (results R, int p)\r
  73 \r
  74   { int n = R.n;\r
  75     int pos = 0;\r
  76     int npos;\r
  77     int pot = R.lgn;\r
  78     p = conv(p,n,pot);\r
  79     do { npos = (pos<<1)+1;\r
  80          if (!getBit(R.tree,pos))\r
  81             { setBit(R.tree,pos);\r
  82               if (npos < n) \r
  83                  { clearBit(R.tree,npos);\r
  84                    clearBit(R.tree,npos+1);\r
  85                  }\r
  86             }\r
  87           pot--;\r
  88           pos = npos+(p>>pot);\r
  89           p &= ~(1<<pot);\r
  90         }\r
  91     while (pos < n);\r
  92   }\r
  93 \r
  94         // returns final value of bit at pos\r
  95         \r
  96 static int clearRangeLeft (int *tree, int p1, int n, int pos, int pot)\r
  97 \r
  98   { int npos;\r
  99     int bit;\r
 100     if (!getBit(tree,pos)) return 0; // range already zeroed\r
 101     p1 &= ~(1<<pot);\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
 105     pot--;\r
 106     npos = (pos<<1)+1;\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
 110        } \r
 111     else // go right\r
 112        { bit = clearRangeLeft(tree,p1,n,npos+1,pot);\r
 113          if (!bit) bit = getBit(tree,npos);\r
 114        }\r
 115     if (!bit) clearBit(tree,pos);\r
 116     return bit;\r
 117   }\r
 118 \r
 119 static int clearRangeRight (int *tree, int p2, int n, int pos, int pot)\r
 120 \r
 121   { int npos;\r
 122     int bit;\r
 123     if (!getBit(tree,pos)) return 0; // range already zeroed\r
 124     p2 &= ~(1<<pot);\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
 127     pot--;\r
 128     npos = (pos<<1)+1;\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
 132        } \r
 133     else // go left\r
 134        { bit = clearRangeRight(tree,p2,n,npos,pot);\r
 135          if (!bit) bit = getBit(tree,npos+1);\r
 136        }\r
 137     if (!bit) clearBit(tree,pos);\r
 138     return bit;\r
 139   }\r
 140 \r
 141 static int clearBoth (int *tree, int n, int p1, int p2, int pos, int pot)\r
 142 \r
 143   { int npos,npos1,npos2;\r
 144     int bit;\r
 145     if (!getBit(tree,pos)) return 0; // range is already zeroed\r
 146     npos = (pos<<1)+1;\r
 147         // children must exist while the path is unique, as p1<p2\r
 148     pot--;\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
 154        }\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
 158         }\r
 159      if (!bit) clearBit(tree,pos);\r
 160      return bit;\r
 161   }\r
 162 \r
 163 void clearRange (results R, int p1, int p2)\r
 164 \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
 168   }\r
 169 \r
 170 static int nextSmallest (int *tree, int n, int pos, int pot)\r
 171 \r
 172   { int p = 0;\r
 173     while (1)\r
 174        { pot--;\r
 175          pos = (pos<<1)+1;\r
 176          if (pos >= n) return p;\r
 177          if (!getBit(tree,pos)) { pos++; p |= (1<<pot); }\r
 178        }\r
 179   }\r
 180 \r
 181 static int nextLarger (int *tree, int n, int p, int pos, int pot)\r
 182 \r
 183   { int answ;\r
 184     if (!getBit(tree,pos)) return -1; // no answer\r
 185     pos = (pos<<1)+1;\r
 186     if (pos >= n) return 0; // when n is not a power of 2, missing leaves\r
 187     pot--;\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
 193        }\r
 194     else \r
 195        { answ = nextLarger(tree,n,p&~(1<<pot),pos+1,pot);\r
 196          if (answ != -1) return (1<<pot) | answ;\r
 197          return -1;\r
 198        }\r
 199   }\r
 200 \r
 201 int nextResult (results R, int p) // returns pos of next(p) or -1 if none\r
 202 \r
 203   { int answ;\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
 207   }\r
 208 \r
 209 // Naively implemented by kim\r
 210 \r
 211 unsigned int countResult(results R) {\r
 212   unsigned int result = -1;\r
 213   int i = 0;\r
 214   while ( i != -1 && i < R.n) {\r
 215     result ++; \r
 216     i = unconv(nextLarger(R.tree,R.n,conv(i+1,R.n,R.lgn),0,R.lgn),R.n,R.lgn);\r
 217   };\r
 218   return result;\r
 219    \r
 220 }\r
 221 \r
 222 \r
 223 static void prnspace (int k)\r
 224 \r
 225   { while (k--) putchar(' ');\r
 226   }\r
 227 \r
 228 void printTree (results R)\r
 229 \r
 230   { int n = R.n;\r
 231     int pot = lg(R.n);\r
 232     int pos = 0;\r
 233     int num = 1;\r
 234     while (pot)\r
 235       { int lnum = num;\r
 236         prnspace((1<<(pot-1))-1);\r
 237         while (lnum-- && n--)\r
 238             { putchar (getBit(R.tree,pos) ? '1' : '0');\r
 239               pos++;\r
 240               prnspace((1<<pot)-1); \r
 241             }\r
 242         putchar('\n');\r
 243         num <<= 1;\r
 244         pot--;\r
 245       }\r
 246   }\r
 247 \r