libcds/src/static_sequence/static_sequence_wvtree.h

   1
   2 #ifndef STATIC_SEQUENCE_WVTREE_H
   3 #define STATIC_SEQUENCE_WVTREE_H
   4 #include <iostream>
   5 #include <cassert>
   6 #include <basics.h>
   7 #include <static_bitsequence.h>
   8 #include <static_bitsequence_builder.h>
   9 #include <wt_node_internal.h>
  10 #include <wt_coder_binary.h>
  11 #include <alphabet_mapper.h>
  12 #include <static_sequence.h>
  13
  14 using namespace std;
  15
  16 class static_sequence_wvtree : public static_sequence {
  17   public:
  18
  19     /** Builds a Wavelet Tree for the string
  20      * pointed by symbols assuming its length
  21      * equals n and the test flag allows to set
  22      * if the structure must be tested for
  23      * correctness after being created (this is very expensive). */
  24     static_sequence_wvtree(uint * symbols, uint n, wt_coder * coder, static_bitsequence_builder * bmb, alphabet_mapper * am);
  25
  26     virtual ~static_sequence_wvtree();
  27
  28     virtual uint rank(uint symbol, uint pos);
  29
  30     virtual uint select(uint symbol, uint i);
  31
  32     virtual uint access(uint pos);
  33
  34     virtual uint count(uint s);
  35
  36     virtual uint size();
  37
  38     virtual uint save(FILE * fp);
  39     static static_sequence_wvtree * load(FILE *fp);
  40   protected:
  41
  42     static_sequence_wvtree();
  43
  44     wt_node * root;
  45     wt_coder * c;
  46     alphabet_mapper * am;
  47     //bitmap_builder * bmb;
  48
  49     /** Length of the string. */
  50     uint n;
  51
  52     /** Height of the Wavelet Tree. */
  53     uint max_v;
  54
  55     /** Flag for testing for correcteness. */
  56     bool test;
  57
  58
  59 };
  60 #endif /* _STATIC_SEQUENCE_WVTREE_H */