SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <iosfwd>
16#include <stdint.h>
17#include <string>
18
19#include <sdsl/bits.hpp>
20#include <sdsl/int_vector.hpp>
21#include <sdsl/rank_support.hpp>
22#include <sdsl/util.hpp>
23
25namespace sdsl
26{
27class structure_tree_node;
28
30
33{
34protected:
36
37public:
39 bit_vector const * vv;
40
42
44 select_support(int_vector<1> const * f_v = nullptr) : vv(f_v)
45 {
46 m_v = f_v;
47 }
49
54 virtual ~select_support(){};
55
57
62 virtual size_type select(size_type i) const = 0;
63
65 virtual size_type operator()(size_type i) const = 0;
67 virtual size_type serialize(std::ostream & out, structure_tree_node * v, std::string name) const = 0;
69
74 virtual void load(std::istream & in, int_vector<1> const * v = nullptr) = 0;
75
77 virtual void set_vector(int_vector<1> const * v = nullptr) = 0;
78};
79
80template <uint8_t bit_pattern, uint8_t pattern_len>
82{
84
85 /* Count the number of arguments for the specific select support */
87 {
88 return 0;
89 }
90
91 static size_type args_in_the_first_word(uint64_t, uint8_t, uint64_t)
92 {
93 return 0;
94 }
95
96 static size_type ith_arg_pos_in_the_first_word(uint64_t, size_type, uint8_t, uint64_t)
97 {
98 return 0;
99 }
100
101 static size_type args_in_the_word(uint64_t, uint64_t &)
102 {
103 return 0;
104 }
105
106 static size_type ith_arg_pos_in_the_word(uint64_t, size_type, uint64_t)
107 {
108 return 0;
109 }
110
111 static bool found_arg(size_type, bit_vector const &)
112 {
113 return 0;
114 }
115
116 static uint64_t init_carry(uint64_t const *, size_type)
117 {
118 return 0;
119 }
120
121 static uint64_t get_carry(uint64_t)
122 {
123 return 0;
124 }
125};
126
127template <>
129{
131
132 static size_type arg_cnt(bit_vector const & v)
133 {
134 return v.bit_size() - util::cnt_one_bits(v);
135 }
136 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t)
137 {
138 return bits::cnt((~w) & bits::lo_unset[offset]);
139 }
140 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t)
141 {
142 return bits::sel(~w & bits::lo_unset[offset], (uint32_t)i);
143 }
144 static size_type args_in_the_word(uint64_t w, uint64_t &)
145 {
146 return bits::cnt(~w);
147 }
148 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t)
149 {
150 return bits::sel(~w, (uint32_t)i);
151 }
152 static bool found_arg(size_type i, bit_vector const & v)
153 {
154 return !v[i];
155 }
156 static uint64_t init_carry(uint64_t const *, size_type)
157 {
158 return 0;
159 }
160 static uint64_t get_carry(uint64_t)
161 {
162 return 0;
163 }
164};
165
166template <>
168{
170
171 static size_type arg_cnt(bit_vector const & v)
172 {
173 return util::cnt_one_bits(v);
174 }
175 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t)
176 {
177 return bits::cnt(w & bits::lo_unset[offset]);
178 }
179 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t)
180 {
181 return bits::sel(w & bits::lo_unset[offset], (uint32_t)i);
182 }
183 static size_type args_in_the_word(uint64_t w, uint64_t &)
184 {
185 return bits::cnt(w);
186 }
187 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t)
188 {
189 return bits::sel(w, (uint32_t)i);
190 }
191 static bool found_arg(size_type i, bit_vector const & v)
192 {
193 return v[i] == 1;
194 }
195 static uint64_t init_carry(uint64_t const *, size_type)
196 {
197 return 0;
198 }
199 static uint64_t get_carry(uint64_t)
200 {
201 return 0;
202 }
203};
204
205template <>
207{
209
210 static size_type arg_cnt(bit_vector const & v)
211 {
212 return util::cnt_onezero_bits(v);
213 }
214 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
215 {
216 return bits::cnt(bits::map10(w, carry) & bits::lo_unset[offset]);
217 }
218 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
219 {
220 return bits::sel(bits::map10(w, carry) & bits::lo_unset[offset], (uint32_t)i);
221 }
222 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
223 {
224 return bits::cnt10(w, carry);
225 }
226 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
227 {
228 return bits::sel(bits::map10(w, carry), (uint32_t)i);
229 }
230 static bool found_arg(size_type i, bit_vector const & v)
231 {
232 if (i > 0 and v[i - 1] and !v[i])
233 return true;
234 return false;
235 }
236 static uint64_t init_carry(uint64_t const * data, size_type word_pos)
237 {
238 return word_pos ? (*(data - 1) >> 63) : 0;
239 }
240 static uint64_t get_carry(uint64_t w)
241 {
242 return w >> 63;
243 }
244};
245
246template <>
248{
250
251 static size_type arg_cnt(bit_vector const & v)
252 {
253 return util::cnt_zeroone_bits(v);
254 }
255 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
256 {
257 return bits::cnt(bits::map01(w, carry) & bits::lo_unset[offset]);
258 }
259 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
260 {
261 return bits::sel(bits::map01(w, carry) & bits::lo_unset[offset], (uint32_t)i);
262 }
263 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
264 {
265 return bits::cnt01(w, carry);
266 }
267 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
268 {
269 return bits::sel(bits::map01(w, carry), (uint32_t)i);
270 }
271 static bool found_arg(size_type i, bit_vector const & v)
272 {
273 if (i > 0 and !v[i - 1] and v[i])
274 return true;
275 return false;
276 }
277 static uint64_t init_carry(uint64_t const * data, size_type word_pos)
278 {
279 return word_pos ? (*(data - 1) >> 63) : 1;
280 }
281 static uint64_t get_carry(uint64_t w)
282 {
283 return w >> 63;
284 }
285};
286
287template <>
289{
291
292 static size_type arg_cnt(bit_vector const & v)
293 {
294 uint64_t const * data = v.data();
295 if (v.empty())
296 return 0;
297 uint64_t carry = rank_support_trait<00, 2>::init_carry();
298 size_type result = 0;
299 for (auto end = v.data() + (v.size() >> 6); data < end; ++data)
300 {
301 result += rank_support_trait<00, 2>::args_in_the_word(*data, carry);
302 }
303 if (v.bit_size() & 0x3F)
304 { // if bit_size is not a multiple of 64, add count of the last word
305 result += rank_support_trait<00, 2>::args_in_the_word((*data) | bits::lo_unset[v.bit_size() & 0x3F], carry);
306 }
307 return result;
308 }
309
310 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
311 {
312 size_type res = 0;
313 if (offset == 0)
315 else
316 {
317 res = bits::cnt((~(w | (w << 1))) & bits::lo_unset[offset]);
318 }
319 return res;
320 }
321
322 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
323 {
324 return bits::sel((~(((w << 1) | carry) | w)) & bits::lo_unset[offset], i);
325 }
326 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
327 {
329 }
330 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
331 {
332 return bits::sel(~(((w << 1) | carry) | w), i);
333 }
334 static bool found_arg(size_type i, bit_vector const & v)
335 {
336 return i > 0 and !v[i - 1] and !v[i];
337 }
338 static uint64_t init_carry(uint64_t const * data, size_type word_pos)
339 {
340 return word_pos ? (*(data - 1) >> 63) : 1;
341 }
342 static uint64_t get_carry(uint64_t w)
343 {
344 return w >> 63;
345 }
346};
347
348template <>
350{
352
353 static size_type arg_cnt(bit_vector const & v)
354 {
355 uint64_t const * data = v.data();
356 if (v.empty())
357 return 0;
358 uint64_t carry = rank_support_trait<11, 2>::init_carry();
359 size_type result = 0;
360 for (auto end = v.data() + (v.size() >> 6); data < end; ++data)
361 {
362 result += rank_support_trait<11, 2>::args_in_the_word(*data, carry);
363 }
364 if (v.bit_size() & 0x3F)
365 { // if bit_size is not a multiple of 64, add count of the last word
366 result += rank_support_trait<11, 2>::args_in_the_word((*data) & bits::lo_set[v.bit_size() & 0x3F], carry);
367 }
368 return result;
369 }
370
371 static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
372 {
373 size_type res = 0;
374 if (offset == 0)
376 else
377 {
378 res = bits::cnt((w >> (offset - 1)) & (w >> offset));
379 }
380 return res;
381 }
382
383 static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
384 {
385 return bits::sel((((w << 1) | carry) & w) & bits::lo_unset[offset], i);
386 }
387 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
388 {
390 }
391 static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
392 {
393 return bits::sel(((w << 1) | carry) & w, i);
394 }
395 static bool found_arg(size_type i, bit_vector const & v)
396 {
397 if (i > 0 and v[i - 1] and v[i])
398 return true;
399 return false;
400 }
401 static uint64_t init_carry(uint64_t const * data, size_type word_pos)
402 {
403 return word_pos ? (*(data - 1) >> 63) : 0;
404 }
405 static uint64_t get_carry(uint64_t w)
406 {
407 return w >> 63;
408 }
409};
410
411} // end namespace sdsl
412
413#endif
bits.hpp contains the sdsl::bits class.
A generic vector class for integers of width .
Definition io.hpp:36
int_vector_size_type size_type
bool empty() const noexcept
Equivalent to size() == 0.
size_type size() const noexcept
The number of elements in the int_vector.
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
size_type bit_size() const noexcept
The number of bits in the int_vector.
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
bit_vector const * vv
int_vector< 1 > const * m_v
Pointer to the select supported sdsl::bit_vector.
virtual void load(std::istream &in, int_vector< 1 > const *v=nullptr)=0
Load the select_support from an in file stream.
virtual void set_vector(int_vector< 1 > const *v=nullptr)=0
This method sets the supported bit_vector.
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.
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.
select_support(int_vector< 1 > const *f_v=nullptr)
Constructor of select_support.
select_support(select_support const &f_v)
Copy constructor.
virtual ~select_support()
Destructor of select_support.
int_vector.hpp contains the sdsl::int_vector class.
Number of set bits in v t_int_vec::size_type cnt_one_bits(t_int_vec const &v)
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_zeroone_bits(t_int_vec const &v)
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_onezero_bits(t_int_vec const &v)
Namespace for the succinct data structure library.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
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:586
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:216
static constexpr uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
Definition bits.hpp:572
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition bits.hpp:486
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:580
static constexpr uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
Definition bits.hpp:558
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition bits.hpp:194
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:566
static uint64_t init_carry()
static size_type args_in_the_word(uint64_t, uint64_t &)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
static uint64_t init_carry(uint64_t const *data, size_type word_pos)
select_support::size_type size_type
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 arg_cnt(bit_vector const &v)
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 get_carry(uint64_t w)
static bool found_arg(size_type i, bit_vector const &v)
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, bit_vector const &v)
static size_type arg_cnt(bit_vector const &v)
select_support::size_type size_type
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint64_t get_carry(uint64_t w)
static uint64_t init_carry(uint64_t const *data, size_type word_pos)
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)
select_support::size_type size_type
static uint64_t init_carry(uint64_t const *, size_type)
static uint64_t get_carry(uint64_t)
static size_type arg_cnt(bit_vector const &v)
static bool found_arg(size_type i, bit_vector const &v)
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)
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 uint64_t init_carry(uint64_t const *data, size_type word_pos)
static bool found_arg(size_type i, bit_vector const &v)
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 arg_cnt(bit_vector const &v)
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(uint64_t const *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 arg_cnt(bit_vector const &v)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
select_support::size_type size_type
static bool found_arg(size_type i, bit_vector const &v)
static uint64_t init_carry(uint64_t const *, size_type)
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)
select_support::size_type size_type
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t)
static bool found_arg(size_type i, bit_vector const &v)
static size_type arg_cnt(bit_vector const &v)
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 uint64_t init_carry(uint64_t const *, size_type)
static size_type args_in_the_word(uint64_t, uint64_t &)
select_support::size_type size_type
static bool found_arg(size_type, bit_vector const &)
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)
static size_type arg_cnt(bit_vector const &)
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.