20#ifndef OR_TOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_
21#define OR_TOOLS_UTIL_PIECEWISE_LINEAR_FUNCTION_H_
30#include "absl/algorithm/container.h"
31#include "absl/container/inlined_vector.h"
32#include "absl/log/check.h"
33#include "absl/strings/string_view.h"
42 int64_t other_point_x);
45 int64_t
Value(int64_t x)
const;
47 int64_t
start_x()
const {
return start_x_; }
49 int64_t
end_x()
const {
return end_x_; }
55 int64_t
slope()
const {
return slope_; }
80 int64_t SafeValuePostReference(int64_t x)
const;
84 int64_t SafeValuePreReference(int64_t x)
const;
97 int64_t intersection_y_;
102class PiecewiseLinearFunction {
122 std::vector<int64_t> points_x, std::vector<int64_t> points_y,
123 std::vector<int64_t> slopes, std::vector<int64_t> other_points_x);
129 std::vector<int64_t> points_x, std::vector<int64_t> points_y,
130 std::vector<int64_t> other_points_x);
138 int64_t initial_level, std::vector<int64_t> points_x,
139 std::vector<int64_t> slopes);
143 int64_t point_x, int64_t point_y, int64_t slope, int64_t other_point_x);
170 int64_t reference, int64_t earliness_slope, int64_t tardiness_slope);
179 int64_t early_slack, int64_t late_slack, int64_t earliness_slope,
180 int64_t tardiness_slope);
192 int64_t
Value(int64_t x)
const;
200 int64_t
GetMaximum(int64_t range_start, int64_t range_end)
const;
204 int64_t
GetMinimum(int64_t range_start, int64_t range_end)
const;
208 int64_t range_start, int64_t range_end, int64_t value)
const;
212 int64_t range_start, int64_t range_end, int64_t value)
const;
216 int64_t range_start, int64_t range_end, int64_t value_min,
217 int64_t value_max)
const;
230 void Add(
const PiecewiseLinearFunction& other);
234 void Subtract(
const PiecewiseLinearFunction& other);
239 const std::vector<PiecewiseSegment>&
segments()
const {
return segments_; }
252 const std::function<int64_t(int64_t, int64_t)>& operation);
255 bool FindSegmentIndicesFromRange(int64_t range_start, int64_t range_end,
256 int* start_segment,
int* end_segment)
const;
257 void UpdateStatus() {
259 is_convex_ = IsConvexInternal();
260 is_non_decreasing_ = IsNonDecreasingInternal();
261 is_non_increasing_ = IsNonIncreasingInternal();
262 is_modified_ =
false;
265 bool IsConvexInternal()
const;
266 bool IsNonDecreasingInternal()
const;
267 bool IsNonIncreasingInternal()
const;
271 std::vector<PiecewiseSegment> segments_;
274 bool is_non_decreasing_;
275 bool is_non_increasing_;
293 absl::InlinedVector<int64_t, 8>
y_anchors);
296 *
this = std::move(other);
301 x_anchors_ = std::move(other.x_anchors_);
302 y_anchors_ = std::move(other.y_anchors_);
306 std::string
DebugString(absl::string_view line_prefix = {})
const;
308 const absl::InlinedVector<int64_t, 8>&
x_anchors()
const {
311 const absl::InlinedVector<int64_t, 8>&
y_anchors()
const {
329 int GetSegmentIndex(int64_t x)
const {
330 if (x_anchors_.empty() || x < x_anchors_[0] || x > x_anchors_.back()) {
333 if (x == x_anchors_.back())
return x_anchors_.size() - 2;
336 const auto upper_segment = absl::c_upper_bound(x_anchors_, x);
337 const int segment_index =
338 std::distance(x_anchors_.begin(), upper_segment) - 1;
339 DCHECK_GE(segment_index, 0);
340 DCHECK_LE(segment_index, x_anchors_.size() - 2);
341 return segment_index;
346 int64_t GetValueOnSegment(int64_t x,
int segment_index)
const;
349 absl::InlinedVector<int64_t, 8> x_anchors_;
355 absl::InlinedVector<int64_t, 8> y_anchors_;
int64_t ComputeConvexValue(int64_t x) const
FloatSlopePiecewiseLinearFunction(FloatSlopePiecewiseLinearFunction &&other) noexcept
FloatSlopePiecewiseLinearFunction()=default
int64_t ComputeInBoundsValue(int64_t x) const
std::string DebugString(absl::string_view line_prefix={}) const
const absl::InlinedVector< int64_t, 8 > & x_anchors() const
const absl::InlinedVector< int64_t, 8 > & y_anchors() const
static const int kNoValue
FloatSlopePiecewiseLinearFunction.
FloatSlopePiecewiseLinearFunction & operator=(FloatSlopePiecewiseLinearFunction &&other) noexcept
int64_t GetMaximum() const
Returns the maximum value of all the segments in the function.
std::vector< PiecewiseLinearFunction * > DecomposeToConvexFunctions() const
static PiecewiseLinearFunction * CreateFullDomainFunction(int64_t initial_level, std::vector< int64_t > points_x, std::vector< int64_t > slopes)
static PiecewiseLinearFunction * CreateRightRayFunction(int64_t point_x, int64_t point_y, int64_t slope)
bool IsNonIncreasing() const
Returns true if the piecewise linear function is non-increasing.
std::pair< int64_t, int64_t > GetSmallestRangeLessThanValue(int64_t range_start, int64_t range_end, int64_t value) const
static const int kNotFound
PiecewiseLinearFunction.
static PiecewiseLinearFunction * CreateFixedChargeFunction(int64_t slope, int64_t value)
std::string DebugString() const
void Add(const PiecewiseLinearFunction &other)
static PiecewiseLinearFunction * CreateStepFunction(std::vector< int64_t > points_x, std::vector< int64_t > points_y, std::vector< int64_t > other_points_x)
int64_t GetMinimum() const
Returns the minimum value of all the segments in the function.
void AddConstantToY(int64_t constant)
const std::vector< PiecewiseSegment > & segments() const
static PiecewiseLinearFunction * CreateOneSegmentFunction(int64_t point_x, int64_t point_y, int64_t slope, int64_t other_point_x)
Builds a function consisting of one segment.
std::pair< int64_t, int64_t > GetSmallestRangeInValueRange(int64_t range_start, int64_t range_end, int64_t value_min, int64_t value_max) const
static PiecewiseLinearFunction * CreateLeftRayFunction(int64_t point_x, int64_t point_y, int64_t slope)
bool IsNonDecreasing() const
Returns true if the piecewise linear function is non-decreasing.
static PiecewiseLinearFunction * CreateEarlyTardyFunction(int64_t reference, int64_t earliness_slope, int64_t tardiness_slope)
void AddConstantToX(int64_t constant)
static PiecewiseLinearFunction * CreatePiecewiseLinearFunction(std::vector< int64_t > points_x, std::vector< int64_t > points_y, std::vector< int64_t > slopes, std::vector< int64_t > other_points_x)
static PiecewiseLinearFunction * CreateEarlyTardyFunctionWithSlack(int64_t early_slack, int64_t late_slack, int64_t earliness_slope, int64_t tardiness_slope)
int64_t Value(int64_t x) const
Returns the value of the piecewise linear function for x.
std::pair< int64_t, int64_t > GetSmallestRangeGreaterThanValue(int64_t range_start, int64_t range_end, int64_t value) const
bool InDomain(int64_t x) const
Returns if x is in the domain of the function.
void Subtract(const PiecewiseLinearFunction &other)
int64_t end_x() const
Returns the end of the segment's domain.
int64_t start_y() const
Returns the value at the start of the segment's domain.
static bool FindComparator(int64_t point, const PiecewiseSegment &segment)
Comparison method useful for finding in which segment a point belongs.
static bool SortComparator(const PiecewiseSegment &segment1, const PiecewiseSegment &segment2)
Comparison method useful for sorting a sequence of segments.
std::string DebugString() const
void ExpandEnd(int64_t end_x)
void AddConstantToY(int64_t constant)
Adds 'constant' to the 'y' the segments.
int64_t intersection_y() const
Returns the intersection of the segment's extension with the y axis.
int64_t slope() const
Returns the segment's slope.
int64_t start_x() const
Returns the start of the segment's domain.
void AddConstantToX(int64_t constant)
Adds 'constant' to the 'x' the segments.
PiecewiseSegment(int64_t point_x, int64_t point_y, int64_t slope, int64_t other_point_x)
PiecewiseSegment.
int64_t Value(int64_t x) const
Returns the value of the segment at point x.
int64_t end_y() const
Returns the value at the end of the segment's domain.
In SWIG mode, we don't want anything besides these top-level includes.