8#ifndef INCLUDED_SDSL_K2_TREAP_ALGORITHM
9#define INCLUDED_SDSL_K2_TREAP_ALGORITHM
40 return real(p) >= real(p1) and real(p) <= real(p2) and imag(p) >= imag(p1) and imag(p) <= imag(p2);
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;
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);
62template <
typename t_k2_treap>
71 typedef std::pair<node_type, bool> t_nt_b;
73 t_k2_treap
const * m_treap =
nullptr;
74 std::priority_queue<t_nt_b> m_pq;
90 m_valid(treap.
size() > 0)
92 if (m_treap->size() > 0)
94 m_pq.emplace(m_treap->root(),
false);
103 while (!m_pq.empty())
105 auto v = std::get<0>(m_pq.top());
106 auto is_contained = std::get<1>(m_pq.top());
110 auto nodes = m_treap->children(v);
111 for (
auto node : nodes)
112 m_pq.emplace(node,
true);
119 if (contained<t_k2_treap::k>(m_p1, m_p2, v))
121 m_pq.emplace(v,
true);
123 else if (overlap<t_k2_treap::k>(m_p1, m_p2, v))
125 auto nodes = m_treap->children(v);
126 for (
auto node : nodes)
127 m_pq.emplace(node,
false);
164template <
typename t_k2_treap>
173 typedef std::pair<node_type, bool> t_nt_b;
175 t_k2_treap
const * m_treap =
nullptr;
176 std::priority_queue<t_nt_b> m_pq;
181 bool m_valid =
false;
185 if (v.
max_v >= real(m_r))
202 m_valid(treap.
size() > 0)
204 if (m_treap->size() > 0)
206 pq_emplace(m_treap->root(),
false);
215 while (!m_pq.empty())
217 auto v = std::get<0>(m_pq.top());
218 auto is_contained = std::get<1>(m_pq.top());
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))
234 if (contained<t_k2_treap::k>(m_p1, m_p2, v))
236 m_pq.emplace(v,
true);
238 else if (overlap<t_k2_treap::k>(m_p1, m_p2, v))
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))
285template <
typename t_k2_treap>
286k2_treap_ns::top_k_iterator<t_k2_treap>
301template <
typename t_k2_treap>
302k2_treap_ns::range_iterator<t_k2_treap>
309template <
typename t_k2_treap>
310uint64_t
__count(t_k2_treap
const &,
typename t_k2_treap::node_type);
313template <
typename t_k2_treap>
323template <
typename t_k2_treap>
326 if (treap.size() > 0)
328 return _count(treap, p1, p2, treap.root());
333template <
typename t_k2_treap>
337 typename t_k2_treap::node_type v)
339 using namespace k2_treap_ns;
340 if (contained<t_k2_treap::k>(p1, p2, v))
344 else if (overlap<t_k2_treap::k>(p1, p2, v))
346 uint64_t res = contained(v.max_p, p1, p2);
347 auto nodes = treap.children(v);
348 for (
auto node : nodes)
350 res +=
_count(treap, p1, p2, node);
357template <
typename t_k2_treap>
358uint64_t
__count(t_k2_treap
const & treap,
typename t_k2_treap::node_type v)
361 auto nodes = treap.children(v);
362 for (
auto node : nodes)
368template <u
int8_t t_k,
typename t_bv,
typename t_rank,
typename t_max_vec>
372template <u
int8_t t_k,
typename t_bv,
typename t_rank,
typename t_max_vec>
382template <u
int8_t t_k,
typename t_bv,
typename t_rank,
typename t_max_vec>
386 std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> d;
389 d.push_back(std::make_tuple(x[0], x[1], x[2]));
range_iterator & operator++()
Prefix increment of the iterator.
range_iterator(t_k2_treap const &treap, point_type p1, point_type p2, range_type range)
std::pair< point_type, uint64_t > t_point_val
range_iterator(range_iterator &&)=default
t_point_val operator*() const
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)
top_k_iterator & operator=(top_k_iterator &&)=default
t_point_val operator*() const
top_k_iterator & operator=(top_k_iterator const &)=default
std::pair< point_type, uint64_t > t_point_val
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.
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)
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)
Helper class for construction process.
static uint64_t exp(uint8_t l)