SDSL 3.0.1
Succinct Data Structure Library
k2_tree_helper.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef INCLUDED_SDSL_K2_TREE_HELPER
9#define INCLUDED_SDSL_K2_TREE_HELPER
10
11#include <cmath>
12#include <iostream>
13
14#include <sdsl/bit_vectors.hpp>
15
17namespace sdsl
18{
19
21namespace k2_tree_ns
22{
23
26
27template <typename t_bv = bit_vector>
28int _build_from_matrix(const std::vector<std::vector<int>> & matrix,
29 const uint8_t k,
30 int n,
31 const int height,
32 int l,
33 int p,
34 int q,
35 std::vector<std::deque<t_bv>> & acc)
36{
37 unsigned i, j, b_size = pow(k, 2);
38 t_bv b(b_size, 0);
39 bool is_leaf = (l == height);
40
41 if (is_leaf)
42 {
43 for (i = 0; i < k; i++)
44 for (j = 0; j < k; j++)
45 if (p + i < matrix.size() && q + j < matrix.size() && matrix[p + i][q + j] == 1) b[i * k + j] = 1;
46 }
47 else
48 { // Internal node
49 for (i = 0; i < k; i++)
50 for (j = 0; j < k; j++)
51 b[i * k +
52 j] = _build_from_matrix(matrix, k, n / k, height, l + 1, p + i * (n / k), q + j * (n / k), acc);
53 }
54
55 // TODO There must be a better way to check if there is a 1 at b.
56 for (i = 0; i < b_size; i++)
57 if (b[i] == 1) break;
58 if (i == b_size) // If there are not 1s at b.
59 return 0;
60
61 acc[l].push_back(std::move(b));
62 return 1;
63}
64
78inline uint16_t get_chunk_idx(idx_type v, idx_type u, idx_type c_0, idx_type r_0, size_type l, uint8_t k)
79{
80 return ((v - r_0) / l) * k + (u - c_0) / l;
81}
82
83template <typename t_bv = bit_vector>
84void build_template_vector(bit_vector & k_t_, bit_vector & k_l_, t_bv & k_t, t_bv & k_l)
85{
86 k_t = t_bv(k_t_);
87 k_l = t_bv(k_l_);
88}
89
90template <>
92{
93 std::swap(k_t, k_t_);
94 std::swap(k_l, k_l_);
95}
96
97} // end namespace k2_tree_ns
98} // end namespace sdsl
99
100#endif
bit_vectors.hpp contains classes for uncompressed and compressed bit vector representations.
A generic vector class for integers of width .
Definition: int_vector.hpp:216
int _build_from_matrix(const std::vector< std::vector< int > > &matrix, const uint8_t k, int n, const int height, int l, int p, int q, std::vector< std::deque< t_bv > > &acc)
uint16_t get_chunk_idx(idx_type v, idx_type u, idx_type c_0, idx_type r_0, size_type l, uint8_t k)
Get the chunk index ([0, k^2[) of a submatrix point.
void build_template_vector(bit_vector &k_t_, bit_vector &k_l_, t_bv &k_t, t_bv &k_l)
int_vector ::size_type size_type
void build_template_vector< bit_vector >(bit_vector &k_t_, bit_vector &k_l_, bit_vector &k_t, bit_vector &k_l)
int_vector ::size_type idx_type
Namespace for the succinct data structure library.
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
Definition: int_vector.hpp:946