SDSL 3.0.1
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 <algorithm>
12#include <array>
13#include <climits>
14#include <complex>
15#include <iterator>
16#include <queue>
17#include <tuple>
18#include <vector>
19
20#include <sdsl/bits.hpp>
22#include <sdsl/vectors.hpp>
23
25namespace sdsl
26{
27
28namespace k2_treap_ns
29{
30
32
36inline bool contained(const point_type p, const point_type & p1, const point_type & p2)
37{
38 return real(p) >= real(p1) and real(p) <= real(p2) and imag(p) >= imag(p1) and imag(p) <= imag(p2);
39}
40
42template <uint8_t t_k>
43bool contained(const point_type & p1, const point_type & p2, const node_type & v)
44{
45 // uint64_t d = (1ULL << v.t)-1;
46 // uint64_t d = (1ULL << v.t)-1;
47 uint64_t d = precomp<t_k>::exp(v.t) - 1;
48 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;
49}
50
52template <uint8_t t_k>
53bool overlap(const point_type & p1, const point_type & p2, const node_type & v)
54{
55 // uint64_t d = (1ULL << v.t)-1;
56 uint64_t d = precomp<t_k>::exp(v.t) - 1;
57 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);
58}
59
60template <typename t_k2_treap>
62{
63 public:
64 typedef void (*t_mfptr)();
65 typedef std::pair<point_type, uint64_t> t_point_val;
66
67 private:
69 typedef std::pair<node_type, bool> t_nt_b;
70
71 const t_k2_treap * m_treap = nullptr;
72 std::priority_queue<t_nt_b> m_pq;
73 t_point_val m_point_val;
74 point_type m_p1;
75 point_type m_p2;
76 bool m_valid = false;
77
78 public:
79 top_k_iterator() = default;
80 top_k_iterator(const top_k_iterator &) = default;
84 top_k_iterator(const t_k2_treap & treap, point_type p1, point_type p2)
85 : m_treap(&treap)
86 , m_p1(p1)
87 , m_p2(p2)
88 , m_valid(treap.size() > 0)
89 {
90 if (m_treap->size() > 0)
91 {
92 m_pq.emplace(m_treap->root(), false);
93 ++(*this);
94 }
95 }
96
99 {
100 m_valid = false;
101 while (!m_pq.empty())
102 {
103 auto v = std::get<0>(m_pq.top());
104 auto is_contained = std::get<1>(m_pq.top());
105 m_pq.pop();
106 if (is_contained)
107 {
108 auto nodes = m_treap->children(v);
109 for (auto node : nodes) m_pq.emplace(node, true);
110 m_point_val = t_point_val(v.max_p, v.max_v);
111 m_valid = true;
112 break;
113 }
114 else
115 {
116 if (contained<t_k2_treap::k>(m_p1, m_p2, v)) { m_pq.emplace(v, true); }
117 else if (overlap<t_k2_treap::k>(m_p1, m_p2, v))
118 {
119 auto nodes = m_treap->children(v);
120 for (auto node : nodes) m_pq.emplace(node, false);
121 if (contained(v.max_p, m_p1, m_p2))
122 {
123 m_point_val = t_point_val(v.max_p, v.max_v);
124 m_valid = true;
125 break;
126 }
127 }
128 }
129 }
130 return *this;
131 }
132
135 {
136 top_k_iterator it = *this;
137 ++(*this);
138 return it;
139 }
140
141 t_point_val operator*() const { return m_point_val; }
142
144 // Test if there are more elements
145 // Can be casted to bool but not implicit in an arithmetic experession
146 // See Alexander C.'s comment on
147 // http://stackoverflow.com/questions/835590/how-would-stdostringstream-convert-to-bool
148 operator t_mfptr() const { return (t_mfptr)(m_valid); }
149};
150
151template <typename t_k2_treap>
153{
154 public:
155 typedef void (*t_mfptr)();
156 typedef std::pair<point_type, uint64_t> t_point_val;
157
158 private:
160 typedef std::pair<node_type, bool> t_nt_b;
161
162 const t_k2_treap * m_treap = nullptr;
163 std::priority_queue<t_nt_b> m_pq;
164 t_point_val m_point_val;
165 point_type m_p1;
166 point_type m_p2;
167 range_type m_r;
168 bool m_valid = false;
169
170 void pq_emplace(node_type v, bool b)
171 {
172 if (v.max_v >= real(m_r)) { m_pq.emplace(v, b); }
173 }
174
175 public:
176 range_iterator() = default;
177 range_iterator(const range_iterator &) = default;
181 range_iterator(const t_k2_treap & treap, point_type p1, point_type p2, range_type range)
182 : m_treap(&treap)
183 , m_p1(p1)
184 , m_p2(p2)
185 , m_r(range)
186 , m_valid(treap.size() > 0)
187 {
188 if (m_treap->size() > 0)
189 {
190 pq_emplace(m_treap->root(), false);
191 ++(*this);
192 }
193 }
194
197 {
198 m_valid = false;
199 while (!m_pq.empty())
200 {
201 auto v = std::get<0>(m_pq.top());
202 auto is_contained = std::get<1>(m_pq.top());
203 m_pq.pop();
204 if (is_contained)
205 {
206 auto nodes = m_treap->children(v);
207 for (auto node : nodes) pq_emplace(node, true);
208 if (v.max_v <= imag(m_r))
209 {
210 m_point_val = t_point_val(v.max_p, v.max_v);
211 m_valid = true;
212 break;
213 }
214 }
215 else
216 {
217 if (contained<t_k2_treap::k>(m_p1, m_p2, v)) { m_pq.emplace(v, true); }
218 else if (overlap<t_k2_treap::k>(m_p1, m_p2, v))
219 {
220 auto nodes = m_treap->children(v);
221 for (auto node : nodes) pq_emplace(node, false);
222 if (contained(v.max_p, m_p1, m_p2) and v.max_v <= imag(m_r))
223 {
224 m_point_val = t_point_val(v.max_p, v.max_v);
225 m_valid = true;
226 break;
227 }
228 }
229 }
230 }
231 return *this;
232 }
233
236 {
237 range_iterator it = *this;
238 ++(*this);
239 return it;
240 }
241
242 t_point_val operator*() const { return m_point_val; }
243
245 // Test if there are more elements
246 operator t_mfptr() const { return (t_mfptr)(m_valid); }
247};
248
249} // end namespace k2_treap_ns
250
252
258template <typename t_k2_treap>
262{
264}
265
267
275template <typename t_k2_treap>
280{
281 return k2_treap_ns::range_iterator<t_k2_treap>(t, p1, p2, range);
282}
283
284// forward declaration
285template <typename t_k2_treap>
286uint64_t __count(const t_k2_treap &, typename t_k2_treap::node_type);
287
288// forward declaration
289template <typename t_k2_treap>
290uint64_t _count(const t_k2_treap &, k2_treap_ns::point_type, k2_treap_ns::point_type, typename t_k2_treap::node_type);
291
293
299template <typename t_k2_treap>
300uint64_t count(const t_k2_treap & treap, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
301{
302 if (treap.size() > 0) { return _count(treap, p1, p2, treap.root()); }
303 return 0;
304}
305
306template <typename t_k2_treap>
307uint64_t _count(const t_k2_treap & treap,
310 typename t_k2_treap::node_type v)
311{
312 using namespace k2_treap_ns;
313 if (contained<t_k2_treap::k>(p1, p2, v)) { return __count(treap, v); }
314 else if (overlap<t_k2_treap::k>(p1, p2, v))
315 {
316 uint64_t res = contained(v.max_p, p1, p2);
317 auto nodes = treap.children(v);
318 for (auto node : nodes) { res += _count(treap, p1, p2, node); }
319 return res;
320 }
321 return 0;
322}
323
324template <typename t_k2_treap>
325uint64_t __count(const t_k2_treap & treap, typename t_k2_treap::node_type v)
326{
327 uint64_t res = 1; // count the point at the node
328 auto nodes = treap.children(v);
329 for (auto node : nodes) res += __count(treap, node);
330 return res;
331}
332
333// forward declaration
334template <uint8_t t_k, typename t_bv, typename t_rank, typename t_max_vec>
335class k2_treap;
336
338template <uint8_t t_k, typename t_bv, typename t_rank, typename t_max_vec>
339void construct(k2_treap<t_k, t_bv, t_rank, t_max_vec> & idx, std::string file, cache_config & config)
340{
341 int_vector_buffer<> buf_x(file + ".x", std::ios::in);
342 int_vector_buffer<> buf_y(file + ".y", std::ios::in);
343 int_vector_buffer<> buf_w(file + ".w", std::ios::in);
344 idx = k2_treap<t_k, t_bv, t_rank, t_max_vec>(buf_x, buf_y, buf_w, config.dir);
345}
346
348template <uint8_t t_k, typename t_bv, typename t_rank, typename t_max_vec>
349void construct_im(k2_treap<t_k, t_bv, t_rank, t_max_vec> & idx, std::vector<std::array<uint64_t, 3>> data)
350{
351 std::string tmp_dir = ram_file_name("/tmp");
352 std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> d;
353 for (auto x : data) { d.push_back(std::make_tuple(x[0], x[1], x[2])); }
355}
356
357} // namespace sdsl
358#endif
bits.hpp contains the sdsl::bits class.
range_iterator(const t_k2_treap &treap, point_type p1, point_type p2, range_type range)
range_iterator & operator++()
Prefix increment of the iterator.
range_iterator(const range_iterator &)=default
std::pair< point_type, uint64_t > t_point_val
range_iterator(range_iterator &&)=default
range_iterator & operator=(const range_iterator &)=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 & operator=(top_k_iterator &&)=default
top_k_iterator(const top_k_iterator &)=default
std::pair< point_type, uint64_t > t_point_val
top_k_iterator operator++(int)
Postfix increment of the iterator.
top_k_iterator & operator++()
Prefix increment of the iterator.
top_k_iterator & operator=(const top_k_iterator &)=default
top_k_iterator(const t_k2_treap &treap, point_type p1, point_type p2)
A k^2-treap.
Definition: k2_treap.hpp:51
k2_treap_helper.hpp contains helper functions and definitions for a k^2-treap implementation.
bool overlap(const point_type &p1, const point_type &p2, const node_type &v)
Check if rectangle (p1,p2) and the area of node v overlap.
bool contained(const point_type p, const point_type &p1, const point_type &p2)
Check if point x is contained in the rectangle (p1,p2)
Namespace for the succinct data structure library.
uint64_t __count(const t_k2_treap &, typename t_k2_treap::node_type)
uint64_t count(const t_k2_treap &treap, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
Count how many points are in the rectangle (p1,p2)
std::string ram_file_name(const std::string &file)
Returns the corresponding RAM-file name for file.
Definition: ram_fs.hpp:174
uint64_t _count(const t_k2_treap &, k2_treap_ns::point_type, k2_treap_ns::point_type, typename t_k2_treap::node_type)
k2_treap_ns::top_k_iterator< t_k2_treap > top_k(const t_k2_treap &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.
void construct(t_index &idx, std::string file, uint8_t num_bytes=0, bool move_input=false)
Definition: construct.hpp:45
k2_treap_ns::range_iterator< t_k2_treap > range_3d(const t_k2_treap &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.
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
void construct_im(t_index &idx, t_data &&data, uint8_t num_bytes=0)
Definition: construct.hpp:58
Helper class for construction process.
Definition: config.hpp:67
std::string dir
Definition: config.hpp:71
static uint64_t exp(uint8_t l)