8 #ifndef INCLUDED_SDSL_UTIL
9 #define INCLUDED_SDSL_UTIL
36 #define SDSL_STR(x) #x
37 #define SDSL_XSTR(s) SDSL_STR(s)
45 #include <sys/types.h>
46 #include <type_traits>
56 #include <sys/resource.h>
91 template <
class t_
int_vec>
94 template <
class t_
int_vec>
97 template <
class t_
int_vec>
105 template <
class t_
int_vec>
109 template <
class t_
int_vec>
113 template <
class t_
int_vec>
116 inline void cyclic_shifts(uint64_t * vec, uint8_t & n, uint64_t k, uint8_t int_width);
125 template <
class t_
int_vec>
136 template <
class t_
int_vec,
class t_
int_vec_iterator>
137 void set_to_value(t_int_vec & v, uint64_t k, t_int_vec_iterator it);
140 template <
class t_
int_vec>
147 template <
class t_
int_vec>
153 template <
class t_
int_vec>
159 template <
class t_
int_vec>
168 template <
class t_
int_vec>
177 template <
class t_
int_vec>
192 stat(file.c_str(), &fs);
205 char * c = _strdup((
const char *)file.c_str());
206 char file_name[_MAX_FNAME] = { 0 };
208 ::_splitpath_s(c, NULL, 0, NULL, NULL, file_name, _MAX_FNAME, NULL, 0);
210 ::_splitpath(c, NULL, NULL, file_name, NULL);
212 std::string res(file_name);
214 char * c = strdup((
const char *)file.c_str());
215 std::string res = std::string(::
basename(c));
230 char * c = _strdup((
const char *)file.c_str());
231 char dir_name[_MAX_DIR] = { 0 };
232 char drive[_MAX_DRIVE] = { 0 };
234 ::_splitpath_s(c, drive, _MAX_DRIVE, dir_name, _MAX_DIR, NULL, 0, NULL, 0);
236 ::_splitpath(c, drive, dir_name, NULL, NULL);
238 std::string res = std::string(drive) + std::string(dir_name);
240 char * c = strdup((
const char *)file.c_str());
241 std::string res = std::string(::
dirname(c));
242 auto it = res.begin();
243 auto next_it = res.begin() + 1;
244 while (it != res.end() and next_it != res.end())
246 if (*next_it !=
'/' or *it !=
'/') { *(++it) = *next_it; }
249 res.resize(it - res.begin() + 1);
267 inline std::string demangle(
const std::string & name)
273 abi::__cxa_demangle(name.c_str(), buf, &
size, &status);
274 if (status == 0)
return std::string(buf);
282 inline std::string demangle2(
const std::string & name)
284 std::string result = demangle(name);
285 std::vector<std::string> words_to_delete;
286 words_to_delete.push_back(
"sdsl::");
287 words_to_delete.push_back(
"(unsigned char)");
288 words_to_delete.push_back(
", unsigned long");
290 for (
size_t k = 0; k < words_to_delete.size(); ++k)
292 std::string w = words_to_delete[k];
293 for (
size_t i = result.find(w); i != std::string::npos; i = result.find(w, i))
295 result.erase(i, w.length());
300 std::string to_replace =
"int_vector<1>";
301 while ((index = result.find(to_replace, index)) != std::string::npos)
303 result.replace(index, to_replace.size(),
"bit_vector");
309 template <
typename T>
310 std::string
to_string(
const T & t,
int w);
314 uint64_t hashvalue_of_classname(
const T &)
316 std::hash<std::string> str_hash;
317 return str_hash(sdsl::util::demangle2(
typeid(T).name()));
322 std::string class_to_hash(
const T & t)
324 return to_string(hashvalue_of_classname(t));
328 std::string class_name(
const T & t)
330 std::string result = demangle2(
typeid(t).name());
331 size_t template_pos = result.find(
"<");
332 if (template_pos != std::string::npos) { result = result.erase(template_pos); }
337 inline char * str_from_errno()
340 #pragma warning(disable : 4996)
341 return strerror(errno);
342 #pragma warning(default : 4996)
344 return strerror(errno);
348 struct _id_helper_struct
353 extern inline uint64_t _id_helper()
355 static _id_helper_struct data;
360 inline uint64_t
pid()
375 template <
typename T>
376 std::string to_latex_string(
const T & t);
378 inline std::string to_latex_string(
unsigned char c)
389 inline void delete_all_files(
tMSS & file_map)
391 for (
auto file_pair : file_map) {
sdsl::remove(file_pair.second); }
415 template <
class S,
class P>
416 void swap_support(S & s1, S & s2,
const P * p1,
const P * p2)
427 template <
class S,
class X>
428 void init_support(S & s,
const X * x)
438 template <
class t_
int_vec>
439 t_int_vec rnd_positions(uint8_t log_s, uint64_t & mask, uint64_t
mod = 0, uint64_t seed = 17)
441 mask = (1 << log_s) - 1;
442 t_int_vec rands(1 << log_s, 0);
452 template <
typename T>
454 : std::integral_constant<bool,
455 std::is_default_constructible<T>::value && std::is_copy_constructible<T>::value &&
456 std::is_move_constructible<T>::value &&
457 std::is_copy_assignable<T>::value &&
458 std::is_move_assignable<T>::value>
465 template <
class t_
int_vec>
469 if (0 == seed) { rng.seed(std::chrono::system_clock::now().time_since_epoch().
count() +
util::id()); }
473 uint64_t * data = v.data();
474 if (v.empty())
return;
476 for (
typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i) { *(++data) = rng(); }
480 template <
class t_
int_vec>
486 template <
class t_
int_vec>
489 auto max_elem = std::max_element(v.begin(), v.end());
491 if (max_elem != v.end()) { max = *max_elem; }
492 uint8_t min_width =
bits::hi(max) + 1;
493 uint8_t old_width = v.width();
494 if (old_width > min_width)
496 const uint64_t * read_data = v.data();
497 uint64_t * write_data = v.data();
498 uint8_t read_offset = 0;
499 uint8_t write_offset = 0;
505 v.bit_resize(v.size() * min_width);
511 template <
class t_
int_vec>
514 uint8_t old_width = v.width();
516 if (new_width > old_width)
521 new_pos = (n - 1) * new_width;
522 old_pos = (n - 1) * old_width;
523 v.bit_resize(v.size() * new_width);
524 for (i = 0; i < n; ++i, new_pos -= new_width, old_pos -= old_width)
526 v.set_int(new_pos, v.get_int(old_pos, old_width), new_width);
533 template <
class t_
int_vec>
536 std::for_each(v.data(), v.data() + ((v.bit_size() + 63) >> 6), [](uint64_t & value) { value = 0ULL; });
539 template <
class t_
int_vec>
542 std::for_each(v.data(), v.data() + ((v.bit_size() + 63) >> 6), [](uint64_t & value) { value = -1ULL; });
550 k &= 0xFFFFFFFFFFFFFFFFULL >> (64 - int_width);
552 vec[n] |= k << offset;
557 if (int_width == 64)
return;
558 assert(int_width - (offset - 64) < 64);
559 vec[n] = k >> (int_width - (offset - 64));
562 }
while (offset != 0);
565 template <
class t_
int_vec>
568 uint64_t * data = v.data();
569 if (v.empty())
return;
570 uint8_t int_width = v.width();
571 if (int_width == 0) {
throw std::logic_error(
"util::set_to_value can not be performed with int_width=0!"); }
589 for (uint64_t ii = 0; ii < n and i < n64; ++ii, ++i) { *(data++) = vec[ii]; }
593 template <
class t_
int_vec,
class t_
int_vec_iterator>
598 if (v.empty())
return;
599 uint8_t int_width = v.
width();
600 if (int_width == 0) {
throw std::logic_error(
"util::set_to_value can not be performed with int_width=0!"); }
605 size_type words = (v.bit_size() + 63) >> 6;
606 size_type word_pos = ((it - v.begin()) * int_width) >> 6;
607 uint8_t pos_in_word = ((it - v.begin()) * int_width) - (word_pos << 6);
608 uint8_t cyclic_shift = word_pos % n;
610 uint64_t * data = v.
data() + word_pos;
615 while (word_pos < words)
617 for (; cyclic_shift < n && word_pos < words; ++cyclic_shift, ++word_pos) { *(++data) = vec[cyclic_shift]; }
623 template <
class t_
int_vec>
626 std::iota(v.begin(), v.end(), 0ULL);
629 template <
class t_
int_vec>
632 const uint64_t * data = v.data();
633 if (v.empty())
return 0;
640 template <
class t_
int_vec>
643 const uint64_t * data = v.data();
644 if (v.empty())
return 0;
645 uint64_t carry = 0, oldcarry = 0;
652 if (v.bit_size() & 0x3F)
659 template <
class t_
int_vec>
662 const uint64_t * data = v.data();
663 if (v.empty())
return 0;
664 uint64_t carry = 1, oldcarry = 1;
671 if (v.bit_size() & 0x3F)
678 template <
class t_
int_vec>
681 uint64_t pos = idx >> 6;
682 uint64_t node = v.data()[pos];
683 node >>= (idx & 0x3F);
684 if (node) {
return idx +
bits::lo(node); }
688 while ((pos << 6) < v.bit_size())
690 if (v.data()[pos]) {
return (pos << 6) |
bits::lo(v.data()[pos]); }
697 template <
class t_
int_vec>
700 uint64_t pos = idx >> 6;
701 uint64_t node = v.data()[pos];
702 node <<= 63 - (idx & 0x3F);
703 if (node) {
return bits::hi(node) + (pos << 6) - (63 - (idx & 0x3F)); }
707 while ((pos << 6) < v.bit_size())
709 if (v.data()[pos]) {
return (pos << 6) |
bits::hi(v.data()[pos]); }
716 template <
typename T>
719 std::stringstream ss;
720 ss << std::setw(w) << t;
724 template <
typename T>
725 std::string util::to_latex_string(
const T & t)
bits.hpp contains the sdsl::bits class.
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.
int_vector ::size_type size_type
size_t file_size(const std::string &name)
Get the file size.
void set_to_id(t_int_vec &v)
Sets each entry of the numerical vector v at position $fi.
Get the size of a file in bytes size_t file_size(const std::string &file)
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 occurrences of bit pattern in v t_int_vec::size_type cnt_onezero_bits(const t_int_vec &v)
Get the greatest position f $i leq idx f where a bit is set t_int_vec::size_type prev_bit(const t_int_vec &v, uint64_t idx)
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(const t_int_vec &v, uint64_t idx)
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.
std::string to_string(const T &t, int w=1)
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_zeroone_bits(const t_int_vec &v)
Number of set bits in v t_int_vec::size_type cnt_one_bits(const t_int_vec &v)
void _set_zero_bits(t_int_vec &v)
Sets all bits of the int_vector to 0-bits.
Namespace for the succinct data structure library.
bool is_ram_file(const std::string &file)
Determines if the given file is a RAM-file.
std::map< std::string, std::string > tMSS
uint64_t count(const t_k2_treap &treap, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
Count how many points are in the rectangle (p1,p2)
std::string ram_file_name(const std::string &file)
Returns the corresponding RAM-file name for file.
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
std::string disk_file_name(const std::string &file)
Returns for a RAM-file the corresponding disk file name.
int remove(const std::string &)
Remove a file.
int_vector ::size_type size(const range_type &r)
Size of a range.
sfstream.hpp contains a two stream class which can be used to read/write from/to files or strings.
constexpr static 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 SDSL_CONSTEXPR uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
static SDSL_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 SDSL_CONSTEXPR uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
static SDSL_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 SDSL_CONSTEXPR uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
constexpr static 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 SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
static SDSL_CONSTEXPR uint64_t read_int_and_move(const uint64_t *&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 SDSL_CONSTEXPR uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
static SDSL_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.