12 #include "BlockArray.h"
18 GapEncode(ulong *, ulong, bool);
22 void Save(FILE *) const;
24 ulong rankrun(ulong i) {return bitRun->rank(i);};
25 ulong selectrun(ulong i) {return bitRun->select(i);};
28 ulong select0(ulong); // Not implemented, yet...
29 bool IsBitSet(ulong i) {
30 ulong r = bitRun->rank(i);
33 ulong pred = bitRun->select(r);
35 ulong bitsBeforeRun = 0;
37 bitsBeforeRun = runLength->select(r - 1) + 1;
39 ulong bitsInRun = runLength->select(r) + 1 - bitsBeforeRun;
40 if (i - pred >= bitsInRun)
47 * Returns also the rank_1 of given position i
49 bool IsBitSet(ulong i, ulong *rank) {
51 ulong r = bitRun->rank(i);
54 ulong pred = bitRun->select(r);
56 ulong bitsBeforeRun = 0;
58 bitsBeforeRun = runLength->select(r - 1) + 1;
60 ulong bitsInRun = runLength->select(r) + 1 - bitsBeforeRun;
61 if (i - pred >= bitsInRun)
63 *rank = bitsBeforeRun + bitsInRun;
67 *rank = bitsBeforeRun + i - pred + 1;
72 * Returns also the rank_1 of given position i
73 * and the length of the trailing 0/1-run.
75 bool IsBitSet(ulong i, ulong *rank, ulong *runl) {
77 ulong r = bitRun->rank(i);
80 // Length of 0-bit run after pos i
81 *runl = bitRun->select(1) - i - 1;
84 ulong pred = bitRun->select(r);
86 ulong bitsBeforeRun = 0;
88 bitsBeforeRun = runLength->select(r - 1) + 1;
90 ulong bitsInRun = runLength->select(r) + 1 - bitsBeforeRun;
91 if (i - pred >= bitsInRun)
93 *rank = bitsBeforeRun + bitsInRun;
96 *runl = bitRun->select(r+1) - i - 1;
100 *rank = bitsBeforeRun + i - pred + 1;
101 *runl = bitsInRun - (i - pred) - 1;
106 ulong u; // Universe size, number of bits in B
107 ulong numberOfRuns; // Number of 1-bit runs
108 BSGAP *bitRun, // Contains 1-bit at the start of each 1-bit-run
109 *runLength; // Contains run lengths for each 1-bit-run
110 ulong totalLength; // Total length of runs