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
26
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 {
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 {
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
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
int_vector const * m_v
Pointer to the rank supported bit_vector.
static constexpr uint8_t sigma_bits
rank_support_int(int_vector<> const *v=nullptr)
Constructor.
static constexpr std::array< uint64_t, sizeof...(value_t)> word_prefix_rank(const uint64_t word, const size_type bit_pos, const value_t... values) noexcept
Counts the occurrences of elements smaller or equal to v in the word starting at data up to position ...
int_vector ::value_type value_type
static constexpr uint32_t full_word_prefix_rank(const uint64_t word, const value_type v) noexcept
Counts the occurrences of v in the word starting at data up to position idx.
static constexpr uint32_t word_rank(const uint64_t word, const size_type bit_pos, const value_type v) noexcept
Counts the occurrences of elements smaller or equal to v in the word starting at data up to position ...
int_vector ::size_type size_type
static constexpr uint32_t full_word_rank(const uint64_t word, const value_type v) noexcept
Counts the occurrences of v in the word starting at data up to position idx.
static constexpr uint64_t extract_word(uint64_t const *data, const size_type word_position) noexcept
Returns the word a the given word position.
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)