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