incbwt/rlcsa.h

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