SDSL  3.0.0
Succinct Data Structure Library
int_vector.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_INT_VECTOR
9 #define INCLUDED_SDSL_INT_VECTOR
10 
11 #include <cassert>
12 #include <cinttypes>
13 #include <cstddef>
14 #include <cstdlib>
15 #include <cstring> // for memcpy
16 #include <ctime> // for rand initialization
17 #include <ios>
18 #include <iosfwd> // forward declaration of ostream
19 #include <iostream> // for cerr
20 #include <istream>
21 #include <iterator>
22 #include <ostream>
23 #include <stdexcept> // for exceptions
24 #include <string>
25 #include <typeinfo>
26 #include <vector>
27 
28 #include <sdsl/bits.hpp>
29 #include <sdsl/config.hpp>
30 #include <sdsl/io.hpp>
32 #include <sdsl/ram_fs.hpp>
33 #include <sdsl/sfstream.hpp>
34 #include <sdsl/structure_tree.hpp>
35 #include <sdsl/uintx_t.hpp>
36 #include <sdsl/util.hpp>
37 
38 #include <initializer_list>
39 #include <type_traits>
40 
42 namespace sdsl
43 {
44 
46 
47 template <uint8_t t_width = 0>
48 class int_vector;
49 
50 template <class int_vector_type>
51 class mm_item;
52 
55 
56 template <class t_int_vector>
58 
59 template <class t_int_vector>
61 
62 template <class t_int_vector>
64 
65 template <class t_int_vector>
67 
68 template <uint8_t t_width, std::ios_base::openmode t_mode>
69 class int_vector_mapper;
70 
71 template <uint8_t b, uint8_t t_patter_len> // forward declaration
72 class rank_support_v;
73 
74 class rank_support;
75 
76 class select_support;
77 
78 template <uint8_t t_bit_pattern, uint8_t t_pattern_len>
79 class select_support_mcl;
80 
81 namespace coder
82 {
83 template <typename T>
84 class fibonacci;
85 template <typename T>
86 class elias_delta;
87 template <typename T>
88 class elias_gamma;
89 template <uint8_t t_width>
90 class comma;
91 } // namespace coder
92 
93 template <uint8_t t_width>
95 {
96  typedef iv_tag type;
97 };
98 
99 template <>
101 {
102  typedef bv_tag type;
103 };
104 
105 template <uint8_t t_width>
107 {
108  typedef uint64_t value_type;
111  typedef uint64_t const_reference;
112  typedef uint8_t int_width_type;
115 
116  static iterator begin(int_vector_type * v, uint64_t *) noexcept { return iterator(v, 0); }
117  static iterator end(int_vector_type * v, uint64_t *, int_vector_size_type) noexcept
118  {
119  return iterator(v, v->size() * v->width());
120  }
121  static const_iterator begin(const int_vector_type * v, const uint64_t *) noexcept { return const_iterator(v, 0); }
122  static const_iterator end(const int_vector_type * v, const uint64_t *, int_vector_size_type) noexcept
123  {
124  return const_iterator(v, v->size() * v->width());
125  }
126 
127  static void set_width(uint8_t new_width, int_width_type & width) noexcept
128  {
129  if (t_width == 0)
130  {
131  if (0 < new_width and new_width <= 64)
132  width = new_width;
133  else
134  width = 64;
135  }
136  }
137 };
138 
139 template <>
141 {
142  typedef uint64_t value_type;
144  typedef uint64_t & reference;
145  typedef uint64_t const_reference;
146  typedef uint8_t int_width_type;
147  typedef uint64_t * iterator;
148  typedef const uint64_t * const_iterator;
149 
150  static iterator begin(int_vector_type *, uint64_t * begin) noexcept { return begin; }
151  static iterator end(int_vector_type *, uint64_t * begin, int_vector_size_type size) noexcept
152  {
153  return begin + size;
154  }
155  static const_iterator begin(const int_vector_type *, const uint64_t * begin) noexcept { return begin; }
156  static const_iterator end(const int_vector_type *, const uint64_t * begin, int_vector_size_type size) noexcept
157  {
158  return begin + size;
159  }
160 
161  static void set_width(uint8_t, int_width_type) noexcept {}
162 };
163 
164 template <>
166 {
167  typedef uint32_t value_type;
169  typedef uint32_t & reference;
170  typedef uint32_t const_reference;
171  typedef uint8_t int_width_type;
172  typedef uint32_t * iterator;
173  typedef const uint32_t * const_iterator;
174 
175  static iterator begin(int_vector_type *, uint64_t * begin) noexcept { return (uint32_t *)begin; }
176  static iterator end(int_vector_type *, uint64_t * begin, int_vector_size_type size) noexcept
177  {
178  return ((uint32_t *)begin) + size;
179  }
180  static const_iterator begin(const int_vector_type *, const uint64_t * begin) noexcept { return (uint32_t *)begin; }
181  static const_iterator end(const int_vector_type *, const uint64_t * begin, int_vector_size_type size) noexcept
182  {
183  return ((uint32_t *)begin) + size;
184  }
185 
186  static void set_width(uint8_t, int_width_type) noexcept {}
187 };
188 
189 template <>
191 {
192  typedef uint16_t value_type;
194  typedef uint16_t & reference;
195  typedef uint16_t const_reference;
196  typedef uint8_t int_width_type;
197  typedef uint16_t * iterator;
198  typedef const uint16_t * const_iterator;
199 
200  static iterator begin(int_vector_type *, uint64_t * begin) noexcept { return (uint16_t *)begin; }
201  static iterator end(int_vector_type *, uint64_t * begin, int_vector_size_type size) noexcept
202  {
203  return ((uint16_t *)begin) + size;
204  }
205  static const_iterator begin(const int_vector_type *, const uint64_t * begin) noexcept { return (uint16_t *)begin; }
206  static const_iterator end(const int_vector_type *, const uint64_t * begin, int_vector_size_type size) noexcept
207  {
208  return ((uint16_t *)begin) + size;
209  }
210 
211  static void set_width(uint8_t, int_width_type) noexcept {}
212 };
213 
214 template <>
216 {
217  typedef uint8_t value_type;
219  typedef uint8_t & reference;
220  typedef uint8_t const_reference;
221  typedef uint8_t int_width_type;
222  typedef uint8_t * iterator;
223  typedef const uint8_t * const_iterator;
224 
225  static iterator begin(int_vector_type *, uint64_t * begin) noexcept { return (uint8_t *)begin; }
226  static iterator end(int_vector_type *, uint64_t * begin, int_vector_size_type size) noexcept
227  {
228  return ((uint8_t *)begin) + size;
229  }
230  static const_iterator begin(const int_vector_type *, const uint64_t * begin) noexcept { return (uint8_t *)begin; }
231  static const_iterator end(const int_vector_type *, const uint64_t * begin, int_vector_size_type size) noexcept
232  {
233  return ((uint8_t *)begin) + size;
234  }
235 
236  static void set_width(uint8_t, int_width_type) noexcept {}
237 };
238 
240 
251 template <uint8_t t_width>
253 {
254  private:
255  static_assert(t_width <= 64, "int_vector: width of must be at most 64bits.");
256 
257  public:
264  typedef const value_type * const_pointer;
265  typedef ptrdiff_t difference_type;
273 
274  friend struct int_vector_trait<t_width>;
275  friend class int_vector_iterator_base<int_vector>;
276  friend class int_vector_iterator<int_vector>;
278  template <uint8_t, std::ios_base::openmode>
279  friend class int_vector_mapper;
280  template <typename T>
281  friend class coder::elias_delta;
282  template <typename T>
283  friend class coder::elias_gamma;
284  template <typename T>
285  friend class coder::fibonacci;
286  template <uint8_t>
287  friend class coder::comma;
288  friend class memory_manager;
289  static constexpr uint8_t fixed_int_width = t_width;
290  float growth_factor = 1.5;
291  // see the explanation in the documentation of FBVector on different growth factors
292  // https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#memory-handling
293 
294  private:
295  size_type m_size;
296  size_type m_capacity;
297  uint64_t * m_data;
298  int_width_type m_width;
299 
300  // Hidden, since number of bits (size) does not go well together with int value.
301  void bit_resize(const size_type size, const value_type value);
302 
303  void amortized_resize(const size_type size)
304  {
305  assert(growth_factor > 1.0);
306  size_type bit_size = size * m_width;
307  if (bit_size > m_capacity || m_data == nullptr)
308  {
309  // start with 64 bit if vector has no capacity
310  size_type tmp_capacity = m_capacity == 0 ? 64 : m_capacity;
311  // find smallest x s.t. m_capacity * 1.5 ** x >= size
312  auto resize_factor = pow(growth_factor,
313  std::ceil(std::log((bit_size + tmp_capacity - 1) / tmp_capacity) /
314  std::log(growth_factor)));
315  size_type new_capacity = std::ceil(tmp_capacity * resize_factor);
316  memory_manager::resize(*this, new_capacity);
317  }
318  m_size = size * m_width;
319  }
320 
321  // The number of 64-bit words used by the int_vector.
322  size_type bit_data_size() const { return (m_size + 63) >> 6; }
323 
324  public:
326 
332  int_vector(size_type size, value_type default_value, uint8_t int_width = t_width);
333 
335  explicit int_vector(size_type size = 0)
336  : int_vector(size, static_cast<value_type>(0), t_width)
337  {}
339  int_vector(std::initializer_list<value_type> il)
340  : int_vector(0, 0)
341  {
342  assign(il);
343  }
344 
346 
349  template <typename input_iterator_t>
350  int_vector(typename std::enable_if<std::is_base_of<std::input_iterator_tag,
351  typename std::iterator_traits<input_iterator_t>::iterator_category>::
352  value,
353  input_iterator_t>::type first,
354  input_iterator_t last)
355  : int_vector(0, 0)
356  {
357  assign(first, last);
358  }
359 
361 
363  void clear() noexcept { m_size = 0; }
364 
366 
369  {
370  iterator it_nonconst = begin() + (it - cbegin());
371  std::copy(it_nonconst + 1, end(), it_nonconst);
372  resize(size() - 1);
373  return it_nonconst;
374  }
375 
377 
381  {
382  iterator first_nonconst = begin() + (first - cbegin());
383  iterator last_nonconst = begin() + (last - cbegin());
384  std::copy(last_nonconst, end(), first_nonconst);
385  resize(size() - (last - first));
386  return first_nonconst;
387  }
388 
390 
393  template <class... Args>
394  iterator emplace(const_iterator it, Args &&... args)
395  {
396  return insert(it, 1, value_type(std::forward<Args>(args)...));
397  }
398 
400 
403  iterator insert(const_iterator it, value_type value) { return insert(it, 1, value); }
404 
406 
411  {
412  size_type pos = it - cbegin();
413  amortized_resize(size() + n);
414  iterator it_new = begin() + pos;
415  std::copy_backward(it_new, end() - n, end());
416  std::fill_n(it_new, n, value);
417  return it_new;
418  }
419 
421 
424  iterator insert(const_iterator it, std::initializer_list<value_type> il)
425  {
426  return insert(it, il.begin(), il.end());
427  }
428 
430 
434  template <typename input_iterator_t>
435  typename std::enable_if<std::is_base_of<std::input_iterator_tag,
436  typename std::iterator_traits<input_iterator_t>::iterator_category>::value,
437  iterator>::type
438  insert(const_iterator it, input_iterator_t first, input_iterator_t last)
439  {
440  size_type pos = it - cbegin();
441  amortized_resize(size() + last - first);
442  iterator it_new = begin() + pos;
443  std::copy_backward(it_new, end() - (last - first), end());
444  std::copy(first, last, it_new);
445  return it_new;
446  }
447 
449  reference front() noexcept { return *begin(); }
450 
452  const_reference front() const noexcept { return *cbegin(); }
453 
455  reference back() noexcept { return *(end() - 1); }
456 
458  const_reference back() const noexcept { return *(cend() - 1); }
459 
461 
463  template <class... Args>
464  void emplace_back(Args &&... args)
465  {
466  push_back(value_type(std::forward<Args>(args)...));
467  }
468 
470 
472  void push_back(value_type value)
473  {
474  amortized_resize(size() + 1);
475  *(end() - 1) = value;
476  }
477 
479  void pop_back() { resize(size() - 1); }
480 
483 
485  int_vector(const int_vector & v);
486 
489 
491 
494  void assign(size_type size, value_type default_value)
495  {
496  bit_resize(size * m_width);
497  util::set_to_value(*this, default_value); // new initialization
498  }
499 
501 
503  void assign(std::initializer_list<value_type> il)
504  {
505  bit_resize(il.size() * m_width);
506  size_type idx = 0;
507  for (auto x : il) { (*this)[idx++] = x; }
508  }
509 
511 
514  template <typename input_iterator_t>
515  void assign(input_iterator_t first, input_iterator_t last)
516  {
517  assert(first <= last);
518  bit_resize((last - first) * m_width);
519  size_type idx = 0;
520  while (first < last) { (*this)[idx++] = *(first++); }
521  }
522 
524  bool empty() const noexcept { return 0 == m_size; }
525 
527  void swap(int_vector & v) noexcept { std::swap(v, *this); }
528 
530  void shrink_to_fit() { memory_manager::resize(*this, m_size); }
531 
533 
536  {
537  if (capacity * m_width > m_capacity || m_data == nullptr) { memory_manager::resize(*this, capacity * m_width); }
538  }
539 
542 
545  void resize(const size_type size) { resize(size, 0); }
546 
548 
551  void resize(const size_type size, const value_type value) { bit_resize(size * m_width, value); }
552 
554 
556  void bit_resize(const size_type size);
557 
559 
561  inline size_type size() const noexcept;
562 
564 
566  static size_type max_size() noexcept { return ((size_type)1) << (sizeof(size_type) * 8 - 6); }
567 
569 
571  size_type bit_size() const noexcept { return m_size; }
572 
574 
578  inline size_type capacity() const noexcept;
579 
581 
585  size_type bit_capacity() const noexcept { return m_capacity; }
586 
588 
590  const uint64_t * data() const noexcept { return m_data; }
591 
593 
595  uint64_t * data() noexcept { return m_data; }
596 
598 
603  value_type get_int(size_type idx, const uint8_t len = 64) const;
604 
606 
613  void set_int(size_type idx, value_type x, const uint8_t len = 64);
614 
616 
619  uint8_t width() const noexcept { return m_width; }
620 
622 
626  void width(uint8_t new_width) noexcept { int_vector_trait<t_width>::set_width(new_width, m_width); }
627 
628  // Write data (without header) to a stream.
629  size_type write_data(std::ostream & out) const;
630 
632 
635  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
636 
638  void load(std::istream & in);
639 
640  /* For cereal we need to define different versions of the load and save function depending on whether we want
641  * binary data or text (XML/JSON) data.
642  * See https://github.com/USCiLab/cereal/blob/master/include/cereal/types/vector.hpp for an example.
643  */
644 
646  template <typename archive_t>
647  inline typename std::enable_if<!cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
648  archive_t>::value,
649  void>::type
650  CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
651 
653  template <typename archive_t>
654  inline typename std::enable_if<cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
655  archive_t>::value,
656  void>::type
657  CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
658 
660  template <typename archive_t>
661  inline typename std::enable_if<!cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
662  archive_t>::value,
663  void>::type
664  CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
665 
667  template <typename archive_t>
668  inline typename std::enable_if<cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
669  archive_t>::value,
670  void>::type
671  CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
672 
674 
677  inline reference operator[](const size_type & i) noexcept;
678 
680 
683  inline const_reference operator[](const size_type & i) const noexcept;
684 
686 
689  reference at(const size_type & i) { return (*this)[i]; }
690 
692 
695  const_reference at(const size_type & i) const { return (*this)[i]; }
696 
698 
701 
704 
706 
710  bool operator==(const int_vector<t_width> & v) const noexcept
711  {
712  if (bit_size() != v.bit_size()) return false;
713  if (empty()) return true;
714  const uint64_t * data1 = v.data();
715  const uint64_t * data2 = data();
716  for (size_type i = 0; i < bit_data_size() - 1; ++i)
717  {
718  if (*(data1++) != *(data2++)) return false;
719  }
720  uint8_t l = 64 - ((bit_data_size() << 6) - m_size);
721  return ((*data1) & bits::lo_set[l]) == ((*data2) & bits::lo_set[l]);
722  }
723 
725 
731  template <class container>
732  friend bool operator==(const int_vector<t_width> & lhs, const container & rhs) noexcept
733  {
734  return std::equal(lhs.begin(), lhs.end(), rhs.begin());
735  }
736 
738 
744  template <uint8_t t_width2>
745  bool operator!=(const int_vector<t_width2> & v) const noexcept
746  {
747  return !(*this == v);
748  }
749 
751 
756  bool operator<(const int_vector & v) const noexcept;
757 
759 
763  bool operator>(const int_vector & v) const noexcept;
764 
766  bool operator<=(const int_vector & v) const noexcept;
767 
769  bool operator>=(const int_vector & v) const noexcept;
770 
773 
776 
779 
781 
783  iterator begin() noexcept { return int_vector_trait<t_width>::begin(this, m_data); }
784 
786 
788  iterator end() noexcept { return int_vector_trait<t_width>::end(this, m_data, (m_size / m_width)); }
789 
791  const_iterator begin() const noexcept { return int_vector_trait<t_width>::begin(this, m_data); }
792 
794  const_iterator end() const noexcept { return int_vector_trait<t_width>::end(this, m_data, (m_size / m_width)); }
795 
797  const_iterator cbegin() const noexcept { return int_vector_trait<t_width>::begin(this, m_data); }
798 
800  const_iterator cend() const noexcept { return int_vector_trait<t_width>::end(this, m_data, (m_size / m_width)); }
801 
803  void flip()
804  {
805  static_assert(1 == t_width, "int_vector: flip() is available only for bit_vector.");
806  if (!empty())
807  {
808  for (uint64_t i = 0; i < bit_data_size(); ++i) { m_data[i] = ~m_data[i]; }
809  }
810  }
811 
813  static size_t read_header(int_vector_size_type & size, int_width_type & int_width, std::istream & in)
814  {
815  uint64_t width_and_size = 0;
816  read_member(width_and_size, in);
817  size = width_and_size & bits::lo_set[56];
818  uint8_t read_int_width = (uint8_t)(width_and_size >> 56);
819  if (t_width == 0) { int_width = read_int_width; }
820  if (t_width > 0 and t_width != read_int_width)
821  {
822  std::cerr << "Warning: Width of int_vector<" << (size_t)t_width << ">";
823  std::cerr << " was specified as " << (size_type)read_int_width << std::endl;
824  std::cerr << "Length is " << size << " bits" << std::endl;
825  }
826  return sizeof(width_and_size);
827  }
828 
830  static uint64_t write_header(uint64_t size, uint8_t int_width, std::ostream & out)
831  {
832  if (t_width > 0)
833  {
834  if (t_width != int_width)
835  {
836  std::cout << "Warning: writing width=" << (size_type)int_width << " != fixed " << (size_type)t_width
837  << std::endl;
838  }
839  }
840  uint64_t width_and_size = (((uint64_t)int_width) << 56) | size;
841  return write_member(width_and_size, out);
842  }
843 
844  struct raw_wrapper
845  {
846  const int_vector & vec;
847  raw_wrapper() = delete;
848  raw_wrapper(const int_vector & _vec)
849  : vec(_vec)
850  {}
851 
852  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
853  {
854  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
855  auto written_bytes = vec.write_data(out);
856  structure_tree::add_size(child, written_bytes);
857  return written_bytes;
858  }
859  };
860 
861  const raw_wrapper raw = raw_wrapper(*this);
862 };
863 
865 
867 template <class t_int_vector>
869 {
870  public:
871  typedef typename t_int_vector::value_type value_type;
872 
873  private:
874  typename t_int_vector::value_type * const m_word;
875  const uint8_t m_offset;
876  const uint8_t m_len;
877  public:
881  constexpr int_vector_reference(int_vector_reference const &) noexcept = default;
882  constexpr int_vector_reference(int_vector_reference &&) noexcept = default;
883 
885 
889  int_vector_reference(value_type * word, uint8_t offset, uint8_t len) noexcept
890  : m_word(word)
891  , m_offset(offset)
892  , m_len(len){};
893 
895 
903  {
904  bits::write_int(m_word, x, m_offset, m_len);
905  return *this;
906  };
907 
908  int_vector_reference & operator=(const int_vector_reference & x) noexcept { return *this = value_type(x); };
909 
910  int_vector_reference & operator=(int_vector_reference && x) noexcept { return *this = value_type(std::move(x)); };
911 
913  operator value_type() const noexcept { return bits::read_int(m_word, m_offset, m_len); }
914 
917  {
918  value_type x = bits::read_int(m_word, m_offset, m_len);
919  bits::write_int(m_word, x + 1, m_offset, m_len);
920  return *this;
921  }
922 
924  value_type operator++(int) noexcept
925  {
926  value_type val = (typename t_int_vector::value_type) * this;
927  ++(*this);
928  return val;
929  }
930 
933  {
934  value_type x = bits::read_int(m_word, m_offset, m_len);
935  bits::write_int(m_word, x - 1, m_offset, m_len);
936  return *this;
937  }
938 
940  value_type operator--(int) noexcept
941  {
942  value_type val = (value_type) * this;
943  --(*this);
944  return val;
945  }
946 
949  {
950  value_type w = bits::read_int(m_word, m_offset, m_len);
951  bits::write_int(m_word, w + x, m_offset, m_len);
952  return *this;
953  }
954 
957  {
958  value_type w = bits::read_int(m_word, m_offset, m_len);
959  bits::write_int(m_word, w - x, m_offset, m_len);
960  return *this;
961  }
962 
963  bool operator==(const int_vector_reference & x) const noexcept { return value_type(*this) == value_type(x); }
964 
965  bool operator<(const int_vector_reference & x) const noexcept { return value_type(*this) < value_type(x); }
966 };
967 
968 // For C++11
969 template <class t_int_vector>
971 {
972  // TODO: more efficient solution?
974  x = y;
975  y = tmp;
976 }
977 
978 // For C++11
979 template <class t_int_vector>
982 {
983  // TODO: more efficient solution?
985  x = y;
986  y = tmp;
987 }
988 
989 // For C++11
990 template <class t_int_vector>
993 {
994  // TODO: more efficient solution?
996  x = y;
997  y = tmp;
998 }
999 
1000 // specialization for int_vector_reference for int_vector == bit_vector
1001 // special thanks to Timo Beller, who pointed out that the specialization is missing
1002 // Same implementation as in stl_bvector.h.
1003 template <>
1005 {
1006  public:
1007  typedef bool value_type;
1008 
1009  private:
1010  uint64_t * const m_word;
1011  uint64_t m_mask;
1012 
1013  public:
1017  constexpr int_vector_reference(int_vector_reference const &) noexcept = default;
1018  constexpr int_vector_reference(int_vector_reference &&) noexcept = default;
1019 
1021 
1024  int_vector_reference(uint64_t * word, uint8_t offset, uint8_t) noexcept
1025  : m_word(word)
1026  , m_mask(1ULL << offset){};
1027 
1029  int_vector_reference & operator=(bool x) noexcept
1030  {
1031  if (x)
1032  *m_word |= m_mask;
1033  else
1034  *m_word &= ~m_mask;
1035  return *this;
1036  };
1037 
1038  int_vector_reference & operator=(const int_vector_reference & x) noexcept { return *this = bool(x); };
1039  int_vector_reference & operator=(int_vector_reference && x) noexcept { return *this = bool(x); };
1040 
1042  operator bool() const noexcept { return !!(*m_word & m_mask); }
1043 
1044  bool operator==(const int_vector_reference & x) const noexcept { return bool(*this) == bool(x); }
1045 
1046  bool operator<(const int_vector_reference & x) const noexcept { return !bool(*this) && bool(x); }
1047 };
1048 
1049 // For C++11
1050 template <>
1052 {
1053  // TODO: more efficient solution?
1054  bool tmp = x;
1055  x = y;
1056  y = tmp;
1057 }
1058 
1059 // For C++11
1060 template <>
1061 inline void swap(bool & x, int_vector_reference<bit_vector> y) noexcept
1062 {
1063  // TODO: more efficient solution?
1064  bool tmp = x;
1065  x = y;
1066  y = tmp;
1067 }
1068 
1069 // For C++11
1070 template <>
1071 inline void swap(int_vector_reference<bit_vector> x, bool & y) noexcept
1072 {
1073  // TODO: more efficient solution?
1074  bool tmp = x;
1075  x = y;
1076  y = tmp;
1077 }
1078 
1079 template <class t_int_vector>
1081  : public std::iterator<std::random_access_iterator_tag,
1082  typename t_int_vector::value_type,
1083  typename t_int_vector::difference_type>
1084 {
1085  public:
1086  typedef uint64_t size_type;
1087 
1088  protected:
1089  uint8_t m_offset;
1090  uint8_t m_len;
1091 
1092  public:
1093  int_vector_iterator_base(uint8_t offset, uint8_t len)
1094  : m_offset(offset)
1095  , m_len(len)
1096  {}
1097 
1098  int_vector_iterator_base(const t_int_vector * v = nullptr, size_type idx = 0)
1099  : m_offset(idx & 0x3F)
1100  , m_len(v == nullptr ? 0 : v->m_width)
1101  {}
1102 };
1103 
1104 template <class t_int_vector>
1105 class int_vector_iterator : public int_vector_iterator_base<t_int_vector>
1106 {
1107  public:
1109  typedef uint64_t value_type;
1111  typedef reference * pointer;
1113  typedef typename t_int_vector::difference_type difference_type;
1114 
1115  friend class int_vector_const_iterator<t_int_vector>;
1116 
1117  private:
1118  using int_vector_iterator_base<t_int_vector>::m_offset; // make m_offset easy usable
1119  using int_vector_iterator_base<t_int_vector>::m_len; // make m_len easy usable
1120 
1121  typename t_int_vector::value_type * m_word;
1122 
1123  public:
1124  int_vector_iterator(t_int_vector * v = nullptr, size_type idx = 0)
1125  : int_vector_iterator_base<t_int_vector>(v, idx)
1126  , m_word((v != nullptr) ? v->m_data + (idx >> 6) : nullptr)
1127  {}
1128 
1130  : int_vector_iterator_base<t_int_vector>(it)
1131  , m_word(it.m_word)
1132  {
1133  m_offset = it.m_offset;
1134  m_len = it.m_len;
1135  }
1136 
1137  reference operator*() const { return reference(m_word, m_offset, m_len); }
1138 
1141  {
1142  m_offset += m_len;
1143  if (m_offset >= 64)
1144  {
1145  m_offset &= 0x3F;
1146  ++m_word;
1147  }
1148  return *this;
1149  }
1150 
1153  {
1154  int_vector_iterator it = *this;
1155  ++(*this);
1156  return it;
1157  }
1158 
1161  {
1162  m_offset -= m_len;
1163  if (m_offset >= 64)
1164  {
1165  m_offset &= 0x3F;
1166  --m_word;
1167  }
1168  return *this;
1169  }
1170 
1173  {
1174  int_vector_iterator it = *this;
1175  --(*this);
1176  return it;
1177  }
1178 
1180  {
1181  if (i < 0) return *this -= (-i);
1182  difference_type t = i * m_len;
1183  m_word += (t >> 6);
1184  if ((m_offset += (t & 0x3F)) & ~0x3F)
1185  { // if new offset is >= 64
1186  ++m_word; // add one to the word
1187  m_offset &= 0x3F; // offset = offset mod 64
1188  }
1189  return *this;
1190  }
1191 
1193  {
1194  if (i < 0) return *this += (-i);
1195  difference_type t = i * m_len;
1196  m_word -= (t >> 6);
1197  if ((m_offset -= (t & 0x3F)) & ~0x3F)
1198  { // if new offset is < 0
1199  --m_word;
1200  m_offset &= 0x3F;
1201  }
1202  return *this;
1203  }
1204 
1206  {
1207  if (this != &it)
1208  {
1209  m_word = it.m_word;
1210  m_offset = it.m_offset;
1211  m_len = it.m_len;
1212  }
1213  return *this;
1214  }
1215 
1217  {
1218  iterator it = *this;
1219  return it += i;
1220  }
1221 
1223  {
1224  iterator it = *this;
1225  return it -= i;
1226  }
1227 
1228  reference operator[](difference_type i) const { return *(*this + i); }
1229 
1230  bool operator==(const int_vector_iterator & it) const noexcept
1231  {
1232  return it.m_word == m_word && it.m_offset == m_offset;
1233  }
1234 
1235  bool operator!=(const int_vector_iterator & it) const noexcept { return !(*this == it); }
1236 
1237  bool operator<(const int_vector_iterator & it) const noexcept
1238  {
1239  if (m_word == it.m_word) return m_offset < it.m_offset;
1240  return m_word < it.m_word;
1241  }
1242 
1243  bool operator>(const int_vector_iterator & it) const noexcept
1244  {
1245  if (m_word == it.m_word) return m_offset > it.m_offset;
1246  return m_word > it.m_word;
1247  }
1248 
1249  bool operator>=(const int_vector_iterator & it) const noexcept { return !(*this < it); }
1250 
1251  bool operator<=(const int_vector_iterator & it) const noexcept { return !(*this > it); }
1252  inline difference_type operator-(const int_vector_iterator & it) const noexcept
1253  {
1254  return (((m_word - it.m_word) << 6) + m_offset - it.m_offset) / m_len;
1255  }
1256 };
1257 
1258 // template<class t_int_vector>
1259 // void swap(const int_vector_iterator<t_int_vector> &x, const int_vector_iterator<t_int_vector> &y){
1260 // x->swap(*y);
1261 //}
1262 
1263 template <class t_int_vector>
1266 {
1267  return it + n;
1268 }
1269 
1270 template <class t_int_vector>
1272 {
1273  public:
1274  typedef typename t_int_vector::value_type const_reference;
1275  typedef const typename t_int_vector::value_type * pointer;
1278  typedef typename t_int_vector::difference_type difference_type;
1279 
1280  template <class X>
1282  const int_vector_const_iterator<X> & y);
1283  friend class int_vector_iterator<t_int_vector>;
1284  friend class int_vector_iterator_base<t_int_vector>;
1285 
1286  private:
1287  using int_vector_iterator_base<t_int_vector>::m_offset; // make m_offset easy usable
1288  using int_vector_iterator_base<t_int_vector>::m_len; // make m_len easy usable
1289 
1290  const typename t_int_vector::value_type * m_word;
1291 
1292  public:
1293  int_vector_const_iterator(const t_int_vector * v = nullptr, size_type idx = 0)
1294  : int_vector_iterator_base<t_int_vector>(v, idx)
1295  , m_word((v != nullptr) ? v->m_data + (idx >> 6) : nullptr)
1296  {}
1297 
1299  : m_word(it.m_word)
1300  {
1301  m_offset = it.m_offset;
1302  m_len = it.m_len;
1303  }
1304 
1306  {
1307  if (m_offset + m_len <= 64) { return ((*m_word) >> m_offset) & bits::lo_set[m_len]; }
1308  return ((*m_word) >> m_offset) | ((*(m_word + 1) & bits::lo_set[(m_offset + m_len) & 0x3F]) << (64 - m_offset));
1309  }
1310 
1313  {
1314  m_offset += m_len;
1315  if (m_offset >= 64)
1316  {
1317  m_offset &= 0x3F;
1318  ++m_word;
1319  }
1320  return *this;
1321  }
1322 
1325  {
1326  int_vector_const_iterator it = *this;
1327  ++(*this);
1328  return it;
1329  }
1330 
1333  {
1334  m_offset -= m_len;
1335  if (m_offset >= 64)
1336  {
1337  m_offset &= 0x3F;
1338  --m_word;
1339  }
1340  return *this;
1341  }
1342 
1345  {
1346  int_vector_const_iterator it = *this;
1347  --(*this);
1348  return it;
1349  }
1350 
1352  {
1353  if (i < 0) return *this -= (-i);
1354  difference_type t = i * m_len;
1355  m_word += (t >> 6);
1356  if ((m_offset += (t & 0x3F)) & ~0x3F)
1357  { // if new offset >= 64
1358  ++m_word; // add one to the word
1359  m_offset &= 0x3F; // offset = offset mod 64
1360  }
1361  return *this;
1362  }
1363 
1365  {
1366  if (i < 0) return *this += (-i);
1367  difference_type t = i * m_len;
1368  m_word -= (t >> 6);
1369  if ((m_offset -= (t & 0x3F)) & ~0x3F)
1370  { // if new offset is < 0
1371  --m_word;
1372  m_offset &= 0x3F;
1373  }
1374  return *this;
1375  }
1376 
1378  {
1379  const_iterator it = *this;
1380  return it += i;
1381  }
1382 
1384  {
1385  const_iterator it = *this;
1386  return it -= i;
1387  }
1388 
1389  const_reference operator[](difference_type i) const { return *(*this + i); }
1390 
1391  bool operator==(const int_vector_const_iterator & it) const noexcept
1392  {
1393  return it.m_word == m_word && it.m_offset == m_offset;
1394  }
1395 
1396  bool operator!=(const int_vector_const_iterator & it) const noexcept { return !(*this == it); }
1397 
1398  bool operator<(const int_vector_const_iterator & it) const noexcept
1399  {
1400  if (m_word == it.m_word) return m_offset < it.m_offset;
1401  return m_word < it.m_word;
1402  }
1403 
1404  bool operator>(const int_vector_const_iterator & it) const noexcept
1405  {
1406  if (m_word == it.m_word) return m_offset > it.m_offset;
1407  return m_word > it.m_word;
1408  }
1409 
1410  bool operator>=(const int_vector_const_iterator & it) const noexcept { return !(*this < it); }
1411 
1412  bool operator<=(const int_vector_const_iterator & it) const noexcept { return !(*this > it); }
1413 };
1414 
1415 template <class t_int_vector>
1419 {
1420  return (((x.m_word - y.m_word) << 6) + x.m_offset - y.m_offset) / x.m_len;
1421 }
1422 
1423 template <class t_int_vector>
1427 {
1428  return it + n;
1429 }
1430 
1431 template <class t_bv>
1432 inline typename std::enable_if<std::is_same<typename t_bv::index_category, bv_tag>::value, std::ostream &>::type
1433 operator<<(std::ostream & os, const t_bv & bv)
1434 {
1435  for (auto b : bv) { os << b; }
1436  return os;
1437 }
1438 
1439 // ==== int_vector implementation ====
1440 
1441 template <uint8_t t_width>
1442 inline int_vector<t_width>::int_vector(size_type size, value_type default_value, uint8_t int_width)
1443  : m_size(0)
1444  , m_capacity(0)
1445  , m_data(nullptr)
1446  , m_width(t_width)
1447 {
1448  width(int_width);
1449  assign(size, default_value);
1450 }
1451 
1452 template <uint8_t t_width>
1454  : m_size(v.m_size)
1455  , m_capacity(v.m_capacity)
1456  , m_data(v.m_data)
1457  , m_width(v.m_width)
1458 {
1459  v.m_data = nullptr; // ownership of v.m_data now transfered
1460  v.m_size = 0;
1461  v.m_capacity = 0;
1462 }
1463 
1464 template <uint8_t t_width>
1466  : m_size(0)
1467  , m_capacity(0)
1468  , m_data(nullptr)
1469  , m_width(v.m_width)
1470 {
1471  width(v.m_width);
1472  resize(v.size());
1473  if (v.m_size > 0)
1474  {
1475  if (memcpy(m_data, v.data(), bit_data_size() << 3) == nullptr)
1476  {
1477  throw std::bad_alloc(); // LCOV_EXCL_LINE
1478  }
1479  }
1480 }
1481 
1482 template <uint8_t t_width>
1484 {
1485  if (this != &v)
1486  { // if v is not the same object
1487  int_vector<t_width> tmp(v);
1488  *this = std::move(tmp);
1489  }
1490  return *this;
1491 }
1492 
1493 template <uint8_t t_width>
1495 {
1496  if (this != &v)
1497  { // if v is not the same object
1498  memory_manager::clear(*this); // clear allocated memory
1499  m_size = v.m_size;
1500  m_data = v.m_data; // assign new memory
1501  m_width = v.m_width;
1502  m_capacity = v.m_capacity;
1503  v.m_data = nullptr;
1504  v.m_size = 0;
1505  v.m_capacity = 0;
1506  }
1507  return *this;
1508 }
1509 
1510 // Destructor
1511 template <uint8_t t_width>
1513 {
1514  memory_manager::clear(*this);
1515 }
1516 
1517 // sdsl::swap (to fulfill the container concept)
1518 template <uint8_t t_width>
1520 {
1521  std::swap(v1, v2);
1522 }
1523 
1524 template <uint8_t t_width>
1526 {
1527  if (size > m_capacity || m_data == nullptr) { memory_manager::resize(*this, size); }
1528  m_size = size;
1529 }
1530 
1531 template <uint8_t t_width>
1532 void int_vector<t_width>::bit_resize(const size_type size, const value_type value)
1533 {
1534  size_type old_size = m_size;
1535  bit_resize(size);
1536  auto it = begin() + old_size / m_width;
1537  util::set_to_value(*this, value, it);
1538 }
1539 
1540 template <uint8_t t_width>
1541 auto int_vector<t_width>::get_int(size_type idx, const uint8_t len) const -> value_type
1542 {
1543 #ifdef SDSL_DEBUG
1544  if (idx + len > m_size)
1545  {
1546  throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::get_int(size_type, uint8_t); idx+len > size()!");
1547  }
1548  if (len > 64) { throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::get_int(size_type, uint8_t); len>64!"); }
1549 #endif
1550  return bits::read_int(m_data + (idx >> 6), idx & 0x3F, len);
1551 }
1552 
1553 template <uint8_t t_width>
1554 inline void int_vector<t_width>::set_int(size_type idx, value_type x, const uint8_t len)
1555 {
1556 #ifdef SDSL_DEBUG
1557  if (idx + len > m_size)
1558  {
1559  throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::set_int(size_type, uint8_t); idx+len > size()!");
1560  }
1561  if (len > 64) { throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::set_int(size_type, uint8_t); len>64!"); }
1562 #endif
1563  bits::write_int(m_data + (idx >> 6), x, idx & 0x3F, len);
1564 }
1565 
1566 template <uint8_t t_width>
1568 {
1569  return m_size / m_width;
1570 }
1571 
1572 // specialized size method for 64-bit integer vector
1573 template <>
1574 inline typename int_vector<64>::size_type int_vector<64>::size() const noexcept
1575 {
1576  return m_size >> 6;
1577 }
1578 
1579 // specialized size method for 32-bit integer vector
1580 template <>
1581 inline typename int_vector<32>::size_type int_vector<32>::size() const noexcept
1582 {
1583  return m_size >> 5;
1584 }
1585 
1586 // specialized size method for 64-bit integer vector
1587 template <>
1588 inline typename int_vector<16>::size_type int_vector<16>::size() const noexcept
1589 {
1590  return m_size >> 4;
1591 }
1592 
1593 // specialized size method for 64-bit integer vector
1594 template <>
1595 inline typename int_vector<8>::size_type int_vector<8>::size() const noexcept
1596 {
1597  return m_size >> 3;
1598 }
1599 
1600 // specialized size method for bit_vector
1601 template <>
1602 inline typename int_vector<1>::size_type int_vector<1>::size() const noexcept
1603 {
1604  return m_size;
1605 }
1606 
1607 template <uint8_t t_width>
1609 {
1610  return m_capacity / m_width;
1611 }
1612 
1613 // specialized capacity method for 64-bit integer vector
1614 template <>
1615 inline typename int_vector<64>::size_type int_vector<64>::capacity() const noexcept
1616 {
1617  return m_capacity >> 6;
1618 }
1619 
1620 // specialized capacity method for 32-bit integer vector
1621 template <>
1622 inline typename int_vector<32>::size_type int_vector<32>::capacity() const noexcept
1623 {
1624  return m_capacity >> 5;
1625 }
1626 
1627 // specialized capacity method for 64-bit integer vector
1628 template <>
1629 inline typename int_vector<16>::size_type int_vector<16>::capacity() const noexcept
1630 {
1631  return m_capacity >> 4;
1632 }
1633 
1634 // specialized capacity method for 64-bit integer vector
1635 template <>
1636 inline typename int_vector<8>::size_type int_vector<8>::capacity() const noexcept
1637 {
1638  return m_capacity >> 3;
1639 }
1640 
1641 // specialized capacity method for bit_vector
1642 template <>
1643 inline typename int_vector<1>::size_type int_vector<1>::capacity() const noexcept
1644 {
1645  return m_capacity;
1646 }
1647 
1648 template <uint8_t t_width>
1649 inline auto int_vector<t_width>::operator[](const size_type & idx) noexcept -> reference
1650 {
1651  assert(idx < this->size());
1652  size_type i = idx * m_width;
1653  return reference(this->m_data + (i >> 6), i & 0x3F, m_width);
1654 }
1655 
1656 // specialized [] operator for 64 bit access.
1657 template <>
1658 inline auto int_vector<64>::operator[](const size_type & idx) noexcept -> reference
1659 {
1660  assert(idx < this->size());
1661  return *(this->m_data + idx);
1662 }
1663 
1664 // specialized [] operator for 32 bit access.
1665 template <>
1666 inline auto int_vector<32>::operator[](const size_type & idx) noexcept -> reference
1667 {
1668  assert(idx < this->size());
1669  return *(((uint32_t *)(this->m_data)) + idx);
1670 }
1671 
1672 // specialized [] operator for 16 bit access.
1673 template <>
1674 inline auto int_vector<16>::operator[](const size_type & idx) noexcept -> reference
1675 {
1676  assert(idx < this->size());
1677  return *(((uint16_t *)(this->m_data)) + idx);
1678 }
1679 
1680 // specialized [] operator for 8 bit access.
1681 template <>
1682 inline auto int_vector<8>::operator[](const size_type & idx) noexcept -> reference
1683 {
1684  assert(idx < this->size());
1685  return *(((uint8_t *)(this->m_data)) + idx);
1686 }
1687 
1688 template <uint8_t t_width>
1689 inline auto int_vector<t_width>::operator[](const size_type & idx) const noexcept -> const_reference
1690 {
1691  assert(idx < this->size());
1692  return get_int(idx * t_width, t_width);
1693 }
1694 
1695 template <>
1696 inline auto int_vector<0>::operator[](const size_type & idx) const noexcept -> const_reference
1697 {
1698  assert(idx < this->size());
1699  return get_int(idx * m_width, m_width);
1700 }
1701 
1702 template <>
1703 inline auto int_vector<64>::operator[](const size_type & idx) const noexcept -> const_reference
1704 {
1705  assert(idx < this->size());
1706  return *(this->m_data + idx);
1707 }
1708 
1709 template <>
1710 inline auto int_vector<32>::operator[](const size_type & idx) const noexcept -> const_reference
1711 {
1712  assert(idx < this->size());
1713  return *(((uint32_t *)this->m_data) + idx);
1714 }
1715 
1716 template <>
1717 inline auto int_vector<16>::operator[](const size_type & idx) const noexcept -> const_reference
1718 {
1719  assert(idx < this->size());
1720  return *(((uint16_t *)this->m_data) + idx);
1721 }
1722 
1723 template <>
1724 inline auto int_vector<8>::operator[](const size_type & idx) const noexcept -> const_reference
1725 {
1726  assert(idx < this->size());
1727  return *(((uint8_t *)this->m_data) + idx);
1728 }
1729 
1730 template <>
1731 inline auto int_vector<1>::operator[](const size_type & idx) const noexcept -> const_reference
1732 {
1733  assert(idx < this->size());
1734  return ((*(m_data + (idx >> 6))) >> (idx & 0x3F)) & 1;
1735 }
1736 
1737 template <uint8_t t_width>
1738 bool int_vector<t_width>::operator<(const int_vector & v) const noexcept
1739 {
1740  size_type min_size = size();
1741  if (min_size > v.size()) min_size = v.size();
1742  for (auto it = begin(), end = begin() + min_size, it_v = v.begin(); it != end; ++it, ++it_v)
1743  {
1744  if (*it == *it_v)
1745  continue;
1746  else
1747  return *it < *it_v;
1748  }
1749  return size() < v.size();
1750 }
1751 
1752 template <uint8_t t_width>
1753 bool int_vector<t_width>::operator>(const int_vector & v) const noexcept
1754 {
1755  size_type min_size = size();
1756  if (min_size > v.size()) min_size = v.size();
1757  for (auto it = begin(), end = begin() + min_size, it_v = v.begin(); it != end; ++it, ++it_v)
1758  {
1759  if (*it == *it_v)
1760  continue;
1761  else
1762  return *it > *it_v;
1763  }
1764  return size() > v.size();
1765 }
1766 
1767 template <uint8_t t_width>
1768 bool int_vector<t_width>::operator<=(const int_vector & v) const noexcept
1769 {
1770  return *this == v or *this < v;
1771 }
1772 
1773 template <uint8_t t_width>
1774 bool int_vector<t_width>::operator>=(const int_vector & v) const noexcept
1775 {
1776  return *this == v or *this > v;
1777 }
1778 
1779 template <uint8_t t_width>
1781 {
1782  assert(v.bit_size() == bit_size());
1783  for (uint64_t i = 0; i < bit_data_size(); ++i) m_data[i] &= v.m_data[i];
1784  return *this;
1785 }
1786 
1787 template <uint8_t t_width>
1789 {
1790  assert(bit_size() == v.bit_size());
1791  for (uint64_t i = 0; i < bit_data_size(); ++i) m_data[i] |= v.m_data[i];
1792  return *this;
1793 }
1794 
1795 template <uint8_t t_width>
1797 {
1798  assert(bit_size() == v.bit_size());
1799  for (uint64_t i = 0; i < bit_data_size(); ++i) m_data[i] ^= v.m_data[i];
1800  return *this;
1801 }
1802 
1803 template <uint8_t t_width>
1805 {
1806  size_type written_bytes = 0;
1807  uint64_t * p = m_data;
1808  size_type idx = 0;
1809  while (idx + conf::SDSL_BLOCK_SIZE < bit_data_size())
1810  {
1811  out.write((char *)p, conf::SDSL_BLOCK_SIZE * sizeof(uint64_t));
1812  written_bytes += conf::SDSL_BLOCK_SIZE * sizeof(uint64_t);
1813  p += conf::SDSL_BLOCK_SIZE;
1814  idx += conf::SDSL_BLOCK_SIZE;
1815  }
1816  out.write((char *)p, (bit_data_size() - idx) * sizeof(uint64_t));
1817  written_bytes += (bit_data_size() - idx) * sizeof(uint64_t);
1818  return written_bytes;
1819 }
1820 
1821 template <uint8_t t_width>
1823  structure_tree_node * v,
1824  std::string name) const
1825 {
1826  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
1827  size_type written_bytes = int_vector<t_width>::write_header(m_size, m_width, out);
1828  written_bytes += write_data(out);
1829  structure_tree::add_size(child, written_bytes);
1830  return written_bytes;
1831 }
1832 
1833 template <uint8_t t_width>
1834 void int_vector<t_width>::load(std::istream & in)
1835 {
1836  size_type size;
1837  int_vector<t_width>::read_header(size, m_width, in);
1838 
1839  bit_resize(size);
1840  uint64_t * p = m_data;
1841  size_type idx = 0;
1842  while (idx + conf::SDSL_BLOCK_SIZE < bit_data_size())
1843  {
1844  in.read((char *)p, conf::SDSL_BLOCK_SIZE * sizeof(uint64_t));
1845  p += conf::SDSL_BLOCK_SIZE;
1846  idx += conf::SDSL_BLOCK_SIZE;
1847  }
1848  in.read((char *)p, (bit_data_size() - idx) * sizeof(uint64_t));
1849 }
1850 
1851 template <uint8_t t_width>
1852 template <typename archive_t>
1853 inline typename std::enable_if<cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
1854  archive_t>::value,
1855  void>::type
1857 {
1858  ar(CEREAL_NVP(cereal::make_size_tag(static_cast<int_width_type>(m_width))));
1859  ar(CEREAL_NVP(growth_factor));
1860  ar(CEREAL_NVP(cereal::make_size_tag(static_cast<size_type>(m_size))));
1861  ar(cereal::make_nvp("data", cereal::binary_data(m_data, bit_data_size() * sizeof(uint64_t))));
1862 }
1863 
1864 template <uint8_t t_width>
1865 template <typename archive_t>
1866 inline typename std::enable_if<!cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
1867  archive_t>::value,
1868  void>::type
1870 {
1871  ar(CEREAL_NVP(m_width));
1872  ar(CEREAL_NVP(growth_factor));
1873  ar(CEREAL_NVP(m_size));
1874  for (value_type const & v : *this) ar(v);
1875 }
1876 
1877 template <uint8_t t_width>
1878 template <typename archive_t>
1879 inline typename std::enable_if<cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
1880  archive_t>::value,
1881  void>::type
1883 {
1884  ar(CEREAL_NVP(cereal::make_size_tag(m_width)));
1885  ar(CEREAL_NVP(growth_factor));
1886  ar(CEREAL_NVP(cereal::make_size_tag(m_size)));
1887  resize(size());
1888  ar(cereal::make_nvp("data", cereal::binary_data(m_data, bit_data_size() * sizeof(uint64_t))));
1889 }
1890 
1891 template <uint8_t t_width>
1892 template <typename archive_t>
1893 inline typename std::enable_if<!cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
1894  archive_t>::value,
1895  void>::type
1897 {
1898  ar(CEREAL_NVP(m_width));
1899  width(width());
1900  ar(CEREAL_NVP(growth_factor));
1901  ar(CEREAL_NVP(m_size));
1902  resize(size());
1903 
1904  for (size_t i = 0; i < size(); ++i)
1905  {
1906  value_type tmp;
1907  ar(tmp);
1908  operator[](i) = tmp;
1909  }
1910 }
1911 
1912 } // end namespace sdsl
1913 
1914 #include <sdsl/int_vector_buffer.hpp>
1915 #include <sdsl/int_vector_mapper.hpp>
1916 
1917 #endif
bits.hpp contains the sdsl::bits class.
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
#define CEREAL_LOAD_FUNCTION_NAME
Definition: cereal.hpp:33
#define CEREAL_SAVE_FUNCTION_NAME
Definition: cereal.hpp:34
A class to encode and decode between comma code and binary code.
Definition: coder_comma.hpp:48
A class to encode and decode between Elias- and binary code.
A class to encode and decode between Elias- and binary code.
A class to encode and decode between Fibonacci and binary code.
t_int_vector::difference_type difference_type
t_int_vector::size_type size_type
const_iterator operator-(difference_type i) const
const_iterator operator--(int)
Postfix decrement of the Iterator.
bool operator!=(const int_vector_const_iterator &it) const noexcept
int_vector_const_iterator const_iterator
const_iterator operator+(difference_type i) const
int_vector_const_iterator(const int_vector_iterator< t_int_vector > &it)
const_reference operator[](difference_type i) const
const t_int_vector::value_type * pointer
bool operator>(const int_vector_const_iterator &it) const noexcept
bool operator>=(const int_vector_const_iterator &it) const noexcept
bool operator<=(const int_vector_const_iterator &it) const noexcept
const_iterator & operator--()
Prefix decrement of the Iterator.
const_reference operator*() const
const_iterator & operator++()
Prefix increment of the Iterator.
t_int_vector::value_type const_reference
bool operator<(const int_vector_const_iterator &it) const noexcept
friend int_vector_const_iterator< X >::difference_type operator-(const int_vector_const_iterator< X > &x, const int_vector_const_iterator< X > &y)
const_iterator & operator+=(difference_type i)
int_vector_const_iterator(const t_int_vector *v=nullptr, size_type idx=0)
bool operator==(const int_vector_const_iterator &it) const noexcept
const_iterator & operator-=(difference_type i)
const_iterator operator++(int)
Postfix increment of the Iterator.
int_vector_iterator_base(const t_int_vector *v=nullptr, size_type idx=0)
int_vector_iterator_base(uint8_t offset, uint8_t len)
int_vector_iterator iterator
iterator & operator--()
Prefix decrement of the Iterator.
reference operator*() const
iterator & operator+=(difference_type i)
iterator operator++(int)
Postfix increment of the Iterator.
bool operator<(const int_vector_iterator &it) const noexcept
bool operator==(const int_vector_iterator &it) const noexcept
reference operator[](difference_type i) const
int_vector_iterator(const int_vector_iterator< t_int_vector > &it)
t_int_vector::difference_type difference_type
bool operator!=(const int_vector_iterator &it) const noexcept
bool operator<=(const int_vector_iterator &it) const noexcept
t_int_vector::size_type size_type
iterator operator+(difference_type i) const
iterator & operator=(const int_vector_iterator< t_int_vector > &it)
iterator operator-(difference_type i) const
iterator & operator++()
Prefix increment of the Iterator.
bool operator>=(const int_vector_iterator &it) const noexcept
iterator operator--(int)
Postfix decrement of the Iterator.
int_vector_iterator(t_int_vector *v=nullptr, size_type idx=0)
iterator & operator-=(difference_type i)
difference_type operator-(const int_vector_iterator &it) const noexcept
bool operator>(const int_vector_iterator &it) const noexcept
int_vector_reference< t_int_vector > reference
bool operator<(const int_vector_reference &x) const noexcept
int_vector_reference()=delete
Default constructor explicitly deleted.
constexpr int_vector_reference(int_vector_reference &&) noexcept=default
int_vector_reference & operator=(const int_vector_reference &x) noexcept
constexpr int_vector_reference(int_vector_reference const &) noexcept=default
Copy and move explicitly defaulted.
int_vector_reference & operator=(int_vector_reference &&x) noexcept
bool operator==(const int_vector_reference &x) const noexcept
int_vector_reference & operator=(bool x) noexcept
Assignment operator for the proxy class.
A proxy class that acts as a reference to an integer of length len bits in a int_vector.
Definition: int_vector.hpp:869
int_vector_reference & operator--() noexcept
Prefix decrement of the proxy object.
Definition: int_vector.hpp:932
t_int_vector::value_type value_type
Definition: int_vector.hpp:871
bool operator<(const int_vector_reference &x) const noexcept
Definition: int_vector.hpp:965
int_vector_reference & operator=(int_vector_reference &&x) noexcept
Definition: int_vector.hpp:910
int_vector_reference & operator=(value_type x) noexcept
Assignment operator for the proxy class.
Definition: int_vector.hpp:902
value_type operator++(int) noexcept
Postfix increment of the proxy object.
Definition: int_vector.hpp:924
int_vector_reference & operator++() noexcept
Prefix increment of the proxy object.
Definition: int_vector.hpp:916
int_vector_reference & operator=(const int_vector_reference &x) noexcept
Definition: int_vector.hpp:908
int_vector_reference()=delete
Default constructor explicitly deleted.
int_vector_reference & operator+=(const value_type x) noexcept
Add assign from the proxy object.
Definition: int_vector.hpp:948
value_type operator--(int) noexcept
Postfix decrement of the proxy object.
Definition: int_vector.hpp:940
constexpr int_vector_reference(int_vector_reference &&) noexcept=default
constexpr int_vector_reference(int_vector_reference const &) noexcept=default
Copy and move explicitly defaulted.
bool operator==(const int_vector_reference &x) const noexcept
Definition: int_vector.hpp:963
int_vector_reference & operator-=(const value_type x) noexcept
Subtract assign from the proxy object.
Definition: int_vector.hpp:956
A generic vector class for integers of width .
Definition: int_vector.hpp:253
iterator end() noexcept
Iterator that points to the element after the last element of int_vector.
Definition: int_vector.hpp:788
void flip()
Flip all bits of bit_vector.
Definition: int_vector.hpp:803
iterator insert(const_iterator it, std::initializer_list< value_type > il)
Insert elements from intializer_list before the element that the iterator is pointing to.
Definition: int_vector.hpp:424
const raw_wrapper raw
Definition: int_vector.hpp:861
reference operator[](const size_type &i) noexcept
non const version of [] operator
rank_support_v< 1, 1 > rank_1_type
Definition: int_vector.hpp:268
int_vector(const int_vector &v)
Copy constructor.
size_type capacity() const noexcept
Returns the size of the occupied bits of the int_vector.
std::enable_if<!cereal::traits::is_output_serializable< cereal::BinaryData< int_vector< t_width > >, archive_t >::value, void >::type CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal if archive is not binary.
~int_vector()
Destructor.
bool empty() const noexcept
Equivalent to size() == 0.
Definition: int_vector.hpp:524
value_type get_int(size_type idx, const uint8_t len=64) const
Get the integer value of the binary string of length len starting at position idx in the int_vector.
void assign(size_type size, value_type default_value)
Assign. Resize int_vector to size and fill elements with default_value.
Definition: int_vector.hpp:494
void reserve(size_type capacity)
Reserve storage. If the new capacity is smaller than the current, this method does nothing.
Definition: int_vector.hpp:535
int_vector_trait< t_width >::iterator iterator
Definition: int_vector.hpp:259
void resize(const size_type size, const value_type value)
Resize the int_vector in terms of elements. Only as much space as necessary is allocated.
Definition: int_vector.hpp:551
int_vec_category_trait< t_width >::type index_category
Definition: int_vector.hpp:272
const value_type * const_pointer
Definition: int_vector.hpp:264
const_iterator end() const noexcept
Const iterator that points to the element after the last element of int_vector.
Definition: int_vector.hpp:794
const_reference back() const noexcept
Returns last element.
Definition: int_vector.hpp:458
std::enable_if< std::is_base_of< std::input_iterator_tag, typename std::iterator_traits< input_iterator_t >::iterator_category >::value, iterator >::type insert(const_iterator it, input_iterator_t first, input_iterator_t last)
Insert elements from an iterator pair before the element that the iterator it is pointing to.
Definition: int_vector.hpp:438
int_vector(typename std::enable_if< std::is_base_of< std::input_iterator_tag, typename std::iterator_traits< input_iterator_t >::iterator_category >::value, input_iterator_t >::type first, input_iterator_t last)
Constructor for iterator range.
Definition: int_vector.hpp:350
void swap(int_vector &v) noexcept
Swap method for int_vector.
Definition: int_vector.hpp:527
rank_support_v< 0, 1 > rank_0_type
Definition: int_vector.hpp:269
void bit_resize(const size_type size)
Resize the int_vector in terms of bits. Only as much space as necessary is allocated.
int_vector_size_type size_type
Definition: int_vector.hpp:266
ptrdiff_t difference_type
Definition: int_vector.hpp:265
bool operator>(const int_vector &v) const noexcept
Greater operator for two int_vectors.
select_support_mcl< 0, 1 > select_0_type
Definition: int_vector.hpp:271
std::enable_if< cereal::traits::is_output_serializable< cereal::BinaryData< int_vector< t_width > >, archive_t >::value, void >::type CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal if archive is binary.
void width(uint8_t new_width) noexcept
Sets the width of the integers which are accessed via the [] operator, if t_width equals 0.
Definition: int_vector.hpp:626
bool operator>=(const int_vector &v) const noexcept
Greater of equal operator.
int_vector_reference< int_vector > * pointer
Definition: int_vector.hpp:263
int_vector_trait< t_width >::const_reference const_reference
Definition: int_vector.hpp:262
iterator erase(const_iterator it)
Remove element that iterator is pointing to.
Definition: int_vector.hpp:368
int_vector_trait< t_width >::int_width_type int_width_type
Definition: int_vector.hpp:267
size_type write_data(std::ostream &out) const
reference at(const size_type &i)
non const version of at() function
Definition: int_vector.hpp:689
friend bool operator==(const int_vector< t_width > &lhs, const container &rhs) noexcept
Equality operator for an arbitrary container.
Definition: int_vector.hpp:732
iterator insert(const_iterator it, size_type n, value_type value)
Insert n copies of an element before the element that the iterator is pointing to.
Definition: int_vector.hpp:410
int_vector & operator|=(const int_vector &v)
bitwise-or-update equal operator
size_type bit_size() const noexcept
The number of bits in the int_vector.
Definition: int_vector.hpp:571
iterator emplace(const_iterator it, Args &&... args)
Insert an element constructed with std::forward<Args>(args) before the element that the iterator is p...
Definition: int_vector.hpp:394
int_vector & operator=(const int_vector &v)
Assignment operator.
size_type bit_capacity() const noexcept
Returns the size of the occupied bits of the int_vector.
Definition: int_vector.hpp:585
bool operator!=(const int_vector< t_width2 > &v) const noexcept
Inequality operator for two int_vectors.
Definition: int_vector.hpp:745
void clear() noexcept
Clearing the int_vector. Allocated memory will not be released.
Definition: int_vector.hpp:363
bool operator<(const int_vector &v) const noexcept
Less operator for two int_vectors.
int_vector & operator&=(const int_vector &v)
bitwise-and-update operator
select_support_mcl< 1, 1 > select_1_type
Definition: int_vector.hpp:270
const_iterator begin() const noexcept
Const iterator that points to the first element of the int_vector.
Definition: int_vector.hpp:791
reference back() noexcept
Returns last element.
Definition: int_vector.hpp:455
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:590
int_vector & operator=(int_vector &&v)
Move assignment operator.
int_vector_trait< t_width >::const_iterator const_iterator
Definition: int_vector.hpp:260
void load(std::istream &in)
Load the int_vector for a stream.
bool operator<=(const int_vector &v) const noexcept
Less or equal operator.
const_iterator cbegin() const noexcept
Const iterator that points to the first element of the int_vector.
Definition: int_vector.hpp:797
void shrink_to_fit()
Free unused allocated memory.
Definition: int_vector.hpp:530
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
Definition: int_vector.hpp:619
int_vector_trait< t_width >::reference reference
Definition: int_vector.hpp:261
void emplace_back(Args &&... args)
Insert an element constructed with std::forward<Args>(args) at the end.
Definition: int_vector.hpp:464
void assign(std::initializer_list< value_type > il)
Assign. Resize int_vector and initialize with initializer_list.
Definition: int_vector.hpp:503
size_type size() const noexcept
The number of elements in the int_vector.
static constexpr uint8_t fixed_int_width
Definition: int_vector.hpp:289
iterator insert(const_iterator it, value_type value)
Insert an element before the element that the iterator is pointing to.
Definition: int_vector.hpp:403
void push_back(value_type value)
Insert element at the end.
Definition: int_vector.hpp:472
const_reference at(const size_type &i) const
const version of at() function
Definition: int_vector.hpp:695
int_vector & operator^=(const int_vector &v)
bitwise-xor-update operator
uint64_t * data() noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:595
const_reference operator[](const size_type &i) const noexcept
const version of [] operator
void assign(input_iterator_t first, input_iterator_t last)
Assign. Resize int_vector and initialize by copying from an iterator range.
Definition: int_vector.hpp:515
float growth_factor
Growth factor for amortized constant time operations.
Definition: int_vector.hpp:290
std::enable_if<!cereal::traits::is_input_serializable< cereal::BinaryData< int_vector< t_width > >, archive_t >::value, void >::type CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal if archive is not binary.
const_iterator cend() const noexcept
Const iterator that points to the element after the last element of int_vector.
Definition: int_vector.hpp:800
int_vector(size_type size=0)
Constructor to fix possible comparison with integeres issue.
Definition: int_vector.hpp:335
int_vector_trait< t_width >::value_type value_type
Definition: int_vector.hpp:255
static size_t read_header(int_vector_size_type &size, int_width_type &int_width, std::istream &in)
Read the size and int_width of a int_vector.
Definition: int_vector.hpp:813
bool operator==(const int_vector< t_width > &v) const noexcept
Equality operator for two int_vectors.
Definition: int_vector.hpp:710
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
reference front() noexcept
Returns first element.
Definition: int_vector.hpp:449
int_vector(int_vector &&v)
Move constructor.
static size_type max_size() noexcept
Maximum size of the int_vector.
Definition: int_vector.hpp:566
int_vector(size_type size, value_type default_value, uint8_t int_width=t_width)
Constructor for int_vector.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:545
int_vector(std::initializer_list< value_type > il)
Constructor for initializer_list.
Definition: int_vector.hpp:339
iterator erase(const_iterator first, const_iterator last)
Remove elements in given iterator range.
Definition: int_vector.hpp:380
const_reference front() const noexcept
Returns first element.
Definition: int_vector.hpp:452
static uint64_t write_header(uint64_t size, uint8_t int_width, std::ostream &out)
Write the size and int_width of a int_vector.
Definition: int_vector.hpp:830
void set_int(size_type idx, value_type x, const uint8_t len=64)
Set the bits from position idx to idx+len-1 to the binary representation of integer x.
void pop_back()
Remove element at the end.
Definition: int_vector.hpp:479
std::enable_if< cereal::traits::is_input_serializable< cereal::BinaryData< int_vector< t_width > >, archive_t >::value, void >::type CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (save) via cereal if archive is binary.
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
Definition: int_vector.hpp:783
static void resize(t_vec &v, const typename t_vec::size_type capacity)
static void clear(t_vec &v)
A rank structure proposed by Sebastiano Vigna.
The base class of classes supporting rank_queries for a sdsl::bit_vector in constant time.
A class supporting constant time select queries.
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
memory_management.hpp contains two function for allocating and deallocating memory
void make_nvp(t1 const &, t2 const &)
Definition: cereal.hpp:60
void make_size_tag(t const &)
Definition: cereal.hpp:64
t1 binary_data(t1 const &, t2 const &)
Definition: cereal.hpp:68
const uint64_t SDSL_BLOCK_SIZE
Definition: config.hpp:33
int_vector ::size_type size_type
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition: util.hpp:566
Namespace for the succinct data structure library.
int_vector_const_iterator< t_int_vector >::difference_type operator-(const int_vector_const_iterator< t_int_vector > &x, const int_vector_const_iterator< t_int_vector > &y)
std::ostream & operator<<(std::ostream &os, const bp_interval< t_int > &interval)
Definition: cst_sct3.hpp:1332
std::enable_if< has_serialize< X >::value, typename X::size_type >::type serialize(const X &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
Definition: io.hpp:131
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
Definition: io.hpp:154
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
Definition: int_vector.hpp:970
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition: io.hpp:84
void read_member(T &t, std::istream &in)
Definition: io.hpp:111
uint64_t std_size_type_for_int_vector
Definition: int_vector.hpp:45
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
Definition: int_vector.hpp:51
void swap(int_vector< t_width > &v1, int_vector< t_width > &v2) noexcept
uint64_t int_vector_size_type
Definition: config.hpp:48
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
int_vector_iterator< t_int_vector > operator+(typename int_vector_iterator< t_int_vector >::difference_type n, const int_vector_iterator< t_int_vector > &it)
ram_fs.hpp
sfstream.hpp contains a two stream class which can be used to read/write from/to files or strings.
static SDSL_CONSTEXPR uint64_t read_int(const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
Reads a value from a bit position in an array.
Definition: bits.hpp:783
static SDSL_CONSTEXPR void write_int(uint64_t *word, uint64_t x, const uint8_t offset=0, const uint8_t len=64)
Writes value x to an bit position in an array.
Definition: bits.hpp:727
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
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Definition: int_vector.hpp:852
raw_wrapper(const int_vector &_vec)
Definition: int_vector.hpp:848
static iterator end(int_vector_type *, uint64_t *begin, int_vector_size_type size) noexcept
Definition: int_vector.hpp:201
static iterator begin(int_vector_type *, uint64_t *begin) noexcept
Definition: int_vector.hpp:200
int_vector< 16 > int_vector_type
Definition: int_vector.hpp:193
static const_iterator begin(const int_vector_type *, const uint64_t *begin) noexcept
Definition: int_vector.hpp:205
static void set_width(uint8_t, int_width_type) noexcept
Definition: int_vector.hpp:211
static const_iterator end(const int_vector_type *, const uint64_t *begin, int_vector_size_type size) noexcept
Definition: int_vector.hpp:206
const uint16_t * const_iterator
Definition: int_vector.hpp:198
const uint32_t * const_iterator
Definition: int_vector.hpp:173
static iterator begin(int_vector_type *, uint64_t *begin) noexcept
Definition: int_vector.hpp:175
static const_iterator end(const int_vector_type *, const uint64_t *begin, int_vector_size_type size) noexcept
Definition: int_vector.hpp:181
static const_iterator begin(const int_vector_type *, const uint64_t *begin) noexcept
Definition: int_vector.hpp:180
static void set_width(uint8_t, int_width_type) noexcept
Definition: int_vector.hpp:186
static iterator end(int_vector_type *, uint64_t *begin, int_vector_size_type size) noexcept
Definition: int_vector.hpp:176
int_vector< 32 > int_vector_type
Definition: int_vector.hpp:168
const uint64_t * const_iterator
Definition: int_vector.hpp:148
static const_iterator begin(const int_vector_type *, const uint64_t *begin) noexcept
Definition: int_vector.hpp:155
static iterator end(int_vector_type *, uint64_t *begin, int_vector_size_type size) noexcept
Definition: int_vector.hpp:151
static const_iterator end(const int_vector_type *, const uint64_t *begin, int_vector_size_type size) noexcept
Definition: int_vector.hpp:156
static iterator begin(int_vector_type *, uint64_t *begin) noexcept
Definition: int_vector.hpp:150
int_vector< 64 > int_vector_type
Definition: int_vector.hpp:143
static void set_width(uint8_t, int_width_type) noexcept
Definition: int_vector.hpp:161
static const_iterator end(const int_vector_type *, const uint64_t *begin, int_vector_size_type size) noexcept
Definition: int_vector.hpp:231
int_vector< 8 > int_vector_type
Definition: int_vector.hpp:218
static const_iterator begin(const int_vector_type *, const uint64_t *begin) noexcept
Definition: int_vector.hpp:230
const uint8_t * const_iterator
Definition: int_vector.hpp:223
static iterator begin(int_vector_type *, uint64_t *begin) noexcept
Definition: int_vector.hpp:225
static void set_width(uint8_t, int_width_type) noexcept
Definition: int_vector.hpp:236
static iterator end(int_vector_type *, uint64_t *begin, int_vector_size_type size) noexcept
Definition: int_vector.hpp:226
int_vector_const_iterator< int_vector_type > const_iterator
Definition: int_vector.hpp:114
int_vector< t_width > int_vector_type
Definition: int_vector.hpp:109
static const_iterator begin(const int_vector_type *v, const uint64_t *) noexcept
Definition: int_vector.hpp:121
static void set_width(uint8_t new_width, int_width_type &width) noexcept
Definition: int_vector.hpp:127
int_vector_reference< int_vector_type > reference
Definition: int_vector.hpp:110
static iterator end(int_vector_type *v, uint64_t *, int_vector_size_type) noexcept
Definition: int_vector.hpp:117
static const_iterator end(const int_vector_type *v, const uint64_t *, int_vector_size_type) noexcept
Definition: int_vector.hpp:122
static iterator begin(int_vector_type *v, uint64_t *) noexcept
Definition: int_vector.hpp:116
int_vector_iterator< int_vector_type > iterator
Definition: int_vector.hpp:113
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.