--- /dev/null
+\r
+#include <stdio.h> \r
+#include <stdlib.h> \r
+#include "results.h"\r
+\r
+#define W (8*sizeof(int))\r
+#define logW 5 // code checks = lg(W)-1\r
+#define divW(p) ((p)>>logW)\r
+#define modW(p) ((p)&(W-1))\r
+\r
+#define setBit(arr,pos) ((arr)[divW(pos)] |= 1<<modW(pos))\r
+#define clearBit(arr,pos) ((arr)[divW(pos)] &= ~(1<<modW(pos)))\r
+#define getBit(arr,pos) ((arr)[divW(pos)] & (1<<modW(pos))) // 0 or !=0\r
+\r
+static int lg (int n)\r
+\r
+ { int answ=0;\r
+ while (n) { n>>=1; answ++; }\r
+ return answ;\r
+ }\r
+\r
+results createResults (int n)\r
+\r
+ { results R;\r
+ if (logW != lg(W)-1)\r
+ { fprintf(stderr,"Error, redefine logW as %i and recompile\n",lg(W)-1);\r
+ exit(1);\r
+ }\r
+\r
+ R.n = 2*n-1;\r
+ R.lgn = lg(n);\r
+ //fprintf(stderr,"Size of the result set : %i elements, %li kB\n", n,\r
+ //(((R.n+W-1)/W)*sizeof(int)/1024));\r
+ R.tree = (int*) malloc (((R.n+W-1)/W)*sizeof(int));\r
+ clearBit(R.tree,0); // clear all\r
+ return R;\r
+ }\r
+\r
+void freeResults (results R)\r
+\r
+ { free (R.tree);\r
+ }\r
+\r
+ // to map 1..n to the bottom of the tree when n is not a power of 2\r
+static int conv (int p, int n, int lgn)\r
+\r
+ { int t = n+1-(1<<lgn);\r
+ return (p < t) ? p : (p<<1)-t;\r
+ }\r
+\r
+static int unconv (int p, int n, int lgn)\r
+\r
+ { int t = n+1-(1<<lgn);\r
+ return (p < t) ? p : (p+t)>>1;\r
+ }\r
+\r
+int readResult (results R, int p) // returns 0 or 1\r
+\r
+ { int n = R.n;\r
+ int pos = 0;\r
+ int pot = R.lgn;\r
+ p = conv(p,n,pot);\r
+ do { if (!getBit(R.tree,pos)) return 0;\r
+ pot--;\r
+ pos = (pos<<1)+1+(p>>pot);\r
+ p &= ~(1<<pot);\r
+ }\r
+ while (pos < n);\r
+ return 1;\r
+ }\r
+\r
+void setResult (results R, int p)\r
+\r
+ { int n = R.n;\r
+ int pos = 0;\r
+ int npos;\r
+ int pot = R.lgn;\r
+ p = conv(p,n,pot);\r
+ do { npos = (pos<<1)+1;\r
+ if (!getBit(R.tree,pos))\r
+ { setBit(R.tree,pos);\r
+ if (npos < n) \r
+ { clearBit(R.tree,npos);\r
+ clearBit(R.tree,npos+1);\r
+ }\r
+ }\r
+ pot--;\r
+ pos = npos+(p>>pot);\r
+ p &= ~(1<<pot);\r
+ }\r
+ while (pos < n);\r
+ }\r
+\r
+ // returns final value of bit at pos\r
+ \r
+static int clearRangeLeft (int *tree, int p1, int n, int pos, int pot)\r
+\r
+ { int npos;\r
+ int bit;\r
+ if (!getBit(tree,pos)) return 0; // range already zeroed\r
+ p1 &= ~(1<<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<<1)+1;\r
+ if ((p1>>pot) == 0) // go left, clear right\r
+ { clearBit(tree,npos+1);\r
+ bit = clearRangeLeft(tree,p1,n,npos,pot);\r
+ } \r
+ else // go right\r
+ { bit = clearRangeLeft(tree,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
+static int clearRangeRight (int *tree, int p2, int n, int pos, int pot)\r
+\r
+ { int npos;\r
+ int bit;\r
+ if (!getBit(tree,pos)) return 0; // range already zeroed\r
+ p2 &= ~(1<<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<<1)+1;\r
+ if ((p2>>pot) == 1) // go right, clear left\r
+ { clearBit(tree,npos);\r
+ bit = clearRangeRight(tree,p2,n,npos+1,pot);\r
+ } \r
+ else // go left\r
+ { bit = clearRangeRight(tree,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
+static int clearBoth (int *tree, int n, int p1, int p2, int pos, int pot)\r
+\r
+ { int npos,npos1,npos2;\r
+ int bit;\r
+ if (!getBit(tree,pos)) return 0; // range is already zeroed\r
+ npos = (pos<<1)+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 (tree,n,p1&~(1<<pot),p2&~(1<<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(tree,p1,n,npos1,pot); \r
+ bit |= clearRangeRight(tree,p2,n,npos2,pot);\r
+ }\r
+ if (!bit) clearBit(tree,pos);\r
+ return bit;\r
+ }\r
+\r
+void clearRange (results R, int p1, int p2)\r
+\r
+ { if ((p2+1)<<1 > R.n) \r
+ clearRangeLeft(R.tree,conv(p1,R.n,R.lgn),R.n,0,R.lgn);\r
+ else clearBoth(R.tree,R.n,conv(p1,R.n,R.lgn),conv(p2+1,R.n,R.lgn),0,R.lgn);\r
+ }\r
+\r
+static int nextSmallest (int *tree, int n, int pos, int pot)\r
+\r
+ { int p = 0;\r
+ while (1)\r
+ { pot--;\r
+ pos = (pos<<1)+1;\r
+ if (pos >= n) return p;\r
+ if (!getBit(tree,pos)) { pos++; p |= (1<<pot); }\r
+ }\r
+ }\r
+\r
+static int nextLarger (int *tree, int n, int p, int pos, int pot)\r
+\r
+ { int answ;\r
+ if (!getBit(tree,pos)) return -1; // no answer\r
+ pos = (pos<<1)+1;\r
+ if (pos >= n) return 0; // when n is not a power of 2, missing leaves\r
+ pot--;\r
+ if ((p>>pot) == 0) // p goes left\r
+ { answ = nextLarger(tree,n,p&~(1<<pot),pos,pot);\r
+ if (answ != -1) return answ;\r
+ if (!getBit(tree,pos+1)) return -1; // no answer\r
+ return (1<<pot) | nextSmallest(tree,n,pos+1,pot);\r
+ }\r
+ else \r
+ { answ = nextLarger(tree,n,p&~(1<<pot),pos+1,pot);\r
+ if (answ != -1) return (1<<pot) | answ;\r
+ return -1;\r
+ }\r
+ }\r
+\r
+int nextResult (results R, int p) // returns pos of next(p) or -1 if none\r
+\r
+ { int answ;\r
+ if (((p+1)<<1) > R.n) return -1; // next(last), p+1 out of bounds\r
+ answ = nextLarger(R.tree,R.n,conv(p+1,R.n,R.lgn),0,R.lgn);\r
+ return (answ == -1) ? -1 : unconv(answ,R.n,R.lgn);\r
+ }\r
+\r
+// Naively implemented by kim\r
+\r
+unsigned int countResult(results R) {\r
+ unsigned int result = -1;\r
+ int i = 0;\r
+ while ( i != -1 && i < R.n) {\r
+ result ++; \r
+ i = unconv(nextLarger(R.tree,R.n,conv(i+1,R.n,R.lgn),0,R.lgn),R.n,R.lgn);\r
+ };\r
+ return result;\r
+ \r
+}\r
+\r
+\r
+static void prnspace (int k)\r
+\r
+ { while (k--) putchar(' ');\r
+ }\r
+\r
+void printTree (results R)\r
+\r
+ { int n = R.n;\r
+ int pot = lg(R.n);\r
+ int pos = 0;\r
+ int num = 1;\r
+ while (pot)\r
+ { int lnum = num;\r
+ prnspace((1<<(pot-1))-1);\r
+ while (lnum-- && n--)\r
+ { putchar (getBit(R.tree,pos) ? '1' : '0');\r
+ pos++;\r
+ prnspace((1<<pot)-1); \r
+ }\r
+ putchar('\n');\r
+ num <<= 1;\r
+ pot--;\r
+ }\r
+ }\r
+\r