X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=src%2Fresults.c;fp=src%2Fresults.c;h=4e7b4ec0b62751dbeef8e4f8dd6cadfdcb321996;hb=4b52da1a20a4fe031930bb96d2ca46bec06dc529;hp=0000000000000000000000000000000000000000;hpb=a223af3254fb51c279cfbccdc18c59484fdca74e;p=SXSI%2Fxpathcomp.git

diff --git a/src/results.c b/src/results.c
new file mode 100644
index 0000000..4e7b4ec
--- /dev/null
+++ b/src/results.c
@@ -0,0 +1,247 @@
+
+#include <stdio.h> 
+#include <stdlib.h> 
+#include "results.h"
+
+#define W (8*sizeof(int))
+#define logW 5 // code checks = lg(W)-1
+#define divW(p) ((p)>>logW)
+#define modW(p) ((p)&(W-1))
+
+#define setBit(arr,pos) ((arr)[divW(pos)] |= 1<<modW(pos))
+#define clearBit(arr,pos) ((arr)[divW(pos)] &= ~(1<<modW(pos)))
+#define getBit(arr,pos) ((arr)[divW(pos)] & (1<<modW(pos))) // 0 or !=0
+
+static int lg (int n)
+
+  { int answ=0;
+    while (n) { n>>=1; answ++; }
+    return answ;
+  }
+
+results createResults (int n)
+
+  { results R;
+    if (logW != lg(W)-1)
+       { fprintf(stderr,"Error, redefine logW as %i and recompile\n",lg(W)-1);
+	 exit(1);
+       }
+
+    R.n = 2*n-1;
+    R.lgn = lg(n);
+    //fprintf(stderr,"Size of the result set : %i elements, %li kB\n", n,
+    //(((R.n+W-1)/W)*sizeof(int)/1024));
+    R.tree = (int*) malloc (((R.n+W-1)/W)*sizeof(int));
+    clearBit(R.tree,0); // clear all
+    return R;
+  }
+
+void freeResults (results R)
+
+  { free (R.tree);
+  }
+
+	// to map 1..n to the bottom of the tree when n is not a power of 2
+static int conv (int p, int n, int lgn)
+
+  { int t = n+1-(1<<lgn);
+    return (p < t) ? p : (p<<1)-t;
+  }
+
+static int unconv (int p, int n, int lgn)
+
+  { int t = n+1-(1<<lgn);
+    return (p < t) ? p : (p+t)>>1;
+  }
+
+int readResult (results R, int p) // returns 0 or 1
+
+  { int n = R.n;
+    int pos = 0;
+    int pot = R.lgn;
+    p = conv(p,n,pot);
+    do { if (!getBit(R.tree,pos)) return 0;
+	  pot--;
+	  pos = (pos<<1)+1+(p>>pot);
+	  p &= ~(1<<pot);
+	}
+    while (pos < n);
+    return 1;
+  }
+
+void setResult (results R, int p)
+
+  { int n = R.n;
+    int pos = 0;
+    int npos;
+    int pot = R.lgn;
+    p = conv(p,n,pot);
+    do { npos = (pos<<1)+1;
+	 if (!getBit(R.tree,pos))
+	    { setBit(R.tree,pos);
+	      if (npos < n) 
+		 { clearBit(R.tree,npos);
+	           clearBit(R.tree,npos+1);
+		 }
+	    }
+	  pot--;
+	  pos = npos+(p>>pot);
+	  p &= ~(1<<pot);
+	}
+    while (pos < n);
+  }
+
+	// returns final value of bit at pos
+	
+static int clearRangeLeft (int *tree, int p1, int n, int pos, int pot)
+
+  { int npos;
+    int bit;
+    if (!getBit(tree,pos)) return 0; // range already zeroed
+    p1 &= ~(1<<pot);
+    if (p1 == 0) // full range to clear
+       { clearBit(tree,pos); return 0; }
+	// p1 != 0, there must be children
+    pot--;
+    npos = (pos<<1)+1;
+    if ((p1>>pot) == 0) // go left, clear right
+       { clearBit(tree,npos+1);
+	 bit = clearRangeLeft(tree,p1,n,npos,pot);
+       } 
+    else // go right
+       { bit = clearRangeLeft(tree,p1,n,npos+1,pot);
+	 if (!bit) bit = getBit(tree,npos);
+       }
+    if (!bit) clearBit(tree,pos);
+    return bit;
+  }
+
+static int clearRangeRight (int *tree, int p2, int n, int pos, int pot)
+
+  { int npos;
+    int bit;
+    if (!getBit(tree,pos)) return 0; // range already zeroed
+    p2 &= ~(1<<pot);
+    if (p2 == 0) return 1; // empty range to clear, and bit is 1 for sure
+	// p2 != 0, there must be children
+    pot--;
+    npos = (pos<<1)+1;
+    if ((p2>>pot) == 1) // go right, clear left
+       { clearBit(tree,npos);
+	 bit = clearRangeRight(tree,p2,n,npos+1,pot);
+       } 
+    else // go left
+       { bit = clearRangeRight(tree,p2,n,npos,pot);
+	 if (!bit) bit = getBit(tree,npos+1);
+       }
+    if (!bit) clearBit(tree,pos);
+    return bit;
+  }
+
+static int clearBoth (int *tree, int n, int p1, int p2, int pos, int pot)
+
+  { int npos,npos1,npos2;
+    int bit;
+    if (!getBit(tree,pos)) return 0; // range is already zeroed
+    npos = (pos<<1)+1;
+	// children must exist while the path is unique, as p1<p2
+    pot--;
+    npos1 = npos+(p1>>pot);
+    npos2 = npos+(p2>>pot);
+    if (npos1 == npos2) // we're inside npos1=npos2
+       { bit = clearBoth (tree,n,p1&~(1<<pot),p2&~(1<<pot),npos1,pot);
+	 bit |= getBit(tree,npos+1-(p1>>pot)); // the other
+       }
+     else  // p1 and p2 take different paths here
+	{ bit  = clearRangeLeft(tree,p1,n,npos1,pot); 
+          bit |= clearRangeRight(tree,p2,n,npos2,pot);
+	}
+     if (!bit) clearBit(tree,pos);
+     return bit;
+  }
+
+void clearRange (results R, int p1, int p2)
+
+  { if ((p2+1)<<1 > R.n) 
+         clearRangeLeft(R.tree,conv(p1,R.n,R.lgn),R.n,0,R.lgn);
+    else clearBoth(R.tree,R.n,conv(p1,R.n,R.lgn),conv(p2+1,R.n,R.lgn),0,R.lgn);
+  }
+
+static int nextSmallest (int *tree, int n, int pos, int pot)
+
+  { int p = 0;
+    while (1)
+       { pot--;
+	 pos = (pos<<1)+1;
+	 if (pos >= n) return p;
+	 if (!getBit(tree,pos)) { pos++; p |= (1<<pot); }
+       }
+  }
+
+static int nextLarger (int *tree, int n, int p, int pos, int pot)
+
+  { int answ;
+    if (!getBit(tree,pos)) return -1; // no answer
+    pos = (pos<<1)+1;
+    if (pos >= n) return 0; // when n is not a power of 2, missing leaves
+    pot--;
+    if ((p>>pot) == 0) // p goes left
+       { answ = nextLarger(tree,n,p&~(1<<pot),pos,pot);
+	 if (answ != -1) return answ;
+         if (!getBit(tree,pos+1)) return -1; // no answer
+	 return (1<<pot) | nextSmallest(tree,n,pos+1,pot);
+       }
+    else 
+       { answ = nextLarger(tree,n,p&~(1<<pot),pos+1,pot);
+         if (answ != -1) return (1<<pot) | answ;
+         return -1;
+       }
+  }
+
+int nextResult (results R, int p) // returns pos of next(p) or -1 if none
+
+  { int answ;
+    if (((p+1)<<1) > R.n) return -1; // next(last), p+1 out of bounds
+    answ = nextLarger(R.tree,R.n,conv(p+1,R.n,R.lgn),0,R.lgn);
+    return (answ == -1) ? -1 : unconv(answ,R.n,R.lgn);
+  }
+
+// Naively implemented by kim
+
+unsigned int countResult(results R) {
+  unsigned int result = -1;
+  int i = 0;
+  while ( i != -1 && i < R.n) {
+    result ++; 
+    i = unconv(nextLarger(R.tree,R.n,conv(i+1,R.n,R.lgn),0,R.lgn),R.n,R.lgn);
+  };
+  return result;
+   
+}
+
+
+static void prnspace (int k)
+
+  { while (k--) putchar(' ');
+  }
+
+void printTree (results R)
+
+  { int n = R.n;
+    int pot = lg(R.n);
+    int pos = 0;
+    int num = 1;
+    while (pot)
+      { int lnum = num;
+        prnspace((1<<(pot-1))-1);
+	while (lnum-- && n--)
+	    { putchar (getBit(R.tree,pos) ? '1' : '0');
+	      pos++;
+	      prnspace((1<<pot)-1); 
+	    }
+	putchar('\n');
+	num <<= 1;
+	pot--;
+      }
+  }
+