A toolkit for working with phylogenetic data.
v0.22.1
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
Class that allows to efficiently find the index of the minimum element within an interval of an array...
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
int32_t IntType
Data type of the array for which we want to run RMQ queries.
RangeMinimumQuery & operator=(RangeMinimumQuery const &)=default
size_t query(size_t i, size_t j) const
Main function for the Range Minimum Query.