SDSL  3.0.0
Succinct Data Structure Library
sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec > Class Template Reference

A k^2-treap. More...

#include <k2_treap.hpp>

Public Types

enum  { k = t_k }
 
typedef int_vector ::size_type size_type
 
using node_type = k2_treap_ns::node_type
 
using point_type = k2_treap_ns::point_type
 
using t_p = k2_treap_ns::t_p
 

Public Member Functions

 k2_treap ()=default
 
 k2_treap (const k2_treap &tr)
 
 k2_treap (k2_treap &&tr)
 
k2_treapoperator= (k2_treap &&tr)
 Move assignment operator. More...
 
k2_treapoperator= (k2_treap &tr)
 Assignment operator. More...
 
size_type size () const
 Number of points in the 2^k treap. More...
 
 k2_treap (int_vector_buffer<> &buf_x, int_vector_buffer<> &buf_y, int_vector_buffer<> &buf_w, std::string temp_dir)
 
template<typename t_x = uint64_t, typename t_y = uint64_t, typename t_w = uint64_t>
std::vector< std::tuple< t_x, t_y, t_w > > read (std::vector< int_vector_buffer<> * > &bufs)
 
template<typename t_x , typename t_y , typename t_w >
 k2_treap (std::vector< std::tuple< t_x, t_y, t_w >> &v, std::string temp_dir=".")
 
template<typename t_x , typename t_y , typename t_w >
void construct (std::vector< std::tuple< t_x, t_y, t_w >> &v, std::string temp_dir=".")
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes the data structure into the given ostream. More...
 
void load (std::istream &in)
 Loads the data structure from the given istream. More...
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 Serialise (save) via cereal. More...
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 Load via cereal. More...
 
bool operator== (k2_treap const &other) const noexcept
 Equality operator. More...
 
bool operator!= (k2_treap const &other) const noexcept
 Inequality operator. More...
 
node_type root () const
 
bool is_leaf (const node_type &v) const
 
std::vector< node_typechildren (const node_type &v) const
 

Public Attributes

uint8_t & t = m_t
 

Detailed Description

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
class sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >

A k^2-treap.

A k^2-treap is an indexing structure for a set of weighted points. The set consists of triples (x,y,w), where the first two components x and y are the coordinates of the point and w is the point's weight.

The k^2 treap supports 4-sided range count queries and 4-sided prioritized range queries in 2d. Using the latter functionality it is also possible to support 6-sided range queries in 3d. An example can be found in examples/k2_treap_in_mem.cpp .

The k^2-treap constructed in-place. The construct method expects either a vector of std::array<X,3> elements (each array represent a tuple x,y,w) or a file prefix FILE. In the latter case three serialized int_vector<> have to be present at FILE.x, FILE.y, and FILE.w. One int_vector<> per component.

References
[1] N. Brisaboa, G. de Bernardo, R. Konow, and G. Navarro: ,,$K^2$-Treaps: Range Top-$k$ Queries in Compact Space, Proceedings of SPIRE 2014.

Definition at line 50 of file k2_treap.hpp.

Member Typedef Documentation

◆ node_type

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
using sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::node_type = k2_treap_ns::node_type

Definition at line 57 of file k2_treap.hpp.

◆ point_type

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
using sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::point_type = k2_treap_ns::point_type

Definition at line 58 of file k2_treap.hpp.

◆ size_type

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
typedef int_vector ::size_type sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::size_type

Definition at line 56 of file k2_treap.hpp.

◆ t_p

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
using sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::t_p = k2_treap_ns::t_p

Definition at line 59 of file k2_treap.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
anonymous enum
Enumerator

Definition at line 61 of file k2_treap.hpp.

Constructor & Destructor Documentation

◆ k2_treap() [1/5]

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::k2_treap ( )
default

◆ k2_treap() [2/5]

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::k2_treap ( const k2_treap< t_k, t_bv, t_rank, t_max_vec > &  tr)
inline

Definition at line 93 of file k2_treap.hpp.

◆ k2_treap() [3/5]

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::k2_treap ( k2_treap< t_k, t_bv, t_rank, t_max_vec > &&  tr)
inline

Definition at line 104 of file k2_treap.hpp.

◆ k2_treap() [4/5]

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::k2_treap ( int_vector_buffer<> &  buf_x,
int_vector_buffer<> &  buf_y,
int_vector_buffer<> &  buf_w,
std::string  temp_dir 
)
inline

Definition at line 136 of file k2_treap.hpp.

◆ k2_treap() [5/5]

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
template<typename t_x , typename t_y , typename t_w >
sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::k2_treap ( std::vector< std::tuple< t_x, t_y, t_w >> &  v,
std::string  temp_dir = "." 
)
inline

Definition at line 190 of file k2_treap.hpp.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
template<typename archive_t >
void sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Load via cereal.

Definition at line 371 of file k2_treap.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
template<typename archive_t >
void sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Serialise (save) via cereal.

Definition at line 359 of file k2_treap.hpp.

◆ children()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
std::vector<node_type> sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::children ( const node_type v) const
inline

Definition at line 399 of file k2_treap.hpp.

◆ construct()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
template<typename t_x , typename t_y , typename t_w >
void sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::construct ( std::vector< std::tuple< t_x, t_y, t_w >> &  v,
std::string  temp_dir = "." 
)
inline

Definition at line 196 of file k2_treap.hpp.

◆ is_leaf()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
bool sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::is_leaf ( const node_type v) const
inline

Definition at line 397 of file k2_treap.hpp.

◆ load()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
void sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::load ( std::istream &  in)
inline

Loads the data structure from the given istream.

Definition at line 345 of file k2_treap.hpp.

◆ operator!=()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
bool sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::operator!= ( k2_treap< t_k, t_bv, t_rank, t_max_vec > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 390 of file k2_treap.hpp.

◆ operator=() [1/2]

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
k2_treap& sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::operator= ( k2_treap< t_k, t_bv, t_rank, t_max_vec > &&  tr)
inline

Move assignment operator.

Definition at line 107 of file k2_treap.hpp.

◆ operator=() [2/2]

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
k2_treap& sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::operator= ( k2_treap< t_k, t_bv, t_rank, t_max_vec > &  tr)
inline

Assignment operator.

Definition at line 123 of file k2_treap.hpp.

◆ operator==()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
bool sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::operator== ( k2_treap< t_k, t_bv, t_rank, t_max_vec > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 383 of file k2_treap.hpp.

◆ read()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
template<typename t_x = uint64_t, typename t_y = uint64_t, typename t_w = uint64_t>
std::vector<std::tuple<t_x, t_y, t_w> > sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::read ( std::vector< int_vector_buffer<> * > &  bufs)
inline

Definition at line 179 of file k2_treap.hpp.

◆ root()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
node_type sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::root ( ) const
inline

Definition at line 392 of file k2_treap.hpp.

◆ serialize()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
size_type sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inline

Serializes the data structure into the given ostream.

Definition at line 330 of file k2_treap.hpp.

◆ size()

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
size_type sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::size ( ) const
inline

Number of points in the 2^k treap.

Definition at line 134 of file k2_treap.hpp.

Member Data Documentation

◆ t

template<uint8_t t_k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type, typename t_max_vec = dac_vector<>>
uint8_t& sdsl::k2_treap< t_k, t_bv, t_rank, t_max_vec >::t = m_t

Definition at line 89 of file k2_treap.hpp.


The documentation for this class was generated from the following file: