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     if (p < t) return p;\r
  49     return (p<<1)-t;\r
  50   }\r
  51 \r
  52 static int unconv (int p, int n, int lgn)\r
  53 \r
  54   { int t = n+1-(1<<lgn);\r
  55     if (p < t) return p;\r
  56     return (p+t)>>1;\r
  57   }\r
  58 \r
  59 int readResult (results R, int p) // returns 0 or 1\r
  60 \r
  61   { int n = R.n;\r
  62     int pos = 0;\r
  63     int pot = R.lgn;\r
  64     p = conv(p,n,pot);\r
  65     do { if (!getBit(R.tree,pos)) return 0;\r
  66           pot--;\r
  67           pos = (pos<<1)+1+(p>>pot);\r
  68           p &= ~(1<<pot);\r
  69         }\r
  70     while (pos < n);\r
  71     return 1;\r
  72   }\r
  73 \r
  74 void setResult (results R, int p)\r
  75 \r
  76   { int n = R.n;\r
  77     int pos = 0;\r
  78     int npos;\r
  79     int pot = R.lgn;\r
  80     p = conv(p,n,pot);\r
  81     do { npos = (pos<<1)+1;\r
  82          if (!getBit(R.tree,pos))\r
  83             { setBit(R.tree,pos);\r
  84               if (npos < n) \r
  85                  { clearBit(R.tree,npos);\r
  86                    clearBit(R.tree,npos+1);\r
  87                  }\r
  88             }\r
  89           pot--;\r
  90           pos = npos+(p>>pot);\r
  91           p &= ~(1<<pot);\r
  92         }\r
  93     while (pos < n);\r
  94   }\r
  95 \r
  96         // returns final value of bit at pos\r
  97         \r
  98 static int clearRangeLeft (int *tree, int p1, int n, int pos, int pot)\r
  99 \r
 100   { int npos;\r
 101     int bit;\r
 102     if (!getBit(tree,pos)) return 0; // range already zeroed\r
 103     p1 &= ~(1<<pot);\r
 104     if (p1 == 0) // full range to clear\r
 105        { clearBit(tree,pos); return 0; }\r
 106         // p1 != 0, there must be children\r
 107     pot--;\r
 108     npos = (pos<<1)+1;\r
 109     if ((p1>>pot) == 0) // go left, clear right\r
 110        { clearBit(tree,npos+1);\r
 111          bit = clearRangeLeft(tree,p1,n,npos,pot);\r
 112        } \r
 113     else // go right\r
 114        { bit = clearRangeLeft(tree,p1,n,npos+1,pot);\r
 115          if (!bit) bit = getBit(tree,npos);\r
 116        }\r
 117     if (!bit) clearBit(tree,pos);\r
 118     return bit;\r
 119   }\r
 120 \r
 121 static int clearRangeRight (int *tree, int p2, int n, int pos, int pot)\r
 122 \r
 123   { int npos;\r
 124     int bit;\r
 125     if (!getBit(tree,pos)) return 0; // range already zeroed\r
 126     p2 &= ~(1<<pot);\r
 127     if (p2 == 0) return 1; // empty range to clear, and bit is 1 for sure\r
 128         // p2 != 0, there must be children\r
 129     pot--;\r
 130     npos = (pos<<1)+1;\r
 131     if ((p2>>pot) == 1) // go right, clear left\r
 132        { clearBit(tree,npos);\r
 133          bit = clearRangeRight(tree,p2,n,npos+1,pot);\r
 134        } \r
 135     else // go left\r
 136        { bit = clearRangeRight(tree,p2,n,npos,pot);\r
 137          if (!bit) bit = getBit(tree,npos+1);\r
 138        }\r
 139     if (!bit) clearBit(tree,pos);\r
 140     return bit;\r
 141   }\r
 142 \r
 143 static int clearBoth (int *tree, int n, int p1, int p2, int pos, int pot)\r
 144 \r
 145   { int npos,npos1,npos2;\r
 146     int bit;\r
 147     if (!getBit(tree,pos)) return 0; // range is already zeroed\r
 148     npos = (pos<<1)+1;\r
 149         // children must exist while the path is unique, as p1<p2\r
 150     pot--;\r
 151     npos1 = npos+(p1>>pot);\r
 152     npos2 = npos+(p2>>pot);\r
 153     if (npos1 == npos2) // we're inside npos1=npos2\r
 154        { bit = clearBoth (tree,n,p1&~(1<<pot),p2&~(1<<pot),npos1,pot);\r
 155          bit |= getBit(tree,npos+1-(p1>>pot)); // the other\r
 156        }\r
 157      else  // p1 and p2 take different paths here\r
 158         { bit  = clearRangeLeft(tree,p1,n,npos1,pot); \r
 159           bit |= clearRangeRight(tree,p2,n,npos2,pot);\r
 160         }\r
 161      if (!bit) clearBit(tree,pos);\r
 162      return bit;\r
 163   }\r
 164 \r
 165 void clearRange (results R, int p1, int p2)\r
 166 \r
 167   { if ((p2+1)<<1 > R.n) \r
 168          clearRangeLeft(R.tree,conv(p1,R.n,R.lgn),R.n,0,R.lgn);\r
 169     else clearBoth(R.tree,R.n,conv(p1,R.n,R.lgn),conv(p2+1,R.n,R.lgn),0,R.lgn);\r
 170   }\r
 171 \r
 172 static int nextSmallest (int *tree, int n, int pos, int pot)\r
 173 \r
 174   { int p = 0;\r
 175     while (1)\r
 176        { pot--;\r
 177          pos = (pos<<1)+1;\r
 178          if (pos >= n) return p;\r
 179          if (!getBit(tree,pos)) { pos++; p |= (1<<pot); }\r
 180        }\r
 181   }\r
 182 \r
 183 static int nextLarger (int *tree, int n, int p, int pos, int pot)\r
 184 \r
 185   { int answ;\r
 186     if (!getBit(tree,pos)) return -1; // no answer\r
 187     pos = (pos<<1)+1;\r
 188     if (pos >= n) return 0; // when n is not a power of 2, missing leaves\r
 189     pot--;\r
 190     if ((p>>pot) == 0) // p goes left\r
 191        { answ = nextLarger(tree,n,p&~(1<<pot),pos,pot);\r
 192          if (answ != -1) return answ;\r
 193          if (!getBit(tree,pos+1)) return -1; // no answer\r
 194          return (1<<pot) | nextSmallest(tree,n,pos+1,pot);\r
 195        }\r
 196     else \r
 197        { answ = nextLarger(tree,n,p&~(1<<pot),pos+1,pot);\r
 198          if (answ != -1) return (1<<pot) | answ;\r
 199          return -1;\r
 200        }\r
 201   }\r
 202 \r
 203 int nextResult (results R, int p) // returns pos of next(p) or -1 if none\r
 204 \r
 205   { int answ;\r
 206     if (((p+1)<<1) > R.n) return -1; // next(last), p+1 out of bounds\r
 207     answ = nextLarger(R.tree,R.n,conv(p+1,R.n,R.lgn),0,R.lgn);\r
 208     if (answ == -1) return -1;\r
 209     return unconv(answ,R.n,R.lgn);\r
 210   }\r
 211 \r
 212 // Naively implemented by kim\r
 213 \r
 214 unsigned int countResult(results R) {\r
 215   unsigned int result = -1;\r
 216   int i = 0;\r
 217   while ( i != -1 && i < R.n) {\r
 218     result ++; \r
 219     i = unconv(nextLarger(R.tree,R.n,conv(i+1,R.n,R.lgn),0,R.lgn),R.n,R.lgn);\r
 220   };\r
 221   return result;\r
 222    \r
 223 }\r
 224 \r
 225 \r
 226 static void prnspace (int k)\r
 227 \r
 228   { while (k--) putchar(' ');\r
 229   }\r
 230 \r
 231 void printTree (results R)\r
 232 \r
 233   { int n = R.n;\r
 234     int pot = lg(R.n);\r
 235     int pos = 0;\r
 236     int num = 1;\r
 237     while (pot)\r
 238       { int lnum = num;\r
 239         prnspace((1<<(pot-1))-1);\r
 240         while (lnum-- && n--)\r
 241             { putchar (getBit(R.tree,pos) ? '1' : '0');\r
 242               pos++;\r
 243               prnspace((1<<pot)-1); \r
 244             }\r
 245         putchar('\n');\r
 246         num <<= 1;\r
 247         pot--;\r
 248       }\r
 249   }\r
 250 \r