8 #ifndef INCLUDED_SDSL_K2_TREAP
9 #define INCLUDED_SDSL_K2_TREAP
46 template <uint8_t t_k,
48 typename t_rank =
typename t_bv::rank_1_type,
49 typename t_max_vec = dac_vector<>>
52 static_assert(t_k > 1,
"t_k has to be larger than 1.");
53 static_assert(t_k <= 16,
"t_k has to be smaller than 17.");
71 std::vector<int_vector<>> m_coord;
74 template <
typename t_tv>
75 uint8_t get_t(
const t_tv & v)
77 using namespace k2_treap_ns;
78 if (v.size() == 0) {
return 0; }
79 using t_e =
typename t_tv::value_type;
80 auto tupmax = [](t_e a) {
return std::max(std::get<0>(a), std::get<1>(a)); };
81 auto max_it = std::max_element(std::begin(v), std::end(v), [&](t_e a, t_e b) {
return tupmax(a) < tupmax(b); });
82 uint64_t x = tupmax(*max_it);
84 while (precomp<t_k>::exp(res) <= x) { ++res; }
96 , m_bp_rank(tr.m_bp_rank)
97 , m_maxval(tr.m_maxval)
99 , m_level_idx(tr.m_level_idx)
101 m_bp_rank.set_vector(&m_bp);
112 m_bp = std::move(tr.m_bp);
113 m_bp_rank = std::move(tr.m_bp_rank);
114 m_bp_rank.set_vector(&m_bp);
115 m_maxval = std::move(tr.m_maxval);
116 m_coord = std::move(tr.m_coord);
117 m_level_idx = std::move(tr.m_level_idx);
128 *
this = std::move(tmp);
139 std::string temp_dir)
141 using namespace k2_treap_ns;
143 std::vector<t_buf_p> bufs = { &buf_x, &buf_y, &buf_w };
146 uint64_t max_val = 0;
147 for (
auto val : buf) { max_val = std::max((uint64_t)val, max_val); }
151 auto max_buf_element = [&]() {
153 for (
auto buf : bufs)
155 uint64_t _max_v = max_element(*buf);
156 max_v = std::max(max_v, _max_v);
161 uint64_t x = max_buf_element();
163 while (res <= 64 and precomp<t_k>::exp(res) <= x) { ++res; }
164 if (res == 65) {
throw std::logic_error(
"Maximal element of input is too big."); }
166 if (precomp<t_k>::exp(res) <= std::numeric_limits<uint32_t>::max())
168 auto v = read<uint32_t, uint32_t, uint32_t>(bufs);
173 auto v = read<uint64_t, uint64_t, uint64_t>(bufs);
178 template <
typename t_x = u
int64_t,
typename t_y = u
int64_t,
typename t_w = u
int64_t>
181 typedef std::vector<std::tuple<t_x, t_y, t_w>> t_tuple_vec;
182 t_tuple_vec v = t_tuple_vec(bufs[0]->
size());
183 for (uint64_t j = 0; j < v.size(); ++j) { std::get<0>(v[j]) = (*(bufs[0]))[j]; }
184 for (uint64_t j = 0; j < v.size(); ++j) { std::get<1>(v[j]) = (*(bufs[1]))[j]; }
185 for (uint64_t j = 0; j < v.size(); ++j) { std::get<2>(v[j]) = (*(bufs[2]))[j]; }
189 template <
typename t_x,
typename t_y,
typename t_w>
190 k2_treap(std::vector<std::tuple<t_x, t_y, t_w>> & v, std::string temp_dir =
".")
192 if (v.size() > 0) {
construct(v, temp_dir); }
195 template <
typename t_x,
typename t_y,
typename t_w>
196 void construct(std::vector<std::tuple<t_x, t_y, t_w>> & v, std::string temp_dir =
".")
198 using namespace k2_treap_ns;
199 using t_e = std::tuple<t_x, t_y, t_w>;
201 uint64_t M = precomp<t_k>::exp(
t);
202 t_e MM = t_e(M, M, M);
209 std::string val_file = temp_dir +
"/k2_treap_" + id_part +
".sdsl";
210 std::string bp_file = temp_dir +
"/bp_" + id_part +
".sdsl";
216 auto end = std::end(v);
217 uint64_t last_level_nodes = 1;
218 uint64_t level_nodes;
219 for (uint64_t l =
t, cc = 0; l + 1 > 0; --l)
223 m_level_idx[l - 1] = m_level_idx[l] + last_level_nodes;
228 auto sp = std::begin(v);
229 for (
auto ep = sp; ep != end;)
231 ep = std::find_if(sp, end, [&sp, &l](
const t_e & e) {
232 auto x1 = std::get<0>(*sp);
233 auto y1 = std::get<1>(*sp);
234 auto x2 = std::get<0>(e);
235 auto y2 = std::get<1>(e);
236 return precomp<t_k>::divexp(x1, l) != precomp<t_k>::divexp(x2, l) or
237 precomp<t_k>::divexp(y1, l) != precomp<t_k>::divexp(y2, l);
239 auto max_it = std::max_element(sp, ep, [](t_e a, t_e b) {
240 if (std::get<2>(a) != std::get<2>(b))
241 return std::get<2>(a) < std::get<2>(b);
242 else if (std::get<0>(a) != std::get<0>(b))
243 return std::get<0>(a) > std::get<0>(b);
244 return std::get<1>(a) > std::get<1>(b);
248 m_coord[l - 1][2 * cc] = precomp<t_k>::modexp(std::get<0>(*max_it), l);
249 m_coord[l - 1][2 * cc + 1] = precomp<t_k>::modexp(std::get<1>(*max_it), l);
261 for (uint8_t i = 0; i < t_k; ++i)
266 _ep = std::partition(_sp, ep, [&i, &l](
const t_e & e) {
267 return precomp<t_k>::divexp(std::get<0>(e), l - 1) % t_k <= i;
271 for (uint8_t j = 0; j < t_k; ++j)
276 __ep = std::partition(__sp, _ep, [&j, &l](
const t_e & e) {
277 return precomp<t_k>::divexp(std::get<1>(e), l - 1) % t_k <= j;
280 bool not_empty = __ep > __sp;
282 level_nodes += not_empty;
291 end = std::remove_if(begin(v), end, [&](t_e e) {
return e == MM; });
292 last_level_nodes = level_nodes;
300 uint64_t bp_idx = bp.
size();
301 uint64_t r_idx = m_level_idx[0];
302 uint64_t rw_idx = val_rw.
size();
306 for (
size_t i = 0; i < t_k * t_k; ++i)
311 val_rw[rw_idx] = val_r[r_idx] - val_rw[rw_idx];
318 m_maxval = t_max_vec(val_r);
324 util::init_support(m_bp_rank, &m_bp);
335 written_bytes += m_bp.serialize(out, child,
"bp");
336 written_bytes += m_bp_rank.serialize(out, child,
"bp_rank");
338 written_bytes += m_maxval.serialize(out, child,
"maxval");
339 written_bytes += m_level_idx.
serialize(out, child,
"level_idx");
341 return written_bytes;
350 m_bp_rank.set_vector(&m_bp);
354 m_level_idx.
load(in);
358 template <
typename archive_t>
370 template <
typename archive_t>
376 m_bp_rank.set_vector(&m_bp);
385 return (m_t == other.m_t) && (m_bp == other.m_bp) && (m_bp_rank == other.m_bp_rank) &&
386 (m_maxval == other.m_maxval) && (m_coord == other.m_coord) && (m_level_idx == other.m_level_idx);
394 return node_type(
t,
t_p(0, 0), 0, m_maxval[0],
t_p(m_coord[
t - 1][0], m_coord[
t - 1][1]));
401 using namespace k2_treap_ns;
402 std::vector<node_type> res;
405 uint64_t rank = m_bp_rank(v.
idx);
406 auto x = std::real(v.
p);
407 auto y = std::imag(v.
p);
409 for (
size_t i = 0; i < t_k; ++i)
411 for (
size_t j = 0; j < t_k; ++j)
415 if (m_bp[v.
idx + t_k * i + j])
419 auto _x = x + i * precomp<t_k>::exp(v.
t - 1);
420 auto _y = y + j * precomp<t_k>::exp(v.
t - 1);
422 auto _max_v = v.
max_v - m_maxval[rank];
423 auto _max_p =
t_p(_x, _y);
426 auto y = rank - m_level_idx[v.
t - 1];
427 _max_p =
t_p(_x + m_coord[v.
t - 2][2 * y], _y + m_coord[v.
t - 2][2 * y + 1]);
429 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.
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 .
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(std::vector< std::tuple< t_x, t_y, t_w >> &v, std::string temp_dir=".")
k2_treap(int_vector_buffer<> &buf_x, int_vector_buffer<> &buf_y, int_vector_buffer<> &buf_w, std::string temp_dir)
void load(std::istream &in)
Loads the data structure from the given istream.
void construct(std::vector< std::tuple< t_x, t_y, t_w >> &v, std::string temp_dir=".")
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
std::vector< node_type > children(const node_type &v) const
bool operator==(k2_treap const &other) const noexcept
Equality operator.
k2_treap & operator=(k2_treap &&tr)
Move assignment operator.
k2_treap & operator=(k2_treap &tr)
Assignment operator.
size_type size() const
Number of points in the 2^k treap.
k2_treap_ns::node_type node_type
std::vector< std::tuple< t_x, t_y, t_w > > read(std::vector< int_vector_buffer<> * > &bufs)
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
int_vector ::size_type size_type
bool is_leaf(const node_type &v) const
k2_treap(const k2_treap &tr)
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)
k2_treap_algorithm.hpp contains k^2-treap algorithms.
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(const T &t, int w=1)
Namespace for the succinct data structure library.
void load_vector(std::vector< T > &, std::istream &)
Load all elements of a vector from a input stream.
uint64_t serialize_vector(const std::vector< T > &, std::ostream &, sdsl::structure_tree_node *v=nullptr, std::string="")
Serialize each element of an std::vector.
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
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.
bool load_from_file(T &v, const std::string &file)
Load sdsl-object v from a file.
int remove(const std::string &)
Remove a file.
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.