SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
k2_treap.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.
8#ifndef INCLUDED_SDSL_K2_TREAP
9#define INCLUDED_SDSL_K2_TREAP
10
11#include <algorithm>
12#include <complex>
13#include <ios>
14#include <limits>
15#include <stddef.h>
16#include <stdexcept>
17#include <stdint.h>
18#include <string>
19#include <tuple>
20#include <utility>
21#include <vector>
22
23#include <sdsl/bits.hpp>
24#include <sdsl/cereal.hpp>
25#include <sdsl/dac_vector.hpp>
26#include <sdsl/int_vector.hpp>
28#include <sdsl/io.hpp>
30#include <sdsl/ram_fs.hpp>
32#include <sdsl/util.hpp>
33
35namespace sdsl
36{
37
39
59template <uint8_t t_k,
60 typename t_bv = bit_vector,
61 typename t_rank = typename t_bv::rank_1_type,
62 typename t_max_vec = dac_vector<>>
64{
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.");
67
68public:
73
74 enum
75 {
76 k = t_k
77 };
78
79private:
80 uint8_t m_t = 0;
81 t_bv m_bp;
82 t_rank m_bp_rank;
83 t_max_vec m_maxval;
84 std::vector<int_vector<>> m_coord;
85 int_vector<64> m_level_idx;
86
87 template <typename t_tv>
88 uint8_t get_t(t_tv const & v)
89 {
90 using namespace k2_treap_ns;
91 if (v.size() == 0)
92 {
93 return 0;
94 }
95 using t_e = typename t_tv::value_type;
96 auto tupmax = [](t_e a)
97 {
98 return std::max(std::get<0>(a), std::get<1>(a));
99 };
100 auto max_it = std::max_element(std::begin(v),
101 std::end(v),
102 [&](t_e a, t_e b)
103 {
104 return tupmax(a) < tupmax(b);
105 });
106 uint64_t x = tupmax(*max_it);
107 uint8_t res = 0;
108 while (precomp<t_k>::exp(res) <= x)
109 {
110 ++res;
111 }
112 return res;
113 }
114
115public:
116 uint8_t & t = m_t;
117
118 k2_treap() = default;
119
120 k2_treap(k2_treap const & tr) :
121 m_t(tr.m_t),
122 m_bp(tr.m_bp),
123 m_bp_rank(tr.m_bp_rank),
124 m_maxval(tr.m_maxval),
125 m_coord(tr.m_coord),
126 m_level_idx(tr.m_level_idx)
127 {
128 m_bp_rank.set_vector(&m_bp);
129 }
130
132 {
133 *this = std::move(tr);
134 }
135
138 {
139 if (this != &tr)
140 {
141 m_t = tr.m_t;
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);
148 }
149 return *this;
150 }
151
154 {
155 if (this != &tr)
156 {
157 k2_treap tmp(tr);
158 *this = std::move(tmp);
159 }
160 return *this;
161 }
162
165 {
166 return m_maxval.size();
167 }
168
170 int_vector_buffer<> & buf_y,
171 int_vector_buffer<> & buf_w,
172 std::string temp_dir)
173 {
174 using namespace k2_treap_ns;
175 typedef int_vector_buffer<> * t_buf_p;
176 std::vector<t_buf_p> bufs = {&buf_x, &buf_y, &buf_w};
177
178 auto max_element = [](int_vector_buffer<> & buf)
179 {
180 uint64_t max_val = 0;
181 for (auto val : buf)
182 {
183 max_val = std::max((uint64_t)val, max_val);
184 }
185 return max_val;
186 };
187
188 auto max_buf_element = [&]()
189 {
190 uint64_t max_v = 0;
191 for (auto buf : bufs)
192 {
193 uint64_t _max_v = max_element(*buf);
194 max_v = std::max(max_v, _max_v);
195 }
196 return max_v;
197 };
198
199 uint64_t x = max_buf_element();
200 uint8_t res = 0;
201 while (res <= 64 and precomp<t_k>::exp(res) <= x)
202 {
203 ++res;
204 }
205 if (res == 65)
206 {
207 throw std::logic_error("Maximal element of input is too big.");
208 }
209
210 if (precomp<t_k>::exp(res) <= std::numeric_limits<uint32_t>::max())
211 {
212 auto v = read<uint32_t, uint32_t, uint32_t>(bufs);
213 construct(v, temp_dir);
214 }
215 else
216 {
217 auto v = read<uint64_t, uint64_t, uint64_t>(bufs);
218 construct(v, temp_dir);
219 }
220 }
221
222 template <typename t_x = uint64_t, typename t_y = uint64_t, typename t_w = uint64_t>
223 std::vector<std::tuple<t_x, t_y, t_w>> read(std::vector<int_vector_buffer<> *> & bufs)
224 {
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)
228 {
229 std::get<0>(v[j]) = (*(bufs[0]))[j];
230 }
231 for (uint64_t j = 0; j < v.size(); ++j)
232 {
233 std::get<1>(v[j]) = (*(bufs[1]))[j];
234 }
235 for (uint64_t j = 0; j < v.size(); ++j)
236 {
237 std::get<2>(v[j]) = (*(bufs[2]))[j];
238 }
239 return v;
240 }
241
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 = ".")
244 {
245 if (v.size() > 0)
246 {
247 construct(v, temp_dir);
248 }
249 }
250
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 = ".")
253 {
254 using namespace k2_treap_ns;
255 using t_e = std::tuple<t_x, t_y, t_w>;
256 m_t = get_t(v);
257 uint64_t M = precomp<t_k>::exp(t);
258 t_e MM = t_e(M, M, M);
259
260 std::string id_part = util::to_string(util::pid()) + "_" + util::to_string(util::id());
261
262 m_coord.resize(t);
263 m_level_idx = int_vector<64>(1 + t, 0);
264
265 std::string val_file = temp_dir + "/k2_treap_" + id_part + ".sdsl";
266 std::string bp_file = temp_dir + "/bp_" + id_part + ".sdsl";
267
268 {
269 int_vector_buffer<> val_buf(val_file, std::ios::out);
270 int_vector_buffer<1> bp_buf(bp_file, std::ios::out);
271
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)
276 {
277 if (l > 0)
278 {
279 m_level_idx[l - 1] = m_level_idx[l] + last_level_nodes;
280 m_coord[l - 1] = int_vector<>(2 * last_level_nodes, 0, bits::hi(precomp<t_k>::exp(l)) + 1);
281 }
282 level_nodes = 0;
283 cc = 0;
284 auto sp = std::begin(v);
285 for (auto ep = sp; ep != end;)
286 {
287 ep = std::find_if(sp,
288 end,
289 [&sp, &l](t_e const & e)
290 {
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);
297 });
298 auto max_it = std::max_element(sp,
299 ep,
300 [](t_e a, t_e b)
301 {
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);
307 });
308 if (l > 0)
309 {
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);
312 ++cc;
313 }
314
315 val_buf.push_back(std::get<2>(*max_it));
316 *max_it = MM;
317 --ep;
318 std::swap(*max_it, *ep);
319 if (l > 0)
320 {
321 auto _sp = sp;
322
323 for (uint8_t i = 0; i < t_k; ++i)
324 {
325 auto _ep = ep;
326 if (i + 1 < t_k)
327 {
328 _ep = std::partition(_sp,
329 ep,
330 [&i, &l](t_e const & e)
331 {
332 return precomp<t_k>::divexp(std::get<0>(e), l - 1) % t_k <= i;
333 });
334 }
335 auto __sp = _sp;
336 for (uint8_t j = 0; j < t_k; ++j)
337 {
338 auto __ep = _ep;
339 if (j + 1 < t_k)
340 {
341 __ep = std::partition(__sp,
342 _ep,
343 [&j, &l](t_e const & e)
344 {
345 return precomp<t_k>::divexp(std::get<1>(e), l - 1) % t_k
346 <= j;
347 });
348 }
349 bool not_empty = __ep > __sp;
350 bp_buf.push_back(not_empty);
351 level_nodes += not_empty;
352 __sp = __ep;
353 }
354 _sp = _ep;
355 }
356 }
357 ++ep;
358 sp = ep;
359 }
360 end = std::remove_if(begin(v),
361 end,
362 [&](t_e e)
363 {
364 return e == MM;
365 });
366 last_level_nodes = level_nodes;
367 }
368 }
369 bit_vector bp;
370 load_from_file(bp, bp_file);
371 {
372 int_vector_buffer<> val_rw(val_file, std::ios::in | std::ios::out);
373 int_vector_buffer<> val_r(val_file, std::ios::in);
374 uint64_t bp_idx = bp.size();
375 uint64_t r_idx = m_level_idx[0];
376 uint64_t rw_idx = val_rw.size();
377 while (bp_idx > 0)
378 {
379 --r_idx;
380 for (size_t i = 0; i < t_k * t_k; ++i)
381 {
382 if (bp[--bp_idx])
383 {
384 --rw_idx;
385 val_rw[rw_idx] = val_r[r_idx] - val_rw[rw_idx];
386 }
387 }
388 }
389 }
390 {
391 int_vector_buffer<> val_r(val_file);
392 m_maxval = t_max_vec(val_r);
393 }
394 {
395 bit_vector _bp(std::move(bp));
396 m_bp = t_bv(_bp);
397 }
398 util::init_support(m_bp_rank, &m_bp);
399 sdsl::remove(bp_file);
400 sdsl::remove(val_file);
401 }
402
404 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
405 {
406 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
407 size_type written_bytes = 0;
408 written_bytes += write_member(m_t, out, child, "t");
409 written_bytes += m_bp.serialize(out, child, "bp");
410 written_bytes += m_bp_rank.serialize(out, child, "bp_rank");
411 written_bytes += serialize_vector(m_coord, out, child, "coord");
412 written_bytes += m_maxval.serialize(out, child, "maxval");
413 written_bytes += m_level_idx.serialize(out, child, "level_idx");
414 structure_tree::add_size(child, written_bytes);
415 return written_bytes;
416 }
417
419 void load(std::istream & in)
420 {
421 read_member(m_t, in);
422 m_bp.load(in);
423 m_bp_rank.load(in);
424 m_bp_rank.set_vector(&m_bp);
425 m_coord.resize(t);
426 load_vector(m_coord, in);
427 m_maxval.load(in);
428 m_level_idx.load(in);
429 }
430
432 template <typename archive_t>
433 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
434 {
435 ar(CEREAL_NVP(m_t));
436 ar(CEREAL_NVP(m_bp));
437 ar(CEREAL_NVP(m_bp_rank));
438 ar(CEREAL_NVP(m_coord));
439 ar(CEREAL_NVP(m_maxval));
440 ar(CEREAL_NVP(m_level_idx));
441 }
442
444 template <typename archive_t>
445 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
446 {
447 ar(CEREAL_NVP(m_t));
448 ar(CEREAL_NVP(m_bp));
449 ar(CEREAL_NVP(m_bp_rank));
450 m_bp_rank.set_vector(&m_bp);
451 ar(CEREAL_NVP(m_coord));
452 ar(CEREAL_NVP(m_maxval));
453 ar(CEREAL_NVP(m_level_idx));
454 }
455
457 bool operator==(k2_treap const & other) const noexcept
458 {
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);
461 }
462
464 bool operator!=(k2_treap const & other) const noexcept
465 {
466 return !(*this == other);
467 }
468
470 {
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]));
472 }
473
474 bool is_leaf(node_type const & v) const
475 {
476 return v.idx >= m_bp.size();
477 }
478
479 std::vector<node_type> children(node_type const & v) const
480 {
481 using namespace k2_treap_ns;
482 std::vector<node_type> res;
483 if (!is_leaf(v))
484 {
485 uint64_t rank = m_bp_rank(v.idx);
486 auto x = std::real(v.p);
487 auto y = std::imag(v.p);
488
489 for (size_t i = 0; i < t_k; ++i)
490 {
491 for (size_t j = 0; j < t_k; ++j)
492 {
493 // get_int better for compressed bitvectors
494 // or introduce cache for bitvectors
495 if (m_bp[v.idx + t_k * i + j])
496 {
497 ++rank;
498
499 auto _x = x + i * precomp<t_k>::exp(v.t - 1);
500 auto _y = y + j * precomp<t_k>::exp(v.t - 1);
501
502 auto _max_v = v.max_v - m_maxval[rank];
503 auto _max_p = t_p(_x, _y);
504 if (v.t > 1)
505 {
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]);
508 }
509 res.emplace_back(v.t - 1, t_p(_x, _y), rank * t_k * t_k, _max_v, _max_p);
510 }
511 }
512 }
513 }
514 return res;
515 }
516};
517} // namespace sdsl
518#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
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.
A k^2-treap.
Definition k2_treap.hpp:64
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition k2_treap.hpp:433
k2_treap()=default
k2_treap(int_vector_buffer<> &buf_x, int_vector_buffer<> &buf_y, int_vector_buffer<> &buf_w, std::string temp_dir)
Definition k2_treap.hpp:169
k2_treap & operator=(k2_treap &&tr)
Move assignment operator.
Definition k2_treap.hpp:137
void load(std::istream &in)
Loads the data structure from the given istream.
Definition k2_treap.hpp:419
k2_treap & operator=(k2_treap &tr)
Assignment operator.
Definition k2_treap.hpp:153
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Definition k2_treap.hpp:445
k2_treap(k2_treap &&tr)
Definition k2_treap.hpp:131
std::vector< std::tuple< t_x, t_y, t_w > > read(std::vector< int_vector_buffer<> * > &bufs)
Definition k2_treap.hpp:223
k2_treap(std::vector< std::tuple< t_x, t_y, t_w > > &v, std::string temp_dir=".")
Definition k2_treap.hpp:243
k2_treap_ns::t_p t_p
Definition k2_treap.hpp:72
std::vector< node_type > children(node_type const &v) const
Definition k2_treap.hpp:479
uint8_t & t
Definition k2_treap.hpp:116
bool is_leaf(node_type const &v) const
Definition k2_treap.hpp:474
bool operator==(k2_treap const &other) const noexcept
Equality operator.
Definition k2_treap.hpp:457
size_type size() const
Number of points in the 2^k treap.
Definition k2_treap.hpp:164
k2_treap_ns::node_type node_type
Definition k2_treap.hpp:70
bool operator!=(k2_treap const &other) const noexcept
Inequality operator.
Definition k2_treap.hpp:464
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
Definition k2_treap.hpp:404
node_type root() const
Definition k2_treap.hpp:469
k2_treap_ns::point_type point_type
Definition k2_treap.hpp:71
int_vector ::size_type size_type
Definition k2_treap.hpp:69
void construct(std::vector< std::tuple< t_x, t_y, t_w > > &v, std::string temp_dir=".")
Definition k2_treap.hpp:252
k2_treap(k2_treap const &tr)
Definition k2_treap.hpp:120
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
uint64_t id()
uint64_t pid()
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.
Definition ram_fs.hpp:221
void load_vector(std::vector< T > &, std::istream &)
Load all elements of a vector from a input stream.
Definition io.hpp:425
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
bool load_from_file(T &v, std::string const &file)
Load sdsl-object v from a file.
Definition io.hpp:989
void read_member(T &t, std::istream &in)
Definition io.hpp:119
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.
Definition io.hpp:397
ram_fs.hpp
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
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.