libcds/src/static_sequence/static_sequence_gmr_chunk.h

   1
   2 #ifndef _STATIC_SEQUENCE_GMR_CHUNK_H
   3 #define _STATIC_SEQUENCE_GMR_CHUNK_H
   4
   5 #include <basics.h>
   6 #include <static_bitsequence.h>
   7 #include <static_bitsequence_builder.h>
   8 #include <static_permutation.h>
   9 #include <cassert>
  10 #include <iostream>
  11
  12 using namespace std;
  13
  14 /** Implementation of the Chunk of Golynski et al's rank/select
  15  * data structure [1].
  16  *
  17  * [1] A. Golynski and I. Munro and S. Rao.
  18  * Rank/select operations on large alphabets: a tool for text indexing.
  19  * SODA 06.
  20  *
  21  * @author Francisco Claude
  22  */
  23 class static_sequence_gmr_chunk: public static_sequence {
  24   public:
  25     /** Builds the structures needed for the chunk */
  26     static_sequence_gmr_chunk(uint * sequence, uint chunk_length, static_bitsequence_builder *bmb, static_permutation_builder *pmb);
  27
  28     /** Destroy the chunk */
  29     ~static_sequence_gmr_chunk();
  30
  31     virtual uint access(uint j);
  32     virtual uint select(uint i, uint j);
  33     virtual uint rank(uint i, uint j);
  34     virtual uint size();
  35     virtual uint save(FILE *fp);
  36     static_sequence_gmr_chunk * load(FILE *fp);
  37
  38   protected:
  39     /** Bitmap */
  40     static_bitsequence * X;
  41     /** Permutation */
  42     static_permutation permutation;
  43     /** Size of the alphabet */
  44     uint sigma;
  45     /** Length of the chunk */
  46     uint chunk_length;
  47 };
  48 #endif