12 GapEncode::GapEncode(ulong *B, ulong u, bool freeB = false)
14 ulong i, lastIndex, *bitRun, *runLength;
16 this->numberOfRuns = 0;
17 bitRun = new ulong[u/W + 1];
18 for (i = 0; i < u/W + 1; i ++)
21 // Collect the runs of 1- or 0-bits
25 for (i = 0; i < u; i ++)
26 if (Tools::GetField(B, 1, i) != curBit)
29 totalLength += i - lastIndex;
30 else if (Tools::GetField(B, 1, i))
31 Tools::SetField(bitRun, 1, i, 1);
34 curBit = Tools::GetField(B, 1, i);
36 // Handle the last run
38 totalLength += i - lastIndex;
40 runLength = new ulong[totalLength/W + 1];
41 for (i = 0; i < totalLength/W + 1; i ++)
44 // Calculate run lengths
48 for (i = 0; i < u; i ++)
49 if (Tools::GetField(B, 1, i) != curBit)
53 totalLength += i - lastIndex;
54 Tools::SetField(runLength, 1, totalLength - 1, 1);
57 curBit = Tools::GetField(B, 1, i);
59 // Handle the last run
62 totalLength += i - lastIndex;
63 Tools::SetField(runLength, 1, totalLength - 1, 1);
66 // Construct BSGAP structures
67 this->bitRun = new BSGAP(bitRun, u, true, 0);
68 numberOfRuns = this->bitRun->rank(u-1);
69 this->runLength = new BSGAP(runLength, totalLength, true, 0);
75 GapEncode::~GapEncode()
77 // Free BSGAP structures
82 ulong GapEncode::rank(ulong i)
84 ulong pred, r = bitRun->rank(i);
87 pred = bitRun->select(r);
89 ulong bitsBeforeRun = 0;
91 bitsBeforeRun = runLength->select(r - 1) + 1;
93 ulong bitsInRun = runLength->select(r) + 1 - bitsBeforeRun;
94 if (i - pred >= bitsInRun)
95 return bitsBeforeRun + bitsInRun;
97 return bitsBeforeRun + i - pred + 1;
100 ulong GapEncode::rank0(ulong i)
102 return i - rank(i) + 1;
105 ulong GapEncode::select(ulong i)
107 throw logic_error("GapEncode::select() is not implemented");
111 ulong GapEncode::select0(ulong i)
113 throw logic_error("GapEncode::select0() is not implemented");
114 return 0; // To be implemented...
118 * Saving data fields:
119 ulong u; // Universe size, number of bits in B
120 ulong numberOfRuns; // Number of 1-bit runs
121 BSGAP *bitRun, // Contains 1-bit at the start of each 1-bit-run
122 *runLength; // Contains run lengths for each 1-bit-run
123 ulong totalLength; // Total length of runs
125 void GapEncode::Save(FILE *file) const
127 if (std::fwrite(&(this->u), sizeof(ulong), 1, file) != 1)
128 throw std::runtime_error("GapEncode::Save(): file write error (u).");
129 if (std::fwrite(&(this->numberOfRuns), sizeof(ulong), 1, file) != 1)
130 throw std::runtime_error("GapEncode::Save(): file write error (numberOfRuns).");
133 runLength->Save(file);
135 if (std::fwrite(&(this->totalLength), sizeof(ulong), 1, file) != 1)
136 throw std::runtime_error("GapEncode::Save(): file write error (totalLength).");
139 GapEncode::GapEncode(FILE *file)
141 if (std::fread(&(this->u), sizeof(ulong), 1, file) != 1)
142 throw std::runtime_error("GapEncode::Load(): file read error (u).");
143 if (std::fread(&(this->numberOfRuns), sizeof(ulong), 1, file) != 1)
144 throw std::runtime_error("GapEncode::Load(): file read error (numberOfRuns).");
146 bitRun = new BSGAP(file);
147 runLength = new BSGAP(file);
149 if (std::fread(&(this->totalLength), sizeof(ulong), 1, file) != 1)
150 throw std::runtime_error("GapEncode::Load(): file read error (totalLength).");