BSGAP.h

   1 /**
   2  * Binary-searchable gap encoding scheme (BSGAP)
   3  * Niko Välimäki
   4  *
   5  * Based on:
   6  *
   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).
   9  */
  10 #ifndef _BSGAP_H_
  11 #define _BSGAP_H_
  12
  13 #include "Tools.h"
  14 #include "BlockArray.h"
  15
  16 class BSGAP
  17 {
  18 public:
  19     BSGAP(ulong *, ulong, bool = false, ulong = 0);
  20     BSGAP(FILE *);
  21     ~BSGAP();
  22     ulong rank(ulong);
  23     ulong rank0(ulong);
  24     ulong rank(bool b, ulong i) {return b?rank(i):i+1-rank(i);};
  25     ulong select(ulong);
  26     ulong select0(ulong);
  27     ulong select(bool b, ulong i) {return b?select(i):select0(i);};
  28
  29     bool IsBitSet(ulong pos);
  30     // Returns also the rank_1(pos) via the second param
  31     bool IsBitSet(ulong pos, ulong *);
  32
  33     ulong size() {return u;};
  34     ulong bitsSet() {return n;}
  35     void Save(FILE *) const;
  36 private:
  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
  45
  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);
  58
  59     inline bool IsSubtreeFull(ulong firstKey, ulong l, ulong r, ulong n)
  60     {
  61         if (l == firstKey)
  62             n --;
  63
  64         if (r - l - 1 == n)
  65             return true;
  66         return false;
  67     }
  68     /**
  69      * Returns the number of zeros in the left subtree
  70      */
  71     inline ulong numberOfZeros(ulong firstKey, ulong l, ulong key, ulong n)
  72     {
  73         ulong z = key - l - 1 - n/2;
  74         if (l == firstKey)
  75             ++z;
  76         if (z == -1lu)
  77             z = 0;
  78         return z;
  79     }
  80
  81     inline ulong FindRightSubtree(ulong *B, ulong offset, ulong firstKey, ulong key, ulong l, ulong r, ulong n)
  82     {
  83         if (n - n/2 - 1 == 0)
  84             return 0;       // Does not exists
  85
  86         if (IsSubtreeFull(firstKey, key, r, n - n/2 - 1))
  87             return 0;       // Right subtree is full (does not exists)
  88
  89         if (n/2 == 0)
  90             return offset; // Left subtree does not exists
  91
  92         if (IsSubtreeFull(firstKey, l, key, n/2))
  93             return offset; // Left subtree is full (does not exists)
  94
  95         ulong len = DeltaDecode(B, offset);
  96         return offset + len;         // Skipping left subtree
  97     }
  98
  99     inline ulong FindLeftSubtree(ulong *B, ulong offset, ulong firstKey, ulong key, ulong l, ulong r, ulong n)
 100     {
 101         if (n/2 == 0)
 102             return 0;       // Does not exists
 103
 104         if (IsSubtreeFull(firstKey, l, key, n/2))
 105             return 0;       // Left subtree is full
 106
 107         if (n - n/2 - 1 == 0)
 108             return offset; // Right subtree does not exists
 109
 110         if (IsSubtreeFull(firstKey, key, r, n - n/2 - 1))
 111             return offset; // Right subtree is full
 112
 113         DeltaDecode(B, offset); // Calculate new offset
 114         return offset;      // Left subtree is the first one
 115     }
 116
 117 };
 118
 119 #endif