New (faster) representation for tags added; faster construction of parentheses

[SXSI/XMLTree.git] / libcds / src / static_bitsequence / static_bitsequence_brw32.cpp

diff --git a/libcds/src/static_bitsequence/static_bitsequence_brw32.cpp b/libcds/src/static_bitsequence/static_bitsequence_brw32.cpp
index 9bc1313..2ca4eed 100644 (file)
--- a/libcds/src/static_bitsequence/static_bitsequence_brw32.cpp
+++ b/libcds/src/static_bitsequence/static_bitsequence_brw32.cpp
@@ -38,7 +38,7 @@
 
 static_bitsequence_brw32::static_bitsequence_brw32(){
   data=NULL;
-  this->owner = true;
+//  this->owner = true;
   this->n=0;
   this->factor=0;
 }
@@ -54,7 +54,7 @@ static_bitsequence_brw32::static_bitsequence_brw32( uint *bitarray, uint _n, uin
     data[i] = bitarray[i];
   for(uint i=uint_len(_n,1);i<_n/W+1;i++)
     data[i] = 0;
-  this->owner = true;
+  //this->owner = true;
   this->n=_n;
   uint lgn=bits(n-1);
   this->factor=_factor;
@@ -70,7 +70,7 @@ static_bitsequence_brw32::static_bitsequence_brw32( uint *bitarray, uint _n, uin
 
 static_bitsequence_brw32::~static_bitsequence_brw32() {
   delete [] Rs;
-  if (owner) delete [] data;
+  delete [] data;
 }
 
 //Metodo que realiza la busqueda d
@@ -142,7 +142,6 @@ static_bitsequence_brw32 * static_bitsequence_brw32::load(FILE *f) {
   ret->data = new uint[ret->n/W+1];
   if (!ret->data) return NULL;
   if (fread (ret->data,sizeof(uint),ret->n/W+1,f) != ret->n/W+1) return NULL;
-  ret->owner = true;
   ret->Rs= new uint[ret->n/ret->s+1];
   if (!ret->Rs) return NULL;
   if (fread (ret->Rs,sizeof(uint),ret->n/ret->s+1,f) != ret->n/ret->s+1) return NULL;
@@ -152,15 +151,15 @@ static_bitsequence_brw32 * static_bitsequence_brw32::load(FILE *f) {
 }
 
 uint static_bitsequence_brw32::SpaceRequirementInBits() {
-  return (owner?n:0)+(n/s)*sizeof(uint)*8 +sizeof(static_bitsequence_brw32)*8; 
+  return uint_len(n,1)*sizeof(uint)*8+(n/s)*sizeof(uint)*8 +sizeof(static_bitsequence_brw32)*8; 
 }
 
 uint static_bitsequence_brw32::size() {
-  return SpaceRequirementInBits()/8;
+  return sizeof(static_bitsequence_brw32)+SpaceRequirementInBits()/8;
 }
 
 uint static_bitsequence_brw32::SpaceRequirement() {
-  return (owner?n:0)/8+(n/s)*sizeof(uint)+sizeof(static_bitsequence_brw32); 
+  return n/8+(n/s)*sizeof(uint)+sizeof(static_bitsequence_brw32); 
 }
 
 uint static_bitsequence_brw32::prev2(uint start) {
@@ -293,3 +292,67 @@ uint static_bitsequence_brw32::select1(uint x) {
   }
   return left-1;
 }
+
+uint static_bitsequence_brw32::select0(uint x) {
+  // returns i such that x=rank_0(i) && rank_0(i-1)<x or n if that i not exist
+  // first binary search over first level rank structure
+  // then sequential search using popcount over a int
+  // then sequential search using popcount over a char
+  // then sequential search bit a bit
+
+  //binary search over first level rank structure
+  if(x==0) return 0;
+  uint l=0, r=n/s;
+  uint mid=(l+r)/2;
+  uint rankmid = mid*factor*W-Rs[mid];
+  while (l<=r) {
+    if (rankmid<x)
+      l = mid+1;
+    else
+      r = mid-1;
+    mid = (l+r)/2;
+    rankmid = mid*factor*W-Rs[mid];
+  }
+  //sequential search using popcount over a int
+  uint left;
+  left=mid*factor;
+  x-=rankmid;
+  uint j=data[left];
+  uint zeros = W-popcount(j);
+  while (zeros < x) {
+    x-=zeros;left++;
+    if (left > integers) return n;
+    j = data[left];
+    zeros = W-popcount(j);
+  }
+  //sequential search using popcount over a char
+  left=left*b;
+  rankmid = 8-popcount8(j);
+  if (rankmid < x) {
+    j=j>>8;
+    x-=rankmid;
+    left+=8;
+    rankmid = 8-popcount8(j);
+    if (rankmid < x) {
+      j=j>>8;
+      x-=rankmid;
+      left+=8;
+      rankmid = 8-popcount8(j);
+      if (rankmid < x) {
+        j=j>>8;
+        x-=rankmid;
+        left+=8;
+      }
+    }
+  }
+
+  // then sequential search bit a bit
+  while (x>0) {
+    if  (j%2 == 0 ) x--;
+    j=j>>1;
+    left++;
+  }
+  left--;
+  if (left > n)  return n;
+  else return left;
+}