+++ /dev/null
-/**
- * Gap encoding scheme
- * Niko Välimäki
- *
- */
-
-#include "GapEncode.h"
-#include <stdexcept>
-using namespace std;
-
-
-GapEncode::GapEncode(ulong *B, ulong u, bool freeB = false)
-{
- ulong i, lastIndex, *bitRun, *runLength;
- this->u = u;
- this->numberOfRuns = 0;
- bitRun = new ulong[u/W + 1];
- for (i = 0; i < u/W + 1; i ++)
- bitRun[i] = 0;
-
- // Collect the runs of 1- or 0-bits
- totalLength = 0;
- uchar curBit = 0xFF;
- lastIndex = 0;
- for (i = 0; i < u; i ++)
- if (Tools::GetField(B, 1, i) != curBit)
- {
- if (curBit == 1)
- totalLength += i - lastIndex;
- else if (Tools::GetField(B, 1, i))
- Tools::SetField(bitRun, 1, i, 1);
-
- lastIndex = i;
- curBit = Tools::GetField(B, 1, i);
- }
- // Handle the last run
- if (curBit == 1)
- totalLength += i - lastIndex;
-
- runLength = new ulong[totalLength/W + 1];
- for (i = 0; i < totalLength/W + 1; i ++)
- runLength[i] = 0;
-
- // Calculate run lengths
- totalLength = 0;
- curBit = 0xFF;
- lastIndex = 0;
- for (i = 0; i < u; i ++)
- if (Tools::GetField(B, 1, i) != curBit)
- {
- if (curBit == 1)
- {
- totalLength += i - lastIndex;
- Tools::SetField(runLength, 1, totalLength - 1, 1);
- }
- lastIndex = i;
- curBit = Tools::GetField(B, 1, i);
- }
- // Handle the last run
- if (curBit == 1)
- {
- totalLength += i - lastIndex;
- Tools::SetField(runLength, 1, totalLength - 1, 1);
- }
-
- // Construct BSGAP structures
- this->bitRun = new BSGAP(bitRun, u, true, 0);
- numberOfRuns = this->bitRun->rank(u-1);
- this->runLength = new BSGAP(runLength, totalLength, true, 0);
-
- if (freeB)
- delete [] B;
-}
-
-GapEncode::~GapEncode()
-{
- // Free BSGAP structures
- delete bitRun;
- delete runLength;
-}
-
-ulong GapEncode::rank(ulong i)
-{
- ulong pred, r = bitRun->rank(i);
- if (r == 0)
- return 0;
- pred = bitRun->select(r);
-
- ulong bitsBeforeRun = 0;
- if (r > 1)
- bitsBeforeRun = runLength->select(r - 1) + 1;
-
- ulong bitsInRun = runLength->select(r) + 1 - bitsBeforeRun;
- if (i - pred >= bitsInRun)
- return bitsBeforeRun + bitsInRun;
-
- return bitsBeforeRun + i - pred + 1;
-}
-
-ulong GapEncode::rank0(ulong i)
-{
- return i - rank(i) + 1;
-}
-
-ulong GapEncode::select(ulong i)
-{
- throw logic_error("GapEncode::select() is not implemented");
- return 0;
-}
-
-ulong GapEncode::select0(ulong i)
-{
- throw logic_error("GapEncode::select0() is not implemented");
- return 0; // To be implemented...
-}
-
-/**
- * Saving data fields:
- ulong u; // Universe size, number of bits in B
- ulong numberOfRuns; // Number of 1-bit runs
- BSGAP *bitRun, // Contains 1-bit at the start of each 1-bit-run
- *runLength; // Contains run lengths for each 1-bit-run
- ulong totalLength; // Total length of runs
-*/
-void GapEncode::Save(FILE *file) const
-{
- if (std::fwrite(&(this->u), sizeof(ulong), 1, file) != 1)
- throw std::runtime_error("GapEncode::Save(): file write error (u).");
- if (std::fwrite(&(this->numberOfRuns), sizeof(ulong), 1, file) != 1)
- throw std::runtime_error("GapEncode::Save(): file write error (numberOfRuns).");
-
- bitRun->Save(file);
- runLength->Save(file);
-
- if (std::fwrite(&(this->totalLength), sizeof(ulong), 1, file) != 1)
- throw std::runtime_error("GapEncode::Save(): file write error (totalLength).");
-}
-
-GapEncode::GapEncode(FILE *file)
-{
- if (std::fread(&(this->u), sizeof(ulong), 1, file) != 1)
- throw std::runtime_error("GapEncode::Load(): file read error (u).");
- if (std::fread(&(this->numberOfRuns), sizeof(ulong), 1, file) != 1)
- throw std::runtime_error("GapEncode::Load(): file read error (numberOfRuns).");
-
- bitRun = new BSGAP(file);
- runLength = new BSGAP(file);
-
- if (std::fread(&(this->totalLength), sizeof(ulong), 1, file) != 1)
- throw std::runtime_error("GapEncode::Load(): file read error (totalLength).");
-}