SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <deque>
13#include <stdint.h>
14#include <utility>
15#include <vector>
16
17#include <sdsl/int_vector.hpp>
18
20namespace sdsl
21{
22
24namespace k2_tree_ns
25{
26
29
30template <typename t_bv = bit_vector>
31int _build_from_matrix(std::vector<std::vector<int>> const & matrix,
32 const uint8_t k,
33 int n,
34 int const height,
35 int l,
36 int p,
37 int q,
38 std::vector<std::deque<t_bv>> & acc)
39{
40 unsigned i, j, b_size = pow(k, 2);
41 t_bv b(b_size, 0);
42 bool is_leaf = (l == height);
43
44 if (is_leaf)
45 {
46 for (i = 0; i < k; i++)
47 for (j = 0; j < k; j++)
48 if (p + i < matrix.size() && q + j < matrix.size() && matrix[p + i][q + j] == 1)
49 b[i * k + j] = 1;
50 }
51 else
52 { // Internal node
53 for (i = 0; i < k; i++)
54 for (j = 0; j < k; j++)
55 b[i * k + j] =
56 _build_from_matrix(matrix, k, n / k, height, l + 1, p + i * (n / k), q + j * (n / k), acc);
57 }
58
59 // TODO There must be a better way to check if there is a 1 at b.
60 for (i = 0; i < b_size; i++)
61 if (b[i] == 1)
62 break;
63 if (i == b_size) // If there are not 1s at b.
64 return 0;
65
66 acc[l].push_back(std::move(b));
67 return 1;
68}
69
83inline 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)
84{
85 return ((v - r_0) / l) * k + (u - c_0) / l;
86}
87
88template <typename t_bv = bit_vector>
89void build_template_vector(bit_vector & k_t_, bit_vector & k_l_, t_bv & k_t, t_bv & k_l)
90{
91 k_t = t_bv(k_t_);
92 k_l = t_bv(k_l_);
93}
94
95template <>
97{
98 std::swap(k_t, k_t_);
99 std::swap(k_l, k_l_);
100}
101
102} // end namespace k2_tree_ns
103} // end namespace sdsl
104
105#endif
A generic vector class for integers of width .
int_vector.hpp contains the sdsl::int_vector class.
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.
int _build_from_matrix(std::vector< std::vector< int > > const &matrix, const uint8_t k, int n, int const height, int l, int p, int q, std::vector< std::deque< t_bv > > &acc)
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.