* samplerate == number of keys in each gap encoded binary search tree
* default value is log^2 n where n is the number of keys.
*/
-BSGAP::BSGAP(ulong *B, ulong u, bool freeB, ulong sampleRate)
+BSGAP::BSGAP(ulong *B, ulong u_, bool freeB, ulong sampleRate)
+ : u(u_), n(0), topCount(0), bitsInP(0), P(0), b(0), offsetA(0), firstKeyA(0)
{
- this->u = u;
- this->n = 0;
- this->P = 0;
- this->offsetA = 0;
- this->firstKeyA = 0;
- this->topCount = 0;
-
// Count keys
for (ulong i = 0; i < u; i ++)
if (Tools::GetField(B, 1, i))
if (n == 0) // Sanity check
{
- if (freeB && B)
+ if (freeB)
delete [] B;
return;
ulong **tempP = new ulong * [n / b + 1];
ulong *bitsInBSD = new ulong [n / b + 1];
ulong totalBits = 0;
- this->firstKeyA = new BlockArray(n/b + 1, Tools::CeilLog2(this->u));
+ // Number of nodes:
+ this->topCount = n%b ? n/b + 1: n/b;
+ this->firstKeyA = new BlockArray(topCount, Tools::CeilLog2(this->u));
for (ulong i = 0; i < n/b; i ++)
{
if (i == n/b - 1 && n%b == 0)
lastKey = u;
- tempP[i] = GetSubtree(B, firstKey, firstKey, lastKey, b, true, bitsInBSD[i]); // FIXME: left of right subtree?
+ tempP[i] = GetSubtree(B, firstKey, firstKey, lastKey, b, true, bitsInBSD[i]);
totalBits += bitsInBSD[i];
(*firstKeyA)[i] = firstKey;
while (!Tools::GetField(B, 1, firstKey))
firstKey ++;
- tempP[n/b] = GetSubtree(B, firstKey, firstKey, u, n - (n/b) * b, true, bitsInBSD[n/b]); // FIXME: left of right subtree?
+ tempP[n/b] = GetSubtree(B, firstKey, firstKey, u, n - (n/b) * b, true, bitsInBSD[n/b]);
totalBits += bitsInBSD[n/b];
(*firstKeyA)[n/b] = firstKey;
}
- // Number of nodes:
- this->topCount = n%b ? n/b + 1: n/b;
-
// Catenate binary trees into one bitvector
this->P = new ulong[totalBits/W + 1];
+ for (ulong i = 0; i < totalBits/W + 1; ++i)
+ P[i] = 0;
this->bitsInP = totalBits;
ulong offset = 0;
for (ulong i = 0; i < this->topCount ; ++i)
// bits is the sum of keyBits, jumpBits, leftBits and rightBits
bits = keyBits + jumpBits + leftBits + rightBits;
ulong *output = new ulong[bits / W + 1];
+ for (ulong i = 0; i < bits/W+1; ++i)
+ output[i] = 0;
/**
* Write "output"
if (std::fwrite(&(this->n), sizeof(ulong), 1, file) != 1)
throw std::runtime_error("BSGAP::Save(): file write error (n).");
+ if (n == 0)
+ return; // Done.
+
if (std::fwrite(&(this->topCount), sizeof(ulong), 1, file) != 1)
throw std::runtime_error("BSGAP::Save(): file write error (topCount).");
for (ulong offset = 0; offset < bitsInP/W+1; offset ++)
{
- if (std::fwrite(this->P+offset, sizeof(ulong), 1, file) != 1)
+ if (std::fwrite((this->P)+offset, sizeof(ulong), 1, file) != 1)
throw std::runtime_error("BSGAP::Save(): file write error (P).");
- }
+ }
if (std::fwrite(&(this->b), sizeof(unsigned), 1, file) != 1)
throw std::runtime_error("BSGAP::Save(): file write error (b).");
* Load from file
*/
BSGAP::BSGAP(FILE *file)
+ : u(0), n(0), topCount(0), bitsInP(0), P(0), b(0), offsetA(0), firstKeyA(0)
{
if (std::fread(&(this->u), sizeof(ulong), 1, file) != 1)
throw std::runtime_error("BSGAP::Load(): file read error (u).");
if (std::fread(&(this->n), sizeof(ulong), 1, file) != 1)
throw std::runtime_error("BSGAP::Load(): file read error (n).");
+ if (n == 0)
+ return; // Done.
+
if (std::fread(&(this->topCount), sizeof(ulong), 1, file) != 1)
throw std::runtime_error("BSGAP::Load(): file read error (topCount).");