SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
rank_support_v5.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_VFIVE
9#define INCLUDED_SDSL_RANK_SUPPORT_VFIVE
10
11#include <assert.h>
12#include <iosfwd>
13#include <stdint.h>
14#include <string>
15
16#include <sdsl/cereal.hpp>
17#include <sdsl/int_vector.hpp>
18#include <sdsl/rank_support.hpp>
20#include <sdsl/util.hpp>
21
23namespace sdsl
24{
25
27
43template <uint8_t t_b = 1, uint8_t t_pat_len = 1>
45{
46private:
47 static_assert(t_b == 1u or t_b == 0u or t_b == 10u or t_b == 11u,
48 "rank_support_v5: bit pattern must be `0`,`1`,`10` or `01` or `11`");
49 static_assert(t_pat_len == 1u or t_pat_len == 2u, "rank_support_v5: bit pattern length must be 1 or 2");
50
51public:
54 enum
55 {
56 bit_pat = t_b
57 };
58 enum
59 {
60 bit_pat_len = t_pat_len
61 };
62
63private:
64 // basic block for interleaved storage of superblockrank and blockrank
65 int_vector<64> m_basic_block;
66
67public:
68 explicit rank_support_v5(bit_vector const * v = nullptr)
69 {
70 set_vector(v);
71 if (v == nullptr)
72 {
73 return;
74 }
75 else if (v->empty())
76 {
77 m_basic_block = int_vector<64>(2, 0);
78 return;
79 }
80 size_type basic_block_size = (((v->bit_size() + 63) >> 11) + 1) << 1;
81 m_basic_block.resize(basic_block_size); // resize structure for basic_blocks
82 if (m_basic_block.empty())
83 return;
84 uint64_t const * data = m_v->data();
85 size_type i, j = 0;
86 m_basic_block[0] = m_basic_block[1] = 0;
87
88 uint64_t carry = trait_type::init_carry();
89 uint64_t sum = trait_type::args_in_the_word(*data, carry);
90 uint64_t second_level_cnt = 0;
91 uint64_t cnt_words = 1;
92 for (i = 1; i < ((m_v->bit_size() + 63) >> 6); ++i, ++cnt_words)
93 {
94 if (cnt_words == 32)
95 {
96 j += 2;
97 m_basic_block[j - 1] = second_level_cnt;
98 m_basic_block[j] = m_basic_block[j - 2] + sum;
99 second_level_cnt = sum = cnt_words = 0;
100 }
101 else if ((cnt_words % 6) == 0)
102 {
103 // pack the prefix sum for each 6x64bit block into the second_level_cnt
104 second_level_cnt |= sum << (60 - 12 * (cnt_words / 6)); // 48, 36, 24, 12, 0
105 }
106 sum += trait_type::args_in_the_word(*(++data), carry);
107 }
108
109 if ((cnt_words % 6) == 0)
110 {
111 second_level_cnt |= sum << (60 - 12 * (cnt_words / 6));
112 }
113 if (cnt_words == 32)
114 {
115 j += 2;
116 m_basic_block[j - 1] = second_level_cnt;
117 m_basic_block[j] = m_basic_block[j - 2] + sum;
118 m_basic_block[j + 1] = 0;
119 }
120 else
121 {
122 m_basic_block[j + 1] = second_level_cnt;
123 }
124 }
125
130
132 {
133 assert(m_v != nullptr);
134 assert(idx <= m_v->size());
135 uint64_t const * p = m_basic_block.data() + ((idx >> 10) & 0xFFFFFFFFFFFFFFFEULL); // (idx/2048)*2
136 // ( prefix sum of the 6x64bit blocks | (idx%2048)/(64*6) )
137 size_type result = *p + ((*(p + 1) >> (60 - 12 * ((idx & 0x7FF) / (64 * 6)))) & 0x7FFULL)
138 + trait_type::word_rank(m_v->data(), idx);
139 idx -= (idx & 0x3F);
140 uint8_t to_do = ((idx >> 6) & 0x1FULL) % 6;
141 --idx;
142 while (to_do)
143 {
144 result += trait_type::full_word_rank(m_v->data(), idx);
145 --to_do;
146 idx -= 64;
147 }
148 return result;
149 }
150
152 {
153 return rank(idx);
154 }
156 {
157 return m_v->size();
158 }
159
160 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
161 {
162 size_type written_bytes = 0;
163 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
164 written_bytes += m_basic_block.serialize(out, child, "cumulative_counts");
165 structure_tree::add_size(child, written_bytes);
166 return written_bytes;
167 }
168
169 void load(std::istream & in, bit_vector const * v = nullptr)
170 {
171 set_vector(v);
172 m_basic_block.load(in);
173 }
174
175 template <typename archive_t>
176 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
177 {
178 ar(CEREAL_NVP(m_basic_block));
179 }
180
181 template <typename archive_t>
182 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
183 {
184 ar(CEREAL_NVP(m_basic_block));
185 }
186
187 bool operator==(rank_support_v5 const & other) const noexcept
188 {
189 return m_basic_block == other.m_basic_block;
190 }
191
192 bool operator!=(rank_support_v5 const & other) const noexcept
193 {
194 return !(*this == other);
195 }
196
197 void set_vector(bit_vector const * v = nullptr)
198 {
199 m_v = v;
200 }
201};
202
203} // namespace sdsl
204
205#endif // end file
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
A generic vector class for integers of width .
bool operator!=(rank_support_v5 const &other) const noexcept
rank_support_trait< t_b, t_pat_len > trait_type
rank_support_v5 & operator=(rank_support_v5 const &)=default
void load(std::istream &in, bit_vector const *v=nullptr)
Loads the rank_support.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes rank_support.
rank_support_v5(bit_vector const *v=nullptr)
size_type rank(size_type idx) const
Answers rank queries for the supported bit_vector.
bool operator==(rank_support_v5 const &other) const noexcept
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
void set_vector(bit_vector const *v=nullptr)
Sets the supported bit_vector to the given pointer.
rank_support_v5 & operator=(rank_support_v5 &&)=default
rank_support_v5(rank_support_v5 &&)=default
size_type operator()(size_type idx) const
Alias for rank(i)
rank_support_v5(rank_support_v5 const &)=default
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
rank_support(bit_vector const *v=nullptr)
Constructor.
bit_vector const * m_v
Pointer to the rank supported bit_vector.
bit_vector::size_type size_type
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
excess< T >::impl excess< T >::data
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
static uint32_t word_rank(uint64_t const *, size_type)
static uint32_t full_word_rank(uint64_t const *, size_type)
static size_type args_in_the_word(uint64_t, uint64_t &)
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.