8#ifndef INCLUDED_SDSL_UTIL
9#define INCLUDED_SDSL_UTIL
43#define SDSL_XSTR(s) SDSL_STR(s)
53#include <sys/resource.h>
88template <
class t_
int_vec>
91template <
class t_
int_vec>
94template <
class t_
int_vec>
102template <
class t_
int_vec>
106template <
class t_
int_vec>
110template <
class t_
int_vec>
113inline void cyclic_shifts(uint64_t * vec, uint8_t & n, uint64_t k, uint8_t int_width);
122template <
class t_
int_vec>
133template <
class t_
int_vec,
class t_
int_vec_iterator>
134void set_to_value(t_int_vec & v, uint64_t k, t_int_vec_iterator it);
137template <
class t_
int_vec>
144template <
class t_
int_vec>
150template <
class t_
int_vec>
156template <
class t_
int_vec>
165template <
class t_
int_vec>
174template <
class t_
int_vec>
189 stat(file.c_str(), &fs);
202 char * c = _strdup((
const char *)file.c_str());
203 char file_name[_MAX_FNAME] = { 0 };
205 ::_splitpath_s(c, NULL, 0, NULL, NULL, file_name, _MAX_FNAME, NULL, 0);
207 ::_splitpath(c, NULL, NULL, file_name, NULL);
209 std::string res(file_name);
211 char * c = strdup((
const char *)file.c_str());
227 char * c = _strdup((
const char *)file.c_str());
228 char dir_name[_MAX_DIR] = { 0 };
229 char drive[_MAX_DRIVE] = { 0 };
231 ::_splitpath_s(c, drive, _MAX_DRIVE, dir_name, _MAX_DIR, NULL, 0, NULL, 0);
233 ::_splitpath(c, drive, dir_name, NULL, NULL);
235 std::string res = std::string(drive) + std::string(dir_name);
237 char * c = strdup((
const char *)file.c_str());
238 std::string res = std::string(
::dirname(c));
239 auto it = res.begin();
240 auto next_it = res.begin() + 1;
241 while (it != res.end() and next_it != res.end())
243 if (*next_it !=
'/' or *it !=
'/') { *(++it) = *next_it; }
246 res.resize(it - res.begin() + 1);
264inline std::string demangle(
const std::string & name)
270 abi::__cxa_demangle(name.c_str(), buf, &
size, &status);
271 if (status == 0)
return std::string(buf);
279inline std::string demangle2(
const std::string & 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(
const T & t,
int w);
311uint64_t hashvalue_of_classname(
const T &)
313 std::hash<std::string> str_hash;
314 return str_hash(sdsl::util::demangle2(
typeid(T).name()));
319std::string class_to_hash(
const T & t)
321 return to_string(hashvalue_of_classname(t));
325std::string class_name(
const T & t)
327 std::string result = demangle2(
typeid(t).name());
328 size_t template_pos = result.find(
"<");
329 if (template_pos != std::string::npos) { result = result.erase(template_pos); }
334inline char * str_from_errno()
337#pragma warning(disable : 4996)
338 return strerror(errno);
339#pragma warning(default : 4996)
341 return strerror(errno);
345struct _id_helper_struct
350extern inline uint64_t _id_helper()
352 static _id_helper_struct data;
373std::string to_latex_string(
const T & t);
375inline std::string to_latex_string(
unsigned char c)
386inline void delete_all_files(
tMSS & file_map)
388 for (
auto file_pair : file_map) {
sdsl::remove(file_pair.second); }
412template <
class S,
class P>
413void swap_support(S & s1, S & s2,
const P * p1,
const P * p2)
424template <
class S,
class X>
425void init_support(S & s,
const X * x)
435template <
class t_
int_vec>
436t_int_vec rnd_positions(uint8_t log_s, uint64_t & mask, uint64_t
mod = 0, uint64_t seed = 17)
438 mask = (1 << log_s) - 1;
439 t_int_vec rands(1 << log_s, 0);
451 : std::integral_constant<bool,
452 std::is_default_constructible<T>::value && std::is_copy_constructible<T>::value &&
453 std::is_move_constructible<T>::value &&
454 std::is_copy_assignable<T>::value &&
455 std::is_move_assignable<T>::value>
462template <
class t_
int_vec>
466 if (0 == seed) { rng.seed(std::chrono::system_clock::now().time_since_epoch().
count() +
util::id()); }
470 uint64_t * data = v.data();
471 if (v.empty())
return;
473 for (
typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i) { *(++data) = rng(); }
477template <
class t_
int_vec>
483template <
class t_
int_vec>
486 auto max_elem = std::max_element(v.begin(), v.end());
488 if (max_elem != v.end()) { max = *max_elem; }
489 uint8_t min_width =
bits::hi(max) + 1;
490 uint8_t old_width = v.width();
491 if (old_width > min_width)
493 const uint64_t * read_data = v.data();
494 uint64_t * write_data = v.data();
495 uint8_t read_offset = 0;
496 uint8_t write_offset = 0;
502 v.bit_resize(v.size() * min_width);
508template <
class t_
int_vec>
511 uint8_t old_width = v.width();
513 if (new_width > old_width)
518 new_pos = (n - 1) * new_width;
519 old_pos = (n - 1) * old_width;
520 v.bit_resize(v.size() * new_width);
521 for (i = 0; i < n; ++i, new_pos -= new_width, old_pos -= old_width)
523 v.set_int(new_pos, v.get_int(old_pos, old_width), new_width);
530template <
class t_
int_vec>
533 std::for_each(v.data(), v.data() + ((v.bit_size() + 63) >> 6), [](uint64_t & value) { value = 0ULL; });
536template <
class t_
int_vec>
539 std::for_each(v.data(), v.data() + ((v.bit_size() + 63) >> 6), [](uint64_t & value) { value = -1ULL; });
547 k &= 0xFFFFFFFFFFFFFFFFULL >> (64 - int_width);
549 vec[n] |= k << offset;
554 if (int_width == 64)
return;
555 assert(int_width - (offset - 64) < 64);
556 vec[n] = k >> (int_width - (offset - 64));
559 }
while (offset != 0);
562template <
class t_
int_vec>
565 uint64_t * data = v.data();
566 if (v.empty())
return;
567 uint8_t int_width = v.width();
568 if (int_width == 0) {
throw std::logic_error(
"util::set_to_value can not be performed with int_width=0!"); }
586 for (uint64_t ii = 0; ii < n and i < n64; ++ii, ++i) { *(data++) = vec[ii]; }
590template <
class t_
int_vec,
class t_
int_vec_iterator>
595 if (v.empty())
return;
596 uint8_t int_width = v.
width();
597 if (int_width == 0) {
throw std::logic_error(
"util::set_to_value can not be performed with int_width=0!"); }
602 size_type words = (v.bit_size() + 63) >> 6;
603 size_type word_pos = ((it - v.begin()) * int_width) >> 6;
604 uint8_t pos_in_word = ((it - v.begin()) * int_width) - (word_pos << 6);
605 uint8_t cyclic_shift = word_pos % n;
607 uint64_t * data = v.
data() + word_pos;
612 while (word_pos < words)
614 for (; cyclic_shift < n && word_pos < words; ++cyclic_shift, ++word_pos) { *(++data) = vec[cyclic_shift]; }
620template <
class t_
int_vec>
623 std::iota(v.begin(), v.end(), 0ULL);
626template <
class t_
int_vec>
629 const uint64_t * data = v.data();
630 if (v.empty())
return 0;
637template <
class t_
int_vec>
640 const uint64_t * data = v.data();
641 if (v.empty())
return 0;
642 uint64_t carry = 0, oldcarry = 0;
649 if (v.bit_size() & 0x3F)
656template <
class t_
int_vec>
659 const uint64_t * data = v.data();
660 if (v.empty())
return 0;
661 uint64_t carry = 1, oldcarry = 1;
668 if (v.bit_size() & 0x3F)
675template <
class t_
int_vec>
678 uint64_t pos = idx >> 6;
679 uint64_t node = v.data()[pos];
680 node >>= (idx & 0x3F);
681 if (node) {
return idx +
bits::lo(node); }
685 while ((pos << 6) < v.bit_size())
687 if (v.data()[pos]) {
return (pos << 6) |
bits::lo(v.data()[pos]); }
694template <
class t_
int_vec>
697 uint64_t pos = idx >> 6;
698 uint64_t node = v.data()[pos];
699 node <<= 63 - (idx & 0x3F);
700 if (node) {
return bits::hi(node) + (pos << 6) - (63 - (idx & 0x3F)); }
704 while ((pos << 6) < v.bit_size())
706 if (v.data()[pos]) {
return (pos << 6) |
bits::hi(v.data()[pos]); }
716 std::stringstream ss;
717 ss << std::setw(w) << t;
722std::string util::to_latex_string(
const T & 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_type size() const noexcept
The number of elements in the int_vector.
const uint64_t * data() const noexcept
Pointer to the raw data of 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)
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 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)
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)
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.
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)
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.
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(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 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.