SDSL  3.0.0
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 
17 namespace sdsl
18 {
19 
21 namespace k2_tree_ns
22 {
23 
26 
27 template <typename t_bv = bit_vector>
28 int _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 
78 inline 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 
83 template <typename t_bv = bit_vector>
84 void 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 
90 template <>
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:253
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:970