SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
k2_treap_algorithm.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_ALGORITHM
9#define INCLUDED_SDSL_K2_TREAP_ALGORITHM
10
11#include <array>
12#include <complex>
13#include <cstdint>
14#include <iosfwd>
15#include <queue>
16#include <string>
17#include <tuple>
18#include <utility>
19#include <vector>
20
21#include <sdsl/config.hpp>
24#include <sdsl/ram_fs.hpp>
25
27namespace sdsl
28{
29
30namespace k2_treap_ns
31{
32
34
38inline bool contained(const point_type p, point_type const & p1, point_type const & p2)
39{
40 return real(p) >= real(p1) and real(p) <= real(p2) and imag(p) >= imag(p1) and imag(p) <= imag(p2);
41}
42
44template <uint8_t t_k>
45bool contained(point_type const & p1, point_type const & p2, node_type const & v)
46{
47 // uint64_t d = (1ULL << v.t)-1;
48 // uint64_t d = (1ULL << v.t)-1;
49 uint64_t d = precomp<t_k>::exp(v.t) - 1;
50 return real(p1) <= real(v.p) and real(p2) >= real(v.p) + d and imag(p1) <= imag(v.p) and imag(p2) >= imag(v.p) + d;
51}
52
54template <uint8_t t_k>
55bool overlap(point_type const & p1, point_type const & p2, node_type const & v)
56{
57 // uint64_t d = (1ULL << v.t)-1;
58 uint64_t d = precomp<t_k>::exp(v.t) - 1;
59 return real(p1) <= real(v.p) + d and real(p2) >= real(v.p) and imag(p1) <= imag(v.p) + d and imag(p2) >= imag(v.p);
60}
61
62template <typename t_k2_treap>
64{
65public:
66 typedef void (*t_mfptr)();
67 typedef std::pair<point_type, uint64_t> t_point_val;
68
69private:
71 typedef std::pair<node_type, bool> t_nt_b;
72
73 t_k2_treap const * m_treap = nullptr;
74 std::priority_queue<t_nt_b> m_pq;
75 t_point_val m_point_val;
76 point_type m_p1;
77 point_type m_p2;
78 bool m_valid = false;
79
80public:
81 top_k_iterator() = default;
82 top_k_iterator(top_k_iterator const &) = default;
86 top_k_iterator(t_k2_treap const & treap, point_type p1, point_type p2) :
87 m_treap(&treap),
88 m_p1(p1),
89 m_p2(p2),
90 m_valid(treap.size() > 0)
91 {
92 if (m_treap->size() > 0)
93 {
94 m_pq.emplace(m_treap->root(), false);
95 ++(*this);
96 }
97 }
98
101 {
102 m_valid = false;
103 while (!m_pq.empty())
104 {
105 auto v = std::get<0>(m_pq.top());
106 auto is_contained = std::get<1>(m_pq.top());
107 m_pq.pop();
108 if (is_contained)
109 {
110 auto nodes = m_treap->children(v);
111 for (auto node : nodes)
112 m_pq.emplace(node, true);
113 m_point_val = t_point_val(v.max_p, v.max_v);
114 m_valid = true;
115 break;
116 }
117 else
118 {
119 if (contained<t_k2_treap::k>(m_p1, m_p2, v))
120 {
121 m_pq.emplace(v, true);
122 }
123 else if (overlap<t_k2_treap::k>(m_p1, m_p2, v))
124 {
125 auto nodes = m_treap->children(v);
126 for (auto node : nodes)
127 m_pq.emplace(node, false);
128 if (contained(v.max_p, m_p1, m_p2))
129 {
130 m_point_val = t_point_val(v.max_p, v.max_v);
131 m_valid = true;
132 break;
133 }
134 }
135 }
136 }
137 return *this;
138 }
139
142 {
143 top_k_iterator it = *this;
144 ++(*this);
145 return it;
146 }
147
149 {
150 return m_point_val;
151 }
152
154 // Test if there are more elements
155 // Can be casted to bool but not implicit in an arithmetic experession
156 // See Alexander C.'s comment on
157 // http://stackoverflow.com/questions/835590/how-would-stdostringstream-convert-to-bool
158 operator t_mfptr() const
159 {
160 return (t_mfptr)(m_valid);
161 }
162};
163
164template <typename t_k2_treap>
166{
167public:
168 typedef void (*t_mfptr)();
169 typedef std::pair<point_type, uint64_t> t_point_val;
170
171private:
173 typedef std::pair<node_type, bool> t_nt_b;
174
175 t_k2_treap const * m_treap = nullptr;
176 std::priority_queue<t_nt_b> m_pq;
177 t_point_val m_point_val;
178 point_type m_p1;
179 point_type m_p2;
180 range_type m_r;
181 bool m_valid = false;
182
183 void pq_emplace(node_type v, bool b)
184 {
185 if (v.max_v >= real(m_r))
186 {
187 m_pq.emplace(v, b);
188 }
189 }
190
191public:
192 range_iterator() = default;
193 range_iterator(range_iterator const &) = default;
197 range_iterator(t_k2_treap const & treap, point_type p1, point_type p2, range_type range) :
198 m_treap(&treap),
199 m_p1(p1),
200 m_p2(p2),
201 m_r(range),
202 m_valid(treap.size() > 0)
203 {
204 if (m_treap->size() > 0)
205 {
206 pq_emplace(m_treap->root(), false);
207 ++(*this);
208 }
209 }
210
213 {
214 m_valid = false;
215 while (!m_pq.empty())
216 {
217 auto v = std::get<0>(m_pq.top());
218 auto is_contained = std::get<1>(m_pq.top());
219 m_pq.pop();
220 if (is_contained)
221 {
222 auto nodes = m_treap->children(v);
223 for (auto node : nodes)
224 pq_emplace(node, true);
225 if (v.max_v <= imag(m_r))
226 {
227 m_point_val = t_point_val(v.max_p, v.max_v);
228 m_valid = true;
229 break;
230 }
231 }
232 else
233 {
234 if (contained<t_k2_treap::k>(m_p1, m_p2, v))
235 {
236 m_pq.emplace(v, true);
237 }
238 else if (overlap<t_k2_treap::k>(m_p1, m_p2, v))
239 {
240 auto nodes = m_treap->children(v);
241 for (auto node : nodes)
242 pq_emplace(node, false);
243 if (contained(v.max_p, m_p1, m_p2) and v.max_v <= imag(m_r))
244 {
245 m_point_val = t_point_val(v.max_p, v.max_v);
246 m_valid = true;
247 break;
248 }
249 }
250 }
251 }
252 return *this;
253 }
254
257 {
258 range_iterator it = *this;
259 ++(*this);
260 return it;
261 }
262
264 {
265 return m_point_val;
266 }
267
269 // Test if there are more elements
270 operator t_mfptr() const
271 {
272 return (t_mfptr)(m_valid);
273 }
274};
275
276} // end namespace k2_treap_ns
277
279
285template <typename t_k2_treap>
286k2_treap_ns::top_k_iterator<t_k2_treap>
288{
290}
291
293
301template <typename t_k2_treap>
302k2_treap_ns::range_iterator<t_k2_treap>
304{
305 return k2_treap_ns::range_iterator<t_k2_treap>(t, p1, p2, range);
306}
307
308// forward declaration
309template <typename t_k2_treap>
310uint64_t __count(t_k2_treap const &, typename t_k2_treap::node_type);
311
312// forward declaration
313template <typename t_k2_treap>
314uint64_t _count(t_k2_treap const &, k2_treap_ns::point_type, k2_treap_ns::point_type, typename t_k2_treap::node_type);
315
317
323template <typename t_k2_treap>
324uint64_t count(t_k2_treap const & treap, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
325{
326 if (treap.size() > 0)
327 {
328 return _count(treap, p1, p2, treap.root());
329 }
330 return 0;
331}
332
333template <typename t_k2_treap>
334uint64_t _count(t_k2_treap const & treap,
337 typename t_k2_treap::node_type v)
338{
339 using namespace k2_treap_ns;
340 if (contained<t_k2_treap::k>(p1, p2, v))
341 {
342 return __count(treap, v);
343 }
344 else if (overlap<t_k2_treap::k>(p1, p2, v))
345 {
346 uint64_t res = contained(v.max_p, p1, p2);
347 auto nodes = treap.children(v);
348 for (auto node : nodes)
349 {
350 res += _count(treap, p1, p2, node);
351 }
352 return res;
353 }
354 return 0;
355}
356
357template <typename t_k2_treap>
358uint64_t __count(t_k2_treap const & treap, typename t_k2_treap::node_type v)
359{
360 uint64_t res = 1; // count the point at the node
361 auto nodes = treap.children(v);
362 for (auto node : nodes)
363 res += __count(treap, node);
364 return res;
365}
366
367// forward declaration
368template <uint8_t t_k, typename t_bv, typename t_rank, typename t_max_vec>
370
372template <uint8_t t_k, typename t_bv, typename t_rank, typename t_max_vec>
373void construct(k2_treap<t_k, t_bv, t_rank, t_max_vec> & idx, std::string file, cache_config & config)
374{
375 int_vector_buffer<> buf_x(file + ".x", std::ios::in);
376 int_vector_buffer<> buf_y(file + ".y", std::ios::in);
377 int_vector_buffer<> buf_w(file + ".w", std::ios::in);
378 idx = k2_treap<t_k, t_bv, t_rank, t_max_vec>(buf_x, buf_y, buf_w, config.dir);
379}
380
382template <uint8_t t_k, typename t_bv, typename t_rank, typename t_max_vec>
383void construct_im(k2_treap<t_k, t_bv, t_rank, t_max_vec> & idx, std::vector<std::array<uint64_t, 3>> data)
384{
385 std::string tmp_dir = ram_file_name("/tmp");
386 std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> d;
387 for (auto x : data)
388 {
389 d.push_back(std::make_tuple(x[0], x[1], x[2]));
390 }
392}
393
394} // namespace sdsl
395#endif
range_iterator & operator++()
Prefix increment of the iterator.
std::pair< point_type, uint64_t > t_point_val
range_iterator(t_k2_treap const &treap, point_type p1, point_type p2, range_type range)
range_iterator(range_iterator &&)=default
range_iterator(range_iterator const &)=default
range_iterator & operator=(range_iterator const &)=default
range_iterator operator++(int)
Postfix increment of the iterator.
range_iterator & operator=(range_iterator &&)=default
top_k_iterator(top_k_iterator &&)=default
top_k_iterator(t_k2_treap const &treap, point_type p1, point_type p2)
std::pair< point_type, uint64_t > t_point_val
top_k_iterator & operator=(top_k_iterator &&)=default
top_k_iterator & operator=(top_k_iterator const &)=default
top_k_iterator(top_k_iterator const &)=default
top_k_iterator operator++(int)
Postfix increment of the iterator.
top_k_iterator & operator++()
Prefix increment of the iterator.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
k2_treap_helper.hpp contains helper functions and definitions for a k^2-treap implementation.
bool overlap(point_type const &p1, point_type const &p2, node_type const &v)
Check if rectangle (p1,p2) and the area of node v overlap.
bool contained(const point_type p, point_type const &p1, point_type const &p2)
Check if point x is contained in the rectangle (p1,p2)
Namespace for the succinct data structure library.
uint64_t _count(t_k2_treap const &, k2_treap_ns::point_type, k2_treap_ns::point_type, typename t_k2_treap::node_type)
uint64_t __count(t_k2_treap const &, typename t_k2_treap::node_type)
std::string ram_file_name(std::string const &file)
Returns the corresponding RAM-file name for file.
Definition ram_fs.hpp:195
uint64_t count(t_k2_treap const &treap, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
Count how many points are in the rectangle (p1,p2)
void construct(t_index &idx, std::string file, uint8_t num_bytes=0, bool move_input=false)
Definition construct.hpp:56
int_vector ::size_type size(range_type const &r)
Size of a range.
k2_treap_ns::top_k_iterator< t_k2_treap > top_k(t_k2_treap const &t, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
Get iterator for all heaviest points in rectangle (p1,p2) in decreasing order.
k2_treap_ns::range_iterator< t_k2_treap > range_3d(t_k2_treap const &t, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2, k2_treap_ns::range_type range)
Get iterator for all points in rectangle (p1,p2) with weights in range.
void construct_im(t_index &idx, t_data &&data, uint8_t num_bytes=0)
Definition construct.hpp:69
ram_fs.hpp
Helper class for construction process.
Definition config.hpp:66
std::string dir
Definition config.hpp:70
static uint64_t exp(uint8_t l)