8#ifndef INCLUDED_SDSL_K2_TREAP
9#define INCLUDED_SDSL_K2_TREAP
61 typename t_rank =
typename t_bv::rank_1_type,
62 typename t_max_vec = dac_vector<>>
65 static_assert(t_k > 1,
"t_k has to be larger than 1.");
66 static_assert(t_k <= 16,
"t_k has to be smaller than 17.");
84 std::vector<int_vector<>> m_coord;
87 template <
typename t_tv>
88 uint8_t get_t(t_tv
const & v)
90 using namespace k2_treap_ns;
95 using t_e =
typename t_tv::value_type;
96 auto tupmax = [](t_e a)
98 return std::max(std::get<0>(a), std::get<1>(a));
100 auto max_it = std::max_element(std::begin(v),
104 return tupmax(a) < tupmax(b);
106 uint64_t x = tupmax(*max_it);
108 while (precomp<t_k>::exp(res) <= x)
123 m_bp_rank(tr.m_bp_rank),
124 m_maxval(tr.m_maxval),
126 m_level_idx(tr.m_level_idx)
128 m_bp_rank.set_vector(&m_bp);
133 *
this = std::move(tr);
142 m_bp = std::move(tr.m_bp);
143 m_bp_rank = std::move(tr.m_bp_rank);
144 m_bp_rank.set_vector(&m_bp);
145 m_maxval = std::move(tr.m_maxval);
146 m_coord = std::move(tr.m_coord);
147 m_level_idx = std::move(tr.m_level_idx);
158 *
this = std::move(tmp);
166 return m_maxval.size();
172 std::string temp_dir)
174 using namespace k2_treap_ns;
176 std::vector<t_buf_p> bufs = {&buf_x, &buf_y, &buf_w};
180 uint64_t max_val = 0;
183 max_val = std::max((uint64_t)val, max_val);
188 auto max_buf_element = [&]()
191 for (
auto buf : bufs)
193 uint64_t _max_v = max_element(*buf);
194 max_v = std::max(max_v, _max_v);
199 uint64_t x = max_buf_element();
201 while (res <= 64 and precomp<t_k>::exp(res) <= x)
207 throw std::logic_error(
"Maximal element of input is too big.");
210 if (precomp<t_k>::exp(res) <= std::numeric_limits<uint32_t>::max())
222 template <
typename t_x = u
int64_t,
typename t_y = u
int64_t,
typename t_w = u
int64_t>
225 typedef std::vector<std::tuple<t_x, t_y, t_w>> t_tuple_vec;
226 t_tuple_vec v = t_tuple_vec(bufs[0]->
size());
227 for (uint64_t j = 0; j < v.size(); ++j)
229 std::get<0>(v[j]) = (*(bufs[0]))[j];
231 for (uint64_t j = 0; j < v.size(); ++j)
233 std::get<1>(v[j]) = (*(bufs[1]))[j];
235 for (uint64_t j = 0; j < v.size(); ++j)
237 std::get<2>(v[j]) = (*(bufs[2]))[j];
242 template <
typename t_x,
typename t_y,
typename t_w>
243 k2_treap(std::vector<std::tuple<t_x, t_y, t_w>> & v, std::string temp_dir =
".")
251 template <
typename t_x,
typename t_y,
typename t_w>
252 void construct(std::vector<std::tuple<t_x, t_y, t_w>> & v, std::string temp_dir =
".")
254 using namespace k2_treap_ns;
255 using t_e = std::tuple<t_x, t_y, t_w>;
257 uint64_t M = precomp<t_k>::exp(
t);
258 t_e MM = t_e(M, M, M);
265 std::string val_file = temp_dir +
"/k2_treap_" + id_part +
".sdsl";
266 std::string bp_file = temp_dir +
"/bp_" + id_part +
".sdsl";
272 auto end = std::end(v);
273 uint64_t last_level_nodes = 1;
274 uint64_t level_nodes;
275 for (uint64_t l =
t, cc = 0; l + 1 > 0; --l)
279 m_level_idx[l - 1] = m_level_idx[l] + last_level_nodes;
284 auto sp = std::begin(v);
285 for (
auto ep = sp; ep != end;)
287 ep = std::find_if(sp,
289 [&sp, &l](t_e
const & e)
291 auto x1 = std::get<0>(*sp);
292 auto y1 = std::get<1>(*sp);
293 auto x2 = std::get<0>(e);
294 auto y2 = std::get<1>(e);
295 return precomp<t_k>::divexp(x1, l) != precomp<t_k>::divexp(x2, l)
296 or precomp<t_k>::divexp(y1, l) != precomp<t_k>::divexp(y2, l);
298 auto max_it = std::max_element(sp,
302 if (std::get<2>(a) != std::get<2>(b))
303 return std::get<2>(a) < std::get<2>(b);
304 else if (std::get<0>(a) != std::get<0>(b))
305 return std::get<0>(a) > std::get<0>(b);
306 return std::get<1>(a) > std::get<1>(b);
310 m_coord[l - 1][2 * cc] = precomp<t_k>::modexp(std::get<0>(*max_it), l);
311 m_coord[l - 1][2 * cc + 1] = precomp<t_k>::modexp(std::get<1>(*max_it), l);
318 std::swap(*max_it, *ep);
323 for (uint8_t i = 0; i < t_k; ++i)
328 _ep = std::partition(_sp,
330 [&i, &l](t_e
const & e)
332 return precomp<t_k>::divexp(std::get<0>(e), l - 1) % t_k <= i;
336 for (uint8_t j = 0; j < t_k; ++j)
341 __ep = std::partition(__sp,
343 [&j, &l](t_e
const & e)
345 return precomp<t_k>::divexp(std::get<1>(e), l - 1) % t_k
349 bool not_empty = __ep > __sp;
351 level_nodes += not_empty;
360 end = std::remove_if(begin(v),
366 last_level_nodes = level_nodes;
374 uint64_t bp_idx = bp.
size();
375 uint64_t r_idx = m_level_idx[0];
376 uint64_t rw_idx = val_rw.
size();
380 for (
size_t i = 0; i < t_k * t_k; ++i)
385 val_rw[rw_idx] = val_r[r_idx] - val_rw[rw_idx];
392 m_maxval = t_max_vec(val_r);
398 util::init_support(m_bp_rank, &m_bp);
409 written_bytes += m_bp.serialize(out, child,
"bp");
410 written_bytes += m_bp_rank.serialize(out, child,
"bp_rank");
412 written_bytes += m_maxval.serialize(out, child,
"maxval");
413 written_bytes += m_level_idx.
serialize(out, child,
"level_idx");
415 return written_bytes;
424 m_bp_rank.set_vector(&m_bp);
428 m_level_idx.
load(in);
432 template <
typename archive_t>
444 template <
typename archive_t>
450 m_bp_rank.set_vector(&m_bp);
459 return (m_t == other.m_t) && (m_bp == other.m_bp) && (m_bp_rank == other.m_bp_rank)
460 && (m_maxval == other.m_maxval) && (m_coord == other.m_coord) && (m_level_idx == other.m_level_idx);
466 return !(*
this == other);
471 return node_type(
t,
t_p(0, 0), 0, m_maxval[0],
t_p(m_coord[
t - 1][0], m_coord[
t - 1][1]));
476 return v.
idx >= m_bp.size();
481 using namespace k2_treap_ns;
482 std::vector<node_type> res;
485 uint64_t rank = m_bp_rank(v.
idx);
486 auto x = std::real(v.
p);
487 auto y = std::imag(v.
p);
489 for (
size_t i = 0; i < t_k; ++i)
491 for (
size_t j = 0; j < t_k; ++j)
495 if (m_bp[v.
idx + t_k * i + j])
499 auto _x = x + i * precomp<t_k>::exp(v.
t - 1);
500 auto _y = y + j * precomp<t_k>::exp(v.
t - 1);
502 auto _max_v = v.
max_v - m_maxval[rank];
503 auto _max_p =
t_p(_x, _y);
506 auto y = rank - m_level_idx[v.
t - 1];
507 _max_p =
t_p(_x + m_coord[v.
t - 2][2 * y], _y + m_coord[v.
t - 2][2 * y + 1]);
509 res.emplace_back(v.
t - 1,
t_p(_x, _y), rank * t_k * t_k, _max_v, _max_p);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
uint64_t size() const
Returns the number of elements currently stored.
void push_back(const uint64_t value)
Appends the given element value to the end of the int_vector_buffer.
A generic vector class for integers of width .
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.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
k2_treap(int_vector_buffer<> &buf_x, int_vector_buffer<> &buf_y, int_vector_buffer<> &buf_w, std::string temp_dir)
k2_treap & operator=(k2_treap &&tr)
Move assignment operator.
void load(std::istream &in)
Loads the data structure from the given istream.
k2_treap & operator=(k2_treap &tr)
Assignment operator.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
int_vector ::size_type size_type
std::vector< std::tuple< t_x, t_y, t_w > > read(std::vector< int_vector_buffer<> * > &bufs)
k2_treap(std::vector< std::tuple< t_x, t_y, t_w > > &v, std::string temp_dir=".")
std::vector< node_type > children(node_type const &v) const
bool is_leaf(node_type const &v) const
bool operator==(k2_treap const &other) const noexcept
Equality operator.
size_type size() const
Number of points in the 2^k treap.
k2_treap_ns::node_type node_type
bool operator!=(k2_treap const &other) const noexcept
Inequality operator.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
k2_treap_ns::point_type point_type
void construct(std::vector< std::tuple< t_x, t_y, t_w > > &v, std::string temp_dir=".")
k2_treap(k2_treap const &tr)
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)
dac_vector.hpp contains a vector which stores the values with variable length codes.
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
k2_treap_helper.hpp contains helper functions and definitions for a k^2-treap implementation.
std::complex< uint64_t > t_p
std::string to_string(T const &t, int w=1)
Namespace for the succinct data structure library.
int remove(std::string const &)
Remove a file.
void load_vector(std::vector< T > &, std::istream &)
Load all elements of a vector from a input stream.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
bool load_from_file(T &v, std::string const &file)
Load sdsl-object v from a file.
void read_member(T &t, std::istream &in)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
uint64_t serialize_vector(std::vector< T > const &, std::ostream &, sdsl::structure_tree_node *v=nullptr, std::string="")
Serialize each element of an std::vector.
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.