SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <algorithm>
12#include <cassert>
13#include <cinttypes>
14#include <cmath>
15#include <cstddef>
16#include <cstring> // for memcpy
17#include <initializer_list>
18#include <iostream> // for cerr
19#include <iterator>
20#include <new>
21#include <string>
22#include <type_traits>
23#include <utility>
24
25#include <sdsl/bits.hpp>
26#include <sdsl/cereal.hpp>
27#include <sdsl/config.hpp>
28#include <sdsl/io.hpp>
32#include <sdsl/util.hpp>
33
35namespace sdsl
36{
37
39
40template <uint8_t t_width>
41class int_vector;
42
45
46template <class t_int_vector>
48template <class t_int_vector>
50template <class t_int_vector>
52template <class t_int_vector>
54template <uint8_t, uint8_t>
55class rank_support_v;
56template <uint8_t, uint8_t>
58
59namespace coder
60{
61template <typename>
62class elias_delta; // IWYU pragma: keep
63template <typename>
64class elias_gamma; // IWYU pragma: keep
65template <typename>
66class fibonacci; // IWYU pragma: keep
67template <uint8_t>
68class comma; // IWYU pragma: keep
69} // namespace coder
70
71template <uint8_t t_width>
73{
74 typedef iv_tag type;
75};
76
77template <>
79{
80 typedef bv_tag type;
81};
82
83template <uint8_t t_width>
85{
86 typedef uint64_t value_type;
89 typedef uint64_t const_reference;
90 typedef uint8_t int_width_type;
93
94 static iterator begin(int_vector_type * v) noexcept
95 {
96 return iterator(v, 0);
97 }
98 static iterator end(int_vector_type * v) noexcept
99 {
100 return iterator(v, v->size() * v->width());
101 }
102 static const_iterator begin(int_vector_type const * v) noexcept
103 {
104 return const_iterator(v, 0);
105 }
106 static const_iterator end(int_vector_type const * v) noexcept
107 {
108 return const_iterator(v, v->size() * v->width());
109 }
110
111 static void set_width(uint8_t new_width, int_width_type & width) noexcept
112 {
113 if constexpr (t_width == 0)
114 width = new_width ? std::min(new_width, uint8_t{64u}) : 64u;
115 }
116};
117
118template <>
120{
121 typedef uint64_t value_type;
123 typedef uint64_t & reference;
124 typedef uint64_t const_reference;
125 typedef uint8_t int_width_type;
126 typedef uint64_t * iterator;
127 typedef uint64_t const * const_iterator;
128
129 static iterator begin(int_vector_type * v) noexcept;
130 static iterator end(int_vector_type * v) noexcept;
131 static const_iterator begin(int_vector_type const * v) noexcept;
132 static const_iterator end(int_vector_type const * v) noexcept;
133
134 static void set_width(uint8_t, int_width_type) noexcept
135 {}
136};
137
138template <>
140{
141 typedef uint32_t value_type;
143 typedef uint32_t & reference;
144 typedef uint32_t const_reference;
145 typedef uint8_t int_width_type;
146 typedef uint32_t * iterator;
147 typedef uint32_t const * const_iterator;
148
149 static iterator begin(int_vector_type * v) noexcept;
150 static iterator end(int_vector_type * v) noexcept;
151 static const_iterator begin(int_vector_type const * v) noexcept;
152 static const_iterator end(int_vector_type const * v) noexcept;
153
154 static void set_width(uint8_t, int_width_type) noexcept
155 {}
156};
157
158template <>
160{
161 typedef uint16_t value_type;
163 typedef uint16_t & reference;
164 typedef uint16_t const_reference;
165 typedef uint8_t int_width_type;
166 typedef uint16_t * iterator;
167 typedef uint16_t const * const_iterator;
168
169 static iterator begin(int_vector_type * v) noexcept;
170 static iterator end(int_vector_type * v) noexcept;
171 static const_iterator begin(int_vector_type const * v) noexcept;
172 static const_iterator end(int_vector_type const * v) noexcept;
173
174 static void set_width(uint8_t, int_width_type) noexcept
175 {}
176};
177
178template <>
180{
181 typedef uint8_t value_type;
183 typedef uint8_t & reference;
184 typedef uint8_t const_reference;
185 typedef uint8_t int_width_type;
186 typedef uint8_t * iterator;
187 typedef uint8_t const * const_iterator;
188
189 static iterator begin(int_vector_type * v) noexcept;
190 static iterator end(int_vector_type * v) noexcept;
191 static const_iterator begin(int_vector_type const * v) noexcept;
192 static const_iterator end(int_vector_type const * v) noexcept;
193
194 static void set_width(uint8_t, int_width_type) noexcept
195 {}
196};
197
199
210template <uint8_t t_width>
212{
213private:
214 static_assert(t_width <= 64, "int_vector: width of must be at most 64bits.");
215
216public:
223 typedef value_type const * const_pointer;
224 typedef ptrdiff_t difference_type;
232
233 friend struct int_vector_trait<t_width>;
235 friend class int_vector_iterator<int_vector>;
237 template <uint8_t, std::ios_base::openmode>
238 friend class int_vector_mapper;
239 template <typename T>
240 friend class coder::elias_delta;
241 template <typename T>
242 friend class coder::elias_gamma;
243 template <typename T>
244 friend class coder::fibonacci;
245 template <uint8_t>
246 friend class coder::comma;
247 friend class memory_manager;
248 static constexpr uint8_t fixed_int_width = t_width;
249 float growth_factor = 1.5;
250 // see the explanation in the documentation of FBVector on different growth factors
251 // https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#memory-handling
252
253private:
254 size_type m_size;
255 size_type m_capacity;
256 uint64_t * m_data;
257 int_width_type m_width;
258
259 // Hidden, since number of bits (size) does not go well together with int value.
260 void bit_resize(const size_type size, const value_type value);
261
262 void amortized_resize(const size_type size)
263 {
264 assert(growth_factor > 1.0);
265 if constexpr (t_width != 0)
266 {
267 size_type const bit_size{size * t_width};
268 if (bit_size > m_capacity || m_data == nullptr)
269 {
270 // start with 64 bit if vector has no capacity
271 size_type new_capacity = std::max<size_type>(m_capacity, 64u);
272 // find smallest x s.t. m_capacity * 1.5 ** x >= size
273 while (new_capacity < bit_size)
274 new_capacity *= growth_factor;
275 memory_manager::resize(*this, new_capacity);
276 }
277 m_size = bit_size;
278 }
279 else
280 {
281 size_type const bit_size{size * m_width};
282 if (bit_size > m_capacity || m_data == nullptr)
283 {
284 // start with 64 bit if vector has no capacity
285 size_type new_capacity = std::max<size_type>(m_capacity, 64u);
286 // find smallest x s.t. m_capacity * 1.5 ** x >= size
287 while (new_capacity < bit_size)
288 new_capacity *= growth_factor;
289 memory_manager::resize(*this, new_capacity);
290 }
291 m_size = bit_size;
292 }
293 }
294
295 // The number of 64-bit words used by the int_vector.
296 size_type bit_data_size() const
297 {
298 return (m_size + 63) >> 6;
299 }
300
301public:
303
309 int_vector(size_type size, value_type default_value, uint8_t int_width = t_width);
310
312 explicit int_vector(size_type size = 0) : int_vector(size, static_cast<value_type>(0), t_width)
313 {}
315 int_vector(std::initializer_list<value_type> il) : int_vector(0, 0)
316 {
317 assign(il);
318 }
319
321
324 template <typename input_iterator_t>
325 int_vector(typename std::enable_if<
326 std::is_base_of<std::input_iterator_tag,
327 typename std::iterator_traits<input_iterator_t>::iterator_category>::value,
328 input_iterator_t>::type first,
329 input_iterator_t last) :
330 int_vector(0, 0)
331 {
332 assign(first, last);
333 }
334
336
338 void clear() noexcept
339 {
340 m_size = 0;
341 }
342
344
347 {
348 iterator it_nonconst = begin() + (it - cbegin());
349 std::copy(it_nonconst + 1, end(), it_nonconst);
350 resize(size() - 1);
351 return it_nonconst;
352 }
353
355
359 {
360 iterator first_nonconst = begin() + (first - cbegin());
361 iterator last_nonconst = begin() + (last - cbegin());
362 std::copy(last_nonconst, end(), first_nonconst);
363 resize(size() - (last - first));
364 return first_nonconst;
365 }
366
368
371 template <class... Args>
372 iterator emplace(const_iterator it, Args &&... args)
373 {
374 return insert(it, 1, value_type(std::forward<Args>(args)...));
375 }
376
378
382 {
383 return insert(it, 1, value);
384 }
385
387
392 {
393 size_type pos = it - cbegin();
394 amortized_resize(size() + n);
395 iterator it_new = begin() + pos;
396 std::copy_backward(it_new, end() - n, end());
397 std::fill_n(it_new, n, value);
398 return it_new;
399 }
400
402
405 iterator insert(const_iterator it, std::initializer_list<value_type> il)
406 {
407 return insert(it, il.begin(), il.end());
408 }
409
411
415 template <typename input_iterator_t>
416 typename std::enable_if<std::is_base_of<std::input_iterator_tag,
417 typename std::iterator_traits<input_iterator_t>::iterator_category>::value,
418 iterator>::type
419 insert(const_iterator it, input_iterator_t first, input_iterator_t last)
420 {
421 size_type pos = it - cbegin();
422 amortized_resize(size() + last - first);
423 iterator it_new = begin() + pos;
424 std::copy_backward(it_new, end() - (last - first), end());
425 std::copy(first, last, it_new);
426 return it_new;
427 }
428
430 reference front() noexcept
431 {
432 return *begin();
433 }
434
436 const_reference front() const noexcept
437 {
438 return *cbegin();
439 }
440
442 reference back() noexcept
443 {
444 return *(end() - 1);
445 }
446
448 const_reference back() const noexcept
449 {
450 return *(cend() - 1);
451 }
452
454
456 template <class... Args>
457 void emplace_back(Args &&... args)
458 {
459 push_back(value_type(std::forward<Args>(args)...));
460 }
461
463
466 {
467 amortized_resize(size() + 1);
468 *(end() - 1) = value;
469 }
470
472 void pop_back()
473 {
474 resize(size() - 1);
475 }
476
479
482
485
487
490 void assign(size_type size, value_type default_value)
491 {
492 bit_resize(size * m_width);
493 util::set_to_value(*this, default_value); // new initialization
494 }
495
497
499 void assign(std::initializer_list<value_type> il)
500 {
501 bit_resize(il.size() * m_width);
502 size_type idx = 0;
503 for (auto x : il)
504 {
505 (*this)[idx++] = x;
506 }
507 }
508
510
513 template <typename input_iterator_t>
514 void assign(input_iterator_t first, input_iterator_t last)
515 {
516 assert(first <= last);
517 bit_resize((last - first) * m_width);
518 size_type idx = 0;
519 while (first < last)
520 {
521 (*this)[idx++] = *(first++);
522 }
523 }
524
526 bool empty() const noexcept
527 {
528 return 0 == m_size;
529 }
530
532 void swap(int_vector & v) noexcept
533 {
534 std::swap(v, *this);
535 }
536
539 {
540 memory_manager::resize(*this, m_size);
541 }
542
544
547 {
548 if (capacity * m_width > m_capacity || m_data == nullptr)
549 {
550 memory_manager::resize(*this, capacity * m_width);
551 }
552 }
553
556
560 {
561 resize(size, 0);
562 }
563
565
568 void resize(const size_type size, const value_type value)
569 {
570 bit_resize(size * m_width, value);
571 }
572
574
577
579
581 inline size_type size() const noexcept;
582
584
586 static size_type max_size() noexcept
587 {
588 return ((size_type)1) << (sizeof(size_type) * 8 - 6);
589 }
590
592
594 size_type bit_size() const noexcept
595 {
596 return m_size;
597 }
598
600
604 inline size_type capacity() const noexcept;
605
607
611 size_type bit_capacity() const noexcept
612 {
613 return m_capacity;
614 }
615
617
619 uint64_t const * data() const noexcept
620 {
621 return m_data;
622 }
623
625
627 uint64_t * data() noexcept
628 {
629 return m_data;
630 }
631
633
638 value_type get_int(size_type idx, const uint8_t len = 64) const;
639
641
648 void set_int(size_type idx, value_type x, const uint8_t len = 64);
649
651
654 uint8_t width() const noexcept
655 {
656 return m_width;
657 }
658
660
664 void width(uint8_t new_width) noexcept
665 {
666 int_vector_trait<t_width>::set_width(new_width, m_width);
667 }
668
669 // Write data (without header) to a stream.
670 size_type write_data(std::ostream & out) const;
671
673
676 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
677
679 void load(std::istream & in);
680
681 /* For cereal we need to define different versions of the load and save function depending on whether we want
682 * binary data or text (XML/JSON) data.
683 * See https://github.com/USCiLab/cereal/blob/master/include/cereal/types/vector.hpp for an example.
684 */
685
687 template <typename archive_t>
688 inline typename std::enable_if<
690 void>::type
691 CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
692
694 template <typename archive_t>
695 inline typename std::enable_if<
697 void>::type
698 CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
699
701 template <typename archive_t>
702 inline typename std::enable_if<
704 void>::type
706
708 template <typename archive_t>
709 inline typename std::enable_if<
711 void>::type
713
715
718 inline reference operator[](size_type const & i) noexcept;
719
721
724 inline const_reference operator[](size_type const & i) const noexcept;
725
727
731 {
732 return (*this)[i];
733 }
734
736
739 const_reference at(size_type const & i) const
740 {
741 return (*this)[i];
742 }
743
745
748
751
753
757 bool operator==(int_vector<t_width> const & v) const noexcept
758 {
759 if (bit_size() != v.bit_size())
760 return false;
761 if (empty())
762 return true;
763 uint64_t const * data1 = v.data();
764 uint64_t const * data2 = data();
765 for (size_type i = 0; i < bit_data_size() - 1; ++i)
766 {
767 if (*(data1++) != *(data2++))
768 return false;
769 }
770 uint8_t l = 64 - ((bit_data_size() << 6) - m_size);
771 return ((*data1) & bits::lo_set[l]) == ((*data2) & bits::lo_set[l]);
772 }
773
775
781 template <uint8_t t_width2>
782 bool operator==(int_vector<t_width2> const & v) const noexcept
783 {
784 return (this->size() == v.size()) && std::equal(this->begin(), this->end(), v.begin());
785 }
786
788
794 template <uint8_t t_width2>
795 bool operator!=(int_vector<t_width2> const & v) const noexcept
796 {
797 return !(*this == v);
798 }
799
801
806 bool operator<(int_vector const & v) const noexcept;
807
809
813 bool operator>(int_vector const & v) const noexcept;
814
816 bool operator<=(int_vector const & v) const noexcept;
817
819 bool operator>=(int_vector const & v) const noexcept;
820
823
826
829
831
833 iterator begin() noexcept
834 {
836 }
837
839
841 iterator end() noexcept
842 {
844 }
845
847 const_iterator begin() const noexcept
848 {
850 }
851
853 const_iterator end() const noexcept
854 {
856 }
857
859 const_iterator cbegin() const noexcept
860 {
862 }
863
865 const_iterator cend() const noexcept
866 {
868 }
869
871 void flip()
872 {
873 static_assert(1 == t_width, "int_vector: flip() is available only for bit_vector.");
874 if (!empty())
875 {
876 for (uint64_t i = 0; i < bit_data_size(); ++i)
877 {
878 m_data[i] = ~m_data[i];
879 }
880 }
881 }
882
884 static size_t read_header(int_vector_size_type & size, int_width_type & int_width, std::istream & in)
885 {
886 uint64_t width_and_size = 0;
887 read_member(width_and_size, in);
888 size = width_and_size & bits::lo_set[56];
889 uint8_t read_int_width = (uint8_t)(width_and_size >> 56);
890 if (t_width == 0)
891 {
892 int_width = read_int_width;
893 }
894 if (t_width > 0 and t_width != read_int_width)
895 {
896 std::cerr << "Warning: Width of int_vector<" << (size_t)t_width << ">";
897 std::cerr << " was specified as " << (size_type)read_int_width << std::endl;
898 std::cerr << "Length is " << size << " bits" << std::endl;
899 }
900 return sizeof(width_and_size);
901 }
902
904 static uint64_t write_header(uint64_t size, uint8_t int_width, std::ostream & out)
905 {
906 if (t_width > 0)
907 {
908 if (t_width != int_width)
909 {
910 std::cout << "Warning: writing width=" << (size_type)int_width << " != fixed " << (size_type)t_width
911 << std::endl;
912 }
913 }
914 uint64_t width_and_size = (((uint64_t)int_width) << 56) | size;
915 return write_member(width_and_size, out);
916 }
917
919 {
921 raw_wrapper() = delete;
922 raw_wrapper(int_vector const & _vec) : vec(_vec)
923 {}
924
925 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
926 {
927 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
928 auto written_bytes = vec.write_data(out);
929 structure_tree::add_size(child, written_bytes);
930 return written_bytes;
931 }
932 };
933
935};
936
938
940template <class t_int_vector>
942{
943public:
944 typedef typename t_int_vector::value_type value_type;
945
946private:
947 typename t_int_vector::value_type * const m_word;
948 const uint8_t m_offset;
949 const uint8_t m_len;
950
951public:
955 constexpr int_vector_reference(int_vector_reference const &) noexcept = default;
956 constexpr int_vector_reference(int_vector_reference &&) noexcept = default;
957
959
963 int_vector_reference(value_type * word, uint8_t offset, uint8_t len) noexcept :
964 m_word(word),
965 m_offset(offset),
966 m_len(len){};
967
969
977 {
978 bits::write_int(m_word, x, m_offset, m_len);
979 return *this;
980 };
981
983 {
984 return *this = value_type(x);
985 };
986
988 {
989 return *this = value_type(std::move(x));
990 };
991
993 operator value_type() const noexcept
994 {
995 return bits::read_int(m_word, m_offset, m_len);
996 }
997
1000 {
1001 value_type x = bits::read_int(m_word, m_offset, m_len);
1002 bits::write_int(m_word, x + 1, m_offset, m_len);
1003 return *this;
1004 }
1005
1008 {
1009 value_type val = (typename t_int_vector::value_type) * this;
1010 ++(*this);
1011 return val;
1012 }
1013
1016 {
1017 value_type x = bits::read_int(m_word, m_offset, m_len);
1018 bits::write_int(m_word, x - 1, m_offset, m_len);
1019 return *this;
1020 }
1021
1024 {
1025 value_type val = (value_type) * this;
1026 --(*this);
1027 return val;
1028 }
1029
1032 {
1033 value_type w = bits::read_int(m_word, m_offset, m_len);
1034 bits::write_int(m_word, w + x, m_offset, m_len);
1035 return *this;
1036 }
1037
1040 {
1041 value_type w = bits::read_int(m_word, m_offset, m_len);
1042 bits::write_int(m_word, w - x, m_offset, m_len);
1043 return *this;
1044 }
1045
1046 bool operator==(int_vector_reference const & x) const noexcept
1047 {
1048 return value_type(*this) == value_type(x);
1049 }
1050
1051 bool operator<(int_vector_reference const & x) const noexcept
1052 {
1053 return value_type(*this) < value_type(x);
1054 }
1055};
1056
1057// For C++11
1058template <class t_int_vector>
1060{
1061 // TODO: more efficient solution?
1063 x = y;
1064 y = tmp;
1065}
1066
1067// For C++11
1068template <class t_int_vector>
1071{
1072 // TODO: more efficient solution?
1074 x = y;
1075 y = tmp;
1076}
1077
1078// For C++11
1079template <class t_int_vector>
1082{
1083 // TODO: more efficient solution?
1085 x = y;
1086 y = tmp;
1087}
1088
1089// specialization for int_vector_reference for int_vector == bit_vector
1090// special thanks to Timo Beller, who pointed out that the specialization is missing
1091// Same implementation as in stl_bvector.h.
1092template <>
1094{
1095public:
1096 typedef bool value_type;
1097
1098private:
1099 uint64_t * const m_word;
1100 uint64_t m_mask;
1101
1102public:
1106 constexpr int_vector_reference(int_vector_reference const &) noexcept = default;
1107 constexpr int_vector_reference(int_vector_reference &&) noexcept = default;
1108
1110
1113 int_vector_reference(uint64_t * word, uint8_t offset, uint8_t) noexcept : m_word(word), m_mask(1ULL << offset){};
1114
1117 {
1118 if (x)
1119 *m_word |= m_mask;
1120 else
1121 *m_word &= ~m_mask;
1122 return *this;
1123 };
1124
1126 {
1127 return *this = bool(x);
1128 };
1130 {
1131 return *this = bool(x);
1132 };
1133
1135 operator bool() const noexcept
1136 {
1137 return !!(*m_word & m_mask);
1138 }
1139
1140 bool operator==(int_vector_reference const & x) const noexcept
1141 {
1142 return bool(*this) == bool(x);
1143 }
1144
1145 bool operator<(int_vector_reference const & x) const noexcept
1146 {
1147 return !bool(*this) && bool(x);
1148 }
1149};
1150
1151// For C++11
1152template <>
1154{
1155 // TODO: more efficient solution?
1156 bool tmp = x;
1157 x = y;
1158 y = tmp;
1159}
1160
1161// For C++11
1162template <>
1163inline void swap(bool & x, int_vector_reference<bit_vector> y) noexcept
1164{
1165 // TODO: more efficient solution?
1166 bool tmp = x;
1167 x = y;
1168 y = tmp;
1169}
1170
1171// For C++11
1172template <>
1173inline void swap(int_vector_reference<bit_vector> x, bool & y) noexcept
1174{
1175 // TODO: more efficient solution?
1176 bool tmp = x;
1177 x = y;
1178 y = tmp;
1179}
1180
1181template <class t_int_vector>
1183{
1184public:
1185 using iterator_category = std::random_access_iterator_tag;
1186 using value_type = typename t_int_vector::value_type;
1187 using difference_type = typename t_int_vector::difference_type;
1190
1191 typedef uint64_t size_type;
1192
1193protected:
1194 uint8_t m_offset;
1195 uint8_t m_len;
1196
1197public:
1198 int_vector_iterator_base(uint8_t offset, uint8_t len) : m_offset(offset), m_len(len)
1199 {}
1200
1201 int_vector_iterator_base(t_int_vector const * v = nullptr, size_type idx = 0) :
1202 m_offset(idx & 0x3F),
1203 m_len(v == nullptr ? 0 : v->m_width)
1204 {}
1205};
1206
1207template <class t_int_vector>
1209{
1210public:
1212 typedef uint64_t value_type;
1215 typedef typename t_int_vector::size_type size_type;
1216 typedef typename t_int_vector::difference_type difference_type;
1217
1218 friend class int_vector_const_iterator<t_int_vector>;
1219
1220private:
1221 using int_vector_iterator_base<t_int_vector>::m_offset; // make m_offset easy usable
1222 using int_vector_iterator_base<t_int_vector>::m_len; // make m_len easy usable
1223
1224 typename t_int_vector::value_type * m_word;
1225
1226public:
1227 int_vector_iterator(t_int_vector * v = nullptr, size_type idx = 0) :
1228 int_vector_iterator_base<t_int_vector>(v, idx),
1229 m_word((v != nullptr) ? v->m_data + (idx >> 6) : nullptr)
1230 {}
1231
1233 int_vector_iterator_base<t_int_vector>(it),
1234 m_word(it.m_word)
1235 {
1236 m_offset = it.m_offset;
1237 m_len = it.m_len;
1238 }
1239
1241 {
1242 return reference(m_word, m_offset, m_len);
1243 }
1244
1247 {
1248 m_offset += m_len;
1249 if (m_offset >= 64)
1250 {
1251 m_offset &= 0x3F;
1252 ++m_word;
1253 }
1254 return *this;
1255 }
1256
1259 {
1260 int_vector_iterator it = *this;
1261 ++(*this);
1262 return it;
1263 }
1264
1267 {
1268 m_offset -= m_len;
1269 if (m_offset >= 64)
1270 {
1271 m_offset &= 0x3F;
1272 --m_word;
1273 }
1274 return *this;
1275 }
1276
1279 {
1280 int_vector_iterator it = *this;
1281 --(*this);
1282 return it;
1283 }
1284
1286 {
1287 if (i < 0)
1288 return *this -= (-i);
1289 difference_type t = i * m_len;
1290 m_word += (t >> 6);
1291 if ((m_offset += (t & 0x3F)) & ~0x3F)
1292 { // if new offset is >= 64
1293 ++m_word; // add one to the word
1294 m_offset &= 0x3F; // offset = offset mod 64
1295 }
1296 return *this;
1297 }
1298
1300 {
1301 if (i < 0)
1302 return *this += (-i);
1303 difference_type t = i * m_len;
1304 m_word -= (t >> 6);
1305 if ((m_offset -= (t & 0x3F)) & ~0x3F)
1306 { // if new offset is < 0
1307 --m_word;
1308 m_offset &= 0x3F;
1309 }
1310 return *this;
1311 }
1312
1314 {
1315 if (this != &it)
1316 {
1317 m_word = it.m_word;
1318 m_offset = it.m_offset;
1319 m_len = it.m_len;
1320 }
1321 return *this;
1322 }
1323
1325 {
1326 iterator it = *this;
1327 return it += i;
1328 }
1329
1331 {
1332 iterator it = *this;
1333 return it -= i;
1334 }
1335
1337 {
1338 return *(*this + i);
1339 }
1340
1341 bool operator==(int_vector_iterator const & it) const noexcept
1342 {
1343 return it.m_word == m_word && it.m_offset == m_offset;
1344 }
1345
1346 bool operator!=(int_vector_iterator const & it) const noexcept
1347 {
1348 return !(*this == it);
1349 }
1350
1351 bool operator<(int_vector_iterator const & it) const noexcept
1352 {
1353 if (m_word == it.m_word)
1354 return m_offset < it.m_offset;
1355 return m_word < it.m_word;
1356 }
1357
1358 bool operator>(int_vector_iterator const & it) const noexcept
1359 {
1360 if (m_word == it.m_word)
1361 return m_offset > it.m_offset;
1362 return m_word > it.m_word;
1363 }
1364
1365 bool operator>=(int_vector_iterator const & it) const noexcept
1366 {
1367 return !(*this < it);
1368 }
1369
1370 bool operator<=(int_vector_iterator const & it) const noexcept
1371 {
1372 return !(*this > it);
1373 }
1374 inline difference_type operator-(int_vector_iterator const & it) const noexcept
1375 {
1376 return (((m_word - it.m_word) << 6) + m_offset - it.m_offset) / m_len;
1377 }
1378};
1379
1380// template<class t_int_vector>
1381// void swap(const int_vector_iterator<t_int_vector> &x, const int_vector_iterator<t_int_vector> &y){
1382// x->swap(*y);
1383//}
1384
1385template <class t_int_vector>
1391
1392template <class t_int_vector>
1394{
1395public:
1396 typedef typename t_int_vector::value_type const_reference;
1397 typedef const typename t_int_vector::value_type * pointer;
1399 typedef typename t_int_vector::size_type size_type;
1400 typedef typename t_int_vector::difference_type difference_type;
1401
1402 template <class X>
1405 friend class int_vector_iterator<t_int_vector>;
1406 friend class int_vector_iterator_base<t_int_vector>;
1407
1408private:
1409 using int_vector_iterator_base<t_int_vector>::m_offset; // make m_offset easy usable
1410 using int_vector_iterator_base<t_int_vector>::m_len; // make m_len easy usable
1411
1412 const typename t_int_vector::value_type * m_word;
1413
1414public:
1415 int_vector_const_iterator(t_int_vector const * v = nullptr, size_type idx = 0) :
1416 int_vector_iterator_base<t_int_vector>(v, idx),
1417 m_word((v != nullptr) ? v->m_data + (idx >> 6) : nullptr)
1418 {}
1419
1421 {
1422 m_offset = it.m_offset;
1423 m_len = it.m_len;
1424 }
1425
1427
1429
1431 {
1432 if (m_offset + m_len <= 64)
1433 {
1434 return ((*m_word) >> m_offset) & bits::lo_set[m_len];
1435 }
1436 return ((*m_word) >> m_offset) | ((*(m_word + 1) & bits::lo_set[(m_offset + m_len) & 0x3F]) << (64 - m_offset));
1437 }
1438
1441 {
1442 m_offset += m_len;
1443 if (m_offset >= 64)
1444 {
1445 m_offset &= 0x3F;
1446 ++m_word;
1447 }
1448 return *this;
1449 }
1450
1453 {
1454 int_vector_const_iterator it = *this;
1455 ++(*this);
1456 return it;
1457 }
1458
1461 {
1462 m_offset -= m_len;
1463 if (m_offset >= 64)
1464 {
1465 m_offset &= 0x3F;
1466 --m_word;
1467 }
1468 return *this;
1469 }
1470
1473 {
1474 int_vector_const_iterator it = *this;
1475 --(*this);
1476 return it;
1477 }
1478
1480 {
1481 if (i < 0)
1482 return *this -= (-i);
1483 difference_type t = i * m_len;
1484 m_word += (t >> 6);
1485 if ((m_offset += (t & 0x3F)) & ~0x3F)
1486 { // if new offset >= 64
1487 ++m_word; // add one to the word
1488 m_offset &= 0x3F; // offset = offset mod 64
1489 }
1490 return *this;
1491 }
1492
1494 {
1495 if (i < 0)
1496 return *this += (-i);
1497 difference_type t = i * m_len;
1498 m_word -= (t >> 6);
1499 if ((m_offset -= (t & 0x3F)) & ~0x3F)
1500 { // if new offset is < 0
1501 --m_word;
1502 m_offset &= 0x3F;
1503 }
1504 return *this;
1505 }
1506
1508 {
1509 const_iterator it = *this;
1510 return it += i;
1511 }
1512
1514 {
1515 const_iterator it = *this;
1516 return it -= i;
1517 }
1518
1520 {
1521 return *(*this + i);
1522 }
1523
1524 bool operator==(int_vector_const_iterator const & it) const noexcept
1525 {
1526 return it.m_word == m_word && it.m_offset == m_offset;
1527 }
1528
1529 bool operator!=(int_vector_const_iterator const & it) const noexcept
1530 {
1531 return !(*this == it);
1532 }
1533
1534 bool operator<(int_vector_const_iterator const & it) const noexcept
1535 {
1536 if (m_word == it.m_word)
1537 return m_offset < it.m_offset;
1538 return m_word < it.m_word;
1539 }
1540
1541 bool operator>(int_vector_const_iterator const & it) const noexcept
1542 {
1543 if (m_word == it.m_word)
1544 return m_offset > it.m_offset;
1545 return m_word > it.m_word;
1546 }
1547
1548 bool operator>=(int_vector_const_iterator const & it) const noexcept
1549 {
1550 return !(*this < it);
1551 }
1552
1553 bool operator<=(int_vector_const_iterator const & it) const noexcept
1554 {
1555 return !(*this > it);
1556 }
1557};
1558
1559template <class t_int_vector>
1562{
1563 return (((x.m_word - y.m_word) << 6) + x.m_offset - y.m_offset) / x.m_len;
1564}
1565
1566template <class t_int_vector>
1567inline int_vector_const_iterator<t_int_vector>
1573
1574template <class t_bv>
1575inline typename std::enable_if<std::is_same<typename t_bv::index_category, bv_tag>::value, std::ostream &>::type
1576operator<<(std::ostream & os, t_bv const & bv)
1577{
1578 for (auto b : bv)
1579 {
1580 os << b;
1581 }
1582 return os;
1583}
1584
1585// ==== int_vector implementation ====
1586
1587template <uint8_t t_width>
1588inline int_vector<t_width>::int_vector(size_type size, value_type default_value, uint8_t int_width) :
1589 m_size(0),
1590 m_capacity(0),
1591 m_data(nullptr),
1592 m_width(t_width)
1593{
1594 width(int_width);
1595 assign(size, default_value);
1596}
1597
1598template <uint8_t t_width>
1600 m_size(v.m_size),
1601 m_capacity(v.m_capacity),
1602 m_data(v.m_data),
1603 m_width(v.m_width)
1604{
1605 v.m_data = nullptr; // ownership of v.m_data now transfered
1606 v.m_size = 0;
1607 v.m_capacity = 0;
1608}
1609
1610template <uint8_t t_width>
1612 m_size(0),
1613 m_capacity(0),
1614 m_data(nullptr),
1615 m_width(v.m_width)
1616{
1617 width(v.m_width);
1618 resize(v.size());
1619 if (v.m_size > 0)
1620 {
1621 if (memcpy(m_data, v.data(), bit_data_size() << 3) == nullptr)
1622 {
1623 throw std::bad_alloc(); // LCOV_EXCL_LINE
1624 }
1625 }
1626}
1627
1628template <uint8_t t_width>
1630{
1631 if (this != &v)
1632 { // if v is not the same object
1633 int_vector<t_width> tmp(v);
1634 *this = std::move(tmp);
1635 }
1636 return *this;
1637}
1638
1639template <uint8_t t_width>
1641{
1642 if (this != &v)
1643 { // if v is not the same object
1644 memory_manager::clear(*this); // clear allocated memory
1645 m_size = v.m_size;
1646 m_data = v.m_data; // assign new memory
1647 m_width = v.m_width;
1648 m_capacity = v.m_capacity;
1649 v.m_data = nullptr;
1650 v.m_size = 0;
1651 v.m_capacity = 0;
1652 }
1653 return *this;
1654}
1655
1656// Destructor
1657template <uint8_t t_width>
1662
1663// sdsl::swap (to fulfill the container concept)
1664template <uint8_t t_width>
1666{
1667 std::swap(v1, v2);
1668}
1669
1670template <uint8_t t_width>
1672{
1673 if (size > m_capacity || m_data == nullptr)
1674 {
1676 }
1677 m_size = size;
1678}
1679
1680template <uint8_t t_width>
1681void int_vector<t_width>::bit_resize(const size_type size, const value_type value)
1682{
1683 size_type old_size = m_size;
1684 bit_resize(size);
1685 auto it = begin() + old_size / m_width;
1686 util::set_to_value(*this, value, it);
1687}
1688
1689template <uint8_t t_width>
1690auto int_vector<t_width>::get_int(size_type idx, const uint8_t len) const -> value_type
1691{
1692#ifdef SDSL_DEBUG
1693 if (idx + len > m_size)
1694 {
1695 throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::get_int(size_type, uint8_t); idx+len > size()!");
1696 }
1697 if (len > 64)
1698 {
1699 throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::get_int(size_type, uint8_t); len>64!");
1700 }
1701#endif
1702 return bits::read_int(m_data + (idx >> 6), idx & 0x3F, len);
1703}
1704
1705template <uint8_t t_width>
1706inline void int_vector<t_width>::set_int(size_type idx, value_type x, const uint8_t len)
1707{
1708#ifdef SDSL_DEBUG
1709 if (idx + len > m_size)
1710 {
1711 throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::set_int(size_type, uint8_t); idx+len > size()!");
1712 }
1713 if (len > 64)
1714 {
1715 throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::set_int(size_type, uint8_t); len>64!");
1716 }
1717#endif
1718 bits::write_int(m_data + (idx >> 6), x, idx & 0x3F, len);
1719}
1720
1721template <uint8_t t_width>
1723{
1724 return m_size / t_width;
1725}
1726
1727// specialized size method for 64-bit integer vector
1728template <>
1729inline typename int_vector<64>::size_type int_vector<64>::size() const noexcept
1730{
1731 return m_size >> 6;
1732}
1733
1734// specialized size method for 32-bit integer vector
1735template <>
1736inline typename int_vector<32>::size_type int_vector<32>::size() const noexcept
1737{
1738 return m_size >> 5;
1739}
1740
1741// specialized size method for 16-bit integer vector
1742template <>
1743inline typename int_vector<16>::size_type int_vector<16>::size() const noexcept
1744{
1745 return m_size >> 4;
1746}
1747
1748// specialized size method for 8-bit integer vector
1749template <>
1750inline typename int_vector<8>::size_type int_vector<8>::size() const noexcept
1751{
1752 return m_size >> 3;
1753}
1754
1755// specialized size method for bit_vector
1756template <>
1757inline typename int_vector<1>::size_type int_vector<1>::size() const noexcept
1758{
1759 return m_size;
1760}
1761
1762// specialized size method for dyanmic int_vector
1763template <>
1764inline typename int_vector<0>::size_type int_vector<0>::size() const noexcept
1765{
1766 return m_size / m_width;
1767}
1768
1769template <uint8_t t_width>
1771{
1772 return m_capacity / t_width;
1773}
1774
1775// specialized capacity method for 64-bit integer vector
1776template <>
1778{
1779 return m_capacity >> 6;
1780}
1781
1782// specialized capacity method for 32-bit integer vector
1783template <>
1785{
1786 return m_capacity >> 5;
1787}
1788
1789// specialized capacity method for 16-bit integer vector
1790template <>
1792{
1793 return m_capacity >> 4;
1794}
1795
1796// specialized capacity method for 8-bit integer vector
1797template <>
1799{
1800 return m_capacity >> 3;
1801}
1802
1803// specialized capacity method for bit_vector
1804template <>
1806{
1807 return m_capacity;
1808}
1809
1810// specialized capacity method for dynamic int_vector
1811template <>
1813{
1814 return m_capacity / m_width;
1815}
1816
1817template <uint8_t t_width>
1818inline auto int_vector<t_width>::operator[](size_type const & idx) noexcept -> reference
1819{
1820 assert(idx < this->size());
1821 size_type i = idx * m_width;
1822 return reference(this->m_data + (i >> 6), i & 0x3F, m_width);
1823}
1824
1825// specialized [] operator for 64 bit access.
1826template <>
1827inline auto int_vector<64>::operator[](size_type const & idx) noexcept -> reference
1828{
1829 assert(idx < this->size());
1830 return *(this->m_data + idx);
1831}
1832
1833// specialized [] operator for 32 bit access.
1834template <>
1835inline auto int_vector<32>::operator[](size_type const & idx) noexcept -> reference
1836{
1837 assert(idx < this->size());
1838 return *(((uint32_t *)(this->m_data)) + idx);
1839}
1840
1841// specialized [] operator for 16 bit access.
1842template <>
1843inline auto int_vector<16>::operator[](size_type const & idx) noexcept -> reference
1844{
1845 assert(idx < this->size());
1846 return *(((uint16_t *)(this->m_data)) + idx);
1847}
1848
1849// specialized [] operator for 8 bit access.
1850template <>
1851inline auto int_vector<8>::operator[](size_type const & idx) noexcept -> reference
1852{
1853 assert(idx < this->size());
1854 return *(((uint8_t *)(this->m_data)) + idx);
1855}
1856
1857template <uint8_t t_width>
1858inline auto int_vector<t_width>::operator[](size_type const & idx) const noexcept -> const_reference
1859{
1860 assert(idx < this->size());
1861 return get_int(idx * t_width, t_width);
1862}
1863
1864template <>
1865inline auto int_vector<0>::operator[](size_type const & idx) const noexcept -> const_reference
1866{
1867 assert(idx < this->size());
1868 return get_int(idx * m_width, m_width);
1869}
1870
1871template <>
1872inline auto int_vector<64>::operator[](size_type const & idx) const noexcept -> const_reference
1873{
1874 assert(idx < this->size());
1875 return *(this->m_data + idx);
1876}
1877
1878template <>
1879inline auto int_vector<32>::operator[](size_type const & idx) const noexcept -> const_reference
1880{
1881 assert(idx < this->size());
1882 return *(((uint32_t *)this->m_data) + idx);
1883}
1884
1885template <>
1886inline auto int_vector<16>::operator[](size_type const & idx) const noexcept -> const_reference
1887{
1888 assert(idx < this->size());
1889 return *(((uint16_t *)this->m_data) + idx);
1890}
1891
1892template <>
1893inline auto int_vector<8>::operator[](size_type const & idx) const noexcept -> const_reference
1894{
1895 assert(idx < this->size());
1896 return *(((uint8_t *)this->m_data) + idx);
1897}
1898
1899template <>
1900inline auto int_vector<1>::operator[](size_type const & idx) const noexcept -> const_reference
1901{
1902 assert(idx < this->size());
1903 return ((*(m_data + (idx >> 6))) >> (idx & 0x3F)) & 1;
1904}
1905
1906template <uint8_t t_width>
1907bool int_vector<t_width>::operator<(int_vector const & v) const noexcept
1908{
1909 size_type min_size = size();
1910 if (min_size > v.size())
1911 min_size = v.size();
1912 for (auto it = begin(), end = begin() + min_size, it_v = v.begin(); it != end; ++it, ++it_v)
1913 {
1914 if (*it == *it_v)
1915 continue;
1916 else
1917 return *it < *it_v;
1918 }
1919 return size() < v.size();
1920}
1921
1922template <uint8_t t_width>
1923bool int_vector<t_width>::operator>(int_vector const & v) const noexcept
1924{
1925 size_type min_size = size();
1926 if (min_size > v.size())
1927 min_size = v.size();
1928 for (auto it = begin(), end = begin() + min_size, it_v = v.begin(); it != end; ++it, ++it_v)
1929 {
1930 if (*it == *it_v)
1931 continue;
1932 else
1933 return *it > *it_v;
1934 }
1935 return size() > v.size();
1936}
1937
1938template <uint8_t t_width>
1939bool int_vector<t_width>::operator<=(int_vector const & v) const noexcept
1940{
1941 return *this == v or *this < v;
1942}
1943
1944template <uint8_t t_width>
1945bool int_vector<t_width>::operator>=(int_vector const & v) const noexcept
1946{
1947 return *this == v or *this > v;
1948}
1949
1950template <uint8_t t_width>
1952{
1953 assert(v.bit_size() == bit_size());
1954 for (uint64_t i = 0; i < bit_data_size(); ++i)
1955 m_data[i] &= v.m_data[i];
1956 return *this;
1957}
1958
1959template <uint8_t t_width>
1961{
1962 assert(bit_size() == v.bit_size());
1963 for (uint64_t i = 0; i < bit_data_size(); ++i)
1964 m_data[i] |= v.m_data[i];
1965 return *this;
1966}
1967
1968template <uint8_t t_width>
1970{
1971 assert(bit_size() == v.bit_size());
1972 for (uint64_t i = 0; i < bit_data_size(); ++i)
1973 m_data[i] ^= v.m_data[i];
1974 return *this;
1975}
1976
1977template <uint8_t t_width>
1979{
1980 size_type written_bytes = 0;
1981 uint64_t * p = m_data;
1982 size_type idx = 0;
1983 while (idx + conf::SDSL_BLOCK_SIZE < bit_data_size())
1984 {
1985 out.write((char *)p, conf::SDSL_BLOCK_SIZE * sizeof(uint64_t));
1986 written_bytes += conf::SDSL_BLOCK_SIZE * sizeof(uint64_t);
1988 idx += conf::SDSL_BLOCK_SIZE;
1989 }
1990 out.write((char *)p, (bit_data_size() - idx) * sizeof(uint64_t));
1991 written_bytes += (bit_data_size() - idx) * sizeof(uint64_t);
1992 return written_bytes;
1993}
1994
1995template <uint8_t t_width>
1997int_vector<t_width>::serialize(std::ostream & out, structure_tree_node * v, std::string name) const
1998{
1999 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
2000 size_type written_bytes = int_vector<t_width>::write_header(m_size, m_width, out);
2001 written_bytes += write_data(out);
2002 structure_tree::add_size(child, written_bytes);
2003 return written_bytes;
2004}
2005
2006template <uint8_t t_width>
2007void int_vector<t_width>::load(std::istream & in)
2008{
2011
2012 bit_resize(size);
2013 uint64_t * p = m_data;
2014 size_type idx = 0;
2015 while (idx + conf::SDSL_BLOCK_SIZE < bit_data_size())
2016 {
2017 in.read((char *)p, conf::SDSL_BLOCK_SIZE * sizeof(uint64_t));
2019 idx += conf::SDSL_BLOCK_SIZE;
2020 }
2021 in.read((char *)p, (bit_data_size() - idx) * sizeof(uint64_t));
2022}
2023
2024template <uint8_t t_width>
2025template <typename archive_t>
2026inline typename std::enable_if<
2028 void>::type
2030{
2031 ar(CEREAL_NVP(cereal::make_size_tag(static_cast<int_width_type>(m_width))));
2032 ar(CEREAL_NVP(growth_factor));
2033 ar(CEREAL_NVP(cereal::make_size_tag(static_cast<size_type>(m_size))));
2034 ar(cereal::make_nvp("data", cereal::binary_data(m_data, bit_data_size() * sizeof(uint64_t))));
2035}
2036
2037template <uint8_t t_width>
2038template <typename archive_t>
2039inline typename std::enable_if<
2041 void>::type
2043{
2044 ar(CEREAL_NVP(m_width));
2045 ar(CEREAL_NVP(growth_factor));
2046 ar(CEREAL_NVP(m_size));
2047 for (value_type const & v : *this)
2048 ar(v);
2049}
2050
2051template <uint8_t t_width>
2052template <typename archive_t>
2053inline typename std::enable_if<
2055 void>::type
2057{
2058 ar(CEREAL_NVP(cereal::make_size_tag(m_width)));
2059 ar(CEREAL_NVP(growth_factor));
2060 ar(CEREAL_NVP(cereal::make_size_tag(m_size)));
2061 resize(size());
2062 ar(cereal::make_nvp("data", cereal::binary_data(m_data, bit_data_size() * sizeof(uint64_t))));
2063}
2064
2065template <uint8_t t_width>
2066template <typename archive_t>
2067inline typename std::enable_if<
2069 void>::type
2071{
2072 ar(CEREAL_NVP(m_width));
2073 width(width());
2074 ar(CEREAL_NVP(growth_factor));
2075 ar(CEREAL_NVP(m_size));
2076 resize(size());
2077
2078 for (size_t i = 0; i < size(); ++i)
2079 {
2080 value_type tmp;
2081 ar(tmp);
2082 operator[](i) = tmp;
2083 }
2084}
2085
2086inline typename int_vector_trait<64>::iterator
2088{
2089 return v->data();
2090}
2091inline typename int_vector_trait<64>::iterator
2093{
2094 return v->data() + v->size();
2095}
2098{
2099 return v->data();
2100}
2103{
2104 return v->data() + v->size();
2105}
2106
2107inline typename int_vector_trait<32>::iterator
2109{
2110 return (uint32_t *)v->data();
2111}
2112inline typename int_vector_trait<32>::iterator
2114{
2115 return ((uint32_t *)v->data()) + v->size();
2116}
2119{
2120 return (uint32_t *)v->data();
2121}
2124{
2125 return ((uint32_t *)v->data()) + v->size();
2126}
2127
2128inline typename int_vector_trait<16>::iterator
2130{
2131 return (uint16_t *)v->data();
2132}
2133inline typename int_vector_trait<16>::iterator
2135{
2136 return ((uint16_t *)v->data()) + v->size();
2137}
2140{
2141 return (uint16_t *)v->data();
2142}
2145{
2146 return ((uint16_t *)v->data()) + v->size();
2147}
2148
2149inline typename int_vector_trait<8>::iterator
2151{
2152 return (uint8_t *)v->data();
2153}
2154inline typename int_vector_trait<8>::iterator
2156{
2157 return ((uint8_t *)v->data()) + v->size();
2158}
2161{
2162 return (uint8_t *)v->data();
2163}
2166{
2167 return ((uint8_t *)v->data()) + v->size();
2168}
2169
2170} // end namespace sdsl
2171
2172// clang-format off
2173// Cyclic includes start
2176// Cyclic includes end
2177// clang-format on
2178
2179#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
A class to encode and decode between comma code and binary code.
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
const_iterator & operator-=(difference_type i)
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>(int_vector_const_iterator const &it) const noexcept
int_vector_const_iterator const_iterator
int_vector_const_iterator(int_vector_iterator< t_int_vector > const &it)
bool operator<=(int_vector_const_iterator const &it) const noexcept
const_iterator operator+(difference_type i) const
const_reference operator[](difference_type i) const
const t_int_vector::value_type * pointer
int_vector_const_iterator(int_vector_const_iterator const &)=default
const_iterator & operator+=(difference_type i)
const_reference operator*() const
const_iterator & operator--()
Prefix decrement of the Iterator.
bool operator!=(int_vector_const_iterator const &it) const noexcept
t_int_vector::value_type const_reference
bool operator==(int_vector_const_iterator const &it) const noexcept
int_vector_const_iterator & operator=(int_vector_const_iterator const &)=default
bool operator<(int_vector_const_iterator const &it) const noexcept
bool operator>=(int_vector_const_iterator const &it) const noexcept
int_vector_const_iterator(t_int_vector const *v=nullptr, size_type idx=0)
const_iterator operator++(int)
Postfix increment of the Iterator.
friend int_vector_const_iterator< X >::difference_type operator-(int_vector_const_iterator< X > const &x, int_vector_const_iterator< X > const &y)
const_iterator & operator++()
Prefix increment of the Iterator.
int_vector_iterator_base(t_int_vector const *v=nullptr, size_type idx=0)
int_vector_iterator_base(uint8_t offset, uint8_t len)
typename t_int_vector::difference_type difference_type
typename t_int_vector::value_type value_type
std::random_access_iterator_tag iterator_category
int_vector_iterator iterator
iterator & operator++()
Prefix increment of the Iterator.
reference operator*() const
iterator & operator-=(difference_type i)
bool operator==(int_vector_iterator const &it) const noexcept
bool operator>(int_vector_iterator const &it) const noexcept
bool operator<=(int_vector_iterator const &it) const noexcept
bool operator<(int_vector_iterator const &it) const noexcept
difference_type operator-(int_vector_iterator const &it) const noexcept
bool operator>=(int_vector_iterator const &it) const noexcept
bool operator!=(int_vector_iterator const &it) const noexcept
iterator operator++(int)
Postfix increment of the Iterator.
reference operator[](difference_type i) const
t_int_vector::difference_type difference_type
t_int_vector::size_type size_type
iterator & operator--()
Prefix decrement of the Iterator.
iterator operator+(difference_type i) const
iterator & operator+=(difference_type i)
iterator operator-(difference_type i) const
iterator & operator=(int_vector_iterator< t_int_vector > const &it)
iterator operator--(int)
Postfix decrement of the Iterator.
int_vector_iterator(t_int_vector *v=nullptr, size_type idx=0)
int_vector_iterator(int_vector_iterator< t_int_vector > const &it)
int_vector_reference< t_int_vector > reference
int_vector_reference & operator=(bool x) noexcept
Assignment operator for the proxy class.
int_vector_reference()=delete
Default constructor explicitly deleted.
bool operator<(int_vector_reference const &x) const noexcept
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==(int_vector_reference const &x) const noexcept
int_vector_reference & operator=(int_vector_reference &&x) noexcept
int_vector_reference & operator=(int_vector_reference const &x) noexcept
A proxy class that acts as a reference to an integer of length len bits in a int_vector.
bool operator==(int_vector_reference const &x) const noexcept
t_int_vector::value_type value_type
bool operator<(int_vector_reference const &x) const noexcept
int_vector_reference & operator=(int_vector_reference &&x) noexcept
int_vector_reference & operator+=(const value_type x) noexcept
Add assign from the proxy object.
int_vector_reference & operator=(value_type x) noexcept
Assignment operator for the proxy class.
int_vector_reference & operator-=(const value_type x) noexcept
Subtract assign from the proxy object.
value_type operator++(int) noexcept
Postfix increment of the proxy object.
int_vector_reference & operator--() noexcept
Prefix decrement of the proxy object.
int_vector_reference()=delete
Default constructor explicitly deleted.
value_type operator--(int) noexcept
Postfix decrement of the proxy object.
int_vector_reference & operator++() noexcept
Prefix increment of the proxy object.
constexpr int_vector_reference(int_vector_reference &&) noexcept=default
constexpr int_vector_reference(int_vector_reference const &) noexcept=default
Copy and move explicitly defaulted.
int_vector_reference & operator=(int_vector_reference const &x) noexcept
A generic vector class for integers of width .
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
iterator end() noexcept
Iterator that points to the element after the last element of int_vector.
void flip()
Flip all bits of bit_vector.
bool operator<=(int_vector const &v) const noexcept
Less or equal operator.
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.
bool operator>(int_vector const &v) const noexcept
Greater operator for two int_vectors.
const raw_wrapper raw
uint64_t * data() noexcept
Pointer to the raw data of the int_vector.
bool operator!=(int_vector< t_width2 > const &v) const noexcept
Inequality operator for two int_vectors.
rank_support_v< 1, 1 > rank_1_type
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.
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.
value_type const * const_pointer
void assign(size_type size, value_type default_value)
Assign. Resize int_vector to size and fill elements with default_value.
void reserve(size_type capacity)
Reserve storage. If the new capacity is smaller than the current, this method does nothing.
int_vector_trait< t_width >::iterator iterator
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.
int_vec_category_trait< t_width >::type index_category
const_iterator end() const noexcept
Const iterator that points to the element after the last element of int_vector.
const_reference back() const noexcept
Returns last element.
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.
void swap(int_vector &v) noexcept
Swap method for int_vector.
rank_support_v< 0, 1 > rank_0_type
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
bool operator<(int_vector const &v) const noexcept
Less operator for two int_vectors.
ptrdiff_t difference_type
bool operator==(int_vector< t_width2 > const &v) const noexcept
Equality operator for two int_vectors.
const_reference operator[](size_type const &i) const noexcept
const version of [] operator
select_support_mcl< 0, 1 > select_0_type
void width(uint8_t new_width) noexcept
Sets the width of the integers which are accessed via the [] operator, if t_width equals 0.
int_vector_reference< int_vector > * pointer
int_vector_trait< t_width >::const_reference const_reference
iterator erase(const_iterator it)
Remove element that iterator is pointing to.
int_vector_trait< t_width >::int_width_type int_width_type
size_type write_data(std::ostream &out) const
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.
size_type bit_size() const noexcept
The number of bits in the int_vector.
iterator emplace(const_iterator it, Args &&... args)
Insert an element constructed with std::forward<Args>(args) before the element that the iterator is p...
size_type bit_capacity() const noexcept
Returns the size of the occupied bits of the int_vector.
void clear() noexcept
Clearing the int_vector. Allocated memory will not be released.
reference operator[](size_type const &i) noexcept
non const version of [] operator
int_vector & operator^=(int_vector const &v)
bitwise-xor-update operator
select_support_mcl< 1, 1 > select_1_type
const_iterator begin() const noexcept
Const iterator that points to the first element of the int_vector.
reference back() noexcept
Returns last element.
int_vector & operator=(int_vector &&v)
Move assignment operator.
int_vector_trait< t_width >::const_iterator const_iterator
std::enable_if< std::is_base_of< std::input_iterator_tag, typenamestd::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.
const_reference at(size_type const &i) const
const version of at() function
void load(std::istream &in)
Load the int_vector for a stream.
bool operator>=(int_vector const &v) const noexcept
Greater of equal operator.
const_iterator cbegin() const noexcept
Const iterator that points to the first element of the int_vector.
int_vector & operator=(int_vector const &v)
Assignment operator.
void shrink_to_fit()
Free unused allocated memory.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
int_vector_trait< t_width >::reference reference
void emplace_back(Args &&... args)
Insert an element constructed with std::forward<Args>(args) at the end.
void assign(std::initializer_list< value_type > il)
Assign. Resize int_vector and initialize with initializer_list.
size_type size() const noexcept
The number of elements in the int_vector.
int_vector & operator&=(int_vector const &v)
bitwise-and-update operator
static constexpr uint8_t fixed_int_width
iterator insert(const_iterator it, value_type value)
Insert an element before the element that the iterator is pointing to.
void push_back(value_type value)
Insert element at the end.
void assign(input_iterator_t first, input_iterator_t last)
Assign. Resize int_vector and initialize by copying from an iterator range.
float growth_factor
Growth factor for amortized constant time operations.
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.
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.
const_iterator cend() const noexcept
Const iterator that points to the element after the last element of int_vector.
int_vector(size_type size=0)
Constructor to fix possible comparison with integeres issue.
int_vector_trait< t_width >::value_type value_type
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.
reference at(size_type const &i)
non const version of at() function
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
int_vector & operator|=(int_vector const &v)
bitwise-or-update equal operator
reference front() noexcept
Returns first element.
int_vector(int_vector &&v)
Move constructor.
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.
static size_type max_size() noexcept
Maximum size of the int_vector.
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.
int_vector(std::initializer_list< value_type > il)
Constructor for initializer_list.
iterator erase(const_iterator first, const_iterator last)
Remove elements in given iterator range.
const_reference front() const noexcept
Returns first element.
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.
bool operator==(int_vector< t_width > const &v) const noexcept
Equality operator for two int_vectors.
int_vector(int_vector const &v)
Copy constructor.
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.
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
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.
A class supporting constant time select queries.
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
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:61
void make_size_tag(t const &)
Definition cereal.hpp:65
t1 binary_data(t1 const &, t2 const &)
Definition cereal.hpp:69
const uint64_t SDSL_BLOCK_SIZE
Definition config.hpp:32
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition util.hpp:597
Namespace for the succinct data structure library.
std::ostream & operator<<(std::ostream &os, bp_interval< t_int > const &interval)
int_vector_iterator< t_int_vector > operator+(typename int_vector_iterator< t_int_vector >::difference_type n, int_vector_iterator< t_int_vector > const &it)
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
void read_member(T &t, std::istream &in)
Definition io.hpp:119
uint64_t std_size_type_for_int_vector
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
int_vector_const_iterator< t_int_vector >::difference_type operator-(int_vector_const_iterator< t_int_vector > const &x, int_vector_const_iterator< t_int_vector > const &y)
uint64_t int_vector_size_type
Definition config.hpp:47
int_vector ::size_type size(range_type const &r)
Size of a range.
Contains declarations and definitions of data structure concepts.
static 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:724
static constexpr uint64_t read_int(uint64_t const *word, uint8_t offset=0, const uint8_t len=64)
Reads a value from a bit position in an array.
Definition bits.hpp:777
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition bits.hpp:194
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
raw_wrapper(int_vector const &_vec)
int_vector< 16 > int_vector_type
static iterator begin(int_vector_type *v) noexcept
static const_iterator end(int_vector_type const *v) noexcept
static iterator end(int_vector_type *v) noexcept
uint16_t const * const_iterator
static void set_width(uint8_t, int_width_type) noexcept
static const_iterator begin(int_vector_type const *v) noexcept
static iterator begin(int_vector_type *v) noexcept
static iterator end(int_vector_type *v) noexcept
static const_iterator begin(int_vector_type const *v) noexcept
static void set_width(uint8_t, int_width_type) noexcept
static const_iterator end(int_vector_type const *v) noexcept
uint32_t const * const_iterator
int_vector< 32 > int_vector_type
static const_iterator end(int_vector_type const *v) noexcept
static iterator begin(int_vector_type *v) noexcept
static iterator end(int_vector_type *v) noexcept
uint64_t const * const_iterator
static const_iterator begin(int_vector_type const *v) noexcept
int_vector< 64 > int_vector_type
static void set_width(uint8_t, int_width_type) noexcept
static const_iterator begin(int_vector_type const *v) noexcept
int_vector< 8 > int_vector_type
static iterator begin(int_vector_type *v) noexcept
static void set_width(uint8_t, int_width_type) noexcept
static const_iterator end(int_vector_type const *v) noexcept
static iterator end(int_vector_type *v) noexcept
uint8_t const * const_iterator
static const_iterator begin(int_vector_type const *v) noexcept
int_vector_const_iterator< int_vector_type > const_iterator
static const_iterator end(int_vector_type const *v) noexcept
int_vector< t_width > int_vector_type
static void set_width(uint8_t new_width, int_width_type &width) noexcept
static iterator begin(int_vector_type *v) noexcept
int_vector_reference< int_vector_type > reference
int_vector_iterator< int_vector_type > iterator
static iterator end(int_vector_type *v) noexcept
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.