SDSL  3.0.0
Succinct Data Structure Library
util.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
8 #ifndef INCLUDED_SDSL_UTIL
9 #define INCLUDED_SDSL_UTIL
10 
11 #include <algorithm>
12 #include <atomic>
13 #include <cassert>
14 #include <chrono>
15 #include <cstdlib>
16 #include <ctime> // for rand initialization
17 #include <functional> // for class_to_hash
18 #include <iomanip>
19 #include <iosfwd> // forward declaration of ostream
20 #include <mutex>
21 #include <numeric>
22 #include <random>
23 #include <sstream> // for to_string method
24 #include <stdexcept> // for std::logic_error
25 #include <stdint.h> // for uint64_t uint32_t declaration
26 #include <string.h> // for strlen and strdup
27 #include <string>
28 #include <typeinfo> // for typeid
29 
30 #include <sdsl/bits.hpp>
31 #include <sdsl/config.hpp> // for constants
32 #include <sdsl/ram_fs.hpp>
33 #include <sdsl/sfstream.hpp>
34 
35 // macros to transform a defined name to a string
36 #define SDSL_STR(x) #x
37 #define SDSL_XSTR(s) SDSL_STR(s)
38 
39 #include <iomanip>
40 #include <string>
41 #include <typeinfo>
42 #include <vector>
43 
44 #include <sys/stat.h> // for file_size
45 #include <sys/types.h> // for file_size
46 #include <type_traits>
47 
48 #ifndef MSVC_COMPILER
49 #include <cxxabi.h>
50 #endif
51 
52 #ifndef _WIN32
53 #include <libgen.h> // for basename
54 #include <unistd.h> // for getpid, file_size, clock_gettime
55 
56 #include <sys/resource.h> // for struct rusage
57 #include <sys/time.h> // for struct timeval
58 #else
59 #include <iso646.h>
60 #include <process.h>
61 #endif
62 
64 namespace sdsl
65 {
66 
67 template <uint8_t>
68 class int_vector; // forward declaration
69 
71 namespace util
72 {
73 
74 //============= Debug information =========================
75 
76 SDSL_UNUSED static bool verbose = false;
77 
78 inline void set_verbose()
79 {
80  verbose = true;
81 }
82 
83 //============ Manipulating int_vectors ===================
84 
86 
91 template <class t_int_vec>
92 void set_random_bits(t_int_vec & v, int seed = 0);
94 template <class t_int_vec>
95 void _set_zero_bits(t_int_vec & v);
97 template <class t_int_vec>
98 void _set_one_bits(t_int_vec & v);
99 
101 
105 template <class t_int_vec>
106 void bit_compress(t_int_vec & v);
107 
109 template <class t_int_vec>
110 void expand_width(t_int_vec & v, uint8_t new_width);
111 
113 template <class t_int_vec>
114 void mod(t_int_vec & v, typename t_int_vec::size_type m);
115 
116 inline void cyclic_shifts(uint64_t * vec, uint8_t & n, uint64_t k, uint8_t int_width);
117 
119 
125 template <class t_int_vec>
126 void set_to_value(t_int_vec & v, uint64_t k);
127 
129 
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);
138 
140 template <class t_int_vec>
141 void set_to_id(t_int_vec & v);
142 
144 
147 template <class t_int_vec>
148 typename t_int_vec::size_type cnt_one_bits(const t_int_vec & v);
149 
151 
153 template <class t_int_vec>
154 typename t_int_vec::size_type cnt_onezero_bits(const t_int_vec & v);
155 
157 
159 template <class t_int_vec>
160 typename t_int_vec::size_type cnt_zeroone_bits(const t_int_vec & v);
161 
163 
168 template <class t_int_vec>
169 typename t_int_vec::size_type next_bit(const t_int_vec & v, uint64_t idx);
170 
172 
177 template <class t_int_vec>
178 typename t_int_vec::size_type prev_bit(const t_int_vec & v, uint64_t idx);
179 
180 //============= Handling files =============================
181 
183 
186 inline size_t file_size(const std::string & file)
187 {
188  if (is_ram_file(file)) { return ram_fs::file_size(file); }
189  else
190  {
191  struct stat fs;
192  stat(file.c_str(), &fs);
193  return fs.st_size;
194  }
195 }
196 
198 
201 inline std::string basename(std::string file)
202 {
203  file = disk_file_name(file); // remove RAM-prefix
204 #ifdef _WIN32
205  char * c = _strdup((const char *)file.c_str());
206  char file_name[_MAX_FNAME] = { 0 };
207 #ifdef MSVC_COMPILER
208  ::_splitpath_s(c, NULL, 0, NULL, NULL, file_name, _MAX_FNAME, NULL, 0);
209 #else
210  ::_splitpath(c, NULL, NULL, file_name, NULL);
211 #endif
212  std::string res(file_name);
213 #else
214  char * c = strdup((const char *)file.c_str());
215  std::string res = std::string(::basename(c));
216 #endif
217  free(c);
218  return res;
219 }
220 
222 
225 inline std::string dirname(std::string file)
226 {
227  bool ram_file = is_ram_file(file);
228  file = disk_file_name(file); // remove RAM-prefix
229 #ifdef _WIN32
230  char * c = _strdup((const char *)file.c_str());
231  char dir_name[_MAX_DIR] = { 0 };
232  char drive[_MAX_DRIVE] = { 0 };
233 #ifdef MSVC_COMPILER
234  ::_splitpath_s(c, drive, _MAX_DRIVE, dir_name, _MAX_DIR, NULL, 0, NULL, 0);
235 #else
236  ::_splitpath(c, drive, dir_name, NULL, NULL);
237 #endif
238  std::string res = std::string(drive) + std::string(dir_name);
239 #else
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())
245  {
246  if (*next_it != '/' or *it != '/') { *(++it) = *next_it; }
247  ++next_it;
248  }
249  res.resize(it - res.begin() + 1);
250 #endif
251  free(c);
252  if (ram_file)
253  {
254  if ("." == res) { res = ram_file_name(""); }
255  else if ("/" == res)
256  {
257  res = ram_file_name(res);
258  }
259  }
260  return res;
261 }
262 
264 
267 inline std::string demangle(const std::string & name)
268 {
269 #if 1
270  char buf[4096];
271  size_t size = 4096;
272  int status = 0;
273  abi::__cxa_demangle(name.c_str(), buf, &size, &status);
274  if (status == 0) return std::string(buf);
275  return name;
276 #else
277  return name;
278 #endif
279 }
280 
282 inline std::string demangle2(const std::string & name)
283 {
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");
289 
290  for (size_t k = 0; k < words_to_delete.size(); ++k)
291  {
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))
294  {
295  result.erase(i, w.length());
296  ++i;
297  }
298  }
299  size_t index = 0;
300  std::string to_replace = "int_vector<1>";
301  while ((index = result.find(to_replace, index)) != std::string::npos)
302  {
303  result.replace(index, to_replace.size(), "bit_vector");
304  }
305  return result;
306 }
307 
309 template <typename T>
310 std::string to_string(const T & t, int w);
311 
313 template <class T>
314 uint64_t hashvalue_of_classname(const T &)
315 {
316  std::hash<std::string> str_hash;
317  return str_hash(sdsl::util::demangle2(typeid(T).name()));
318 }
319 
321 template <class T>
322 std::string class_to_hash(const T & t)
323 {
324  return to_string(hashvalue_of_classname(t));
325 }
326 
327 template <class T>
328 std::string class_name(const T & t)
329 {
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); }
333  return result;
334 }
335 
336 // convert an errno number to a readable msg
337 inline char * str_from_errno()
338 {
339 #ifdef MSVC_COMPILER
340 #pragma warning(disable : 4996)
341  return strerror(errno);
342 #pragma warning(default : 4996)
343 #else
344  return strerror(errno);
345 #endif
346 }
347 
348 struct _id_helper_struct
349 {
350  uint64_t id = 0;
351 };
352 
353 extern inline uint64_t _id_helper()
354 {
355  static _id_helper_struct data;
356  return data.id++;
357 }
358 
360 inline uint64_t pid()
361 {
362 #ifdef MSVC_COMPILER
363  return _getpid();
364 #else
365  return getpid();
366 #endif
367 }
368 
370 inline uint64_t id()
371 {
372  return _id_helper();
373 }
374 
375 template <typename T>
376 std::string to_latex_string(const T & t);
377 
378 inline std::string to_latex_string(unsigned char c)
379 {
380  if (c == '_')
381  return "\\_";
382  else if (c == '\0')
383  return "\\$";
384  else
385  return to_string(c);
386 }
387 
389 inline void delete_all_files(tMSS & file_map)
390 {
391  for (auto file_pair : file_map) { sdsl::remove(file_pair.second); }
392  file_map.clear();
393 }
394 
396 
399 template <class T>
400 void clear(T & x)
401 {
402  T y;
403  x = std::move(y);
404 }
405 
407 
415 template <class S, class P>
416 void swap_support(S & s1, S & s2, const P * p1, const P * p2)
417 {
418  std::swap(s1, s2);
419  s1.set_vector(p1);
420  s2.set_vector(p2);
421 }
422 
424 
427 template <class S, class X>
428 void init_support(S & s, const X * x)
429 {
430  S temp(x); // generate a temporary support object
431  s = std::move(temp); // swap its content with the target object
432  s.set_vector(x); // set the support object's pointer to x
433 }
434 
436 /*
437  */
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)
440 {
441  mask = (1 << log_s) - 1;
442  t_int_vec rands(1 << log_s, 0);
443  set_random_bits(rands, seed);
444  if (mod > 0) { util::mod(rands, mod); }
445  return rands;
446 }
447 
449 /* static_assert(is_regular<YOUR_TYPE>::value);
450  * Code is from a talk of Aerix Consulting
451  */
452 template <typename T>
453 struct is_regular
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>
459 {};
460 
461 } // end namespace util
462 
463 //==================== Template functions ====================
464 
465 template <class t_int_vec>
466 void util::set_random_bits(t_int_vec & v, int seed)
467 {
468  std::mt19937_64 rng;
469  if (0 == seed) { rng.seed(std::chrono::system_clock::now().time_since_epoch().count() + util::id()); }
470  else
471  rng.seed(seed);
472 
473  uint64_t * data = v.data();
474  if (v.empty()) return;
475  *data = rng();
476  for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i) { *(++data) = rng(); }
477 }
478 
479 // all elements of vector v modulo m
480 template <class t_int_vec>
481 void util::mod(t_int_vec & v, typename t_int_vec::size_type m)
482 {
483  for (typename t_int_vec::size_type i = 0; i < v.size(); ++i) { v[i] = v[i] % m; }
484 }
485 
486 template <class t_int_vec>
487 void util::bit_compress(t_int_vec & v)
488 {
489  auto max_elem = std::max_element(v.begin(), v.end());
490  uint64_t max = 0;
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)
495  {
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;
500  for (typename t_int_vec::size_type i = 0; i < v.size(); ++i)
501  {
502  uint64_t x = bits::read_int_and_move(read_data, read_offset, old_width);
503  bits::write_int_and_move(write_data, x, write_offset, min_width);
504  }
505  v.bit_resize(v.size() * min_width);
506  v.width(min_width);
507  // v.shrink_to_fit(); TODO(cpockrandt): comment in once int_vector_mapper has the same interface
508  }
509 }
510 
511 template <class t_int_vec>
512 void util::expand_width(t_int_vec & v, uint8_t new_width)
513 {
514  uint8_t old_width = v.width();
515  typename t_int_vec::size_type n = v.size();
516  if (new_width > old_width)
517  {
518  if (n > 0)
519  {
520  typename t_int_vec::size_type i, old_pos, new_pos;
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)
525  {
526  v.set_int(new_pos, v.get_int(old_pos, old_width), new_width);
527  }
528  }
529  v.width(new_width);
530  }
531 }
532 
533 template <class t_int_vec>
534 void util::_set_zero_bits(t_int_vec & v)
535 {
536  std::for_each(v.data(), v.data() + ((v.bit_size() + 63) >> 6), [](uint64_t & value) { value = 0ULL; });
537 }
538 
539 template <class t_int_vec>
540 void util::_set_one_bits(t_int_vec & v)
541 {
542  std::for_each(v.data(), v.data() + ((v.bit_size() + 63) >> 6), [](uint64_t & value) { value = -1ULL; });
543 }
544 
545 inline void util::cyclic_shifts(uint64_t * vec, uint8_t & n, uint64_t k, uint8_t int_width)
546 {
547  n = 0;
548  vec[0] = 0;
549  uint8_t offset = 0;
550  k &= 0xFFFFFFFFFFFFFFFFULL >> (64 - int_width);
551  do { // loop terminates after at most 64 iterations
552  vec[n] |= k << offset;
553  offset += int_width;
554  if (offset >= 64)
555  {
556  ++n;
557  if (int_width == 64) return;
558  assert(int_width - (offset - 64) < 64);
559  vec[n] = k >> (int_width - (offset - 64));
560  offset -= 64;
561  }
562  } while (offset != 0);
563 }
564 
565 template <class t_int_vec>
566 void util::set_to_value(t_int_vec & v, uint64_t k)
567 {
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!"); }
572  if (0 == k)
573  {
574  _set_zero_bits(v);
575  return;
576  }
577  if (bits::lo_set[int_width] == k)
578  {
579  _set_one_bits(v);
580  return;
581  }
582  uint8_t n;
583  uint64_t vec[65];
584  util::cyclic_shifts(vec, n, k, int_width);
585 
586  typename t_int_vec::size_type n64 = (v.bit_size() + 63) >> 6;
587  for (typename t_int_vec::size_type i = 0; i < n64;)
588  {
589  for (uint64_t ii = 0; ii < n and i < n64; ++ii, ++i) { *(data++) = vec[ii]; }
590  }
591 }
592 
593 template <class t_int_vec, class t_int_vec_iterator>
594 void util::set_to_value(t_int_vec & v, uint64_t k, t_int_vec_iterator it)
595 {
596  typedef typename t_int_vec::size_type size_type;
597 
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!"); }
601  uint8_t n;
602  uint64_t vec[65];
603  util::cyclic_shifts(vec, n, k, int_width);
604 
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); // ((it - v.begin()) * int_width) % 64
608  uint8_t cyclic_shift = word_pos % n;
609 
610  uint64_t * data = v.data() + word_pos;
611  *(data) &= bits::lo_set[pos_in_word]; // unset first bits
612  *(data) |= bits::lo_unset[pos_in_word] & vec[cyclic_shift++]; // set last bits
613  ++word_pos;
614 
615  while (word_pos < words)
616  {
617  for (; cyclic_shift < n && word_pos < words; ++cyclic_shift, ++word_pos) { *(++data) = vec[cyclic_shift]; }
618  cyclic_shift = 0;
619  }
620 }
621 
623 template <class t_int_vec>
624 void util::set_to_id(t_int_vec & v)
625 {
626  std::iota(v.begin(), v.end(), 0ULL);
627 }
628 
629 template <class t_int_vec>
630 typename t_int_vec::size_type util::cnt_one_bits(const t_int_vec & v)
631 {
632  const uint64_t * data = v.data();
633  if (v.empty()) return 0;
634  typename t_int_vec::size_type result = bits::cnt(*data);
635  for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i) { result += bits::cnt(*(++data)); }
636  if (v.bit_size() & 0x3F) { result -= bits::cnt((*data) & (~bits::lo_set[v.bit_size() & 0x3F])); }
637  return result;
638 }
639 
640 template <class t_int_vec>
641 typename t_int_vec::size_type util::cnt_onezero_bits(const t_int_vec & v)
642 {
643  const uint64_t * data = v.data();
644  if (v.empty()) return 0;
645  uint64_t carry = 0, oldcarry = 0;
646  typename t_int_vec::size_type result = bits::cnt10(*data, carry);
647  for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
648  {
649  oldcarry = carry;
650  result += bits::cnt10(*(++data), carry);
651  }
652  if (v.bit_size() & 0x3F)
653  { // if bit_size is not a multiple of 64, subtract the counts of the additional bits
654  result -= bits::cnt(bits::map10(*data, oldcarry) & bits::lo_unset[v.bit_size() & 0x3F]);
655  }
656  return result;
657 }
658 
659 template <class t_int_vec>
660 typename t_int_vec::size_type util::cnt_zeroone_bits(const t_int_vec & v)
661 {
662  const uint64_t * data = v.data();
663  if (v.empty()) return 0;
664  uint64_t carry = 1, oldcarry = 1;
665  typename t_int_vec::size_type result = bits::cnt01(*data, carry);
666  for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
667  {
668  oldcarry = carry;
669  result += bits::cnt01(*(++data), carry);
670  }
671  if (v.bit_size() & 0x3F)
672  { // if bit_size is not a multiple of 64, subtract the counts of the additional bits
673  result -= bits::cnt(bits::map01(*data, oldcarry) & bits::lo_unset[v.bit_size() & 0x3F]);
674  }
675  return result;
676 }
677 
678 template <class t_int_vec>
679 typename t_int_vec::size_type util::next_bit(const t_int_vec & v, uint64_t idx)
680 {
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); }
685  else
686  {
687  ++pos;
688  while ((pos << 6) < v.bit_size())
689  {
690  if (v.data()[pos]) { return (pos << 6) | bits::lo(v.data()[pos]); }
691  ++pos;
692  }
693  return v.bit_size();
694  }
695 }
696 
697 template <class t_int_vec>
698 typename t_int_vec::size_type util::prev_bit(const t_int_vec & v, uint64_t idx)
699 {
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)); }
704  else
705  {
706  --pos;
707  while ((pos << 6) < v.bit_size())
708  {
709  if (v.data()[pos]) { return (pos << 6) | bits::hi(v.data()[pos]); }
710  --pos;
711  }
712  return v.bit_size();
713  }
714 }
715 
716 template <typename T>
717 std::string util::to_string(const T & t, int w)
718 {
719  std::stringstream ss;
720  ss << std::setw(w) << t;
721  return ss.str();
722 }
723 
724 template <typename T>
725 std::string util::to_latex_string(const T & t)
726 {
727  return to_string(t);
728 }
729 
730 } // end namespace sdsl
731 #endif
bits.hpp contains the sdsl::bits class.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:590
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
Definition: int_vector.hpp:619
size_type size() const noexcept
The number of elements in the int_vector.
#define SDSL_UNUSED
Definition: config.hpp:13
int_vector ::size_type size_type
size_t file_size(const std::string &name)
Get the file size.
Definition: ram_fs.hpp:49
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)
Definition: util.hpp:186
Returns the directory of a file A trailing will be removed std::string dirname(std::string file)
Definition: util.hpp:225
Returns the basename of a file std::string basename(std::string file)
Definition: util.hpp:201
uint64_t id()
void set_random_bits(t_int_vec &v, int seed=0)
Sets all bits of the int_vector to pseudo-random bits.
Definition: util.hpp:466
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.
Definition: util.hpp:481
void expand_width(t_int_vec &v, uint8_t new_width)
Expands the integer width to new_width >= v.width()
Definition: util.hpp:512
void cyclic_shifts(uint64_t *vec, uint8_t &n, uint64_t k, uint8_t int_width)
Definition: util.hpp:545
void set_verbose()
Definition: util.hpp:78
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)
uint64_t pid()
void bit_compress(t_int_vec &v)
Bit compress the int_vector.
Definition: util.hpp:487
void _set_one_bits(t_int_vec &v)
Sets all bits of the int_vector to 1-bits.
Definition: util.hpp:540
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition: util.hpp:566
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.
Definition: util.hpp:534
Namespace for the succinct data structure library.
bool is_ram_file(const std::string &file)
Determines if the given file is a RAM-file.
Definition: ram_fs.hpp:158
std::map< std::string, std::string > tMSS
Definition: config.hpp:50
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.
Definition: ram_fs.hpp:174
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
Definition: int_vector.hpp:970
std::string disk_file_name(const std::string &file)
Returns for a RAM-file the corresponding disk file name.
Definition: ram_fs.hpp:184
int remove(const std::string &)
Remove a file.
Definition: ram_fs.hpp:194
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
ram_fs.hpp
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.
Definition: bits.hpp:220
static SDSL_CONSTEXPR uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
Definition: bits.hpp:566
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.
Definition: bits.hpp:588
static SDSL_CONSTEXPR uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
Definition: bits.hpp:580
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.
Definition: bits.hpp:752
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.
Definition: bits.hpp:696
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.
Definition: bits.hpp:197
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:661
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.
Definition: bits.hpp:805
static SDSL_CONSTEXPR uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:494
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.
Definition: bits.hpp:574