static_bitsequence_brw32::static_bitsequence_brw32(){
data=NULL;
- this->owner = true;
+// this->owner = true;
this->n=0;
this->factor=0;
}
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;
static_bitsequence_brw32::~static_bitsequence_brw32() {
delete [] Rs;
- if (owner) delete [] data;
+ delete [] data;
}
//Metodo que realiza la busqueda d
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;
}
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) {
}
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;
+}