SDSL 3.0.1
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 <sdsl/rank_support.hpp>
12
14namespace sdsl
15{
16
17template <uint8_t, uint8_t>
18struct rank_support_trait;
19
21
37template <uint8_t t_b = 1, uint8_t t_pat_len = 1>
39{
40 private:
41 static_assert(t_b == 1u or t_b == 0u or t_b == 10u or t_b == 11u,
42 "rank_support_v5: bit pattern must be `0`,`1`,`10` or `01` or `11`");
43 static_assert(t_pat_len == 1u or t_pat_len == 2u, "rank_support_v5: bit pattern length must be 1 or 2");
44
45 public:
48 enum
49 {
50 bit_pat = t_b
51 };
52 enum
53 {
54 bit_pat_len = t_pat_len
55 };
56
57 private:
58 // basic block for interleaved storage of superblockrank and blockrank
59 int_vector<64> m_basic_block;
60
61 public:
62 explicit rank_support_v5(const bit_vector * v = nullptr)
63 {
64 set_vector(v);
65 if (v == nullptr) { return; }
66 else if (v->empty())
67 {
68 m_basic_block = int_vector<64>(2, 0);
69 return;
70 }
71 size_type basic_block_size = (((v->bit_size() + 63) >> 11) + 1) << 1;
72 m_basic_block.resize(basic_block_size); // resize structure for basic_blocks
73 if (m_basic_block.empty()) return;
74 const uint64_t * data = m_v->data();
75 size_type i, j = 0;
76 m_basic_block[0] = m_basic_block[1] = 0;
77
78 uint64_t carry = trait_type::init_carry();
79 uint64_t sum = trait_type::args_in_the_word(*data, carry);
80 uint64_t second_level_cnt = 0;
81 uint64_t cnt_words = 1;
82 for (i = 1; i < ((m_v->bit_size() + 63) >> 6); ++i, ++cnt_words)
83 {
84 if (cnt_words == 32)
85 {
86 j += 2;
87 m_basic_block[j - 1] = second_level_cnt;
88 m_basic_block[j] = m_basic_block[j - 2] + sum;
89 second_level_cnt = sum = cnt_words = 0;
90 }
91 else if ((cnt_words % 6) == 0)
92 {
93 // pack the prefix sum for each 6x64bit block into the second_level_cnt
94 second_level_cnt |= sum << (60 - 12 * (cnt_words / 6)); // 48, 36, 24, 12, 0
95 }
96 sum += trait_type::args_in_the_word(*(++data), carry);
97 }
98
99 if ((cnt_words % 6) == 0) { second_level_cnt |= sum << (60 - 12 * (cnt_words / 6)); }
100 if (cnt_words == 32)
101 {
102 j += 2;
103 m_basic_block[j - 1] = second_level_cnt;
104 m_basic_block[j] = m_basic_block[j - 2] + sum;
105 m_basic_block[j + 1] = 0;
106 }
107 else
108 {
109 m_basic_block[j + 1] = second_level_cnt;
110 }
111 }
112
117
119 {
120 assert(m_v != nullptr);
121 assert(idx <= m_v->size());
122 const uint64_t * p = m_basic_block.data() + ((idx >> 10) & 0xFFFFFFFFFFFFFFFEULL); // (idx/2048)*2
123 // ( prefix sum of the 6x64bit blocks | (idx%2048)/(64*6) )
124 size_type result = *p + ((*(p + 1) >> (60 - 12 * ((idx & 0x7FF) / (64 * 6)))) & 0x7FFULL) +
126 idx -= (idx & 0x3F);
127 uint8_t to_do = ((idx >> 6) & 0x1FULL) % 6;
128 --idx;
129 while (to_do)
130 {
131 result += trait_type::full_word_rank(m_v->data(), idx);
132 --to_do;
133 idx -= 64;
134 }
135 return result;
136 }
137
138 inline size_type operator()(size_type idx) const { return rank(idx); }
139 size_type size() const { return m_v->size(); }
140
141 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
142 {
143 size_type written_bytes = 0;
144 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
145 written_bytes += m_basic_block.serialize(out, child, "cumulative_counts");
146 structure_tree::add_size(child, written_bytes);
147 return written_bytes;
148 }
149
150 void load(std::istream & in, const bit_vector * v = nullptr)
151 {
152 set_vector(v);
153 m_basic_block.load(in);
154 }
155
156 template <typename archive_t>
157 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
158 {
159 ar(CEREAL_NVP(m_basic_block));
160 }
161
162 template <typename archive_t>
163 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
164 {
165 ar(CEREAL_NVP(m_basic_block));
166 }
167
168 bool operator==(const rank_support_v5 & other) const noexcept { return m_basic_block == other.m_basic_block; }
169
170 bool operator!=(const rank_support_v5 & other) const noexcept { return !(*this == other); }
171
172 void set_vector(const bit_vector * v = nullptr) { m_v = v; }
173};
174
175} // namespace sdsl
176
177#endif // end file
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
bool empty() const noexcept
Equivalent to size() == 0.
Definition: int_vector.hpp:500
size_type bit_size() const noexcept
The number of bits in the int_vector.
Definition: int_vector.hpp:547
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:566
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:521
A class supporting rank queries in constant time.
rank_support_trait< t_b, t_pat_len > trait_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes rank_support.
bool operator==(const rank_support_v5 &other) const noexcept
void set_vector(const bit_vector *v=nullptr)
Sets the supported bit_vector to the given pointer.
bool operator!=(const rank_support_v5 &other) const noexcept
size_type rank(size_type idx) const
Answers rank queries for the supported bit_vector.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
rank_support_v5(const rank_support_v5 &)=default
rank_support_v5 & operator=(rank_support_v5 &&)=default
rank_support_v5(rank_support_v5 &&)=default
void load(std::istream &in, const bit_vector *v=nullptr)
Loads the rank_support.
size_type operator()(size_type idx) const
Alias for rank(i)
size_type size() const
rank_support_v5(const bit_vector *v=nullptr)
rank_support_v5 & operator=(const rank_support_v5 &)=default
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
The base class of classes supporting rank_queries for a sdsl::bit_vector in constant time.
const bit_vector * 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, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
Namespace for the succinct data structure library.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
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 &)