SDSL 3.0.1
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 <sdsl/int_vector.hpp>
16
18namespace sdsl
19{
20
22
25{
26 protected:
27 const bit_vector * m_v;
28 public:
30
32
34 rank_support(const bit_vector * v = nullptr);
36 rank_support(const rank_support &) = default;
38 rank_support & operator=(const rank_support &) = default;
41 virtual ~rank_support() {}
42
44
49 virtual size_type rank(size_type i) const = 0;
51 virtual size_type operator()(size_type idx) const = 0;
53
55 virtual size_type serialize(std::ostream & out, structure_tree_node * v, std::string name) const = 0;
57
60 virtual void load(std::istream & in, const bit_vector * v = nullptr) = 0;
62
66 virtual void set_vector(const bit_vector * v = nullptr) = 0;
67};
68
70{
71 m_v = v;
72}
73
74//----------------------------------------------------------------------
75
76template <uint8_t bit_pattern, uint8_t pattern_len>
78{
80
81 static size_type args_in_the_word(uint64_t, uint64_t &) { return 0; }
82
83 static uint32_t word_rank(const uint64_t *, size_type) { return 0; }
84
85 static uint32_t full_word_rank(const uint64_t *, size_type) { return 0; }
86
87 static uint64_t init_carry() { return 0; }
88};
89
90template <>
92{
94
95 static size_type args_in_the_word(uint64_t w, uint64_t &) { return bits::cnt(~w); }
96
97 static uint32_t word_rank(const uint64_t * data, size_type idx)
98 {
99 return bits::cnt((~*(data + (idx >> 6))) & bits::lo_set[idx & 0x3F]);
100 }
101
102 static uint32_t full_word_rank(const uint64_t * data, size_type idx) { return bits::cnt((~*(data + (idx >> 6)))); }
103
104 static uint64_t init_carry() { return 0; }
105};
106
107template <>
109{
111
112 static size_type args_in_the_word(uint64_t w, uint64_t &) { return bits::cnt(w); }
113
114 static uint32_t word_rank(const uint64_t * data, size_type idx)
115 {
116 return bits::cnt(*(data + (idx >> 6)) & bits::lo_set[idx & 0x3F]);
117 }
118
119 static uint32_t full_word_rank(const uint64_t * data, size_type idx) { return bits::cnt(*(data + (idx >> 6))); }
120
121 static uint64_t init_carry() { return 0; }
122};
123
124template <>
126{
128
129 static size_type args_in_the_word(uint64_t w, uint64_t & carry) { return bits::cnt10(w, carry); }
130
131 static uint32_t word_rank(const uint64_t * data, size_type idx)
132 {
133 data = data + (idx >> 6);
134 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 0;
135 return bits::cnt(bits::map10(*data, carry) & bits::lo_set[idx & 0x3F]);
136 }
137
138 static uint32_t full_word_rank(const uint64_t * data, size_type idx)
139 {
140 data = data + (idx >> 6);
141 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 0;
142 return bits::cnt(bits::map10(*data, carry));
143 }
144
145 static uint64_t init_carry() { return 0; }
146};
147
148template <>
150{
152
153 static size_type args_in_the_word(uint64_t w, uint64_t & carry) { return bits::cnt01(w, carry); }
154
155 static uint32_t word_rank(const uint64_t * data, size_type idx)
156 {
157 data = data + (idx >> 6);
158 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 1;
159 return bits::cnt(bits::map01(*data, carry) & bits::lo_set[idx & 0x3F]);
160 }
161
162 static uint32_t full_word_rank(const uint64_t * data, size_type idx)
163 {
164 data = data + (idx >> 6);
165 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 1;
166 return bits::cnt(bits::map01(*data, carry));
167 }
168
169 static uint64_t init_carry() { return 1; }
170};
171
172template <>
174{
176
177 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
178 {
179 size_type res = bits::cnt(~(w | (w << 1 | carry)));
180 carry = (w >> 63);
181 return res;
182 }
183
184 static uint32_t word_rank(const uint64_t * data, size_type idx)
185 {
186 data = data + (idx >> 6);
187 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 1;
188 return bits::cnt((~(*data | ((*data) << 1 | carry))) & bits::lo_set[idx & 0x3F]);
189 }
190
191 static uint32_t full_word_rank(const uint64_t * data, size_type idx)
192 {
193 data = data + (idx >> 6);
194 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 1;
195 return bits::cnt(~(*data | ((*data) << 1 | carry)));
196 }
197
198 static uint64_t init_carry() { return 1; }
199};
200
201template <>
203{
205
206 static size_type args_in_the_word(uint64_t w, uint64_t & carry)
207 {
208 size_type res = bits::cnt(w & (w << 1 | carry));
209 carry = (w >> 63);
210 return res;
211 }
212
213 static uint32_t word_rank(const uint64_t * data, size_type idx)
214 {
215 data = data + (idx >> 6);
216 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 0;
217 return bits::cnt((*data & ((*data) << 1 | carry)) & bits::lo_set[idx & 0x3F]);
218 }
219
220 static uint32_t full_word_rank(const uint64_t * data, size_type idx)
221 {
222 data = data + (idx >> 6);
223 uint64_t carry = (idx > 63) ? *(data - 1) >> 63 : 0;
224 return bits::cnt(*data & ((*data) << 1 | carry));
225 }
226
227 static uint64_t init_carry() { return 0; }
228};
229
230} // end namespace sdsl
231
235
236#endif // end file
int_vector_size_type size_type
Definition: int_vector.hpp:229
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 & operator=(const rank_support &)=default
virtual void set_vector(const bit_vector *v=nullptr)=0
Sets the supported bit_vector to the given pointer.
virtual void load(std::istream &in, const bit_vector *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)
rank_support(rank_support &&)=default
virtual size_type serialize(std::ostream &out, structure_tree_node *v, std::string name) const =0
Serializes rank_support.
const bit_vector * m_v
Pointer to the rank supported bit_vector.
rank_support(const rank_support &)=default
Copy constructor.
bit_vector::size_type size_type
rank_support(const bit_vector *v=nullptr)
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: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 uint32_t word_rank(const uint64_t *data, size_type idx)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint32_t full_word_rank(const uint64_t *data, size_type idx)
rank_support::size_type size_type
static uint32_t word_rank(const uint64_t *data, size_type idx)
static uint32_t full_word_rank(const uint64_t *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(const uint64_t *data, size_type idx)
static size_type args_in_the_word(uint64_t w, uint64_t &)
rank_support::size_type size_type
static uint32_t word_rank(const uint64_t *data, size_type idx)
static uint32_t word_rank(const uint64_t *data, size_type idx)
rank_support::size_type size_type
static uint32_t full_word_rank(const uint64_t *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(const uint64_t *data, size_type idx)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint32_t full_word_rank(const uint64_t *data, size_type idx)
rank_support::size_type size_type
static uint32_t word_rank(const uint64_t *data, size_type idx)
static size_type args_in_the_word(uint64_t w, uint64_t &)
static uint32_t full_word_rank(const uint64_t *data, size_type idx)
rank_support::size_type size_type
static uint32_t word_rank(const uint64_t *, size_type)
static uint64_t init_carry()
static uint32_t full_word_rank(const uint64_t *, size_type)
static size_type args_in_the_word(uint64_t, uint64_t &)