OR-Tools  8.2
range_minimum_query.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// We use the notation min(arr, i, j) for the minimum arr[x] such that i <= x
15// and x < j.
16// Range Minimum Query (RMQ) is a data structure preprocessing an array arr so
17// that querying min(arr, i, j) takes O(1) time. The preprocessing takes
18// O(n*log(n)) time and memory.
19
20// Note: There exists an O(n) preprocessing algorithm, but it is considerably
21// more involved and the hidden constants behind it are much higher.
22//
23// The algorithms are well explained in Wikipedia:
24// https://en.wikipedia.org/wiki/Range_minimum_query.
25//
26//
27// Implementation: The idea is to cache every min(arr, i, j) where j - i is a
28// power of two, i.e. j = i + 2^k for some k. Provided this information, we can
29// answer all queries in O(1): given a pair (i, j) find the maximum k such that
30// i + 2^k < j and note that
31// std::min(min(arr, i, i+2^k), min(arr, j-2^k, j)) = min(arr, i, j).
32
33#ifndef OR_TOOLS_UTIL_RANGE_MINIMUM_QUERY_H_
34#define OR_TOOLS_UTIL_RANGE_MINIMUM_QUERY_H_
35
36#include <algorithm>
37#include <functional>
38#include <numeric>
39#include <utility>
40#include <vector>
41
42#include "ortools/util/bitset.h"
43
44namespace operations_research {
45template <typename T, typename Compare = std::less<T>>
47 public:
48 explicit RangeMinimumQuery(std::vector<T> array);
49 RangeMinimumQuery(std::vector<T> array, Compare cmp);
50
51 // Returns the minimum (w.r.t. Compare) arr[x], where x is contained in
52 // [from, to).
53 T GetMinimumFromRange(int from, int to) const;
54
55 const std::vector<T>& array() const;
56
57 private:
58 // cache_[k][i] = min(arr, i, i+2^k).
59 std::vector<std::vector<T>> cache_;
60 Compare cmp_;
61
62 DISALLOW_COPY_AND_ASSIGN(RangeMinimumQuery);
63};
64
65// RangeMinimumIndexQuery is similar to RangeMinimumQuery, but
66// GetMinimumIndexFromRange returns the index for which the minimum is attained.
67template <typename T, typename Compare = std::less<T>>
69 public:
70 explicit RangeMinimumIndexQuery(std::vector<T> array);
71 RangeMinimumIndexQuery(std::vector<T> array, Compare cmp);
72
73 // Returns an index idx from [from, to) such that arr[idx] is the minimum
74 // value of arr over the interval [from, to).
75 int GetMinimumIndexFromRange(int from, int to) const;
76
77 // Returns the original array.
78 const std::vector<T>& array() const;
79
80 private:
81 // Returns a vector with values 0, 1, ... n - 1 for a given n.
82 static std::vector<int> CreateIndexVector(int n);
83 struct IndexComparator {
84 bool operator()(int lhs_idx, int rhs_idx) const;
85 const std::vector<T> array;
86 Compare cmp;
87 } cmp_;
89 DISALLOW_COPY_AND_ASSIGN(RangeMinimumIndexQuery);
90};
91
92// RangeMinimumQuery implementation
93template <typename T, typename Compare>
95 : RangeMinimumQuery(std::move(array), Compare()) {}
96
97// Reminder: The task is to fill cache_ so that
98// cache_[k][i] = min(arr, i, i+2^k) for every k <= Log2(n) and i <= n-2^k.
99// Note that cache_[k+1][i] = min(cache_[k][i], cache_[k][i+2^k]), hence every
100// row can be efficiently computed from the previous.
101template <typename T, typename Compare>
103 Compare cmp)
104 : cache_(MostSignificantBitPosition32(array.size()) + 1),
105 cmp_(std::move(cmp)) {
106 const int array_size = array.size();
107 cache_[0] = std::move(array);
108 for (int row_idx = 1; row_idx < cache_.size(); ++row_idx) {
109 const int row_length = array_size - (1 << row_idx) + 1;
110 const int window = 1 << (row_idx - 1);
111 cache_[row_idx].resize(row_length);
112 for (int col_idx = 0; col_idx < row_length; ++col_idx) {
113 cache_[row_idx][col_idx] =
114 std::min(cache_[row_idx - 1][col_idx],
115 cache_[row_idx - 1][col_idx + window], cmp_);
116 }
117 }
118}
119
120template <typename T, typename Compare>
122 int to) const {
123 DCHECK_LE(0, from);
124 DCHECK_LT(from, to);
125 DCHECK_LE(to, array().size());
126 const int log_diff = MostSignificantBitPosition32(to - from);
127 const int window = 1 << log_diff;
128 const std::vector<T>& row = cache_[log_diff];
129 return std::min(row[from], row[to - window], cmp_);
130}
131
132template <typename T, typename Compare>
133inline const std::vector<T>& RangeMinimumQuery<T, Compare>::array() const {
134 return cache_[0];
135}
136
137// RangeMinimumIndexQuery implementation
138template <typename T, typename Compare>
140 std::vector<T> array)
141 : RangeMinimumIndexQuery(std::move(array), Compare()) {}
142
143template <typename T, typename Compare>
145 Compare cmp)
146 : cmp_({std::move(array), std::move(cmp)}),
147 rmq_(CreateIndexVector(cmp_.array.size()), cmp_) {}
148
149template <typename T, typename Compare>
151 int from, int to) const {
152 return rmq_.GetMinimumFromRange(from, to);
153}
154
155template <typename T, typename Compare>
157 int lhs_idx, int rhs_idx) const {
158 return cmp(array[lhs_idx], array[rhs_idx]);
159}
160
161template <typename T, typename Compare>
162std::vector<int> RangeMinimumIndexQuery<T, Compare>::CreateIndexVector(int n) {
163 std::vector<int> result(n, 0);
164 std::iota(result.begin(), result.end(), 0);
165 return result;
166}
167
168template <typename T, typename Compare>
169inline const std::vector<T>& RangeMinimumIndexQuery<T, Compare>::array() const {
170 return cmp_.array;
171}
172} // namespace operations_research
173#endif // OR_TOOLS_UTIL_RANGE_MINIMUM_QUERY_H_
int64 min
Definition: alldiff_cst.cc:138
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
const std::vector< T > & array() const
int GetMinimumIndexFromRange(int from, int to) const
const std::vector< T > & array() const
T GetMinimumFromRange(int from, int to) const
RangeMinimumQuery(std::vector< T > array, Compare cmp)
RowIndex row
Definition: markowitz.cc:175
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int MostSignificantBitPosition32(uint32 n)
Definition: bitset.h:273
STL namespace.