data=bitarray;
this->owner = owner;
this->n=n; // length of bitarray in bits
- b = W; // b is a word
- s=b*superFactor;
ulong aux=(n+1)%W;
if (aux != 0)
integers = (n+1)/W+1;
}
BitRank::~BitRank() {
- delete [] Rs;
+ delete Rs;
delete [] Rb;
if (owner) delete [] data;
}
void BitRank::BuildRank()
{
ulong num_sblock = n/s;
- ulong num_block = n/b;
- Rs = new ulong[num_sblock+1];//+1 we add the 0 pos
+ ulong num_block = n/W;
+ Rs = new BlockArray(num_sblock+1, Tools::CeilLog2(n));//+1 we add the 0 pos
Rb = new uchar[num_block+1];//+1 we add the 0 pos
ulong j;
- Rs[0] = 0lu;
+ (*Rs)[0] = 0lu;
for (j=1;j<=num_sblock;j++)
{
- Rs[j]=BuildRankSub((j-1)*superFactor,superFactor)+Rs[j-1];
+ (*Rs)[j]=BuildRankSub((j-1)*superFactor,superFactor)+(*Rs)[j-1];
}
Rb[0]=0;
//this rank ask from 0 to n-1
ulong BitRank::rank(ulong i) {
++i; // the following gives sum of 1s before i
- return Rs[i>>8]+Rb[i>>wordShift]
+ return (*Rs)[i>>8]+Rb[i>>wordShift]
+popcount(data[i >> wordShift] & ((1lu << (i & Wminusone))-1));
}
ulong l=0, r=n/s;
ulong mid=(l+r)/2;
- ulong rankmid = Rs[mid];
+ ulong rankmid = (*Rs)[mid];
while (l<=r) {
if (rankmid<x)
l = mid+1;
else
r = mid-1;
mid = (l+r)/2;
- rankmid = Rs[mid];
+ rankmid = (*Rs)[mid];
}
//sequential search using popcount over a int
ulong left;
ones = popcount(j);
}
//sequential search using popcount over a char
- left=left*b;
+ left=left*W;
rankmid = popcount8(j);
if (rankmid < x) {
j=j>>8;
ulong l=0, r=n/s;
ulong mid=(l+r)/2;
- ulong rankmid = mid * s - Rs[mid];
+ ulong rankmid = mid * s - (*Rs)[mid];
while (l<=r) {
if (rankmid<x)
l = mid+1;
else
r = mid-1;
mid = (l+r)/2;
- rankmid = mid * s - Rs[mid];
+ rankmid = mid * s - (*Rs)[mid];
}
//sequential search using popcount over a int
}
//sequential search using popcount over a char
- left=left*b;
+ left=left*W;
rankmid = 8 - popcount8(j);
if (rankmid < x) {
j=j>>8;
ulong BitRank::NumberOfBits() {
return n;
}
+
+/**
+ * Saving data fields:
+
+ ulong n;
+ ulong *data; //here is the bit-arra
+ */
+void BitRank::Save(FILE *file)
+{
+ if (std::fwrite(&(this->n), sizeof(ulong), 1, file) != 1)
+ throw std::runtime_error("BitRank::Save(): file write error (n).");
+
+ for (ulong offset = 0; offset < integers; ++offset)
+ if (std::fwrite(this->data + offset, sizeof(ulong), 1, file) != 1)
+ throw std::runtime_error("BitRank::Save(): file write error (data).");
+}
+
+BitRank::BitRank(FILE *file)
+{
+ owner = 1;
+ if (std::fread(&(this->n), sizeof(ulong), 1, file) != 1)
+ throw std::runtime_error("BitRank::Load(): file read error (n).");
+
+ ulong aux=(n+1)%W;
+ if (aux != 0)
+ integers = (n+1)/W+1;
+ else
+ integers = (n+1)/W;
+
+ data = new ulong[integers];
+ for (ulong offset = 0; offset < integers; ++offset)
+ if (std::fread(this->data + offset, sizeof(ulong), 1, file) != 1)
+ throw std::runtime_error("BitRank::Load(): file read error (data).");
+
+ BuildRank();
+}