8#ifndef INCLUDED_SDSL_NEAREST_NEIGHBOUR_DICTIONARY
9#define INCLUDED_SDSL_NEAREST_NEIGHBOUR_DICTIONARY
43template <u
int8_t t_sample_dens>
47 static_assert(t_sample_dens != 0,
"nearest_neighbour_dictionary: t_sample_dens should not be equal 0!");
75 size_type max_distance_between_two_ones = 0;
80 for (
size_type i = 0, last_one_pos_plus_1 = 0; i < v.
size(); ++i)
84 if (i + 1 - last_one_pos_plus_1 > max_distance_between_two_ones)
85 max_distance_between_two_ones = i + 1 - last_one_pos_plus_1;
86 last_one_pos_plus_1 = i + 1;
96 m_differences =
int_vector<>(m_ones - m_ones / t_sample_dens, 0,
bits::hi(max_distance_between_two_ones) + 1);
98 m_contains_abs_sample =
bit_vector((v.
size() + t_sample_dens - 1) / t_sample_dens, 0);
105 if ((
ones % t_sample_dens) == 0)
107 m_abs_samples[
ones / t_sample_dens] = i;
108 m_contains_abs_sample[i / t_sample_dens] = 1;
112 m_differences[
ones -
ones / t_sample_dens - 1] = i - last_one_pos;
117 util::init_support(m_rank_contains_abs_sample, &m_contains_abs_sample);
122 m_abs_samples(nnd.m_abs_samples),
123 m_differences(nnd.m_differences),
126 m_contains_abs_sample(nnd.m_contains_abs_sample),
127 m_rank_contains_abs_sample(nnd.m_rank_contains_abs_sample)
129 m_rank_contains_abs_sample.
set_vector(&m_contains_abs_sample);
135 *
this = std::move(nnd);
147 *
this = std::move(tmp);
156 m_abs_samples = std::move(nnd.m_abs_samples);
157 m_differences = std::move(nnd.m_differences);
158 m_ones = std::move(nnd.m_ones);
159 m_size = std::move(nnd.m_size);
160 m_contains_abs_sample = std::move(nnd.m_contains_abs_sample);
161 m_rank_contains_abs_sample = std::move(nnd.m_rank_contains_abs_sample);
162 m_rank_contains_abs_sample.
set_vector(&m_contains_abs_sample);
174 assert(idx <= m_size);
175 size_type r = m_rank_contains_abs_sample.
rank(idx / t_sample_dens);
178 while (++result <= m_ones)
180 if ((result % t_sample_dens) == 0)
182 i = m_abs_samples[result / t_sample_dens];
186 i = i + m_differences[result - result / t_sample_dens - 1];
201 assert(i > 0 and i <= m_ones);
204 j = j * t_sample_dens - j;
205 for (
size_type end = j + (i % t_sample_dens); j < end; ++j)
207 result += m_differences[j];
254 written_bytes += m_abs_samples.
serialize(out, child,
"absolute_samples");
255 written_bytes += m_differences.
serialize(out, child,
"differences");
256 written_bytes +=
write_member(m_ones, out, child,
"ones");
257 written_bytes +=
write_member(m_size, out, child,
"size");
258 written_bytes += m_contains_abs_sample.
serialize(out, child,
"contains_abs_sample");
259 written_bytes += m_rank_contains_abs_sample.
serialize(out, child,
"rank_contains_abs_sample");
261 return written_bytes;
269 m_abs_samples.
load(in);
270 m_differences.
load(in);
273 m_contains_abs_sample.
load(in);
274 m_rank_contains_abs_sample.
load(in, &m_contains_abs_sample);
277 template <
typename archive_t>
288 template <
typename archive_t>
297 m_rank_contains_abs_sample.
set_vector(&m_contains_abs_sample);
303 return (m_ones == other.m_ones) && (m_size == other.m_size) && (m_abs_samples == other.m_abs_samples)
304 && (m_differences == other.m_differences) && (m_contains_abs_sample == other.m_contains_abs_sample)
305 && (m_rank_contains_abs_sample == other.m_rank_contains_abs_sample);
311 return !(*
this == other);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
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.
nearest_neighbour_dictionary & operator=(nearest_neighbour_dictionary &&nnd)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
nearest_neighbour_dictionary()
Default constructor.
nearest_neighbour_dictionary(nearest_neighbour_dictionary const &nnd)
Copy constructor.
bit_vector::size_type size_type
nearest_neighbour_dictionary & operator=(nearest_neighbour_dictionary const &nnd)
nearest_neighbour_dictionary(nearest_neighbour_dictionary &&nnd)
Move constructor.
nearest_neighbour_dictionary(bit_vector const &v)
Constructor.
size_type select(size_type i) const
Answers select queries for the supported bit_vector.
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.
void load(std::istream &in, int_vector< 1 > const *v=nullptr)
Loads the rank_support.
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(bit_vector const *v=nullptr)
Sets the supported bit_vector to the given pointer.
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
Namespace for the succinct data structure library.
size_t write_member(T const &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_v.hpp contains rank_support_v.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.