21 #include "absl/strings/str_format.h"
22 #include "absl/strings/str_join.h"
31 "If true, caching for IntElement is disabled.");
36 void LinkVarExpr(Solver*
const s, IntExpr*
const expr, IntVar*
const var);
43 explicit VectorLess(
const std::vector<T>* values) : values_(values) {}
44 bool operator()(
const T& x,
const T& y)
const {
45 return (*values_)[x] < (*values_)[y];
49 const std::vector<T>* values_;
55 explicit VectorGreater(
const std::vector<T>* values) : values_(values) {}
56 bool operator()(
const T& x,
const T& y)
const {
57 return (*values_)[x] > (*values_)[y];
61 const std::vector<T>* values_;
66 class BaseIntExprElement :
public BaseIntExpr {
68 BaseIntExprElement(Solver*
const s, IntVar*
const e);
69 ~BaseIntExprElement()
override {}
70 int64 Min()
const override;
71 int64 Max()
const override;
73 void SetMin(
int64 m)
override;
74 void SetMax(
int64 m)
override;
76 bool Bound()
const override {
return (
expr_->Bound()); }
78 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
81 virtual int64 ElementValue(
int index)
const = 0;
82 virtual int64 ExprMin()
const = 0;
83 virtual int64 ExprMax()
const = 0;
88 void UpdateSupports()
const;
91 mutable int min_support_;
93 mutable int max_support_;
94 mutable bool initial_update_;
95 IntVarIterator*
const expr_iterator_;
98 BaseIntExprElement::BaseIntExprElement(Solver*
const s, IntVar*
const e)
105 initial_update_(true),
106 expr_iterator_(
expr_->MakeDomainIterator(true)) {
111 int64 BaseIntExprElement::Min()
const {
116 int64 BaseIntExprElement::Max()
const {
121 void BaseIntExprElement::Range(
int64* mi,
int64* ma) {
127 #define UPDATE_BASE_ELEMENT_INDEX_BOUNDS(test) \
128 const int64 emin = ExprMin(); \
129 const int64 emax = ExprMax(); \
131 int64 value = ElementValue(nmin); \
132 while (nmin < emax && test) { \
134 value = ElementValue(nmin); \
136 if (nmin == emax && test) { \
140 value = ElementValue(nmax); \
141 while (nmax >= nmin && test) { \
143 value = ElementValue(nmax); \
145 expr_->SetRange(nmin, nmax);
147 void BaseIntExprElement::SetMin(
int64 m) {
151 void BaseIntExprElement::SetMax(
int64 m) {
155 void BaseIntExprElement::SetRange(
int64 mi,
int64 ma) {
162 #undef UPDATE_BASE_ELEMENT_INDEX_BOUNDS
164 void BaseIntExprElement::UpdateSupports()
const {
165 if (initial_update_ || !
expr_->Contains(min_support_) ||
166 !
expr_->Contains(max_support_)) {
167 const int64 emin = ExprMin();
168 const int64 emax = ExprMax();
169 int64 min_value = ElementValue(emax);
170 int64 max_value = min_value;
171 int min_support = emax;
172 int max_support = emax;
175 if (expr_size == emax - emin + 1) {
179 if (
value > max_value) {
182 }
else if (
value < min_value) {
188 for (
const int64 index : InitAndGetValues(expr_iterator_)) {
191 if (
value > max_value) {
194 }
else if (
value < min_value) {
202 Solver* s = solver();
203 s->SaveAndSetValue(&min_, min_value);
204 s->SaveAndSetValue(&min_support_, min_support);
205 s->SaveAndSetValue(&max_, max_value);
206 s->SaveAndSetValue(&max_support_, max_support);
207 s->SaveAndSetValue(&initial_update_,
false);
216 class IntElementConstraint :
public CastConstraint {
218 IntElementConstraint(Solver*
const s,
const std::vector<int64>& values,
219 IntVar*
const index, IntVar*
const elem)
220 : CastConstraint(s, elem),
223 index_iterator_(index_->MakeDomainIterator(true)) {
227 void Post()
override {
229 solver()->MakeDelayedConstraintInitialPropagateCallback(
this);
230 index_->WhenDomain(d);
234 void InitialPropagate()
override {
235 index_->SetRange(0, values_.size() - 1);
238 int64 new_min = target_var_max;
239 int64 new_max = target_var_min;
241 for (
const int64 index : InitAndGetValues(index_iterator_)) {
243 if (value < target_var_min || value > target_var_max) {
246 if (
value < new_min) {
249 if (
value > new_max) {
260 std::string DebugString()
const override {
261 return absl::StrFormat(
"IntElementConstraint(%s, %s, %s)",
262 absl::StrJoin(values_,
", "), index_->DebugString(),
266 void Accept(ModelVisitor*
const visitor)
const override {
267 visitor->BeginVisitConstraint(ModelVisitor::kElementEqual,
this);
268 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument, values_);
269 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndexArgument,
271 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
273 visitor->EndVisitConstraint(ModelVisitor::kElementEqual,
this);
277 const std::vector<int64> values_;
278 IntVar*
const index_;
279 IntVarIterator*
const index_iterator_;
285 IntVar* BuildDomainIntVar(Solver*
const solver, std::vector<int64>* values);
287 class IntExprElement :
public BaseIntExprElement {
289 IntExprElement(Solver*
const s,
const std::vector<int64>& vals,
291 : BaseIntExprElement(s, expr), values_(vals) {}
293 ~IntExprElement()
override {}
295 std::string
name()
const override {
296 const int size = values_.size();
298 return absl::StrFormat(
"IntElement(array of size %d, %s)", size,
301 return absl::StrFormat(
"IntElement(%s, %s)", absl::StrJoin(values_,
", "),
306 std::string DebugString()
const override {
307 const int size = values_.size();
309 return absl::StrFormat(
"IntElement(array of size %d, %s)", size,
310 expr_->DebugString());
312 return absl::StrFormat(
"IntElement(%s, %s)", absl::StrJoin(values_,
", "),
313 expr_->DebugString());
317 IntVar* CastToVar()
override {
318 Solver*
const s = solver();
319 IntVar*
const var = s->MakeIntVar(values_);
320 s->AddCastConstraint(
321 s->RevAlloc(
new IntElementConstraint(s, values_,
expr_,
var)),
var,
326 void Accept(ModelVisitor*
const visitor)
const override {
327 visitor->BeginVisitIntegerExpression(ModelVisitor::kElement,
this);
328 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument, values_);
329 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndexArgument,
331 visitor->EndVisitIntegerExpression(ModelVisitor::kElement,
this);
335 int64 ElementValue(
int index)
const override {
337 return values_[
index];
339 int64 ExprMin()
const override {
return std::max<int64>(0,
expr_->Min()); }
340 int64 ExprMax()
const override {
341 return values_.empty() ? 0
342 : std::min<int64>(values_.size() - 1,
expr_->Max());
346 const std::vector<int64> values_;
351 class RangeMinimumQueryExprElement :
public BaseIntExpr {
353 RangeMinimumQueryExprElement(Solver* solver,
const std::vector<int64>& values,
355 ~RangeMinimumQueryExprElement()
override {}
356 int64 Min()
const override;
357 int64 Max()
const override;
359 void SetMin(
int64 m)
override;
360 void SetMax(
int64 m)
override;
362 bool Bound()
const override {
return (index_->Bound()); }
364 void WhenRange(Demon* d)
override { index_->WhenRange(d); }
365 IntVar* CastToVar()
override {
369 IntVar*
const var = solver()->MakeIntVar(min_rmq_.array());
370 solver()->AddCastConstraint(solver()->RevAlloc(
new IntElementConstraint(
371 solver(), min_rmq_.array(), index_,
var)),
375 void Accept(ModelVisitor*
const visitor)
const override {
376 visitor->BeginVisitIntegerExpression(ModelVisitor::kElement,
this);
377 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument,
379 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndexArgument,
381 visitor->EndVisitIntegerExpression(ModelVisitor::kElement,
this);
385 int64 IndexMin()
const {
return std::max<int64>(0, index_->Min()); }
386 int64 IndexMax()
const {
387 return std::min<int64>(min_rmq_.array().size() - 1, index_->Max());
390 IntVar*
const index_;
391 const RangeMinimumQuery<int64, std::less<int64>> min_rmq_;
392 const RangeMinimumQuery<int64, std::greater<int64>> max_rmq_;
395 RangeMinimumQueryExprElement::RangeMinimumQueryExprElement(
396 Solver* solver,
const std::vector<int64>& values, IntVar*
index)
397 : BaseIntExpr(solver), index_(
index), min_rmq_(values), max_rmq_(values) {
398 CHECK(solver !=
nullptr);
402 int64 RangeMinimumQueryExprElement::Min()
const {
403 return min_rmq_.GetMinimumFromRange(IndexMin(), IndexMax() + 1);
406 int64 RangeMinimumQueryExprElement::Max()
const {
407 return max_rmq_.GetMinimumFromRange(IndexMin(), IndexMax() + 1);
410 void RangeMinimumQueryExprElement::Range(
int64* mi,
int64* ma) {
411 const int64 range_min = IndexMin();
412 const int64 range_max = IndexMax() + 1;
413 *mi = min_rmq_.GetMinimumFromRange(range_min, range_max);
414 *ma = max_rmq_.GetMinimumFromRange(range_min, range_max);
417 #define UPDATE_RMQ_BASE_ELEMENT_INDEX_BOUNDS(test) \
418 const std::vector<int64>& values = min_rmq_.array(); \
419 int64 index_min = IndexMin(); \
420 int64 index_max = IndexMax(); \
421 int64 value = values[index_min]; \
422 while (index_min < index_max && (test)) { \
424 value = values[index_min]; \
426 if (index_min == index_max && (test)) { \
429 value = values[index_max]; \
430 while (index_max >= index_min && (test)) { \
432 value = values[index_max]; \
434 index_->SetRange(index_min, index_max);
436 void RangeMinimumQueryExprElement::SetMin(
int64 m) {
440 void RangeMinimumQueryExprElement::SetMax(
int64 m) {
444 void RangeMinimumQueryExprElement::SetRange(
int64 mi,
int64 ma) {
451 #undef UPDATE_RMQ_BASE_ELEMENT_INDEX_BOUNDS
455 class IncreasingIntExprElement :
public BaseIntExpr {
457 IncreasingIntExprElement(Solver*
const s,
const std::vector<int64>& values,
458 IntVar*
const index);
459 ~IncreasingIntExprElement()
override {}
461 int64 Min()
const override;
462 void SetMin(
int64 m)
override;
463 int64 Max()
const override;
464 void SetMax(
int64 m)
override;
466 bool Bound()
const override {
return (index_->Bound()); }
468 std::string
name()
const override {
469 return absl::StrFormat(
"IntElement(%s, %s)", absl::StrJoin(values_,
", "),
472 std::string DebugString()
const override {
473 return absl::StrFormat(
"IntElement(%s, %s)", absl::StrJoin(values_,
", "),
474 index_->DebugString());
477 void Accept(ModelVisitor*
const visitor)
const override {
478 visitor->BeginVisitIntegerExpression(ModelVisitor::kElement,
this);
479 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument, values_);
480 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndexArgument,
482 visitor->EndVisitIntegerExpression(ModelVisitor::kElement,
this);
485 void WhenRange(Demon* d)
override { index_->WhenRange(d); }
487 IntVar* CastToVar()
override {
488 Solver*
const s = solver();
489 IntVar*
const var = s->MakeIntVar(values_);
495 const std::vector<int64> values_;
496 IntVar*
const index_;
499 IncreasingIntExprElement::IncreasingIntExprElement(
500 Solver*
const s,
const std::vector<int64>& values, IntVar*
const index)
501 : BaseIntExpr(s), values_(values), index_(
index) {
506 int64 IncreasingIntExprElement::Min()
const {
507 const int64 expression_min = std::max<int64>(0, index_->Min());
508 return (expression_min < values_.size() ? values_[expression_min]
512 void IncreasingIntExprElement::SetMin(
int64 m) {
513 const int64 index_min = std::max<int64>(0, index_->Min());
514 const int64 index_max = std::min<int64>(values_.size() - 1, index_->Max());
516 if (index_min > index_max || m > values_[index_max]) {
520 const std::vector<int64>::const_iterator first =
521 std::lower_bound(values_.begin(), values_.end(), m);
522 const int64 new_index_min = first - values_.begin();
523 index_->SetMin(new_index_min);
526 int64 IncreasingIntExprElement::Max()
const {
527 const int64 expression_max =
528 std::min<int64>(values_.size() - 1, index_->Max());
529 return (expression_max >= 0 ? values_[expression_max] :
kint64max);
532 void IncreasingIntExprElement::SetMax(
int64 m) {
533 int64 index_min = std::max<int64>(0, index_->Min());
534 if (m < values_[index_min]) {
538 const std::vector<int64>::const_iterator last_after =
539 std::upper_bound(values_.begin(), values_.end(), m);
540 const int64 new_index_max = (last_after - values_.begin()) - 1;
541 index_->SetRange(0, new_index_max);
544 void IncreasingIntExprElement::SetRange(
int64 mi,
int64 ma) {
548 const int64 index_min = std::max<int64>(0, index_->Min());
549 const int64 index_max = std::min<int64>(values_.size() - 1, index_->Max());
551 if (mi > ma || ma < values_[index_min] || mi > values_[index_max]) {
555 const std::vector<int64>::const_iterator first =
556 std::lower_bound(values_.begin(), values_.end(), mi);
557 const int64 new_index_min = first - values_.begin();
559 const std::vector<int64>::const_iterator last_after =
560 std::upper_bound(first, values_.end(), ma);
561 const int64 new_index_max = (last_after - values_.begin()) - 1;
564 index_->SetRange(new_index_min, new_index_max);
568 IntExpr* BuildElement(Solver*
const solver,
const std::vector<int64>& values,
569 IntVar*
const index) {
573 solver->AddConstraint(solver->MakeBetweenCt(
index, 0, values.size() - 1));
574 return solver->MakeIntConst(values[0]);
579 std::vector<int64> ones;
581 for (
int i = 0; i < values.size(); ++i) {
582 if (values[i] == 1) {
588 if (ones.size() == 1) {
590 solver->AddConstraint(solver->MakeBetweenCt(
index, 0, values.size() - 1));
591 return solver->MakeIsEqualCstVar(
index, ones.back());
592 }
else if (ones.size() == values.size() - 1) {
593 solver->AddConstraint(solver->MakeBetweenCt(
index, 0, values.size() - 1));
594 return solver->MakeIsDifferentCstVar(
index, first_zero);
595 }
else if (ones.size() == ones.back() - ones.front() + 1) {
596 solver->AddConstraint(solver->MakeBetweenCt(
index, 0, values.size() - 1));
597 IntVar*
const b = solver->MakeBoolVar(
"ContiguousBooleanElementVar");
598 solver->AddConstraint(
599 solver->MakeIsBetweenCt(
index, ones.front(), ones.back(),
b));
602 IntVar*
const b = solver->MakeBoolVar(
"NonContiguousBooleanElementVar");
603 solver->AddConstraint(solver->MakeBetweenCt(
index, 0, values.size() - 1));
604 solver->AddConstraint(solver->MakeIsMemberCt(
index, ones,
b));
608 IntExpr* cache =
nullptr;
609 if (!absl::GetFlag(FLAGS_cp_disable_element_cache)) {
610 cache = solver->Cache()->FindVarConstantArrayExpression(
611 index, values, ModelCache::VAR_CONSTANT_ARRAY_ELEMENT);
613 if (cache !=
nullptr) {
616 IntExpr* result =
nullptr;
617 if (values.size() >= 2 &&
index->Min() == 0 &&
index->Max() == 1) {
618 result = solver->MakeSum(solver->MakeProd(
index, values[1] - values[0]),
620 }
else if (values.size() == 2 &&
index->Contains(0) &&
index->Contains(1)) {
621 solver->AddConstraint(solver->MakeBetweenCt(
index, 0, 1));
622 result = solver->MakeSum(solver->MakeProd(
index, values[1] - values[0]),
625 result = solver->MakeSum(
index, values[0]);
627 result = solver->RegisterIntExpr(solver->RevAlloc(
628 new IncreasingIntExprElement(solver, values,
index)));
630 if (solver->parameters().use_element_rmq()) {
631 result = solver->RegisterIntExpr(solver->RevAlloc(
632 new RangeMinimumQueryExprElement(solver, values,
index)));
634 result = solver->RegisterIntExpr(
635 solver->RevAlloc(
new IntExprElement(solver, values,
index)));
638 if (!absl::GetFlag(FLAGS_cp_disable_element_cache)) {
639 solver->Cache()->InsertVarConstantArrayExpression(
640 result,
index, values, ModelCache::VAR_CONSTANT_ARRAY_ELEMENT);
647 IntExpr* Solver::MakeElement(
const std::vector<int64>& values,
651 if (
index->Bound()) {
652 return MakeIntConst(values[
index->Min()]);
654 return BuildElement(
this, values,
index);
657 IntExpr* Solver::MakeElement(
const std::vector<int>& values,
661 if (
index->Bound()) {
662 return MakeIntConst(values[
index->Min()]);
670 class IntExprFunctionElement :
public BaseIntExprElement {
674 ~IntExprFunctionElement()
override;
676 std::string
name()
const override {
677 return absl::StrFormat(
"IntFunctionElement(%s)",
expr_->name());
680 std::string DebugString()
const override {
681 return absl::StrFormat(
"IntFunctionElement(%s)",
expr_->DebugString());
684 void Accept(ModelVisitor*
const visitor)
const override {
686 visitor->BeginVisitIntegerExpression(ModelVisitor::kElement,
this);
687 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndexArgument,
689 visitor->VisitInt64ToInt64Extension(values_,
expr_->Min(),
expr_->Max());
690 visitor->EndVisitIntegerExpression(ModelVisitor::kElement,
this);
694 int64 ElementValue(
int index)
const override {
return values_(
index); }
695 int64 ExprMin()
const override {
return expr_->Min(); }
696 int64 ExprMax()
const override {
return expr_->Max(); }
699 Solver::IndexEvaluator1 values_;
702 IntExprFunctionElement::IntExprFunctionElement(Solver*
const s,
703 Solver::IndexEvaluator1 values,
705 : BaseIntExprElement(s, e), values_(std::move(values)) {
706 CHECK(values_ !=
nullptr);
709 IntExprFunctionElement::~IntExprFunctionElement() {}
713 class IncreasingIntExprFunctionElement :
public BaseIntExpr {
715 IncreasingIntExprFunctionElement(Solver*
const s,
718 : BaseIntExpr(s), values_(std::move(values)), index_(
index) {
719 DCHECK(values_ !=
nullptr);
724 ~IncreasingIntExprFunctionElement()
override {}
726 int64 Min()
const override {
return values_(index_->Min()); }
728 void SetMin(
int64 m)
override {
729 const int64 index_min = index_->Min();
730 const int64 index_max = index_->Max();
731 if (m > values_(index_max)) {
734 const int64 new_index_min = FindNewIndexMin(index_min, index_max, m);
735 index_->SetMin(new_index_min);
738 int64 Max()
const override {
return values_(index_->Max()); }
740 void SetMax(
int64 m)
override {
741 int64 index_min = index_->Min();
742 int64 index_max = index_->Max();
743 if (m < values_(index_min)) {
746 const int64 new_index_max = FindNewIndexMax(index_min, index_max, m);
747 index_->SetMax(new_index_max);
751 const int64 index_min = index_->Min();
752 const int64 index_max = index_->Max();
753 const int64 value_min = values_(index_min);
754 const int64 value_max = values_(index_max);
755 if (mi > ma || ma < value_min || mi > value_max) {
758 if (mi <= value_min && ma >= value_max) {
763 const int64 new_index_min = FindNewIndexMin(index_min, index_max, mi);
764 const int64 new_index_max = FindNewIndexMax(new_index_min, index_max, ma);
766 index_->SetRange(new_index_min, new_index_max);
769 std::string
name()
const override {
770 return absl::StrFormat(
"IncreasingIntExprFunctionElement(values, %s)",
774 std::string DebugString()
const override {
775 return absl::StrFormat(
"IncreasingIntExprFunctionElement(values, %s)",
776 index_->DebugString());
779 void WhenRange(Demon* d)
override { index_->WhenRange(d); }
781 void Accept(ModelVisitor*
const visitor)
const override {
786 if (index_->Min() == 0) {
790 visitor->VisitInt64ToInt64Extension(values_, index_->Min(),
798 if (m <= values_(index_min)) {
805 int64 index_lower_bound = index_min;
806 int64 index_upper_bound = index_max;
807 while (index_upper_bound - index_lower_bound > 1) {
808 DCHECK_LT(values_(index_lower_bound), m);
809 DCHECK_GE(values_(index_upper_bound), m);
810 const int64 pivot = (index_lower_bound + index_upper_bound) / 2;
811 const int64 pivot_value = values_(pivot);
812 if (pivot_value < m) {
813 index_lower_bound = pivot;
815 index_upper_bound = pivot;
818 DCHECK(values_(index_upper_bound) >= m);
819 return index_upper_bound;
823 if (m >= values_(index_max)) {
830 int64 index_lower_bound = index_min;
831 int64 index_upper_bound = index_max;
832 while (index_upper_bound - index_lower_bound > 1) {
833 DCHECK_LE(values_(index_lower_bound), m);
834 DCHECK_GT(values_(index_upper_bound), m);
835 const int64 pivot = (index_lower_bound + index_upper_bound) / 2;
836 const int64 pivot_value = values_(pivot);
837 if (pivot_value > m) {
838 index_upper_bound = pivot;
840 index_lower_bound = pivot;
843 DCHECK(values_(index_lower_bound) <= m);
844 return index_lower_bound;
848 IntVar*
const index_;
856 RevAlloc(
new IntExprFunctionElement(
this, std::move(values),
index)));
864 RevAlloc(
new IncreasingIntExprFunctionElement(
this, values,
index)));
872 new IncreasingIntExprFunctionElement(
this, opposite_values,
index))));
879 class IntIntExprFunctionElement :
public BaseIntExpr {
883 ~IntIntExprFunctionElement()
override;
884 std::string DebugString()
const override {
885 return absl::StrFormat(
"IntIntFunctionElement(%s,%s)",
886 expr1_->DebugString(), expr2_->DebugString());
888 int64 Min()
const override;
889 int64 Max()
const override;
890 void Range(
int64* lower_bound,
int64* upper_bound)
override;
891 void SetMin(
int64 lower_bound)
override;
892 void SetMax(
int64 upper_bound)
override;
893 void SetRange(
int64 lower_bound,
int64 upper_bound)
override;
894 bool Bound()
const override {
return expr1_->Bound() && expr2_->Bound(); }
896 void WhenRange(Demon* d)
override {
897 expr1_->WhenRange(d);
898 expr2_->WhenRange(d);
901 void Accept(ModelVisitor*
const visitor)
const override {
908 const int64 expr1_min = expr1_->Min();
909 const int64 expr1_max = expr1_->Max();
912 for (
int i = expr1_min; i <= expr1_max; ++i) {
913 visitor->VisitInt64ToInt64Extension(
914 [
this, i](
int64 j) {
return values_(i, j); }, expr2_->Min(),
921 int64 ElementValue(
int index1,
int index2)
const {
922 return values_(index1, index2);
924 void UpdateSupports()
const;
926 IntVar*
const expr1_;
927 IntVar*
const expr2_;
929 mutable int min_support1_;
930 mutable int min_support2_;
932 mutable int max_support1_;
933 mutable int max_support2_;
934 mutable bool initial_update_;
936 IntVarIterator*
const expr1_iterator_;
937 IntVarIterator*
const expr2_iterator_;
940 IntIntExprFunctionElement::IntIntExprFunctionElement(
952 initial_update_(true),
953 values_(std::move(values)),
954 expr1_iterator_(expr1_->MakeDomainIterator(true)),
955 expr2_iterator_(expr2_->MakeDomainIterator(true)) {
956 CHECK(values_ !=
nullptr);
959 IntIntExprFunctionElement::~IntIntExprFunctionElement() {}
961 int64 IntIntExprFunctionElement::Min()
const {
966 int64 IntIntExprFunctionElement::Max()
const {
971 void IntIntExprFunctionElement::Range(
int64* lower_bound,
int64* upper_bound) {
977 #define UPDATE_ELEMENT_INDEX_BOUNDS(test) \
978 const int64 emin1 = expr1_->Min(); \
979 const int64 emax1 = expr1_->Max(); \
980 const int64 emin2 = expr2_->Min(); \
981 const int64 emax2 = expr2_->Max(); \
982 int64 nmin1 = emin1; \
983 bool found = false; \
984 while (nmin1 <= emax1 && !found) { \
985 for (int i = emin2; i <= emax2; ++i) { \
986 int64 value = ElementValue(nmin1, i); \
996 if (nmin1 > emax1) { \
999 int64 nmin2 = emin2; \
1001 while (nmin2 <= emax2 && !found) { \
1002 for (int i = emin1; i <= emax1; ++i) { \
1003 int64 value = ElementValue(i, nmin2); \
1013 if (nmin2 > emax2) { \
1016 int64 nmax1 = emax1; \
1018 while (nmax1 >= nmin1 && !found) { \
1019 for (int i = emin2; i <= emax2; ++i) { \
1020 int64 value = ElementValue(nmax1, i); \
1030 int64 nmax2 = emax2; \
1032 while (nmax2 >= nmin2 && !found) { \
1033 for (int i = emin1; i <= emax1; ++i) { \
1034 int64 value = ElementValue(i, nmax2); \
1044 expr1_->SetRange(nmin1, nmax1); \
1045 expr2_->SetRange(nmin2, nmax2);
1047 void IntIntExprFunctionElement::SetMin(
int64 lower_bound) {
1051 void IntIntExprFunctionElement::SetMax(
int64 upper_bound) {
1055 void IntIntExprFunctionElement::SetRange(
int64 lower_bound,
int64 upper_bound) {
1056 if (lower_bound > upper_bound) {
1062 #undef UPDATE_ELEMENT_INDEX_BOUNDS
1064 void IntIntExprFunctionElement::UpdateSupports()
const {
1065 if (initial_update_ || !expr1_->
Contains(min_support1_) ||
1067 !expr2_->
Contains(max_support2_)) {
1070 int64 min_value = ElementValue(emax1, emax2);
1071 int64 max_value = min_value;
1072 int min_support1 = emax1;
1073 int max_support1 = emax1;
1074 int min_support2 = emax2;
1075 int max_support2 = emax2;
1076 for (
const int64 index1 : InitAndGetValues(expr1_iterator_)) {
1077 for (
const int64 index2 : InitAndGetValues(expr2_iterator_)) {
1078 const int64 value = ElementValue(index1, index2);
1079 if (
value > max_value) {
1081 max_support1 = index1;
1082 max_support2 = index2;
1083 }
else if (
value < min_value) {
1085 min_support1 = index1;
1086 min_support2 = index2;
1090 Solver* s = solver();
1091 s->SaveAndSetValue(&min_, min_value);
1092 s->SaveAndSetValue(&min_support1_, min_support1);
1093 s->SaveAndSetValue(&min_support2_, min_support2);
1094 s->SaveAndSetValue(&max_, max_value);
1095 s->SaveAndSetValue(&max_support1_, max_support1);
1096 s->SaveAndSetValue(&max_support2_, max_support2);
1097 s->SaveAndSetValue(&initial_update_,
false);
1107 new IntIntExprFunctionElement(
this, std::move(values), index1, index2)));
1119 condition_(condition),
1139 if (condition_->
Max() == 0) {
1140 zero_->
SetRange(target_var_min, target_var_max);
1141 zero_->
Range(&new_min, &new_max);
1142 }
else if (condition_->
Min() == 1) {
1143 one_->
SetRange(target_var_min, target_var_max);
1144 one_->
Range(&new_min, &new_max);
1146 if (target_var_max < zero_->Min() || target_var_min > zero_->
Max()) {
1148 one_->
SetRange(target_var_min, target_var_max);
1149 one_->
Range(&new_min, &new_max);
1150 }
else if (target_var_max < one_->Min() || target_var_min > one_->
Max()) {
1152 zero_->
SetRange(target_var_min, target_var_max);
1153 zero_->
Range(&new_min, &new_max);
1159 zero_->
Range(&zl, &zu);
1160 one_->
Range(&ol, &ou);
1169 return absl::StrFormat(
"(%s ? %s : %s) == %s", condition_->
DebugString(),
1177 IntVar*
const condition_;
1189 class IntExprEvaluatorElementCt :
public CastConstraint {
1193 IntVar*
const index, IntVar*
const target_var);
1194 ~IntExprEvaluatorElementCt()
override {}
1196 void Post()
override;
1197 void InitialPropagate()
override;
1200 void Update(
int index);
1203 std::string DebugString()
const override;
1204 void Accept(ModelVisitor*
const visitor)
const override;
1207 IntVar*
const index_;
1211 const int64 range_start_;
1212 const int64 range_end_;
1217 IntExprEvaluatorElementCt::IntExprEvaluatorElementCt(
1219 int64 range_end, IntVar*
const index, IntVar*
const target_var)
1220 : CastConstraint(s, target_var),
1223 range_start_(range_start),
1224 range_end_(range_end),
1228 void IntExprEvaluatorElementCt::Post() {
1230 solver(),
this, &IntExprEvaluatorElementCt::Propagate,
"Propagate");
1231 for (
int i = range_start_; i < range_end_; ++i) {
1233 current_var->WhenRange(delayed_propagate_demon);
1235 solver(),
this, &IntExprEvaluatorElementCt::Update,
"Update", i);
1236 current_var->WhenRange(update_demon);
1238 index_->
WhenRange(delayed_propagate_demon);
1240 solver(),
this, &IntExprEvaluatorElementCt::UpdateExpr,
"UpdateExpr");
1243 solver(),
this, &IntExprEvaluatorElementCt::Propagate,
"UpdateVar");
1248 void IntExprEvaluatorElementCt::InitialPropagate() { Propagate(); }
1250 void IntExprEvaluatorElementCt::Propagate() {
1252 const int64 emax = std::min<int64>(range_end_ - 1, index_->
Max());
1260 for (; nmin <= emax; nmin++) {
1265 if (nmin_var->Min() <= vmax && nmin_var->Max() >= vmin)
break;
1268 for (; nmin <= nmax; nmax--) {
1273 if (nmax_var->Min() <= vmax && nmax_var->Max() >= vmin)
break;
1280 if (min_support_ == -1 || max_support_ == -1) {
1281 int min_support = -1;
1282 int max_support = -1;
1285 for (
int i = index_->
Min(); i <= index_->Max(); ++i) {
1287 const int64 vmin = var_i->Min();
1291 const int64 vmax = var_i->Max();
1296 solver()->SaveAndSetValue(&min_support_, min_support);
1297 solver()->SaveAndSetValue(&max_support_, max_support);
1302 void IntExprEvaluatorElementCt::Update(
int index) {
1303 if (
index == min_support_ ||
index == max_support_) {
1304 solver()->SaveAndSetValue(&min_support_, -1);
1305 solver()->SaveAndSetValue(&max_support_, -1);
1309 void IntExprEvaluatorElementCt::UpdateExpr() {
1311 solver()->SaveAndSetValue(&min_support_, -1);
1312 solver()->SaveAndSetValue(&max_support_, -1);
1320 for (
int64 i = range_start; i < range_end; ++i) {
1321 if (i != range_start) {
1324 out += absl::StrFormat(
"%d -> %s", i, evaluator(i)->DebugString());
1332 if (range_end - range_begin > 10) {
1333 out = absl::StrFormat(
1334 "IntToIntVar(%s, ...%s)",
1335 StringifyEvaluatorBare(evaluator, range_begin, range_begin + 5),
1336 StringifyEvaluatorBare(evaluator, range_end - 5, range_end));
1338 out = absl::StrFormat(
1340 StringifyEvaluatorBare(evaluator, range_begin, range_end));
1346 std::string IntExprEvaluatorElementCt::DebugString()
const {
1347 return StringifyInt64ToIntVar(
evaluator_, range_start_, range_end_);
1350 void IntExprEvaluatorElementCt::Accept(ModelVisitor*
const visitor)
const {
1352 visitor->VisitIntegerVariableEvaluatorArgument(
1365 class IntExprArrayElementCt :
public IntExprEvaluatorElementCt {
1367 IntExprArrayElementCt(Solver*
const s, std::vector<IntVar*> vars,
1368 IntVar*
const index, IntVar*
const target_var);
1370 std::string DebugString()
const override;
1371 void Accept(ModelVisitor*
const visitor)
const override;
1374 const std::vector<IntVar*>
vars_;
1377 IntExprArrayElementCt::IntExprArrayElementCt(Solver*
const s,
1378 std::vector<IntVar*> vars,
1379 IntVar*
const index,
1380 IntVar*
const target_var)
1381 : IntExprEvaluatorElementCt(
1384 vars_(std::move(vars)) {}
1386 std::string IntExprArrayElementCt::DebugString()
const {
1389 return absl::StrFormat(
1390 "IntExprArrayElement(var array of size %d, %s) == %s", size,
1393 return absl::StrFormat(
"IntExprArrayElement([%s], %s) == %s",
1399 void IntExprArrayElementCt::Accept(ModelVisitor*
const visitor)
const {
1413 class IntExprArrayElementCstCt :
public Constraint {
1415 IntExprArrayElementCstCt(Solver*
const s,
const std::vector<IntVar*>& vars,
1421 demons_(vars.size()) {}
1423 ~IntExprArrayElementCstCt()
override {}
1425 void Post()
override {
1426 for (
int i = 0; i <
vars_.size(); ++i) {
1428 solver(),
this, &IntExprArrayElementCstCt::Propagate,
"Propagate", i);
1429 vars_[i]->WhenDomain(demons_[i]);
1432 solver(),
this, &IntExprArrayElementCstCt::PropagateIndex,
1434 index_->WhenBound(index_demon);
1437 void InitialPropagate()
override {
1438 for (
int i = 0; i <
vars_.size(); ++i) {
1444 void Propagate(
int index) {
1445 if (!vars_[
index]->Contains(target_)) {
1446 index_->RemoveValue(
index);
1447 demons_[
index]->inhibit(solver());
1451 void PropagateIndex() {
1452 if (index_->Bound()) {
1453 vars_[index_->Min()]->SetValue(target_);
1457 std::string DebugString()
const override {
1458 return absl::StrFormat(
"IntExprArrayElement([%s], %s) == %d",
1460 index_->DebugString(), target_);
1463 void Accept(ModelVisitor*
const visitor)
const override {
1474 const std::vector<IntVar*>
vars_;
1475 IntVar*
const index_;
1476 const int64 target_;
1477 std::vector<Demon*> demons_;
1482 class IntExprIndexOfCt :
public Constraint {
1484 IntExprIndexOfCt(Solver*
const s,
const std::vector<IntVar*>& vars,
1490 demons_(
vars_.size()),
1491 index_iterator_(
index->MakeHoleIterator(true)) {}
1493 ~IntExprIndexOfCt()
override {}
1495 void Post()
override {
1496 for (
int i = 0; i <
vars_.size(); ++i) {
1498 solver(),
this, &IntExprIndexOfCt::Propagate,
"Propagate", i);
1499 vars_[i]->WhenDomain(demons_[i]);
1502 solver(),
this, &IntExprIndexOfCt::PropagateIndex,
"PropagateIndex");
1503 index_->WhenDomain(index_demon);
1506 void InitialPropagate()
override {
1507 for (
int i = 0; i <
vars_.size(); ++i) {
1508 if (!index_->Contains(i)) {
1509 vars_[i]->RemoveValue(target_);
1510 }
else if (!vars_[i]->Contains(target_)) {
1511 index_->RemoveValue(i);
1512 demons_[i]->inhibit(solver());
1513 }
else if (vars_[i]->Bound()) {
1514 index_->SetValue(i);
1515 demons_[i]->inhibit(solver());
1520 void Propagate(
int index) {
1521 if (!vars_[
index]->Contains(target_)) {
1522 index_->RemoveValue(
index);
1523 demons_[
index]->inhibit(solver());
1524 }
else if (vars_[
index]->Bound()) {
1525 index_->SetValue(
index);
1529 void PropagateIndex() {
1530 const int64 oldmax = index_->OldMax();
1531 const int64 vmin = index_->Min();
1532 const int64 vmax = index_->Max();
1535 demons_[
value]->inhibit(solver());
1537 for (
const int64 value : InitAndGetValues(index_iterator_)) {
1539 demons_[
value]->inhibit(solver());
1543 demons_[
value]->inhibit(solver());
1545 if (index_->Bound()) {
1546 vars_[index_->Min()]->SetValue(target_);
1550 std::string DebugString()
const override {
1551 return absl::StrFormat(
"IntExprIndexOf([%s], %s) == %d",
1553 index_->DebugString(), target_);
1556 void Accept(ModelVisitor*
const visitor)
const override {
1567 const std::vector<IntVar*>
vars_;
1568 IntVar*
const index_;
1569 const int64 target_;
1570 std::vector<Demon*> demons_;
1571 IntVarIterator*
const index_iterator_;
1576 Constraint* MakeElementEqualityFunc(Solver*
const solver,
1577 const std::vector<int64>& vals,
1578 IntVar*
const index, IntVar*
const target) {
1579 if (
index->Bound()) {
1581 if (val < 0 || val >= vals.size()) {
1582 return solver->MakeFalseConstraint();
1584 return solver->MakeEquality(target, vals[val]);
1588 return solver->MakeEquality(target, solver->MakeSum(
index, vals[0]));
1590 return solver->RevAlloc(
1591 new IntElementConstraint(solver, vals,
index, target));
1600 IntVar*
const target_var) {
1602 new IfThenElseCt(
this, condition, then_expr, else_expr, target_var));
1607 if (
index->Bound()) {
1608 return vars[
index->Min()];
1610 const int size = vars.size();
1612 std::vector<int64> values(size);
1613 for (
int i = 0; i < size; ++i) {
1614 values[i] = vars[i]->Value();
1619 index->Min() >= 0 &&
index->Max() < vars.size()) {
1624 const std::string
name = absl::StrFormat(
1634 std::unique_ptr<IntVarIterator> iterator(
index->MakeDomainIterator(
false));
1636 if (index_value >= 0 && index_value < size) {
1637 emin =
std::min(emin, vars[index_value]->Min());
1638 emax =
std::max(emax, vars[index_value]->Max());
1641 const std::string vname =
1642 size > 10 ? absl::StrFormat(
"ElementVar(var array of size %d, %s)", size,
1643 index->DebugString())
1644 : absl::StrFormat(
"ElementVar([%s], %s)",
1648 RevAlloc(
new IntExprArrayElementCt(
this, vars,
index, element_var)));
1654 const std::string index_name =
1656 const std::string vname = absl::StrFormat(
1657 "ElementVar(%s, %s)",
1658 StringifyInt64ToIntVar(vars, range_start, range_end), index_name);
1660 IntExprEvaluatorElementCt* evaluation_ct =
new IntExprEvaluatorElementCt(
1661 this, std::move(vars), range_start, range_end, argument, element_var);
1663 evaluation_ct->Propagate();
1670 return MakeElementEqualityFunc(
this, vals,
index, target);
1683 std::vector<int64> values(vars.size());
1684 for (
int i = 0; i < vars.size(); ++i) {
1685 values[i] = vars[i]->Value();
1689 if (
index->Bound()) {
1691 if (val < 0 || val >= vars.size()) {
1697 if (target->
Bound()) {
1699 new IntExprArrayElementCstCt(
this, vars,
index, target->
Min()));
1701 return RevAlloc(
new IntExprArrayElementCt(
this, vars,
index, target));
1709 std::vector<int> valid_indices;
1710 for (
int i = 0; i < vars.size(); ++i) {
1711 if (vars[i]->
Value() == target) {
1712 valid_indices.push_back(i);
1717 if (
index->Bound()) {
1719 if (pos >= 0 && pos < vars.size()) {
1726 return RevAlloc(
new IntExprArrayElementCstCt(
this, vars,
index, target));
1732 if (
index->Bound()) {
1734 if (pos >= 0 && pos < vars.size()) {
1741 return RevAlloc(
new IntExprIndexOfCt(
this, vars,
index, target));
1747 IntExpr*
const cache = model_cache_->FindVarArrayConstantExpression(
1749 if (cache !=
nullptr) {
1750 return cache->
Var();
1752 const std::string
name =
1756 model_cache_->InsertVarArrayConstantExpression(
const std::vector< IntVar * > vars_
#define DCHECK_LE(val1, val2)
#define CHECK_EQ(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
This is the base class for all expressions that are not variables.
Cast constraints are special channeling constraints designed to keep a variable in sync with an expre...
IntVar *const target_var_
A constraint is the main modeling object.
A Demon is the base element of a propagation queue.
void Post() override
This method is called when the constraint is processed by the solver.
void InitialPropagate() override
This method performs the initial propagation of the constraint.
IfThenElseCt(Solver *const solver, IntVar *const condition, IntExpr *const one, IntExpr *const zero, IntVar *const target)
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
std::string DebugString() const override
Utility class to encapsulate an IntVarIterator and use it in a range-based loop.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual IntVar * Var()=0
Creates a variable from the expression.
virtual void SetRange(int64 l, int64 u)
This method sets both the min and the max of the expression.
virtual void SetValue(int64 v)
This method sets the value of the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual void Range(int64 *l, int64 *u)
By default calls Min() and Max(), but can be redefined when Min and Max code can be factorized.
virtual int64 Max() const =0
virtual int64 Min() const =0
virtual void WhenRange(Demon *d)=0
Attach a demon that will watch the min or the max of the expression.
The class IntVar is a subset of IntExpr.
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
virtual bool Contains(int64 v) const =0
This method returns whether the value 'v' is in the domain of the variable.
@ VAR_ARRAY_CONSTANT_INDEX
static const char kIndex2Argument[]
static const char kMinArgument[]
static const char kElementEqual[]
static const char kTargetArgument[]
static const char kMaxArgument[]
static const char kEvaluatorArgument[]
static const char kVarsArgument[]
static const char kIndexOf[]
static const char kElement[]
static const char kValuesArgument[]
static const char kIndexArgument[]
virtual std::string name() const
Object naming.
std::string DebugString() const override
IntExpr * MakeElement(const std::vector< int64 > &values, IntVar *const index)
values[index]
Constraint * MakeMemberCt(IntExpr *const expr, const std::vector< int64 > &values)
expr in set.
IntExpr * RegisterIntExpr(IntExpr *const expr)
Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
Constraint * MakeFalseConstraint()
This constraint always fails.
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
void AddConstraint(Constraint *const c)
Adds the constraint 'c' to the model.
IntExpr * MakeOpposite(IntExpr *const expr)
-expr
Constraint * MakeIfThenElseCt(IntVar *const condition, IntExpr *const then_expr, IntExpr *const else_expr, IntVar *const target_var)
Special cases with arrays of size two.
Demon * MakeConstraintInitialPropagateCallback(Constraint *const ct)
This method is a specialized case of the MakeConstraintDemon method to call the InitiatePropagate of ...
std::function< int64(int64)> IndexEvaluator1
Callback typedefs.
T * RevAlloc(T *object)
Registers the given object as being reversible.
std::function< int64(int64, int64)> IndexEvaluator2
IntExpr * MakeSum(IntExpr *const left, IntExpr *const right)
left + right.
IntExpr * MakeIndexExpression(const std::vector< IntVar * > &vars, int64 value)
Returns the expression expr such that vars[expr] == value.
IntVar * MakeIntVar(int64 min, int64 max, const std::string &name)
MakeIntVar will create the best range based int var for the bounds given.
Constraint * MakeIndexOfConstraint(const std::vector< IntVar * > &vars, IntVar *const index, int64 target)
This constraint is a special case of the element constraint with an array of integer variables,...
std::function< IntVar *(int64)> Int64ToIntVar
Constraint * MakeElementEquality(const std::vector< int64 > &vals, IntVar *const index, IntVar *const target)
IntExpr * MakeMonotonicElement(IndexEvaluator1 values, bool increasing, IntVar *const index)
Function based element.
std::vector< int64 > to_remove_
#define UPDATE_ELEMENT_INDEX_BOUNDS(test)
ABSL_FLAG(bool, cp_disable_element_cache, true, "If true, caching for IntElement is disabled.")
#define UPDATE_BASE_ELEMENT_INDEX_BOUNDS(test)
#define UPDATE_RMQ_BASE_ELEMENT_INDEX_BOUNDS(test)
static const int64 kint64max
static const int64 kint64min
std::function< int64(const Model &)> Value(IntegerVariable v)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool IsArrayConstant(const std::vector< T > &values, const T &value)
bool IsIncreasing(const std::vector< T > &values)
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
bool IsArrayBoolean(const std::vector< T > &values)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
bool IsIncreasingContiguous(const std::vector< T > &values)
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
void LinkVarExpr(Solver *const s, IntExpr *const expr, IntVar *const var)
bool AreAllBound(const std::vector< IntVar * > &vars)
std::string JoinNamePtr(const std::vector< T > &v, const std::string &separator)
IntervalVar *const target_var_
std::function< int64(int64, int64)> evaluator_