17#include "absl/strings/str_cat.h"
18#include "absl/strings/str_format.h"
27#pragma warning(disable : 4351 4355 4804 4805)
43void LinkVarExpr(Solver*
const s, IntExpr*
const expr, IntVar*
const var);
51enum IntervalField { START, DURATION, END };
53IntervalVar* NullInterval() {
return nullptr; }
56class MirrorIntervalVar :
public IntervalVar {
58 MirrorIntervalVar(Solver*
const s, IntervalVar*
const t)
59 : IntervalVar(s,
"Mirror<" + t->
name() +
">"), t_(t) {}
60 ~MirrorIntervalVar()
override {}
64 int64 StartMin()
const override {
return -t_->EndMax(); }
65 int64 StartMax()
const override {
return -t_->EndMin(); }
66 void SetStartMin(
int64 m)
override { t_->SetEndMax(-m); }
67 void SetStartMax(
int64 m)
override { t_->SetEndMin(-m); }
68 void SetStartRange(
int64 mi,
int64 ma)
override { t_->SetEndRange(-ma, -mi); }
69 int64 OldStartMin()
const override {
return -t_->OldEndMax(); }
70 int64 OldStartMax()
const override {
return -t_->OldEndMin(); }
71 void WhenStartRange(Demon*
const d)
override { t_->WhenEndRange(d); }
72 void WhenStartBound(Demon*
const d)
override { t_->WhenEndBound(d); }
75 int64 DurationMin()
const override {
return t_->DurationMin(); }
76 int64 DurationMax()
const override {
return t_->DurationMax(); }
77 void SetDurationMin(
int64 m)
override { t_->SetDurationMin(m); }
78 void SetDurationMax(
int64 m)
override { t_->SetDurationMax(m); }
79 void SetDurationRange(
int64 mi,
int64 ma)
override {
80 t_->SetDurationRange(mi, ma);
82 int64 OldDurationMin()
const override {
return t_->OldDurationMin(); }
83 int64 OldDurationMax()
const override {
return t_->OldDurationMax(); }
84 void WhenDurationRange(Demon*
const d)
override { t_->WhenDurationRange(d); }
85 void WhenDurationBound(Demon*
const d)
override { t_->WhenDurationBound(d); }
88 int64 EndMin()
const override {
return -t_->StartMax(); }
89 int64 EndMax()
const override {
return -t_->StartMin(); }
90 void SetEndMin(
int64 m)
override { t_->SetStartMax(-m); }
91 void SetEndMax(
int64 m)
override { t_->SetStartMin(-m); }
92 void SetEndRange(
int64 mi,
int64 ma)
override { t_->SetStartRange(-ma, -mi); }
93 int64 OldEndMin()
const override {
return -t_->OldStartMax(); }
94 int64 OldEndMax()
const override {
return -t_->OldStartMin(); }
95 void WhenEndRange(Demon*
const d)
override { t_->WhenStartRange(d); }
96 void WhenEndBound(Demon*
const d)
override { t_->WhenStartBound(d); }
100 bool MustBePerformed()
const override {
return t_->MustBePerformed(); }
101 bool MayBePerformed()
const override {
return t_->MayBePerformed(); }
102 void SetPerformed(
bool val)
override { t_->SetPerformed(val); }
103 bool WasPerformedBound()
const override {
return t_->WasPerformedBound(); }
104 void WhenPerformedBound(Demon*
const d)
override {
105 t_->WhenPerformedBound(d);
108 void Accept(ModelVisitor*
const visitor)
const override {
112 std::string DebugString()
const override {
113 return absl::StrFormat(
"MirrorInterval(%s)", t_->DebugString());
116 IntExpr* StartExpr()
override {
117 return solver()->MakeOpposite(t_->EndExpr());
119 IntExpr* DurationExpr()
override {
return t_->DurationExpr(); }
120 IntExpr* EndExpr()
override {
121 return solver()->MakeOpposite(t_->StartExpr());
123 IntExpr* PerformedExpr()
override {
return t_->PerformedExpr(); }
127 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
128 return solver()->MakeOpposite(t_->SafeEndExpr(-unperformed_value));
130 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
131 return t_->SafeDurationExpr(unperformed_value);
133 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
134 return solver()->MakeOpposite(t_->SafeStartExpr(-unperformed_value));
138 IntervalVar*
const t_;
158class AlwaysPerformedIntervalVarWrapper :
public IntervalVar {
160 explicit AlwaysPerformedIntervalVarWrapper(IntervalVar*
const t)
161 : IntervalVar(t->solver(),
162 absl::StrFormat(
"AlwaysPerformed<%s>", t->
name())),
164 start_expr_(nullptr),
165 duration_expr_(nullptr),
166 end_expr_(nullptr) {}
168 ~AlwaysPerformedIntervalVarWrapper()
override {}
169 int64 StartMin()
const override {
170 return MayUnderlyingBePerformed() ? t_->StartMin() : kMinValidValue;
172 int64 StartMax()
const override {
173 return MayUnderlyingBePerformed() ? t_->StartMax() : kMaxValidValue;
175 void SetStartMin(
int64 m)
override { t_->SetStartMin(m); }
176 void SetStartMax(
int64 m)
override { t_->SetStartMax(m); }
177 void SetStartRange(
int64 mi,
int64 ma)
override { t_->SetStartRange(mi, ma); }
178 int64 OldStartMin()
const override {
179 return MayUnderlyingBePerformed() ? t_->OldStartMin() : kMinValidValue;
181 int64 OldStartMax()
const override {
182 return MayUnderlyingBePerformed() ? t_->OldStartMax() : kMaxValidValue;
184 void WhenStartRange(Demon*
const d)
override { t_->WhenStartRange(d); }
185 void WhenStartBound(Demon*
const d)
override { t_->WhenStartBound(d); }
186 int64 DurationMin()
const override {
187 return MayUnderlyingBePerformed() ? t_->DurationMin() : 0LL;
189 int64 DurationMax()
const override {
190 return MayUnderlyingBePerformed() ? t_->DurationMax() : 0LL;
192 void SetDurationMin(
int64 m)
override { t_->SetDurationMin(m); }
193 void SetDurationMax(
int64 m)
override { t_->SetDurationMax(m); }
194 void SetDurationRange(
int64 mi,
int64 ma)
override {
195 t_->SetDurationRange(mi, ma);
197 int64 OldDurationMin()
const override {
198 return MayUnderlyingBePerformed() ? t_->OldDurationMin() : 0LL;
200 int64 OldDurationMax()
const override {
201 return MayUnderlyingBePerformed() ? t_->OldDurationMax() : 0LL;
203 void WhenDurationRange(Demon*
const d)
override { t_->WhenDurationRange(d); }
204 void WhenDurationBound(Demon*
const d)
override { t_->WhenDurationBound(d); }
205 int64 EndMin()
const override {
206 return MayUnderlyingBePerformed() ? t_->EndMin() : kMinValidValue;
208 int64 EndMax()
const override {
209 return MayUnderlyingBePerformed() ? t_->EndMax() : kMaxValidValue;
211 void SetEndMin(
int64 m)
override { t_->SetEndMin(m); }
212 void SetEndMax(
int64 m)
override { t_->SetEndMax(m); }
213 void SetEndRange(
int64 mi,
int64 ma)
override { t_->SetEndRange(mi, ma); }
214 int64 OldEndMin()
const override {
215 return MayUnderlyingBePerformed() ? t_->OldEndMin() : kMinValidValue;
217 int64 OldEndMax()
const override {
218 return MayUnderlyingBePerformed() ? t_->OldEndMax() : kMaxValidValue;
220 void WhenEndRange(Demon*
const d)
override { t_->WhenEndRange(d); }
221 void WhenEndBound(Demon*
const d)
override { t_->WhenEndBound(d); }
222 bool MustBePerformed()
const override {
return true; }
223 bool MayBePerformed()
const override {
return true; }
224 void SetPerformed(
bool val)
override {
233 bool WasPerformedBound()
const override {
return true; }
234 void WhenPerformedBound(Demon*
const d)
override {
235 t_->WhenPerformedBound(d);
237 IntExpr* StartExpr()
override {
238 if (start_expr_ ==
nullptr) {
239 solver()->SaveValue(
reinterpret_cast<void**
>(&start_expr_));
244 IntExpr* DurationExpr()
override {
245 if (duration_expr_ ==
nullptr) {
246 solver()->SaveValue(
reinterpret_cast<void**
>(&duration_expr_));
249 return duration_expr_;
251 IntExpr* EndExpr()
override {
252 if (end_expr_ ==
nullptr) {
253 solver()->SaveValue(
reinterpret_cast<void**
>(&end_expr_));
258 IntExpr* PerformedExpr()
override {
return solver()->MakeIntConst(1); }
259 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
262 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
263 return DurationExpr();
265 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
return EndExpr(); }
268 IntervalVar*
const underlying()
const {
return t_; }
269 bool MayUnderlyingBePerformed()
const {
270 return underlying()->MayBePerformed();
274 IntervalVar*
const t_;
275 IntExpr* start_expr_;
276 IntExpr* duration_expr_;
294class IntervalVarRelaxedMax :
public AlwaysPerformedIntervalVarWrapper {
296 explicit IntervalVarRelaxedMax(IntervalVar*
const t)
297 : AlwaysPerformedIntervalVarWrapper(t) {}
298 ~IntervalVarRelaxedMax()
override {}
299 int64 StartMax()
const override {
301 return underlying()->MustBePerformed() ? underlying()->StartMax()
302 : (kMaxValidValue - DurationMin());
304 void SetStartMax(
int64 m)
override {
306 <<
"Calling SetStartMax on a IntervalVarRelaxedMax is not supported, "
307 <<
"as it seems there is no legitimate use case.";
309 int64 EndMax()
const override {
310 return underlying()->MustBePerformed() ? underlying()->EndMax()
313 void SetEndMax(
int64 m)
override {
315 <<
"Calling SetEndMax on a IntervalVarRelaxedMax is not supported, "
316 <<
"as it seems there is no legitimate use case.";
319 void Accept(ModelVisitor*
const visitor)
const override {
324 std::string DebugString()
const override {
325 return absl::StrFormat(
"IntervalVarRelaxedMax(%s)",
326 underlying()->DebugString());
344class IntervalVarRelaxedMin :
public AlwaysPerformedIntervalVarWrapper {
346 explicit IntervalVarRelaxedMin(IntervalVar*
const t)
347 : AlwaysPerformedIntervalVarWrapper(t) {}
348 ~IntervalVarRelaxedMin()
override {}
349 int64 StartMin()
const override {
350 return underlying()->MustBePerformed() ? underlying()->StartMin()
353 void SetStartMin(
int64 m)
override {
355 <<
"Calling SetStartMin on a IntervalVarRelaxedMin is not supported, "
356 <<
"as it seems there is no legitimate use case.";
358 int64 EndMin()
const override {
360 return underlying()->MustBePerformed() ? underlying()->EndMin()
361 : (kMinValidValue + DurationMin());
363 void SetEndMin(
int64 m)
override {
365 <<
"Calling SetEndMin on a IntervalVarRelaxedMin is not supported, "
366 <<
"as it seems there is no legitimate use case.";
369 void Accept(ModelVisitor*
const visitor)
const override {
374 std::string DebugString()
const override {
375 return absl::StrFormat(
"IntervalVarRelaxedMin(%s)",
376 underlying()->DebugString());
382class BaseIntervalVar :
public IntervalVar {
384 class Handler :
public Demon {
386 explicit Handler(BaseIntervalVar*
const var) : var_(
var) {}
387 ~Handler()
override {}
388 void Run(Solver*
const s)
override { var_->Process(); }
392 std::string DebugString()
const override {
393 return absl::StrFormat(
"Handler(%s)", var_->DebugString());
397 BaseIntervalVar*
const var_;
400 BaseIntervalVar(Solver*
const s,
const std::string&
name)
401 : IntervalVar(s,
name),
404 cleaner_([this](Solver* s) { CleanInProcess(); }) {}
406 ~BaseIntervalVar()
override {}
408 virtual void Process() = 0;
410 virtual void Push() = 0;
414 std::string BaseName()
const override {
return "IntervalVar"; }
424class RangeVar :
public IntExpr {
426 RangeVar(Solver*
const s, BaseIntervalVar*
var,
int64 mi,
int64 ma)
435 cast_var_(
nullptr) {}
437 ~RangeVar()
override {}
439 bool Bound()
const override {
return min_.Value() == max_.Value(); }
441 int64 Min()
const override {
return min_.Value(); }
443 int64 Max()
const override {
return max_.Value(); }
445 void SetMin(
int64 m)
override {
447 if (m <= min_.Value()) {
451 if (m > max_.Value()) {
452 var_->SetPerformed(
false);
455 if (var_->InProcess()) {
457 if (m > postponed_max_) {
458 var_->SetPerformed(
false);
460 if (m > postponed_min_) {
465 SyncPreviousBounds();
466 min_.SetValue(solver(), m);
471 int64 OldMin()
const {
472 DCHECK(var_->InProcess());
473 return previous_min_;
476 void SetMax(
int64 m)
override {
477 if (m >= max_.Value()) {
480 if (m < min_.Value()) {
481 var_->SetPerformed(
false);
484 if (var_->InProcess()) {
486 if (m < postponed_min_) {
487 var_->SetPerformed(
false);
489 if (m < postponed_max_) {
494 SyncPreviousBounds();
495 max_.SetValue(solver(), m);
500 int64 OldMax()
const {
return previous_min_; }
503 if (mi <= min_.Value() && ma >= max_.Value()) {
507 if (mi > max_.Value() || ma < min_.Value() || mi > ma) {
508 var_->SetPerformed(
false);
510 if (var_->InProcess()) {
511 if (mi > postponed_max_ || ma < postponed_min_) {
512 var_->SetPerformed(
false);
514 if (mi > postponed_min_) {
517 if (ma < postponed_max_) {
522 SyncPreviousBounds();
523 if (mi > min_.Value()) {
524 min_.SetValue(solver(), mi);
526 if (ma < max_.Value()) {
527 max_.SetValue(solver(), ma);
533 void WhenRange(Demon*
const demon)
override {
536 delayed_range_demons_.PushIfNotTop(solver(),
539 range_demons_.PushIfNotTop(solver(), solver()->
RegisterDemon(demon));
544 virtual void WhenBound(Demon*
const demon) {
547 delayed_bound_demons_.PushIfNotTop(solver(),
550 bound_demons_.PushIfNotTop(solver(), solver()->
RegisterDemon(demon));
555 void UpdatePostponedBounds() {
556 postponed_min_ = min_.Value();
557 postponed_max_ = max_.Value();
560 void ProcessDemons() {
562 ExecuteAll(bound_demons_);
563 EnqueueAll(delayed_bound_demons_);
565 if (min_.Value() != previous_min_ || max_.Value() != previous_max_) {
566 ExecuteAll(range_demons_);
567 EnqueueAll(delayed_range_demons_);
571 void UpdatePreviousBounds() {
572 previous_min_ = min_.Value();
573 previous_max_ = max_.Value();
577 void ApplyPostponedBounds(IntervalField which) {
578 if (min_.Value() < postponed_min_ || max_.Value() > postponed_max_) {
581 var_->SetStartRange(
std::max(postponed_min_, min_.Value()),
582 std::min(postponed_max_, max_.Value()));
585 var_->SetDurationRange(
std::max(postponed_min_, min_.Value()),
586 std::min(postponed_max_, max_.Value()));
589 var_->SetEndRange(
std::max(postponed_min_, min_.Value()),
590 std::min(postponed_max_, max_.Value()));
596 IntVar* Var()
override {
597 if (cast_var_ ==
nullptr) {
598 solver()->SaveValue(
reinterpret_cast<void**
>(&cast_var_));
599 cast_var_ = solver()->MakeIntVar(min_.Value(), max_.Value());
605 std::string DebugString()
const override {
606 std::string out = absl::StrCat(min_.Value());
608 absl::StrAppendFormat(&out,
" .. %d", max_.Value());
620 void SyncPreviousBounds() {
621 if (previous_min_ > min_.Value()) {
622 previous_min_ = min_.Value();
624 if (previous_max_ < max_.Value()) {
625 previous_max_ = max_.Value();
630 NumericalRev<int64> min_;
631 NumericalRev<int64> max_;
632 BaseIntervalVar*
const var_;
635 int64 postponed_min_;
636 int64 postponed_max_;
642 SimpleRevFIFO<Demon*> bound_demons_;
643 SimpleRevFIFO<Demon*> delayed_bound_demons_;
645 SimpleRevFIFO<Demon*> range_demons_;
646 SimpleRevFIFO<Demon*> delayed_range_demons_;
652class PerformedVar :
public BooleanVar {
655 PerformedVar(Solver*
const s, BaseIntervalVar*
const var,
bool optional)
658 previous_value_(optional ? kUnboundBooleanVarValue : 1),
659 postponed_value_(optional ? kUnboundBooleanVarValue : 1) {
665 PerformedVar(Solver*
const s, BaseIntervalVar*
var)
666 : BooleanVar(s,
""), var_(
var), previous_value_(0), postponed_value_(0) {
670 ~PerformedVar()
override {}
672 void SetValue(
int64 v)
override {
673 if ((v & 0xfffffffffffffffe) != 0 ||
674 (value_ != kUnboundBooleanVarValue && v != value_)) {
677 if (var_->InProcess()) {
678 if (postponed_value_ != kUnboundBooleanVarValue &&
679 v != postponed_value_) {
682 postponed_value_ = v;
684 }
else if (value_ == kUnboundBooleanVarValue) {
685 previous_value_ = kUnboundBooleanVarValue;
687 value_ =
static_cast<int>(v);
692 int64 OldMin()
const override {
return previous_value_ == 1; }
694 int64 OldMax()
const override {
return previous_value_ != 0; }
696 void RestoreValue()
override {
697 previous_value_ = kUnboundBooleanVarValue;
698 value_ = kUnboundBooleanVarValue;
699 postponed_value_ = kUnboundBooleanVarValue;
703 if (previous_value_ != value_) {
704 ExecuteAll(bound_demons_);
705 EnqueueAll(delayed_bound_demons_);
709 void UpdatePostponedValue() { postponed_value_ = value_; }
711 void UpdatePreviousValueAndApplyPostponedValue() {
712 previous_value_ = value_;
713 if (value_ != postponed_value_) {
714 DCHECK_NE(kUnboundBooleanVarValue, postponed_value_);
715 SetValue(postponed_value_);
719 std::string DebugString()
const override {
731 BaseIntervalVar*
const var_;
733 int postponed_value_;
738class FixedDurationIntervalVar :
public BaseIntervalVar {
741 int64 duration,
bool optional,
742 const std::string&
name);
744 FixedDurationIntervalVar(Solver*
const s,
const std::string&
name);
745 ~FixedDurationIntervalVar()
override {}
747 int64 StartMin()
const override;
748 int64 StartMax()
const override;
749 void SetStartMin(
int64 m)
override;
750 void SetStartMax(
int64 m)
override;
751 void SetStartRange(
int64 mi,
int64 ma)
override;
752 int64 OldStartMin()
const override {
return start_.OldMin(); }
753 int64 OldStartMax()
const override {
return start_.OldMax(); }
754 void WhenStartRange(Demon*
const d)
override {
755 if (performed_.Max() == 1) {
759 void WhenStartBound(Demon*
const d)
override {
760 if (performed_.Max() == 1) {
765 int64 DurationMin()
const override;
766 int64 DurationMax()
const override;
767 void SetDurationMin(
int64 m)
override;
768 void SetDurationMax(
int64 m)
override;
769 void SetDurationRange(
int64 mi,
int64 ma)
override;
770 int64 OldDurationMin()
const override {
return duration_; }
771 int64 OldDurationMax()
const override {
return duration_; }
772 void WhenDurationRange(Demon*
const d)
override {}
773 void WhenDurationBound(Demon*
const d)
override {}
775 int64 EndMin()
const override;
776 int64 EndMax()
const override;
777 void SetEndMin(
int64 m)
override;
778 void SetEndMax(
int64 m)
override;
779 void SetEndRange(
int64 mi,
int64 ma)
override;
780 int64 OldEndMin()
const override {
return CapAdd(OldStartMin(), duration_); }
781 int64 OldEndMax()
const override {
return CapAdd(OldStartMax(), duration_); }
782 void WhenEndRange(Demon*
const d)
override { WhenStartRange(d); }
783 void WhenEndBound(Demon*
const d)
override { WhenStartBound(d); }
785 bool MustBePerformed()
const override;
786 bool MayBePerformed()
const override;
787 void SetPerformed(
bool val)
override;
788 bool WasPerformedBound()
const override {
789 return performed_.OldMin() == performed_.OldMax();
791 void WhenPerformedBound(Demon*
const d)
override { performed_.WhenBound(d); }
792 void Process()
override;
793 std::string DebugString()
const override;
795 void Accept(ModelVisitor*
const visitor)
const override {
796 visitor->VisitIntervalVariable(
this,
"", 0, NullInterval());
799 IntExpr* StartExpr()
override {
return &start_; }
800 IntExpr* DurationExpr()
override {
return solver()->MakeIntConst(duration_); }
801 IntExpr* EndExpr()
override {
802 return solver()->MakeSum(StartExpr(), duration_);
804 IntExpr* PerformedExpr()
override {
return &performed_; }
805 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
808 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
811 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
815 void Push()
override;
820 PerformedVar performed_;
823FixedDurationIntervalVar::FixedDurationIntervalVar(
825 bool optional,
const std::string&
name)
826 : BaseIntervalVar(s,
name),
829 performed_(s, this, optional) {}
831FixedDurationIntervalVar::FixedDurationIntervalVar(Solver*
const s,
832 const std::string&
name)
833 : BaseIntervalVar(s,
name),
834 start_(s, this, 0, 0),
836 performed_(s, this) {}
838void FixedDurationIntervalVar::Process() {
841 start_.UpdatePostponedBounds();
842 performed_.UpdatePostponedValue();
844 if (performed_.Max() == 1) {
845 start_.ProcessDemons();
847 performed_.Process();
848 reset_action_on_fail();
850 start_.UpdatePreviousBounds();
851 start_.ApplyPostponedBounds(START);
852 performed_.UpdatePreviousValueAndApplyPostponedValue();
855int64 FixedDurationIntervalVar::StartMin()
const {
860int64 FixedDurationIntervalVar::StartMax()
const {
865void FixedDurationIntervalVar::SetStartMin(
int64 m) {
866 if (performed_.Max() == 1) {
871void FixedDurationIntervalVar::SetStartMax(
int64 m) {
872 if (performed_.Max() == 1) {
877void FixedDurationIntervalVar::SetStartRange(
int64 mi,
int64 ma) {
878 if (performed_.Max() == 1) {
879 start_.SetRange(mi, ma);
883int64 FixedDurationIntervalVar::DurationMin()
const {
888int64 FixedDurationIntervalVar::DurationMax()
const {
893void FixedDurationIntervalVar::SetDurationMin(
int64 m) {
899void FixedDurationIntervalVar::SetDurationMax(
int64 m) {
905void FixedDurationIntervalVar::SetDurationRange(
int64 mi,
int64 ma) {
906 if (mi > duration_ || ma < duration_ || mi > ma) {
911int64 FixedDurationIntervalVar::EndMin()
const {
913 return start_.Min() + duration_;
916int64 FixedDurationIntervalVar::EndMax()
const {
918 return CapAdd(start_.Max(), duration_);
921void FixedDurationIntervalVar::SetEndMin(
int64 m) {
922 SetStartMin(
CapSub(m, duration_));
925void FixedDurationIntervalVar::SetEndMax(
int64 m) {
926 SetStartMax(
CapSub(m, duration_));
929void FixedDurationIntervalVar::SetEndRange(
int64 mi,
int64 ma) {
930 SetStartRange(
CapSub(mi, duration_),
CapSub(ma, duration_));
933bool FixedDurationIntervalVar::MustBePerformed()
const {
934 return (performed_.Min() == 1);
937bool FixedDurationIntervalVar::MayBePerformed()
const {
938 return (performed_.Max() == 1);
941void FixedDurationIntervalVar::SetPerformed(
bool val) {
942 performed_.SetValue(val);
945void FixedDurationIntervalVar::Push() {
951std::string FixedDurationIntervalVar::DebugString()
const {
952 const std::string& var_name =
name();
953 if (performed_.Max() == 0) {
954 if (!var_name.empty()) {
955 return absl::StrFormat(
"%s(performed = false)", var_name);
957 return "IntervalVar(performed = false)";
961 if (!var_name.empty()) {
962 out = var_name +
"(start = ";
964 out =
"IntervalVar(start = ";
966 absl::StrAppendFormat(&out,
"%s, duration = %d, performed = %s)",
967 start_.DebugString(), duration_,
968 performed_.DebugString());
975class FixedDurationPerformedIntervalVar :
public BaseIntervalVar {
977 FixedDurationPerformedIntervalVar(Solver*
const s,
int64 start_min,
979 const std::string&
name);
981 FixedDurationPerformedIntervalVar(Solver*
const s,
const std::string&
name);
982 ~FixedDurationPerformedIntervalVar()
override {}
984 int64 StartMin()
const override;
985 int64 StartMax()
const override;
986 void SetStartMin(
int64 m)
override;
987 void SetStartMax(
int64 m)
override;
988 void SetStartRange(
int64 mi,
int64 ma)
override;
989 int64 OldStartMin()
const override {
return start_.OldMin(); }
990 int64 OldStartMax()
const override {
return start_.OldMax(); }
991 void WhenStartRange(Demon*
const d)
override { start_.WhenRange(d); }
992 void WhenStartBound(Demon*
const d)
override { start_.WhenBound(d); }
994 int64 DurationMin()
const override;
995 int64 DurationMax()
const override;
996 void SetDurationMin(
int64 m)
override;
997 void SetDurationMax(
int64 m)
override;
998 void SetDurationRange(
int64 mi,
int64 ma)
override;
999 int64 OldDurationMin()
const override {
return duration_; }
1000 int64 OldDurationMax()
const override {
return duration_; }
1001 void WhenDurationRange(Demon*
const d)
override {}
1002 void WhenDurationBound(Demon*
const d)
override {}
1004 int64 EndMin()
const override;
1005 int64 EndMax()
const override;
1006 void SetEndMin(
int64 m)
override;
1007 void SetEndMax(
int64 m)
override;
1008 void SetEndRange(
int64 mi,
int64 ma)
override;
1009 int64 OldEndMin()
const override {
return CapAdd(OldStartMin(), duration_); }
1010 int64 OldEndMax()
const override {
return CapAdd(OldStartMax(), duration_); }
1011 void WhenEndRange(Demon*
const d)
override { WhenStartRange(d); }
1012 void WhenEndBound(Demon*
const d)
override { WhenEndRange(d); }
1014 bool MustBePerformed()
const override;
1015 bool MayBePerformed()
const override;
1016 void SetPerformed(
bool val)
override;
1017 bool WasPerformedBound()
const override {
return true; }
1018 void WhenPerformedBound(Demon*
const d)
override {}
1019 void Process()
override;
1020 std::string DebugString()
const override;
1022 void Accept(ModelVisitor*
const visitor)
const override {
1023 visitor->VisitIntervalVariable(
this,
"", 0, NullInterval());
1026 IntExpr* StartExpr()
override {
return &start_; }
1027 IntExpr* DurationExpr()
override {
return solver()->MakeIntConst(duration_); }
1028 IntExpr* EndExpr()
override {
1029 return solver()->MakeSum(StartExpr(), duration_);
1031 IntExpr* PerformedExpr()
override {
return solver()->MakeIntConst(1); }
1032 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
1035 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
1036 return DurationExpr();
1038 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
return EndExpr(); }
1041 void CheckOldPerformed() {}
1042 void Push()
override;
1048FixedDurationPerformedIntervalVar::FixedDurationPerformedIntervalVar(
1050 const std::string&
name)
1051 : BaseIntervalVar(s,
name),
1053 duration_(duration) {}
1055FixedDurationPerformedIntervalVar::FixedDurationPerformedIntervalVar(
1056 Solver*
const s,
const std::string&
name)
1057 : BaseIntervalVar(s,
name), start_(s, this, 0, 0), duration_(0) {}
1059void FixedDurationPerformedIntervalVar::Process() {
1062 start_.UpdatePostponedBounds();
1064 start_.ProcessDemons();
1065 reset_action_on_fail();
1067 start_.UpdatePreviousBounds();
1068 start_.ApplyPostponedBounds(START);
1071int64 FixedDurationPerformedIntervalVar::StartMin()
const {
1072 return start_.Min();
1075int64 FixedDurationPerformedIntervalVar::StartMax()
const {
1076 return start_.Max();
1079void FixedDurationPerformedIntervalVar::SetStartMin(
int64 m) {
1083void FixedDurationPerformedIntervalVar::SetStartMax(
int64 m) {
1087void FixedDurationPerformedIntervalVar::SetStartRange(
int64 mi,
int64 ma) {
1088 start_.SetRange(mi, ma);
1091int64 FixedDurationPerformedIntervalVar::DurationMin()
const {
1095int64 FixedDurationPerformedIntervalVar::DurationMax()
const {
1099void FixedDurationPerformedIntervalVar::SetDurationMin(
int64 m) {
1100 if (m > duration_) {
1101 SetPerformed(
false);
1105void FixedDurationPerformedIntervalVar::SetDurationMax(
int64 m) {
1106 if (m < duration_) {
1107 SetPerformed(
false);
1110int64 FixedDurationPerformedIntervalVar::EndMin()
const {
1111 return CapAdd(start_.Min(), duration_);
1114int64 FixedDurationPerformedIntervalVar::EndMax()
const {
1115 return CapAdd(start_.Max(), duration_);
1118void FixedDurationPerformedIntervalVar::SetEndMin(
int64 m) {
1119 SetStartMin(
CapSub(m, duration_));
1122void FixedDurationPerformedIntervalVar::SetEndMax(
int64 m) {
1123 SetStartMax(
CapSub(m, duration_));
1126void FixedDurationPerformedIntervalVar::SetEndRange(
int64 mi,
int64 ma) {
1127 SetStartRange(
CapSub(mi, duration_),
CapSub(ma, duration_));
1130void FixedDurationPerformedIntervalVar::SetDurationRange(
int64 mi,
int64 ma) {
1131 if (mi > duration_ || ma < duration_ || mi > ma) {
1132 SetPerformed(
false);
1136bool FixedDurationPerformedIntervalVar::MustBePerformed()
const {
return true; }
1138bool FixedDurationPerformedIntervalVar::MayBePerformed()
const {
return true; }
1140void FixedDurationPerformedIntervalVar::SetPerformed(
bool val) {
1146void FixedDurationPerformedIntervalVar::Push() {
1152std::string FixedDurationPerformedIntervalVar::DebugString()
const {
1154 const std::string& var_name =
name();
1155 if (!var_name.empty()) {
1156 out = var_name +
"(start = ";
1158 out =
"IntervalVar(start = ";
1160 absl::StrAppendFormat(&out,
"%s, duration = %d, performed = true)",
1161 start_.DebugString(), duration_);
1167class StartVarPerformedIntervalVar :
public IntervalVar {
1169 StartVarPerformedIntervalVar(Solver*
const s, IntVar*
const var,
1170 int64 duration,
const std::string&
name);
1171 ~StartVarPerformedIntervalVar()
override {}
1173 int64 StartMin()
const override;
1174 int64 StartMax()
const override;
1175 void SetStartMin(
int64 m)
override;
1176 void SetStartMax(
int64 m)
override;
1177 void SetStartRange(
int64 mi,
int64 ma)
override;
1178 int64 OldStartMin()
const override {
return start_var_->OldMin(); }
1179 int64 OldStartMax()
const override {
return start_var_->OldMax(); }
1180 void WhenStartRange(Demon*
const d)
override { start_var_->WhenRange(d); }
1181 void WhenStartBound(Demon*
const d)
override { start_var_->WhenBound(d); }
1183 int64 DurationMin()
const override;
1184 int64 DurationMax()
const override;
1185 void SetDurationMin(
int64 m)
override;
1186 void SetDurationMax(
int64 m)
override;
1187 void SetDurationRange(
int64 mi,
int64 ma)
override;
1188 int64 OldDurationMin()
const override {
return duration_; }
1189 int64 OldDurationMax()
const override {
return duration_; }
1190 void WhenDurationRange(Demon*
const d)
override {}
1191 void WhenDurationBound(Demon*
const d)
override {}
1193 int64 EndMin()
const override;
1194 int64 EndMax()
const override;
1195 void SetEndMin(
int64 m)
override;
1196 void SetEndMax(
int64 m)
override;
1197 void SetEndRange(
int64 mi,
int64 ma)
override;
1198 int64 OldEndMin()
const override {
return CapAdd(OldStartMin(), duration_); }
1199 int64 OldEndMax()
const override {
return CapAdd(OldStartMax(), duration_); }
1200 void WhenEndRange(Demon*
const d)
override { start_var_->WhenRange(d); }
1201 void WhenEndBound(Demon*
const d)
override { start_var_->WhenBound(d); }
1203 bool MustBePerformed()
const override;
1204 bool MayBePerformed()
const override;
1205 void SetPerformed(
bool val)
override;
1206 bool WasPerformedBound()
const override {
return true; }
1207 void WhenPerformedBound(Demon*
const d)
override {}
1208 std::string DebugString()
const override;
1210 IntExpr* StartExpr()
override {
return start_var_; }
1211 IntExpr* DurationExpr()
override {
return solver()->MakeIntConst(duration_); }
1212 IntExpr* EndExpr()
override {
1213 return solver()->MakeSum(start_var_, duration_);
1215 IntExpr* PerformedExpr()
override {
return solver()->MakeIntConst(1); }
1216 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
1219 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
1220 return DurationExpr();
1222 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
return EndExpr(); }
1224 void Accept(ModelVisitor*
const visitor)
const override {
1225 visitor->VisitIntervalVariable(
this,
"", 0, NullInterval());
1229 IntVar*
const start_var_;
1234StartVarPerformedIntervalVar::StartVarPerformedIntervalVar(
1235 Solver*
const s, IntVar*
const var,
int64 duration,
const std::string&
name)
1236 : IntervalVar(s,
name), start_var_(
var), duration_(duration) {}
1238int64 StartVarPerformedIntervalVar::StartMin()
const {
1239 return start_var_->Min();
1242int64 StartVarPerformedIntervalVar::StartMax()
const {
1243 return start_var_->Max();
1246void StartVarPerformedIntervalVar::SetStartMin(
int64 m) {
1247 start_var_->SetMin(m);
1250void StartVarPerformedIntervalVar::SetStartMax(
int64 m) {
1251 start_var_->SetMax(m);
1254void StartVarPerformedIntervalVar::SetStartRange(
int64 mi,
int64 ma) {
1255 start_var_->SetRange(mi, ma);
1258int64 StartVarPerformedIntervalVar::DurationMin()
const {
return duration_; }
1260int64 StartVarPerformedIntervalVar::DurationMax()
const {
return duration_; }
1262void StartVarPerformedIntervalVar::SetDurationMin(
int64 m) {
1263 if (m > duration_) {
1268void StartVarPerformedIntervalVar::SetDurationMax(
int64 m) {
1269 if (m < duration_) {
1273int64 StartVarPerformedIntervalVar::EndMin()
const {
1274 return start_var_->Min() + duration_;
1277int64 StartVarPerformedIntervalVar::EndMax()
const {
1278 return start_var_->Max() + duration_;
1281void StartVarPerformedIntervalVar::SetEndMin(
int64 m) {
1282 SetStartMin(
CapSub(m, duration_));
1285void StartVarPerformedIntervalVar::SetEndMax(
int64 m) {
1286 SetStartMax(
CapSub(m, duration_));
1289void StartVarPerformedIntervalVar::SetEndRange(
int64 mi,
int64 ma) {
1290 SetStartRange(
CapSub(mi, duration_),
CapSub(ma, duration_));
1293void StartVarPerformedIntervalVar::SetDurationRange(
int64 mi,
int64 ma) {
1294 if (mi > duration_ || ma < duration_ || mi > ma) {
1299bool StartVarPerformedIntervalVar::MustBePerformed()
const {
return true; }
1301bool StartVarPerformedIntervalVar::MayBePerformed()
const {
return true; }
1303void StartVarPerformedIntervalVar::SetPerformed(
bool val) {
1309std::string StartVarPerformedIntervalVar::DebugString()
const {
1311 const std::string& var_name =
name();
1312 if (!var_name.empty()) {
1313 out = var_name +
"(start = ";
1315 out =
"IntervalVar(start = ";
1317 absl::StrAppendFormat(&out,
"%d", start_var_->Min());
1318 if (!start_var_->Bound()) {
1319 absl::StrAppendFormat(&out,
" .. %d", start_var_->Max());
1322 absl::StrAppendFormat(&out,
", duration = %d, performed = true)", duration_);
1328class StartVarIntervalVar :
public BaseIntervalVar {
1330 StartVarIntervalVar(Solver*
const s, IntVar*
const start,
int64 duration,
1332 ~StartVarIntervalVar()
override {}
1334 int64 StartMin()
const override;
1335 int64 StartMax()
const override;
1336 void SetStartMin(
int64 m)
override;
1337 void SetStartMax(
int64 m)
override;
1338 void SetStartRange(
int64 mi,
int64 ma)
override;
1339 int64 OldStartMin()
const override {
return start_->OldMin(); }
1340 int64 OldStartMax()
const override {
return start_->OldMax(); }
1341 void WhenStartRange(Demon*
const d)
override {
1342 if (performed_->Max() == 1) {
1343 start_->WhenRange(d);
1346 void WhenStartBound(Demon*
const d)
override {
1347 if (performed_->Max() == 1) {
1348 start_->WhenBound(d);
1352 int64 DurationMin()
const override;
1353 int64 DurationMax()
const override;
1354 void SetDurationMin(
int64 m)
override;
1355 void SetDurationMax(
int64 m)
override;
1356 void SetDurationRange(
int64 mi,
int64 ma)
override;
1357 int64 OldDurationMin()
const override {
return duration_; }
1358 int64 OldDurationMax()
const override {
return duration_; }
1359 void WhenDurationRange(Demon*
const d)
override {}
1360 void WhenDurationBound(Demon*
const d)
override {}
1362 int64 EndMin()
const override;
1363 int64 EndMax()
const override;
1364 void SetEndMin(
int64 m)
override;
1365 void SetEndMax(
int64 m)
override;
1366 void SetEndRange(
int64 mi,
int64 ma)
override;
1367 int64 OldEndMin()
const override {
return CapAdd(OldStartMin(), duration_); }
1368 int64 OldEndMax()
const override {
return CapAdd(OldStartMax(), duration_); }
1369 void WhenEndRange(Demon*
const d)
override { WhenStartRange(d); }
1370 void WhenEndBound(Demon*
const d)
override { WhenStartBound(d); }
1372 bool MustBePerformed()
const override;
1373 bool MayBePerformed()
const override;
1374 void SetPerformed(
bool val)
override;
1375 bool WasPerformedBound()
const override {
1376 return performed_->OldMin() == performed_->OldMax();
1378 void WhenPerformedBound(Demon*
const d)
override { performed_->WhenBound(d); }
1379 std::string DebugString()
const override;
1381 void Accept(ModelVisitor*
const visitor)
const override {
1382 visitor->VisitIntervalVariable(
this,
"", 0, NullInterval());
1385 IntExpr* StartExpr()
override {
return start_; }
1386 IntExpr* DurationExpr()
override {
return solver()->MakeIntConst(duration_); }
1387 IntExpr* EndExpr()
override {
1388 return solver()->MakeSum(StartExpr(), duration_);
1390 IntExpr* PerformedExpr()
override {
return performed_; }
1391 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
1394 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
1397 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
1401 void Process()
override {
LOG(
FATAL) <<
"Should not be here"; }
1403 void Push()
override {
LOG(
FATAL) <<
"Should not be here"; }
1405 int64 StoredMin()
const {
return start_min_.Value(); }
1406 int64 StoredMax()
const {
return start_max_.Value(); }
1409 IntVar*
const start_;
1411 IntVar*
const performed_;
1412 Rev<int64> start_min_;
1413 Rev<int64> start_max_;
1416StartVarIntervalVar::StartVarIntervalVar(Solver*
const s, IntVar*
const start,
1419 const std::string&
name)
1420 : BaseIntervalVar(s,
name),
1422 duration_(duration),
1424 start_min_(start->Min()),
1425 start_max_(start->Max()) {}
1427int64 StartVarIntervalVar::StartMin()
const {
1429 return std::max(start_->Min(), start_min_.Value());
1432int64 StartVarIntervalVar::StartMax()
const {
1434 return std::min(start_->Max(), start_max_.Value());
1437void StartVarIntervalVar::SetStartMin(
int64 m) {
1438 if (performed_->Min() == 1) {
1441 start_min_.SetValue(solver(),
std::max(m, start_min_.Value()));
1442 if (start_min_.Value() >
std::min(start_max_.Value(), start_->Max())) {
1443 performed_->SetValue(0);
1448void StartVarIntervalVar::SetStartMax(
int64 m) {
1449 if (performed_->Min() == 1) {
1452 start_max_.SetValue(solver(),
std::min(m, start_max_.Value()));
1453 if (start_max_.Value() <
std::max(start_min_.Value(), start_->Min())) {
1454 performed_->SetValue(0);
1459void StartVarIntervalVar::SetStartRange(
int64 mi,
int64 ma) {
1460 if (performed_->Min() == 1) {
1461 start_->SetRange(mi, ma);
1463 start_min_.SetValue(solver(),
std::max(mi, start_min_.Value()));
1464 start_max_.SetValue(solver(),
std::min(ma, start_max_.Value()));
1465 if (
std::max(start_min_.Value(), start_->Min()) >
1466 std::min(start_max_.Value(), start_->Max())) {
1467 performed_->SetValue(0);
1472int64 StartVarIntervalVar::DurationMin()
const {
1477int64 StartVarIntervalVar::DurationMax()
const {
1482void StartVarIntervalVar::SetDurationMin(
int64 m) {
1483 if (m > duration_) {
1484 SetPerformed(
false);
1488void StartVarIntervalVar::SetDurationMax(
int64 m) {
1489 if (m < duration_) {
1490 SetPerformed(
false);
1494void StartVarIntervalVar::SetDurationRange(
int64 mi,
int64 ma) {
1495 if (mi > duration_ || ma < duration_ || mi > ma) {
1496 SetPerformed(
false);
1500int64 StartVarIntervalVar::EndMin()
const {
1502 return CapAdd(StartMin(), duration_);
1505int64 StartVarIntervalVar::EndMax()
const {
1507 return CapAdd(StartMax(), duration_);
1510void StartVarIntervalVar::SetEndMin(
int64 m) {
1511 SetStartMin(
CapSub(m, duration_));
1514void StartVarIntervalVar::SetEndMax(
int64 m) {
1515 SetStartMax(
CapSub(m, duration_));
1518void StartVarIntervalVar::SetEndRange(
int64 mi,
int64 ma) {
1519 SetStartRange(
CapSub(mi, duration_),
CapSub(ma, duration_));
1522bool StartVarIntervalVar::MustBePerformed()
const {
1523 return (performed_->Min() == 1);
1526bool StartVarIntervalVar::MayBePerformed()
const {
1527 return (performed_->Max() == 1);
1530void StartVarIntervalVar::SetPerformed(
bool val) {
1531 const bool was_bound = performed_->Bound();
1532 performed_->SetValue(val);
1533 if (val && !was_bound) {
1534 start_->SetRange(start_min_.Value(), start_max_.Value());
1538std::string StartVarIntervalVar::DebugString()
const {
1539 const std::string& var_name =
name();
1540 if (performed_->Max() == 0) {
1541 if (!var_name.empty()) {
1542 return absl::StrFormat(
"%s(performed = false)", var_name);
1544 return "IntervalVar(performed = false)";
1548 if (!var_name.empty()) {
1549 out = var_name +
"(start = ";
1551 out =
"IntervalVar(start = ";
1553 absl::StrAppendFormat(&out,
"%s, duration = %d, performed = %s)",
1554 start_->DebugString(), duration_,
1555 performed_->DebugString());
1560class LinkStartVarIntervalVar :
public Constraint {
1562 LinkStartVarIntervalVar(Solver*
const solver,
1563 StartVarIntervalVar*
const interval,
1564 IntVar*
const start, IntVar*
const performed)
1565 : Constraint(solver),
1570 ~LinkStartVarIntervalVar()
override {}
1572 void Post()
override {
1574 solver(),
this, &LinkStartVarIntervalVar::PerformedBound,
1576 performed_->WhenBound(demon);
1579 void InitialPropagate()
override {
1580 if (performed_->Bound()) {
1585 void PerformedBound() {
1586 if (performed_->Min() == 1) {
1587 start_->SetRange(interval_->StoredMin(), interval_->StoredMax());
1592 StartVarIntervalVar*
const interval_;
1593 IntVar*
const start_;
1594 IntVar*
const performed_;
1599class FixedInterval :
public IntervalVar {
1601 FixedInterval(Solver*
const s,
int64 start,
int64 duration,
1602 const std::string&
name);
1603 ~FixedInterval()
override {}
1605 int64 StartMin()
const override {
return start_; }
1606 int64 StartMax()
const override {
return start_; }
1607 void SetStartMin(
int64 m)
override;
1608 void SetStartMax(
int64 m)
override;
1609 void SetStartRange(
int64 mi,
int64 ma)
override;
1610 int64 OldStartMin()
const override {
return start_; }
1611 int64 OldStartMax()
const override {
return start_; }
1612 void WhenStartRange(Demon*
const d)
override {}
1613 void WhenStartBound(Demon*
const d)
override {}
1615 int64 DurationMin()
const override {
return duration_; }
1616 int64 DurationMax()
const override {
return duration_; }
1617 void SetDurationMin(
int64 m)
override;
1618 void SetDurationMax(
int64 m)
override;
1619 void SetDurationRange(
int64 mi,
int64 ma)
override;
1620 int64 OldDurationMin()
const override {
return duration_; }
1621 int64 OldDurationMax()
const override {
return duration_; }
1622 void WhenDurationRange(Demon*
const d)
override {}
1623 void WhenDurationBound(Demon*
const d)
override {}
1625 int64 EndMin()
const override {
return start_ + duration_; }
1626 int64 EndMax()
const override {
return start_ + duration_; }
1627 void SetEndMin(
int64 m)
override;
1628 void SetEndMax(
int64 m)
override;
1629 void SetEndRange(
int64 mi,
int64 ma)
override;
1630 int64 OldEndMin()
const override {
return start_ + duration_; }
1631 int64 OldEndMax()
const override {
return start_ + duration_; }
1632 void WhenEndRange(Demon*
const d)
override {}
1633 void WhenEndBound(Demon*
const d)
override {}
1635 bool MustBePerformed()
const override {
return true; }
1636 bool MayBePerformed()
const override {
return true; }
1637 void SetPerformed(
bool val)
override;
1638 bool WasPerformedBound()
const override {
return true; }
1639 void WhenPerformedBound(Demon*
const d)
override {}
1640 std::string DebugString()
const override;
1642 void Accept(ModelVisitor*
const visitor)
const override {
1643 visitor->VisitIntervalVariable(
this,
"", 0, NullInterval());
1646 IntExpr* StartExpr()
override {
return solver()->MakeIntConst(start_); }
1647 IntExpr* DurationExpr()
override {
return solver()->MakeIntConst(duration_); }
1648 IntExpr* EndExpr()
override {
1649 return solver()->MakeIntConst(start_ + duration_);
1651 IntExpr* PerformedExpr()
override {
return solver()->MakeIntConst(1); }
1652 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
1655 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
1656 return DurationExpr();
1658 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
return EndExpr(); }
1662 const int64 duration_;
1665FixedInterval::FixedInterval(Solver*
const s,
int64 start,
int64 duration,
1666 const std::string&
name)
1667 : IntervalVar(s,
name), start_(start), duration_(duration) {}
1669void FixedInterval::SetStartMin(
int64 m) {
1675void FixedInterval::SetStartMax(
int64 m) {
1681void FixedInterval::SetStartRange(
int64 mi,
int64 ma) {
1682 if (mi > start_ || ma < start_) {
1687void FixedInterval::SetDurationMin(
int64 m) {
1688 if (m > duration_) {
1693void FixedInterval::SetDurationMax(
int64 m) {
1694 if (m < duration_) {
1699void FixedInterval::SetEndMin(
int64 m) {
1700 if (m > start_ + duration_) {
1705void FixedInterval::SetEndMax(
int64 m) {
1706 if (m < start_ + duration_) {
1711void FixedInterval::SetEndRange(
int64 mi,
int64 ma) {
1712 if (mi > start_ + duration_ || ma < start_ + duration_) {
1717void FixedInterval::SetDurationRange(
int64 mi,
int64 ma) {
1718 if (mi > duration_ || ma < duration_) {
1723void FixedInterval::SetPerformed(
bool val) {
1729std::string FixedInterval::DebugString()
const {
1731 const std::string& var_name =
name();
1732 if (!var_name.empty()) {
1733 out = var_name +
"(start = ";
1735 out =
"IntervalVar(start = ";
1737 absl::StrAppendFormat(&out,
"%d, duration = %d, performed = true)", start_,
1744class VariableDurationIntervalVar :
public BaseIntervalVar {
1749 const std::string&
name)
1750 : BaseIntervalVar(s,
name),
1757 performed_(s, this, optional) {}
1759 ~VariableDurationIntervalVar()
override {}
1761 int64 StartMin()
const override {
1763 return start_.Min();
1766 int64 StartMax()
const override {
1768 return start_.Max();
1771 void SetStartMin(
int64 m)
override {
1772 if (performed_.Max() == 1) {
1777 void SetStartMax(
int64 m)
override {
1778 if (performed_.Max() == 1) {
1783 void SetStartRange(
int64 mi,
int64 ma)
override {
1784 if (performed_.Max() == 1) {
1785 start_.SetRange(mi, ma);
1789 int64 OldStartMin()
const override {
1792 return start_.OldMin();
1795 int64 OldStartMax()
const override {
1798 return start_.OldMax();
1801 void WhenStartRange(Demon*
const d)
override {
1802 if (performed_.Max() == 1) {
1803 start_.WhenRange(d);
1807 void WhenStartBound(Demon*
const d)
override {
1808 if (performed_.Max() == 1) {
1809 start_.WhenBound(d);
1813 int64 DurationMin()
const override {
1815 return duration_.Min();
1818 int64 DurationMax()
const override {
1820 return duration_.Max();
1823 void SetDurationMin(
int64 m)
override {
1824 if (performed_.Max() == 1) {
1825 duration_.SetMin(m);
1829 void SetDurationMax(
int64 m)
override {
1830 if (performed_.Max() == 1) {
1831 duration_.SetMax(m);
1835 void SetDurationRange(
int64 mi,
int64 ma)
override {
1836 if (performed_.Max() == 1) {
1837 duration_.SetRange(mi, ma);
1841 int64 OldDurationMin()
const override {
1844 return duration_.OldMin();
1847 int64 OldDurationMax()
const override {
1850 return duration_.OldMax();
1853 void WhenDurationRange(Demon*
const d)
override {
1854 if (performed_.Max() == 1) {
1855 duration_.WhenRange(d);
1859 void WhenDurationBound(Demon*
const d)
override {
1860 if (performed_.Max() == 1) {
1861 duration_.WhenBound(d);
1865 int64 EndMin()
const override {
1870 int64 EndMax()
const override {
1875 void SetEndMin(
int64 m)
override {
1876 if (performed_.Max() == 1) {
1881 void SetEndMax(
int64 m)
override {
1882 if (performed_.Max() == 1) {
1887 void SetEndRange(
int64 mi,
int64 ma)
override {
1888 if (performed_.Max() == 1) {
1889 end_.SetRange(mi, ma);
1893 int64 OldEndMin()
const override {
1896 return end_.OldMin();
1899 int64 OldEndMax()
const override {
1902 return end_.OldMax();
1905 void WhenEndRange(Demon*
const d)
override {
1906 if (performed_.Max() == 1) {
1911 void WhenEndBound(Demon*
const d)
override {
1912 if (performed_.Max() == 1) {
1917 bool MustBePerformed()
const override {
return (performed_.Min() == 1); }
1919 bool MayBePerformed()
const override {
return (performed_.Max() == 1); }
1921 void SetPerformed(
bool val)
override { performed_.SetValue(val); }
1923 bool WasPerformedBound()
const override {
1925 return performed_.OldMin() == performed_.OldMax();
1928 void WhenPerformedBound(Demon*
const d)
override { performed_.WhenBound(d); }
1930 void Process()
override {
1933 start_.UpdatePostponedBounds();
1934 duration_.UpdatePostponedBounds();
1935 end_.UpdatePostponedBounds();
1936 performed_.UpdatePostponedValue();
1938 if (performed_.Max() == 1) {
1939 start_.ProcessDemons();
1940 duration_.ProcessDemons();
1941 end_.ProcessDemons();
1943 performed_.Process();
1944 reset_action_on_fail();
1947 start_.UpdatePreviousBounds();
1948 start_.ApplyPostponedBounds(START);
1949 duration_.UpdatePreviousBounds();
1950 duration_.ApplyPostponedBounds(DURATION);
1951 end_.UpdatePreviousBounds();
1952 end_.ApplyPostponedBounds(END);
1953 performed_.UpdatePreviousValueAndApplyPostponedValue();
1956 std::string DebugString()
const override {
1957 const std::string& var_name =
name();
1958 if (performed_.Max() != 1) {
1959 if (!var_name.empty()) {
1960 return absl::StrFormat(
"%s(performed = false)", var_name);
1962 return "IntervalVar(performed = false)";
1966 if (!var_name.empty()) {
1967 out = var_name +
"(start = ";
1969 out =
"IntervalVar(start = ";
1972 absl::StrAppendFormat(&out,
1973 "%s, duration = %s, end = %s, performed = %s)",
1974 start_.DebugString(), duration_.DebugString(),
1975 end_.DebugString(), performed_.DebugString());
1980 void Accept(ModelVisitor*
const visitor)
const override {
1981 visitor->VisitIntervalVariable(
this,
"", 0, NullInterval());
1984 IntExpr* StartExpr()
override {
return &start_; }
1985 IntExpr* DurationExpr()
override {
return &duration_; }
1986 IntExpr* EndExpr()
override {
return &end_; }
1987 IntExpr* PerformedExpr()
override {
return &performed_; }
1988 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
1991 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
1994 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
1999 void Push()
override {
2001 if (performed_.Max() == 1) {
2005 start_.SetRange(
CapSub(end_.Min(), duration_.Max()),
2006 CapSub(end_.Max(), duration_.Min()));
2007 duration_.SetRange(
CapSub(end_.Min(), start_.Max()),
2008 CapSub(end_.Max(), start_.Min()));
2009 end_.SetRange(
CapAdd(start_.Min(), duration_.Min()),
2010 CapAdd(start_.Max(), duration_.Max()));
2019 PerformedVar performed_;
2024class FixedDurationSyncedIntervalVar :
public IntervalVar {
2026 FixedDurationSyncedIntervalVar(IntervalVar*
const t,
int64 duration,
2028 : IntervalVar(t->solver(),
name),
2030 duration_(duration),
2032 ~FixedDurationSyncedIntervalVar()
override {}
2033 int64 DurationMin()
const override {
return duration_; }
2034 int64 DurationMax()
const override {
return duration_; }
2035 void SetDurationMin(
int64 m)
override {
2036 if (m > duration_) {
2040 void SetDurationMax(
int64 m)
override {
2041 if (m < duration_) {
2045 void SetDurationRange(
int64 mi,
int64 ma)
override {
2046 if (mi > duration_ || ma < duration_ || mi > ma) {
2050 int64 OldDurationMin()
const override {
return duration_; }
2051 int64 OldDurationMax()
const override {
return duration_; }
2052 void WhenDurationRange(Demon*
const d)
override {}
2053 void WhenDurationBound(Demon*
const d)
override {}
2054 int64 EndMin()
const override {
return CapAdd(StartMin(), duration_); }
2055 int64 EndMax()
const override {
return CapAdd(StartMax(), duration_); }
2056 void SetEndMin(
int64 m)
override { SetStartMin(
CapSub(m, duration_)); }
2057 void SetEndMax(
int64 m)
override { SetStartMax(
CapSub(m, duration_)); }
2058 void SetEndRange(
int64 mi,
int64 ma)
override {
2059 SetStartRange(
CapSub(mi, duration_),
CapSub(ma, duration_));
2061 int64 OldEndMin()
const override {
return CapAdd(OldStartMin(), duration_); }
2062 int64 OldEndMax()
const override {
return CapAdd(OldStartMax(), duration_); }
2063 void WhenEndRange(Demon*
const d)
override { WhenStartRange(d); }
2064 void WhenEndBound(Demon*
const d)
override { WhenStartBound(d); }
2065 bool MustBePerformed()
const override {
return t_->MustBePerformed(); }
2066 bool MayBePerformed()
const override {
return t_->MayBePerformed(); }
2067 void SetPerformed(
bool val)
override { t_->SetPerformed(val); }
2068 bool WasPerformedBound()
const override {
return t_->WasPerformedBound(); }
2069 void WhenPerformedBound(Demon*
const d)
override {
2070 t_->WhenPerformedBound(d);
2074 IntervalVar*
const t_;
2075 const int64 duration_;
2084class FixedDurationIntervalVarStartSyncedOnStart
2085 :
public FixedDurationSyncedIntervalVar {
2087 FixedDurationIntervalVarStartSyncedOnStart(IntervalVar*
const t,
2089 : FixedDurationSyncedIntervalVar(
2090 t, duration, offset,
2092 "IntervalStartSyncedOnStart(%s, duration = %d, offset = %d)",
2093 t->
name(), duration, offset)) {}
2094 ~FixedDurationIntervalVarStartSyncedOnStart()
override {}
2099 void SetStartRange(
int64 mi,
int64 ma)
override {
2102 int64 OldStartMin()
const override {
2105 int64 OldStartMax()
const override {
2108 void WhenStartRange(Demon*
const d)
override { t_->WhenStartRange(d); }
2109 void WhenStartBound(Demon*
const d)
override { t_->WhenStartBound(d); }
2110 IntExpr* StartExpr()
override {
2111 return solver()->MakeSum(t_->StartExpr(),
offset_);
2113 IntExpr* DurationExpr()
override {
return solver()->MakeIntConst(duration_); }
2114 IntExpr* EndExpr()
override {
2115 return solver()->MakeSum(t_->StartExpr(),
offset_ + duration_);
2117 IntExpr* PerformedExpr()
override {
return t_->PerformedExpr(); }
2121 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
2124 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
2127 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
2130 void Accept(ModelVisitor*
const visitor)
const override {
2131 visitor->VisitIntervalVariable(
2132 this, ModelVisitor::kStartSyncOnStartOperation,
offset_, t_);
2134 std::string DebugString()
const override {
2135 return absl::StrFormat(
2136 "IntervalStartSyncedOnStart(%s, duration = %d, offset = %d)",
2137 t_->DebugString(), duration_,
offset_);
2143class FixedDurationIntervalVarStartSyncedOnEnd
2144 :
public FixedDurationSyncedIntervalVar {
2146 FixedDurationIntervalVarStartSyncedOnEnd(IntervalVar*
const t,
int64 duration,
2148 : FixedDurationSyncedIntervalVar(
2149 t, duration, offset,
2151 "IntervalStartSyncedOnEnd(%s, duration = %d, offset = %d)",
2152 t->
name(), duration, offset)) {}
2153 ~FixedDurationIntervalVarStartSyncedOnEnd()
override {}
2158 void SetStartRange(
int64 mi,
int64 ma)
override {
2161 int64 OldStartMin()
const override {
2164 int64 OldStartMax()
const override {
2167 void WhenStartRange(Demon*
const d)
override { t_->WhenEndRange(d); }
2168 void WhenStartBound(Demon*
const d)
override { t_->WhenEndBound(d); }
2169 IntExpr* StartExpr()
override {
2170 return solver()->MakeSum(t_->EndExpr(),
offset_);
2172 IntExpr* DurationExpr()
override {
return solver()->MakeIntConst(duration_); }
2173 IntExpr* EndExpr()
override {
2174 return solver()->MakeSum(t_->EndExpr(),
offset_ + duration_);
2176 IntExpr* PerformedExpr()
override {
return t_->PerformedExpr(); }
2180 IntExpr* SafeStartExpr(
int64 unperformed_value)
override {
2183 IntExpr* SafeDurationExpr(
int64 unperformed_value)
override {
2186 IntExpr* SafeEndExpr(
int64 unperformed_value)
override {
2190 void Accept(ModelVisitor*
const visitor)
const override {
2191 visitor->VisitIntervalVariable(
this, ModelVisitor::kStartSyncOnEndOperation,
2194 std::string DebugString()
const override {
2195 return absl::StrFormat(
2196 "IntervalStartSyncedOnEnd(%s, duration = %d, offset = %d)",
2197 t_->DebugString(), duration_,
offset_);
2205 return RegisterIntervalVar(
2206 RevAlloc(
new MirrorIntervalVar(
this, interval_var)));
2211 return interval_var;
2213 return RegisterIntervalVar(
2214 RevAlloc(
new IntervalVarRelaxedMax(interval_var)));
2220 return interval_var;
2222 return RegisterIntervalVar(
2223 RevAlloc(
new IntervalVarRelaxedMin(interval_var)));
2227void IntervalVar::WhenAnything(
Demon*
const d) {
2229 WhenDurationRange(d);
2231 WhenPerformedBound(d);
2235 const std::string&
name) {
2236 return RevAlloc(
new FixedInterval(
this, start, duration,
name));
2241 int64 duration,
bool optional,
2242 const std::string&
name) {
2245 }
else if (!optional) {
2246 return RegisterIntervalVar(RevAlloc(
new FixedDurationPerformedIntervalVar(
2249 return RegisterIntervalVar(RevAlloc(
new FixedDurationIntervalVar(
2253void Solver::MakeFixedDurationIntervalVarArray(
2255 const std::string&
name, std::vector<IntervalVar*>* array) {
2257 CHECK(array !=
nullptr);
2259 for (
int i = 0; i < count; ++i) {
2260 const std::string var_name = absl::StrCat(
name, i);
2261 array->push_back(MakeFixedDurationIntervalVar(
2268 const std::string&
name) {
2269 CHECK(start_variable !=
nullptr);
2271 return RegisterIntervalVar(RevAlloc(
2272 new StartVarPerformedIntervalVar(
this, start_variable, duration,
name)));
2279 IntVar*
const performed_variable,
const std::string&
name) {
2280 CHECK(start_variable !=
nullptr);
2281 CHECK(performed_variable !=
nullptr);
2283 if (!performed_variable->
Bound()) {
2284 StartVarIntervalVar*
const interval =
2285 reinterpret_cast<StartVarIntervalVar*
>(
2286 RegisterIntervalVar(RevAlloc(
new StartVarIntervalVar(
2287 this, start_variable, duration, performed_variable,
name))));
2288 AddConstraint(RevAlloc(
new LinkStartVarIntervalVar(
2289 this,
interval, start_variable, performed_variable)));
2291 }
else if (performed_variable->
Min() == 1) {
2292 return RegisterIntervalVar(RevAlloc(
new StartVarPerformedIntervalVar(
2293 this, start_variable, duration,
name)));
2298void Solver::MakeFixedDurationIntervalVarArray(
2299 const std::vector<IntVar*>& start_variables,
int64 duration,
2300 const std::string&
name, std::vector<IntervalVar*>* array) {
2301 CHECK(array !=
nullptr);
2303 for (
int i = 0; i < start_variables.size(); ++i) {
2304 const std::string var_name = absl::StrCat(
name, i);
2306 MakeFixedDurationIntervalVar(start_variables[i], duration, var_name));
2312void Solver::MakeFixedDurationIntervalVarArray(
2313 const std::vector<IntVar*>& start_variables,
2314 const std::vector<int64>& durations,
const std::string&
name,
2315 std::vector<IntervalVar*>* array) {
2316 CHECK(array !=
nullptr);
2317 CHECK_EQ(start_variables.size(), durations.size());
2319 for (
int i = 0; i < start_variables.size(); ++i) {
2320 const std::string var_name = absl::StrCat(
name, i);
2321 array->push_back(MakeFixedDurationIntervalVar(start_variables[i],
2322 durations[i], var_name));
2326void Solver::MakeFixedDurationIntervalVarArray(
2327 const std::vector<IntVar*>& start_variables,
2328 const std::vector<int>& durations,
const std::string&
name,
2329 std::vector<IntervalVar*>* array) {
2330 CHECK(array !=
nullptr);
2331 CHECK_EQ(start_variables.size(), durations.size());
2333 for (
int i = 0; i < start_variables.size(); ++i) {
2334 const std::string var_name = absl::StrCat(
name, i);
2335 array->push_back(MakeFixedDurationIntervalVar(start_variables[i],
2336 durations[i], var_name));
2340void Solver::MakeFixedDurationIntervalVarArray(
2341 const std::vector<IntVar*>& start_variables,
2342 const std::vector<int>& durations,
2343 const std::vector<IntVar*>& performed_variables,
const std::string&
name,
2344 std::vector<IntervalVar*>* array) {
2345 CHECK(array !=
nullptr);
2347 for (
int i = 0; i < start_variables.size(); ++i) {
2348 const std::string var_name = absl::StrCat(
name, i);
2349 array->push_back(MakeFixedDurationIntervalVar(
2350 start_variables[i], durations[i], performed_variables[i], var_name));
2354void Solver::MakeFixedDurationIntervalVarArray(
2355 const std::vector<IntVar*>& start_variables,
2356 const std::vector<int64>& durations,
2357 const std::vector<IntVar*>& performed_variables,
const std::string&
name,
2358 std::vector<IntervalVar*>* array) {
2359 CHECK(array !=
nullptr);
2361 for (
int i = 0; i < start_variables.size(); ++i) {
2362 const std::string var_name = absl::StrCat(
name, i);
2363 array->push_back(MakeFixedDurationIntervalVar(
2364 start_variables[i], durations[i], performed_variables[i], var_name));
2373 bool optional,
const std::string&
name) {
2374 return RegisterIntervalVar(RevAlloc(
new VariableDurationIntervalVar(
2382 const std::string&
name,
2383 std::vector<IntervalVar*>*
const array) {
2385 CHECK(array !=
nullptr);
2387 for (
int i = 0; i < count; ++i) {
2388 const std::string var_name = absl::StrCat(
name, i);
2398 return RegisterIntervalVar(
2399 RevAlloc(
new FixedDurationIntervalVarStartSyncedOnStart(
2400 interval_var, duration, offset)));
2405 return RegisterIntervalVar(
2406 RevAlloc(
new FixedDurationIntervalVarStartSyncedOnEnd(interval_var,
2407 duration, offset)));
2412 return RegisterIntervalVar(
2413 RevAlloc(
new FixedDurationIntervalVarStartSyncedOnStart(
2414 interval_var, duration,
CapSub(offset, duration))));
2419 return RegisterIntervalVar(
2420 RevAlloc(
new FixedDurationIntervalVarStartSyncedOnEnd(
2421 interval_var, duration,
CapSub(offset, duration))));
#define DCHECK_NE(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
A Demon is the base element of a propagation queue.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual int64 Min() const =0
The class IntVar is a subset of IntExpr.
Interval variables are often used in scheduling.
static const int64 kMaxValidValue
The largest acceptable value to be returned by EndMax()
static const int64 kMinValidValue
The smallest acceptable value to be returned by StartMin()
virtual bool MustBePerformed() const =0
These methods query, set, and watch the performed status of the interval var.
static const char kMirrorOperation[]
Operations.
static const char kRelaxedMaxOperation[]
static const char kRelaxedMinOperation[]
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
std::function< void(Solver *)> Action
static const int64 kint64max
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
IntExpr * BuildEndExpr(IntervalVar *var)
IntExpr * BuildStartExpr(IntervalVar *var)
IntExpr * BuildSafeEndExpr(IntervalVar *var, int64 unperformed_value)
int64 CapSub(int64 x, int64 y)
IntExpr * BuildSafeStartExpr(IntervalVar *var, int64 unperformed_value)
IntExpr * BuildSafeDurationExpr(IntervalVar *var, int64 unperformed_value)
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
void LinkVarExpr(Solver *const s, IntExpr *const expr, IntVar *const var)
void RegisterDemon(Solver *const solver, Demon *const demon, DemonProfiler *const monitor)
void InternalSaveBooleanVarValue(Solver *const solver, IntVar *const var)
IntExpr * BuildDurationExpr(IntervalVar *var)