SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
rank_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_RANK_SUPPORT
9#define INCLUDED_SDSL_RANK_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
23namespace sdsl
24{
25class structure_tree_node;
26
28
31{
32protected:
33 bit_vector const * m_v;
34
35public:
37
39
41 rank_support(bit_vector const * v = nullptr);
43 rank_support(rank_support const &) = default;
45 rank_support & operator=(rank_support const &) = default;
48 virtual ~rank_support()
49 {}
50
52
57 virtual size_type rank(size_type i) const = 0;
59 virtual size_type operator()(size_type idx) const = 0;
61
63 virtual size_type serialize(std::ostream & out, structure_tree_node * v, std::string name) const = 0;
65
68 virtual void load(std::istream & in, bit_vector const * v = nullptr) = 0;
70
74 virtual void set_vector(bit_vector const * v = nullptr) = 0;
75};
76
78{
79 m_v = v;
80}
81
82//----------------------------------------------------------------------
83
84template <uint8_t bit_pattern, uint8_t pattern_len>
86{
88
89 static size_type args_in_the_word(uint64_t, uint64_t &)
90 {
91 return 0;
92 }
93
94 static uint32_t word_rank(uint64_t const *, size_type)
95 {
96 return 0;
97 }
98
99 static uint32_t full_word_rank(uint64_t const *, size_type)
100 {
101 return 0;
102 }
103
104 static uint64_t init_carry()
105 {
106 return 0;
107 }
108};
109
110template <>
112{
114
115 static size_type args_in_the_word(uint64_t w, uint64_t &)
116 {
117 return bits::cnt(~w);
118 }
119
120 static uint32_t word_rank(uint64_t const * data, size_type idx)
121 {
122 return bits::cnt((~*(data + (idx >> 6))) & bits::lo_set[idx & 0x3F]);
123 }
124
125 static uint32_t full_word_rank(uint64_t const * data, size_type idx)
126 {
127 return bits::cnt((~*(data + (idx >> 6))));
128 }
129
130 static uint64_t init_carry()
131 {
132 return 0;
133 }
134};
135
136template <>
138{
140
141 static size_type args_in_the_word(uint64_t w, uint64_t &)
142 {
143 return bits::cnt(w);
144 }
145
146 static uint32_t word_rank(uint64_t const * data, size_type idx)
147 {
148 return bits::cnt(*(data + (idx >> 6)) & bits::lo_set[idx & 0x3F]);
149 }
150
151 static uint32_t full_word_rank(uint64_t const * data, size_type idx)
152 {
153 return bits::cnt(*(data + (idx >> 6)));
154 }
155
156 static uint64_t init_carry()
157 {
158 return 0;
159 }
160};
161
162template <>
164{
166
167 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
168 {
169 return bits::cnt10(w, carry);
170 }
171
172 static uint32_t word_rank(uint64_t const * data, size_type idx)
173 {
174 data = data + (idx >> 6);
175 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 0;
176 return bits::cnt(bits::map10(*data, carry) & bits::lo_set[idx & 0x3F]);
177 }
178
179 static uint32_t full_word_rank(uint64_t const * data, size_type idx)
180 {
181 data = data + (idx >> 6);
182 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 0;
183 return bits::cnt(bits::map10(*data, carry));
184 }
185
186 static uint64_t init_carry()
187 {
188 return 0;
189 }
190};
191
192template <>
194{
196
197 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
198 {
199 return bits::cnt01(w, carry);
200 }
201
202 static uint32_t word_rank(uint64_t const * data, size_type idx)
203 {
204 data = data + (idx >> 6);
205 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 1;
206 return bits::cnt(bits::map01(*data, carry) & bits::lo_set[idx & 0x3F]);
207 }
208
209 static uint32_t full_word_rank(uint64_t const * data, size_type idx)
210 {
211 data = data + (idx >> 6);
212 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 1;
213 return bits::cnt(bits::map01(*data, carry));
214 }
215
216 static uint64_t init_carry()
217 {
218 return 1;
219 }
220};
221
222template <>
224{
226
227 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
228 {
229 size_type res = bits::cnt(~(w | (w << 1 | carry)));
230 carry = (w >> 63);
231 return res;
232 }
233
234 static uint32_t word_rank(uint64_t const * data, size_type idx)
235 {
236 data = data + (idx >> 6);
237 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 1;
238 return bits::cnt((~(*data | ((*data) << 1 | carry))) & bits::lo_set[idx & 0x3F]);
239 }
240
241 static uint32_t full_word_rank(uint64_t const * data, size_type idx)
242 {
243 data = data + (idx >> 6);
244 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 1;
245 return bits::cnt(~(*data | ((*data) << 1 | carry)));
246 }
247
248 static uint64_t init_carry()
249 {
250 return 1;
251 }
252};
253
254template <>
256{
258
259 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
260 {
261 size_type res = bits::cnt(w & (w << 1 | carry));
262 carry = (w >> 63);
263 return res;
264 }
265
266 static uint32_t word_rank(uint64_t const * data, size_type idx)
267 {
268 data = data + (idx >> 6);
269 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 0;
270 return bits::cnt((*data & ((*data) << 1 | carry)) & bits::lo_set[idx & 0x3F]);
271 }
272
273 static uint32_t full_word_rank(uint64_t const * data, size_type idx)
274 {
275 data = data + (idx >> 6);
276 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 0;
277 return bits::cnt(*data & ((*data) << 1 | carry));
278 }
279
280 static uint64_t init_carry()
281 {
282 return 0;
283 }
284};
285
286} // namespace sdsl
287
288// clang-format off
289// Cyclic includes start
293// Cyclic includes end
294// clang-format on
295
296#endif
bits.hpp contains the sdsl::bits class.
int_vector_size_type size_type
The base class of classes supporting rank_queries for a sdsl::bit_vector in constant time.
virtual size_type rank(size_type i) const =0
Answers rank queries for the supported bit_vector.
virtual ~rank_support()
Destructor.
rank_support(bit_vector const *v=nullptr)
Constructor.
virtual void load(std::istream &in, bit_vector const *v=nullptr)=0
Loads the rank_support.
rank_support & operator=(rank_support &&)=default
virtual size_type operator()(size_type idx) const =0
Alias for rank(i)
bit_vector const * m_v
Pointer to the rank supported bit_vector.
rank_support & operator=(rank_support const &)=default
rank_support(rank_support &&)=default
virtual size_type serialize(std::ostream &out, structure_tree_node *v, std::string name) const =0
Serializes rank_support.
bit_vector::size_type size_type
virtual void set_vector(bit_vector const *v=nullptr)=0
Sets the supported bit_vector to the given pointer.
rank_support(rank_support const &)=default
Copy constructor.
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
rank_support_scan.hpp contains rank_support_scan that support a sdsl::bit_vector with linear time ran...
rank_support_v5.hpp contains rank_support_v5.5
rank_support_v.hpp contains rank_support_v.
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 uint32_t word_rank(uint64_t const *data, size_type idx)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
rank_support::size_type size_type
static uint32_t full_word_rank(uint64_t const *data, size_type idx)
static uint32_t word_rank(uint64_t const *data, size_type idx)
rank_support::size_type size_type
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint32_t full_word_rank(uint64_t const *data, size_type idx)
static size_type args_in_the_word(uint64_t w, uint64_t &)
static uint32_t word_rank(uint64_t const *data, size_type idx)
rank_support::size_type size_type
static uint32_t full_word_rank(uint64_t const *data, size_type idx)
rank_support::size_type size_type
static uint32_t word_rank(uint64_t const *data, size_type idx)
static uint32_t full_word_rank(uint64_t const *data, size_type idx)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
rank_support::size_type size_type
static uint32_t full_word_rank(uint64_t const *data, size_type idx)
static uint32_t word_rank(uint64_t const *data, size_type idx)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
rank_support::size_type size_type
static uint32_t word_rank(uint64_t const *data, size_type idx)
static size_type args_in_the_word(uint64_t w, uint64_t &)
static uint32_t full_word_rank(uint64_t const *data, size_type idx)
rank_support::size_type size_type
static uint32_t word_rank(uint64_t const *, size_type)
static uint32_t full_word_rank(uint64_t const *, size_type)
static uint64_t init_carry()
static size_type args_in_the_word(uint64_t, uint64_t &)