8 #ifndef INCLUDED_SDSL_NEAREST_NEIGHBOUR_DICTIONARY
9 #define INCLUDED_SDSL_NEAREST_NEIGHBOUR_DICTIONARY
38 template <u
int8_t t_sample_dens>
42 static_assert(t_sample_dens != 0,
"nearest_neighbour_dictionary: t_sample_dens should not be equal 0!");
74 size_type max_distance_between_two_ones = 0;
79 for (
size_type i = 0, last_one_pos_plus_1 = 0; i < v.
size(); ++i)
83 if (i + 1 - last_one_pos_plus_1 > max_distance_between_two_ones)
84 max_distance_between_two_ones = i + 1 - last_one_pos_plus_1;
85 last_one_pos_plus_1 = i + 1;
95 m_differences =
int_vector<>(m_ones - m_ones / t_sample_dens, 0,
bits::hi(max_distance_between_two_ones) + 1);
97 m_contains_abs_sample =
bit_vector((v.
size() + t_sample_dens - 1) / t_sample_dens, 0);
104 if ((
ones % t_sample_dens) == 0)
106 m_abs_samples[
ones / t_sample_dens] = i;
107 m_contains_abs_sample[i / t_sample_dens] = 1;
111 m_differences[
ones -
ones / t_sample_dens - 1] = i - last_one_pos;
116 util::init_support(m_rank_contains_abs_sample, &m_contains_abs_sample);
121 : m_abs_samples(nnd.m_abs_samples)
122 , m_differences(nnd.m_differences)
125 , m_contains_abs_sample(nnd.m_contains_abs_sample)
126 , m_rank_contains_abs_sample(nnd.m_rank_contains_abs_sample)
128 m_rank_contains_abs_sample.
set_vector(&m_contains_abs_sample);
142 *
this = std::move(tmp);
151 m_abs_samples = std::move(nnd.m_abs_samples);
152 m_differences = std::move(nnd.m_differences);
153 m_ones = std::move(nnd.m_ones);
154 m_size = std::move(nnd.m_size);
155 m_contains_abs_sample = std::move(nnd.m_contains_abs_sample);
156 m_rank_contains_abs_sample = std::move(nnd.m_rank_contains_abs_sample);
157 m_rank_contains_abs_sample.
set_vector(&m_contains_abs_sample);
169 assert(idx <= m_size);
170 size_type r = m_rank_contains_abs_sample.
rank(idx / t_sample_dens);
173 while (++result <= m_ones)
175 if ((result % t_sample_dens) == 0) { i = m_abs_samples[result / t_sample_dens]; }
178 i = i + m_differences[result - result / t_sample_dens - 1];
180 if (i >= idx)
return result - 1;
192 assert(i > 0 and i <= m_ones);
195 j = j * t_sample_dens - j;
196 for (
size_type end = j + (i % t_sample_dens); j < end; ++j) { result += m_differences[j]; }
236 written_bytes += m_abs_samples.
serialize(out, child,
"absolute_samples");
237 written_bytes += m_differences.
serialize(out, child,
"differences");
238 written_bytes +=
write_member(m_ones, out, child,
"ones");
239 written_bytes +=
write_member(m_size, out, child,
"size");
240 written_bytes += m_contains_abs_sample.
serialize(out, child,
"contains_abs_sample");
241 written_bytes += m_rank_contains_abs_sample.
serialize(out, child,
"rank_contains_abs_sample");
243 return written_bytes;
251 m_abs_samples.
load(in);
252 m_differences.
load(in);
255 m_contains_abs_sample.
load(in);
256 m_rank_contains_abs_sample.
load(in, &m_contains_abs_sample);
259 template <
typename archive_t>
270 template <
typename archive_t>
279 m_rank_contains_abs_sample.
set_vector(&m_contains_abs_sample);
285 return (m_ones == other.m_ones) && (m_size == other.m_size) && (m_abs_samples == other.m_abs_samples) &&
286 (m_differences == other.m_differences) && (m_contains_abs_sample == other.m_contains_abs_sample) &&
287 (m_rank_contains_abs_sample == other.m_rank_contains_abs_sample);
int_vector_size_type size_type
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.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
Nearest neighbour dictionary for sparse uniform sets (described in Geary et al., A Simple Optimal Rep...
~nearest_neighbour_dictionary()
Destructor.
size_type next(size_type i) const
Answers "next occurence of one" queries for the supported bit_vector.
bool operator==(nearest_neighbour_dictionary const &other) const noexcept
Equality operator.
size_type rank(size_type idx) const
Answers rank queries for the supported bit_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the nearest_neighbour_dictionary.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
void load(std::istream &in)
Loads the nearest_neighbour_dictionary.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
nearest_neighbour_dictionary(const bit_vector &v)
Constructor.
nearest_neighbour_dictionary()
Default constructor.
nearest_neighbour_dictionary & operator=(const nearest_neighbour_dictionary &nnd)
bit_vector::size_type size_type
nearest_neighbour_dictionary(nearest_neighbour_dictionary &&nnd)
Move constructor.
nearest_neighbour_dictionary(const nearest_neighbour_dictionary &nnd)
Copy constructor.
size_type select(size_type i) const
Answers select queries for the supported bit_vector.
nearest_neighbour_dictionary & operator=(nearest_neighbour_dictionary &&nnd)
size_type prev(size_type i) const
Answers "previous occurence of one" queries for the supported bit_vector.
bool operator!=(nearest_neighbour_dictionary const &other) const noexcept
Inequality operator.
A rank structure proposed by Sebastiano Vigna.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes rank_support.
size_type rank(size_type idx) const
Answers rank queries for the supported bit_vector.
void set_vector(const bit_vector *v=nullptr)
Sets the supported bit_vector to the given pointer.
void load(std::istream &in, const int_vector< 1 > *v=nullptr)
Loads the rank_support.
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.
wm_int.hpp contains a specialized class for a wavelet tree for sequences over large alphabets.