OR-Tools  8.2
piecewise_linear_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 <algorithm>
17#include <set>
18#include <string>
19#include <vector>
20
21#include "absl/strings/str_format.h"
23
24namespace operations_research {
25namespace {
26// If the x value is in the function's domain, it returns the index of the
27// segment it belongs to. The segments are closed to the left and open to
28// the right, hence if x is a common endpoint of two segments, it returns
29// the index of the right segment. If the x value is not in the function's
30// domain, it returns the index of the previous segment or kNotFound if x
31// is before the first segment's start.
32int FindSegmentIndex(const std::vector<PiecewiseSegment>& segments, int64 x) {
33 if (segments.empty() || segments.front().start_x() > x) {
35 }
36
37 // Returns an iterator pointing to the first segment whose the x coordinate
38 // of its start point which compares greater than the x value.
39 std::vector<PiecewiseSegment>::const_iterator position = std::upper_bound(
40 segments.begin(), segments.end(), x, PiecewiseSegment::FindComparator);
41 if (position == segments.end()) {
42 return segments.size() - 1;
43 }
44 position -= position->start_x() > x ? 1 : 0;
45
46 return position - segments.begin();
47}
48
49inline bool IsAtBounds(int64 value) {
50 return value == kint64min || value == kint64max;
51}
52
53inline bool PointInsideRange(int64 point, int64 range_start, int64 range_end) {
54 return range_start <= point && range_end >= point;
55}
56
57// Checks whether two segments form a convex pair, i.e. they are continuous and
58// the slope of the right is bigger than the slope of the left.
59inline bool FormConvexPair(const PiecewiseSegment& left,
60 const PiecewiseSegment& right) {
61 return right.slope() >= left.slope() && right.start_x() == left.end_x() &&
62 right.start_y() == left.end_y();
63}
64
65uint64 UnsignedCapAdd(uint64 left, uint64 right) {
66 return left > kuint64max - right ? kuint64max : left + right;
67}
68
69uint64 UnsignedCapProd(uint64 left, uint64 right) {
70 if (right == 0) return 0;
71 if (left > kuint64max / right) return kuint64max;
72 return left * right;
73}
74} // namespace
75
77 int64 other_point_x)
78 : slope_(slope), reference_x_(point_x), reference_y_(point_y) {
79 start_x_ = std::min(point_x, other_point_x);
80 end_x_ = std::max(point_x, other_point_x);
81 intersection_y_ =
82 reference_x_ < 0 ? SafeValuePostReference(0) : SafeValuePreReference(0);
83}
84
86 CHECK_GE(x, start_x_);
87 CHECK_LE(x, end_x_);
88
89 const int64 span_x = CapSub(x, reference_x_);
90
91 if (span_x == kint64max) {
92 return SafeValuePostReference(x);
93 }
94 if (span_x == kint64min) {
95 return SafeValuePreReference(x);
96 }
97
98 const int64 span_y = CapProd(slope_, span_x);
99 if (IsAtBounds(span_y)) {
100 if (span_x >= 0) {
101 return SafeValuePostReference(x);
102 } else {
103 return SafeValuePreReference(x);
104 }
105 }
106
107 const int64 value = CapAdd(reference_y_, span_y);
108 if (IsAtBounds(value)) {
109 if (span_x >= 0) {
110 return SafeValuePostReference(x);
111 } else {
112 return SafeValuePreReference(x);
113 }
114 } else {
115 return value;
116 }
117}
118
119int64 PiecewiseSegment::SafeValuePostReference(int64 x) const {
120 DCHECK_GE(x, reference_x_);
121 const uint64 span_x = static_cast<uint64>(x) - reference_x_;
122 if (span_x == 0) {
123 return reference_y_;
124 }
125 if (slope_ == 0) {
126 // Zero slope segment.
127 return reference_y_;
128 } else if (slope_ > 0) {
129 // Positive slope segment.
130 const uint64 span_y = UnsignedCapProd(span_x, slope_);
131 if (reference_y_ == 0) {
132 return span_y > kint64max ? kint64max : span_y;
133 } else if (reference_y_ > 0) {
134 const uint64 unsigned_sum = UnsignedCapAdd(reference_y_, span_y);
135 return unsigned_sum > kint64max ? kint64max
136 : static_cast<int64>(unsigned_sum);
137 } else {
138 const uint64 opp_reference_y = -static_cast<uint64>(reference_y_);
139 if (span_y >= opp_reference_y) {
140 return span_y - opp_reference_y > kint64max
141 ? kint64max
142 : static_cast<int64>(span_y - opp_reference_y);
143 } else {
144 return opp_reference_y - span_y > static_cast<uint64>(kint64max) + 1
145 ? kint64min
146 : -static_cast<int64>(opp_reference_y - span_y);
147 }
148 }
149 } else {
150 // Negative slope segment.
151 const uint64 span_y = UnsignedCapProd(span_x, -slope_);
152 if (reference_y_ == 0) {
153 return span_y > kint64max ? kint64min : -static_cast<int64>(span_y);
154 } else if (reference_y_ < 0) {
155 const uint64 opp_reference_y = -static_cast<uint64>(reference_y_);
156 const uint64 opp_unsigned_sum = UnsignedCapAdd(opp_reference_y, span_y);
157 return opp_unsigned_sum > kint64max
158 ? kint64min
159 : -static_cast<int64>(opp_unsigned_sum);
160 } else {
161 if (reference_y_ >= span_y) {
162 return reference_y_ - span_y > kint64max
163 ? kint64max
164 : static_cast<int64>(reference_y_ - span_y);
165 } else {
166 return span_y - reference_y_ > static_cast<uint64>(kint64max) + 1
167 ? kint64min
168 : -static_cast<int64>(span_y - reference_y_);
169 }
170 }
171 }
172}
173
174int64 PiecewiseSegment::SafeValuePreReference(int64 x) const {
175 DCHECK_LE(x, reference_x_);
176 const uint64 span_x = static_cast<uint64>(reference_x_) - x;
177 if (slope_ == 0) {
178 // Zero slope segment.
179 return reference_y_;
180 } else if (slope_ > 0) {
181 // Positive slope segment.
182 const uint64 span_y = UnsignedCapProd(span_x, slope_);
183 if (reference_y_ == 0) {
184 return span_y > kint64max ? kint64min : -static_cast<int64>(span_y);
185 } else if (reference_y_ > 0) {
186 if (reference_y_ >= span_y) {
187 return reference_y_ - span_y > kint64max
188 ? kint64max
189 : static_cast<int64>(reference_y_ - span_y);
190 } else {
191 return span_y - reference_y_ > static_cast<uint64>(kint64max) + 1
192 ? kint64min
193 : -static_cast<uint64>(span_y - reference_y_);
194 }
195 } else {
196 const uint64 opp_reference_y = -static_cast<uint64>(reference_y_);
197 const uint64 opp_unsigned_sum = UnsignedCapAdd(opp_reference_y, span_y);
198 return opp_unsigned_sum > kint64max
199 ? kint64min
200 : -static_cast<uint64>(opp_unsigned_sum);
201 }
202 } else {
203 // Negative slope segment.
204 const uint64 span_y = UnsignedCapProd(span_x, -slope_);
205 if (reference_y_ == 0) {
206 return span_y > kint64max ? kint64max : span_y;
207 } else if (reference_y_ < 0) {
208 const uint64 opp_reference_y = -static_cast<uint64>(reference_y_);
209 if (span_y >= opp_reference_y) {
210 return span_y - opp_reference_y > kint64max
211 ? kint64max
212 : static_cast<int64>(span_y - opp_reference_y);
213 } else {
214 return opp_reference_y - span_y > static_cast<uint64>(kint64max) + 1
215 ? kint64min
216 : -static_cast<uint64>(opp_reference_y - span_y);
217 }
218 } else {
219 const uint64 unsigned_sum = UnsignedCapAdd(reference_y_, span_y);
220 return unsigned_sum > kint64max ? kint64max
221 : static_cast<int64>(unsigned_sum);
222 }
223 }
224}
225
227 const PiecewiseSegment& segment2) {
228 return segment1.start_x_ < segment2.start_x_;
229}
230
232 const PiecewiseSegment& segment) {
233 return point == kint64min || point < segment.start_x();
234}
235
237 end_x_ = std::max(end_x_, end_x);
238}
239
241 if (IsAtBounds(CapAdd(reference_x_, constant))) {
242 LOG(ERROR) << "Segment Overflow: " << DebugString();
243 return;
244 }
245 start_x_ = CapAdd(start_x_, constant);
246 end_x_ = CapAdd(end_x_, constant);
247 reference_x_ = CapAdd(reference_x_, constant);
248}
249
251 if (IsAtBounds(CapAdd(reference_y_, constant))) {
252 LOG(ERROR) << "Segment Overflow: " << DebugString();
253 return;
254 }
255 reference_y_ = CapAdd(reference_y_, constant);
256}
257
258std::string PiecewiseSegment::DebugString() const {
259 std::string result = absl::StrFormat(
260 "PiecewiseSegment(<start: (%d, %d), end: (%d, %d), "
261 "reference: (%d, %d), slope = %d>)",
262 start_x_, Value(start_x_), end_x_, Value(end_x_), reference_x_,
263 reference_y_, slope_);
264 return result;
265}
266
268
269PiecewiseLinearFunction::PiecewiseLinearFunction(
270 std::vector<PiecewiseSegment> segments)
271 : is_modified_(true),
272 is_convex_(false),
273 is_non_decreasing_(false),
274 is_non_increasing_(false) {
275 // Sort the segments in ascending order of start.
276 std::sort(segments.begin(), segments.end(), PiecewiseSegment::SortComparator);
277 // Check for overlapping segments.
278 for (int i = 0; i < segments.size() - 1; ++i) {
279 if (segments[i].end_x() > segments[i + 1].start_x()) {
280 LOG(FATAL) << "Overlapping segments: " << segments[i].DebugString()
281 << " & " << segments[i + 1].DebugString();
282 }
283 }
284 // Construct the piecewise linear function.
285 for (const auto& segment : segments) {
286 InsertSegment(segment);
287 }
288}
289
291 std::vector<int64> points_x, std::vector<int64> points_y,
292 std::vector<int64> slopes, std::vector<int64> other_points_x) {
293 CHECK_EQ(points_x.size(), points_y.size());
294 CHECK_EQ(points_x.size(), other_points_x.size());
295 CHECK_EQ(points_x.size(), slopes.size());
296 CHECK_GT(points_x.size(), 0);
297
298 std::vector<PiecewiseSegment> segments;
299 for (int i = 0; i < points_x.size(); ++i) {
300 segments.push_back(PiecewiseSegment(points_x[i], points_y[i], slopes[i],
301 other_points_x[i]));
302 }
303
304 return new PiecewiseLinearFunction(std::move(segments));
305}
306
308 std::vector<int64> points_x, std::vector<int64> points_y,
309 std::vector<int64> other_points_x) {
310 CHECK_EQ(points_x.size(), points_y.size());
311 CHECK_EQ(points_x.size(), other_points_x.size());
312 CHECK_GT(points_x.size(), 0);
313
314 std::vector<PiecewiseSegment> segments;
315 for (int i = 0; i < points_x.size(); ++i) {
316 segments.push_back(
317 PiecewiseSegment(points_x[i], points_y[i], 0, other_points_x[i]));
318 }
319
320 return new PiecewiseLinearFunction(std::move(segments));
321}
322
324 int64 initial_level, std::vector<int64> points_x,
325 std::vector<int64> slopes) {
326 CHECK_EQ(points_x.size(), slopes.size() - 1);
327 CHECK_GT(points_x.size(), 0);
328
329 int64 level = initial_level;
330 std::vector<PiecewiseSegment> segments;
331 PiecewiseSegment segment =
332 PiecewiseSegment(points_x[0], level, slopes[0], kint64min);
333 segments.push_back(segment);
334 level = segment.Value(points_x[0]);
335 for (int i = 1; i < points_x.size(); ++i) {
336 PiecewiseSegment segment =
337 PiecewiseSegment(points_x[i - 1], level, slopes[i], points_x[i]);
338 segments.push_back(segment);
339 level = segment.Value(points_x[i]);
340 }
341 segments.push_back(
342 PiecewiseSegment(points_x.back(), level, slopes.back(), kint64max));
343
344 return new PiecewiseLinearFunction(std::move(segments));
345}
346
348 int64 point_x, int64 point_y, int64 slope, int64 other_point_x) {
349 // Visual studio 2013: We cannot inline the vector in the
350 // PiecewiseLinearFunction ctor.
351 std::vector<PiecewiseSegment> segments = {
352 PiecewiseSegment(point_x, point_y, slope, other_point_x)};
353 return new PiecewiseLinearFunction(std::move(segments));
354}
355
357 int64 point_x, int64 point_y, int64 slope) {
358 std::vector<PiecewiseSegment> segments = {
359 PiecewiseSegment(point_x, point_y, slope, kint64max)};
360 return new PiecewiseLinearFunction(std::move(segments));
361}
362
364 int64 point_x, int64 point_y, int64 slope) {
365 std::vector<PiecewiseSegment> segments = {
366 PiecewiseSegment(point_x, point_y, slope, kint64min)};
367 return new PiecewiseLinearFunction(std::move(segments));
368}
369
371 int64 slope, int64 value) {
372 std::vector<PiecewiseSegment> segments = {
373 PiecewiseSegment(0, 0, 0, kint64min),
374 PiecewiseSegment(0, value, slope, kint64max)};
375 CHECK_GE(slope, 0);
376 CHECK_GE(value, 0);
377 return new PiecewiseLinearFunction(std::move(segments));
378}
379
381 int64 reference, int64 earliness_slope, int64 tardiness_slope) {
382 std::vector<PiecewiseSegment> segments = {
383 PiecewiseSegment(reference, 0, -earliness_slope, kint64min),
384 PiecewiseSegment(reference, 0, tardiness_slope, kint64max)};
385 CHECK_GE(earliness_slope, 0);
386 CHECK_GE(tardiness_slope, 0);
387 return new PiecewiseLinearFunction(std::move(segments));
388}
389
392 int64 early_slack, int64 late_slack, int64 earliness_slope,
393 int64 tardiness_slope) {
394 std::vector<PiecewiseSegment> segments = {
395 PiecewiseSegment(early_slack, 0, -earliness_slope, kint64min),
396 PiecewiseSegment(early_slack, 0, 0, late_slack),
397 PiecewiseSegment(late_slack, 0, tardiness_slope, kint64max)};
398
399 CHECK_GE(earliness_slope, 0);
400 CHECK_GE(tardiness_slope, 0);
401 return new PiecewiseLinearFunction(std::move(segments));
402}
403
405 int index = FindSegmentIndex(segments_, x);
406 if (index == kNotFound) {
407 return false;
408 }
409 if (segments_[index].end_x() < x) {
410 return false;
411 }
412 return true;
413}
414
416 const_cast<PiecewiseLinearFunction*>(this)->UpdateStatus();
417 return is_convex_;
418}
419
421 const_cast<PiecewiseLinearFunction*>(this)->UpdateStatus();
422 return is_non_decreasing_;
423}
424
426 const_cast<PiecewiseLinearFunction*>(this)->UpdateStatus();
427 return is_non_increasing_;
428}
429
431 if (!InDomain(x)) {
432 // TODO(user): Allow the user to specify the
433 // undefined value and use kint64max as the default.
434 return kint64max;
435 }
436 const int index = FindSegmentIndex(segments_, x);
437 return segments_[index].Value(x);
438}
439
441 int64 range_end) const {
442 if (IsNonDecreasing() && InDomain(range_end)) {
443 return Value(range_end);
444 } else if (IsNonIncreasing() && InDomain(range_start)) {
445 return Value(range_start);
446 }
447 int start_segment = -1;
448 int end_segment = -1;
449 if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,
450 &end_segment)) {
451 return kint64max;
452 }
453 CHECK_GE(end_segment, start_segment);
454
455 int64 range_maximum = kint64min;
456 if (InDomain(range_start)) {
457 range_maximum = std::max(Value(range_start), range_maximum);
458 }
459 if (InDomain(range_end)) {
460 range_maximum = std::max(Value(range_end), range_maximum);
461 }
462
463 for (int i = std::max(0, start_segment); i <= end_segment; ++i) {
464 if (PointInsideRange(segments_[i].start_x(), range_start, range_end)) {
465 range_maximum = std::max(range_maximum, segments_[i].start_y());
466 }
467 if (PointInsideRange(segments_[i].end_x(), range_start, range_end)) {
468 range_maximum = std::max(range_maximum, segments_[i].end_y());
469 }
470 }
471 return range_maximum;
472}
473
475 int64 range_end) const {
476 if (IsNonDecreasing() && InDomain(range_start)) {
477 return Value(range_start);
478 } else if (IsNonIncreasing() && InDomain(range_end)) {
479 return Value(range_end);
480 }
481 int start_segment = -1;
482 int end_segment = -1;
483 if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,
484 &end_segment)) {
485 return kint64max;
486 }
487 CHECK_GE(end_segment, start_segment);
488
489 int64 range_minimum = kint64max;
490 if (InDomain(range_start)) {
491 range_minimum = std::min(Value(range_start), range_minimum);
492 }
493 if (InDomain(range_end)) {
494 range_minimum = std::min(Value(range_end), range_minimum);
495 }
496
497 for (int i = std::max(0, start_segment); i <= end_segment; ++i) {
498 if (PointInsideRange(segments_[i].start_x(), range_start, range_end)) {
499 range_minimum = std::min(range_minimum, segments_[i].start_y());
500 }
501 if (PointInsideRange(segments_[i].end_x(), range_start, range_end)) {
502 range_minimum = std::min(range_minimum, segments_[i].end_y());
503 }
504 }
505 return range_minimum;
506}
507
509 return GetMaximum(segments_.front().start_x(), segments_.back().end_x());
510}
511
513 return GetMinimum(segments_.front().start_x(), segments_.back().end_x());
514}
515
516std::pair<int64, int64>
518 int64 range_end,
519 int64 value) const {
520 return GetSmallestRangeInValueRange(range_start, range_end, value, kint64max);
521}
522
524 int64 range_start, int64 range_end, int64 value) const {
525 return GetSmallestRangeInValueRange(range_start, range_end, kint64min, value);
526}
527
528namespace {
529std::pair<int64, int64> ComputeXFromY(int64 start_x, int64 start_y, int64 slope,
530 int64 y) {
531 DCHECK_NE(slope, 0);
532 const int64 delta_y = CapSub(y, start_y);
533 const int64 delta_x = delta_y / slope;
534 if ((delta_y >= 0 && slope >= 0) || (delta_y <= 0 && slope <= 0)) {
535 const int64 delta_x_down = delta_x;
536 const int64 delta_x_up = delta_y % slope == 0 ? delta_x : delta_x + 1;
537 return {delta_x_down + start_x, delta_x_up + start_x};
538 } else {
539 const int64 delta_x_down = delta_y % slope == 0 ? delta_x : delta_x - 1;
540 const int64 delta_x_up = -(-delta_y / slope);
541 return {delta_x_down + start_x, delta_x_up + start_x};
542 }
543}
544
545std::pair<int64, int64> GetRangeInValueRange(int64 start_x, int64 end_x,
546 int64 start_y, int64 end_y,
547 int64 slope, int64 value_min,
548 int64 value_max) {
549 if ((start_y > value_max && end_y > value_max) ||
550 (start_y < value_min && end_y < value_min)) {
551 return {kint64max, kint64min};
552 }
553 std::pair<int64, int64> x_range_max = {kint64max, kint64min};
554 if (start_y <= value_max && end_y <= value_max) {
555 x_range_max = {start_x, end_x};
556 } else if (start_y <= value_max || end_y <= value_max) {
557 const auto x = start_x == kint64min
558 ? ComputeXFromY(end_x, end_y, slope, value_max)
559 : ComputeXFromY(start_x, start_y, slope, value_max);
560 if (end_y <= value_max) {
561 x_range_max = {x.second, end_x};
562 } else {
563 x_range_max = {start_x, x.first};
564 }
565 }
566 std::pair<int64, int64> x_range_min = {kint64max, kint64min};
567 if (start_y >= value_min && end_y >= value_min) {
568 x_range_min = {start_x, end_x};
569 } else if (start_y >= value_min || end_y >= value_min) {
570 const auto x = start_x == kint64min
571 ? ComputeXFromY(end_x, end_y, slope, value_min)
572 : ComputeXFromY(start_x, start_y, slope, value_min);
573 if (end_y >= value_min) {
574 x_range_min = {x.second, end_x};
575 } else {
576 x_range_min = {start_x, x.first};
577 }
578 }
579 if (x_range_min.first > x_range_max.second ||
580 x_range_max.first > x_range_min.second) {
581 return {kint64max, kint64min};
582 }
583 return {std::max(x_range_min.first, x_range_max.first),
584 std::min(x_range_min.second, x_range_max.second)};
585}
586} // namespace
587
589 int64 range_start, int64 range_end, int64 value_min,
590 int64 value_max) const {
591 int64 reduced_range_start = kint64max;
592 int64 reduced_range_end = kint64min;
593 int start_segment = -1;
594 int end_segment = -1;
595 if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,
596 &end_segment)) {
597 return {reduced_range_start, reduced_range_end};
598 }
599 for (int i = std::max(0, start_segment); i <= end_segment; ++i) {
600 const auto& segment = segments_[i];
601 const int64 start_x = std::max(range_start, segment.start_x());
602 const int64 end_x = std::min(range_end, segment.end_x());
603 const int64 start_y = segment.Value(start_x);
604 const int64 end_y = segment.Value(end_x);
605 const std::pair<int64, int64> range = GetRangeInValueRange(
606 start_x, end_x, start_y, end_y, segment.slope(), value_min, value_max);
607 reduced_range_start = std::min(reduced_range_start, range.first);
608 reduced_range_end = std::max(reduced_range_end, range.second);
609 }
610 return {reduced_range_start, reduced_range_end};
611}
612
614 is_modified_ = true;
615 for (int i = 0; i < segments_.size(); ++i) {
616 segments_[i].AddConstantToX(constant);
617 }
618}
619
621 is_modified_ = true;
622 for (int i = 0; i < segments_.size(); ++i) {
623 segments_[i].AddConstantToY(constant);
624 }
625}
626
628 Operation(other, [](int64 a, int64 b) { return CapAdd(a, b); });
629}
630
632 Operation(other, [](int64 a, int64 b) { return CapSub(a, b); });
633}
634
635std::vector<PiecewiseLinearFunction*>
637 CHECK_GE(segments_.size(), 1);
638 if (IsConvex()) {
639 return {new PiecewiseLinearFunction(segments_)};
640 }
641
642 std::vector<PiecewiseLinearFunction*> convex_functions;
643 std::vector<PiecewiseSegment> convex_segments;
644
645 for (const PiecewiseSegment& segment : segments_) {
646 if (convex_segments.empty()) {
647 convex_segments.push_back(segment);
648 continue;
649 }
650
651 const PiecewiseSegment& last = convex_segments.back();
652 if (FormConvexPair(last, segment)) {
653 // The segment belongs to the convex sub-function formulated up to now.
654 convex_segments.push_back(segment);
655 } else {
656 convex_functions.push_back(new PiecewiseLinearFunction(convex_segments));
657 convex_segments.clear();
658 convex_segments.push_back(segment);
659 }
660 }
661
662 if (!convex_segments.empty()) {
663 convex_functions.push_back(
664 new PiecewiseLinearFunction(std::move(convex_segments)));
665 }
666 return convex_functions;
667}
668
670 std::string result = "PiecewiseLinearFunction(";
671 for (int i = 0; i < segments_.size(); ++i) {
672 result.append(segments_[i].DebugString());
673 result.append(" ");
674 }
675 return result;
676}
677
678void PiecewiseLinearFunction::InsertSegment(const PiecewiseSegment& segment) {
679 is_modified_ = true;
680 // No intersection.
681 if (segments_.empty() || segments_.back().end_x() < segment.start_x()) {
682 segments_.push_back(segment);
683 return;
684 }
685
686 // Common endpoint.
687 if (segments_.back().end_x() == segment.start_x()) {
688 if (segments_.back().end_y() == segment.start_y() &&
689 segments_.back().slope() == segment.slope()) {
690 segments_.back().ExpandEnd(segment.end_x());
691 return;
692 }
693 segments_.push_back(segment);
694 }
695}
696
697void PiecewiseLinearFunction::Operation(
698 const PiecewiseLinearFunction& other,
699 const std::function<int64(int64, int64)>& operation) {
700 is_modified_ = true;
701 std::vector<PiecewiseSegment> own_segments;
702 const std::vector<PiecewiseSegment>& other_segments = other.segments();
703 own_segments.swap(segments_);
704
705 std::set<int64> start_x_points;
706 for (int i = 0; i < own_segments.size(); ++i) {
707 start_x_points.insert(own_segments[i].start_x());
708 }
709 for (int i = 0; i < other_segments.size(); ++i) {
710 start_x_points.insert(other_segments[i].start_x());
711 }
712
713 for (int64 start_x : start_x_points) {
714 const int own_index = FindSegmentIndex(own_segments, start_x);
715 const int other_index = FindSegmentIndex(other_segments, start_x);
716 if (own_index >= 0 && other_index >= 0) {
717 const PiecewiseSegment& own_segment = own_segments[own_index];
718 const PiecewiseSegment& other_segment = other_segments[other_index];
719
720 const int64 end_x = std::min(own_segment.end_x(), other_segment.end_x());
721 const int64 start_y =
722 operation(own_segment.Value(start_x), other_segment.Value(start_x));
723 const int64 end_y =
724 operation(own_segment.Value(end_x), other_segment.Value(end_x));
725 const int64 slope = operation(own_segment.slope(), other_segment.slope());
726
727 int64 point_x, point_y, other_point_x;
728 if (IsAtBounds(start_y)) {
729 point_x = end_x;
730 point_y = end_y;
731 other_point_x = start_x;
732 } else {
733 point_x = start_x;
734 point_y = start_y;
735 other_point_x = end_x;
736 }
737 InsertSegment(PiecewiseSegment(point_x, point_y, slope, other_point_x));
738 }
739 }
740}
741
742bool PiecewiseLinearFunction::FindSegmentIndicesFromRange(
743 int64 range_start, int64 range_end, int* start_segment,
744 int* end_segment) const {
745 *start_segment = FindSegmentIndex(segments_, range_start);
746 *end_segment = FindSegmentIndex(segments_, range_end);
747 if (*start_segment == *end_segment) {
748 if (*start_segment < 0) {
749 // Given range before function's domain start.
750 return false;
751 }
752 if (segments_[*start_segment].end_x() < range_start) {
753 // Given range in a hole of the function's domain.
754 return false;
755 }
756 }
757 return true;
758}
759
760bool PiecewiseLinearFunction::IsConvexInternal() const {
761 for (int i = 1; i < segments_.size(); ++i) {
762 if (!FormConvexPair(segments_[i - 1], segments_[i])) {
763 return false;
764 }
765 }
766 return true;
767}
768
769bool PiecewiseLinearFunction::IsNonDecreasingInternal() const {
771 for (const auto& segment : segments_) {
772 const int64 start_y = segment.start_y();
773 const int64 end_y = segment.end_y();
774 if (end_y < start_y || start_y < value) return false;
775 value = end_y;
776 }
777 return true;
778}
779
780bool PiecewiseLinearFunction::IsNonIncreasingInternal() const {
782 for (const auto& segment : segments_) {
783 const int64 start_y = segment.start_y();
784 const int64 end_y = segment.end_y();
785 if (end_y > start_y || start_y > value) return false;
786 value = end_y;
787 }
788 return true;
789}
790
791} // 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_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define LOG(severity)
Definition: base/logging.h:420
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
std::pair< int64, int64 > GetSmallestRangeInValueRange(int64 range_start, int64 range_end, int64 value_min, int64 value_max) const
static PiecewiseLinearFunction * CreateEarlyTardyFunction(int64 reference, int64 earliness_slope, int64 tardiness_slope)
static PiecewiseLinearFunction * CreateFullDomainFunction(int64 initial_level, std::vector< int64 > points_x, std::vector< int64 > slopes)
static PiecewiseLinearFunction * CreatePiecewiseLinearFunction(std::vector< int64 > points_x, std::vector< int64 > points_y, std::vector< int64 > slopes, std::vector< int64 > other_points_x)
static PiecewiseLinearFunction * CreateStepFunction(std::vector< int64 > points_x, std::vector< int64 > points_y, std::vector< int64 > other_points_x)
std::vector< PiecewiseLinearFunction * > DecomposeToConvexFunctions() const
void Add(const PiecewiseLinearFunction &other)
static PiecewiseLinearFunction * CreateFixedChargeFunction(int64 slope, int64 value)
void Subtract(const PiecewiseLinearFunction &other)
std::pair< int64, int64 > GetSmallestRangeGreaterThanValue(int64 range_start, int64 range_end, int64 value) const
std::pair< int64, int64 > GetSmallestRangeLessThanValue(int64 range_start, int64 range_end, int64 value) const
static PiecewiseLinearFunction * CreateOneSegmentFunction(int64 point_x, int64 point_y, int64 slope, int64 other_point_x)
const std::vector< PiecewiseSegment > & segments() const
static PiecewiseLinearFunction * CreateEarlyTardyFunctionWithSlack(int64 early_slack, int64 late_slack, int64 earliness_slope, int64 tardiness_slope)
static PiecewiseLinearFunction * CreateRightRayFunction(int64 point_x, int64 point_y, int64 slope)
static PiecewiseLinearFunction * CreateLeftRayFunction(int64 point_x, int64 point_y, int64 slope)
static bool FindComparator(int64 point, const PiecewiseSegment &segment)
PiecewiseSegment(int64 point_x, int64 point_y, int64 slope, int64 other_point_x)
static bool SortComparator(const PiecewiseSegment &segment1, const PiecewiseSegment &segment2)
int64 value
static const int64 kint64max
int64_t int64
static const uint64 kuint64max
uint64_t uint64
static const int64 kint64min
const int ERROR
Definition: log_severity.h:32
const int FATAL
Definition: log_severity.h:32
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
int64 CapProd(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
int index
Definition: pack.cc:508