|
| k2_treap ()=default |
|
| k2_treap (k2_treap const &tr) |
|
| k2_treap (k2_treap &&tr) |
|
k2_treap & | operator= (k2_treap &&tr) |
| Move assignment operator.
|
|
k2_treap & | operator= (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_type > | children (node_type const &v) const |
|
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.