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 
19 #include "ortools/base/logging.h"
20 #include "ortools/base/macros.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:
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 
90 std::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.
104 class 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 
174 class 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)