27class LinearRangeIntToIntFunction :
public RangeIntToIntFunction {
29 explicit LinearRangeIntToIntFunction(
31 : base_function_(
std::move(base_function)) {}
34 return base_function_(argument);
40 for (
int64 i = range_begin; i < range_end; ++i) {
41 min_val =
std::min(min_val, base_function_(i));
49 for (
int64 i = range_begin; i < range_end; ++i) {
50 max_val =
std::max(max_val, base_function_(i));
57 int64 interval_end)
const override {
61 int64 i = range_begin;
62 for (; i < range_end; ++i) {
64 if (interval_begin <=
value &&
value < interval_end)
break;
71 int64 interval_end)
const override {
76 int64 i = range_end - 1;
77 for (; i >= range_begin; --i) {
79 if (interval_begin <=
value &&
value < interval_end)
break;
90std::vector<int64> FunctionToVector(
const std::function<
int64(
int64)>& f,
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);
104class CachedRangeIntToIntFunction :
public RangeIntToIntFunction {
106 CachedRangeIntToIntFunction(
const std::function<
int64(
int64)>& base_function,
108 : domain_start_(domain_start),
109 rmq_min_(FunctionToVector(base_function, domain_start, domain_end)),
110 rmq_max_(rmq_min_.array()) {
116 DCHECK_LE(argument, domain_start_ +
static_cast<int64>(array().size()));
117 return array()[argument - domain_start_];
122 DCHECK_LE(to, domain_start_ +
static_cast<int64>(array().size()));
123 return rmq_min_.GetMinimumFromRange(from - domain_start_,
129 DCHECK_LE(to, domain_start_ +
static_cast<int64>(array().size()));
130 return rmq_max_.GetMinimumFromRange(from - domain_start_,
134 int64 interval_begin,
135 int64 interval_end)
const override {
139 DCHECK_LE(range_end, domain_start_ + array().size());
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;
149 int64 interval_begin,
150 int64 interval_end)
const override {
154 DCHECK_LE(range_end, domain_start_ + array().size());
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;
165 const std::vector<int64>& array()
const {
return rmq_min_.array(); }
167 const int64 domain_start_;
168 const RangeMinimumQuery<int64, std::less<int64>> rmq_min_;
169 const RangeMinimumQuery<int64, std::greater<int64>> rmq_max_;
174class CachedRangeMinMaxIndexFunction :
public RangeMinMaxIndexFunction {
176 CachedRangeMinMaxIndexFunction(
const std::function<
int64(
int64)>& f,
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()) {
189 return index_rmq_min_.GetMinimumIndexFromRange(from - domain_start_,
190 to - domain_start_) +
197 return index_rmq_max_.GetMinimumIndexFromRange(from - domain_start_,
198 to - domain_start_) +
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_;
213 return new LinearRangeIntToIntFunction(std::move(f));
219 return new CachedRangeIntToIntFunction(f, domain_start, domain_end);
225 return new CachedRangeMinMaxIndexFunction(f, domain_start, domain_end);
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_LT(val1, val2)
#define DCHECK_LT(val1, val2)
static const int64 kint64max
static const int64 kint64min
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
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)