SDSL 3.0.1
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 <cassert>
12#include <cinttypes>
13#include <cstddef>
14#include <cstdlib>
15#include <cstring> // for memcpy
16#include <ctime> // for rand initialization
17#include <initializer_list>
18#include <ios>
19#include <iosfwd> // forward declaration of ostream
20#include <iostream> // for cerr
21#include <istream>
22#include <iterator>
23#include <ostream>
24#include <stdexcept> // for exceptions
25#include <string>
26#include <type_traits>
27#include <typeinfo>
28#include <vector>
29
30#include <sdsl/bits.hpp>
31#include <sdsl/config.hpp>
32#include <sdsl/io.hpp>
34#include <sdsl/ram_fs.hpp>
35#include <sdsl/sfstream.hpp>
37#include <sdsl/uintx_t.hpp>
38#include <sdsl/util.hpp>
39
41namespace sdsl
42{
43
45
46template <uint8_t t_width = 0>
47class int_vector;
48
49template <class int_vector_type>
50class mm_item;
51
54
55template <class t_int_vector>
57
58template <class t_int_vector>
60
61template <class t_int_vector>
63
64template <class t_int_vector>
66
67template <uint8_t t_width, std::ios_base::openmode t_mode>
69
70template <uint8_t b, uint8_t t_patter_len> // forward declaration
71class rank_support_v;
72
73class rank_support;
74
75class select_support;
76
77template <uint8_t t_bit_pattern, uint8_t t_pattern_len>
79
80namespace coder
81{
82template <typename T>
83class fibonacci;
84template <typename T>
85class elias_delta;
86template <typename T>
87class elias_gamma;
88template <uint8_t t_width>
89class comma;
90} // namespace coder
91
92template <uint8_t t_width>
94{
95 typedef iv_tag type;
96};
97
98template <>
100{
101 typedef bv_tag type;
102};
103
104template <uint8_t t_width>
106{
107 typedef uint64_t value_type;
110 typedef uint64_t const_reference;
111 typedef uint8_t int_width_type;
114
115 static iterator begin(int_vector_type * v) noexcept { return iterator(v, 0); }
116 static iterator end(int_vector_type * v) noexcept { return iterator(v, v->size() * v->width()); }
117 static const_iterator begin(const int_vector_type * v) noexcept { return const_iterator(v, 0); }
118 static const_iterator end(const int_vector_type * v) noexcept { return const_iterator(v, v->size() * v->width()); }
119
120 static void set_width(uint8_t new_width, int_width_type & width) noexcept
121 {
122 if constexpr (t_width == 0) width = new_width ? std::min(new_width, uint8_t{ 64u }) : 64u;
123 }
124};
125
126template <>
128{
129 typedef uint64_t value_type;
131 typedef uint64_t & reference;
132 typedef uint64_t const_reference;
133 typedef uint8_t int_width_type;
134 typedef uint64_t * iterator;
135 typedef const uint64_t * const_iterator;
136
137 static iterator begin(int_vector_type * v) noexcept;
138 static iterator end(int_vector_type * v) noexcept;
139 static const_iterator begin(const int_vector_type * v) noexcept;
140 static const_iterator end(const int_vector_type * v) noexcept;
141
142 static void set_width(uint8_t, int_width_type) noexcept {}
143};
144
145template <>
147{
148 typedef uint32_t value_type;
150 typedef uint32_t & reference;
151 typedef uint32_t const_reference;
152 typedef uint8_t int_width_type;
153 typedef uint32_t * iterator;
154 typedef const uint32_t * const_iterator;
155
156 static iterator begin(int_vector_type * v) noexcept;
157 static iterator end(int_vector_type * v) noexcept;
158 static const_iterator begin(const int_vector_type * v) noexcept;
159 static const_iterator end(const int_vector_type * v) noexcept;
160
161 static void set_width(uint8_t, int_width_type) noexcept {}
162};
163
164template <>
166{
167 typedef uint16_t value_type;
169 typedef uint16_t & reference;
170 typedef uint16_t const_reference;
171 typedef uint8_t int_width_type;
172 typedef uint16_t * iterator;
173 typedef const uint16_t * const_iterator;
174
175 static iterator begin(int_vector_type * v) noexcept;
176 static iterator end(int_vector_type * v) noexcept;
177 static const_iterator begin(const int_vector_type * v) noexcept;
178 static const_iterator end(const int_vector_type * v) noexcept;
179
180 static void set_width(uint8_t, int_width_type) noexcept {}
181};
182
183template <>
185{
186 typedef uint8_t value_type;
188 typedef uint8_t & reference;
189 typedef uint8_t const_reference;
190 typedef uint8_t int_width_type;
191 typedef uint8_t * iterator;
192 typedef const uint8_t * const_iterator;
193
194 static iterator begin(int_vector_type * v) noexcept;
195 static iterator end(int_vector_type * v) noexcept;
196 static const_iterator begin(const int_vector_type * v) noexcept;
197 static const_iterator end(const int_vector_type * v) noexcept;
198
199 static void set_width(uint8_t, int_width_type) noexcept {}
200};
201
203
214template <uint8_t t_width>
216{
217 private:
218 static_assert(t_width <= 64, "int_vector: width of must be at most 64bits.");
219
220 public:
227 typedef const value_type * const_pointer;
228 typedef ptrdiff_t difference_type;
236
237 friend struct int_vector_trait<t_width>;
239 friend class int_vector_iterator<int_vector>;
241 template <uint8_t, std::ios_base::openmode>
242 friend class int_vector_mapper;
243 template <typename T>
244 friend class coder::elias_delta;
245 template <typename T>
246 friend class coder::elias_gamma;
247 template <typename T>
248 friend class coder::fibonacci;
249 template <uint8_t>
250 friend class coder::comma;
251 friend class memory_manager;
252 static constexpr uint8_t fixed_int_width = t_width;
253 float growth_factor = 1.5;
254 // see the explanation in the documentation of FBVector on different growth factors
255 // https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#memory-handling
256
257 private:
258 size_type m_size;
259 size_type m_capacity;
260 uint64_t * m_data;
261 int_width_type m_width;
262
263 // Hidden, since number of bits (size) does not go well together with int value.
264 void bit_resize(const size_type size, const value_type value);
265
266 void amortized_resize(const size_type size)
267 {
268 assert(growth_factor > 1.0);
269 if constexpr (t_width != 0)
270 {
271 size_type const bit_size{ size * t_width };
272 if (bit_size > m_capacity || m_data == nullptr)
273 {
274 // start with 64 bit if vector has no capacity
275 size_type new_capacity = std::max<size_type>(m_capacity, 64u);
276 // find smallest x s.t. m_capacity * 1.5 ** x >= size
277 while (new_capacity < bit_size) new_capacity *= growth_factor;
278 memory_manager::resize(*this, new_capacity);
279 }
280 m_size = bit_size;
281 }
282 else
283 {
284 size_type const bit_size{ size * m_width };
285 if (bit_size > m_capacity || m_data == nullptr)
286 {
287 // start with 64 bit if vector has no capacity
288 size_type new_capacity = std::max<size_type>(m_capacity, 64u);
289 // find smallest x s.t. m_capacity * 1.5 ** x >= size
290 while (new_capacity < bit_size) new_capacity *= growth_factor;
291 memory_manager::resize(*this, new_capacity);
292 }
293 m_size = bit_size;
294 }
295 }
296
297 // The number of 64-bit words used by the int_vector.
298 size_type bit_data_size() const { return (m_size + 63) >> 6; }
299
300 public:
302
308 int_vector(size_type size, value_type default_value, uint8_t int_width = t_width);
309
312 : int_vector(size, static_cast<value_type>(0), t_width)
313 {}
315 int_vector(std::initializer_list<value_type> il)
316 : int_vector(0, 0)
317 {
318 assign(il);
319 }
320
322
325 template <typename input_iterator_t>
326 int_vector(typename std::enable_if<std::is_base_of<std::input_iterator_tag,
327 typename std::iterator_traits<input_iterator_t>::iterator_category>::
328 value,
329 input_iterator_t>::type first,
330 input_iterator_t last)
331 : int_vector(0, 0)
332 {
333 assign(first, last);
334 }
335
337
339 void clear() noexcept { m_size = 0; }
340
342
345 {
346 iterator it_nonconst = begin() + (it - cbegin());
347 std::copy(it_nonconst + 1, end(), it_nonconst);
348 resize(size() - 1);
349 return it_nonconst;
350 }
351
353
357 {
358 iterator first_nonconst = begin() + (first - cbegin());
359 iterator last_nonconst = begin() + (last - cbegin());
360 std::copy(last_nonconst, end(), first_nonconst);
361 resize(size() - (last - first));
362 return first_nonconst;
363 }
364
366
369 template <class... Args>
370 iterator emplace(const_iterator it, Args &&... args)
371 {
372 return insert(it, 1, value_type(std::forward<Args>(args)...));
373 }
374
376
379 iterator insert(const_iterator it, value_type value) { return insert(it, 1, value); }
380
382
387 {
388 size_type pos = it - cbegin();
389 amortized_resize(size() + n);
390 iterator it_new = begin() + pos;
391 std::copy_backward(it_new, end() - n, end());
392 std::fill_n(it_new, n, value);
393 return it_new;
394 }
395
397
400 iterator insert(const_iterator it, std::initializer_list<value_type> il)
401 {
402 return insert(it, il.begin(), il.end());
403 }
404
406
410 template <typename input_iterator_t>
411 typename std::enable_if<std::is_base_of<std::input_iterator_tag,
412 typename std::iterator_traits<input_iterator_t>::iterator_category>::value,
413 iterator>::type
414 insert(const_iterator it, input_iterator_t first, input_iterator_t last)
415 {
416 size_type pos = it - cbegin();
417 amortized_resize(size() + last - first);
418 iterator it_new = begin() + pos;
419 std::copy_backward(it_new, end() - (last - first), end());
420 std::copy(first, last, it_new);
421 return it_new;
422 }
423
425 reference front() noexcept { return *begin(); }
426
428 const_reference front() const noexcept { return *cbegin(); }
429
431 reference back() noexcept { return *(end() - 1); }
432
434 const_reference back() const noexcept { return *(cend() - 1); }
435
437
439 template <class... Args>
440 void emplace_back(Args &&... args)
441 {
442 push_back(value_type(std::forward<Args>(args)...));
443 }
444
446
449 {
450 amortized_resize(size() + 1);
451 *(end() - 1) = value;
452 }
453
455 void pop_back() { resize(size() - 1); }
456
459
462
465
467
470 void assign(size_type size, value_type default_value)
471 {
472 bit_resize(size * m_width);
473 util::set_to_value(*this, default_value); // new initialization
474 }
475
477
479 void assign(std::initializer_list<value_type> il)
480 {
481 bit_resize(il.size() * m_width);
482 size_type idx = 0;
483 for (auto x : il) { (*this)[idx++] = x; }
484 }
485
487
490 template <typename input_iterator_t>
491 void assign(input_iterator_t first, input_iterator_t last)
492 {
493 assert(first <= last);
494 bit_resize((last - first) * m_width);
495 size_type idx = 0;
496 while (first < last) { (*this)[idx++] = *(first++); }
497 }
498
500 bool empty() const noexcept { return 0 == m_size; }
501
503 void swap(int_vector & v) noexcept { std::swap(v, *this); }
504
506 void shrink_to_fit() { memory_manager::resize(*this, m_size); }
507
509
512 {
513 if (capacity * m_width > m_capacity || m_data == nullptr) { memory_manager::resize(*this, capacity * m_width); }
514 }
515
518
521 void resize(const size_type size) { resize(size, 0); }
522
524
527 void resize(const size_type size, const value_type value) { bit_resize(size * m_width, value); }
528
530
533
535
537 inline size_type size() const noexcept;
538
540
542 static size_type max_size() noexcept { return ((size_type)1) << (sizeof(size_type) * 8 - 6); }
543
545
547 size_type bit_size() const noexcept { return m_size; }
548
550
554 inline size_type capacity() const noexcept;
555
557
561 size_type bit_capacity() const noexcept { return m_capacity; }
562
564
566 const uint64_t * data() const noexcept { return m_data; }
567
569
571 uint64_t * data() noexcept { return m_data; }
572
574
579 value_type get_int(size_type idx, const uint8_t len = 64) const;
580
582
589 void set_int(size_type idx, value_type x, const uint8_t len = 64);
590
592
595 uint8_t width() const noexcept { return m_width; }
596
598
602 void width(uint8_t new_width) noexcept { int_vector_trait<t_width>::set_width(new_width, m_width); }
603
604 // Write data (without header) to a stream.
605 size_type write_data(std::ostream & out) const;
606
608
611 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
612
614 void load(std::istream & in);
615
616 /* For cereal we need to define different versions of the load and save function depending on whether we want
617 * binary data or text (XML/JSON) data.
618 * See https://github.com/USCiLab/cereal/blob/master/include/cereal/types/vector.hpp for an example.
619 */
620
622 template <typename archive_t>
623 inline typename std::enable_if<!cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
624 archive_t>::value,
625 void>::type
626 CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
627
629 template <typename archive_t>
630 inline typename std::enable_if<cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
631 archive_t>::value,
632 void>::type
633 CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
634
636 template <typename archive_t>
637 inline typename std::enable_if<!cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
638 archive_t>::value,
639 void>::type
641
643 template <typename archive_t>
644 inline typename std::enable_if<cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
645 archive_t>::value,
646 void>::type
648
650
653 inline reference operator[](const size_type & i) noexcept;
654
656
659 inline const_reference operator[](const size_type & i) const noexcept;
660
662
665 reference at(const size_type & i) { return (*this)[i]; }
666
668
671 const_reference at(const size_type & i) const { return (*this)[i]; }
672
674
677
680
682
686 bool operator==(const int_vector<t_width> & v) const noexcept
687 {
688 if (bit_size() != v.bit_size()) return false;
689 if (empty()) return true;
690 const uint64_t * data1 = v.data();
691 const uint64_t * data2 = data();
692 for (size_type i = 0; i < bit_data_size() - 1; ++i)
693 {
694 if (*(data1++) != *(data2++)) return false;
695 }
696 uint8_t l = 64 - ((bit_data_size() << 6) - m_size);
697 return ((*data1) & bits::lo_set[l]) == ((*data2) & bits::lo_set[l]);
698 }
699
701
707 template <class container>
708 friend bool operator==(const int_vector<t_width> & lhs, const container & rhs) noexcept
709 {
710 return std::equal(lhs.begin(), lhs.end(), rhs.begin());
711 }
712
714
720 template <uint8_t t_width2>
721 bool operator!=(const int_vector<t_width2> & v) const noexcept
722 {
723 return !(*this == v);
724 }
725
727
732 bool operator<(const int_vector & v) const noexcept;
733
735
739 bool operator>(const int_vector & v) const noexcept;
740
742 bool operator<=(const int_vector & v) const noexcept;
743
745 bool operator>=(const int_vector & v) const noexcept;
746
749
752
755
757
760
762
764 iterator end() noexcept { return int_vector_trait<t_width>::end(this); }
765
767 const_iterator begin() const noexcept { return int_vector_trait<t_width>::begin(this); }
768
770 const_iterator end() const noexcept { return int_vector_trait<t_width>::end(this); }
771
773 const_iterator cbegin() const noexcept { return int_vector_trait<t_width>::begin(this); }
774
776 const_iterator cend() const noexcept { return int_vector_trait<t_width>::end(this); }
777
779 void flip()
780 {
781 static_assert(1 == t_width, "int_vector: flip() is available only for bit_vector.");
782 if (!empty())
783 {
784 for (uint64_t i = 0; i < bit_data_size(); ++i) { m_data[i] = ~m_data[i]; }
785 }
786 }
787
789 static size_t read_header(int_vector_size_type & size, int_width_type & int_width, std::istream & in)
790 {
791 uint64_t width_and_size = 0;
792 read_member(width_and_size, in);
793 size = width_and_size & bits::lo_set[56];
794 uint8_t read_int_width = (uint8_t)(width_and_size >> 56);
795 if (t_width == 0) { int_width = read_int_width; }
796 if (t_width > 0 and t_width != read_int_width)
797 {
798 std::cerr << "Warning: Width of int_vector<" << (size_t)t_width << ">";
799 std::cerr << " was specified as " << (size_type)read_int_width << std::endl;
800 std::cerr << "Length is " << size << " bits" << std::endl;
801 }
802 return sizeof(width_and_size);
803 }
804
806 static uint64_t write_header(uint64_t size, uint8_t int_width, std::ostream & out)
807 {
808 if (t_width > 0)
809 {
810 if (t_width != int_width)
811 {
812 std::cout << "Warning: writing width=" << (size_type)int_width << " != fixed " << (size_type)t_width
813 << std::endl;
814 }
815 }
816 uint64_t width_and_size = (((uint64_t)int_width) << 56) | size;
817 return write_member(width_and_size, out);
818 }
819
821 {
823 raw_wrapper() = delete;
825 : vec(_vec)
826 {}
827
828 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
829 {
830 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
831 auto written_bytes = vec.write_data(out);
832 structure_tree::add_size(child, written_bytes);
833 return written_bytes;
834 }
835 };
836
838};
839
841
843template <class t_int_vector>
845{
846 public:
847 typedef typename t_int_vector::value_type value_type;
848
849 private:
850 typename t_int_vector::value_type * const m_word;
851 const uint8_t m_offset;
852 const uint8_t m_len;
853 public:
857 constexpr int_vector_reference(int_vector_reference const &) noexcept = default;
858 constexpr int_vector_reference(int_vector_reference &&) noexcept = default;
859
861
865 int_vector_reference(value_type * word, uint8_t offset, uint8_t len) noexcept
866 : m_word(word)
867 , m_offset(offset)
868 , m_len(len){};
869
871
879 {
880 bits::write_int(m_word, x, m_offset, m_len);
881 return *this;
882 };
883
884 int_vector_reference & operator=(const int_vector_reference & x) noexcept { return *this = value_type(x); };
885
886 int_vector_reference & operator=(int_vector_reference && x) noexcept { return *this = value_type(std::move(x)); };
887
889 operator value_type() const noexcept { return bits::read_int(m_word, m_offset, m_len); }
890
893 {
894 value_type x = bits::read_int(m_word, m_offset, m_len);
895 bits::write_int(m_word, x + 1, m_offset, m_len);
896 return *this;
897 }
898
900 value_type operator++(int) noexcept
901 {
902 value_type val = (typename t_int_vector::value_type) * this;
903 ++(*this);
904 return val;
905 }
906
909 {
910 value_type x = bits::read_int(m_word, m_offset, m_len);
911 bits::write_int(m_word, x - 1, m_offset, m_len);
912 return *this;
913 }
914
916 value_type operator--(int) noexcept
917 {
918 value_type val = (value_type) * this;
919 --(*this);
920 return val;
921 }
922
925 {
926 value_type w = bits::read_int(m_word, m_offset, m_len);
927 bits::write_int(m_word, w + x, m_offset, m_len);
928 return *this;
929 }
930
933 {
934 value_type w = bits::read_int(m_word, m_offset, m_len);
935 bits::write_int(m_word, w - x, m_offset, m_len);
936 return *this;
937 }
938
939 bool operator==(const int_vector_reference & x) const noexcept { return value_type(*this) == value_type(x); }
940
941 bool operator<(const int_vector_reference & x) const noexcept { return value_type(*this) < value_type(x); }
942};
943
944// For C++11
945template <class t_int_vector>
947{
948 // TODO: more efficient solution?
950 x = y;
951 y = tmp;
952}
953
954// For C++11
955template <class t_int_vector>
958{
959 // TODO: more efficient solution?
961 x = y;
962 y = tmp;
963}
964
965// For C++11
966template <class t_int_vector>
969{
970 // TODO: more efficient solution?
972 x = y;
973 y = tmp;
974}
975
976// specialization for int_vector_reference for int_vector == bit_vector
977// special thanks to Timo Beller, who pointed out that the specialization is missing
978// Same implementation as in stl_bvector.h.
979template <>
981{
982 public:
983 typedef bool value_type;
984
985 private:
986 uint64_t * const m_word;
987 uint64_t m_mask;
988
989 public:
993 constexpr int_vector_reference(int_vector_reference const &) noexcept = default;
994 constexpr int_vector_reference(int_vector_reference &&) noexcept = default;
995
997
1000 int_vector_reference(uint64_t * word, uint8_t offset, uint8_t) noexcept
1001 : m_word(word)
1002 , m_mask(1ULL << offset){};
1003
1006 {
1007 if (x)
1008 *m_word |= m_mask;
1009 else
1010 *m_word &= ~m_mask;
1011 return *this;
1012 };
1013
1014 int_vector_reference & operator=(const int_vector_reference & x) noexcept { return *this = bool(x); };
1015 int_vector_reference & operator=(int_vector_reference && x) noexcept { return *this = bool(x); };
1016
1018 operator bool() const noexcept { return !!(*m_word & m_mask); }
1019
1020 bool operator==(const int_vector_reference & x) const noexcept { return bool(*this) == bool(x); }
1021
1022 bool operator<(const int_vector_reference & x) const noexcept { return !bool(*this) && bool(x); }
1023};
1024
1025// For C++11
1026template <>
1028{
1029 // TODO: more efficient solution?
1030 bool tmp = x;
1031 x = y;
1032 y = tmp;
1033}
1034
1035// For C++11
1036template <>
1037inline void swap(bool & x, int_vector_reference<bit_vector> y) noexcept
1038{
1039 // TODO: more efficient solution?
1040 bool tmp = x;
1041 x = y;
1042 y = tmp;
1043}
1044
1045// For C++11
1046template <>
1047inline void swap(int_vector_reference<bit_vector> x, bool & y) noexcept
1048{
1049 // TODO: more efficient solution?
1050 bool tmp = x;
1051 x = y;
1052 y = tmp;
1053}
1054
1055template <class t_int_vector>
1057{
1058 public:
1059 using iterator_category = std::random_access_iterator_tag;
1060 using value_type = typename t_int_vector::value_type;
1061 using difference_type = typename t_int_vector::difference_type;
1064
1065 typedef uint64_t size_type;
1066
1067 protected:
1068 uint8_t m_offset;
1069 uint8_t m_len;
1070
1071 public:
1072 int_vector_iterator_base(uint8_t offset, uint8_t len)
1073 : m_offset(offset)
1074 , m_len(len)
1075 {}
1076
1077 int_vector_iterator_base(const t_int_vector * v = nullptr, size_type idx = 0)
1078 : m_offset(idx & 0x3F)
1079 , m_len(v == nullptr ? 0 : v->m_width)
1080 {}
1081};
1082
1083template <class t_int_vector>
1085{
1086 public:
1088 typedef uint64_t value_type;
1091 typedef typename t_int_vector::size_type size_type;
1092 typedef typename t_int_vector::difference_type difference_type;
1093
1094 friend class int_vector_const_iterator<t_int_vector>;
1095
1096 private:
1097 using int_vector_iterator_base<t_int_vector>::m_offset; // make m_offset easy usable
1098 using int_vector_iterator_base<t_int_vector>::m_len; // make m_len easy usable
1099
1100 typename t_int_vector::value_type * m_word;
1101
1102 public:
1103 int_vector_iterator(t_int_vector * v = nullptr, size_type idx = 0)
1104 : int_vector_iterator_base<t_int_vector>(v, idx)
1105 , m_word((v != nullptr) ? v->m_data + (idx >> 6) : nullptr)
1106 {}
1107
1109 : int_vector_iterator_base<t_int_vector>(it)
1110 , m_word(it.m_word)
1111 {
1112 m_offset = it.m_offset;
1113 m_len = it.m_len;
1114 }
1115
1116 reference operator*() const { return reference(m_word, m_offset, m_len); }
1117
1120 {
1121 m_offset += m_len;
1122 if (m_offset >= 64)
1123 {
1124 m_offset &= 0x3F;
1125 ++m_word;
1126 }
1127 return *this;
1128 }
1129
1132 {
1133 int_vector_iterator it = *this;
1134 ++(*this);
1135 return it;
1136 }
1137
1140 {
1141 m_offset -= m_len;
1142 if (m_offset >= 64)
1143 {
1144 m_offset &= 0x3F;
1145 --m_word;
1146 }
1147 return *this;
1148 }
1149
1152 {
1153 int_vector_iterator it = *this;
1154 --(*this);
1155 return it;
1156 }
1157
1159 {
1160 if (i < 0) return *this -= (-i);
1161 difference_type t = i * m_len;
1162 m_word += (t >> 6);
1163 if ((m_offset += (t & 0x3F)) & ~0x3F)
1164 { // if new offset is >= 64
1165 ++m_word; // add one to the word
1166 m_offset &= 0x3F; // offset = offset mod 64
1167 }
1168 return *this;
1169 }
1170
1172 {
1173 if (i < 0) return *this += (-i);
1174 difference_type t = i * m_len;
1175 m_word -= (t >> 6);
1176 if ((m_offset -= (t & 0x3F)) & ~0x3F)
1177 { // if new offset is < 0
1178 --m_word;
1179 m_offset &= 0x3F;
1180 }
1181 return *this;
1182 }
1183
1185 {
1186 if (this != &it)
1187 {
1188 m_word = it.m_word;
1189 m_offset = it.m_offset;
1190 m_len = it.m_len;
1191 }
1192 return *this;
1193 }
1194
1196 {
1197 iterator it = *this;
1198 return it += i;
1199 }
1200
1202 {
1203 iterator it = *this;
1204 return it -= i;
1205 }
1206
1207 reference operator[](difference_type i) const { return *(*this + i); }
1208
1209 bool operator==(const int_vector_iterator & it) const noexcept
1210 {
1211 return it.m_word == m_word && it.m_offset == m_offset;
1212 }
1213
1214 bool operator!=(const int_vector_iterator & it) const noexcept { return !(*this == it); }
1215
1216 bool operator<(const int_vector_iterator & it) const noexcept
1217 {
1218 if (m_word == it.m_word) return m_offset < it.m_offset;
1219 return m_word < it.m_word;
1220 }
1221
1222 bool operator>(const int_vector_iterator & it) const noexcept
1223 {
1224 if (m_word == it.m_word) return m_offset > it.m_offset;
1225 return m_word > it.m_word;
1226 }
1227
1228 bool operator>=(const int_vector_iterator & it) const noexcept { return !(*this < it); }
1229
1230 bool operator<=(const int_vector_iterator & it) const noexcept { return !(*this > it); }
1231 inline difference_type operator-(const int_vector_iterator & it) const noexcept
1232 {
1233 return (((m_word - it.m_word) << 6) + m_offset - it.m_offset) / m_len;
1234 }
1235};
1236
1237// template<class t_int_vector>
1238// void swap(const int_vector_iterator<t_int_vector> &x, const int_vector_iterator<t_int_vector> &y){
1239// x->swap(*y);
1240//}
1241
1242template <class t_int_vector>
1245{
1246 return it + n;
1247}
1248
1249template <class t_int_vector>
1251{
1252 public:
1253 typedef typename t_int_vector::value_type const_reference;
1254 typedef const typename t_int_vector::value_type * pointer;
1256 typedef typename t_int_vector::size_type size_type;
1257 typedef typename t_int_vector::difference_type difference_type;
1258
1259 template <class X>
1262 friend class int_vector_iterator<t_int_vector>;
1263 friend class int_vector_iterator_base<t_int_vector>;
1264
1265 private:
1266 using int_vector_iterator_base<t_int_vector>::m_offset; // make m_offset easy usable
1267 using int_vector_iterator_base<t_int_vector>::m_len; // make m_len easy usable
1268
1269 const typename t_int_vector::value_type * m_word;
1270
1271 public:
1272 int_vector_const_iterator(const t_int_vector * v = nullptr, size_type idx = 0)
1273 : int_vector_iterator_base<t_int_vector>(v, idx)
1274 , m_word((v != nullptr) ? v->m_data + (idx >> 6) : nullptr)
1275 {}
1276
1278 : m_word(it.m_word)
1279 {
1280 m_offset = it.m_offset;
1281 m_len = it.m_len;
1282 }
1283
1285
1287
1289 {
1290 if (m_offset + m_len <= 64) { return ((*m_word) >> m_offset) & bits::lo_set[m_len]; }
1291 return ((*m_word) >> m_offset) | ((*(m_word + 1) & bits::lo_set[(m_offset + m_len) & 0x3F]) << (64 - m_offset));
1292 }
1293
1296 {
1297 m_offset += m_len;
1298 if (m_offset >= 64)
1299 {
1300 m_offset &= 0x3F;
1301 ++m_word;
1302 }
1303 return *this;
1304 }
1305
1308 {
1309 int_vector_const_iterator it = *this;
1310 ++(*this);
1311 return it;
1312 }
1313
1316 {
1317 m_offset -= m_len;
1318 if (m_offset >= 64)
1319 {
1320 m_offset &= 0x3F;
1321 --m_word;
1322 }
1323 return *this;
1324 }
1325
1328 {
1329 int_vector_const_iterator it = *this;
1330 --(*this);
1331 return it;
1332 }
1333
1335 {
1336 if (i < 0) return *this -= (-i);
1337 difference_type t = i * m_len;
1338 m_word += (t >> 6);
1339 if ((m_offset += (t & 0x3F)) & ~0x3F)
1340 { // if new offset >= 64
1341 ++m_word; // add one to the word
1342 m_offset &= 0x3F; // offset = offset mod 64
1343 }
1344 return *this;
1345 }
1346
1348 {
1349 if (i < 0) return *this += (-i);
1350 difference_type t = i * m_len;
1351 m_word -= (t >> 6);
1352 if ((m_offset -= (t & 0x3F)) & ~0x3F)
1353 { // if new offset is < 0
1354 --m_word;
1355 m_offset &= 0x3F;
1356 }
1357 return *this;
1358 }
1359
1361 {
1362 const_iterator it = *this;
1363 return it += i;
1364 }
1365
1367 {
1368 const_iterator it = *this;
1369 return it -= i;
1370 }
1371
1372 const_reference operator[](difference_type i) const { return *(*this + i); }
1373
1374 bool operator==(const int_vector_const_iterator & it) const noexcept
1375 {
1376 return it.m_word == m_word && it.m_offset == m_offset;
1377 }
1378
1379 bool operator!=(const int_vector_const_iterator & it) const noexcept { return !(*this == it); }
1380
1381 bool operator<(const int_vector_const_iterator & it) const noexcept
1382 {
1383 if (m_word == it.m_word) return m_offset < it.m_offset;
1384 return m_word < it.m_word;
1385 }
1386
1387 bool operator>(const int_vector_const_iterator & it) const noexcept
1388 {
1389 if (m_word == it.m_word) return m_offset > it.m_offset;
1390 return m_word > it.m_word;
1391 }
1392
1393 bool operator>=(const int_vector_const_iterator & it) const noexcept { return !(*this < it); }
1394
1395 bool operator<=(const int_vector_const_iterator & it) const noexcept { return !(*this > it); }
1396};
1397
1398template <class t_int_vector>
1402{
1403 return (((x.m_word - y.m_word) << 6) + x.m_offset - y.m_offset) / x.m_len;
1404}
1405
1406template <class t_int_vector>
1410{
1411 return it + n;
1412}
1413
1414template <class t_bv>
1415inline typename std::enable_if<std::is_same<typename t_bv::index_category, bv_tag>::value, std::ostream &>::type
1416operator<<(std::ostream & os, const t_bv & bv)
1417{
1418 for (auto b : bv) { os << b; }
1419 return os;
1420}
1421
1422// ==== int_vector implementation ====
1423
1424template <uint8_t t_width>
1425inline int_vector<t_width>::int_vector(size_type size, value_type default_value, uint8_t int_width)
1426 : m_size(0)
1427 , m_capacity(0)
1428 , m_data(nullptr)
1429 , m_width(t_width)
1430{
1431 width(int_width);
1432 assign(size, default_value);
1433}
1434
1435template <uint8_t t_width>
1437 : m_size(v.m_size)
1438 , m_capacity(v.m_capacity)
1439 , m_data(v.m_data)
1440 , m_width(v.m_width)
1441{
1442 v.m_data = nullptr; // ownership of v.m_data now transfered
1443 v.m_size = 0;
1444 v.m_capacity = 0;
1445}
1446
1447template <uint8_t t_width>
1449 : m_size(0)
1450 , m_capacity(0)
1451 , m_data(nullptr)
1452 , m_width(v.m_width)
1453{
1454 width(v.m_width);
1455 resize(v.size());
1456 if (v.m_size > 0)
1457 {
1458 if (memcpy(m_data, v.data(), bit_data_size() << 3) == nullptr)
1459 {
1460 throw std::bad_alloc(); // LCOV_EXCL_LINE
1461 }
1462 }
1463}
1464
1465template <uint8_t t_width>
1467{
1468 if (this != &v)
1469 { // if v is not the same object
1470 int_vector<t_width> tmp(v);
1471 *this = std::move(tmp);
1472 }
1473 return *this;
1474}
1475
1476template <uint8_t t_width>
1478{
1479 if (this != &v)
1480 { // if v is not the same object
1481 memory_manager::clear(*this); // clear allocated memory
1482 m_size = v.m_size;
1483 m_data = v.m_data; // assign new memory
1484 m_width = v.m_width;
1485 m_capacity = v.m_capacity;
1486 v.m_data = nullptr;
1487 v.m_size = 0;
1488 v.m_capacity = 0;
1489 }
1490 return *this;
1491}
1492
1493// Destructor
1494template <uint8_t t_width>
1496{
1497 memory_manager::clear(*this);
1498}
1499
1500// sdsl::swap (to fulfill the container concept)
1501template <uint8_t t_width>
1503{
1504 std::swap(v1, v2);
1505}
1506
1507template <uint8_t t_width>
1509{
1510 if (size > m_capacity || m_data == nullptr) { memory_manager::resize(*this, size); }
1511 m_size = size;
1512}
1513
1514template <uint8_t t_width>
1515void int_vector<t_width>::bit_resize(const size_type size, const value_type value)
1516{
1517 size_type old_size = m_size;
1518 bit_resize(size);
1519 auto it = begin() + old_size / m_width;
1520 util::set_to_value(*this, value, it);
1521}
1522
1523template <uint8_t t_width>
1524auto int_vector<t_width>::get_int(size_type idx, const uint8_t len) const -> value_type
1525{
1526#ifdef SDSL_DEBUG
1527 if (idx + len > m_size)
1528 {
1529 throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::get_int(size_type, uint8_t); idx+len > size()!");
1530 }
1531 if (len > 64) { throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::get_int(size_type, uint8_t); len>64!"); }
1532#endif
1533 return bits::read_int(m_data + (idx >> 6), idx & 0x3F, len);
1534}
1535
1536template <uint8_t t_width>
1537inline void int_vector<t_width>::set_int(size_type idx, value_type x, const uint8_t len)
1538{
1539#ifdef SDSL_DEBUG
1540 if (idx + len > m_size)
1541 {
1542 throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::set_int(size_type, uint8_t); idx+len > size()!");
1543 }
1544 if (len > 64) { throw std::out_of_range("OUT_OF_RANGE_ERROR: int_vector::set_int(size_type, uint8_t); len>64!"); }
1545#endif
1546 bits::write_int(m_data + (idx >> 6), x, idx & 0x3F, len);
1547}
1548
1549template <uint8_t t_width>
1551{
1552 return m_size / t_width;
1553}
1554
1555// specialized size method for 64-bit integer vector
1556template <>
1557inline typename int_vector<64>::size_type int_vector<64>::size() const noexcept
1558{
1559 return m_size >> 6;
1560}
1561
1562// specialized size method for 32-bit integer vector
1563template <>
1564inline typename int_vector<32>::size_type int_vector<32>::size() const noexcept
1565{
1566 return m_size >> 5;
1567}
1568
1569// specialized size method for 16-bit integer vector
1570template <>
1571inline typename int_vector<16>::size_type int_vector<16>::size() const noexcept
1572{
1573 return m_size >> 4;
1574}
1575
1576// specialized size method for 8-bit integer vector
1577template <>
1578inline typename int_vector<8>::size_type int_vector<8>::size() const noexcept
1579{
1580 return m_size >> 3;
1581}
1582
1583// specialized size method for bit_vector
1584template <>
1585inline typename int_vector<1>::size_type int_vector<1>::size() const noexcept
1586{
1587 return m_size;
1588}
1589
1590// specialized size method for dyanmic int_vector
1591template <>
1592inline typename int_vector<0>::size_type int_vector<0>::size() const noexcept
1593{
1594 return m_size / m_width;
1595}
1596
1597template <uint8_t t_width>
1599{
1600 return m_capacity / t_width;
1601}
1602
1603// specialized capacity method for 64-bit integer vector
1604template <>
1606{
1607 return m_capacity >> 6;
1608}
1609
1610// specialized capacity method for 32-bit integer vector
1611template <>
1613{
1614 return m_capacity >> 5;
1615}
1616
1617// specialized capacity method for 16-bit integer vector
1618template <>
1620{
1621 return m_capacity >> 4;
1622}
1623
1624// specialized capacity method for 8-bit integer vector
1625template <>
1627{
1628 return m_capacity >> 3;
1629}
1630
1631// specialized capacity method for bit_vector
1632template <>
1634{
1635 return m_capacity;
1636}
1637
1638// specialized capacity method for dynamic int_vector
1639template <>
1641{
1642 return m_capacity / m_width;
1643}
1644
1645template <uint8_t t_width>
1646inline auto int_vector<t_width>::operator[](const size_type & idx) noexcept -> reference
1647{
1648 assert(idx < this->size());
1649 size_type i = idx * m_width;
1650 return reference(this->m_data + (i >> 6), i & 0x3F, m_width);
1651}
1652
1653// specialized [] operator for 64 bit access.
1654template <>
1655inline auto int_vector<64>::operator[](const size_type & idx) noexcept -> reference
1656{
1657 assert(idx < this->size());
1658 return *(this->m_data + idx);
1659}
1660
1661// specialized [] operator for 32 bit access.
1662template <>
1663inline auto int_vector<32>::operator[](const size_type & idx) noexcept -> reference
1664{
1665 assert(idx < this->size());
1666 return *(((uint32_t *)(this->m_data)) + idx);
1667}
1668
1669// specialized [] operator for 16 bit access.
1670template <>
1671inline auto int_vector<16>::operator[](const size_type & idx) noexcept -> reference
1672{
1673 assert(idx < this->size());
1674 return *(((uint16_t *)(this->m_data)) + idx);
1675}
1676
1677// specialized [] operator for 8 bit access.
1678template <>
1679inline auto int_vector<8>::operator[](const size_type & idx) noexcept -> reference
1680{
1681 assert(idx < this->size());
1682 return *(((uint8_t *)(this->m_data)) + idx);
1683}
1684
1685template <uint8_t t_width>
1686inline auto int_vector<t_width>::operator[](const size_type & idx) const noexcept -> const_reference
1687{
1688 assert(idx < this->size());
1689 return get_int(idx * t_width, t_width);
1690}
1691
1692template <>
1693inline auto int_vector<0>::operator[](const size_type & idx) const noexcept -> const_reference
1694{
1695 assert(idx < this->size());
1696 return get_int(idx * m_width, m_width);
1697}
1698
1699template <>
1700inline auto int_vector<64>::operator[](const size_type & idx) const noexcept -> const_reference
1701{
1702 assert(idx < this->size());
1703 return *(this->m_data + idx);
1704}
1705
1706template <>
1707inline auto int_vector<32>::operator[](const size_type & idx) const noexcept -> const_reference
1708{
1709 assert(idx < this->size());
1710 return *(((uint32_t *)this->m_data) + idx);
1711}
1712
1713template <>
1714inline auto int_vector<16>::operator[](const size_type & idx) const noexcept -> const_reference
1715{
1716 assert(idx < this->size());
1717 return *(((uint16_t *)this->m_data) + idx);
1718}
1719
1720template <>
1721inline auto int_vector<8>::operator[](const size_type & idx) const noexcept -> const_reference
1722{
1723 assert(idx < this->size());
1724 return *(((uint8_t *)this->m_data) + idx);
1725}
1726
1727template <>
1728inline auto int_vector<1>::operator[](const size_type & idx) const noexcept -> const_reference
1729{
1730 assert(idx < this->size());
1731 return ((*(m_data + (idx >> 6))) >> (idx & 0x3F)) & 1;
1732}
1733
1734template <uint8_t t_width>
1735bool int_vector<t_width>::operator<(const int_vector & v) const noexcept
1736{
1737 size_type min_size = size();
1738 if (min_size > v.size()) min_size = v.size();
1739 for (auto it = begin(), end = begin() + min_size, it_v = v.begin(); it != end; ++it, ++it_v)
1740 {
1741 if (*it == *it_v)
1742 continue;
1743 else
1744 return *it < *it_v;
1745 }
1746 return size() < v.size();
1747}
1748
1749template <uint8_t t_width>
1750bool int_vector<t_width>::operator>(const int_vector & v) const noexcept
1751{
1752 size_type min_size = size();
1753 if (min_size > v.size()) min_size = v.size();
1754 for (auto it = begin(), end = begin() + min_size, it_v = v.begin(); it != end; ++it, ++it_v)
1755 {
1756 if (*it == *it_v)
1757 continue;
1758 else
1759 return *it > *it_v;
1760 }
1761 return size() > v.size();
1762}
1763
1764template <uint8_t t_width>
1765bool int_vector<t_width>::operator<=(const int_vector & v) const noexcept
1766{
1767 return *this == v or *this < v;
1768}
1769
1770template <uint8_t t_width>
1771bool int_vector<t_width>::operator>=(const int_vector & v) const noexcept
1772{
1773 return *this == v or *this > v;
1774}
1775
1776template <uint8_t t_width>
1778{
1779 assert(v.bit_size() == bit_size());
1780 for (uint64_t i = 0; i < bit_data_size(); ++i) m_data[i] &= v.m_data[i];
1781 return *this;
1782}
1783
1784template <uint8_t t_width>
1786{
1787 assert(bit_size() == v.bit_size());
1788 for (uint64_t i = 0; i < bit_data_size(); ++i) m_data[i] |= v.m_data[i];
1789 return *this;
1790}
1791
1792template <uint8_t t_width>
1794{
1795 assert(bit_size() == v.bit_size());
1796 for (uint64_t i = 0; i < bit_data_size(); ++i) m_data[i] ^= v.m_data[i];
1797 return *this;
1798}
1799
1800template <uint8_t t_width>
1802{
1803 size_type written_bytes = 0;
1804 uint64_t * p = m_data;
1805 size_type idx = 0;
1806 while (idx + conf::SDSL_BLOCK_SIZE < bit_data_size())
1807 {
1808 out.write((char *)p, conf::SDSL_BLOCK_SIZE * sizeof(uint64_t));
1809 written_bytes += conf::SDSL_BLOCK_SIZE * sizeof(uint64_t);
1811 idx += conf::SDSL_BLOCK_SIZE;
1812 }
1813 out.write((char *)p, (bit_data_size() - idx) * sizeof(uint64_t));
1814 written_bytes += (bit_data_size() - idx) * sizeof(uint64_t);
1815 return written_bytes;
1816}
1817
1818template <uint8_t t_width>
1821 std::string name) const
1822{
1823 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
1824 size_type written_bytes = int_vector<t_width>::write_header(m_size, m_width, out);
1825 written_bytes += write_data(out);
1826 structure_tree::add_size(child, written_bytes);
1827 return written_bytes;
1828}
1829
1830template <uint8_t t_width>
1831void int_vector<t_width>::load(std::istream & in)
1832{
1835
1836 bit_resize(size);
1837 uint64_t * p = m_data;
1838 size_type idx = 0;
1839 while (idx + conf::SDSL_BLOCK_SIZE < bit_data_size())
1840 {
1841 in.read((char *)p, conf::SDSL_BLOCK_SIZE * sizeof(uint64_t));
1843 idx += conf::SDSL_BLOCK_SIZE;
1844 }
1845 in.read((char *)p, (bit_data_size() - idx) * sizeof(uint64_t));
1846}
1847
1848template <uint8_t t_width>
1849template <typename archive_t>
1850inline typename std::enable_if<cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
1851 archive_t>::value,
1852 void>::type
1854{
1855 ar(CEREAL_NVP(cereal::make_size_tag(static_cast<int_width_type>(m_width))));
1856 ar(CEREAL_NVP(growth_factor));
1857 ar(CEREAL_NVP(cereal::make_size_tag(static_cast<size_type>(m_size))));
1858 ar(cereal::make_nvp("data", cereal::binary_data(m_data, bit_data_size() * sizeof(uint64_t))));
1859}
1860
1861template <uint8_t t_width>
1862template <typename archive_t>
1863inline typename std::enable_if<!cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
1864 archive_t>::value,
1865 void>::type
1867{
1868 ar(CEREAL_NVP(m_width));
1869 ar(CEREAL_NVP(growth_factor));
1870 ar(CEREAL_NVP(m_size));
1871 for (value_type const & v : *this) ar(v);
1872}
1873
1874template <uint8_t t_width>
1875template <typename archive_t>
1876inline typename std::enable_if<cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
1877 archive_t>::value,
1878 void>::type
1880{
1881 ar(CEREAL_NVP(cereal::make_size_tag(m_width)));
1882 ar(CEREAL_NVP(growth_factor));
1883 ar(CEREAL_NVP(cereal::make_size_tag(m_size)));
1884 resize(size());
1885 ar(cereal::make_nvp("data", cereal::binary_data(m_data, bit_data_size() * sizeof(uint64_t))));
1886}
1887
1888template <uint8_t t_width>
1889template <typename archive_t>
1890inline typename std::enable_if<!cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
1891 archive_t>::value,
1892 void>::type
1894{
1895 ar(CEREAL_NVP(m_width));
1896 width(width());
1897 ar(CEREAL_NVP(growth_factor));
1898 ar(CEREAL_NVP(m_size));
1899 resize(size());
1900
1901 for (size_t i = 0; i < size(); ++i)
1902 {
1903 value_type tmp;
1904 ar(tmp);
1905 operator[](i) = tmp;
1906 }
1907}
1908
1910 typename int_vector_trait<64>::int_vector_type * v) noexcept
1911{
1912 return v->data();
1913}
1915 typename int_vector_trait<64>::int_vector_type * v) noexcept
1916{
1917 return v->data() + v->size();
1918}
1920 const typename int_vector_trait<64>::int_vector_type * v) noexcept
1921{
1922 return v->data();
1923}
1925 const typename int_vector_trait<64>::int_vector_type * v) noexcept
1926{
1927 return v->data() + v->size();
1928}
1929
1931 typename int_vector_trait<32>::int_vector_type * v) noexcept
1932{
1933 return (uint32_t *)v->data();
1934}
1936 typename int_vector_trait<32>::int_vector_type * v) noexcept
1937{
1938 return ((uint32_t *)v->data()) + v->size();
1939}
1941 const typename int_vector_trait<32>::int_vector_type * v) noexcept
1942{
1943 return (uint32_t *)v->data();
1944}
1946 const typename int_vector_trait<32>::int_vector_type * v) noexcept
1947{
1948 return ((uint32_t *)v->data()) + v->size();
1949}
1950
1952 typename int_vector_trait<16>::int_vector_type * v) noexcept
1953{
1954 return (uint16_t *)v->data();
1955}
1957 typename int_vector_trait<16>::int_vector_type * v) noexcept
1958{
1959 return ((uint16_t *)v->data()) + v->size();
1960}
1962 const typename int_vector_trait<16>::int_vector_type * v) noexcept
1963{
1964 return (uint16_t *)v->data();
1965}
1967 const typename int_vector_trait<16>::int_vector_type * v) noexcept
1968{
1969 return ((uint16_t *)v->data()) + v->size();
1970}
1971
1973 typename int_vector_trait<8>::int_vector_type * v) noexcept
1974{
1975 return (uint8_t *)v->data();
1976}
1978 typename int_vector_trait<8>::int_vector_type * v) noexcept
1979{
1980 return ((uint8_t *)v->data()) + v->size();
1981}
1983 const typename int_vector_trait<8>::int_vector_type * v) noexcept
1984{
1985 return (uint8_t *)v->data();
1986}
1988 const typename int_vector_trait<8>::int_vector_type * v) noexcept
1989{
1990 return ((uint8_t *)v->data()) + v->size();
1991}
1992
1993} // end namespace sdsl
1994
1997
1998#endif
bits.hpp contains the sdsl::bits class.
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
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
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!=(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
const_iterator & operator+=(difference_type i)
bool operator>=(const int_vector_const_iterator &it) const noexcept
bool operator<=(const int_vector_const_iterator &it) const noexcept
int_vector_const_iterator(const int_vector_const_iterator &)=default
const_reference operator*() const
const_iterator & operator--()
Prefix decrement of the Iterator.
friend int_vector_const_iterator< X >::difference_type operator-(const int_vector_const_iterator< X > &x, const int_vector_const_iterator< X > &y)
t_int_vector::value_type const_reference
bool operator<(const int_vector_const_iterator &it) const noexcept
int_vector_const_iterator(const t_int_vector *v=nullptr, size_type idx=0)
bool operator==(const int_vector_const_iterator &it) const noexcept
int_vector_const_iterator & operator=(const int_vector_const_iterator &)=default
const_iterator operator++(int)
Postfix increment of the Iterator.
const_iterator & operator++()
Prefix 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)
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)
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--()
Prefix decrement of the Iterator.
iterator operator+(difference_type i) const
iterator & operator+=(difference_type i)
iterator operator-(difference_type i) const
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)
difference_type operator-(const int_vector_iterator &it) const noexcept
iterator & operator=(const int_vector_iterator< t_int_vector > &it)
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 & operator=(const int_vector_reference &x) noexcept
int_vector_reference & operator=(bool x) noexcept
Assignment operator for the proxy class.
int_vector_reference()=delete
Default constructor explicitly deleted.
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 &&x) noexcept
bool operator==(const int_vector_reference &x) const noexcept
A proxy class that acts as a reference to an integer of length len bits in a int_vector.
Definition: int_vector.hpp:845
t_int_vector::value_type value_type
Definition: int_vector.hpp:847
bool operator<(const int_vector_reference &x) const noexcept
Definition: int_vector.hpp:941
int_vector_reference & operator=(int_vector_reference &&x) noexcept
Definition: int_vector.hpp:886
int_vector_reference & operator+=(const value_type x) noexcept
Add assign from the proxy object.
Definition: int_vector.hpp:924
int_vector_reference & operator=(value_type x) noexcept
Assignment operator for the proxy class.
Definition: int_vector.hpp:878
int_vector_reference & operator-=(const value_type x) noexcept
Subtract assign from the proxy object.
Definition: int_vector.hpp:932
int_vector_reference & operator=(const int_vector_reference &x) noexcept
Definition: int_vector.hpp:884
value_type operator++(int) noexcept
Postfix increment of the proxy object.
Definition: int_vector.hpp:900
int_vector_reference & operator--() noexcept
Prefix decrement of the proxy object.
Definition: int_vector.hpp:908
int_vector_reference()=delete
Default constructor explicitly deleted.
value_type operator--(int) noexcept
Postfix decrement of the proxy object.
Definition: int_vector.hpp:916
int_vector_reference & operator++() noexcept
Prefix increment of the proxy object.
Definition: int_vector.hpp:892
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:939
A generic vector class for integers of width .
Definition: int_vector.hpp:216
iterator end() noexcept
Iterator that points to the element after the last element of int_vector.
Definition: int_vector.hpp:764
void flip()
Flip all bits of bit_vector.
Definition: int_vector.hpp:779
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:400
const raw_wrapper raw
Definition: int_vector.hpp:837
uint64_t * data() noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:571
reference operator[](const size_type &i) noexcept
non const version of [] operator
rank_support_v< 1, 1 > rank_1_type
Definition: int_vector.hpp:231
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:500
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:470
void reserve(size_type capacity)
Reserve storage. If the new capacity is smaller than the current, this method does nothing.
Definition: int_vector.hpp:511
int_vector_trait< t_width >::iterator iterator
Definition: int_vector.hpp:222
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:527
int_vec_category_trait< t_width >::type index_category
Definition: int_vector.hpp:235
const value_type * const_pointer
Definition: int_vector.hpp:227
const_iterator end() const noexcept
Const iterator that points to the element after the last element of int_vector.
Definition: int_vector.hpp:770
const_reference back() const noexcept
Returns last element.
Definition: int_vector.hpp:434
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:326
void swap(int_vector &v) noexcept
Swap method for int_vector.
Definition: int_vector.hpp:503
rank_support_v< 0, 1 > rank_0_type
Definition: int_vector.hpp:232
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:229
ptrdiff_t difference_type
Definition: int_vector.hpp:228
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:234
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:602
bool operator>=(const int_vector &v) const noexcept
Greater of equal operator.
int_vector_reference< int_vector > * pointer
Definition: int_vector.hpp:226
int_vector_trait< t_width >::const_reference const_reference
Definition: int_vector.hpp:225
iterator erase(const_iterator it)
Remove element that iterator is pointing to.
Definition: int_vector.hpp:344
int_vector_trait< t_width >::int_width_type int_width_type
Definition: int_vector.hpp:230
size_type write_data(std::ostream &out) const
reference at(const size_type &i)
non const version of at() function
Definition: int_vector.hpp:665
friend bool operator==(const int_vector< t_width > &lhs, const container &rhs) noexcept
Equality operator for an arbitrary container.
Definition: int_vector.hpp:708
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:386
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:547
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:370
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:561
bool operator!=(const int_vector< t_width2 > &v) const noexcept
Inequality operator for two int_vectors.
Definition: int_vector.hpp:721
void clear() noexcept
Clearing the int_vector. Allocated memory will not be released.
Definition: int_vector.hpp:339
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:233
const_iterator begin() const noexcept
Const iterator that points to the first element of the int_vector.
Definition: int_vector.hpp:767
reference back() noexcept
Returns last element.
Definition: int_vector.hpp:431
int_vector & operator=(int_vector &&v)
Move assignment operator.
int_vector_trait< t_width >::const_iterator const_iterator
Definition: int_vector.hpp:223
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.
Definition: int_vector.hpp:414
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:773
void shrink_to_fit()
Free unused allocated memory.
Definition: int_vector.hpp:506
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
Definition: int_vector.hpp:595
int_vector_trait< t_width >::reference reference
Definition: int_vector.hpp:224
void emplace_back(Args &&... args)
Insert an element constructed with std::forward<Args>(args) at the end.
Definition: int_vector.hpp:440
void assign(std::initializer_list< value_type > il)
Assign. Resize int_vector and initialize with initializer_list.
Definition: int_vector.hpp:479
size_type size() const noexcept
The number of elements in the int_vector.
static constexpr uint8_t fixed_int_width
Definition: int_vector.hpp:252
iterator insert(const_iterator it, value_type value)
Insert an element before the element that the iterator is pointing to.
Definition: int_vector.hpp:379
void push_back(value_type value)
Insert element at the end.
Definition: int_vector.hpp:448
const_reference at(const size_type &i) const
const version of at() function
Definition: int_vector.hpp:671
int_vector & operator^=(const int_vector &v)
bitwise-xor-update operator
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:491
float growth_factor
Growth factor for amortized constant time operations.
Definition: int_vector.hpp:253
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.
Definition: int_vector.hpp:776
int_vector(size_type size=0)
Constructor to fix possible comparison with integeres issue.
Definition: int_vector.hpp:311
int_vector_trait< t_width >::value_type value_type
Definition: int_vector.hpp:221
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:789
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:566
bool operator==(const int_vector< t_width > &v) const noexcept
Equality operator for two int_vectors.
Definition: int_vector.hpp:686
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:425
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.
Definition: int_vector.hpp:542
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:521
int_vector(std::initializer_list< value_type > il)
Constructor for initializer_list.
Definition: int_vector.hpp:315
iterator erase(const_iterator first, const_iterator last)
Remove elements in given iterator range.
Definition: int_vector.hpp:356
const_reference front() const noexcept
Returns first element.
Definition: int_vector.hpp:428
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:806
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:455
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
Definition: int_vector.hpp:759
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 structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &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:33
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition: util.hpp:563
Namespace for the succinct data structure library.
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)
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
Definition: int_vector.hpp:946
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)
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:44
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
Definition: int_vector.hpp:53
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
std::ostream & operator<<(std::ostream &os, const bp_interval< t_int > &interval)
Definition: cst_sct3.hpp:1331
ram_fs.hpp
sfstream.hpp contains a two stream class which can be used to read/write from/to files or strings.
static 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:770
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:717
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:187
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Definition: int_vector.hpp:828
raw_wrapper(const int_vector &_vec)
Definition: int_vector.hpp:824
int_vector< 16 > int_vector_type
Definition: int_vector.hpp:168
static iterator begin(int_vector_type *v) noexcept
static iterator end(int_vector_type *v) noexcept
static const_iterator begin(const int_vector_type *v) noexcept
static void set_width(uint8_t, int_width_type) noexcept
Definition: int_vector.hpp:180
static const_iterator end(const int_vector_type *v) noexcept
const uint16_t * const_iterator
Definition: int_vector.hpp:173
const uint32_t * const_iterator
Definition: int_vector.hpp:154
static iterator begin(int_vector_type *v) noexcept
static iterator end(int_vector_type *v) noexcept
static void set_width(uint8_t, int_width_type) noexcept
Definition: int_vector.hpp:161
static const_iterator end(const int_vector_type *v) noexcept
static const_iterator begin(const int_vector_type *v) noexcept
int_vector< 32 > int_vector_type
Definition: int_vector.hpp:149
const uint64_t * const_iterator
Definition: int_vector.hpp:135
static const_iterator begin(const int_vector_type *v) noexcept
static iterator begin(int_vector_type *v) noexcept
static iterator end(int_vector_type *v) noexcept
static const_iterator end(const int_vector_type *v) noexcept
int_vector< 64 > int_vector_type
Definition: int_vector.hpp:130
static void set_width(uint8_t, int_width_type) noexcept
Definition: int_vector.hpp:142
static const_iterator begin(const int_vector_type *v) noexcept
int_vector< 8 > int_vector_type
Definition: int_vector.hpp:187
const uint8_t * const_iterator
Definition: int_vector.hpp:192
static iterator begin(int_vector_type *v) noexcept
static void set_width(uint8_t, int_width_type) noexcept
Definition: int_vector.hpp:199
static const_iterator end(const int_vector_type *v) noexcept
static iterator end(int_vector_type *v) noexcept
int_vector_const_iterator< int_vector_type > const_iterator
Definition: int_vector.hpp:113
int_vector< t_width > int_vector_type
Definition: int_vector.hpp:108
static void set_width(uint8_t new_width, int_width_type &width) noexcept
Definition: int_vector.hpp:120
static iterator begin(int_vector_type *v) noexcept
Definition: int_vector.hpp:115
int_vector_reference< int_vector_type > reference
Definition: int_vector.hpp:109
static const_iterator end(const int_vector_type *v) noexcept
Definition: int_vector.hpp:118
int_vector_iterator< int_vector_type > iterator
Definition: int_vector.hpp:112
static const_iterator begin(const int_vector_type *v) noexcept
Definition: int_vector.hpp:117
static iterator end(int_vector_type *v) noexcept
Definition: int_vector.hpp:116
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.