33 #ifndef OR_TOOLS_UTIL_RANGE_MINIMUM_QUERY_H_
34 #define OR_TOOLS_UTIL_RANGE_MINIMUM_QUERY_H_
45 template <
typename T,
typename Compare = std::less<T>>
55 const std::vector<T>&
array()
const;
59 std::vector<std::vector<T>> cache_;
67 template <
typename T,
typename Compare = std::less<T>>
78 const std::vector<T>&
array()
const;
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;
93 template <
typename T,
typename Compare>
101 template <
typename T,
typename Compare>
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_);
120 template <
typename T,
typename Compare>
127 const int window = 1 << log_diff;
128 const std::vector<T>&
row = cache_[log_diff];
132 template <
typename T,
typename Compare>
138 template <
typename T,
typename Compare>
140 std::vector<T> array)
143 template <
typename T,
typename Compare>
146 : cmp_({std::move(
array), std::move(cmp)}),
147 rmq_(CreateIndexVector(cmp_.array.size()), cmp_) {}
149 template <
typename T,
typename Compare>
151 int from,
int to)
const {
152 return rmq_.GetMinimumFromRange(from, to);
155 template <
typename T,
typename Compare>
157 int lhs_idx,
int rhs_idx)
const {
158 return cmp(array[lhs_idx], array[rhs_idx]);
161 template <
typename T,
typename Compare>
162 std::vector<int> RangeMinimumIndexQuery<T, Compare>::CreateIndexVector(
int n) {
163 std::vector<int> result(n, 0);
164 std::iota(result.begin(), result.end(), 0);
168 template <
typename T,
typename Compare>
#define DCHECK_LE(val1, val2)
#define DCHECK_LT(val1, val2)
const std::vector< T > & array() const
RangeMinimumIndexQuery(std::vector< T > array)
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)
RangeMinimumQuery(std::vector< T > array)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int MostSignificantBitPosition32(uint32 n)