GapEncode.h

   1 /**
   2  * Gap encoding scheme
   3  * Niko Välimäki
   4  *
   5  *
   6  */
   7
   8 #ifndef _GapEncode_H_
   9 #define _GapEncode_H_
  10
  11 #include "Tools.h"
  12 #include "BlockArray.h"
  13 #include "BSGAP.h"
  14
  15 class GapEncode
  16 {
  17 public:
  18     GapEncode(ulong *, ulong, bool);
  19     GapEncode(FILE *);
  20     ~GapEncode();
  21
  22     void Save(FILE *) const;
  23     ulong rank(ulong);
  24     ulong rankrun(ulong i) {return bitRun->rank(i);};
  25     ulong selectrun(ulong i) {return bitRun->select(i);};
  26     ulong rank0(ulong);
  27     ulong select(ulong);
  28     ulong select0(ulong); // Not implemented, yet...
  29     bool IsBitSet(ulong i) {
  30         ulong r = bitRun->rank(i);
  31         if (r == 0)
  32             return false;
  33         ulong pred = bitRun->select(r);
  34
  35         ulong bitsBeforeRun = 0;
  36         if (r > 1)
  37             bitsBeforeRun = runLength->select(r - 1) + 1;
  38
  39         ulong bitsInRun = runLength->select(r) + 1 - bitsBeforeRun;
  40         if (i - pred >= bitsInRun)
  41             return false;
  42
  43         return true;
  44     }
  45
  46     /**
  47      * Returns also the rank_1 of given position i
  48      */
  49     bool IsBitSet(ulong i, ulong *rank) {
  50         *rank = 0;
  51         ulong r = bitRun->rank(i);
  52         if (r == 0)
  53             return false;
  54         ulong pred = bitRun->select(r);
  55
  56         ulong bitsBeforeRun = 0;
  57         if (r > 1)
  58             bitsBeforeRun = runLength->select(r - 1) + 1;
  59
  60         ulong bitsInRun = runLength->select(r) + 1 - bitsBeforeRun;
  61         if (i - pred >= bitsInRun)
  62         {
  63             *rank = bitsBeforeRun + bitsInRun;
  64             return false;
  65         }
  66
  67         *rank = bitsBeforeRun + i - pred + 1;
  68         return true;
  69     }
  70
  71     /**
  72      * Returns also the rank_1 of given position i
  73      * and the length of the trailing 0/1-run.
  74      */
  75     bool IsBitSet(ulong i, ulong *rank, ulong *runl) {
  76         *rank = 0;
  77         ulong r = bitRun->rank(i);
  78         if (r == 0)
  79         {
  80             // Length of 0-bit run after pos i
  81             *runl = bitRun->select(1) - i - 1;
  82             return false;
  83         }
  84         ulong pred = bitRun->select(r);
  85
  86         ulong bitsBeforeRun = 0;
  87         if (r > 1)
  88             bitsBeforeRun = runLength->select(r - 1) + 1;
  89
  90         ulong bitsInRun = runLength->select(r) + 1 - bitsBeforeRun;
  91         if (i - pred >= bitsInRun)
  92         {
  93             *rank = bitsBeforeRun + bitsInRun;
  94             *runl = u - i - 1;
  95             if (r < numberOfRuns)
  96                 *runl = bitRun->select(r+1) - i - 1;
  97             return false;
  98         }
  99
 100         *rank = bitsBeforeRun + i - pred + 1;
 101         *runl = bitsInRun - (i - pred) - 1;
 102         return true;
 103     }
 104
 105 private:
 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
 111 };
 112
 113 #endif