21#include "absl/strings/str_format.h"
32int FindSegmentIndex(
const std::vector<PiecewiseSegment>& segments,
int64 x) {
33 if (segments.empty() || segments.front().start_x() > x) {
39 std::vector<PiecewiseSegment>::const_iterator position = std::upper_bound(
41 if (position == segments.end()) {
42 return segments.size() - 1;
44 position -= position->start_x() > x ? 1 : 0;
46 return position - segments.begin();
53inline bool PointInsideRange(
int64 point,
int64 range_start,
int64 range_end) {
54 return range_start <= point && range_end >= point;
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();
70 if (right == 0)
return 0;
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);
82 reference_x_ < 0 ? SafeValuePostReference(0) : SafeValuePreReference(0);
92 return SafeValuePostReference(x);
95 return SafeValuePreReference(x);
99 if (IsAtBounds(span_y)) {
101 return SafeValuePostReference(x);
103 return SafeValuePreReference(x);
108 if (IsAtBounds(
value)) {
110 return SafeValuePostReference(x);
112 return SafeValuePreReference(x);
119int64 PiecewiseSegment::SafeValuePostReference(
int64 x)
const {
121 const uint64 span_x =
static_cast<uint64>(x) - reference_x_;
128 }
else if (slope_ > 0) {
130 const uint64 span_y = UnsignedCapProd(span_x, slope_);
131 if (reference_y_ == 0) {
133 }
else if (reference_y_ > 0) {
134 const uint64 unsigned_sum = UnsignedCapAdd(reference_y_, span_y);
136 :
static_cast<int64>(unsigned_sum);
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
142 :
static_cast<int64>(span_y - opp_reference_y);
146 : -
static_cast<int64>(opp_reference_y - span_y);
151 const uint64 span_y = UnsignedCapProd(span_x, -slope_);
152 if (reference_y_ == 0) {
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);
159 : -
static_cast<int64>(opp_unsigned_sum);
161 if (reference_y_ >= span_y) {
164 :
static_cast<int64>(reference_y_ - span_y);
168 : -
static_cast<int64>(span_y - reference_y_);
174int64 PiecewiseSegment::SafeValuePreReference(
int64 x)
const {
176 const uint64 span_x =
static_cast<uint64>(reference_x_) - x;
180 }
else if (slope_ > 0) {
182 const uint64 span_y = UnsignedCapProd(span_x, slope_);
183 if (reference_y_ == 0) {
185 }
else if (reference_y_ > 0) {
186 if (reference_y_ >= span_y) {
189 :
static_cast<int64>(reference_y_ - span_y);
193 : -
static_cast<uint64>(span_y - reference_y_);
196 const uint64 opp_reference_y = -
static_cast<uint64>(reference_y_);
197 const uint64 opp_unsigned_sum = UnsignedCapAdd(opp_reference_y, span_y);
200 : -
static_cast<uint64>(opp_unsigned_sum);
204 const uint64 span_y = UnsignedCapProd(span_x, -slope_);
205 if (reference_y_ == 0) {
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
212 :
static_cast<int64>(span_y - opp_reference_y);
216 : -
static_cast<uint64>(opp_reference_y - span_y);
219 const uint64 unsigned_sum = UnsignedCapAdd(reference_y_, span_y);
221 :
static_cast<int64>(unsigned_sum);
228 return segment1.start_x_ < segment2.start_x_;
241 if (IsAtBounds(
CapAdd(reference_x_, constant))) {
245 start_x_ =
CapAdd(start_x_, constant);
246 end_x_ =
CapAdd(end_x_, constant);
247 reference_x_ =
CapAdd(reference_x_, constant);
251 if (IsAtBounds(
CapAdd(reference_y_, constant))) {
255 reference_y_ =
CapAdd(reference_y_, constant);
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_);
269PiecewiseLinearFunction::PiecewiseLinearFunction(
270 std::vector<PiecewiseSegment> segments)
271 : is_modified_(true),
273 is_non_decreasing_(false),
274 is_non_increasing_(false) {
278 for (
int i = 0; i < segments.size() - 1; ++i) {
280 LOG(
FATAL) <<
"Overlapping segments: " << segments[i].DebugString()
281 <<
" & " << segments[i + 1].DebugString();
285 for (
const auto& segment : segments) {
286 InsertSegment(segment);
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());
298 std::vector<PiecewiseSegment>
segments;
299 for (
int i = 0; i < points_x.size(); ++i) {
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());
314 std::vector<PiecewiseSegment>
segments;
315 for (
int i = 0; i < points_x.size(); ++i) {
324 int64 initial_level, std::vector<int64> points_x,
325 std::vector<int64> slopes) {
326 CHECK_EQ(points_x.size(), slopes.size() - 1);
329 int64 level = initial_level;
330 std::vector<PiecewiseSegment>
segments;
334 level = segment.
Value(points_x[0]);
335 for (
int i = 1; i < points_x.size(); ++i) {
339 level = segment.
Value(points_x[i]);
351 std::vector<PiecewiseSegment>
segments = {
358 std::vector<PiecewiseSegment>
segments = {
365 std::vector<PiecewiseSegment>
segments = {
372 std::vector<PiecewiseSegment>
segments = {
382 std::vector<PiecewiseSegment>
segments = {
393 int64 tardiness_slope) {
394 std::vector<PiecewiseSegment>
segments = {
405 int index = FindSegmentIndex(segments_, x);
409 if (segments_[
index].end_x() < x) {
422 return is_non_decreasing_;
427 return is_non_increasing_;
436 const int index = FindSegmentIndex(segments_, x);
437 return segments_[
index].Value(x);
441 int64 range_end)
const {
443 return Value(range_end);
445 return Value(range_start);
447 int start_segment = -1;
448 int end_segment = -1;
449 if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,
453 CHECK_GE(end_segment, start_segment);
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());
467 if (PointInsideRange(segments_[i].end_x(), range_start, range_end)) {
468 range_maximum =
std::max(range_maximum, segments_[i].end_y());
471 return range_maximum;
475 int64 range_end)
const {
477 return Value(range_start);
479 return Value(range_end);
481 int start_segment = -1;
482 int end_segment = -1;
483 if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,
487 CHECK_GE(end_segment, start_segment);
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());
501 if (PointInsideRange(segments_[i].end_x(), range_start, range_end)) {
502 range_minimum =
std::min(range_minimum, segments_[i].end_y());
505 return range_minimum;
509 return GetMaximum(segments_.front().start_x(), segments_.back().end_x());
513 return GetMinimum(segments_.front().start_x(), segments_.back().end_x());
516std::pair<int64, int64>
529std::pair<int64, int64> ComputeXFromY(
int64 start_x,
int64 start_y,
int64 slope,
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};
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};
545std::pair<int64, int64> GetRangeInValueRange(
int64 start_x,
int64 end_x,
549 if ((start_y > value_max && end_y > value_max) ||
550 (start_y < value_min && end_y < value_min)) {
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) {
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};
563 x_range_max = {start_x, x.first};
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) {
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};
576 x_range_min = {start_x, x.first};
579 if (x_range_min.first > x_range_max.second ||
580 x_range_max.first > x_range_min.second) {
583 return {
std::max(x_range_min.first, x_range_max.first),
584 std::min(x_range_min.second, x_range_max.second)};
590 int64 value_max)
const {
593 int start_segment = -1;
594 int end_segment = -1;
595 if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,
597 return {reduced_range_start, reduced_range_end};
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());
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);
610 return {reduced_range_start, reduced_range_end};
615 for (
int i = 0; i < segments_.size(); ++i) {
616 segments_[i].AddConstantToX(constant);
622 for (
int i = 0; i < segments_.size(); ++i) {
623 segments_[i].AddConstantToY(constant);
635std::vector<PiecewiseLinearFunction*>
642 std::vector<PiecewiseLinearFunction*> convex_functions;
643 std::vector<PiecewiseSegment> convex_segments;
646 if (convex_segments.empty()) {
647 convex_segments.push_back(segment);
652 if (FormConvexPair(last, segment)) {
654 convex_segments.push_back(segment);
657 convex_segments.clear();
658 convex_segments.push_back(segment);
662 if (!convex_segments.empty()) {
663 convex_functions.push_back(
666 return convex_functions;
670 std::string result =
"PiecewiseLinearFunction(";
671 for (
int i = 0; i < segments_.size(); ++i) {
678void PiecewiseLinearFunction::InsertSegment(
const PiecewiseSegment& segment) {
681 if (segments_.empty() || segments_.back().end_x() < segment.
start_x()) {
682 segments_.push_back(segment);
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());
693 segments_.push_back(segment);
697void PiecewiseLinearFunction::Operation(
698 const PiecewiseLinearFunction& other,
701 std::vector<PiecewiseSegment> own_segments;
702 const std::vector<PiecewiseSegment>& other_segments = other.segments();
703 own_segments.swap(segments_);
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());
709 for (
int i = 0; i < other_segments.size(); ++i) {
710 start_x_points.insert(other_segments[i].start_x());
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];
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));
724 operation(own_segment.Value(end_x), other_segment.Value(end_x));
725 const int64 slope = operation(own_segment.slope(), other_segment.slope());
727 int64 point_x, point_y, other_point_x;
728 if (IsAtBounds(start_y)) {
731 other_point_x = start_x;
735 other_point_x = end_x;
737 InsertSegment(PiecewiseSegment(point_x, point_y, slope, other_point_x));
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) {
752 if (segments_[*start_segment].end_x() < range_start) {
760bool PiecewiseLinearFunction::IsConvexInternal()
const {
761 for (
int i = 1; i < segments_.size(); ++i) {
762 if (!FormConvexPair(segments_[i - 1], segments_[i])) {
769bool PiecewiseLinearFunction::IsNonDecreasingInternal()
const {
771 for (
const auto& segment : segments_) {
774 if (end_y < start_y || start_y <
value)
return false;
780bool PiecewiseLinearFunction::IsNonIncreasingInternal()
const {
782 for (
const auto& segment : segments_) {
785 if (end_y > start_y || start_y >
value)
return false;
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK_GE(val1, val2)
#define CHECK_LE(val1, val2)
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)
int64 Value(int64 x) const
static PiecewiseLinearFunction * CreatePiecewiseLinearFunction(std::vector< int64 > points_x, std::vector< int64 > points_y, std::vector< int64 > slopes, std::vector< int64 > other_points_x)
void AddConstantToY(int64 constant)
void AddConstantToX(int64 constant)
static PiecewiseLinearFunction * CreateStepFunction(std::vector< int64 > points_x, std::vector< int64 > points_y, std::vector< int64 > other_points_x)
static const int kNotFound
std::vector< PiecewiseLinearFunction * > DecomposeToConvexFunctions() const
std::string DebugString() const
void Add(const PiecewiseLinearFunction &other)
bool IsNonDecreasing() const
static PiecewiseLinearFunction * CreateFixedChargeFunction(int64 slope, int64 value)
bool IsNonIncreasing() const
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)
bool InDomain(int64 x) const
static PiecewiseLinearFunction * CreateLeftRayFunction(int64 point_x, int64 point_y, int64 slope)
static bool FindComparator(int64 point, const PiecewiseSegment &segment)
int64 Value(int64 x) const
void AddConstantToY(int64 constant)
void AddConstantToX(int64 constant)
std::string DebugString() const
void ExpandEnd(int64 end_x)
PiecewiseSegment(int64 point_x, int64 point_y, int64 slope, int64 other_point_x)
static bool SortComparator(const PiecewiseSegment &segment1, const PiecewiseSegment &segment2)
static const int64 kint64max
static const uint64 kuint64max
static const int64 kint64min
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)