8#ifndef INCLUDED_SDSL_UTIL
9#define INCLUDED_SDSL_UTIL
37#define SDSL_XSTR(s) SDSL_STR(s)
78template <
class t_
int_vec>
81template <
class t_
int_vec>
84template <
class t_
int_vec>
92template <
class t_
int_vec>
96template <
class t_
int_vec>
100template <
class t_
int_vec>
101void mod(t_int_vec & v,
typename t_int_vec::size_type m);
103inline void cyclic_shifts(uint64_t * vec, uint8_t & n, uint64_t k, uint8_t int_width);
112template <
class t_
int_vec>
123template <
class t_
int_vec,
class t_
int_vec_iterator>
124void set_to_value(t_int_vec & v, uint64_t k, t_int_vec_iterator it);
127template <
class t_
int_vec>
134template <
class t_
int_vec>
140template <
class t_
int_vec>
146template <
class t_
int_vec>
155template <
class t_
int_vec>
156typename t_int_vec::size_type
next_bit(t_int_vec
const & v, uint64_t idx);
164template <
class t_
int_vec>
165typename t_int_vec::size_type
prev_bit(t_int_vec
const & v, uint64_t idx);
182 stat(file.c_str(), &fs);
195 char * c = _strdup((
char const *)file.c_str());
196 char file_name[_MAX_FNAME] = {0};
198 ::_splitpath_s(c, NULL, 0, NULL, NULL, file_name, _MAX_FNAME, NULL, 0);
200 ::_splitpath(c, NULL, NULL, file_name, NULL);
202 std::string res(file_name);
204 char * c = strdup((
char const *)file.c_str());
220 char * c = _strdup((
char const *)file.c_str());
221 char dir_name[_MAX_DIR] = {0};
222 char drive[_MAX_DRIVE] = {0};
224 ::_splitpath_s(c, drive, _MAX_DRIVE, dir_name, _MAX_DIR, NULL, 0, NULL, 0);
226 ::_splitpath(c, drive, dir_name, NULL, NULL);
228 std::string res = std::string(drive) + std::string(dir_name);
230 char * c = strdup((
char const *)file.c_str());
231 std::string res = std::string(
::dirname(c));
232 auto it = res.begin();
233 auto next_it = res.begin() + 1;
234 while (it != res.end() and next_it != res.end())
236 if (*next_it !=
'/' or *it !=
'/')
242 res.resize(it - res.begin() + 1);
263inline std::string demangle(std::string
const & name)
269 abi::__cxa_demangle(name.c_str(), buf, &
size, &status);
271 return std::string(buf);
279inline std::string demangle2(std::string
const & name)
281 std::string result = demangle(name);
282 std::vector<std::string> words_to_delete;
283 words_to_delete.push_back(
"sdsl::");
284 words_to_delete.push_back(
"(unsigned char)");
285 words_to_delete.push_back(
", unsigned long");
287 for (
size_t k = 0; k < words_to_delete.size(); ++k)
289 std::string w = words_to_delete[k];
290 for (
size_t i = result.find(w); i != std::string::npos; i = result.find(w, i))
292 result.erase(i, w.length());
297 std::string to_replace =
"int_vector<1>";
298 while ((index = result.find(to_replace, index)) != std::string::npos)
300 result.replace(index, to_replace.size(),
"bit_vector");
307std::string
to_string(T
const & t,
int w);
311uint64_t hashvalue_of_classname(T
const &)
313 std::hash<std::string> str_hash;
314 return str_hash(sdsl::util::demangle2(
typeid(T).name()));
319std::string class_to_hash(T
const & t)
321 return to_string(hashvalue_of_classname(t));
325std::string class_name(T
const & t)
327 std::string result = demangle2(
typeid(t).name());
328 size_t template_pos = result.find(
"<");
329 if (template_pos != std::string::npos)
331 result = result.erase(template_pos);
337inline char * str_from_errno()
340# pragma warning(disable : 4996)
341 return strerror(errno);
342# pragma warning(default : 4996)
344 return strerror(errno);
348struct _id_helper_struct
353extern inline uint64_t _id_helper()
355 static _id_helper_struct data;
376std::string to_latex_string(T
const & t);
378inline std::string to_latex_string(
unsigned char c)
389inline void delete_all_files(
tMSS & file_map)
391 for (
auto file_pair : file_map)
418template <
class S,
class P>
419void swap_support(S & s1, S & s2, P
const * p1, P
const * p2)
430template <
class S,
class X>
431void init_support(S & s, X
const * x)
441template <
class t_
int_vec>
442t_int_vec rnd_positions(uint8_t log_s, uint64_t & mask, uint64_t
mod = 0, uint64_t seed = 17)
444 mask = (1 << log_s) - 1;
445 t_int_vec rands(1 << log_s, 0);
460 std::integral_constant<bool,
461 std::is_default_constructible<T>::value && std::is_copy_constructible<T>::value
462 && std::is_move_constructible<T>::value && std::is_copy_assignable<T>::value
463 && std::is_move_assignable<T>::value>
470template <
class t_
int_vec>
476 rng.seed(std::chrono::system_clock::now().time_since_epoch().
count() +
util::id());
481 uint64_t * data = v.data();
485 for (
typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
492template <
class t_
int_vec>
493void util::mod(t_int_vec & v,
typename t_int_vec::size_type m)
495 for (
typename t_int_vec::size_type i = 0; i < v.size(); ++i)
501template <
class t_
int_vec>
504 auto max_elem = std::max_element(v.begin(), v.end());
506 if (max_elem != v.end())
510 uint8_t min_width =
bits::hi(max) + 1;
511 uint8_t old_width = v.width();
512 if (old_width > min_width)
514 uint64_t
const * read_data = v.data();
515 uint64_t * write_data = v.data();
516 uint8_t read_offset = 0;
517 uint8_t write_offset = 0;
518 for (
typename t_int_vec::size_type i = 0; i < v.size(); ++i)
523 v.bit_resize(v.size() * min_width);
529template <
class t_
int_vec>
532 uint8_t old_width = v.width();
533 typename t_int_vec::size_type n = v.size();
534 if (new_width > old_width)
538 typename t_int_vec::size_type i, old_pos, new_pos;
539 new_pos = (n - 1) * new_width;
540 old_pos = (n - 1) * old_width;
541 v.bit_resize(v.size() * new_width);
542 for (i = 0; i < n; ++i, new_pos -= new_width, old_pos -= old_width)
544 v.set_int(new_pos, v.get_int(old_pos, old_width), new_width);
551template <
class t_
int_vec>
554 std::for_each(v.data(),
555 v.data() + ((v.bit_size() + 63) >> 6),
562template <
class t_
int_vec>
565 std::for_each(v.data(),
566 v.data() + ((v.bit_size() + 63) >> 6),
578 k &= 0xFFFFFFFFFFFFFFFFULL >> (64 - int_width);
581 vec[n] |= k << offset;
588 assert(int_width - (offset - 64) < 64);
589 vec[n] = k >> (int_width - (offset - 64));
596template <
class t_
int_vec>
599 uint64_t * data = v.data();
602 uint8_t int_width = v.width();
605 throw std::logic_error(
"util::set_to_value can not be performed with int_width=0!");
621 typename t_int_vec::size_type n64 = (v.bit_size() + 63) >> 6;
622 for (
typename t_int_vec::size_type i = 0; i < n64;)
624 for (uint64_t ii = 0; ii < n and i < n64; ++ii, ++i)
631template <
class t_
int_vec,
class t_
int_vec_iterator>
634 typedef typename t_int_vec::size_type size_type;
638 uint8_t int_width = v.
width();
641 throw std::logic_error(
"util::set_to_value can not be performed with int_width=0!");
647 size_type words = (v.bit_size() + 63) >> 6;
648 size_type word_pos = ((it - v.begin()) * int_width) >> 6;
649 uint8_t pos_in_word = ((it - v.begin()) * int_width) - (word_pos << 6);
650 uint8_t cyclic_shift = word_pos % n;
652 uint64_t * data = v.data() + word_pos;
657 while (word_pos < words)
659 for (; cyclic_shift < n && word_pos < words; ++cyclic_shift, ++word_pos)
661 *(++data) = vec[cyclic_shift];
668template <
class t_
int_vec>
671 std::iota(v.begin(), v.end(), 0ULL);
674template <
class t_
int_vec>
677 uint64_t
const * data = v.data();
680 typename t_int_vec::size_type result =
bits::cnt(*data);
681 for (
typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
685 if (v.bit_size() & 0x3F)
692template <
class t_
int_vec>
695 uint64_t
const * data = v.data();
698 uint64_t carry = 0, oldcarry = 0;
699 typename t_int_vec::size_type result =
bits::cnt10(*data, carry);
700 for (
typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
705 if (v.bit_size() & 0x3F)
712template <
class t_
int_vec>
715 uint64_t
const * data = v.data();
718 uint64_t carry = 1, oldcarry = 1;
719 typename t_int_vec::size_type result =
bits::cnt01(*data, carry);
720 for (
typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
725 if (v.bit_size() & 0x3F)
732template <
class t_
int_vec>
733typename t_int_vec::size_type
util::next_bit(t_int_vec
const & v, uint64_t idx)
735 uint64_t pos = idx >> 6;
736 uint64_t node = v.data()[pos];
737 node >>= (idx & 0x3F);
745 while ((pos << 6) < v.bit_size())
749 return (pos << 6) |
bits::lo(v.data()[pos]);
757template <
class t_
int_vec>
758typename t_int_vec::size_type
util::prev_bit(t_int_vec
const & v, uint64_t idx)
760 uint64_t pos = idx >> 6;
761 uint64_t node = v.data()[pos];
762 node <<= 63 - (idx & 0x3F);
765 return bits::hi(node) + (pos << 6) - (63 - (idx & 0x3F));
770 while ((pos << 6) < v.bit_size())
774 return (pos << 6) |
bits::hi(v.data()[pos]);
785 std::stringstream ss;
786 ss << std::setw(w) << t;
791std::string util::to_latex_string(T
const & t)
bits.hpp contains the sdsl::bits class.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
size_t file_size(std::string const &name)
Get the file size.
void set_to_id(t_int_vec &v)
Sets each entry of the numerical vector v at position $fi.
Returns the directory of a file A trailing will be removed std::string dirname(std::string file)
Returns the basename of a file std::string basename(std::string file)
void set_random_bits(t_int_vec &v, int seed=0)
Sets all bits of the int_vector to pseudo-random bits.
Number of set bits in v t_int_vec::size_type cnt_one_bits(t_int_vec const &v)
void mod(t_int_vec &v, typename t_int_vec::size_type m)
All elements of v modulo m.
void expand_width(t_int_vec &v, uint8_t new_width)
Expands the integer width to new_width >= v.width()
void cyclic_shifts(uint64_t *vec, uint8_t &n, uint64_t k, uint8_t int_width)
Get the smallest position f$i geq idx f$ where a bit is set t_int_vec::size_type next_bit(t_int_vec const &v, uint64_t idx)
Get the size of a file in bytes size_t file_size(std::string const &file)
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_zeroone_bits(t_int_vec const &v)
std::string to_string(T const &t, int w=1)
void bit_compress(t_int_vec &v)
Bit compress the int_vector.
void _set_one_bits(t_int_vec &v)
Sets all bits of the int_vector to 1-bits.
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_onezero_bits(t_int_vec const &v)
void _set_zero_bits(t_int_vec &v)
Sets all bits of the int_vector to 0-bits.
Get the greatest position f$i leq idx f$ where a bit is set t_int_vec::size_type prev_bit(t_int_vec const &v, uint64_t idx)
Namespace for the succinct data structure library.
std::string disk_file_name(std::string const &file)
Returns for a RAM-file the corresponding disk file name.
int remove(std::string const &)
Remove a file.
std::map< std::string, std::string > tMSS
std::string ram_file_name(std::string const &file)
Returns the corresponding RAM-file name for file.
uint64_t count(t_k2_treap const &treap, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
Count how many points are in the rectangle (p1,p2)
bool is_ram_file(std::string const &file)
Determines if the given file is a RAM-file.
int_vector ::size_type size(range_type const &r)
Size of a range.
static constexpr uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
static constexpr uint64_t lo_unset[65]
lo_unset[i] is a 64-bit word with the i least significant bits not set and the high bits set.
static constexpr uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
static constexpr void write_int_and_move(uint64_t *&word, uint64_t x, uint8_t &offset, const uint8_t len)
Writes value x to an bit position in an array and moves the bit-pointer.
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
static constexpr uint64_t map01(uint64_t x, uint64_t c=1)
Map all 01 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
static constexpr uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
static constexpr uint64_t read_int_and_move(uint64_t const *&word, uint8_t &offset, const uint8_t len=64)
Reads a value from a bit position in an array and moved the bit-pointer.
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
static constexpr uint64_t map10(uint64_t x, uint64_t c=0)
Map all 10 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.