A library for working with phylogenetic and population genetic data.
v0.32.0
range_minimum_query.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_UTILS_MATH_RANGE_MINIMUM_QUERY_H_
2 #define GENESIS_UTILS_MATH_RANGE_MINIMUM_QUERY_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2019 Lucas Czech and HITS gGmbH
7 
8  This program is free software: you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation, either version 3 of the License, or
11  (at your option) any later version.
12 
13  This program is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with this program. If not, see <http://www.gnu.org/licenses/>.
20 
21  Contact:
22  Lucas Czech <lucas.czech@h-its.org>
23  Exelixis Lab, Heidelberg Institute for Theoretical Studies
24  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
25 */
26 
35 
36 #include <cmath>
37 #include <cstddef>
38 #include <cstdint>
39 #include <vector>
40 
41 namespace genesis {
42 namespace utils {
43 
62 {
63 public:
64 
65  // -------------------------------------------------------------------------
66  // Typedefs and Enums
67  // -------------------------------------------------------------------------
68 
75  using IntType = int32_t;
76 
77  using SuccinctType = unsigned char;
78  using BlockTypeType = unsigned short;
79 
80  // -------------------------------------------------------------------------
81  // Constructors and Rule of Five
82  // -------------------------------------------------------------------------
83 
84  RangeMinimumQuery() = default;
85  explicit RangeMinimumQuery( std::vector<IntType> const& array );
86  explicit RangeMinimumQuery( std::vector<IntType>&& array );
87 
88  ~RangeMinimumQuery() = default;
89 
90  RangeMinimumQuery( RangeMinimumQuery const& ) = default;
91  RangeMinimumQuery( RangeMinimumQuery&& ) = default;
92 
93  RangeMinimumQuery& operator= ( RangeMinimumQuery const& ) = default;
95 
96  // -------------------------------------------------------------------------
97  // Member Functions
98  // -------------------------------------------------------------------------
99 
100  size_t query( size_t i, size_t j ) const;
101 
102  // -------------------------------------------------------------------------
103  // Internal Inline Functions
104  // -------------------------------------------------------------------------
105 
106 private:
107 
111  inline size_t microblock_( size_t i ) const
112  {
113  return i / micro_size_;
114  }
115 
119  inline size_t block_( size_t i ) const
120  {
121  return i / block_size_;
122  }
123 
127  inline size_t superblock_( size_t i ) const
128  {
129  return i / super_size_;
130  }
131 
135  inline size_t lsb_( SuccinctType v ) const
136  {
137  return lsb_table_256_[v];
138  }
139 
144  inline size_t m_(size_t k, size_t block) const
145  {
146  return m_matrix_(k, block)+(block*block_size_);
147  }
148 
149  // -------------------------------------------------------------------------
150  // Internal Functions
151  // -------------------------------------------------------------------------
152 
153  void init_();
154 
155  size_t log2fast_( size_t v ) const;
156  SuccinctType clearbits_( SuccinctType n, size_t x ) const;
157 
158  // -------------------------------------------------------------------------
159  // Lookup Tables
160  // -------------------------------------------------------------------------
161 
162 private:
163 
164  static const size_t catalan_numbers_[17][17];
165  static const unsigned char log_table_256_[256];
166  static const unsigned char lsb_table_256_[256];
167  static const SuccinctType highest_bits_set_[8];
168 
169  // -------------------------------------------------------------------------
170  // Internal Members
171  // -------------------------------------------------------------------------
172 
173 private:
174 
175  // data
176  std::vector<IntType> array_;
177 
178  // table M for the out-of-block queries (contains indices of block-minima)
179  Matrix<SuccinctType> m_matrix_;
180 
181  // table M' for superblock-queries (contains indices of block-minima)
182  Matrix<size_t> m_prime_;
183 
184  // type of blocks
185  std::vector<BlockTypeType> block_types_;
186 
187  // precomputed in-block queries
188  Matrix<SuccinctType> precomputed_queries_;
189 
190  // microblock size
191  size_t micro_size_;
192 
193  // block size
194  size_t block_size_;
195 
196  // superblock size
197  size_t super_size_;
198 
199  // If the data array is too small, we use the naive approach instead.
200  bool naive_ = false;
201 
202 };
203 
204 } // namespace utils
205 } // namespace genesis
206 
207 #endif // include guard
genesis::utils::RangeMinimumQuery::BlockTypeType
unsigned short BlockTypeType
Definition: range_minimum_query.hpp:78
matrix.hpp
genesis::utils::RangeMinimumQuery::IntType
int32_t IntType
Data type of the array for which we want to run RMQ queries.
Definition: range_minimum_query.hpp:75
genesis::utils::RangeMinimumQuery::RangeMinimumQuery
RangeMinimumQuery()=default
genesis
Container namespace for all symbols of genesis in order to keep them separate when used as a library.
Definition: placement/formats/edge_color.cpp:42
genesis::utils::RangeMinimumQuery::operator=
RangeMinimumQuery & operator=(RangeMinimumQuery const &)=default
genesis::utils::RangeMinimumQuery::query
size_t query(size_t i, size_t j) const
Main function for the Range Minimum Query.
Definition: range_minimum_query.cpp:163
genesis::utils::RangeMinimumQuery
Class that allows to efficiently find the index of the minimum element within an interval of an array...
Definition: range_minimum_query.hpp:61
genesis::utils::RangeMinimumQuery::SuccinctType
unsigned char SuccinctType
Definition: range_minimum_query.hpp:77
genesis::utils::RangeMinimumQuery::~RangeMinimumQuery
~RangeMinimumQuery()=default