9 #ifndef INCLUDED_SDSL_CONSTRUCT_SA
10 #define INCLUDED_SDSL_CONSTRUCT_SA
78 template <
typename t_
int_vec>
82 constexpr uint8_t t_width = t_int_vec::fixed_int_width;
87 if (len > 0) sa[0] = 0;
90 bool small_file = (
sizeof(len) <= 4 or len < 0x7FFFFFFFULL);
93 uint8_t sa_width = sa.width();
94 if (32 == t_width or (0 == t_width and 32 >= sa_width))
98 divsufsort(c, (int32_t *)sa.data(), (int32_t)len);
102 for (
size_type i = 0, p = 0; i < len; ++i, p += sa_width)
104 sa.set_int(p, sa.get_int(i << 5, 32), sa_width);
114 throw std::logic_error(
"width of int_vector is to small for the text!!!");
119 for (
size_type i = 0; i < len; ++i) { sa[i] = sufarray[i]; }
124 uint8_t sa_width = sa.
width();
131 for (
size_type i = 0, p = 0; i < len; ++i, p += sa_width)
133 sa.set_int(p, sa.get_int(i << 6, 64), sa_width);
159 template <u
int8_t t_w
idth>
162 static_assert(t_width == 0 or t_width == 8,
163 "construct_sa: width must be `0` for integer alphabet and `8` for byte alphabet");
179 else if (t_width == 0)
188 std::cerr <<
"Unknown alphabet type" << std::endl;
void push_back(const uint64_t value)
Appends the given element value to the end of the int_vector_buffer.
const uint64_t * data() const
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
size_type size() const noexcept
The number of elements in the int_vector.
static int_vector_mapper< t_width > create(const std::string &key, cache_config &config)
int_vector.hpp contains the sdsl::int_vector class.
void calculate_sa(const unsigned char *c, typename t_int_vec::size_type len, t_int_vec &sa)
Calculates the Suffix Array for a text.
constexpr char KEY_TEXT[]
int_vector ::size_type size_type
void construct_sa(int_vector_type &sa, const char *file, uint8_t num_bytes)
Construct a suffix array for the sequence stored in a file.
Namespace for the succinct data structure library.
std::string cache_file_name(const std::string &key, const cache_config &config)
Returns the file name of the resource.
construct_config_data & construct_config()
int32_t divsufsort(const uint8_t *T, saidx_t *SA, saidx_t n)
void construct_sa_se(cache_config &config)
Constructs the Suffix Array (SA) from text over byte-alphabet.
bool load_from_file(T &v, const std::string &file)
Load sdsl-object v from a file.
void register_cache_file(const std::string &key, cache_config &config)
Register the existing resource specified by the key to the cache.
void construct_sa(cache_config &config)
Constructs the Suffix Array (SA) from text over byte- or integer-alphabet.
bool store_to_cache(const T &v, const std::string &key, cache_config &config, bool add_type_hash=false)
Stores the object v as a resource in the cache.
int32_t divsufsort64(const uint8_t *T, int64_t *SA, int64_t n)
qsufsort.hpp contains the interface for the suffix array construction algorithm of Larsson.
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Helper class for construction process.
Helper classes to transform width=0 and width=8 to corresponding text key.