SDSL  3.0.0
Succinct Data Structure Library
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 
18 namespace 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;
37  rank_support(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 
76 template <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 
90 template <>
91 struct rank_support_trait<0, 1>
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 
107 template <>
108 struct rank_support_trait<1, 1>
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 
124 template <>
125 struct rank_support_trait<10, 2>
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 
148 template <>
149 struct rank_support_trait<01, 2>
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 
172 template <>
173 struct rank_support_trait<00, 2>
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 
201 template <>
202 struct rank_support_trait<11, 2>
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 
233 #include <sdsl/rank_support_v.hpp>
234 #include <sdsl/rank_support_v5.hpp>
235 
236 #endif // end file
int_vector_size_type size_type
Definition: int_vector.hpp:266
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.
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 & operator=(const rank_support &)=default
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 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 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 &)