// Copyright (c) 2017, Nicola Prezza. All rights reserved. // Use of this source code is governed // by a MIT license that can be found in the LICENSE file. /* * dynamic.hpp * * Created on: Oct 21, 2015 * Author: nico */ #ifndef DYNAMIC_TYPEDEFS_HPP_ #define DYNAMIC_TYPEDEFS_HPP_ #include "dynamic/internal/spsi.hpp" #include "dynamic/internal/gap_bitvector.hpp" #include "dynamic/internal/spsi_check.hpp" #include "dynamic/internal/succinct_bitvector.hpp" #include "dynamic/internal/rle_string.hpp" #include "dynamic/internal/bwt.hpp" #include "dynamic/internal/sparse_vector.hpp" #include "dynamic/internal/packed_vector.hpp" #include "dynamic/internal/hacked_vector.hpp" #include "dynamic/internal/lciv.hpp" #include "dynamic/internal/wt_string.hpp" #include "dynamic/internal/wm_string.hpp" #include "dynamic/internal/fm_index.hpp" namespace dyn{ /* * a succinct searchable partial sum with inserts implemented with cache-efficient * B trees. Logarithmic-sized leaves */ typedef spsi packed_spsi; typedef lciv packed_lciv; /* * a succinct searchable partial sum with inserts implemented with cache-efficient * B trees. Quadratic-log sized leaves */ typedef spsi succinct_spsi; typedef lciv succinct_lciv; /* * dynamic gap-encoded bitvector */ typedef gap_bitvector gap_bv; /* * dynamic succinct bitvector (about 1.1n bits) */ typedef succinct_bitvector> suc_bv; /* * succinct/compressed dynamic string implemented with wavelet trees. * user can choose (at construction time) between fixed-length / gamma / Huffman encoding of characters. */ typedef wt_string wt_str; /* * succinct/compressed dynamic string implemented with a wavelet matrix. */ typedef wm_string>> wm_str; /* * run-length encoded (RLE) string. This string uses 1 sparse bitvector * for all runs, one dynamic string for run heads, and sigma sparse bitvectors (one per character) */ typedef rle_string rle_str; /* * RLE string implemented with a run-length encoded wavelet tree. Each * WT node is run-length encoded. rle_str is much more efficient and * thus preferable */ typedef wt_string wtrle_str; /* * string implemented with a gap-compressed wavelet tree. Each * WT node is gap-compressed. */ typedef wt_string wtgap_str; /* * succinct/compressed BWT (see description of com_str) */ typedef bwt wt_bwt; /* * run-length encoded BWT */ typedef bwt rle_bwt; /* * dynamic sparse vector: <= m*k + O(m log n/m) bits of space, where k is the maximum * number of bits of any integer > 0 and n is the total number of integers. */ typedef sparse_vector sparse_vec; /* * dynamic succinct/entropy compressed FM index. BWT positions are * marked with a succinct bitvector * * ( n*H0 + n + (n/k)*log n )(1+o(1)) bits of space, where k is the SA sample rate * */ typedef fm_index wt_fmi; /* * dynamic run-length encoded FM index. BWT positions are * marked with a gap-encoded bitvector. * * ( 2*R*log(n/R) + R*H0 + (n/k)*log(n/k) + (n/k)*log n )(1+o(1)) bits of space, where * k is the SA sample rate and R is the number of runs in the BWT * */ typedef fm_index rle_fmi; // ------------- STRUCTURES DESIGNED ONLY FOR DEBUGGING PURPOSES ------------- /* * dynamic bitvector with trivial implementation (test purposes) */ typedef succinct_bitvector > bv_check; typedef wt_string str_check; typedef rle_string rle_str_check; // ------------- template specializations ------------------------------------ /* * build structure given as input the BWT in string format * and the terminator character. * * Efficient constructor: pushes back runs * */ template<> inline void rle_bwt::build_from_string(string& bwt, char terminator, bool verbose){ const ulint step = 1000000; //print status every step characters ulint last_step = 0; terminator_position = bwt.size(); char c = bwt[0]; ulint k=1; for(ulint i=1; ilast_step+(step-1)){ last_step = i; cout << " " << i << " characters processed ..." << endl; } } } //last run if(c == terminator){ //there must be only one terminator in the string assert(terminator_position == bwt.size()); assert(k==1); //terminator in last BWT position terminator_position = bwt.size() - 1; }else{ insert_in_F(c,k); L.insert(L.size(),c,k); } assert(size() == bwt.size()); assert(terminator_position != bwt.size()); } template<> inline ulint rle_bwt::number_of_runs(){ return L.number_of_runs()+1; } template<> inline ulint rle_bwt::number_of_runs(pair interval) const { //coordinates on BWT with terminator auto l1 = interval.first; auto r1 = interval.second; //coordinates on BWT without terminator ulint l2 = interval.first <= terminator_position ? interval.first : interval.first-1; ulint r2 = interval.second <= terminator_position ? interval.second : interval.second-1; //if terminator falls outside the interval, just count number of runs //otherwise, take into account terminator return terminator_position < l1 or terminator_position >= r1 ? L.number_of_runs({l2,r2}) : terminator_position == l1 or terminator_position == r1-1 ? L.number_of_runs({l2,r2})+1 : L.at(terminator_position-1) == L.at(terminator_position) ? L.number_of_runs({l2,r2})+2 : L.number_of_runs({l2,r2})+1; } /* * given a position i inside the string, return the interval [l,r) of the run containing i, * i.e. i \in [l,r) (right position always exclusive) */ template<> inline pair rle_bwt::locate_run(ulint i) const { assert(i= range.second ? range : //terminator outside range i < terminator_position ? //terminator inside range pair {range.first,terminator_position} : //i at the left of terminator pair {terminator_position+1,range.second}; } } #endif /* DYNAMIC_TYPEDEFS_HPP_ */