SDSL 3.0.1
Succinct Data Structure Library
select_support.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_SELECT_SUPPORT
9#define INCLUDED_SDSL_SELECT_SUPPORT
10
15#include <sdsl/int_vector.hpp>
16#include <sdsl/rank_support.hpp>
17
19namespace sdsl
20{
22
25{
26 protected:
28 public:
30 const bit_vector * vv;
31
33
35 select_support(const int_vector<1> * f_v = nullptr)
36 : vv(f_v)
37 {
38 m_v = f_v;
39 }
41
46 virtual ~select_support(){};
47
49
54 virtual size_type select(size_type i) const = 0;
55
57 virtual size_type operator()(size_type i) const = 0;
59 virtual size_type serialize(std::ostream & out, structure_tree_node * v, std::string name) const = 0;
61
66 virtual void load(std::istream & in, const int_vector<1> * v = nullptr) = 0;
67
69 virtual void set_vector(const int_vector<1> * v = nullptr) = 0;
70};
71
72template <uint8_t bit_pattern, uint8_t pattern_len>
74{
76
77 /* Count the number of arguments for the specific select support */
78 static size_type arg_cnt(const bit_vector &) { return 0; }
79
80 static size_type args_in_the_first_word(uint64_t, uint8_t, uint64_t) { return 0; }
81
82 static size_type ith_arg_pos_in_the_first_word(uint64_t, size_type, uint8_t, uint64_t) { return 0; }
83
84 static size_type args_in_the_word(uint64_t, uint64_t &) { return 0; }
85
86 static size_type ith_arg_pos_in_the_word(uint64_t, size_type, uint64_t) { return 0; }
87
88 static bool found_arg(size_type, const bit_vector &) { return 0; }
89
90 static uint64_t init_carry(const uint64_t *, size_type) { return 0; }
91
92 static uint64_t get_carry(uint64_t) { return 0; }
93};
94
95template <>
97{
99
100 static size_type arg_cnt(const bit_vector & v) { return v.bit_size() - util::cnt_one_bits(v); }
101 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t)
102 {
103 return bits::cnt((~w) & bits::lo_unset[offset]);
104 }
105 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t)
106 {
107 return bits::sel(~w & bits::lo_unset[offset], (uint32_t)i);
108 }
109 static size_type args_in_the_word(uint64_t w, uint64_t &) { return bits::cnt(~w); }
110 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t) { return bits::sel(~w, (uint32_t)i); }
111 static bool found_arg(size_type i, const bit_vector & v) { return !v[i]; }
112 static uint64_t init_carry(const uint64_t *, size_type) { return 0; }
113 static uint64_t get_carry(uint64_t) { return 0; }
114};
115
116template <>
118{
120
121 static size_type arg_cnt(const bit_vector & v) { return util::cnt_one_bits(v); }
122 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t)
123 {
124 return bits::cnt(w & bits::lo_unset[offset]);
125 }
126 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t)
127 {
128 return bits::sel(w & bits::lo_unset[offset], (uint32_t)i);
129 }
130 static size_type args_in_the_word(uint64_t w, uint64_t &) { return bits::cnt(w); }
131 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t) { return bits::sel(w, (uint32_t)i); }
132 static bool found_arg(size_type i, const bit_vector & v) { return v[i] == 1; }
133 static uint64_t init_carry(const uint64_t *, size_type) { return 0; }
134 static uint64_t get_carry(uint64_t) { return 0; }
135};
136
137template <>
139{
141
142 static size_type arg_cnt(const bit_vector & v) { return util::cnt_onezero_bits(v); }
143 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
144 {
145 return bits::cnt(bits::map10(w, carry) & bits::lo_unset[offset]);
146 }
147 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
148 {
149 return bits::sel(bits::map10(w, carry) & bits::lo_unset[offset], (uint32_t)i);
150 }
151 static size_type args_in_the_word(uint64_t w, uint64_t & carry) { return bits::cnt10(w, carry); }
152 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
153 {
154 return bits::sel(bits::map10(w, carry), (uint32_t)i);
155 }
156 static bool found_arg(size_type i, const bit_vector & v)
157 {
158 if (i > 0 and v[i - 1] and !v[i]) return true;
159 return false;
160 }
161 static uint64_t init_carry(const uint64_t * data, size_type word_pos) { return word_pos ? (*(data - 1) >> 63) : 0; }
162 static uint64_t get_carry(uint64_t w) { return w >> 63; }
163};
164
165template <>
167{
169
170 static size_type arg_cnt(const bit_vector & v) { return util::cnt_zeroone_bits(v); }
171 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
172 {
173 return bits::cnt(bits::map01(w, carry) & bits::lo_unset[offset]);
174 }
175 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
176 {
177 return bits::sel(bits::map01(w, carry) & bits::lo_unset[offset], (uint32_t)i);
178 }
179 static size_type args_in_the_word(uint64_t w, uint64_t & carry) { return bits::cnt01(w, carry); }
180 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
181 {
182 return bits::sel(bits::map01(w, carry), (uint32_t)i);
183 }
184 static bool found_arg(size_type i, const bit_vector & v)
185 {
186 if (i > 0 and !v[i - 1] and v[i]) return true;
187 return false;
188 }
189 static uint64_t init_carry(const uint64_t * data, size_type word_pos) { return word_pos ? (*(data - 1) >> 63) : 1; }
190 static uint64_t get_carry(uint64_t w) { return w >> 63; }
191};
192
193template <>
195{
197
198 static size_type arg_cnt(const bit_vector & v)
199 {
200 const uint64_t * data = v.data();
201 if (v.empty()) return 0;
202 uint64_t carry = rank_support_trait<00, 2>::init_carry();
203 size_type result = 0;
204 for (auto end = v.data() + (v.size() >> 6); data < end; ++data)
205 {
206 result += rank_support_trait<00, 2>::args_in_the_word(*data, carry);
207 }
208 if (v.bit_size() & 0x3F)
209 { // if bit_size is not a multiple of 64, add count of the last word
210 result += rank_support_trait<00, 2>::args_in_the_word((*data) | bits::lo_unset[v.bit_size() & 0x3F], carry);
211 }
212 return result;
213 }
214
215 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
216 {
217 size_type res = 0;
218 if (offset == 0)
220 else
221 {
222 res = bits::cnt((~(w | (w << 1))) & bits::lo_unset[offset]);
223 }
224 return res;
225 }
226
227 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
228 {
229 return bits::sel((~(((w << 1) | carry) | w)) & bits::lo_unset[offset], i);
230 }
231 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
232 {
234 }
235 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
236 {
237 return bits::sel(~(((w << 1) | carry) | w), i);
238 }
239 static bool found_arg(size_type i, const bit_vector & v) { return i > 0 and !v[i - 1] and !v[i]; }
240 static uint64_t init_carry(const uint64_t * data, size_type word_pos) { return word_pos ? (*(data - 1) >> 63) : 1; }
241 static uint64_t get_carry(uint64_t w) { return w >> 63; }
242};
243
244template <>
246{
248
249 static size_type arg_cnt(const bit_vector & v)
250 {
251 const uint64_t * data = v.data();
252 if (v.empty()) return 0;
253 uint64_t carry = rank_support_trait<11, 2>::init_carry();
254 size_type result = 0;
255 for (auto end = v.data() + (v.size() >> 6); data < end; ++data)
256 {
257 result += rank_support_trait<11, 2>::args_in_the_word(*data, carry);
258 }
259 if (v.bit_size() & 0x3F)
260 { // if bit_size is not a multiple of 64, add count of the last word
261 result += rank_support_trait<11, 2>::args_in_the_word((*data) & bits::lo_set[v.bit_size() & 0x3F], carry);
262 }
263 return result;
264 }
265
266 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
267 {
268 size_type res = 0;
269 if (offset == 0)
271 else
272 {
273 res = bits::cnt((w >> (offset - 1)) & (w >> offset));
274 }
275 return res;
276 }
277
278 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
279 {
280 return bits::sel((((w << 1) | carry) & w) & bits::lo_unset[offset], i);
281 }
282 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
283 {
285 }
286 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
287 {
288 return bits::sel(((w << 1) | carry) & w, i);
289 }
290 static bool found_arg(size_type i, const bit_vector & v)
291 {
292 if (i > 0 and v[i - 1] and v[i]) return true;
293 return false;
294 }
295 static uint64_t init_carry(const uint64_t * data, size_type word_pos) { return word_pos ? (*(data - 1) >> 63) : 0; }
296 static uint64_t get_carry(uint64_t w) { return w >> 63; }
297};
298
299} // end namespace sdsl
300
303
304#endif
bool empty() const noexcept
Equivalent to size() == 0.
Definition: int_vector.hpp:500
size_type bit_size() const noexcept
The number of bits in the int_vector.
Definition: int_vector.hpp:547
size_type size() const noexcept
The number of elements in the int_vector.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:566
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
select_support(const select_support &f_v)
Copy constructor.
const int_vector< 1 > * m_v
Pointer to the select supported sdsl::bit_vector.
const bit_vector * vv
virtual size_type operator()(size_type i) const =0
Alias for select.
virtual size_type select(size_type i) const =0
Select returns the index of the i-th 1-bit in the supported bit_vector.
virtual void load(std::istream &in, const int_vector< 1 > *v=nullptr)=0
Load the select_support from an in file stream.
int_vector< 1 >::size_type size_type
virtual size_type serialize(std::ostream &out, structure_tree_node *v, std::string name) const =0
Serialize the select_support to an out file stream.
virtual ~select_support()
Destructor of select_support.
select_support(const int_vector< 1 > *f_v=nullptr)
Constructor of select_support.
virtual void set_vector(const int_vector< 1 > *v=nullptr)=0
This method sets the supported bit_vector.
int_vector.hpp contains the sdsl::int_vector class.
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_onezero_bits(const t_int_vec &v)
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_zeroone_bits(const t_int_vec &v)
Number of set bits in v t_int_vec::size_type cnt_one_bits(const t_int_vec &v)
Namespace for the succinct data structure library.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
select_support_scan.hpp contains classes that support a sdsl::bit_vector with linear time select.
static constexpr uint32_t sel(uint64_t x, uint32_t i)
Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.
Definition: bits.hpp:584
static constexpr uint64_t lo_unset[65]
lo_unset[i] is a 64-bit word with the i least significant bits not set and the high bits set.
Definition: bits.hpp:210
static constexpr uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
Definition: bits.hpp:570
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:484
static constexpr uint64_t map01(uint64_t x, uint64_t c=1)
Map all 01 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
Definition: bits.hpp:578
static constexpr uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
Definition: bits.hpp:556
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
static constexpr uint64_t map10(uint64_t x, uint64_t c=0)
Map all 10 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
Definition: bits.hpp:564
static uint64_t init_carry()
static size_type args_in_the_word(uint64_t, uint64_t &)
static bool found_arg(size_type i, const bit_vector &v)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
select_support::size_type size_type
static size_type arg_cnt(const bit_vector &v)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static uint64_t init_carry(const uint64_t *data, size_type word_pos)
static uint64_t get_carry(uint64_t w)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
static bool found_arg(size_type i, const bit_vector &v)
select_support::size_type size_type
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint64_t init_carry(const uint64_t *data, size_type word_pos)
static size_type arg_cnt(const bit_vector &v)
static uint64_t get_carry(uint64_t w)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t)
static bool found_arg(size_type i, const bit_vector &v)
select_support::size_type size_type
static size_type arg_cnt(const bit_vector &v)
static uint64_t get_carry(uint64_t)
static uint64_t init_carry(const uint64_t *, size_type)
static size_type args_in_the_word(uint64_t w, uint64_t &)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
static size_type arg_cnt(const bit_vector &v)
select_support::size_type size_type
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static bool found_arg(size_type i, const bit_vector &v)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint64_t init_carry(const uint64_t *data, size_type word_pos)
static uint64_t get_carry(uint64_t w)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static uint64_t init_carry(const uint64_t *data, size_type word_pos)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint64_t get_carry(uint64_t w)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
select_support::size_type size_type
static size_type arg_cnt(const bit_vector &v)
static bool found_arg(size_type i, const bit_vector &v)
static size_type arg_cnt(const bit_vector &v)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t)
static bool found_arg(size_type i, const bit_vector &v)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t)
select_support::size_type size_type
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t)
static uint64_t init_carry(const uint64_t *, size_type)
static uint64_t get_carry(uint64_t)
static size_type args_in_the_word(uint64_t w, uint64_t &)
static uint64_t get_carry(uint64_t)
static size_type ith_arg_pos_in_the_word(uint64_t, size_type, uint64_t)
static size_type args_in_the_word(uint64_t, uint64_t &)
static uint64_t init_carry(const uint64_t *, size_type)
static bool found_arg(size_type, const bit_vector &)
select_support::size_type size_type
static size_type arg_cnt(const bit_vector &)
static size_type ith_arg_pos_in_the_first_word(uint64_t, size_type, uint8_t, uint64_t)
static size_type args_in_the_first_word(uint64_t, uint8_t, uint64_t)