SDSL 3.0.1
Succinct Data Structure Library
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{
30 private:
32
33 public:
37
38 public:
39 explicit rank_support_int_scan(const int_vector<> * v = nullptr)
40 : rank_support_int<alphabet_size>(v){};
45 size_type rank(size_type idx, const value_type v) const;
46 size_type operator()(size_type idx, const value_type v) const { return rank(idx, v); };
47 size_type prefix_rank(size_type idx, const value_type v) const;
48 size_type size() const { return this->m_v->size(); };
49 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, const std::string name = "") const
50 {
51 return serialize_empty_object(out, v, name, this);
52 }
53 void load(std::istream &, const int_vector<> * v = nullptr)
54 {
55 this->m_v = v;
56 this->init(v);
57 }
58 void set_vector(const int_vector<> * v = nullptr) { this->m_v = v; }
59};
60
66template <uint8_t alphabet_size>
68 const size_type idx,
69 const value_type v) const
70{
71 assert(v < this->t_v);
72 assert(this->m_v != nullptr);
73 assert(idx <= this->m_v->size());
74
75 if (unlikely(v == 0)) return prefix_rank(idx, v);
76
77 const uint64_t * p = this->m_v->data();
78 size_type i = 0;
79 size_type result = 0;
80 size_type word_pos = (idx * this->t_b) >> 6;
81 while (i < word_pos)
82 {
83 result += base_t::full_word_rank(base_t::extract_word(p, i), v);
84 ++i;
85 }
86 return result + base_t::word_rank(base_t::extract_word(p, idx), idx * this->sigma_bits, v);
87}
88
94template <uint8_t alphabet_size>
96 const size_type idx,
97 const value_type v) const
98{
99 assert(v < this->t_v);
100 assert(this->m_v != nullptr);
101 assert(idx <= this->m_v->size());
102
103 if (unlikely(v == this->t_v - 1)) return idx;
104
105 const uint64_t * p = this->m_v->data();
106 size_type word_pos = (idx * this->sigma_bits) >> 6;
107 size_type i = 0;
108 size_type result = 0;
109
110 while (i < word_pos)
111 {
112 result += base_t::full_word_prefix_rank(base_t::extract_word(p, i), v);
113 ++i;
114 }
115
116 return result + base_t::word_prefix_rank(base_t::extract_word(p, idx), idx * this->sigma_bits, v)[0];
117}
118
119} // namespace sdsl
120
121#endif // end file
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(const int_vector<> *v=nullptr)
void load(std::istream &, const int_vector<> *v=nullptr)
Loads the rank_support_int.
rank_support_int_scan(const rank_support_int_scan &rs)=default
size_type rank(size_type idx, const value_type v) const
Counts the occurrences of v in the prefix [0..idx-1].
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 & operator=(const rank_support_int_scan &rs)=default
void set_vector(const int_vector<> *v=nullptr)
Sets the supported int_vector to the given pointer.
The base class of classes supporting rank_queries for a sdsl::int_vector in constant time.
const int_vector * 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="", const T *t=nullptr)
Definition: io.hpp:325
rank_support_int.hpp contains classes that support a sdsl::int_vector with constant time rank informa...
#define unlikely(x)