Google OR-Tools: ortools/util/piecewise_linear

Google OR-Tools: ortools/util/piecewise_linear_function.cc Source File

16#include <algorithm>

17#include <cstdint>

18#include <functional>

19#include <string>

20#include <utility>

21#include <vector>

23#include "absl/algorithm/container.h"

24#include "absl/container/btree_set.h"

25#include "absl/container/inlined_vector.h"

26#include "absl/log/check.h"

27#include "absl/strings/str_format.h"

28#include "absl/strings/string_view.h"

36namespace {

43int FindSegmentIndex(const std::vector<PiecewiseSegment>& segments, int64_t x) {

44 if (segments.empty() || segments.front().start_x() > x) {

46 }

50 std::vector<PiecewiseSegment>::const_iterator position = std::upper_bound(

52 if (position == segments.end()) {

53 return segments.size() - 1;

54 }

55 position -= position->start_x() > x ? 1 : 0;

57 return position - segments.begin();

58}

60inline bool IsAtBounds(int64_t value) {

62}

64inline bool PointInsideRange(int64_t point, int64_t range_start,

65 int64_t range_end) {

66 return range_start <= point && range_end >= point;

67}

73 return right.slope() >= left.slope() && right.start_x() == left.end_x() &&

74 right.start_y() == left.end_y();

75}

77uint64_t UnsignedCapAdd(uint64_t left, uint64_t right) {

79}

81uint64_t UnsignedCapProd(uint64_t left, uint64_t right) {

82 if (right == 0) return 0;

84 return left * right;

85}

86}

90 int64_t slope, int64_t other_point_x)

91 : slope_(slope), reference_x_(point_x), reference_y_(point_y) {

92 start_x_ = std::min(point_x, other_point_x);

93 end_x_ = std::max(point_x, other_point_x);

94 intersection_y_ =

95 reference_x_ < 0 ? SafeValuePostReference(0) : SafeValuePreReference(0);

96}

99 CHECK_GE(x, start_x_);

100 CHECK_LE(x, end_x_);

101

102 const int64_t span_x = CapSub(x, reference_x_);

103

105 return SafeValuePostReference(x);

106 }

108 return SafeValuePreReference(x);

109 }

110

111 const int64_t span_y = CapProd(slope_, span_x);

112 if (IsAtBounds(span_y)) {

113 if (span_x >= 0) {

114 return SafeValuePostReference(x);

115 } else {

116 return SafeValuePreReference(x);

117 }

118 }

119

120 const int64_t value = CapAdd(reference_y_, span_y);

121 if (IsAtBounds(value)) {

122 if (span_x >= 0) {

123 return SafeValuePostReference(x);

124 } else {

125 return SafeValuePreReference(x);

126 }

127 } else {

128 return value;

129 }

130}

131

132int64_t PiecewiseSegment::SafeValuePostReference(int64_t x) const {

133 DCHECK_GE(x, reference_x_);

134 const uint64_t span_x = static_cast<uint64_t>(x) - reference_x_;

135 if (span_x == 0) {

136 return reference_y_;

137 }

138 if (slope_ == 0) {

139

140 return reference_y_;

141 } else if (slope_ > 0) {

142

143 const uint64_t span_y = UnsignedCapProd(span_x, slope_);

144 if (reference_y_ == 0) {

146 } else if (reference_y_ > 0) {

147 const uint64_t unsigned_sum = UnsignedCapAdd(reference_y_, span_y);

149 : static_cast<int64_t>(unsigned_sum);

150 } else {

151 const uint64_t opp_reference_y = -static_cast<uint64_t>(reference_y_);

152 if (span_y >= opp_reference_y) {

153 return span_y - opp_reference_y > kint64max

155 : static_cast<int64_t>(span_y - opp_reference_y);

156 } else {

157 return opp_reference_y - span_y > static_cast<uint64_t>(kint64max) + 1

159 : -static_cast<int64_t>(opp_reference_y - span_y);

160 }

161 }

162 } else {

163

164 const uint64_t span_y = UnsignedCapProd(span_x, -slope_);

165 if (reference_y_ == 0) {

166 return span_y > kint64max ? kint64min : -static_cast<int64_t>(span_y);

167 } else if (reference_y_ < 0) {

168 const uint64_t opp_reference_y = -static_cast<uint64_t>(reference_y_);

169 const uint64_t opp_unsigned_sum = UnsignedCapAdd(opp_reference_y, span_y);

170 return opp_unsigned_sum > kint64max

172 : -static_cast<int64_t>(opp_unsigned_sum);

173 } else {

174 if (reference_y_ >= span_y) {

175 return reference_y_ - span_y > kint64max

177 : static_cast<int64_t>(reference_y_ - span_y);

178 } else {

179 return span_y - reference_y_ > static_cast<uint64_t>(kint64max) + 1

181 : -static_cast<int64_t>(span_y - reference_y_);

182 }

183 }

184 }

185}

186

187int64_t PiecewiseSegment::SafeValuePreReference(int64_t x) const {

188 DCHECK_LE(x, reference_x_);

189 const uint64_t span_x = static_cast<uint64_t>(reference_x_) - x;

190 if (slope_ == 0) {

191

192 return reference_y_;

193 } else if (slope_ > 0) {

194

195 const uint64_t span_y = UnsignedCapProd(span_x, slope_);

196 if (reference_y_ == 0) {

197 return span_y > kint64max ? kint64min : -static_cast<int64_t>(span_y);

198 } else if (reference_y_ > 0) {

199 if (reference_y_ >= span_y) {

200 return reference_y_ - span_y > kint64max

202 : static_cast<int64_t>(reference_y_ - span_y);

203 } else {

204 return span_y - reference_y_ > static_cast<uint64_t>(kint64max) + 1

206 : -static_cast<uint64_t>(span_y - reference_y_);

207 }

208 } else {

209 const uint64_t opp_reference_y = -static_cast<uint64_t>(reference_y_);

210 const uint64_t opp_unsigned_sum = UnsignedCapAdd(opp_reference_y, span_y);

211 return opp_unsigned_sum > kint64max

213 : -static_cast<uint64_t>(opp_unsigned_sum);

214 }

215 } else {

216

217 const uint64_t span_y = UnsignedCapProd(span_x, -slope_);

218 if (reference_y_ == 0) {

220 } else if (reference_y_ < 0) {

221 const uint64_t opp_reference_y = -static_cast<uint64_t>(reference_y_);

222 if (span_y >= opp_reference_y) {

223 return span_y - opp_reference_y > kint64max

225 : static_cast<int64_t>(span_y - opp_reference_y);

226 } else {

227 return opp_reference_y - span_y > static_cast<uint64_t>(kint64max) + 1

229 : -static_cast<uint64_t>(opp_reference_y - span_y);

230 }

231 } else {

232 const uint64_t unsigned_sum = UnsignedCapAdd(reference_y_, span_y);

234 : static_cast<int64_t>(unsigned_sum);

235 }

236 }

237}

238

241 return segment1.start_x_ < segment2.start_x_;

242}

243

248

250 end_x_ = std::max(end_x_, end_x);

251}

252

254 if (IsAtBounds(CapAdd(reference_x_, constant))) {

255 LOG(ERROR) << "Segment Overflow: " << DebugString();

256 return;

257 }

258 start_x_ = CapAdd(start_x_, constant);

259 end_x_ = CapAdd(end_x_, constant);

260 reference_x_ = CapAdd(reference_x_, constant);

261}

262

264 if (IsAtBounds(CapAdd(reference_y_, constant))) {

265 LOG(ERROR) << "Segment Overflow: " << DebugString();

266 return;

267 }

268 reference_y_ = CapAdd(reference_y_, constant);

269}

270

272 std::string result = absl::StrFormat(

273 "PiecewiseSegment(<start: (%d, %d), end: (%d, %d), "

274 "reference: (%d, %d), slope = %d>)",

275 start_x_, Value(start_x_), end_x_, Value(end_x_), reference_x_,

276 reference_y_, slope_);

277 return result;

278}

279

280

282

283PiecewiseLinearFunction::PiecewiseLinearFunction(

284 std::vector<PiecewiseSegment> segments)

285 : is_modified_(true),

286 is_convex_(false),

287 is_non_decreasing_(false),

288 is_non_increasing_(false) {

289

291

292 for (int i = 0; i < segments.size() - 1; ++i) {

293 if (segments[i].end_x() > segments[i + 1].start_x()) {

294 LOG(FATAL) << "Overlapping segments: " << segments[i].DebugString()

295 << " & " << segments[i + 1].DebugString();

296 }

297 }

298

299 for (const auto& segment : segments) {

300 InsertSegment(segment);

301 }

302}

303

305 std::vector<int64_t> points_x, std::vector<int64_t> points_y,

306 std::vector<int64_t> slopes, std::vector<int64_t> other_points_x) {

307 CHECK_EQ(points_x.size(), points_y.size());

308 CHECK_EQ(points_x.size(), other_points_x.size());

309 CHECK_EQ(points_x.size(), slopes.size());

310 CHECK_GT(points_x.size(), 0);

311

312 std::vector<PiecewiseSegment> segments;

313 for (int i = 0; i < points_x.size(); ++i) {

315 other_points_x[i]));

316 }

317

318 return new PiecewiseLinearFunction(std::move(segments));

319}

320

322 std::vector<int64_t> points_x, std::vector<int64_t> points_y,

323 std::vector<int64_t> other_points_x) {

324 CHECK_EQ(points_x.size(), points_y.size());

325 CHECK_EQ(points_x.size(), other_points_x.size());

326 CHECK_GT(points_x.size(), 0);

327

328 std::vector<PiecewiseSegment> segments;

329 for (int i = 0; i < points_x.size(); ++i) {

331 PiecewiseSegment(points_x[i], points_y[i], 0, other_points_x[i]));

332 }

333

334 return new PiecewiseLinearFunction(std::move(segments));

335}

336

338 int64_t initial_level, std::vector<int64_t> points_x,

339 std::vector<int64_t> slopes) {

340 CHECK_EQ(points_x.size(), slopes.size() - 1);

341 CHECK_GT(points_x.size(), 0);

342

343 int64_t level = initial_level;

344 std::vector<PiecewiseSegment> segments;

348 level = segment.Value(points_x[0]);

349 for (int i = 1; i < points_x.size(); ++i) {

351 PiecewiseSegment(points_x[i - 1], level, slopes[i], points_x[i]);

353 level = segment.Value(points_x[i]);

354 }

357

358 return new PiecewiseLinearFunction(std::move(segments));

359}

360

362 int64_t point_x, int64_t point_y, int64_t slope, int64_t other_point_x) {

363

364

365 std::vector<PiecewiseSegment> segments = {

367 return new PiecewiseLinearFunction(std::move(segments));

368}

369

371 int64_t point_x, int64_t point_y, int64_t slope) {

372 std::vector<PiecewiseSegment> segments = {

374 return new PiecewiseLinearFunction(std::move(segments));

375}

376

378 int64_t point_x, int64_t point_y, int64_t slope) {

379 std::vector<PiecewiseSegment> segments = {

381 return new PiecewiseLinearFunction(std::move(segments));

382}

383

385 int64_t slope, int64_t value) {

386 std::vector<PiecewiseSegment> segments = {

389 CHECK_GE(slope, 0);

390 CHECK_GE(value, 0);

391 return new PiecewiseLinearFunction(std::move(segments));

392}

393

395 int64_t reference, int64_t earliness_slope, int64_t tardiness_slope) {

396 std::vector<PiecewiseSegment> segments = {

399 CHECK_GE(earliness_slope, 0);

400 CHECK_GE(tardiness_slope, 0);

401 return new PiecewiseLinearFunction(std::move(segments));

402}

403

406 int64_t early_slack, int64_t late_slack, int64_t earliness_slope,

407 int64_t tardiness_slope) {

408 std::vector<PiecewiseSegment> segments = {

412

413 CHECK_GE(earliness_slope, 0);

414 CHECK_GE(tardiness_slope, 0);

415 return new PiecewiseLinearFunction(std::move(segments));

416}

417

419 int index = FindSegmentIndex(segments_, x);

421 return false;

422 }

423 if (segments_[index].end_x() < x) {

424 return false;

425 }

426 return true;

427}

428

430 const_cast<PiecewiseLinearFunction*>(this)->UpdateStatus();

431 return is_convex_;

432}

433

435 const_cast<PiecewiseLinearFunction*>(this)->UpdateStatus();

436 return is_non_decreasing_;

437}

438

440 const_cast<PiecewiseLinearFunction*>(this)->UpdateStatus();

441 return is_non_increasing_;

442}

443

446

447

449 }

450 const int index = FindSegmentIndex(segments_, x);

451 return segments_[index].Value(x);

452}

453

455 int64_t range_end) const {

457 return Value(range_end);

459 return Value(range_start);

460 }

461 int start_segment = -1;

462 int end_segment = -1;

463 if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,

464 &end_segment)) {

466 }

467 CHECK_GE(end_segment, start_segment);

468

469 int64_t range_maximum = kint64min;

471 range_maximum = std::max(Value(range_start), range_maximum);

472 }

474 range_maximum = std::max(Value(range_end), range_maximum);

475 }

476

477 for (int i = std::max(0, start_segment); i <= end_segment; ++i) {

478 if (PointInsideRange(segments_[i].start_x(), range_start, range_end)) {

479 range_maximum = std::max(range_maximum, segments_[i].start_y());

480 }

481 if (PointInsideRange(segments_[i].end_x(), range_start, range_end)) {

482 range_maximum = std::max(range_maximum, segments_[i].end_y());

483 }

484 }

485 return range_maximum;

486}

487

489 int64_t range_end) const {

491 return Value(range_start);

493 return Value(range_end);

494 }

495 int start_segment = -1;

496 int end_segment = -1;

497 if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,

498 &end_segment)) {

500 }

501 CHECK_GE(end_segment, start_segment);

502

503 int64_t range_minimum = kint64max;

505 range_minimum = std::min(Value(range_start), range_minimum);

506 }

508 range_minimum = std::min(Value(range_end), range_minimum);

509 }

510

511 for (int i = std::max(0, start_segment); i <= end_segment; ++i) {

512 if (PointInsideRange(segments_[i].start_x(), range_start, range_end)) {

513 range_minimum = std::min(range_minimum, segments_[i].start_y());

514 }

515 if (PointInsideRange(segments_[i].end_x(), range_start, range_end)) {

516 range_minimum = std::min(range_minimum, segments_[i].end_y());

517 }

518 }

519 return range_minimum;

520}

521

523 return GetMaximum(segments_.front().start_x(), segments_.back().end_x());

524}

525

527 return GetMinimum(segments_.front().start_x(), segments_.back().end_x());

528}

529

530std::pair<int64_t, int64_t>

532 int64_t range_end,

533 int64_t value) const {

535}

536

537std::pair<int64_t, int64_t>

539 int64_t range_end,

540 int64_t value) const {

542}

543

544namespace {

545std::pair<int64_t, int64_t> ComputeXFromY(int64_t start_x, int64_t start_y,

546 int64_t slope, int64_t y) {

547 DCHECK_NE(slope, 0);

548 const int64_t delta_y = CapSub(y, start_y);

549 const int64_t delta_x = delta_y / slope;

550 if ((delta_y >= 0 && slope >= 0) || (delta_y <= 0 && slope <= 0)) {

551 const int64_t delta_x_down = delta_x;

552 const int64_t delta_x_up = delta_y % slope == 0 ? delta_x : delta_x + 1;

553 return {delta_x_down + start_x, delta_x_up + start_x};

554 } else {

555 const int64_t delta_x_down = delta_y % slope == 0 ? delta_x : delta_x - 1;

556 const int64_t delta_x_up = -(-delta_y / slope);

557 return {delta_x_down + start_x, delta_x_up + start_x};

558 }

559}

560

561std::pair<int64_t, int64_t> GetRangeInValueRange(int64_t start_x, int64_t end_x,

562 int64_t start_y, int64_t end_y,

563 int64_t slope,

564 int64_t value_min,

565 int64_t value_max) {

566 if ((start_y > value_max && end_y > value_max) ||

567 (start_y < value_min && end_y < value_min)) {

569 }

571 if (start_y <= value_max && end_y <= value_max) {

572 x_range_max = {start_x, end_x};

573 } else if (start_y <= value_max || end_y <= value_max) {

575 ? ComputeXFromY(end_x, end_y, slope, value_max)

576 : ComputeXFromY(start_x, start_y, slope, value_max);

577 if (end_y <= value_max) {

578 x_range_max = {x.second, end_x};

579 } else {

580 x_range_max = {start_x, x.first};

581 }

582 }

584 if (start_y >= value_min && end_y >= value_min) {

585 x_range_min = {start_x, end_x};

586 } else if (start_y >= value_min || end_y >= value_min) {

588 ? ComputeXFromY(end_x, end_y, slope, value_min)

589 : ComputeXFromY(start_x, start_y, slope, value_min);

590 if (end_y >= value_min) {

591 x_range_min = {x.second, end_x};

592 } else {

593 x_range_min = {start_x, x.first};

594 }

595 }

596 if (x_range_min.first > x_range_max.second ||

597 x_range_max.first > x_range_min.second) {

599 }

600 return {std::max(x_range_min.first, x_range_max.first),

601 std::min(x_range_min.second, x_range_max.second)};

602}

603}

604

605std::pair<int64_t, int64_t>

607 int64_t range_end,

608 int64_t value_min,

609 int64_t value_max) const {

610 int64_t reduced_range_start = kint64max;

611 int64_t reduced_range_end = kint64min;

612 int start_segment = -1;

613 int end_segment = -1;

614 if (!FindSegmentIndicesFromRange(range_start, range_end, &start_segment,

615 &end_segment)) {

616 return {reduced_range_start, reduced_range_end};

617 }

618 for (int i = std::max(0, start_segment); i <= end_segment; ++i) {

619 const auto& segment = segments_[i];

620 const int64_t start_x = std::max(range_start, segment.start_x());

621 const int64_t end_x = std::min(range_end, segment.end_x());

622 const int64_t start_y = segment.Value(start_x);

623 const int64_t end_y = segment.Value(end_x);

624 const std::pair<int64_t, int64_t> range = GetRangeInValueRange(

625 start_x, end_x, start_y, end_y, segment.slope(), value_min, value_max);

626 reduced_range_start = std::min(reduced_range_start, range.first);

627 reduced_range_end = std::max(reduced_range_end, range.second);

628 }

629 return {reduced_range_start, reduced_range_end};

630}

631

633 is_modified_ = true;

634 for (int i = 0; i < segments_.size(); ++i) {

635 segments_[i].AddConstantToX(constant);

636 }

637}

638

640 is_modified_ = true;

641 for (int i = 0; i < segments_.size(); ++i) {

642 segments_[i].AddConstantToY(constant);

643 }

644}

645

647 Operation(other, [](int64_t a, int64_t b) { return CapAdd(a, b); });

648}

649

651 Operation(other, [](int64_t a, int64_t b) { return CapSub(a, b); });

652}

653

654std::vector<PiecewiseLinearFunction*>

656 CHECK_GE(segments_.size(), 1);

658 return {new PiecewiseLinearFunction(segments_)};

659 }

660

661 std::vector<PiecewiseLinearFunction*> convex_functions;

662 std::vector<PiecewiseSegment> convex_segments;

663

665 if (convex_segments.empty()) {

666 convex_segments.push_back(segment);

667 continue;

668 }

669

671 if (FormConvexPair(last, segment)) {

672

673 convex_segments.push_back(segment);

674 } else {

675 convex_functions.push_back(new PiecewiseLinearFunction(convex_segments));

676 convex_segments.clear();

677 convex_segments.push_back(segment);

678 }

679 }

680

681 if (!convex_segments.empty()) {

682 convex_functions.push_back(

683 new PiecewiseLinearFunction(std::move(convex_segments)));

684 }

685 return convex_functions;

686}

687

689 std::string result = "PiecewiseLinearFunction(";

690 for (int i = 0; i < segments_.size(); ++i) {

691 result.append(segments_[i].DebugString());

692 result.append(" ");

693 }

694 return result;

695}

696

697void PiecewiseLinearFunction::InsertSegment(const PiecewiseSegment& segment) {

698 is_modified_ = true;

699

700 if (segments_.empty() || segments_.back().end_x() < segment.start_x()) {

701 segments_.push_back(segment);

702 return;

703 }

704

705

706 if (segments_.back().end_x() == segment.start_x()) {

707 if (segments_.back().end_y() == segment.start_y() &&

708 segments_.back().slope() == segment.slope()) {

709 segments_.back().ExpandEnd(segment.end_x());

710 return;

711 }

712 segments_.push_back(segment);

713 }

714}

715

716void PiecewiseLinearFunction::Operation(

718 const std::function<int64_t(int64_t, int64_t)>& operation) {

719 is_modified_ = true;

720 std::vector<PiecewiseSegment> own_segments;

721 const std::vector<PiecewiseSegment>& other_segments = other.segments();

722 own_segments.swap(segments_);

723

724 absl::btree_set<int64_t> start_x_points;

725 for (int i = 0; i < own_segments.size(); ++i) {

726 start_x_points.insert(own_segments[i].start_x());

727 }

728 for (int i = 0; i < other_segments.size(); ++i) {

729 start_x_points.insert(other_segments[i].start_x());

730 }

731

732 for (int64_t start_x : start_x_points) {

733 const int own_index = FindSegmentIndex(own_segments, start_x);

734 const int other_index = FindSegmentIndex(other_segments, start_x);

735 if (own_index >= 0 && other_index >= 0) {

736 const PiecewiseSegment& own_segment = own_segments[own_index];

737 const PiecewiseSegment& other_segment = other_segments[other_index];

738

739 const int64_t end_x =

740 std::min(own_segment.end_x(), other_segment.end_x());

741 const int64_t start_y =

742 operation(own_segment.Value(start_x), other_segment.Value(start_x));

743 const int64_t end_y =

744 operation(own_segment.Value(end_x), other_segment.Value(end_x));

745 const int64_t slope =

746 operation(own_segment.slope(), other_segment.slope());

747

748 int64_t point_x, point_y, other_point_x;

749 if (IsAtBounds(start_y)) {

750 point_x = end_x;

751 point_y = end_y;

752 other_point_x = start_x;

753 } else {

754 point_x = start_x;

755 point_y = start_y;

756 other_point_x = end_x;

757 }

758 InsertSegment(PiecewiseSegment(point_x, point_y, slope, other_point_x));

759 }

760 }

761}

762

763bool PiecewiseLinearFunction::FindSegmentIndicesFromRange(

764 int64_t range_start, int64_t range_end, int* start_segment,

765 int* end_segment) const {

766 *start_segment = FindSegmentIndex(segments_, range_start);

767 *end_segment = FindSegmentIndex(segments_, range_end);

768 if (*start_segment == *end_segment) {

769 if (*start_segment < 0) {

770

771 return false;

772 }

773 if (segments_[*start_segment].end_x() < range_start) {

774

775 return false;

776 }

777 }

778 return true;

779}

780

781bool PiecewiseLinearFunction::IsConvexInternal() const {

782 for (int i = 1; i < segments_.size(); ++i) {

783 if (!FormConvexPair(segments_[i - 1], segments_[i])) {

784 return false;

785 }

786 }

787 return true;

788}

789

790bool PiecewiseLinearFunction::IsNonDecreasingInternal() const {

792 for (const auto& segment : segments_) {

793 const int64_t start_y = segment.start_y();

794 const int64_t end_y = segment.end_y();

795 if (end_y < start_y || start_y < value) return false;

796 value = end_y;

797 }

798 return true;

799}

800

801bool PiecewiseLinearFunction::IsNonIncreasingInternal() const {

803 for (const auto& segment : segments_) {

804 const int64_t start_y = segment.start_y();

805 const int64_t end_y = segment.end_y();

806 if (end_y > start_y || start_y > value) return false;

807 value = end_y;

808 }

809 return true;

810}

811

812

814

816 absl::InlinedVector<int64_t, 8> x_anchors,

817 absl::InlinedVector<int64_t, 8> y_anchors)

819 DCHECK(absl::c_is_sorted(x_anchors_));

820 DCHECK_EQ(x_anchors_.size(), y_anchors_.size());

821 DCHECK_NE(x_anchors_.size(), 1);

822}

823

825 absl::string_view line_prefix) const {

826 if (x_anchors_.size() <= 10) {

827 return "{ " + DUMP_VARS(x_anchors_, y_anchors_).str() + "}";

828 }

829 return absl::StrFormat("{\n%s%s\n%s%s\n}", line_prefix,

830 DUMP_VARS(x_anchors_).str(), line_prefix,

832}

833

835 int64_t x) const {

836 const int segment_index = GetSegmentIndex(x);

838 return GetValueOnSegment(x, segment_index);

839}

840

842 if (x_anchors_.empty()) return kNoValue;

843

844 int segment_index = kNoValue;

845 if (x <= x_anchors_[0]) {

846 segment_index = 0;

847 } else if (x >= x_anchors_.back()) {

848 segment_index = x_anchors_.size() - 2;

849 } else {

850 segment_index = GetSegmentIndex(x);

851 }

852

853 return GetValueOnSegment(x, segment_index);

854}

855

856int64_t FloatSlopePiecewiseLinearFunction::GetValueOnSegment(

857 int64_t x, int segment_index) const {

858 DCHECK_GE(segment_index, 0);

859 DCHECK_LE(segment_index, x_anchors_.size() - 2);

860 const double slope =

861 static_cast<double>(y_anchors_[segment_index + 1] -

862 y_anchors_[segment_index]) /

863 (x_anchors_[segment_index + 1] - x_anchors_[segment_index]);

865 y_anchors_[segment_index]);

866}

867

868}

int64_t ComputeConvexValue(int64_t x) const

Definition piecewise_linear_function.cc:841

FloatSlopePiecewiseLinearFunction()=default

int64_t ComputeInBoundsValue(int64_t x) const

Definition piecewise_linear_function.cc:834

std::string DebugString(absl::string_view line_prefix={}) const

Definition piecewise_linear_function.cc:824

const absl::InlinedVector< int64_t, 8 > & x_anchors() const

const absl::InlinedVector< int64_t, 8 > & y_anchors() const

static const int kNoValue

static IntOut Round(FloatIn x)

int64_t GetMaximum() const

Definition piecewise_linear_function.cc:522

std::vector< PiecewiseLinearFunction * > DecomposeToConvexFunctions() const

Definition piecewise_linear_function.cc:655

static PiecewiseLinearFunction * CreateFullDomainFunction(int64_t initial_level, std::vector< int64_t > points_x, std::vector< int64_t > slopes)

Definition piecewise_linear_function.cc:337

static PiecewiseLinearFunction * CreateRightRayFunction(int64_t point_x, int64_t point_y, int64_t slope)

Definition piecewise_linear_function.cc:370

bool IsNonIncreasing() const

Definition piecewise_linear_function.cc:439

std::pair< int64_t, int64_t > GetSmallestRangeLessThanValue(int64_t range_start, int64_t range_end, int64_t value) const

Definition piecewise_linear_function.cc:538

bool IsConvex() const

Definition piecewise_linear_function.cc:429

static const int kNotFound

static PiecewiseLinearFunction * CreateFixedChargeFunction(int64_t slope, int64_t value)

Definition piecewise_linear_function.cc:384

std::string DebugString() const

Definition piecewise_linear_function.cc:688

void Add(const PiecewiseLinearFunction &other)

Definition piecewise_linear_function.cc:646

static PiecewiseLinearFunction * CreateStepFunction(std::vector< int64_t > points_x, std::vector< int64_t > points_y, std::vector< int64_t > other_points_x)

Definition piecewise_linear_function.cc:321

int64_t GetMinimum() const

Definition piecewise_linear_function.cc:526

void AddConstantToY(int64_t constant)

Definition piecewise_linear_function.cc:639

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)

Definition piecewise_linear_function.cc:361

std::pair< int64_t, int64_t > GetSmallestRangeInValueRange(int64_t range_start, int64_t range_end, int64_t value_min, int64_t value_max) const

Definition piecewise_linear_function.cc:606

static PiecewiseLinearFunction * CreateLeftRayFunction(int64_t point_x, int64_t point_y, int64_t slope)

Definition piecewise_linear_function.cc:377

bool IsNonDecreasing() const

Definition piecewise_linear_function.cc:434

static PiecewiseLinearFunction * CreateEarlyTardyFunction(int64_t reference, int64_t earliness_slope, int64_t tardiness_slope)

Definition piecewise_linear_function.cc:394

void AddConstantToX(int64_t constant)

Definition piecewise_linear_function.cc:632

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)

Definition piecewise_linear_function.cc:304

static PiecewiseLinearFunction * CreateEarlyTardyFunctionWithSlack(int64_t early_slack, int64_t late_slack, int64_t earliness_slope, int64_t tardiness_slope)

Definition piecewise_linear_function.cc:405

int64_t Value(int64_t x) const

Definition piecewise_linear_function.cc:444

std::pair< int64_t, int64_t > GetSmallestRangeGreaterThanValue(int64_t range_start, int64_t range_end, int64_t value) const

Definition piecewise_linear_function.cc:531

bool InDomain(int64_t x) const

Definition piecewise_linear_function.cc:418

void Subtract(const PiecewiseLinearFunction &other)

Definition piecewise_linear_function.cc:650

static bool FindComparator(int64_t point, const PiecewiseSegment &segment)

Definition piecewise_linear_function.cc:244

static bool SortComparator(const PiecewiseSegment &segment1, const PiecewiseSegment &segment2)