8#ifndef INCLUDED_SDSL_K2_TREAP_ALGORITHM
9#define INCLUDED_SDSL_K2_TREAP_ALGORITHM
38 return real(p) >= real(p1) and real(p) <= real(p2) and imag(p) >= imag(p1) and imag(p) <= imag(p2);
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;
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);
60template <
typename t_k2_treap>
69 typedef std::pair<node_type, bool> t_nt_b;
71 const t_k2_treap * m_treap =
nullptr;
72 std::priority_queue<t_nt_b> m_pq;
88 , m_valid(treap.
size() > 0)
90 if (m_treap->size() > 0)
92 m_pq.emplace(m_treap->root(),
false);
101 while (!m_pq.empty())
103 auto v = std::get<0>(m_pq.top());
104 auto is_contained = std::get<1>(m_pq.top());
108 auto nodes = m_treap->children(v);
109 for (
auto node : nodes) m_pq.emplace(node,
true);
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))
119 auto nodes = m_treap->children(v);
120 for (
auto node : nodes) m_pq.emplace(node,
false);
151template <
typename t_k2_treap>
160 typedef std::pair<node_type, bool> t_nt_b;
162 const t_k2_treap * m_treap =
nullptr;
163 std::priority_queue<t_nt_b> m_pq;
168 bool m_valid =
false;
172 if (v.
max_v >= real(m_r)) { m_pq.emplace(v, b); }
186 , m_valid(treap.
size() > 0)
188 if (m_treap->size() > 0)
190 pq_emplace(m_treap->root(),
false);
199 while (!m_pq.empty())
201 auto v = std::get<0>(m_pq.top());
202 auto is_contained = std::get<1>(m_pq.top());
206 auto nodes = m_treap->children(v);
207 for (
auto node : nodes) pq_emplace(node,
true);
208 if (v.max_v <= imag(m_r))
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))
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))
258template <
typename t_k2_treap>
275template <
typename t_k2_treap>
285template <
typename t_k2_treap>
286uint64_t
__count(
const t_k2_treap &,
typename t_k2_treap::node_type);
289template <
typename t_k2_treap>
299template <
typename t_k2_treap>
302 if (treap.size() > 0) {
return _count(treap, p1, p2, treap.root()); }
306template <
typename t_k2_treap>
310 typename t_k2_treap::node_type v)
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))
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); }
324template <
typename t_k2_treap>
325uint64_t
__count(
const t_k2_treap & treap,
typename t_k2_treap::node_type v)
328 auto nodes = treap.children(v);
329 for (
auto node : nodes) res +=
__count(treap, node);
334template <u
int8_t t_k,
typename t_bv,
typename t_rank,
typename t_max_vec>
338template <u
int8_t t_k,
typename t_bv,
typename t_rank,
typename t_max_vec>
348template <u
int8_t t_k,
typename t_bv,
typename t_rank,
typename t_max_vec>
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])); }
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
t_point_val operator*() const
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
t_point_val operator*() const
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)
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 &p1, const point_type &p2, const node_type &v)
Check if the rectangle of node v is contained in the rectangle (p1,p2)
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.
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)
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.
void construct_im(t_index &idx, t_data &&data, uint8_t num_bytes=0)
Helper class for construction process.
static uint64_t exp(uint8_t l)