incbwt/rlcsa.h

   1 #ifndef RLCSA_H
   2 #define RLCSA_H
   3
   4 #include <fstream>
   5 #include <cstring> // defines std::memset, added by Kim
   6
   7 #include "bits/vectors.h"
   8 #include "sasamples.h"
   9 #include "misc/parameters.h"
  10
  11
  12 namespace CSA
  13 {
  14
  15
  16 const std::string SA_EXTENSION = ".sa";
  17 const std::string PSI_EXTENSION = ".psi";
  18 const std::string ARRAY_EXTENSION = ".rlcsa.array";
  19 const std::string SA_SAMPLES_EXTENSION = ".rlcsa.sa_samples";
  20 const std::string PARAMETERS_EXTENSION = ".rlcsa.parameters";
  21
  22
  23 const parameter_type RLCSA_BLOCK_SIZE  = parameter_type("RLCSA_BLOCK_SIZE", 32);
  24 const parameter_type SAMPLE_RATE       = parameter_type("SAMPLE_RATE", 512);
  25 const parameter_type SUPPORT_LOCATE    = parameter_type("SUPPORT_LOCATE", 0);
  26 const parameter_type SUPPORT_DISPLAY   = parameter_type("SUPPORT_DISPLAY", 0);
  27
  28
  29 struct LocateItem
  30 {
  31   usint value;
  32   usint offset;
  33   bool found;
  34 };
  35
  36
  37
  38 class RLCSA
  39 {
  40   public:
  41     const static usint ENDPOINT_BLOCK_SIZE = 16;
  42
  43     RLCSA(const std::string& base_name, bool print = false);
  44
  45     /*
  46       If multiple_sequences is true, each 0 is treated as a end of sequence marker.
  47       There must be nonzero characters between the 0s. data[bytes - 1] must also be 0.
  48     */
  49     RLCSA(uchar* data, usint bytes, usint block_size, usint sa_sample_rate, bool multiple_sequences, bool delete_data);
  50
  51     // Destroys contents of index and increment.
  52     RLCSA(RLCSA& index, RLCSA& increment, usint* positions, usint block_size);
  53     ~RLCSA();
  54
  55     void writeTo(const std::string& base_name);
  56
  57     bool isOk();
  58
  59     // Returns the closed interval of suffix array containing the matches.
  60     pair_type count(const std::string& pattern);
  61
  62     void reportPositions(uchar* data, usint length, usint* positions);
  63
  64     // Returns SA[range]. User must free the buffer. Latter version uses buffer provided by the user.
  65     LocateItem* locate(pair_type range);
  66     LocateItem* locate(pair_type range, LocateItem* data);
  67
  68     // Returns SA[index].
  69     usint locate(usint index);
  70
  71     // Returns Ti[range]. User must free the buffer. Latter version uses buffer provided by the user.
  72     uchar* display(usint sequence, pair_type range);
  73     uchar* display(usint sequence, pair_type range, uchar* data);
  74
  75     // Writes the Psi array into given file. End of sequence markers are not written.
  76     void decompressInto(std::ofstream& psi_file);
  77
  78     // Returns the BWT of the collection including end of sequence markers.
  79     uchar* readBWT();
  80
  81     // Return value includes the implicit end of sequence markers. To get suffix array indexes,
  82     // subtract getNumberOfSequences() from the value.
  83     usint psi(usint index);
  84     pair_type psi(usint index, usint max_length); // This version returns a run.
  85
  86     inline bool supportsLocate()       { return this->support_locate; }
  87     inline bool supportsDisplay()      { return this->support_display; }
  88     inline usint getSize()              { return this->data_size; }
  89     inline usint getNumberOfSequences() { return this->number_of_sequences; }
  90
  91     pair_type getSequence(usint number);
  92
  93     // Returns the size of the data structure.
  94     usint reportSize(bool print = false);
  95
  96   private:
  97     bool ok;
  98
  99     RLEVector* array[CHARS];
 100     SASamples* sa_samples;
 101
 102     pair_type index_ranges[CHARS];
 103     usint data_size;
 104
 105     usint text_chars[CHARS];  // which characters are present in the text
 106     usint chars;
 107
 108     usint index_pointers[CHARS]; // which of the above is at i * index_rate
 109     usint index_rate;
 110
 111     bool support_locate, support_display;
 112     usint sample_rate;
 113
 114     usint number_of_sequences;
 115     DeltaVector* end_points;
 116
 117     void locateUnsafe(pair_type range, LocateItem* data);
 118     bool processRun(pair_type run, LocateItem* data);
 119     void displayUnsafe(pair_type range, uchar* data);
 120
 121     inline usint getCharacter(usint pos)
 122     {
 123       usint* curr = &(this->text_chars[this->index_pointers[pos / this->index_rate]]);
 124       while(pos > this->index_ranges[*curr].second) { curr++; }
 125       return *curr;
 126     }
 127
 128     void buildCharIndexes(usint* distribution);
 129 };
 130
 131
 132 // Returns the total number of characters.
 133 usint buildRanges(usint* distribution, pair_type* index_ranges);
 134
 135
 136 } // namespace CSA
 137
 138
 139 #endif // RLCSA_H