SDSL  3.0.0
Succinct Data Structure Library
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>
21 #include <sdsl/k2_treap_helper.hpp>
22 #include <sdsl/vectors.hpp>
23 
25 namespace sdsl
26 {
27 
28 namespace k2_treap_ns
29 {
30 
32 
36 inline 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 
42 template <uint8_t t_k>
43 bool 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 
52 template <uint8_t t_k>
53 bool 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 
60 template <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;
82  top_k_iterator & operator=(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 
151 template <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 
258 template <typename t_k2_treap>
262 {
263  return k2_treap_ns::top_k_iterator<t_k2_treap>(t, p1, p2);
264 }
265 
267 
275 template <typename t_k2_treap>
280 {
281  return k2_treap_ns::range_iterator<t_k2_treap>(t, p1, p2, range);
282 }
283 
284 // forward declaration
285 template <typename t_k2_treap>
286 uint64_t __count(const t_k2_treap &, typename t_k2_treap::node_type);
287 
288 // forward declaration
289 template <typename t_k2_treap>
290 uint64_t _count(const t_k2_treap &, k2_treap_ns::point_type, k2_treap_ns::point_type, typename t_k2_treap::node_type);
291 
293 
299 template <typename t_k2_treap>
300 uint64_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 
306 template <typename t_k2_treap>
307 uint64_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 
324 template <typename t_k2_treap>
325 uint64_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
334 template <uint8_t t_k, typename t_bv, typename t_rank, typename t_max_vec>
335 class k2_treap;
336 
338 template <uint8_t t_k, typename t_bv, typename t_rank, typename t_max_vec>
339 void 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 
348 template <uint8_t t_k, typename t_bv, typename t_rank, typename t_max_vec>
349 void 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])); }
354  idx = k2_treap<t_k, t_bv, t_rank, t_max_vec>(d, tmp_dir);
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(const range_iterator &)=default
std::pair< point_type, uint64_t > t_point_val
range_iterator & operator=(const range_iterator &)=default
range_iterator(range_iterator &&)=default
range_iterator & operator++()
Prefix increment of the iterator.
range_iterator & operator=(range_iterator &&)=default
range_iterator operator++(int)
Postfix increment of the iterator.
top_k_iterator(top_k_iterator &&)=default
top_k_iterator & operator++()
Prefix increment of the iterator.
top_k_iterator(const top_k_iterator &)=default
top_k_iterator & operator=(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=(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.
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.
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
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.
uint64_t _count(const t_k2_treap &, k2_treap_ns::point_type, k2_treap_ns::point_type, typename t_k2_treap::node_type)
void construct(t_index &idx, std::string file, uint8_t num_bytes=0, bool move_input=false)
Definition: construct.hpp:45
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)