2 * Binary-searchable gap encoding scheme (BSGAP)
7 * Ankur Gupta and Wing-Kai Hon and Rahul Shah and Jeffrey Scott Vitter. Compressed data structures:
8 * Dictionaries and data-aware measures, Theor. Comput. Sci., Volume 387, Issue 3 (November 2007).
14 #include "BlockArray.h"
19 BSGAP(ulong *, ulong, bool = false, ulong = 0);
24 ulong rank(bool b, ulong i) {return b?rank(i):i+1-rank(i);};
27 ulong select(bool b, ulong i) {return b?select(i):select0(i);};
29 bool IsBitSet(ulong pos);
30 // Returns also the rank_1(pos) via the second param
31 bool IsBitSet(ulong pos, ulong *);
33 ulong size() {return u;};
34 ulong bitsSet() {return n;}
35 void Save(FILE *) const;
37 static const uchar bit_table[];
38 ulong u, n; // Universe size, number of 1-bits in B
39 ulong topCount; // Top structure and the number of substructures
40 ulong bitsInP; // Length of bit vector P
41 ulong *P; // Pointer to BSGAP structures
42 unsigned b; // Subdictionary size (\log^2 n)
43 BlockArray *offsetA; // Array of pointers (into bitvector P)
44 BlockArray *firstKeyA; // Array of first key positions of the substructures
46 ulong rank(ulong *, ulong, ulong, ulong, ulong, ulong, ulong, bool);
47 bool IsBitSet(ulong *, ulong, ulong, ulong, ulong, ulong, ulong, bool);
48 bool IsBitSet(ulong *, ulong, ulong, ulong, ulong, ulong, ulong, bool, ulong *);
49 ulong select(ulong *, ulong, ulong, ulong, ulong, ulong, ulong, bool);
50 ulong select0(ulong *, ulong, ulong, ulong, ulong, ulong, ulong, bool);
51 ulong * GetSubtree(ulong *, ulong, ulong, ulong, ulong, bool, ulong &);
52 ulong DeltaDecode(ulong *, ulong &);
53 ulong DeltaDecode(ulong *, ulong &, bool &);
54 ulong * DeltaEncode(ulong, ulong &, bool = true, bool = false);
55 void BitCopy(ulong *, ulong *, ulong, ulong);
56 ulong FindMedian(ulong *, ulong, ulong, ulong, ulong);
57 unsigned FindLowestBit(ulong);
59 inline bool IsSubtreeFull(ulong firstKey, ulong l, ulong r, ulong n)
69 * Returns the number of zeros in the left subtree
71 inline ulong numberOfZeros(ulong firstKey, ulong l, ulong key, ulong n)
73 ulong z = key - l - 1 - n/2;
81 inline ulong FindRightSubtree(ulong *B, ulong offset, ulong firstKey, ulong key, ulong l, ulong r, ulong n)
84 return 0; // Does not exists
86 if (IsSubtreeFull(firstKey, key, r, n - n/2 - 1))
87 return 0; // Right subtree is full (does not exists)
90 return offset; // Left subtree does not exists
92 if (IsSubtreeFull(firstKey, l, key, n/2))
93 return offset; // Left subtree is full (does not exists)
95 ulong len = DeltaDecode(B, offset);
96 return offset + len; // Skipping left subtree
99 inline ulong FindLeftSubtree(ulong *B, ulong offset, ulong firstKey, ulong key, ulong l, ulong r, ulong n)
102 return 0; // Does not exists
104 if (IsSubtreeFull(firstKey, l, key, n/2))
105 return 0; // Left subtree is full
107 if (n - n/2 - 1 == 0)
108 return offset; // Right subtree does not exists
110 if (IsSubtreeFull(firstKey, key, r, n - n/2 - 1))
111 return offset; // Right subtree is full
113 DeltaDecode(B, offset); // Calculate new offset
114 return offset; // Left subtree is the first one