SDSL  3.0.0
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 
19 namespace sdsl
20 {
22 
25 {
26  protected:
27  const int_vector<1> * m_v;
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 
72 template <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 
95 template <>
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 
116 template <>
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 
137 template <>
138 struct select_support_trait<10, 2>
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 
165 template <>
166 struct select_support_trait<01, 2>
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 
193 template <>
194 struct select_support_trait<00, 2>
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 
244 template <>
245 struct select_support_trait<11, 2>
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:524
size_type bit_size() const noexcept
The number of bits in the int_vector.
Definition: int_vector.hpp:571
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:590
size_type size() const noexcept
The number of elements in the int_vector.
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.
constexpr static 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:220
static SDSL_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:594
static SDSL_CONSTEXPR uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
Definition: bits.hpp:566
static SDSL_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:588
static SDSL_CONSTEXPR uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
Definition: bits.hpp:580
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.
Definition: bits.hpp:197
static SDSL_CONSTEXPR uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:494
static SDSL_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:574
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)