1 // Copyright 2010-2021 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 #include "ortools/util/range_query_function.h"
15
16 #include <memory>
17
18 #include "ortools/base/integral_types.h"
19 #include "ortools/base/logging.h"
20 #include "ortools/base/macros.h"
21 #include "ortools/util/range_minimum_query.h"
22
23 namespace operations_research {
24 namespace {
25 // This implementation basically calls the function as many times as needed for
26 // each query.
27 class LinearRangeIntToIntFunction : public RangeIntToIntFunction {
28 public:
LinearRangeIntToIntFunction(std::function<int64_t (int64_t)> base_function)29 explicit LinearRangeIntToIntFunction(
30 std::function<int64_t(int64_t)> base_function)
31 : base_function_(std::move(base_function)) {}
32
Query(int64_t argument) const33 int64_t Query(int64_t argument) const override {
34 return base_function_(argument);
35 }
36
RangeMin(int64_t range_begin,int64_t range_end) const37 int64_t RangeMin(int64_t range_begin, int64_t range_end) const override {
38 DCHECK_LT(range_begin, range_end);
39 int64_t min_val = kint64max;
40 for (int64_t i = range_begin; i < range_end; ++i) {
41 min_val = std::min(min_val, base_function_(i));
42 }
43 return min_val;
44 }
45
RangeMax(int64_t range_begin,int64_t range_end) const46 int64_t RangeMax(int64_t range_begin, int64_t range_end) const override {
47 DCHECK_LT(range_begin, range_end);
48 int64_t max_val = kint64min;
49 for (int64_t i = range_begin; i < range_end; ++i) {
50 max_val = std::max(max_val, base_function_(i));
51 }
52 return max_val;
53 }
54
RangeFirstInsideInterval(int64_t range_begin,int64_t range_end,int64_t interval_begin,int64_t interval_end) const55 int64_t RangeFirstInsideInterval(int64_t range_begin, int64_t range_end,
56 int64_t interval_begin,
57 int64_t 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_t i = range_begin;
62 for (; i < range_end; ++i) {
63 const int64_t value = base_function_(i);
64 if (interval_begin <= value && value < interval_end) break;
65 }
66 return i;
67 }
68
RangeLastInsideInterval(int64_t range_begin,int64_t range_end,int64_t interval_begin,int64_t interval_end) const69 int64_t RangeLastInsideInterval(int64_t range_begin, int64_t range_end,
70 int64_t interval_begin,
71 int64_t 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_t i = range_end - 1;
77 for (; i >= range_begin; --i) {
78 const int64_t 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_t(int64_t)> base_function_;
86
87 DISALLOW_COPY_AND_ASSIGN(LinearRangeIntToIntFunction);
88 };
89
FunctionToVector(const std::function<int64_t (int64_t)> & f,int64_t domain_start,int64_t domain_end)90 std::vector<int64_t> FunctionToVector(const std::function<int64_t(int64_t)>& f,
91 int64_t domain_start,
92 int64_t domain_end) {
93 CHECK_LT(domain_start, domain_end);
94 std::vector<int64_t> output(domain_end - domain_start, 0);
95 for (int64_t i = 0; i < domain_end - domain_start; ++i) {
96 output[i] = f(i + domain_start);
97 }
98 return output;
99 }
100
101 // This implementation caches the underlying function and improves on the
102 // non-cached version in two ways:
103 // 1. It caches the values returned by the function.
104 // 2. It creates a data structure for quick answer to range queries.
105 class CachedRangeIntToIntFunction : public RangeIntToIntFunction {
106 public:
CachedRangeIntToIntFunction(const std::function<int64_t (int64_t)> & base_function,int64_t domain_start,int64_t domain_end)107 CachedRangeIntToIntFunction(
108 const std::function<int64_t(int64_t)>& base_function,
109 int64_t domain_start, int64_t domain_end)
110 : domain_start_(domain_start),
111 rmq_min_(FunctionToVector(base_function, domain_start, domain_end)),
112 rmq_max_(rmq_min_.array()) {
113 CHECK_LT(domain_start, domain_end);
114 }
115
Query(int64_t argument) const116 int64_t Query(int64_t argument) const override {
117 DCHECK_LE(domain_start_, argument);
118 DCHECK_LE(argument, domain_start_ + static_cast<int64_t>(array().size()));
119 return array()[argument - domain_start_];
120 }
RangeMin(int64_t from,int64_t to) const121 int64_t RangeMin(int64_t from, int64_t to) const override {
122 DCHECK_LE(domain_start_, from);
123 DCHECK_LT(from, to);
124 DCHECK_LE(to, domain_start_ + static_cast<int64_t>(array().size()));
125 return rmq_min_.GetMinimumFromRange(from - domain_start_,
126 to - domain_start_);
127 }
RangeMax(int64_t from,int64_t to) const128 int64_t RangeMax(int64_t from, int64_t to) const override {
129 DCHECK_LE(domain_start_, from);
130 DCHECK_LT(from, to);
131 DCHECK_LE(to, domain_start_ + static_cast<int64_t>(array().size()));
132 return rmq_max_.GetMinimumFromRange(from - domain_start_,
133 to - domain_start_);
134 }
RangeFirstInsideInterval(int64_t range_begin,int64_t range_end,int64_t interval_begin,int64_t interval_end) const135 int64_t RangeFirstInsideInterval(int64_t range_begin, int64_t range_end,
136 int64_t interval_begin,
137 int64_t interval_end) const override {
138 // domain_start_ <= range_begin < range_end <= domain_start_+array().size()
139 DCHECK_LE(domain_start_, range_begin);
140 DCHECK_LT(range_begin, range_end);
141 DCHECK_LE(range_end, domain_start_ + array().size());
142 DCHECK_LT(interval_begin, interval_end);
143 int64_t i = range_begin;
144 for (; i < range_end; ++i) {
145 const int64_t value = array()[i - domain_start_];
146 if (interval_begin <= value && value < interval_end) break;
147 }
148 return i;
149 }
RangeLastInsideInterval(int64_t range_begin,int64_t range_end,int64_t interval_begin,int64_t interval_end) const150 int64_t RangeLastInsideInterval(int64_t range_begin, int64_t range_end,
151 int64_t interval_begin,
152 int64_t interval_end) const override {
153 // domain_start_ <= range_begin < range_end <= domain_start_+array().size()
154 DCHECK_LE(domain_start_, range_begin);
155 DCHECK_LT(range_begin, range_end);
156 DCHECK_LE(range_end, domain_start_ + array().size());
157 DCHECK_LT(interval_begin, interval_end);
158 int64_t i = range_end - 1;
159 for (; i >= range_begin; --i) {
160 const int64_t value = array()[i - domain_start_];
161 if (interval_begin <= value && value < interval_end) break;
162 }
163 return i;
164 }
165
166 private:
array() const167 const std::vector<int64_t>& array() const { return rmq_min_.array(); }
168
169 const int64_t domain_start_;
170 const RangeMinimumQuery<int64_t, std::less<int64_t>> rmq_min_;
171 const RangeMinimumQuery<int64_t, std::greater<int64_t>> rmq_max_;
172
173 DISALLOW_COPY_AND_ASSIGN(CachedRangeIntToIntFunction);
174 };
175
176 class CachedRangeMinMaxIndexFunction : public RangeMinMaxIndexFunction {
177 public:
CachedRangeMinMaxIndexFunction(const std::function<int64_t (int64_t)> & f,int64_t domain_start,int64_t domain_end)178 CachedRangeMinMaxIndexFunction(const std::function<int64_t(int64_t)>& f,
179 int64_t domain_start, int64_t domain_end)
180 : domain_start_(domain_start),
181 domain_end_(domain_end),
182 index_rmq_min_(FunctionToVector(f, domain_start, domain_end)),
183 index_rmq_max_(index_rmq_min_.array()) {
184 CHECK_LT(domain_start, domain_end);
185 }
186
RangeMinArgument(int64_t from,int64_t to) const187 inline int64_t RangeMinArgument(int64_t from, int64_t to) const override {
188 DCHECK_LE(domain_start_, from);
189 DCHECK_LT(from, to);
190 DCHECK_LE(to, domain_end_);
191 return index_rmq_min_.GetMinimumIndexFromRange(from - domain_start_,
192 to - domain_start_) +
193 domain_start_;
194 }
RangeMaxArgument(int64_t from,int64_t to) const195 inline int64_t RangeMaxArgument(int64_t from, int64_t to) const override {
196 DCHECK_LE(domain_start_, from);
197 DCHECK_LT(from, to);
198 DCHECK_LE(to, domain_end_);
199 return index_rmq_max_.GetMinimumIndexFromRange(from - domain_start_,
200 to - domain_start_) +
201 domain_start_;
202 }
203
204 private:
205 const int64_t domain_start_;
206 const int64_t domain_end_;
207 const RangeMinimumIndexQuery<int64_t, std::less<int64_t>> index_rmq_min_;
208 const RangeMinimumIndexQuery<int64_t, std::greater<int64_t>> index_rmq_max_;
209
210 DISALLOW_COPY_AND_ASSIGN(CachedRangeMinMaxIndexFunction);
211 };
212 } // namespace
213
MakeBareIntToIntFunction(std::function<int64_t (int64_t)> f)214 RangeIntToIntFunction* MakeBareIntToIntFunction(
215 std::function<int64_t(int64_t)> f) {
216 return new LinearRangeIntToIntFunction(std::move(f));
217 }
218
MakeCachedIntToIntFunction(const std::function<int64_t (int64_t)> & f,int64_t domain_start,int64_t domain_end)219 RangeIntToIntFunction* MakeCachedIntToIntFunction(
220 const std::function<int64_t(int64_t)>& f, int64_t domain_start,
221 int64_t domain_end) {
222 return new CachedRangeIntToIntFunction(f, domain_start, domain_end);
223 }
224
MakeCachedRangeMinMaxIndexFunction(const std::function<int64_t (int64_t)> & f,int64_t domain_start,int64_t domain_end)225 RangeMinMaxIndexFunction* MakeCachedRangeMinMaxIndexFunction(
226 const std::function<int64_t(int64_t)>& f, int64_t domain_start,
227 int64_t domain_end) {
228 return new CachedRangeMinMaxIndexFunction(f, domain_start, domain_end);
229 }
230 } // namespace operations_research
231