SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 (k2_treap const &tr)
 
 k2_treap (k2_treap &&tr)
 
k2_treapoperator= (k2_treap &&tr)
 Move assignment operator.
 
k2_treapoperator= (k2_treap &tr)
 Assignment operator.
 
size_type size () const
 Number of points in the 2^k treap.
 
 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.
 
void load (std::istream &in)
 Loads the data structure from the given istream.
 
template<typename archive_t>
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 Serialise (save) via cereal.
 
template<typename archive_t>
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 Load via cereal.
 
bool operator== (k2_treap const &other) const noexcept
 Equality operator.
 
bool operator!= (k2_treap const &other) const noexcept
 Inequality operator.
 
node_type root () const
 
bool is_leaf (node_type const &v) const
 
std::vector< node_typechildren (node_type const &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 63 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 70 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 71 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 69 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 72 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 74 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 ( k2_treap< t_k, t_bv, t_rank, t_max_vec > const & tr)
inline

Definition at line 120 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 131 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 169 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 243 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 445 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 433 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 ( node_type const & v) const
inline

Definition at line 479 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 252 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 ( node_type const & v) const
inline

Definition at line 474 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 419 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 464 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 137 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 153 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 457 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 223 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 469 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 404 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 164 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 116 of file k2_treap.hpp.


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