8 #ifndef INCLUDED_SDSL_INT_VECTOR
9 #define INCLUDED_SDSL_INT_VECTOR
38 #include <initializer_list>
39 #include <type_traits>
47 template <u
int8_t t_w
idth = 0>
50 template <
class int_vector_type>
56 template <
class t_
int_vector>
59 template <
class t_
int_vector>
62 template <
class t_
int_vector>
65 template <
class t_
int_vector>
68 template <u
int8_t t_w
idth, std::ios_base::openmode t_mode>
71 template <u
int8_t b, u
int8_t t_patter_len>
78 template <u
int8_t t_bit_pattern, u
int8_t t_pattern_len>
89 template <u
int8_t t_w
idth>
93 template <u
int8_t t_w
idth>
105 template <u
int8_t t_w
idth>
119 return iterator(v, v->size() * v->width());
131 if (0 < new_width and new_width <= 64)
251 template <u
int8_t t_w
idth>
255 static_assert(t_width <= 64,
"int_vector: width of must be at most 64bits.");
278 template <u
int8_t, std::ios_base::openmode>
280 template <
typename T>
282 template <
typename T>
284 template <
typename T>
307 if (
bit_size > m_capacity || m_data ==
nullptr)
310 size_type tmp_capacity = m_capacity == 0 ? 64 : m_capacity;
313 std::ceil(std::log((
bit_size + tmp_capacity - 1) / tmp_capacity) /
315 size_type new_capacity = std::ceil(tmp_capacity * resize_factor);
318 m_size =
size * m_width;
322 size_type bit_data_size()
const {
return (m_size + 63) >> 6; }
349 template <
typename input_iterator_t>
350 int_vector(
typename std::enable_if<std::is_base_of<std::input_iterator_tag,
351 typename std::iterator_traits<input_iterator_t>::iterator_category>::
353 input_iterator_t>::type first,
354 input_iterator_t last)
363 void clear() noexcept { m_size = 0; }
371 std::copy(it_nonconst + 1,
end(), it_nonconst);
384 std::copy(last_nonconst,
end(), first_nonconst);
386 return first_nonconst;
393 template <
class... Args>
413 amortized_resize(
size() + n);
415 std::copy_backward(it_new,
end() - n,
end());
416 std::fill_n(it_new, n, value);
426 return insert(it, il.begin(), il.end());
434 template <
typename input_iterator_t>
435 typename std::enable_if<std::is_base_of<std::input_iterator_tag,
436 typename std::iterator_traits<input_iterator_t>::iterator_category>::value,
441 amortized_resize(
size() + last - first);
443 std::copy_backward(it_new,
end() - (last - first),
end());
444 std::copy(first, last, it_new);
463 template <
class... Args>
474 amortized_resize(
size() + 1);
475 *(
end() - 1) = value;
496 bit_resize(
size * m_width);
503 void assign(std::initializer_list<value_type> il)
505 bit_resize(il.size() * m_width);
507 for (
auto x : il) { (*this)[idx++] = x; }
514 template <
typename input_iterator_t>
515 void assign(input_iterator_t first, input_iterator_t last)
517 assert(first <= last);
518 bit_resize((last - first) * m_width);
520 while (first < last) { (*this)[idx++] = *(first++); }
524 bool empty() const noexcept {
return 0 == m_size; }
590 const uint64_t *
data() const noexcept {
return m_data; }
595 uint64_t *
data() noexcept {
return m_data; }
619 uint8_t
width() const noexcept {
return m_width; }
646 template <
typename archive_t>
647 inline typename std::enable_if<!cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
653 template <
typename archive_t>
654 inline typename std::enable_if<cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
660 template <
typename archive_t>
661 inline typename std::enable_if<!cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
667 template <
typename archive_t>
668 inline typename std::enable_if<cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
712 if (
bit_size() != v.bit_size())
return false;
713 if (
empty())
return true;
714 const uint64_t * data1 = v.data();
715 const uint64_t * data2 =
data();
716 for (
size_type i = 0; i < bit_data_size() - 1; ++i)
718 if (*(data1++) != *(data2++))
return false;
720 uint8_t l = 64 - ((bit_data_size() << 6) - m_size);
731 template <
class container>
734 return std::equal(lhs.begin(), lhs.end(), rhs.begin());
744 template <u
int8_t t_w
idth2>
747 return !(*
this == v);
805 static_assert(1 == t_width,
"int_vector: flip() is available only for bit_vector.");
808 for (uint64_t i = 0; i < bit_data_size(); ++i) { m_data[i] = ~m_data[i]; }
815 uint64_t width_and_size = 0;
818 uint8_t read_int_width = (uint8_t)(width_and_size >> 56);
819 if (t_width == 0) { int_width = read_int_width; }
820 if (t_width > 0 and t_width != read_int_width)
822 std::cerr <<
"Warning: Width of int_vector<" << (size_t)t_width <<
">";
823 std::cerr <<
" was specified as " << (
size_type)read_int_width << std::endl;
824 std::cerr <<
"Length is " <<
size <<
" bits" << std::endl;
826 return sizeof(width_and_size);
834 if (t_width != int_width)
836 std::cout <<
"Warning: writing width=" << (
size_type)int_width <<
" != fixed " << (
size_type)t_width
840 uint64_t width_and_size = (((uint64_t)int_width) << 56) |
size;
857 return written_bytes;
867 template <
class t_
int_vector>
874 typename t_int_vector::value_type *
const m_word;
875 const uint8_t m_offset;
926 value_type val = (
typename t_int_vector::value_type) *
this;
969 template <
class t_
int_vector>
979 template <
class t_
int_vector>
990 template <
class t_
int_vector>
1010 uint64_t *
const m_word;
1026 , m_mask(1ULL << offset){};
1042 operator bool() const noexcept {
return !!(*m_word & m_mask); }
1079 template <
class t_
int_vector>
1081 :
public std::iterator<std::random_access_iterator_tag,
1082 typename t_int_vector::value_type,
1083 typename t_int_vector::difference_type>
1100 ,
m_len(v == nullptr ? 0 : v->m_width)
1104 template <
class t_
int_vector>
1121 typename t_int_vector::value_type * m_word;
1126 , m_word((v != nullptr) ? v->m_data + (idx >> 6) : nullptr)
1181 if (i < 0)
return *
this -= (-i);
1184 if ((
m_offset += (t & 0x3F)) & ~0x3F)
1194 if (i < 0)
return *
this += (-i);
1197 if ((
m_offset -= (t & 0x3F)) & ~0x3F)
1232 return it.m_word == m_word && it.m_offset ==
m_offset;
1239 if (m_word == it.m_word)
return m_offset < it.m_offset;
1240 return m_word < it.m_word;
1245 if (m_word == it.m_word)
return m_offset > it.m_offset;
1246 return m_word > it.m_word;
1254 return (((m_word - it.m_word) << 6) +
m_offset - it.m_offset) /
m_len;
1263 template <
class t_
int_vector>
1270 template <
class t_
int_vector>
1275 typedef const typename t_int_vector::value_type *
pointer;
1290 const typename t_int_vector::value_type * m_word;
1295 , m_word((v != nullptr) ? v->m_data + (idx >> 6) : nullptr)
1353 if (i < 0)
return *
this -= (-i);
1356 if ((
m_offset += (t & 0x3F)) & ~0x3F)
1366 if (i < 0)
return *
this += (-i);
1369 if ((
m_offset -= (t & 0x3F)) & ~0x3F)
1393 return it.m_word == m_word && it.m_offset ==
m_offset;
1400 if (m_word == it.m_word)
return m_offset < it.m_offset;
1401 return m_word < it.m_word;
1406 if (m_word == it.m_word)
return m_offset > it.m_offset;
1407 return m_word > it.m_word;
1415 template <
class t_
int_vector>
1423 template <
class t_
int_vector>
1431 template <
class t_bv>
1432 inline typename std::enable_if<std::is_same<typename t_bv::index_category, bv_tag>::value, std::ostream &>::type
1433 operator<<(std::ostream & os,
const t_bv & bv)
1435 for (
auto b : bv) { os << b; }
1441 template <u
int8_t t_w
idth>
1452 template <u
int8_t t_w
idth>
1455 , m_capacity(v.m_capacity)
1457 , m_width(v.m_width)
1464 template <u
int8_t t_w
idth>
1469 , m_width(v.m_width)
1475 if (memcpy(m_data, v.
data(), bit_data_size() << 3) ==
nullptr)
1477 throw std::bad_alloc();
1482 template <u
int8_t t_w
idth>
1488 *
this = std::move(tmp);
1493 template <u
int8_t t_w
idth>
1501 m_width = v.m_width;
1502 m_capacity = v.m_capacity;
1511 template <u
int8_t t_w
idth>
1518 template <u
int8_t t_w
idth>
1524 template <u
int8_t t_w
idth>
1531 template <u
int8_t t_w
idth>
1536 auto it = begin() + old_size / m_width;
1540 template <u
int8_t t_w
idth>
1544 if (idx + len > m_size)
1546 throw std::out_of_range(
"OUT_OF_RANGE_ERROR: int_vector::get_int(size_type, uint8_t); idx+len > size()!");
1548 if (len > 64) {
throw std::out_of_range(
"OUT_OF_RANGE_ERROR: int_vector::get_int(size_type, uint8_t); len>64!"); }
1553 template <u
int8_t t_w
idth>
1557 if (idx + len > m_size)
1559 throw std::out_of_range(
"OUT_OF_RANGE_ERROR: int_vector::set_int(size_type, uint8_t); idx+len > size()!");
1561 if (len > 64) {
throw std::out_of_range(
"OUT_OF_RANGE_ERROR: int_vector::set_int(size_type, uint8_t); len>64!"); }
1566 template <u
int8_t t_w
idth>
1569 return m_size / m_width;
1607 template <u
int8_t t_w
idth>
1610 return m_capacity / m_width;
1617 return m_capacity >> 6;
1624 return m_capacity >> 5;
1631 return m_capacity >> 4;
1638 return m_capacity >> 3;
1648 template <u
int8_t t_w
idth>
1651 assert(idx < this->
size());
1653 return reference(this->m_data + (i >> 6), i & 0x3F, m_width);
1660 assert(idx < this->
size());
1661 return *(this->m_data + idx);
1668 assert(idx < this->
size());
1669 return *(((uint32_t *)(this->m_data)) + idx);
1676 assert(idx < this->
size());
1677 return *(((uint16_t *)(this->m_data)) + idx);
1684 assert(idx < this->
size());
1685 return *(((uint8_t *)(this->m_data)) + idx);
1688 template <u
int8_t t_w
idth>
1691 assert(idx < this->
size());
1692 return get_int(idx * t_width, t_width);
1698 assert(idx < this->
size());
1699 return get_int(idx * m_width, m_width);
1705 assert(idx < this->
size());
1706 return *(this->m_data + idx);
1712 assert(idx < this->
size());
1713 return *(((uint32_t *)this->m_data) + idx);
1719 assert(idx < this->
size());
1720 return *(((uint16_t *)this->m_data) + idx);
1726 assert(idx < this->
size());
1727 return *(((uint8_t *)this->m_data) + idx);
1733 assert(idx < this->
size());
1734 return ((*(m_data + (idx >> 6))) >> (idx & 0x3F)) & 1;
1737 template <u
int8_t t_w
idth>
1741 if (min_size > v.size()) min_size = v.size();
1742 for (
auto it = begin(), end = begin() + min_size, it_v = v.begin(); it != end; ++it, ++it_v)
1752 template <u
int8_t t_w
idth>
1756 if (min_size > v.size()) min_size = v.size();
1757 for (
auto it = begin(), end = begin() + min_size, it_v = v.begin(); it != end; ++it, ++it_v)
1767 template <u
int8_t t_w
idth>
1770 return *
this == v or *
this < v;
1773 template <u
int8_t t_w
idth>
1776 return *
this == v or *
this > v;
1779 template <u
int8_t t_w
idth>
1782 assert(v.
bit_size() == bit_size());
1783 for (uint64_t i = 0; i < bit_data_size(); ++i) m_data[i] &= v.m_data[i];
1787 template <u
int8_t t_w
idth>
1790 assert(bit_size() == v.
bit_size());
1791 for (uint64_t i = 0; i < bit_data_size(); ++i) m_data[i] |= v.m_data[i];
1795 template <u
int8_t t_w
idth>
1798 assert(bit_size() == v.
bit_size());
1799 for (uint64_t i = 0; i < bit_data_size(); ++i) m_data[i] ^= v.m_data[i];
1803 template <u
int8_t t_w
idth>
1807 uint64_t * p = m_data;
1816 out.write((
char *)p, (bit_data_size() - idx) *
sizeof(uint64_t));
1817 written_bytes += (bit_data_size() - idx) *
sizeof(uint64_t);
1818 return written_bytes;
1821 template <u
int8_t t_w
idth>
1824 std::string name)
const
1826 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*
this));
1828 written_bytes += write_data(out);
1829 structure_tree::add_size(child, written_bytes);
1830 return written_bytes;
1833 template <u
int8_t t_w
idth>
1840 uint64_t * p = m_data;
1848 in.read((
char *)p, (bit_data_size() - idx) *
sizeof(uint64_t));
1851 template <u
int8_t t_w
idth>
1852 template <
typename archive_t>
1853 inline typename std::enable_if<cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
1864 template <u
int8_t t_w
idth>
1865 template <
typename archive_t>
1866 inline typename std::enable_if<!cereal::traits::is_output_serializable<cereal::BinaryData<int_vector<t_width>>,
1874 for (value_type
const & v : *
this) ar(v);
1877 template <u
int8_t t_w
idth>
1878 template <
typename archive_t>
1879 inline typename std::enable_if<cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
1891 template <u
int8_t t_w
idth>
1892 template <
typename archive_t>
1893 inline typename std::enable_if<!cereal::traits::is_input_serializable<cereal::BinaryData<int_vector<t_width>>,
1904 for (
size_t i = 0; i <
size(); ++i)
1908 operator[](i) = tmp;
bits.hpp contains the sdsl::bits class.
#define CEREAL_LOAD_FUNCTION_NAME
#define CEREAL_SAVE_FUNCTION_NAME
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
t_int_vector::size_type size_type
const_iterator operator-(difference_type i) const
const_iterator operator--(int)
Postfix decrement of the Iterator.
bool operator!=(const int_vector_const_iterator &it) const noexcept
int_vector_const_iterator const_iterator
const_iterator operator+(difference_type i) const
int_vector_const_iterator(const int_vector_iterator< t_int_vector > &it)
const_reference operator[](difference_type i) const
const t_int_vector::value_type * pointer
bool operator>(const int_vector_const_iterator &it) const noexcept
bool operator>=(const int_vector_const_iterator &it) const noexcept
bool operator<=(const int_vector_const_iterator &it) const noexcept
const_iterator & operator--()
Prefix decrement of the Iterator.
const_reference operator*() const
const_iterator & operator++()
Prefix increment of the Iterator.
t_int_vector::value_type const_reference
bool operator<(const int_vector_const_iterator &it) const noexcept
friend int_vector_const_iterator< X >::difference_type operator-(const int_vector_const_iterator< X > &x, const int_vector_const_iterator< X > &y)
const_iterator & operator+=(difference_type i)
int_vector_const_iterator(const t_int_vector *v=nullptr, size_type idx=0)
bool operator==(const int_vector_const_iterator &it) const noexcept
const_iterator & operator-=(difference_type i)
const_iterator operator++(int)
Postfix increment of the Iterator.
int_vector_iterator_base(const t_int_vector *v=nullptr, size_type idx=0)
int_vector_iterator_base(uint8_t offset, uint8_t len)
int_vector_iterator iterator
iterator & operator--()
Prefix decrement of the Iterator.
reference operator*() const
iterator & operator+=(difference_type i)
iterator operator++(int)
Postfix increment of the Iterator.
bool operator<(const int_vector_iterator &it) const noexcept
bool operator==(const int_vector_iterator &it) const noexcept
reference operator[](difference_type i) const
int_vector_iterator(const int_vector_iterator< t_int_vector > &it)
t_int_vector::difference_type difference_type
bool operator!=(const int_vector_iterator &it) const noexcept
bool operator<=(const int_vector_iterator &it) const noexcept
t_int_vector::size_type size_type
iterator operator+(difference_type i) const
iterator & operator=(const int_vector_iterator< t_int_vector > &it)
iterator operator-(difference_type i) const
iterator & operator++()
Prefix increment of the Iterator.
bool operator>=(const int_vector_iterator &it) const noexcept
iterator operator--(int)
Postfix decrement of the Iterator.
int_vector_iterator(t_int_vector *v=nullptr, size_type idx=0)
iterator & operator-=(difference_type i)
difference_type operator-(const int_vector_iterator &it) const noexcept
bool operator>(const int_vector_iterator &it) const noexcept
int_vector_reference< t_int_vector > reference
bool operator<(const int_vector_reference &x) const noexcept
int_vector_reference()=delete
Default constructor explicitly deleted.
constexpr int_vector_reference(int_vector_reference &&) noexcept=default
int_vector_reference & operator=(const int_vector_reference &x) noexcept
constexpr int_vector_reference(int_vector_reference const &) noexcept=default
Copy and move explicitly defaulted.
int_vector_reference & operator=(int_vector_reference &&x) noexcept
bool operator==(const int_vector_reference &x) const noexcept
int_vector_reference & operator=(bool x) noexcept
Assignment operator for the proxy class.
A proxy class that acts as a reference to an integer of length len bits in a int_vector.
int_vector_reference & operator--() noexcept
Prefix decrement of the proxy object.
t_int_vector::value_type value_type
bool operator<(const int_vector_reference &x) const noexcept
int_vector_reference & operator=(int_vector_reference &&x) noexcept
int_vector_reference & operator=(value_type x) noexcept
Assignment operator for the proxy class.
value_type operator++(int) noexcept
Postfix increment of the proxy object.
int_vector_reference & operator++() noexcept
Prefix increment of the proxy object.
int_vector_reference & operator=(const int_vector_reference &x) noexcept
int_vector_reference()=delete
Default constructor explicitly deleted.
int_vector_reference & operator+=(const value_type x) noexcept
Add assign from the proxy object.
value_type operator--(int) noexcept
Postfix decrement 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.
bool operator==(const int_vector_reference &x) const noexcept
int_vector_reference & operator-=(const value_type x) noexcept
Subtract assign from the proxy object.
A generic vector class for integers of width .
iterator end() noexcept
Iterator that points to the element after the last element of int_vector.
void flip()
Flip all bits of bit_vector.
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.
reference operator[](const size_type &i) noexcept
non const version of [] operator
rank_support_v< 1, 1 > rank_1_type
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.
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.
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 value_type * const_pointer
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.
std::enable_if< std::is_base_of< std::input_iterator_tag, typename std::iterator_traits< input_iterator_t >::iterator_category >::value, iterator >::type insert(const_iterator it, input_iterator_t first, input_iterator_t last)
Insert elements from an iterator pair before the element that the iterator it is pointing to.
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
ptrdiff_t difference_type
bool operator>(const int_vector &v) const noexcept
Greater operator for two int_vectors.
select_support_mcl< 0, 1 > select_0_type
std::enable_if< cereal::traits::is_output_serializable< cereal::BinaryData< int_vector< t_width > >, archive_t >::value, void >::type CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal if archive is binary.
void width(uint8_t new_width) noexcept
Sets the width of the integers which are accessed via the [] operator, if t_width equals 0.
bool operator>=(const int_vector &v) const noexcept
Greater of equal operator.
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
reference at(const size_type &i)
non const version of at() function
friend bool operator==(const int_vector< t_width > &lhs, const container &rhs) noexcept
Equality operator for an arbitrary container.
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.
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.
iterator emplace(const_iterator it, Args &&... args)
Insert an element constructed with std::forward<Args>(args) before the element that the iterator is p...
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.
bool operator!=(const int_vector< t_width2 > &v) const noexcept
Inequality operator for two int_vectors.
void clear() noexcept
Clearing the int_vector. Allocated memory will not be released.
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
const_iterator begin() const noexcept
Const iterator that points to the first element of the int_vector.
reference back() noexcept
Returns last element.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
int_vector & operator=(int_vector &&v)
Move assignment operator.
int_vector_trait< t_width >::const_iterator const_iterator
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.
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.
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.
const_reference at(const size_type &i) const
const version of at() function
int_vector & operator^=(const int_vector &v)
bitwise-xor-update operator
uint64_t * data() noexcept
Pointer to the raw data of the int_vector.
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.
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.
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.
bool operator==(const int_vector< t_width > &v) const noexcept
Equality operator for two int_vectors.
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.
int_vector(int_vector &&v)
Move constructor.
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.
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.
std::enable_if< cereal::traits::is_input_serializable< cereal::BinaryData< int_vector< t_width > >, archive_t >::value, void >::type CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (save) via cereal if archive is binary.
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
static void resize(t_vec &v, const typename t_vec::size_type capacity)
static void clear(t_vec &v)
A rank structure proposed by Sebastiano Vigna.
The base class of classes supporting rank_queries for a sdsl::bit_vector in constant time.
A class supporting constant time select queries.
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
memory_management.hpp contains two function for allocating and deallocating memory
void make_nvp(t1 const &, t2 const &)
void make_size_tag(t const &)
t1 binary_data(t1 const &, t2 const &)
const uint64_t SDSL_BLOCK_SIZE
int_vector ::size_type size_type
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Namespace for the succinct data structure library.
int_vector_const_iterator< t_int_vector >::difference_type operator-(const int_vector_const_iterator< t_int_vector > &x, const int_vector_const_iterator< t_int_vector > &y)
std::ostream & operator<<(std::ostream &os, const bp_interval< t_int > &interval)
std::enable_if< has_serialize< X >::value, typename X::size_type >::type serialize(const X &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
uint64_t std_size_type_for_int_vector
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
void swap(int_vector< t_width > &v1, int_vector< t_width > &v2) noexcept
uint64_t int_vector_size_type
int_vector ::size_type size(const range_type &r)
Size of a range.
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)
sfstream.hpp contains a two stream class which can be used to read/write from/to files or strings.
static SDSL_CONSTEXPR uint64_t read_int(const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
Reads a value from a bit position in an array.
static SDSL_CONSTEXPR void write_int(uint64_t *word, uint64_t x, const uint8_t offset=0, const uint8_t len=64)
Writes value x to an bit position in an array.
constexpr static uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
raw_wrapper(const int_vector &_vec)
static iterator end(int_vector_type *, uint64_t *begin, int_vector_size_type size) noexcept
static iterator begin(int_vector_type *, uint64_t *begin) noexcept
int_vector< 16 > int_vector_type
static const_iterator begin(const int_vector_type *, const uint64_t *begin) noexcept
static void set_width(uint8_t, int_width_type) noexcept
static const_iterator end(const int_vector_type *, const uint64_t *begin, int_vector_size_type size) noexcept
const uint16_t * const_iterator
const uint32_t * const_iterator
static iterator begin(int_vector_type *, uint64_t *begin) noexcept
static const_iterator end(const int_vector_type *, const uint64_t *begin, int_vector_size_type size) noexcept
static const_iterator begin(const int_vector_type *, const uint64_t *begin) noexcept
static void set_width(uint8_t, int_width_type) noexcept
static iterator end(int_vector_type *, uint64_t *begin, int_vector_size_type size) noexcept
int_vector< 32 > int_vector_type
const uint64_t * const_iterator
static const_iterator begin(const int_vector_type *, const uint64_t *begin) noexcept
static iterator end(int_vector_type *, uint64_t *begin, int_vector_size_type size) noexcept
static const_iterator end(const int_vector_type *, const uint64_t *begin, int_vector_size_type size) noexcept
static iterator begin(int_vector_type *, uint64_t *begin) noexcept
int_vector< 64 > int_vector_type
static void set_width(uint8_t, int_width_type) noexcept
static const_iterator end(const int_vector_type *, const uint64_t *begin, int_vector_size_type size) noexcept
int_vector< 8 > int_vector_type
static const_iterator begin(const int_vector_type *, const uint64_t *begin) noexcept
const uint8_t * const_iterator
static iterator begin(int_vector_type *, uint64_t *begin) noexcept
static void set_width(uint8_t, int_width_type) noexcept
static iterator end(int_vector_type *, uint64_t *begin, int_vector_size_type size) noexcept
int_vector_const_iterator< int_vector_type > const_iterator
int_vector< t_width > int_vector_type
static const_iterator begin(const int_vector_type *v, const uint64_t *) noexcept
static void set_width(uint8_t new_width, int_width_type &width) noexcept
int_vector_reference< int_vector_type > reference
static iterator end(int_vector_type *v, uint64_t *, int_vector_size_type) noexcept
static const_iterator end(const int_vector_type *v, const uint64_t *, int_vector_size_type) noexcept
static iterator begin(int_vector_type *v, uint64_t *) noexcept
int_vector_iterator< int_vector_type > iterator
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.