SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
rank_support_int_scan.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.
9#ifndef INCLUDED_SDSL_RANK_SUPPORT_INT_SCAN
10#define INCLUDED_SDSL_RANK_SUPPORT_INT_SCAN
11
13
14namespace sdsl
15{
16
27template <uint8_t alphabet_size>
28class rank_support_int_scan : public rank_support_int<alphabet_size>
29{
30private:
32
33public:
37
38public:
39 explicit rank_support_int_scan(int_vector<> const * v = nullptr) : rank_support_int<alphabet_size>(v){};
44 size_type rank(size_type idx, const value_type v) const;
46 {
47 return rank(idx, v);
48 };
49 size_type prefix_rank(size_type idx, const value_type v) const;
51 {
52 return this->m_v->size();
53 };
54 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, const std::string name = "") const
55 {
56 return serialize_empty_object(out, v, name, this);
57 }
58 void load(std::istream &, int_vector<> const * v = nullptr)
59 {
60 this->m_v = v;
61 this->init(v);
62 }
63 void set_vector(int_vector<> const * v = nullptr)
64 {
65 this->m_v = v;
66 }
67};
68
74template <uint8_t alphabet_size>
77{
78 assert(v < this->t_v);
79 assert(this->m_v != nullptr);
80 assert(idx <= this->m_v->size());
81
82 if (unlikely(v == 0))
83 return prefix_rank(idx, v);
84
85 uint64_t const * p = this->m_v->data();
86 size_type i = 0;
87 size_type result = 0;
88 size_type word_pos = (idx * this->t_b) >> 6;
89 while (i < word_pos)
90 {
91 result += base_t::full_word_rank(base_t::extract_word(p, i), v);
92 ++i;
93 }
94 return result + base_t::word_rank(base_t::extract_word(p, idx), idx * this->sigma_bits, v);
95}
96
102template <uint8_t alphabet_size>
105{
106 assert(v < this->t_v);
107 assert(this->m_v != nullptr);
108 assert(idx <= this->m_v->size());
109
110 if (unlikely(v == this->t_v - 1))
111 return idx;
112
113 uint64_t const * p = this->m_v->data();
114 size_type word_pos = (idx * this->sigma_bits) >> 6;
115 size_type i = 0;
116 size_type result = 0;
117
118 while (i < word_pos)
119 {
120 result += base_t::full_word_prefix_rank(base_t::extract_word(p, i), v);
121 ++i;
122 }
123
124 return result + base_t::word_prefix_rank(base_t::extract_word(p, idx), idx * this->sigma_bits, v)[0];
125}
126
127} // namespace sdsl
128
129#endif // end file
A generic vector class for integers of width .
Definition io.hpp:36
size_type size() const noexcept
The number of elements in the int_vector.
A class supporting rank queries in linear time.
rank_support_int_scan & operator=(rank_support_int_scan const &rs)=default
rank_support_int_scan(int_vector<> const *v=nullptr)
void load(std::istream &, int_vector<> const *v=nullptr)
Loads the rank_support_int.
size_type rank(size_type idx, const value_type v) const
Counts the occurrences of v in the prefix [0..idx-1].
void set_vector(int_vector<> const *v=nullptr)
Sets the supported int_vector to the given pointer.
rank_support_int< alphabet_size >::value_type value_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const
Serializes rank_support_int.
rank_support_int_scan(rank_support_int_scan &&rs)=default
size_type operator()(size_type idx, const value_type v) const
Alias for rank(idx, v)
rank_support_int< alphabet_size >::size_type size_type
size_type prefix_rank(size_type idx, const value_type v) const
Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1].
rank_support_int_scan & operator=(rank_support_int_scan &&rs)=default
rank_support_int_scan(rank_support_int_scan const &rs)=default
The base class of classes supporting rank_queries for a sdsl::int_vector in constant time.
int_vector const * m_v
Pointer to the rank supported bit_vector.
int_vector ::value_type value_type
int_vector ::size_type size_type
Namespace for the succinct data structure library.
size_t serialize_empty_object(std::ostream &, structure_tree_node *v=nullptr, std::string name="", T const *t=nullptr)
Definition io.hpp:339
rank_support_int.hpp contains classes that support a sdsl::int_vector with constant time rank informa...
#define unlikely(x)