OR-Tools  8.2
range_query_function.cc
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
15
16#include <memory>
17
20#include "ortools/base/macros.h"
22
23namespace operations_research {
24namespace {
25// This implementation basically calls the function as many times as needed for
26// each query.
27class LinearRangeIntToIntFunction : public RangeIntToIntFunction {
28 public:
29 explicit LinearRangeIntToIntFunction(
30 std::function<int64(int64)> base_function)
31 : base_function_(std::move(base_function)) {}
32
33 int64 Query(int64 argument) const override {
34 return base_function_(argument);
35 }
36
37 int64 RangeMin(int64 range_begin, int64 range_end) const override {
38 DCHECK_LT(range_begin, range_end);
39 int64 min_val = kint64max;
40 for (int64 i = range_begin; i < range_end; ++i) {
41 min_val = std::min(min_val, base_function_(i));
42 }
43 return min_val;
44 }
45
46 int64 RangeMax(int64 range_begin, int64 range_end) const override {
47 DCHECK_LT(range_begin, range_end);
48 int64 max_val = kint64min;
49 for (int64 i = range_begin; i < range_end; ++i) {
50 max_val = std::max(max_val, base_function_(i));
51 }
52 return max_val;
53 }
54
55 int64 RangeFirstInsideInterval(int64 range_begin, int64 range_end,
56 int64 interval_begin,
57 int64 interval_end) const override {
58 // domain_start_ <= range_begin < range_end <= domain_start_+array().size()
59 DCHECK_LT(range_begin, range_end);
60 DCHECK_LT(interval_begin, interval_end);
61 int64 i = range_begin;
62 for (; i < range_end; ++i) {
63 const int64 value = base_function_(i);
64 if (interval_begin <= value && value < interval_end) break;
65 }
66 return i;
67 }
68
69 int64 RangeLastInsideInterval(int64 range_begin, int64 range_end,
70 int64 interval_begin,
71 int64 interval_end) const override {
72 // domain_start_ <= range_begin < range_end <= domain_start_+array().size()
73 DCHECK_NE(range_begin, kint64max);
74 DCHECK_LT(range_begin, range_end);
75 DCHECK_LT(interval_begin, interval_end);
76 int64 i = range_end - 1;
77 for (; i >= range_begin; --i) {
78 const int64 value = base_function_(i);
79 if (interval_begin <= value && value < interval_end) break;
80 }
81 return i;
82 }
83
84 private:
85 std::function<int64(int64)> base_function_;
86
87 DISALLOW_COPY_AND_ASSIGN(LinearRangeIntToIntFunction);
88};
89
90std::vector<int64> FunctionToVector(const std::function<int64(int64)>& f,
91 int64 domain_start, int64 domain_end) {
92 CHECK_LT(domain_start, domain_end);
93 std::vector<int64> output(domain_end - domain_start, 0);
94 for (int64 i = 0; i < domain_end - domain_start; ++i) {
95 output[i] = f(i + domain_start);
96 }
97 return output;
98}
99
100// This implementation caches the underlying function and improves on the
101// non-cached version in two ways:
102// 1. It caches the values returned by the function.
103// 2. It creates a data structure for quick answer to range queries.
104class CachedRangeIntToIntFunction : public RangeIntToIntFunction {
105 public:
106 CachedRangeIntToIntFunction(const std::function<int64(int64)>& base_function,
107 int64 domain_start, int64 domain_end)
108 : domain_start_(domain_start),
109 rmq_min_(FunctionToVector(base_function, domain_start, domain_end)),
110 rmq_max_(rmq_min_.array()) {
111 CHECK_LT(domain_start, domain_end);
112 }
113
114 int64 Query(int64 argument) const override {
115 DCHECK_LE(domain_start_, argument);
116 DCHECK_LE(argument, domain_start_ + static_cast<int64>(array().size()));
117 return array()[argument - domain_start_];
118 }
119 int64 RangeMin(int64 from, int64 to) const override {
120 DCHECK_LE(domain_start_, from);
121 DCHECK_LT(from, to);
122 DCHECK_LE(to, domain_start_ + static_cast<int64>(array().size()));
123 return rmq_min_.GetMinimumFromRange(from - domain_start_,
124 to - domain_start_);
125 }
126 int64 RangeMax(int64 from, int64 to) const override {
127 DCHECK_LE(domain_start_, from);
128 DCHECK_LT(from, to);
129 DCHECK_LE(to, domain_start_ + static_cast<int64>(array().size()));
130 return rmq_max_.GetMinimumFromRange(from - domain_start_,
131 to - domain_start_);
132 }
133 int64 RangeFirstInsideInterval(int64 range_begin, int64 range_end,
134 int64 interval_begin,
135 int64 interval_end) const override {
136 // domain_start_ <= range_begin < range_end <= domain_start_+array().size()
137 DCHECK_LE(domain_start_, range_begin);
138 DCHECK_LT(range_begin, range_end);
139 DCHECK_LE(range_end, domain_start_ + array().size());
140 DCHECK_LT(interval_begin, interval_end);
141 int64 i = range_begin;
142 for (; i < range_end; ++i) {
143 const int64 value = array()[i - domain_start_];
144 if (interval_begin <= value && value < interval_end) break;
145 }
146 return i;
147 }
148 int64 RangeLastInsideInterval(int64 range_begin, int64 range_end,
149 int64 interval_begin,
150 int64 interval_end) const override {
151 // domain_start_ <= range_begin < range_end <= domain_start_+array().size()
152 DCHECK_LE(domain_start_, range_begin);
153 DCHECK_LT(range_begin, range_end);
154 DCHECK_LE(range_end, domain_start_ + array().size());
155 DCHECK_LT(interval_begin, interval_end);
156 int64 i = range_end - 1;
157 for (; i >= range_begin; --i) {
158 const int64 value = array()[i - domain_start_];
159 if (interval_begin <= value && value < interval_end) break;
160 }
161 return i;
162 }
163
164 private:
165 const std::vector<int64>& array() const { return rmq_min_.array(); }
166
167 const int64 domain_start_;
168 const RangeMinimumQuery<int64, std::less<int64>> rmq_min_;
169 const RangeMinimumQuery<int64, std::greater<int64>> rmq_max_;
170
171 DISALLOW_COPY_AND_ASSIGN(CachedRangeIntToIntFunction);
172};
173
174class CachedRangeMinMaxIndexFunction : public RangeMinMaxIndexFunction {
175 public:
176 CachedRangeMinMaxIndexFunction(const std::function<int64(int64)>& f,
177 int64 domain_start, int64 domain_end)
178 : domain_start_(domain_start),
179 domain_end_(domain_end),
180 index_rmq_min_(FunctionToVector(f, domain_start, domain_end)),
181 index_rmq_max_(index_rmq_min_.array()) {
182 CHECK_LT(domain_start, domain_end);
183 }
184
185 inline int64 RangeMinArgument(int64 from, int64 to) const override {
186 DCHECK_LE(domain_start_, from);
187 DCHECK_LT(from, to);
188 DCHECK_LE(to, domain_end_);
189 return index_rmq_min_.GetMinimumIndexFromRange(from - domain_start_,
190 to - domain_start_) +
191 domain_start_;
192 }
193 inline int64 RangeMaxArgument(int64 from, int64 to) const override {
194 DCHECK_LE(domain_start_, from);
195 DCHECK_LT(from, to);
196 DCHECK_LE(to, domain_end_);
197 return index_rmq_max_.GetMinimumIndexFromRange(from - domain_start_,
198 to - domain_start_) +
199 domain_start_;
200 }
201
202 private:
203 const int64 domain_start_;
204 const int64 domain_end_;
205 const RangeMinimumIndexQuery<int64, std::less<int64>> index_rmq_min_;
206 const RangeMinimumIndexQuery<int64, std::greater<int64>> index_rmq_max_;
207
208 DISALLOW_COPY_AND_ASSIGN(CachedRangeMinMaxIndexFunction);
209};
210} // namespace
211
213 return new LinearRangeIntToIntFunction(std::move(f));
214}
215
217 const std::function<int64(int64)>& f, int64 domain_start,
218 int64 domain_end) {
219 return new CachedRangeIntToIntFunction(f, domain_start, domain_end);
220}
221
223 const std::function<int64(int64)>& f, int64 domain_start,
224 int64 domain_end) {
225 return new CachedRangeMinMaxIndexFunction(f, domain_start, domain_end);
226}
227} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
int64 value
static const int64 kint64max
int64_t int64
static const int64 kint64min
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
RangeMinMaxIndexFunction * MakeCachedRangeMinMaxIndexFunction(const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
RangeIntToIntFunction * MakeBareIntToIntFunction(std::function< int64(int64)> f)
RangeIntToIntFunction * MakeCachedIntToIntFunction(const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
STL namespace.