1 // Copyright 2010-2021 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 #include <cstdint>
15 #include <limits>
16 #include <string>
17 #include <vector>
18
19 #include "absl/strings/str_cat.h"
20 #include "absl/strings/str_format.h"
21 #include "ortools/base/integral_types.h"
22 #include "ortools/base/logging.h"
23 #include "ortools/base/macros.h"
24 #include "ortools/constraint_solver/constraint_solver.h"
25 #include "ortools/constraint_solver/constraint_solveri.h"
26 #include "ortools/util/saturated_arithmetic.h"
27
28 #if defined(_MSC_VER)
29 #pragma warning(disable : 4351 4355 4804 4805)
30 #endif
31
32 namespace operations_research {
33 // Generic code for start/end/duration expressions.
34 // This is not done in a superclass as this is not compatible with the current
35 // class hierarchy.
36
37 // ----- Expression builders ------
38
39 IntExpr* BuildStartExpr(IntervalVar* var);
40 IntExpr* BuildDurationExpr(IntervalVar* var);
41 IntExpr* BuildEndExpr(IntervalVar* var);
42 IntExpr* BuildSafeStartExpr(IntervalVar* var, int64_t unperformed_value);
43 IntExpr* BuildSafeDurationExpr(IntervalVar* var, int64_t unperformed_value);
44 IntExpr* BuildSafeEndExpr(IntervalVar* var, int64_t unperformed_value);
45 void LinkVarExpr(Solver* const s, IntExpr* const expr, IntVar* const var);
46
47 // It's good to have the two extreme values being symmetrical around zero: it
48 // makes mirroring easier.
49 const int64_t IntervalVar::kMaxValidValue =
50 std::numeric_limits<int64_t>::max() >> 2;
51 const int64_t IntervalVar::kMinValidValue = -kMaxValidValue;
52
53 namespace {
54 enum IntervalField { START, DURATION, END };
55
NullInterval()56 IntervalVar* NullInterval() { return nullptr; }
57 // ----- MirrorIntervalVar -----
58
59 class MirrorIntervalVar : public IntervalVar {
60 public:
MirrorIntervalVar(Solver * const s,IntervalVar * const t)61 MirrorIntervalVar(Solver* const s, IntervalVar* const t)
62 : IntervalVar(s, "Mirror<" + t->name() + ">"), t_(t) {}
~MirrorIntervalVar()63 ~MirrorIntervalVar() override {}
64
65 // These methods query, set and watch the start position of the
66 // interval var.
StartMin() const67 int64_t StartMin() const override { return -t_->EndMax(); }
StartMax() const68 int64_t StartMax() const override { return -t_->EndMin(); }
SetStartMin(int64_t m)69 void SetStartMin(int64_t m) override { t_->SetEndMax(-m); }
SetStartMax(int64_t m)70 void SetStartMax(int64_t m) override { t_->SetEndMin(-m); }
SetStartRange(int64_t mi,int64_t ma)71 void SetStartRange(int64_t mi, int64_t ma) override {
72 t_->SetEndRange(-ma, -mi);
73 }
OldStartMin() const74 int64_t OldStartMin() const override { return -t_->OldEndMax(); }
OldStartMax() const75 int64_t OldStartMax() const override { return -t_->OldEndMin(); }
WhenStartRange(Demon * const d)76 void WhenStartRange(Demon* const d) override { t_->WhenEndRange(d); }
WhenStartBound(Demon * const d)77 void WhenStartBound(Demon* const d) override { t_->WhenEndBound(d); }
78
79 // These methods query, set and watch the duration of the interval var.
DurationMin() const80 int64_t DurationMin() const override { return t_->DurationMin(); }
DurationMax() const81 int64_t DurationMax() const override { return t_->DurationMax(); }
SetDurationMin(int64_t m)82 void SetDurationMin(int64_t m) override { t_->SetDurationMin(m); }
SetDurationMax(int64_t m)83 void SetDurationMax(int64_t m) override { t_->SetDurationMax(m); }
SetDurationRange(int64_t mi,int64_t ma)84 void SetDurationRange(int64_t mi, int64_t ma) override {
85 t_->SetDurationRange(mi, ma);
86 }
OldDurationMin() const87 int64_t OldDurationMin() const override { return t_->OldDurationMin(); }
OldDurationMax() const88 int64_t OldDurationMax() const override { return t_->OldDurationMax(); }
WhenDurationRange(Demon * const d)89 void WhenDurationRange(Demon* const d) override { t_->WhenDurationRange(d); }
WhenDurationBound(Demon * const d)90 void WhenDurationBound(Demon* const d) override { t_->WhenDurationBound(d); }
91
92 // These methods query, set and watch the end position of the interval var.
EndMin() const93 int64_t EndMin() const override { return -t_->StartMax(); }
EndMax() const94 int64_t EndMax() const override { return -t_->StartMin(); }
SetEndMin(int64_t m)95 void SetEndMin(int64_t m) override { t_->SetStartMax(-m); }
SetEndMax(int64_t m)96 void SetEndMax(int64_t m) override { t_->SetStartMin(-m); }
SetEndRange(int64_t mi,int64_t ma)97 void SetEndRange(int64_t mi, int64_t ma) override {
98 t_->SetStartRange(-ma, -mi);
99 }
OldEndMin() const100 int64_t OldEndMin() const override { return -t_->OldStartMax(); }
OldEndMax() const101 int64_t OldEndMax() const override { return -t_->OldStartMin(); }
WhenEndRange(Demon * const d)102 void WhenEndRange(Demon* const d) override { t_->WhenStartRange(d); }
WhenEndBound(Demon * const d)103 void WhenEndBound(Demon* const d) override { t_->WhenStartBound(d); }
104
105 // These methods query, set and watches the performed status of the
106 // interval var.
MustBePerformed() const107 bool MustBePerformed() const override { return t_->MustBePerformed(); }
MayBePerformed() const108 bool MayBePerformed() const override { return t_->MayBePerformed(); }
SetPerformed(bool val)109 void SetPerformed(bool val) override { t_->SetPerformed(val); }
WasPerformedBound() const110 bool WasPerformedBound() const override { return t_->WasPerformedBound(); }
WhenPerformedBound(Demon * const d)111 void WhenPerformedBound(Demon* const d) override {
112 t_->WhenPerformedBound(d);
113 }
114
Accept(ModelVisitor * const visitor) const115 void Accept(ModelVisitor* const visitor) const override {
116 visitor->VisitIntervalVariable(this, ModelVisitor::kMirrorOperation, 0, t_);
117 }
118
DebugString() const119 std::string DebugString() const override {
120 return absl::StrFormat("MirrorInterval(%s)", t_->DebugString());
121 }
122
StartExpr()123 IntExpr* StartExpr() override {
124 return solver()->MakeOpposite(t_->EndExpr());
125 }
DurationExpr()126 IntExpr* DurationExpr() override { return t_->DurationExpr(); }
EndExpr()127 IntExpr* EndExpr() override {
128 return solver()->MakeOpposite(t_->StartExpr());
129 }
PerformedExpr()130 IntExpr* PerformedExpr() override { return t_->PerformedExpr(); }
131 // These methods create expressions encapsulating the start, end
132 // and duration of the interval var. If the interval var is
133 // unperformed, they will return the unperformed_value.
SafeStartExpr(int64_t unperformed_value)134 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
135 return solver()->MakeOpposite(t_->SafeEndExpr(-unperformed_value));
136 }
SafeDurationExpr(int64_t unperformed_value)137 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
138 return t_->SafeDurationExpr(unperformed_value);
139 }
SafeEndExpr(int64_t unperformed_value)140 IntExpr* SafeEndExpr(int64_t unperformed_value) override {
141 return solver()->MakeOpposite(t_->SafeStartExpr(-unperformed_value));
142 }
143
144 private:
145 IntervalVar* const t_;
146 DISALLOW_COPY_AND_ASSIGN(MirrorIntervalVar);
147 };
148
149 // An IntervalVar that passes all function calls to an underlying interval
150 // variable as long as it is not prohibited, and that interprets prohibited
151 // intervals as intervals of duration 0 that must be executed between
152 // [kMinValidValue and kMaxValidValue].
153 //
154 // Such interval variables have a very similar behavior to others.
155 // Invariants such as StartMin() + DurationMin() <= EndMin() that are maintained
156 // for traditional interval variables are maintained for instances of
157 // AlwaysPerformedIntervalVarWrapper. However, there is no monotonicity of the
158 // values returned by the start/end getters. For example, during a given
159 // propagation, three successive calls to StartMin could return,
160 // in this order, 1, 2, and kMinValidValue.
161 //
162
163 // This class exists so that we can easily implement the
164 // IntervalVarRelaxedMax and IntervalVarRelaxedMin classes below.
165 class AlwaysPerformedIntervalVarWrapper : public IntervalVar {
166 public:
AlwaysPerformedIntervalVarWrapper(IntervalVar * const t)167 explicit AlwaysPerformedIntervalVarWrapper(IntervalVar* const t)
168 : IntervalVar(t->solver(),
169 absl::StrFormat("AlwaysPerformed<%s>", t->name())),
170 t_(t),
171 start_expr_(nullptr),
172 duration_expr_(nullptr),
173 end_expr_(nullptr) {}
174
~AlwaysPerformedIntervalVarWrapper()175 ~AlwaysPerformedIntervalVarWrapper() override {}
StartMin() const176 int64_t StartMin() const override {
177 return MayUnderlyingBePerformed() ? t_->StartMin() : kMinValidValue;
178 }
StartMax() const179 int64_t StartMax() const override {
180 return MayUnderlyingBePerformed() ? t_->StartMax() : kMaxValidValue;
181 }
SetStartMin(int64_t m)182 void SetStartMin(int64_t m) override { t_->SetStartMin(m); }
SetStartMax(int64_t m)183 void SetStartMax(int64_t m) override { t_->SetStartMax(m); }
SetStartRange(int64_t mi,int64_t ma)184 void SetStartRange(int64_t mi, int64_t ma) override {
185 t_->SetStartRange(mi, ma);
186 }
OldStartMin() const187 int64_t OldStartMin() const override {
188 return MayUnderlyingBePerformed() ? t_->OldStartMin() : kMinValidValue;
189 }
OldStartMax() const190 int64_t OldStartMax() const override {
191 return MayUnderlyingBePerformed() ? t_->OldStartMax() : kMaxValidValue;
192 }
WhenStartRange(Demon * const d)193 void WhenStartRange(Demon* const d) override { t_->WhenStartRange(d); }
WhenStartBound(Demon * const d)194 void WhenStartBound(Demon* const d) override { t_->WhenStartBound(d); }
DurationMin() const195 int64_t DurationMin() const override {
196 return MayUnderlyingBePerformed() ? t_->DurationMin() : 0LL;
197 }
DurationMax() const198 int64_t DurationMax() const override {
199 return MayUnderlyingBePerformed() ? t_->DurationMax() : 0LL;
200 }
SetDurationMin(int64_t m)201 void SetDurationMin(int64_t m) override { t_->SetDurationMin(m); }
SetDurationMax(int64_t m)202 void SetDurationMax(int64_t m) override { t_->SetDurationMax(m); }
SetDurationRange(int64_t mi,int64_t ma)203 void SetDurationRange(int64_t mi, int64_t ma) override {
204 t_->SetDurationRange(mi, ma);
205 }
OldDurationMin() const206 int64_t OldDurationMin() const override {
207 return MayUnderlyingBePerformed() ? t_->OldDurationMin() : 0LL;
208 }
OldDurationMax() const209 int64_t OldDurationMax() const override {
210 return MayUnderlyingBePerformed() ? t_->OldDurationMax() : 0LL;
211 }
WhenDurationRange(Demon * const d)212 void WhenDurationRange(Demon* const d) override { t_->WhenDurationRange(d); }
WhenDurationBound(Demon * const d)213 void WhenDurationBound(Demon* const d) override { t_->WhenDurationBound(d); }
EndMin() const214 int64_t EndMin() const override {
215 return MayUnderlyingBePerformed() ? t_->EndMin() : kMinValidValue;
216 }
EndMax() const217 int64_t EndMax() const override {
218 return MayUnderlyingBePerformed() ? t_->EndMax() : kMaxValidValue;
219 }
SetEndMin(int64_t m)220 void SetEndMin(int64_t m) override { t_->SetEndMin(m); }
SetEndMax(int64_t m)221 void SetEndMax(int64_t m) override { t_->SetEndMax(m); }
SetEndRange(int64_t mi,int64_t ma)222 void SetEndRange(int64_t mi, int64_t ma) override { t_->SetEndRange(mi, ma); }
OldEndMin() const223 int64_t OldEndMin() const override {
224 return MayUnderlyingBePerformed() ? t_->OldEndMin() : kMinValidValue;
225 }
OldEndMax() const226 int64_t OldEndMax() const override {
227 return MayUnderlyingBePerformed() ? t_->OldEndMax() : kMaxValidValue;
228 }
WhenEndRange(Demon * const d)229 void WhenEndRange(Demon* const d) override { t_->WhenEndRange(d); }
WhenEndBound(Demon * const d)230 void WhenEndBound(Demon* const d) override { t_->WhenEndBound(d); }
MustBePerformed() const231 bool MustBePerformed() const override { return true; }
MayBePerformed() const232 bool MayBePerformed() const override { return true; }
SetPerformed(bool val)233 void SetPerformed(bool val) override {
234 // An AlwaysPerformedIntervalVarWrapper interval variable is always
235 // performed. So setting it to be performed does not change anything,
236 // and setting it not to be performed is inconsistent and should cause
237 // a failure.
238 if (!val) {
239 solver()->Fail();
240 }
241 }
WasPerformedBound() const242 bool WasPerformedBound() const override { return true; }
WhenPerformedBound(Demon * const d)243 void WhenPerformedBound(Demon* const d) override {
244 t_->WhenPerformedBound(d);
245 }
StartExpr()246 IntExpr* StartExpr() override {
247 if (start_expr_ == nullptr) {
248 solver()->SaveValue(reinterpret_cast<void**>(&start_expr_));
249 start_expr_ = BuildStartExpr(this);
250 }
251 return start_expr_;
252 }
DurationExpr()253 IntExpr* DurationExpr() override {
254 if (duration_expr_ == nullptr) {
255 solver()->SaveValue(reinterpret_cast<void**>(&duration_expr_));
256 duration_expr_ = BuildDurationExpr(this);
257 }
258 return duration_expr_;
259 }
EndExpr()260 IntExpr* EndExpr() override {
261 if (end_expr_ == nullptr) {
262 solver()->SaveValue(reinterpret_cast<void**>(&end_expr_));
263 end_expr_ = BuildEndExpr(this);
264 }
265 return end_expr_;
266 }
PerformedExpr()267 IntExpr* PerformedExpr() override { return solver()->MakeIntConst(1); }
SafeStartExpr(int64_t unperformed_value)268 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
269 return StartExpr();
270 }
SafeDurationExpr(int64_t unperformed_value)271 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
272 return DurationExpr();
273 }
SafeEndExpr(int64_t unperformed_value)274 IntExpr* SafeEndExpr(int64_t unperformed_value) override { return EndExpr(); }
275
276 protected:
underlying() const277 IntervalVar* const underlying() const { return t_; }
MayUnderlyingBePerformed() const278 bool MayUnderlyingBePerformed() const {
279 return underlying()->MayBePerformed();
280 }
281
282 private:
283 IntervalVar* const t_;
284 IntExpr* start_expr_;
285 IntExpr* duration_expr_;
286 IntExpr* end_expr_;
287 DISALLOW_COPY_AND_ASSIGN(AlwaysPerformedIntervalVarWrapper);
288 };
289
290 // An interval variable that wraps around an underlying one, relaxing the max
291 // start and end. Relaxing means making unbounded when optional.
292 //
293 // More precisely, such an interval variable behaves as follows:
294 // * When the underlying must be performed, this interval variable behaves
295 // exactly as the underlying;
296 // * When the underlying may or may not be performed, this interval variable
297 // behaves like the underlying, except that it is unbounded on the max side;
298 // * When the underlying cannot be performed, this interval variable is of
299 // duration 0 and must be performed in an interval unbounded on both sides.
300 //
301 // This class is very useful to implement propagators that may only modify
302 // the start min or end min.
303 class IntervalVarRelaxedMax : public AlwaysPerformedIntervalVarWrapper {
304 public:
IntervalVarRelaxedMax(IntervalVar * const t)305 explicit IntervalVarRelaxedMax(IntervalVar* const t)
306 : AlwaysPerformedIntervalVarWrapper(t) {}
~IntervalVarRelaxedMax()307 ~IntervalVarRelaxedMax() override {}
StartMax() const308 int64_t StartMax() const override {
309 // It matters to use DurationMin() and not underlying()->DurationMin() here.
310 return underlying()->MustBePerformed() ? underlying()->StartMax()
311 : (kMaxValidValue - DurationMin());
312 }
SetStartMax(int64_t m)313 void SetStartMax(int64_t m) override {
314 LOG(FATAL)
315 << "Calling SetStartMax on a IntervalVarRelaxedMax is not supported, "
316 << "as it seems there is no legitimate use case.";
317 }
EndMax() const318 int64_t EndMax() const override {
319 return underlying()->MustBePerformed() ? underlying()->EndMax()
320 : kMaxValidValue;
321 }
SetEndMax(int64_t m)322 void SetEndMax(int64_t m) override {
323 LOG(FATAL)
324 << "Calling SetEndMax on a IntervalVarRelaxedMax is not supported, "
325 << "as it seems there is no legitimate use case.";
326 }
327
Accept(ModelVisitor * const visitor) const328 void Accept(ModelVisitor* const visitor) const override {
329 visitor->VisitIntervalVariable(this, ModelVisitor::kRelaxedMaxOperation, 0,
330 underlying());
331 }
332
DebugString() const333 std::string DebugString() const override {
334 return absl::StrFormat("IntervalVarRelaxedMax(%s)",
335 underlying()->DebugString());
336 }
337 };
338
339 // An interval variable that wraps around an underlying one, relaxing the min
340 // start and end. Relaxing means making unbounded when optional.
341 //
342 // More precisely, such an interval variable behaves as follows:
343 // * When the underlying must be performed, this interval variable behaves
344 // exactly as the underlying;
345 // * When the underlying may or may not be performed, this interval variable
346 // behaves like the underlying, except that it is unbounded on the min side;
347 // * When the underlying cannot be performed, this interval variable is of
348 // duration 0 and must be performed in an interval unbounded on both sides.
349 //
350
351 // This class is very useful to implement propagators that may only modify
352 // the start max or end max.
353 class IntervalVarRelaxedMin : public AlwaysPerformedIntervalVarWrapper {
354 public:
IntervalVarRelaxedMin(IntervalVar * const t)355 explicit IntervalVarRelaxedMin(IntervalVar* const t)
356 : AlwaysPerformedIntervalVarWrapper(t) {}
~IntervalVarRelaxedMin()357 ~IntervalVarRelaxedMin() override {}
StartMin() const358 int64_t StartMin() const override {
359 return underlying()->MustBePerformed() ? underlying()->StartMin()
360 : kMinValidValue;
361 }
SetStartMin(int64_t m)362 void SetStartMin(int64_t m) override {
363 LOG(FATAL)
364 << "Calling SetStartMin on a IntervalVarRelaxedMin is not supported, "
365 << "as it seems there is no legitimate use case.";
366 }
EndMin() const367 int64_t EndMin() const override {
368 // It matters to use DurationMin() and not underlying()->DurationMin() here.
369 return underlying()->MustBePerformed() ? underlying()->EndMin()
370 : (kMinValidValue + DurationMin());
371 }
SetEndMin(int64_t m)372 void SetEndMin(int64_t m) override {
373 LOG(FATAL)
374 << "Calling SetEndMin on a IntervalVarRelaxedMin is not supported, "
375 << "as it seems there is no legitimate use case.";
376 }
377
Accept(ModelVisitor * const visitor) const378 void Accept(ModelVisitor* const visitor) const override {
379 visitor->VisitIntervalVariable(this, ModelVisitor::kRelaxedMinOperation, 0,
380 underlying());
381 }
382
DebugString() const383 std::string DebugString() const override {
384 return absl::StrFormat("IntervalVarRelaxedMin(%s)",
385 underlying()->DebugString());
386 }
387 };
388
389 // ----- BaseIntervalVar -----
390
391 class BaseIntervalVar : public IntervalVar {
392 public:
393 class Handler : public Demon {
394 public:
Handler(BaseIntervalVar * const var)395 explicit Handler(BaseIntervalVar* const var) : var_(var) {}
~Handler()396 ~Handler() override {}
Run(Solver * const s)397 void Run(Solver* const s) override { var_->Process(); }
priority() const398 Solver::DemonPriority priority() const override {
399 return Solver::VAR_PRIORITY;
400 }
DebugString() const401 std::string DebugString() const override {
402 return absl::StrFormat("Handler(%s)", var_->DebugString());
403 }
404
405 private:
406 BaseIntervalVar* const var_;
407 };
408
BaseIntervalVar(Solver * const s,const std::string & name)409 BaseIntervalVar(Solver* const s, const std::string& name)
410 : IntervalVar(s, name),
411 in_process_(false),
412 handler_(this),
413 cleaner_([this](Solver* s) { CleanInProcess(); }) {}
414
~BaseIntervalVar()415 ~BaseIntervalVar() override {}
416
417 virtual void Process() = 0;
418
419 virtual void Push() = 0;
420
CleanInProcess()421 void CleanInProcess() { in_process_ = false; }
422
BaseName() const423 std::string BaseName() const override { return "IntervalVar"; }
424
InProcess() const425 bool InProcess() const { return in_process_; }
426
427 protected:
428 bool in_process_;
429 Handler handler_;
430 Solver::Action cleaner_;
431 };
432
433 class RangeVar : public IntExpr {
434 public:
RangeVar(Solver * const s,BaseIntervalVar * var,int64_t mi,int64_t ma)435 RangeVar(Solver* const s, BaseIntervalVar* var, int64_t mi, int64_t ma)
436 : IntExpr(s),
437 min_(mi),
438 max_(ma),
439 var_(var),
440 postponed_min_(mi),
441 postponed_max_(ma),
442 previous_min_(mi),
443 previous_max_(ma),
444 cast_var_(nullptr) {}
445
~RangeVar()446 ~RangeVar() override {}
447
Bound() const448 bool Bound() const override { return min_.Value() == max_.Value(); }
449
Min() const450 int64_t Min() const override { return min_.Value(); }
451
Max() const452 int64_t Max() const override { return max_.Value(); }
453
SetMin(int64_t m)454 void SetMin(int64_t m) override {
455 // No Op.
456 if (m <= min_.Value()) {
457 return;
458 }
459 // Inconsistent value.
460 if (m > max_.Value()) {
461 var_->SetPerformed(false);
462 return;
463 }
464 if (var_->InProcess()) {
465 // In process, postpone modifications.
466 if (m > postponed_max_) {
467 var_->SetPerformed(false);
468 }
469 if (m > postponed_min_) {
470 postponed_min_ = m;
471 }
472 } else {
473 // Not in process.
474 SyncPreviousBounds();
475 min_.SetValue(solver(), m);
476 var_->Push();
477 }
478 }
479
OldMin() const480 int64_t OldMin() const {
481 DCHECK(var_->InProcess());
482 return previous_min_;
483 }
484
SetMax(int64_t m)485 void SetMax(int64_t m) override {
486 if (m >= max_.Value()) {
487 return;
488 }
489 if (m < min_.Value()) {
490 var_->SetPerformed(false);
491 return;
492 }
493 if (var_->InProcess()) {
494 // In process, postpone modifications.
495 if (m < postponed_min_) {
496 var_->SetPerformed(false);
497 }
498 if (m < postponed_max_) {
499 postponed_max_ = m;
500 }
501 } else {
502 // Not in process.
503 SyncPreviousBounds();
504 max_.SetValue(solver(), m);
505 var_->Push();
506 }
507 }
508
OldMax() const509 int64_t OldMax() const { return previous_min_; }
510
SetRange(int64_t mi,int64_t ma)511 void SetRange(int64_t mi, int64_t ma) override {
512 if (mi <= min_.Value() && ma >= max_.Value()) {
513 // No Op.
514 return;
515 }
516 if (mi > max_.Value() || ma < min_.Value() || mi > ma) {
517 var_->SetPerformed(false);
518 }
519 if (var_->InProcess()) {
520 if (mi > postponed_max_ || ma < postponed_min_) {
521 var_->SetPerformed(false);
522 }
523 if (mi > postponed_min_) {
524 postponed_min_ = mi;
525 }
526 if (ma < postponed_max_) {
527 postponed_max_ = ma;
528 }
529 } else {
530 // Not in process.
531 SyncPreviousBounds();
532 if (mi > min_.Value()) {
533 min_.SetValue(solver(), mi);
534 }
535 if (ma < max_.Value()) {
536 max_.SetValue(solver(), ma);
537 }
538 var_->Push();
539 }
540 }
541
WhenRange(Demon * const demon)542 void WhenRange(Demon* const demon) override {
543 if (!Bound()) {
544 if (demon->priority() == Solver::DELAYED_PRIORITY) {
545 delayed_range_demons_.PushIfNotTop(solver(),
546 solver()->RegisterDemon(demon));
547 } else {
548 range_demons_.PushIfNotTop(solver(), solver()->RegisterDemon(demon));
549 }
550 }
551 }
552
WhenBound(Demon * const demon)553 virtual void WhenBound(Demon* const demon) {
554 if (!Bound()) {
555 if (demon->priority() == Solver::DELAYED_PRIORITY) {
556 delayed_bound_demons_.PushIfNotTop(solver(),
557 solver()->RegisterDemon(demon));
558 } else {
559 bound_demons_.PushIfNotTop(solver(), solver()->RegisterDemon(demon));
560 }
561 }
562 }
563
UpdatePostponedBounds()564 void UpdatePostponedBounds() {
565 postponed_min_ = min_.Value();
566 postponed_max_ = max_.Value();
567 }
568
ProcessDemons()569 void ProcessDemons() {
570 if (Bound()) {
571 ExecuteAll(bound_demons_);
572 EnqueueAll(delayed_bound_demons_);
573 }
574 if (min_.Value() != previous_min_ || max_.Value() != previous_max_) {
575 ExecuteAll(range_demons_);
576 EnqueueAll(delayed_range_demons_);
577 }
578 }
579
UpdatePreviousBounds()580 void UpdatePreviousBounds() {
581 previous_min_ = min_.Value();
582 previous_max_ = max_.Value();
583 }
584
585 // TODO(user): Remove this interval field enum.
ApplyPostponedBounds(IntervalField which)586 void ApplyPostponedBounds(IntervalField which) {
587 if (min_.Value() < postponed_min_ || max_.Value() > postponed_max_) {
588 switch (which) {
589 case START:
590 var_->SetStartRange(std::max(postponed_min_, min_.Value()),
591 std::min(postponed_max_, max_.Value()));
592 break;
593 case DURATION:
594 var_->SetDurationRange(std::max(postponed_min_, min_.Value()),
595 std::min(postponed_max_, max_.Value()));
596 break;
597 case END:
598 var_->SetEndRange(std::max(postponed_min_, min_.Value()),
599 std::min(postponed_max_, max_.Value()));
600 break;
601 }
602 }
603 }
604
Var()605 IntVar* Var() override {
606 if (cast_var_ == nullptr) {
607 solver()->SaveValue(reinterpret_cast<void**>(&cast_var_));
608 cast_var_ = solver()->MakeIntVar(min_.Value(), max_.Value());
609 LinkVarExpr(solver(), this, cast_var_);
610 }
611 return cast_var_;
612 }
613
DebugString() const614 std::string DebugString() const override {
615 std::string out = absl::StrCat(min_.Value());
616 if (!Bound()) {
617 absl::StrAppendFormat(&out, " .. %d", max_.Value());
618 }
619 return out;
620 }
621
622 private:
623 // The previous bounds are maintained lazily and non reversibly.
624 // When going down in the search tree, the modifications are
625 // monotonic, thus SyncPreviousBounds is a no-op because they are
626 // correctly updated at the end of the ProcessDemons() call. After
627 // a fail, if they are inconsistent, then they will be outside the
628 // current interval, thus this check.
SyncPreviousBounds()629 void SyncPreviousBounds() {
630 if (previous_min_ > min_.Value()) {
631 previous_min_ = min_.Value();
632 }
633 if (previous_max_ < max_.Value()) {
634 previous_max_ = max_.Value();
635 }
636 }
637
638 // The current reversible bounds of the interval.
639 NumericalRev<int64_t> min_;
640 NumericalRev<int64_t> max_;
641 BaseIntervalVar* const var_;
642 // When in process, the modifications are postponed and stored in
643 // these 2 fields.
644 int64_t postponed_min_;
645 int64_t postponed_max_;
646 // The previous bounds stores the bounds since the last time
647 // ProcessDemons() was run. These are maintained lazily.
648 int64_t previous_min_;
649 int64_t previous_max_;
650 // Demons attached to the 'bound' event (min == max).
651 SimpleRevFIFO<Demon*> bound_demons_;
652 SimpleRevFIFO<Demon*> delayed_bound_demons_;
653 // Demons attached to a modification of bounds.
654 SimpleRevFIFO<Demon*> range_demons_;
655 SimpleRevFIFO<Demon*> delayed_range_demons_;
656 IntVar* cast_var_;
657 }; // class RangeVar
658
659 // ----- PerformedVar -----
660
661 class PerformedVar : public BooleanVar {
662 public:
663 // Optional = true -> var = [0..1], Optional = false -> var = [1].
PerformedVar(Solver * const s,BaseIntervalVar * const var,bool optional)664 PerformedVar(Solver* const s, BaseIntervalVar* const var, bool optional)
665 : BooleanVar(s, ""),
666 var_(var),
667 previous_value_(optional ? kUnboundBooleanVarValue : 1),
668 postponed_value_(optional ? kUnboundBooleanVarValue : 1) {
669 if (!optional) {
670 value_ = 1;
671 }
672 }
673 // var = [0] (always unperformed).
PerformedVar(Solver * const s,BaseIntervalVar * var)674 PerformedVar(Solver* const s, BaseIntervalVar* var)
675 : BooleanVar(s, ""), var_(var), previous_value_(0), postponed_value_(0) {
676 value_ = 1;
677 }
678
~PerformedVar()679 ~PerformedVar() override {}
680
SetValue(int64_t v)681 void SetValue(int64_t v) override {
682 if ((v & 0xfffffffffffffffe) != 0 || // Not 0 or 1.
683 (value_ != kUnboundBooleanVarValue && v != value_)) {
684 solver()->Fail();
685 }
686 if (var_->InProcess()) {
687 if (postponed_value_ != kUnboundBooleanVarValue &&
688 v != postponed_value_) { // Fail early.
689 solver()->Fail();
690 } else {
691 postponed_value_ = v;
692 }
693 } else if (value_ == kUnboundBooleanVarValue) {
694 previous_value_ = kUnboundBooleanVarValue;
695 InternalSaveBooleanVarValue(solver(), this);
696 value_ = static_cast<int>(v);
697 var_->Push();
698 }
699 }
700
OldMin() const701 int64_t OldMin() const override { return previous_value_ == 1; }
702
OldMax() const703 int64_t OldMax() const override { return previous_value_ != 0; }
704
RestoreValue()705 void RestoreValue() override {
706 previous_value_ = kUnboundBooleanVarValue;
707 value_ = kUnboundBooleanVarValue;
708 postponed_value_ = kUnboundBooleanVarValue;
709 }
710
Process()711 void Process() {
712 if (previous_value_ != value_) {
713 ExecuteAll(bound_demons_);
714 EnqueueAll(delayed_bound_demons_);
715 }
716 }
717
UpdatePostponedValue()718 void UpdatePostponedValue() { postponed_value_ = value_; }
719
UpdatePreviousValueAndApplyPostponedValue()720 void UpdatePreviousValueAndApplyPostponedValue() {
721 previous_value_ = value_;
722 if (value_ != postponed_value_) {
723 DCHECK_NE(kUnboundBooleanVarValue, postponed_value_);
724 SetValue(postponed_value_);
725 }
726 }
727
DebugString() const728 std::string DebugString() const override {
729 switch (value_) {
730 case 0:
731 return "false";
732 case 1:
733 return "true";
734 default:
735 return "undecided";
736 }
737 }
738
739 private:
740 BaseIntervalVar* const var_;
741 int previous_value_;
742 int postponed_value_;
743 };
744
745 // ----- FixedDurationIntervalVar -----
746
747 class FixedDurationIntervalVar : public BaseIntervalVar {
748 public:
749 FixedDurationIntervalVar(Solver* const s, int64_t start_min,
750 int64_t start_max, int64_t duration, bool optional,
751 const std::string& name);
752 // Unperformed interval.
753 FixedDurationIntervalVar(Solver* const s, const std::string& name);
~FixedDurationIntervalVar()754 ~FixedDurationIntervalVar() override {}
755
756 int64_t StartMin() const override;
757 int64_t StartMax() const override;
758 void SetStartMin(int64_t m) override;
759 void SetStartMax(int64_t m) override;
760 void SetStartRange(int64_t mi, int64_t ma) override;
OldStartMin() const761 int64_t OldStartMin() const override { return start_.OldMin(); }
OldStartMax() const762 int64_t OldStartMax() const override { return start_.OldMax(); }
WhenStartRange(Demon * const d)763 void WhenStartRange(Demon* const d) override {
764 if (performed_.Max() == 1) {
765 start_.WhenRange(d);
766 }
767 }
WhenStartBound(Demon * const d)768 void WhenStartBound(Demon* const d) override {
769 if (performed_.Max() == 1) {
770 start_.WhenBound(d);
771 }
772 }
773
774 int64_t DurationMin() const override;
775 int64_t DurationMax() const override;
776 void SetDurationMin(int64_t m) override;
777 void SetDurationMax(int64_t m) override;
778 void SetDurationRange(int64_t mi, int64_t ma) override;
OldDurationMin() const779 int64_t OldDurationMin() const override { return duration_; }
OldDurationMax() const780 int64_t OldDurationMax() const override { return duration_; }
WhenDurationRange(Demon * const d)781 void WhenDurationRange(Demon* const d) override {}
WhenDurationBound(Demon * const d)782 void WhenDurationBound(Demon* const d) override {}
783
784 int64_t EndMin() const override;
785 int64_t EndMax() const override;
786 void SetEndMin(int64_t m) override;
787 void SetEndMax(int64_t m) override;
788 void SetEndRange(int64_t mi, int64_t ma) override;
OldEndMin() const789 int64_t OldEndMin() const override {
790 return CapAdd(OldStartMin(), duration_);
791 }
OldEndMax() const792 int64_t OldEndMax() const override {
793 return CapAdd(OldStartMax(), duration_);
794 }
WhenEndRange(Demon * const d)795 void WhenEndRange(Demon* const d) override { WhenStartRange(d); }
WhenEndBound(Demon * const d)796 void WhenEndBound(Demon* const d) override { WhenStartBound(d); }
797
798 bool MustBePerformed() const override;
799 bool MayBePerformed() const override;
800 void SetPerformed(bool val) override;
WasPerformedBound() const801 bool WasPerformedBound() const override {
802 return performed_.OldMin() == performed_.OldMax();
803 }
WhenPerformedBound(Demon * const d)804 void WhenPerformedBound(Demon* const d) override { performed_.WhenBound(d); }
805 void Process() override;
806 std::string DebugString() const override;
807
Accept(ModelVisitor * const visitor) const808 void Accept(ModelVisitor* const visitor) const override {
809 visitor->VisitIntervalVariable(this, "", 0, NullInterval());
810 }
811
StartExpr()812 IntExpr* StartExpr() override { return &start_; }
DurationExpr()813 IntExpr* DurationExpr() override { return solver()->MakeIntConst(duration_); }
EndExpr()814 IntExpr* EndExpr() override {
815 return solver()->MakeSum(StartExpr(), duration_);
816 }
PerformedExpr()817 IntExpr* PerformedExpr() override { return &performed_; }
SafeStartExpr(int64_t unperformed_value)818 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
819 return BuildSafeStartExpr(this, unperformed_value);
820 }
SafeDurationExpr(int64_t unperformed_value)821 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
822 return BuildSafeDurationExpr(this, unperformed_value);
823 }
SafeEndExpr(int64_t unperformed_value)824 IntExpr* SafeEndExpr(int64_t unperformed_value) override {
825 return BuildSafeEndExpr(this, unperformed_value);
826 }
827
828 void Push() override;
829
830 private:
831 RangeVar start_;
832 int64_t duration_;
833 PerformedVar performed_;
834 };
835
FixedDurationIntervalVar(Solver * const s,int64_t start_min,int64_t start_max,int64_t duration,bool optional,const std::string & name)836 FixedDurationIntervalVar::FixedDurationIntervalVar(
837 Solver* const s, int64_t start_min, int64_t start_max, int64_t duration,
838 bool optional, const std::string& name)
839 : BaseIntervalVar(s, name),
840 start_(s, this, start_min, start_max),
841 duration_(duration),
842 performed_(s, this, optional) {}
843
FixedDurationIntervalVar(Solver * const s,const std::string & name)844 FixedDurationIntervalVar::FixedDurationIntervalVar(Solver* const s,
845 const std::string& name)
846 : BaseIntervalVar(s, name),
847 start_(s, this, 0, 0),
848 duration_(0),
849 performed_(s, this) {}
850
Process()851 void FixedDurationIntervalVar::Process() {
852 CHECK(!in_process_);
853 in_process_ = true;
854 start_.UpdatePostponedBounds();
855 performed_.UpdatePostponedValue();
856 set_action_on_fail(cleaner_);
857 if (performed_.Max() == 1) {
858 start_.ProcessDemons();
859 }
860 performed_.Process();
861 reset_action_on_fail();
862 CleanInProcess();
863 start_.UpdatePreviousBounds();
864 start_.ApplyPostponedBounds(START);
865 performed_.UpdatePreviousValueAndApplyPostponedValue();
866 }
867
StartMin() const868 int64_t FixedDurationIntervalVar::StartMin() const {
869 CHECK_EQ(performed_.Max(), 1);
870 return start_.Min();
871 }
872
StartMax() const873 int64_t FixedDurationIntervalVar::StartMax() const {
874 CHECK_EQ(performed_.Max(), 1);
875 return start_.Max();
876 }
877
SetStartMin(int64_t m)878 void FixedDurationIntervalVar::SetStartMin(int64_t m) {
879 if (performed_.Max() == 1) {
880 start_.SetMin(m);
881 }
882 }
883
SetStartMax(int64_t m)884 void FixedDurationIntervalVar::SetStartMax(int64_t m) {
885 if (performed_.Max() == 1) {
886 start_.SetMax(m);
887 }
888 }
889
SetStartRange(int64_t mi,int64_t ma)890 void FixedDurationIntervalVar::SetStartRange(int64_t mi, int64_t ma) {
891 if (performed_.Max() == 1) {
892 start_.SetRange(mi, ma);
893 }
894 }
895
DurationMin() const896 int64_t FixedDurationIntervalVar::DurationMin() const {
897 CHECK_EQ(performed_.Max(), 1);
898 return duration_;
899 }
900
DurationMax() const901 int64_t FixedDurationIntervalVar::DurationMax() const {
902 CHECK_EQ(performed_.Max(), 1);
903 return duration_;
904 }
905
SetDurationMin(int64_t m)906 void FixedDurationIntervalVar::SetDurationMin(int64_t m) {
907 if (m > duration_) {
908 SetPerformed(false);
909 }
910 }
911
SetDurationMax(int64_t m)912 void FixedDurationIntervalVar::SetDurationMax(int64_t m) {
913 if (m < duration_) {
914 SetPerformed(false);
915 }
916 }
917
SetDurationRange(int64_t mi,int64_t ma)918 void FixedDurationIntervalVar::SetDurationRange(int64_t mi, int64_t ma) {
919 if (mi > duration_ || ma < duration_ || mi > ma) {
920 SetPerformed(false);
921 }
922 }
923
EndMin() const924 int64_t FixedDurationIntervalVar::EndMin() const {
925 CHECK_EQ(performed_.Max(), 1);
926 return start_.Min() + duration_;
927 }
928
EndMax() const929 int64_t FixedDurationIntervalVar::EndMax() const {
930 CHECK_EQ(performed_.Max(), 1);
931 return CapAdd(start_.Max(), duration_);
932 }
933
SetEndMin(int64_t m)934 void FixedDurationIntervalVar::SetEndMin(int64_t m) {
935 SetStartMin(CapSub(m, duration_));
936 }
937
SetEndMax(int64_t m)938 void FixedDurationIntervalVar::SetEndMax(int64_t m) {
939 SetStartMax(CapSub(m, duration_));
940 }
941
SetEndRange(int64_t mi,int64_t ma)942 void FixedDurationIntervalVar::SetEndRange(int64_t mi, int64_t ma) {
943 SetStartRange(CapSub(mi, duration_), CapSub(ma, duration_));
944 }
945
MustBePerformed() const946 bool FixedDurationIntervalVar::MustBePerformed() const {
947 return (performed_.Min() == 1);
948 }
949
MayBePerformed() const950 bool FixedDurationIntervalVar::MayBePerformed() const {
951 return (performed_.Max() == 1);
952 }
953
SetPerformed(bool val)954 void FixedDurationIntervalVar::SetPerformed(bool val) {
955 performed_.SetValue(val);
956 }
957
Push()958 void FixedDurationIntervalVar::Push() {
959 DCHECK(!in_process_);
960 EnqueueVar(&handler_);
961 DCHECK(!in_process_);
962 }
963
DebugString() const964 std::string FixedDurationIntervalVar::DebugString() const {
965 const std::string& var_name = name();
966 if (performed_.Max() == 0) {
967 if (!var_name.empty()) {
968 return absl::StrFormat("%s(performed = false)", var_name);
969 } else {
970 return "IntervalVar(performed = false)";
971 }
972 } else {
973 std::string out;
974 if (!var_name.empty()) {
975 out = var_name + "(start = ";
976 } else {
977 out = "IntervalVar(start = ";
978 }
979 absl::StrAppendFormat(&out, "%s, duration = %d, performed = %s)",
980 start_.DebugString(), duration_,
981 performed_.DebugString());
982 return out;
983 }
984 }
985
986 // ----- FixedDurationPerformedIntervalVar -----
987
988 class FixedDurationPerformedIntervalVar : public BaseIntervalVar {
989 public:
990 FixedDurationPerformedIntervalVar(Solver* const s, int64_t start_min,
991 int64_t start_max, int64_t duration,
992 const std::string& name);
993 // Unperformed interval.
994 FixedDurationPerformedIntervalVar(Solver* const s, const std::string& name);
~FixedDurationPerformedIntervalVar()995 ~FixedDurationPerformedIntervalVar() override {}
996
997 int64_t StartMin() const override;
998 int64_t StartMax() const override;
999 void SetStartMin(int64_t m) override;
1000 void SetStartMax(int64_t m) override;
1001 void SetStartRange(int64_t mi, int64_t ma) override;
OldStartMin() const1002 int64_t OldStartMin() const override { return start_.OldMin(); }
OldStartMax() const1003 int64_t OldStartMax() const override { return start_.OldMax(); }
WhenStartRange(Demon * const d)1004 void WhenStartRange(Demon* const d) override { start_.WhenRange(d); }
WhenStartBound(Demon * const d)1005 void WhenStartBound(Demon* const d) override { start_.WhenBound(d); }
1006
1007 int64_t DurationMin() const override;
1008 int64_t DurationMax() const override;
1009 void SetDurationMin(int64_t m) override;
1010 void SetDurationMax(int64_t m) override;
1011 void SetDurationRange(int64_t mi, int64_t ma) override;
OldDurationMin() const1012 int64_t OldDurationMin() const override { return duration_; }
OldDurationMax() const1013 int64_t OldDurationMax() const override { return duration_; }
WhenDurationRange(Demon * const d)1014 void WhenDurationRange(Demon* const d) override {}
WhenDurationBound(Demon * const d)1015 void WhenDurationBound(Demon* const d) override {}
1016
1017 int64_t EndMin() const override;
1018 int64_t EndMax() const override;
1019 void SetEndMin(int64_t m) override;
1020 void SetEndMax(int64_t m) override;
1021 void SetEndRange(int64_t mi, int64_t ma) override;
OldEndMin() const1022 int64_t OldEndMin() const override {
1023 return CapAdd(OldStartMin(), duration_);
1024 }
OldEndMax() const1025 int64_t OldEndMax() const override {
1026 return CapAdd(OldStartMax(), duration_);
1027 }
WhenEndRange(Demon * const d)1028 void WhenEndRange(Demon* const d) override { WhenStartRange(d); }
WhenEndBound(Demon * const d)1029 void WhenEndBound(Demon* const d) override { WhenEndRange(d); }
1030
1031 bool MustBePerformed() const override;
1032 bool MayBePerformed() const override;
1033 void SetPerformed(bool val) override;
WasPerformedBound() const1034 bool WasPerformedBound() const override { return true; }
WhenPerformedBound(Demon * const d)1035 void WhenPerformedBound(Demon* const d) override {}
1036 void Process() override;
1037 std::string DebugString() const override;
1038
Accept(ModelVisitor * const visitor) const1039 void Accept(ModelVisitor* const visitor) const override {
1040 visitor->VisitIntervalVariable(this, "", 0, NullInterval());
1041 }
1042
StartExpr()1043 IntExpr* StartExpr() override { return &start_; }
DurationExpr()1044 IntExpr* DurationExpr() override { return solver()->MakeIntConst(duration_); }
EndExpr()1045 IntExpr* EndExpr() override {
1046 return solver()->MakeSum(StartExpr(), duration_);
1047 }
PerformedExpr()1048 IntExpr* PerformedExpr() override { return solver()->MakeIntConst(1); }
SafeStartExpr(int64_t unperformed_value)1049 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
1050 return StartExpr();
1051 }
SafeDurationExpr(int64_t unperformed_value)1052 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
1053 return DurationExpr();
1054 }
SafeEndExpr(int64_t unperformed_value)1055 IntExpr* SafeEndExpr(int64_t unperformed_value) override { return EndExpr(); }
1056
1057 private:
CheckOldPerformed()1058 void CheckOldPerformed() {}
1059 void Push() override;
1060
1061 RangeVar start_;
1062 int64_t duration_;
1063 };
1064
FixedDurationPerformedIntervalVar(Solver * const s,int64_t start_min,int64_t start_max,int64_t duration,const std::string & name)1065 FixedDurationPerformedIntervalVar::FixedDurationPerformedIntervalVar(
1066 Solver* const s, int64_t start_min, int64_t start_max, int64_t duration,
1067 const std::string& name)
1068 : BaseIntervalVar(s, name),
1069 start_(s, this, start_min, start_max),
1070 duration_(duration) {}
1071
FixedDurationPerformedIntervalVar(Solver * const s,const std::string & name)1072 FixedDurationPerformedIntervalVar::FixedDurationPerformedIntervalVar(
1073 Solver* const s, const std::string& name)
1074 : BaseIntervalVar(s, name), start_(s, this, 0, 0), duration_(0) {}
1075
Process()1076 void FixedDurationPerformedIntervalVar::Process() {
1077 CHECK(!in_process_);
1078 in_process_ = true;
1079 start_.UpdatePostponedBounds();
1080 set_action_on_fail(cleaner_);
1081 start_.ProcessDemons();
1082 reset_action_on_fail();
1083 CleanInProcess();
1084 start_.UpdatePreviousBounds();
1085 start_.ApplyPostponedBounds(START);
1086 }
1087
StartMin() const1088 int64_t FixedDurationPerformedIntervalVar::StartMin() const {
1089 return start_.Min();
1090 }
1091
StartMax() const1092 int64_t FixedDurationPerformedIntervalVar::StartMax() const {
1093 return start_.Max();
1094 }
1095
SetStartMin(int64_t m)1096 void FixedDurationPerformedIntervalVar::SetStartMin(int64_t m) {
1097 start_.SetMin(m);
1098 }
1099
SetStartMax(int64_t m)1100 void FixedDurationPerformedIntervalVar::SetStartMax(int64_t m) {
1101 start_.SetMax(m);
1102 }
1103
SetStartRange(int64_t mi,int64_t ma)1104 void FixedDurationPerformedIntervalVar::SetStartRange(int64_t mi, int64_t ma) {
1105 start_.SetRange(mi, ma);
1106 }
1107
DurationMin() const1108 int64_t FixedDurationPerformedIntervalVar::DurationMin() const {
1109 return duration_;
1110 }
1111
DurationMax() const1112 int64_t FixedDurationPerformedIntervalVar::DurationMax() const {
1113 return duration_;
1114 }
1115
SetDurationMin(int64_t m)1116 void FixedDurationPerformedIntervalVar::SetDurationMin(int64_t m) {
1117 if (m > duration_) {
1118 SetPerformed(false);
1119 }
1120 }
1121
SetDurationMax(int64_t m)1122 void FixedDurationPerformedIntervalVar::SetDurationMax(int64_t m) {
1123 if (m < duration_) {
1124 SetPerformed(false);
1125 }
1126 }
EndMin() const1127 int64_t FixedDurationPerformedIntervalVar::EndMin() const {
1128 return CapAdd(start_.Min(), duration_);
1129 }
1130
EndMax() const1131 int64_t FixedDurationPerformedIntervalVar::EndMax() const {
1132 return CapAdd(start_.Max(), duration_);
1133 }
1134
SetEndMin(int64_t m)1135 void FixedDurationPerformedIntervalVar::SetEndMin(int64_t m) {
1136 SetStartMin(CapSub(m, duration_));
1137 }
1138
SetEndMax(int64_t m)1139 void FixedDurationPerformedIntervalVar::SetEndMax(int64_t m) {
1140 SetStartMax(CapSub(m, duration_));
1141 }
1142
SetEndRange(int64_t mi,int64_t ma)1143 void FixedDurationPerformedIntervalVar::SetEndRange(int64_t mi, int64_t ma) {
1144 SetStartRange(CapSub(mi, duration_), CapSub(ma, duration_));
1145 }
1146
SetDurationRange(int64_t mi,int64_t ma)1147 void FixedDurationPerformedIntervalVar::SetDurationRange(int64_t mi,
1148 int64_t ma) {
1149 if (mi > duration_ || ma < duration_ || mi > ma) {
1150 SetPerformed(false);
1151 }
1152 }
1153
MustBePerformed() const1154 bool FixedDurationPerformedIntervalVar::MustBePerformed() const { return true; }
1155
MayBePerformed() const1156 bool FixedDurationPerformedIntervalVar::MayBePerformed() const { return true; }
1157
SetPerformed(bool val)1158 void FixedDurationPerformedIntervalVar::SetPerformed(bool val) {
1159 if (!val) {
1160 solver()->Fail();
1161 }
1162 }
1163
Push()1164 void FixedDurationPerformedIntervalVar::Push() {
1165 DCHECK(!in_process_);
1166 EnqueueVar(&handler_);
1167 DCHECK(!in_process_);
1168 }
1169
DebugString() const1170 std::string FixedDurationPerformedIntervalVar::DebugString() const {
1171 std::string out;
1172 const std::string& var_name = name();
1173 if (!var_name.empty()) {
1174 out = var_name + "(start = ";
1175 } else {
1176 out = "IntervalVar(start = ";
1177 }
1178 absl::StrAppendFormat(&out, "%s, duration = %d, performed = true)",
1179 start_.DebugString(), duration_);
1180 return out;
1181 }
1182
1183 // ----- StartVarPerformedIntervalVar -----
1184
1185 class StartVarPerformedIntervalVar : public IntervalVar {
1186 public:
1187 StartVarPerformedIntervalVar(Solver* const s, IntVar* const var,
1188 int64_t duration, const std::string& name);
~StartVarPerformedIntervalVar()1189 ~StartVarPerformedIntervalVar() override {}
1190
1191 int64_t StartMin() const override;
1192 int64_t StartMax() const override;
1193 void SetStartMin(int64_t m) override;
1194 void SetStartMax(int64_t m) override;
1195 void SetStartRange(int64_t mi, int64_t ma) override;
OldStartMin() const1196 int64_t OldStartMin() const override { return start_var_->OldMin(); }
OldStartMax() const1197 int64_t OldStartMax() const override { return start_var_->OldMax(); }
WhenStartRange(Demon * const d)1198 void WhenStartRange(Demon* const d) override { start_var_->WhenRange(d); }
WhenStartBound(Demon * const d)1199 void WhenStartBound(Demon* const d) override { start_var_->WhenBound(d); }
1200
1201 int64_t DurationMin() const override;
1202 int64_t DurationMax() const override;
1203 void SetDurationMin(int64_t m) override;
1204 void SetDurationMax(int64_t m) override;
1205 void SetDurationRange(int64_t mi, int64_t ma) override;
OldDurationMin() const1206 int64_t OldDurationMin() const override { return duration_; }
OldDurationMax() const1207 int64_t OldDurationMax() const override { return duration_; }
WhenDurationRange(Demon * const d)1208 void WhenDurationRange(Demon* const d) override {}
WhenDurationBound(Demon * const d)1209 void WhenDurationBound(Demon* const d) override {}
1210
1211 int64_t EndMin() const override;
1212 int64_t EndMax() const override;
1213 void SetEndMin(int64_t m) override;
1214 void SetEndMax(int64_t m) override;
1215 void SetEndRange(int64_t mi, int64_t ma) override;
OldEndMin() const1216 int64_t OldEndMin() const override {
1217 return CapAdd(OldStartMin(), duration_);
1218 }
OldEndMax() const1219 int64_t OldEndMax() const override {
1220 return CapAdd(OldStartMax(), duration_);
1221 }
WhenEndRange(Demon * const d)1222 void WhenEndRange(Demon* const d) override { start_var_->WhenRange(d); }
WhenEndBound(Demon * const d)1223 void WhenEndBound(Demon* const d) override { start_var_->WhenBound(d); }
1224
1225 bool MustBePerformed() const override;
1226 bool MayBePerformed() const override;
1227 void SetPerformed(bool val) override;
WasPerformedBound() const1228 bool WasPerformedBound() const override { return true; }
WhenPerformedBound(Demon * const d)1229 void WhenPerformedBound(Demon* const d) override {}
1230 std::string DebugString() const override;
1231
StartExpr()1232 IntExpr* StartExpr() override { return start_var_; }
DurationExpr()1233 IntExpr* DurationExpr() override { return solver()->MakeIntConst(duration_); }
EndExpr()1234 IntExpr* EndExpr() override {
1235 return solver()->MakeSum(start_var_, duration_);
1236 }
PerformedExpr()1237 IntExpr* PerformedExpr() override { return solver()->MakeIntConst(1); }
SafeStartExpr(int64_t unperformed_value)1238 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
1239 return StartExpr();
1240 }
SafeDurationExpr(int64_t unperformed_value)1241 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
1242 return DurationExpr();
1243 }
SafeEndExpr(int64_t unperformed_value)1244 IntExpr* SafeEndExpr(int64_t unperformed_value) override { return EndExpr(); }
1245
Accept(ModelVisitor * const visitor) const1246 void Accept(ModelVisitor* const visitor) const override {
1247 visitor->VisitIntervalVariable(this, "", 0, NullInterval());
1248 }
1249
1250 private:
1251 IntVar* const start_var_;
1252 int64_t duration_;
1253 };
1254
1255 // TODO(user): Take care of overflows.
StartVarPerformedIntervalVar(Solver * const s,IntVar * const var,int64_t duration,const std::string & name)1256 StartVarPerformedIntervalVar::StartVarPerformedIntervalVar(
1257 Solver* const s, IntVar* const var, int64_t duration,
1258 const std::string& name)
1259 : IntervalVar(s, name), start_var_(var), duration_(duration) {}
1260
StartMin() const1261 int64_t StartVarPerformedIntervalVar::StartMin() const {
1262 return start_var_->Min();
1263 }
1264
StartMax() const1265 int64_t StartVarPerformedIntervalVar::StartMax() const {
1266 return start_var_->Max();
1267 }
1268
SetStartMin(int64_t m)1269 void StartVarPerformedIntervalVar::SetStartMin(int64_t m) {
1270 start_var_->SetMin(m);
1271 }
1272
SetStartMax(int64_t m)1273 void StartVarPerformedIntervalVar::SetStartMax(int64_t m) {
1274 start_var_->SetMax(m);
1275 }
1276
SetStartRange(int64_t mi,int64_t ma)1277 void StartVarPerformedIntervalVar::SetStartRange(int64_t mi, int64_t ma) {
1278 start_var_->SetRange(mi, ma);
1279 }
1280
DurationMin() const1281 int64_t StartVarPerformedIntervalVar::DurationMin() const { return duration_; }
1282
DurationMax() const1283 int64_t StartVarPerformedIntervalVar::DurationMax() const { return duration_; }
1284
SetDurationMin(int64_t m)1285 void StartVarPerformedIntervalVar::SetDurationMin(int64_t m) {
1286 if (m > duration_) {
1287 solver()->Fail();
1288 }
1289 }
1290
SetDurationMax(int64_t m)1291 void StartVarPerformedIntervalVar::SetDurationMax(int64_t m) {
1292 if (m < duration_) {
1293 solver()->Fail();
1294 }
1295 }
EndMin() const1296 int64_t StartVarPerformedIntervalVar::EndMin() const {
1297 return start_var_->Min() + duration_;
1298 }
1299
EndMax() const1300 int64_t StartVarPerformedIntervalVar::EndMax() const {
1301 return start_var_->Max() + duration_;
1302 }
1303
SetEndMin(int64_t m)1304 void StartVarPerformedIntervalVar::SetEndMin(int64_t m) {
1305 SetStartMin(CapSub(m, duration_));
1306 }
1307
SetEndMax(int64_t m)1308 void StartVarPerformedIntervalVar::SetEndMax(int64_t m) {
1309 SetStartMax(CapSub(m, duration_));
1310 }
1311
SetEndRange(int64_t mi,int64_t ma)1312 void StartVarPerformedIntervalVar::SetEndRange(int64_t mi, int64_t ma) {
1313 SetStartRange(CapSub(mi, duration_), CapSub(ma, duration_));
1314 }
1315
SetDurationRange(int64_t mi,int64_t ma)1316 void StartVarPerformedIntervalVar::SetDurationRange(int64_t mi, int64_t ma) {
1317 if (mi > duration_ || ma < duration_ || mi > ma) {
1318 solver()->Fail();
1319 }
1320 }
1321
MustBePerformed() const1322 bool StartVarPerformedIntervalVar::MustBePerformed() const { return true; }
1323
MayBePerformed() const1324 bool StartVarPerformedIntervalVar::MayBePerformed() const { return true; }
1325
SetPerformed(bool val)1326 void StartVarPerformedIntervalVar::SetPerformed(bool val) {
1327 if (!val) {
1328 solver()->Fail();
1329 }
1330 }
1331
DebugString() const1332 std::string StartVarPerformedIntervalVar::DebugString() const {
1333 std::string out;
1334 const std::string& var_name = name();
1335 if (!var_name.empty()) {
1336 out = var_name + "(start = ";
1337 } else {
1338 out = "IntervalVar(start = ";
1339 }
1340 absl::StrAppendFormat(&out, "%d", start_var_->Min());
1341 if (!start_var_->Bound()) {
1342 absl::StrAppendFormat(&out, " .. %d", start_var_->Max());
1343 }
1344
1345 absl::StrAppendFormat(&out, ", duration = %d, performed = true)", duration_);
1346 return out;
1347 }
1348
1349 // ----- StartVarIntervalVar -----
1350
1351 class StartVarIntervalVar : public BaseIntervalVar {
1352 public:
1353 StartVarIntervalVar(Solver* const s, IntVar* const start, int64_t duration,
1354 IntVar* const performed, const std::string& name);
~StartVarIntervalVar()1355 ~StartVarIntervalVar() override {}
1356
1357 int64_t StartMin() const override;
1358 int64_t StartMax() const override;
1359 void SetStartMin(int64_t m) override;
1360 void SetStartMax(int64_t m) override;
1361 void SetStartRange(int64_t mi, int64_t ma) override;
OldStartMin() const1362 int64_t OldStartMin() const override { return start_->OldMin(); }
OldStartMax() const1363 int64_t OldStartMax() const override { return start_->OldMax(); }
WhenStartRange(Demon * const d)1364 void WhenStartRange(Demon* const d) override {
1365 if (performed_->Max() == 1) {
1366 start_->WhenRange(d);
1367 }
1368 }
WhenStartBound(Demon * const d)1369 void WhenStartBound(Demon* const d) override {
1370 if (performed_->Max() == 1) {
1371 start_->WhenBound(d);
1372 }
1373 }
1374
1375 int64_t DurationMin() const override;
1376 int64_t DurationMax() const override;
1377 void SetDurationMin(int64_t m) override;
1378 void SetDurationMax(int64_t m) override;
1379 void SetDurationRange(int64_t mi, int64_t ma) override;
OldDurationMin() const1380 int64_t OldDurationMin() const override { return duration_; }
OldDurationMax() const1381 int64_t OldDurationMax() const override { return duration_; }
WhenDurationRange(Demon * const d)1382 void WhenDurationRange(Demon* const d) override {}
WhenDurationBound(Demon * const d)1383 void WhenDurationBound(Demon* const d) override {}
1384
1385 int64_t EndMin() const override;
1386 int64_t EndMax() const override;
1387 void SetEndMin(int64_t m) override;
1388 void SetEndMax(int64_t m) override;
1389 void SetEndRange(int64_t mi, int64_t ma) override;
OldEndMin() const1390 int64_t OldEndMin() const override {
1391 return CapAdd(OldStartMin(), duration_);
1392 }
OldEndMax() const1393 int64_t OldEndMax() const override {
1394 return CapAdd(OldStartMax(), duration_);
1395 }
WhenEndRange(Demon * const d)1396 void WhenEndRange(Demon* const d) override { WhenStartRange(d); }
WhenEndBound(Demon * const d)1397 void WhenEndBound(Demon* const d) override { WhenStartBound(d); }
1398
1399 bool MustBePerformed() const override;
1400 bool MayBePerformed() const override;
1401 void SetPerformed(bool val) override;
WasPerformedBound() const1402 bool WasPerformedBound() const override {
1403 return performed_->OldMin() == performed_->OldMax();
1404 }
WhenPerformedBound(Demon * const d)1405 void WhenPerformedBound(Demon* const d) override { performed_->WhenBound(d); }
1406 std::string DebugString() const override;
1407
Accept(ModelVisitor * const visitor) const1408 void Accept(ModelVisitor* const visitor) const override {
1409 visitor->VisitIntervalVariable(this, "", 0, NullInterval());
1410 }
1411
StartExpr()1412 IntExpr* StartExpr() override { return start_; }
DurationExpr()1413 IntExpr* DurationExpr() override { return solver()->MakeIntConst(duration_); }
EndExpr()1414 IntExpr* EndExpr() override {
1415 return solver()->MakeSum(StartExpr(), duration_);
1416 }
PerformedExpr()1417 IntExpr* PerformedExpr() override { return performed_; }
SafeStartExpr(int64_t unperformed_value)1418 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
1419 return BuildSafeStartExpr(this, unperformed_value);
1420 }
SafeDurationExpr(int64_t unperformed_value)1421 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
1422 return BuildSafeDurationExpr(this, unperformed_value);
1423 }
SafeEndExpr(int64_t unperformed_value)1424 IntExpr* SafeEndExpr(int64_t unperformed_value) override {
1425 return BuildSafeEndExpr(this, unperformed_value);
1426 }
1427
Process()1428 void Process() override { LOG(FATAL) << "Should not be here"; }
1429
Push()1430 void Push() override { LOG(FATAL) << "Should not be here"; }
1431
StoredMin() const1432 int64_t StoredMin() const { return start_min_.Value(); }
StoredMax() const1433 int64_t StoredMax() const { return start_max_.Value(); }
1434
1435 private:
1436 IntVar* const start_;
1437 int64_t duration_;
1438 IntVar* const performed_;
1439 Rev<int64_t> start_min_;
1440 Rev<int64_t> start_max_;
1441 };
1442
StartVarIntervalVar(Solver * const s,IntVar * const start,int64_t duration,IntVar * const performed,const std::string & name)1443 StartVarIntervalVar::StartVarIntervalVar(Solver* const s, IntVar* const start,
1444 int64_t duration,
1445 IntVar* const performed,
1446 const std::string& name)
1447 : BaseIntervalVar(s, name),
1448 start_(start),
1449 duration_(duration),
1450 performed_(performed),
1451 start_min_(start->Min()),
1452 start_max_(start->Max()) {}
1453
StartMin() const1454 int64_t StartVarIntervalVar::StartMin() const {
1455 DCHECK_EQ(performed_->Max(), 1);
1456 return std::max(start_->Min(), start_min_.Value());
1457 }
1458
StartMax() const1459 int64_t StartVarIntervalVar::StartMax() const {
1460 DCHECK_EQ(performed_->Max(), 1);
1461 return std::min(start_->Max(), start_max_.Value());
1462 }
1463
SetStartMin(int64_t m)1464 void StartVarIntervalVar::SetStartMin(int64_t m) {
1465 if (performed_->Min() == 1) {
1466 start_->SetMin(m);
1467 } else {
1468 start_min_.SetValue(solver(), std::max(m, start_min_.Value()));
1469 if (start_min_.Value() > std::min(start_max_.Value(), start_->Max())) {
1470 performed_->SetValue(0);
1471 }
1472 }
1473 }
1474
SetStartMax(int64_t m)1475 void StartVarIntervalVar::SetStartMax(int64_t m) {
1476 if (performed_->Min() == 1) {
1477 start_->SetMax(m);
1478 } else {
1479 start_max_.SetValue(solver(), std::min(m, start_max_.Value()));
1480 if (start_max_.Value() < std::max(start_min_.Value(), start_->Min())) {
1481 performed_->SetValue(0);
1482 }
1483 }
1484 }
1485
SetStartRange(int64_t mi,int64_t ma)1486 void StartVarIntervalVar::SetStartRange(int64_t mi, int64_t ma) {
1487 if (performed_->Min() == 1) {
1488 start_->SetRange(mi, ma);
1489 } else {
1490 start_min_.SetValue(solver(), std::max(mi, start_min_.Value()));
1491 start_max_.SetValue(solver(), std::min(ma, start_max_.Value()));
1492 if (std::max(start_min_.Value(), start_->Min()) >
1493 std::min(start_max_.Value(), start_->Max())) {
1494 performed_->SetValue(0);
1495 }
1496 }
1497 }
1498
DurationMin() const1499 int64_t StartVarIntervalVar::DurationMin() const {
1500 DCHECK_EQ(performed_->Max(), 1);
1501 return duration_;
1502 }
1503
DurationMax() const1504 int64_t StartVarIntervalVar::DurationMax() const {
1505 DCHECK_EQ(performed_->Max(), 1);
1506 return duration_;
1507 }
1508
SetDurationMin(int64_t m)1509 void StartVarIntervalVar::SetDurationMin(int64_t m) {
1510 if (m > duration_) {
1511 SetPerformed(false);
1512 }
1513 }
1514
SetDurationMax(int64_t m)1515 void StartVarIntervalVar::SetDurationMax(int64_t m) {
1516 if (m < duration_) {
1517 SetPerformed(false);
1518 }
1519 }
1520
SetDurationRange(int64_t mi,int64_t ma)1521 void StartVarIntervalVar::SetDurationRange(int64_t mi, int64_t ma) {
1522 if (mi > duration_ || ma < duration_ || mi > ma) {
1523 SetPerformed(false);
1524 }
1525 }
1526
EndMin() const1527 int64_t StartVarIntervalVar::EndMin() const {
1528 DCHECK_EQ(performed_->Max(), 1);
1529 return CapAdd(StartMin(), duration_);
1530 }
1531
EndMax() const1532 int64_t StartVarIntervalVar::EndMax() const {
1533 DCHECK_EQ(performed_->Max(), 1);
1534 return CapAdd(StartMax(), duration_);
1535 }
1536
SetEndMin(int64_t m)1537 void StartVarIntervalVar::SetEndMin(int64_t m) {
1538 SetStartMin(CapSub(m, duration_));
1539 }
1540
SetEndMax(int64_t m)1541 void StartVarIntervalVar::SetEndMax(int64_t m) {
1542 SetStartMax(CapSub(m, duration_));
1543 }
1544
SetEndRange(int64_t mi,int64_t ma)1545 void StartVarIntervalVar::SetEndRange(int64_t mi, int64_t ma) {
1546 SetStartRange(CapSub(mi, duration_), CapSub(ma, duration_));
1547 }
1548
MustBePerformed() const1549 bool StartVarIntervalVar::MustBePerformed() const {
1550 return (performed_->Min() == 1);
1551 }
1552
MayBePerformed() const1553 bool StartVarIntervalVar::MayBePerformed() const {
1554 return (performed_->Max() == 1);
1555 }
1556
SetPerformed(bool val)1557 void StartVarIntervalVar::SetPerformed(bool val) {
1558 const bool was_bound = performed_->Bound();
1559 performed_->SetValue(val);
1560 if (val && !was_bound) {
1561 start_->SetRange(start_min_.Value(), start_max_.Value());
1562 }
1563 }
1564
DebugString() const1565 std::string StartVarIntervalVar::DebugString() const {
1566 const std::string& var_name = name();
1567 if (performed_->Max() == 0) {
1568 if (!var_name.empty()) {
1569 return absl::StrFormat("%s(performed = false)", var_name);
1570 } else {
1571 return "IntervalVar(performed = false)";
1572 }
1573 } else {
1574 std::string out;
1575 if (!var_name.empty()) {
1576 out = var_name + "(start = ";
1577 } else {
1578 out = "IntervalVar(start = ";
1579 }
1580 absl::StrAppendFormat(&out, "%s, duration = %d, performed = %s)",
1581 start_->DebugString(), duration_,
1582 performed_->DebugString());
1583 return out;
1584 }
1585 }
1586
1587 class LinkStartVarIntervalVar : public Constraint {
1588 public:
LinkStartVarIntervalVar(Solver * const solver,StartVarIntervalVar * const interval,IntVar * const start,IntVar * const performed)1589 LinkStartVarIntervalVar(Solver* const solver,
1590 StartVarIntervalVar* const interval,
1591 IntVar* const start, IntVar* const performed)
1592 : Constraint(solver),
1593 interval_(interval),
1594 start_(start),
1595 performed_(performed) {}
1596
~LinkStartVarIntervalVar()1597 ~LinkStartVarIntervalVar() override {}
1598
Post()1599 void Post() override {
1600 Demon* const demon = MakeConstraintDemon0(
1601 solver(), this, &LinkStartVarIntervalVar::PerformedBound,
1602 "PerformedBound");
1603 performed_->WhenBound(demon);
1604 }
1605
InitialPropagate()1606 void InitialPropagate() override {
1607 if (performed_->Bound()) {
1608 PerformedBound();
1609 }
1610 }
1611
PerformedBound()1612 void PerformedBound() {
1613 if (performed_->Min() == 1) {
1614 start_->SetRange(interval_->StoredMin(), interval_->StoredMax());
1615 }
1616 }
1617
1618 private:
1619 StartVarIntervalVar* const interval_;
1620 IntVar* const start_;
1621 IntVar* const performed_;
1622 };
1623
1624 // ----- FixedInterval -----
1625
1626 class FixedInterval : public IntervalVar {
1627 public:
1628 FixedInterval(Solver* const s, int64_t start, int64_t duration,
1629 const std::string& name);
~FixedInterval()1630 ~FixedInterval() override {}
1631
StartMin() const1632 int64_t StartMin() const override { return start_; }
StartMax() const1633 int64_t StartMax() const override { return start_; }
1634 void SetStartMin(int64_t m) override;
1635 void SetStartMax(int64_t m) override;
1636 void SetStartRange(int64_t mi, int64_t ma) override;
OldStartMin() const1637 int64_t OldStartMin() const override { return start_; }
OldStartMax() const1638 int64_t OldStartMax() const override { return start_; }
WhenStartRange(Demon * const d)1639 void WhenStartRange(Demon* const d) override {}
WhenStartBound(Demon * const d)1640 void WhenStartBound(Demon* const d) override {}
1641
DurationMin() const1642 int64_t DurationMin() const override { return duration_; }
DurationMax() const1643 int64_t DurationMax() const override { return duration_; }
1644 void SetDurationMin(int64_t m) override;
1645 void SetDurationMax(int64_t m) override;
1646 void SetDurationRange(int64_t mi, int64_t ma) override;
OldDurationMin() const1647 int64_t OldDurationMin() const override { return duration_; }
OldDurationMax() const1648 int64_t OldDurationMax() const override { return duration_; }
WhenDurationRange(Demon * const d)1649 void WhenDurationRange(Demon* const d) override {}
WhenDurationBound(Demon * const d)1650 void WhenDurationBound(Demon* const d) override {}
1651
EndMin() const1652 int64_t EndMin() const override { return start_ + duration_; }
EndMax() const1653 int64_t EndMax() const override { return start_ + duration_; }
1654 void SetEndMin(int64_t m) override;
1655 void SetEndMax(int64_t m) override;
1656 void SetEndRange(int64_t mi, int64_t ma) override;
OldEndMin() const1657 int64_t OldEndMin() const override { return start_ + duration_; }
OldEndMax() const1658 int64_t OldEndMax() const override { return start_ + duration_; }
WhenEndRange(Demon * const d)1659 void WhenEndRange(Demon* const d) override {}
WhenEndBound(Demon * const d)1660 void WhenEndBound(Demon* const d) override {}
1661
MustBePerformed() const1662 bool MustBePerformed() const override { return true; }
MayBePerformed() const1663 bool MayBePerformed() const override { return true; }
1664 void SetPerformed(bool val) override;
WasPerformedBound() const1665 bool WasPerformedBound() const override { return true; }
WhenPerformedBound(Demon * const d)1666 void WhenPerformedBound(Demon* const d) override {}
1667 std::string DebugString() const override;
1668
Accept(ModelVisitor * const visitor) const1669 void Accept(ModelVisitor* const visitor) const override {
1670 visitor->VisitIntervalVariable(this, "", 0, NullInterval());
1671 }
1672
StartExpr()1673 IntExpr* StartExpr() override { return solver()->MakeIntConst(start_); }
DurationExpr()1674 IntExpr* DurationExpr() override { return solver()->MakeIntConst(duration_); }
EndExpr()1675 IntExpr* EndExpr() override {
1676 return solver()->MakeIntConst(start_ + duration_);
1677 }
PerformedExpr()1678 IntExpr* PerformedExpr() override { return solver()->MakeIntConst(1); }
SafeStartExpr(int64_t unperformed_value)1679 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
1680 return StartExpr();
1681 }
SafeDurationExpr(int64_t unperformed_value)1682 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
1683 return DurationExpr();
1684 }
SafeEndExpr(int64_t unperformed_value)1685 IntExpr* SafeEndExpr(int64_t unperformed_value) override { return EndExpr(); }
1686
1687 private:
1688 const int64_t start_;
1689 const int64_t duration_;
1690 };
1691
FixedInterval(Solver * const s,int64_t start,int64_t duration,const std::string & name)1692 FixedInterval::FixedInterval(Solver* const s, int64_t start, int64_t duration,
1693 const std::string& name)
1694 : IntervalVar(s, name), start_(start), duration_(duration) {}
1695
SetStartMin(int64_t m)1696 void FixedInterval::SetStartMin(int64_t m) {
1697 if (m > start_) {
1698 solver()->Fail();
1699 }
1700 }
1701
SetStartMax(int64_t m)1702 void FixedInterval::SetStartMax(int64_t m) {
1703 if (m < start_) {
1704 solver()->Fail();
1705 }
1706 }
1707
SetStartRange(int64_t mi,int64_t ma)1708 void FixedInterval::SetStartRange(int64_t mi, int64_t ma) {
1709 if (mi > start_ || ma < start_) {
1710 solver()->Fail();
1711 }
1712 }
1713
SetDurationMin(int64_t m)1714 void FixedInterval::SetDurationMin(int64_t m) {
1715 if (m > duration_) {
1716 solver()->Fail();
1717 }
1718 }
1719
SetDurationMax(int64_t m)1720 void FixedInterval::SetDurationMax(int64_t m) {
1721 if (m < duration_) {
1722 solver()->Fail();
1723 }
1724 }
1725
SetEndMin(int64_t m)1726 void FixedInterval::SetEndMin(int64_t m) {
1727 if (m > start_ + duration_) {
1728 solver()->Fail();
1729 }
1730 }
1731
SetEndMax(int64_t m)1732 void FixedInterval::SetEndMax(int64_t m) {
1733 if (m < start_ + duration_) {
1734 solver()->Fail();
1735 }
1736 }
1737
SetEndRange(int64_t mi,int64_t ma)1738 void FixedInterval::SetEndRange(int64_t mi, int64_t ma) {
1739 if (mi > start_ + duration_ || ma < start_ + duration_) {
1740 solver()->Fail();
1741 }
1742 }
1743
SetDurationRange(int64_t mi,int64_t ma)1744 void FixedInterval::SetDurationRange(int64_t mi, int64_t ma) {
1745 if (mi > duration_ || ma < duration_) {
1746 solver()->Fail();
1747 }
1748 }
1749
SetPerformed(bool val)1750 void FixedInterval::SetPerformed(bool val) {
1751 if (!val) {
1752 solver()->Fail();
1753 }
1754 }
1755
DebugString() const1756 std::string FixedInterval::DebugString() const {
1757 std::string out;
1758 const std::string& var_name = name();
1759 if (!var_name.empty()) {
1760 out = var_name + "(start = ";
1761 } else {
1762 out = "IntervalVar(start = ";
1763 }
1764 absl::StrAppendFormat(&out, "%d, duration = %d, performed = true)", start_,
1765 duration_);
1766 return out;
1767 }
1768
1769 // ----- VariableDurationIntervalVar -----
1770
1771 class VariableDurationIntervalVar : public BaseIntervalVar {
1772 public:
VariableDurationIntervalVar(Solver * const s,int64_t start_min,int64_t start_max,int64_t duration_min,int64_t duration_max,int64_t end_min,int64_t end_max,bool optional,const std::string & name)1773 VariableDurationIntervalVar(Solver* const s, int64_t start_min,
1774 int64_t start_max, int64_t duration_min,
1775 int64_t duration_max, int64_t end_min,
1776 int64_t end_max, bool optional,
1777 const std::string& name)
1778 : BaseIntervalVar(s, name),
1779 start_(s, this, std::max(start_min, CapSub(end_min, duration_max)),
1780 std::min(start_max, CapSub(end_max, duration_min))),
1781 duration_(s, this, std::max(duration_min, CapSub(end_min, start_max)),
1782 std::min(duration_max, CapSub(end_max, start_min))),
1783 end_(s, this, std::max(end_min, CapAdd(start_min, duration_min)),
1784 std::min(end_max, CapAdd(start_max, duration_max))),
1785 performed_(s, this, optional) {}
1786
~VariableDurationIntervalVar()1787 ~VariableDurationIntervalVar() override {}
1788
StartMin() const1789 int64_t StartMin() const override {
1790 CHECK_EQ(performed_.Max(), 1);
1791 return start_.Min();
1792 }
1793
StartMax() const1794 int64_t StartMax() const override {
1795 CHECK_EQ(performed_.Max(), 1);
1796 return start_.Max();
1797 }
1798
SetStartMin(int64_t m)1799 void SetStartMin(int64_t m) override {
1800 if (performed_.Max() == 1) {
1801 start_.SetMin(m);
1802 }
1803 }
1804
SetStartMax(int64_t m)1805 void SetStartMax(int64_t m) override {
1806 if (performed_.Max() == 1) {
1807 start_.SetMax(m);
1808 }
1809 }
1810
SetStartRange(int64_t mi,int64_t ma)1811 void SetStartRange(int64_t mi, int64_t ma) override {
1812 if (performed_.Max() == 1) {
1813 start_.SetRange(mi, ma);
1814 }
1815 }
1816
OldStartMin() const1817 int64_t OldStartMin() const override {
1818 CHECK_EQ(performed_.Max(), 1);
1819 CHECK(in_process_);
1820 return start_.OldMin();
1821 }
1822
OldStartMax() const1823 int64_t OldStartMax() const override {
1824 CHECK_EQ(performed_.Max(), 1);
1825 CHECK(in_process_);
1826 return start_.OldMax();
1827 }
1828
WhenStartRange(Demon * const d)1829 void WhenStartRange(Demon* const d) override {
1830 if (performed_.Max() == 1) {
1831 start_.WhenRange(d);
1832 }
1833 }
1834
WhenStartBound(Demon * const d)1835 void WhenStartBound(Demon* const d) override {
1836 if (performed_.Max() == 1) {
1837 start_.WhenBound(d);
1838 }
1839 }
1840
DurationMin() const1841 int64_t DurationMin() const override {
1842 CHECK_EQ(performed_.Max(), 1);
1843 return duration_.Min();
1844 }
1845
DurationMax() const1846 int64_t DurationMax() const override {
1847 CHECK_EQ(performed_.Max(), 1);
1848 return duration_.Max();
1849 }
1850
SetDurationMin(int64_t m)1851 void SetDurationMin(int64_t m) override {
1852 if (performed_.Max() == 1) {
1853 duration_.SetMin(m);
1854 }
1855 }
1856
SetDurationMax(int64_t m)1857 void SetDurationMax(int64_t m) override {
1858 if (performed_.Max() == 1) {
1859 duration_.SetMax(m);
1860 }
1861 }
1862
SetDurationRange(int64_t mi,int64_t ma)1863 void SetDurationRange(int64_t mi, int64_t ma) override {
1864 if (performed_.Max() == 1) {
1865 duration_.SetRange(mi, ma);
1866 }
1867 }
1868
OldDurationMin() const1869 int64_t OldDurationMin() const override {
1870 CHECK_EQ(performed_.Max(), 1);
1871 CHECK(in_process_);
1872 return duration_.OldMin();
1873 }
1874
OldDurationMax() const1875 int64_t OldDurationMax() const override {
1876 CHECK_EQ(performed_.Max(), 1);
1877 CHECK(in_process_);
1878 return duration_.OldMax();
1879 }
1880
WhenDurationRange(Demon * const d)1881 void WhenDurationRange(Demon* const d) override {
1882 if (performed_.Max() == 1) {
1883 duration_.WhenRange(d);
1884 }
1885 }
1886
WhenDurationBound(Demon * const d)1887 void WhenDurationBound(Demon* const d) override {
1888 if (performed_.Max() == 1) {
1889 duration_.WhenBound(d);
1890 }
1891 }
1892
EndMin() const1893 int64_t EndMin() const override {
1894 CHECK_EQ(performed_.Max(), 1);
1895 return end_.Min();
1896 }
1897
EndMax() const1898 int64_t EndMax() const override {
1899 CHECK_EQ(performed_.Max(), 1);
1900 return end_.Max();
1901 }
1902
SetEndMin(int64_t m)1903 void SetEndMin(int64_t m) override {
1904 if (performed_.Max() == 1) {
1905 end_.SetMin(m);
1906 }
1907 }
1908
SetEndMax(int64_t m)1909 void SetEndMax(int64_t m) override {
1910 if (performed_.Max() == 1) {
1911 end_.SetMax(m);
1912 }
1913 }
1914
SetEndRange(int64_t mi,int64_t ma)1915 void SetEndRange(int64_t mi, int64_t ma) override {
1916 if (performed_.Max() == 1) {
1917 end_.SetRange(mi, ma);
1918 }
1919 }
1920
OldEndMin() const1921 int64_t OldEndMin() const override {
1922 CHECK_EQ(performed_.Max(), 1);
1923 DCHECK(in_process_);
1924 return end_.OldMin();
1925 }
1926
OldEndMax() const1927 int64_t OldEndMax() const override {
1928 CHECK_EQ(performed_.Max(), 1);
1929 DCHECK(in_process_);
1930 return end_.OldMax();
1931 }
1932
WhenEndRange(Demon * const d)1933 void WhenEndRange(Demon* const d) override {
1934 if (performed_.Max() == 1) {
1935 end_.WhenRange(d);
1936 }
1937 }
1938
WhenEndBound(Demon * const d)1939 void WhenEndBound(Demon* const d) override {
1940 if (performed_.Max() == 1) {
1941 end_.WhenBound(d);
1942 }
1943 }
1944
MustBePerformed() const1945 bool MustBePerformed() const override { return (performed_.Min() == 1); }
1946
MayBePerformed() const1947 bool MayBePerformed() const override { return (performed_.Max() == 1); }
1948
SetPerformed(bool val)1949 void SetPerformed(bool val) override { performed_.SetValue(val); }
1950
WasPerformedBound() const1951 bool WasPerformedBound() const override {
1952 CHECK(in_process_);
1953 return performed_.OldMin() == performed_.OldMax();
1954 }
1955
WhenPerformedBound(Demon * const d)1956 void WhenPerformedBound(Demon* const d) override { performed_.WhenBound(d); }
1957
Process()1958 void Process() override {
1959 CHECK(!in_process_);
1960 in_process_ = true;
1961 start_.UpdatePostponedBounds();
1962 duration_.UpdatePostponedBounds();
1963 end_.UpdatePostponedBounds();
1964 performed_.UpdatePostponedValue();
1965 set_action_on_fail(cleaner_);
1966 if (performed_.Max() == 1) {
1967 start_.ProcessDemons();
1968 duration_.ProcessDemons();
1969 end_.ProcessDemons();
1970 }
1971 performed_.Process();
1972 reset_action_on_fail();
1973 CleanInProcess();
1974 // TODO(user): Replace this enum by a callback.
1975 start_.UpdatePreviousBounds();
1976 start_.ApplyPostponedBounds(START);
1977 duration_.UpdatePreviousBounds();
1978 duration_.ApplyPostponedBounds(DURATION);
1979 end_.UpdatePreviousBounds();
1980 end_.ApplyPostponedBounds(END);
1981 performed_.UpdatePreviousValueAndApplyPostponedValue();
1982 }
1983
DebugString() const1984 std::string DebugString() const override {
1985 const std::string& var_name = name();
1986 if (performed_.Max() != 1) {
1987 if (!var_name.empty()) {
1988 return absl::StrFormat("%s(performed = false)", var_name);
1989 } else {
1990 return "IntervalVar(performed = false)";
1991 }
1992 } else {
1993 std::string out;
1994 if (!var_name.empty()) {
1995 out = var_name + "(start = ";
1996 } else {
1997 out = "IntervalVar(start = ";
1998 }
1999
2000 absl::StrAppendFormat(&out,
2001 "%s, duration = %s, end = %s, performed = %s)",
2002 start_.DebugString(), duration_.DebugString(),
2003 end_.DebugString(), performed_.DebugString());
2004 return out;
2005 }
2006 }
2007
Accept(ModelVisitor * const visitor) const2008 void Accept(ModelVisitor* const visitor) const override {
2009 visitor->VisitIntervalVariable(this, "", 0, NullInterval());
2010 }
2011
StartExpr()2012 IntExpr* StartExpr() override { return &start_; }
DurationExpr()2013 IntExpr* DurationExpr() override { return &duration_; }
EndExpr()2014 IntExpr* EndExpr() override { return &end_; }
PerformedExpr()2015 IntExpr* PerformedExpr() override { return &performed_; }
SafeStartExpr(int64_t unperformed_value)2016 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
2017 return BuildSafeStartExpr(this, unperformed_value);
2018 }
SafeDurationExpr(int64_t unperformed_value)2019 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
2020 return BuildSafeDurationExpr(this, unperformed_value);
2021 }
SafeEndExpr(int64_t unperformed_value)2022 IntExpr* SafeEndExpr(int64_t unperformed_value) override {
2023 return BuildSafeEndExpr(this, unperformed_value);
2024 }
2025
2026 private:
Push()2027 void Push() override {
2028 DCHECK(!in_process_);
2029 if (performed_.Max() == 1) {
2030 // Performs the intersection on all intervals before pushing the
2031 // variable onto the queue. This way, we make sure the interval variable
2032 // is always in a consistent minimal state.
2033 start_.SetRange(CapSub(end_.Min(), duration_.Max()),
2034 CapSub(end_.Max(), duration_.Min()));
2035 duration_.SetRange(CapSub(end_.Min(), start_.Max()),
2036 CapSub(end_.Max(), start_.Min()));
2037 end_.SetRange(CapAdd(start_.Min(), duration_.Min()),
2038 CapAdd(start_.Max(), duration_.Max()));
2039 }
2040 EnqueueVar(&handler_);
2041 DCHECK(!in_process_);
2042 }
2043
2044 RangeVar start_;
2045 RangeVar duration_;
2046 RangeVar end_;
2047 PerformedVar performed_;
2048 };
2049
2050 // ----- Base synced interval var -----
2051
2052 class FixedDurationSyncedIntervalVar : public IntervalVar {
2053 public:
FixedDurationSyncedIntervalVar(IntervalVar * const t,int64_t duration,int64_t offset,const std::string & name)2054 FixedDurationSyncedIntervalVar(IntervalVar* const t, int64_t duration,
2055 int64_t offset, const std::string& name)
2056 : IntervalVar(t->solver(), name),
2057 t_(t),
2058 duration_(duration),
2059 offset_(offset) {}
~FixedDurationSyncedIntervalVar()2060 ~FixedDurationSyncedIntervalVar() override {}
DurationMin() const2061 int64_t DurationMin() const override { return duration_; }
DurationMax() const2062 int64_t DurationMax() const override { return duration_; }
SetDurationMin(int64_t m)2063 void SetDurationMin(int64_t m) override {
2064 if (m > duration_) {
2065 solver()->Fail();
2066 }
2067 }
SetDurationMax(int64_t m)2068 void SetDurationMax(int64_t m) override {
2069 if (m < duration_) {
2070 solver()->Fail();
2071 }
2072 }
SetDurationRange(int64_t mi,int64_t ma)2073 void SetDurationRange(int64_t mi, int64_t ma) override {
2074 if (mi > duration_ || ma < duration_ || mi > ma) {
2075 solver()->Fail();
2076 }
2077 }
OldDurationMin() const2078 int64_t OldDurationMin() const override { return duration_; }
OldDurationMax() const2079 int64_t OldDurationMax() const override { return duration_; }
WhenDurationRange(Demon * const d)2080 void WhenDurationRange(Demon* const d) override {}
WhenDurationBound(Demon * const d)2081 void WhenDurationBound(Demon* const d) override {}
EndMin() const2082 int64_t EndMin() const override { return CapAdd(StartMin(), duration_); }
EndMax() const2083 int64_t EndMax() const override { return CapAdd(StartMax(), duration_); }
SetEndMin(int64_t m)2084 void SetEndMin(int64_t m) override { SetStartMin(CapSub(m, duration_)); }
SetEndMax(int64_t m)2085 void SetEndMax(int64_t m) override { SetStartMax(CapSub(m, duration_)); }
SetEndRange(int64_t mi,int64_t ma)2086 void SetEndRange(int64_t mi, int64_t ma) override {
2087 SetStartRange(CapSub(mi, duration_), CapSub(ma, duration_));
2088 }
OldEndMin() const2089 int64_t OldEndMin() const override {
2090 return CapAdd(OldStartMin(), duration_);
2091 }
OldEndMax() const2092 int64_t OldEndMax() const override {
2093 return CapAdd(OldStartMax(), duration_);
2094 }
WhenEndRange(Demon * const d)2095 void WhenEndRange(Demon* const d) override { WhenStartRange(d); }
WhenEndBound(Demon * const d)2096 void WhenEndBound(Demon* const d) override { WhenStartBound(d); }
MustBePerformed() const2097 bool MustBePerformed() const override { return t_->MustBePerformed(); }
MayBePerformed() const2098 bool MayBePerformed() const override { return t_->MayBePerformed(); }
SetPerformed(bool val)2099 void SetPerformed(bool val) override { t_->SetPerformed(val); }
WasPerformedBound() const2100 bool WasPerformedBound() const override { return t_->WasPerformedBound(); }
WhenPerformedBound(Demon * const d)2101 void WhenPerformedBound(Demon* const d) override {
2102 t_->WhenPerformedBound(d);
2103 }
2104
2105 protected:
2106 IntervalVar* const t_;
2107 const int64_t duration_;
2108 const int64_t offset_;
2109
2110 private:
2111 DISALLOW_COPY_AND_ASSIGN(FixedDurationSyncedIntervalVar);
2112 };
2113
2114 // ----- Fixed duration interval var synced on start -----
2115
2116 class FixedDurationIntervalVarStartSyncedOnStart
2117 : public FixedDurationSyncedIntervalVar {
2118 public:
FixedDurationIntervalVarStartSyncedOnStart(IntervalVar * const t,int64_t duration,int64_t offset)2119 FixedDurationIntervalVarStartSyncedOnStart(IntervalVar* const t,
2120 int64_t duration, int64_t offset)
2121 : FixedDurationSyncedIntervalVar(
2122 t, duration, offset,
2123 absl::StrFormat(
2124 "IntervalStartSyncedOnStart(%s, duration = %d, offset = %d)",
2125 t->name(), duration, offset)) {}
~FixedDurationIntervalVarStartSyncedOnStart()2126 ~FixedDurationIntervalVarStartSyncedOnStart() override {}
StartMin() const2127 int64_t StartMin() const override { return CapAdd(t_->StartMin(), offset_); }
StartMax() const2128 int64_t StartMax() const override { return CapAdd(t_->StartMax(), offset_); }
SetStartMin(int64_t m)2129 void SetStartMin(int64_t m) override { t_->SetStartMin(CapSub(m, offset_)); }
SetStartMax(int64_t m)2130 void SetStartMax(int64_t m) override { t_->SetStartMax(CapSub(m, offset_)); }
SetStartRange(int64_t mi,int64_t ma)2131 void SetStartRange(int64_t mi, int64_t ma) override {
2132 t_->SetStartRange(CapSub(mi, offset_), CapSub(ma, offset_));
2133 }
OldStartMin() const2134 int64_t OldStartMin() const override {
2135 return CapAdd(t_->OldStartMin(), offset_);
2136 }
OldStartMax() const2137 int64_t OldStartMax() const override {
2138 return CapAdd(t_->OldStartMax(), offset_);
2139 }
WhenStartRange(Demon * const d)2140 void WhenStartRange(Demon* const d) override { t_->WhenStartRange(d); }
WhenStartBound(Demon * const d)2141 void WhenStartBound(Demon* const d) override { t_->WhenStartBound(d); }
StartExpr()2142 IntExpr* StartExpr() override {
2143 return solver()->MakeSum(t_->StartExpr(), offset_);
2144 }
DurationExpr()2145 IntExpr* DurationExpr() override { return solver()->MakeIntConst(duration_); }
EndExpr()2146 IntExpr* EndExpr() override {
2147 return solver()->MakeSum(t_->StartExpr(), offset_ + duration_);
2148 }
PerformedExpr()2149 IntExpr* PerformedExpr() override { return t_->PerformedExpr(); }
2150 // These methods create expressions encapsulating the start, end
2151 // and duration of the interval var. If the interval var is
2152 // unperformed, they will return the unperformed_value.
SafeStartExpr(int64_t unperformed_value)2153 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
2154 return BuildSafeStartExpr(t_, unperformed_value);
2155 }
SafeDurationExpr(int64_t unperformed_value)2156 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
2157 return BuildSafeDurationExpr(t_, unperformed_value);
2158 }
SafeEndExpr(int64_t unperformed_value)2159 IntExpr* SafeEndExpr(int64_t unperformed_value) override {
2160 return BuildSafeEndExpr(t_, unperformed_value);
2161 }
Accept(ModelVisitor * const visitor) const2162 void Accept(ModelVisitor* const visitor) const override {
2163 visitor->VisitIntervalVariable(
2164 this, ModelVisitor::kStartSyncOnStartOperation, offset_, t_);
2165 }
DebugString() const2166 std::string DebugString() const override {
2167 return absl::StrFormat(
2168 "IntervalStartSyncedOnStart(%s, duration = %d, offset = %d)",
2169 t_->DebugString(), duration_, offset_);
2170 }
2171 };
2172
2173 // ----- Fixed duration interval start synced on end -----
2174
2175 class FixedDurationIntervalVarStartSyncedOnEnd
2176 : public FixedDurationSyncedIntervalVar {
2177 public:
FixedDurationIntervalVarStartSyncedOnEnd(IntervalVar * const t,int64_t duration,int64_t offset)2178 FixedDurationIntervalVarStartSyncedOnEnd(IntervalVar* const t,
2179 int64_t duration, int64_t offset)
2180 : FixedDurationSyncedIntervalVar(
2181 t, duration, offset,
2182 absl::StrFormat(
2183 "IntervalStartSyncedOnEnd(%s, duration = %d, offset = %d)",
2184 t->name(), duration, offset)) {}
~FixedDurationIntervalVarStartSyncedOnEnd()2185 ~FixedDurationIntervalVarStartSyncedOnEnd() override {}
StartMin() const2186 int64_t StartMin() const override { return CapAdd(t_->EndMin(), offset_); }
StartMax() const2187 int64_t StartMax() const override { return CapAdd(t_->EndMax(), offset_); }
SetStartMin(int64_t m)2188 void SetStartMin(int64_t m) override { t_->SetEndMin(CapSub(m, offset_)); }
SetStartMax(int64_t m)2189 void SetStartMax(int64_t m) override { t_->SetEndMax(CapSub(m, offset_)); }
SetStartRange(int64_t mi,int64_t ma)2190 void SetStartRange(int64_t mi, int64_t ma) override {
2191 t_->SetEndRange(CapSub(mi, offset_), CapSub(ma, offset_));
2192 }
OldStartMin() const2193 int64_t OldStartMin() const override {
2194 return CapAdd(t_->OldEndMin(), offset_);
2195 }
OldStartMax() const2196 int64_t OldStartMax() const override {
2197 return CapAdd(t_->OldEndMax(), offset_);
2198 }
WhenStartRange(Demon * const d)2199 void WhenStartRange(Demon* const d) override { t_->WhenEndRange(d); }
WhenStartBound(Demon * const d)2200 void WhenStartBound(Demon* const d) override { t_->WhenEndBound(d); }
StartExpr()2201 IntExpr* StartExpr() override {
2202 return solver()->MakeSum(t_->EndExpr(), offset_);
2203 }
DurationExpr()2204 IntExpr* DurationExpr() override { return solver()->MakeIntConst(duration_); }
EndExpr()2205 IntExpr* EndExpr() override {
2206 return solver()->MakeSum(t_->EndExpr(), offset_ + duration_);
2207 }
PerformedExpr()2208 IntExpr* PerformedExpr() override { return t_->PerformedExpr(); }
2209 // These methods create expressions encapsulating the start, end
2210 // and duration of the interval var. If the interval var is
2211 // unperformed, they will return the unperformed_value.
SafeStartExpr(int64_t unperformed_value)2212 IntExpr* SafeStartExpr(int64_t unperformed_value) override {
2213 return BuildSafeStartExpr(t_, unperformed_value);
2214 }
SafeDurationExpr(int64_t unperformed_value)2215 IntExpr* SafeDurationExpr(int64_t unperformed_value) override {
2216 return BuildSafeDurationExpr(t_, unperformed_value);
2217 }
SafeEndExpr(int64_t unperformed_value)2218 IntExpr* SafeEndExpr(int64_t unperformed_value) override {
2219 return BuildSafeEndExpr(t_, unperformed_value);
2220 }
2221
Accept(ModelVisitor * const visitor) const2222 void Accept(ModelVisitor* const visitor) const override {
2223 visitor->VisitIntervalVariable(this, ModelVisitor::kStartSyncOnEndOperation,
2224 offset_, t_);
2225 }
DebugString() const2226 std::string DebugString() const override {
2227 return absl::StrFormat(
2228 "IntervalStartSyncedOnEnd(%s, duration = %d, offset = %d)",
2229 t_->DebugString(), duration_, offset_);
2230 }
2231 };
2232 } // namespace
2233
2234 // ----- API -----
2235
MakeMirrorInterval(IntervalVar * const interval_var)2236 IntervalVar* Solver::MakeMirrorInterval(IntervalVar* const interval_var) {
2237 return RegisterIntervalVar(
2238 RevAlloc(new MirrorIntervalVar(this, interval_var)));
2239 }
2240
MakeIntervalRelaxedMax(IntervalVar * const interval_var)2241 IntervalVar* Solver::MakeIntervalRelaxedMax(IntervalVar* const interval_var) {
2242 if (interval_var->MustBePerformed()) {
2243 return interval_var;
2244 } else {
2245 return RegisterIntervalVar(
2246 RevAlloc(new IntervalVarRelaxedMax(interval_var)));
2247 }
2248 }
2249
MakeIntervalRelaxedMin(IntervalVar * const interval_var)2250 IntervalVar* Solver::MakeIntervalRelaxedMin(IntervalVar* const interval_var) {
2251 if (interval_var->MustBePerformed()) {
2252 return interval_var;
2253 } else {
2254 return RegisterIntervalVar(
2255 RevAlloc(new IntervalVarRelaxedMin(interval_var)));
2256 }
2257 }
2258
WhenAnything(Demon * const d)2259 void IntervalVar::WhenAnything(Demon* const d) {
2260 WhenStartRange(d);
2261 WhenDurationRange(d);
2262 WhenEndRange(d);
2263 WhenPerformedBound(d);
2264 }
2265
MakeFixedInterval(int64_t start,int64_t duration,const std::string & name)2266 IntervalVar* Solver::MakeFixedInterval(int64_t start, int64_t duration,
2267 const std::string& name) {
2268 return RevAlloc(new FixedInterval(this, start, duration, name));
2269 }
2270
MakeFixedDurationIntervalVar(int64_t start_min,int64_t start_max,int64_t duration,bool optional,const std::string & name)2271 IntervalVar* Solver::MakeFixedDurationIntervalVar(int64_t start_min,
2272 int64_t start_max,
2273 int64_t duration,
2274 bool optional,
2275 const std::string& name) {
2276 if (start_min == start_max && !optional) {
2277 return MakeFixedInterval(start_min, duration, name);
2278 } else if (!optional) {
2279 return RegisterIntervalVar(RevAlloc(new FixedDurationPerformedIntervalVar(
2280 this, start_min, start_max, duration, name)));
2281 }
2282 return RegisterIntervalVar(RevAlloc(new FixedDurationIntervalVar(
2283 this, start_min, start_max, duration, optional, name)));
2284 }
2285
MakeFixedDurationIntervalVarArray(int count,int64_t start_min,int64_t start_max,int64_t duration,bool optional,const std::string & name,std::vector<IntervalVar * > * array)2286 void Solver::MakeFixedDurationIntervalVarArray(
2287 int count, int64_t start_min, int64_t start_max, int64_t duration,
2288 bool optional, const std::string& name, std::vector<IntervalVar*>* array) {
2289 CHECK_GT(count, 0);
2290 CHECK(array != nullptr);
2291 array->clear();
2292 for (int i = 0; i < count; ++i) {
2293 const std::string var_name = absl::StrCat(name, i);
2294 array->push_back(MakeFixedDurationIntervalVar(
2295 start_min, start_max, duration, optional, var_name));
2296 }
2297 }
2298
MakeFixedDurationIntervalVar(IntVar * const start_variable,int64_t duration,const std::string & name)2299 IntervalVar* Solver::MakeFixedDurationIntervalVar(IntVar* const start_variable,
2300 int64_t duration,
2301 const std::string& name) {
2302 CHECK(start_variable != nullptr);
2303 CHECK_GE(duration, 0);
2304 return RegisterIntervalVar(RevAlloc(
2305 new StartVarPerformedIntervalVar(this, start_variable, duration, name)));
2306 }
2307
2308 // Creates an interval var with a fixed duration, and performed var.
2309 // The duration must be greater than 0.
MakeFixedDurationIntervalVar(IntVar * const start_variable,int64_t duration,IntVar * const performed_variable,const std::string & name)2310 IntervalVar* Solver::MakeFixedDurationIntervalVar(
2311 IntVar* const start_variable, int64_t duration,
2312 IntVar* const performed_variable, const std::string& name) {
2313 CHECK(start_variable != nullptr);
2314 CHECK(performed_variable != nullptr);
2315 CHECK_GE(duration, 0);
2316 if (!performed_variable->Bound()) {
2317 StartVarIntervalVar* const interval =
2318 reinterpret_cast<StartVarIntervalVar*>(
2319 RegisterIntervalVar(RevAlloc(new StartVarIntervalVar(
2320 this, start_variable, duration, performed_variable, name))));
2321 AddConstraint(RevAlloc(new LinkStartVarIntervalVar(
2322 this, interval, start_variable, performed_variable)));
2323 return interval;
2324 } else if (performed_variable->Min() == 1) {
2325 return RegisterIntervalVar(RevAlloc(new StartVarPerformedIntervalVar(
2326 this, start_variable, duration, name)));
2327 }
2328 return nullptr;
2329 }
2330
MakeFixedDurationIntervalVarArray(const std::vector<IntVar * > & start_variables,int64_t duration,const std::string & name,std::vector<IntervalVar * > * array)2331 void Solver::MakeFixedDurationIntervalVarArray(
2332 const std::vector<IntVar*>& start_variables, int64_t duration,
2333 const std::string& name, std::vector<IntervalVar*>* array) {
2334 CHECK(array != nullptr);
2335 array->clear();
2336 for (int i = 0; i < start_variables.size(); ++i) {
2337 const std::string var_name = absl::StrCat(name, i);
2338 array->push_back(
2339 MakeFixedDurationIntervalVar(start_variables[i], duration, var_name));
2340 }
2341 }
2342
2343 // This method fills the vector with interval variables built with
2344 // the corresponding start variables.
MakeFixedDurationIntervalVarArray(const std::vector<IntVar * > & start_variables,const std::vector<int64_t> & durations,const std::string & name,std::vector<IntervalVar * > * array)2345 void Solver::MakeFixedDurationIntervalVarArray(
2346 const std::vector<IntVar*>& start_variables,
2347 const std::vector<int64_t>& durations, const std::string& name,
2348 std::vector<IntervalVar*>* array) {
2349 CHECK(array != nullptr);
2350 CHECK_EQ(start_variables.size(), durations.size());
2351 array->clear();
2352 for (int i = 0; i < start_variables.size(); ++i) {
2353 const std::string var_name = absl::StrCat(name, i);
2354 array->push_back(MakeFixedDurationIntervalVar(start_variables[i],
2355 durations[i], var_name));
2356 }
2357 }
2358
MakeFixedDurationIntervalVarArray(const std::vector<IntVar * > & start_variables,const std::vector<int> & durations,const std::string & name,std::vector<IntervalVar * > * array)2359 void Solver::MakeFixedDurationIntervalVarArray(
2360 const std::vector<IntVar*>& start_variables,
2361 const std::vector<int>& durations, const std::string& name,
2362 std::vector<IntervalVar*>* array) {
2363 CHECK(array != nullptr);
2364 CHECK_EQ(start_variables.size(), durations.size());
2365 array->clear();
2366 for (int i = 0; i < start_variables.size(); ++i) {
2367 const std::string var_name = absl::StrCat(name, i);
2368 array->push_back(MakeFixedDurationIntervalVar(start_variables[i],
2369 durations[i], var_name));
2370 }
2371 }
2372
MakeFixedDurationIntervalVarArray(const std::vector<IntVar * > & start_variables,const std::vector<int> & durations,const std::vector<IntVar * > & performed_variables,const std::string & name,std::vector<IntervalVar * > * array)2373 void Solver::MakeFixedDurationIntervalVarArray(
2374 const std::vector<IntVar*>& start_variables,
2375 const std::vector<int>& durations,
2376 const std::vector<IntVar*>& performed_variables, const std::string& name,
2377 std::vector<IntervalVar*>* array) {
2378 CHECK(array != nullptr);
2379 array->clear();
2380 for (int i = 0; i < start_variables.size(); ++i) {
2381 const std::string var_name = absl::StrCat(name, i);
2382 array->push_back(MakeFixedDurationIntervalVar(
2383 start_variables[i], durations[i], performed_variables[i], var_name));
2384 }
2385 }
2386
MakeFixedDurationIntervalVarArray(const std::vector<IntVar * > & start_variables,const std::vector<int64_t> & durations,const std::vector<IntVar * > & performed_variables,const std::string & name,std::vector<IntervalVar * > * array)2387 void Solver::MakeFixedDurationIntervalVarArray(
2388 const std::vector<IntVar*>& start_variables,
2389 const std::vector<int64_t>& durations,
2390 const std::vector<IntVar*>& performed_variables, const std::string& name,
2391 std::vector<IntervalVar*>* array) {
2392 CHECK(array != nullptr);
2393 array->clear();
2394 for (int i = 0; i < start_variables.size(); ++i) {
2395 const std::string var_name = absl::StrCat(name, i);
2396 array->push_back(MakeFixedDurationIntervalVar(
2397 start_variables[i], durations[i], performed_variables[i], var_name));
2398 }
2399 }
2400
2401 // Variable Duration Interval Var
2402
MakeIntervalVar(int64_t start_min,int64_t start_max,int64_t duration_min,int64_t duration_max,int64_t end_min,int64_t end_max,bool optional,const std::string & name)2403 IntervalVar* Solver::MakeIntervalVar(int64_t start_min, int64_t start_max,
2404 int64_t duration_min, int64_t duration_max,
2405 int64_t end_min, int64_t end_max,
2406 bool optional, const std::string& name) {
2407 return RegisterIntervalVar(RevAlloc(new VariableDurationIntervalVar(
2408 this, start_min, start_max, duration_min, duration_max, end_min, end_max,
2409 optional, name)));
2410 }
2411
MakeIntervalVarArray(int count,int64_t start_min,int64_t start_max,int64_t duration_min,int64_t duration_max,int64_t end_min,int64_t end_max,bool optional,const std::string & name,std::vector<IntervalVar * > * const array)2412 void Solver::MakeIntervalVarArray(int count, int64_t start_min,
2413 int64_t start_max, int64_t duration_min,
2414 int64_t duration_max, int64_t end_min,
2415 int64_t end_max, bool optional,
2416 const std::string& name,
2417 std::vector<IntervalVar*>* const array) {
2418 CHECK_GT(count, 0);
2419 CHECK(array != nullptr);
2420 array->clear();
2421 for (int i = 0; i < count; ++i) {
2422 const std::string var_name = absl::StrCat(name, i);
2423 array->push_back(MakeIntervalVar(start_min, start_max, duration_min,
2424 duration_max, end_min, end_max, optional,
2425 var_name));
2426 }
2427 }
2428
2429 // Synced Interval Vars
MakeFixedDurationStartSyncedOnStartIntervalVar(IntervalVar * const interval_var,int64_t duration,int64_t offset)2430 IntervalVar* Solver::MakeFixedDurationStartSyncedOnStartIntervalVar(
2431 IntervalVar* const interval_var, int64_t duration, int64_t offset) {
2432 return RegisterIntervalVar(
2433 RevAlloc(new FixedDurationIntervalVarStartSyncedOnStart(
2434 interval_var, duration, offset)));
2435 }
2436
MakeFixedDurationStartSyncedOnEndIntervalVar(IntervalVar * const interval_var,int64_t duration,int64_t offset)2437 IntervalVar* Solver::MakeFixedDurationStartSyncedOnEndIntervalVar(
2438 IntervalVar* const interval_var, int64_t duration, int64_t offset) {
2439 return RegisterIntervalVar(
2440 RevAlloc(new FixedDurationIntervalVarStartSyncedOnEnd(interval_var,
2441 duration, offset)));
2442 }
2443
MakeFixedDurationEndSyncedOnStartIntervalVar(IntervalVar * const interval_var,int64_t duration,int64_t offset)2444 IntervalVar* Solver::MakeFixedDurationEndSyncedOnStartIntervalVar(
2445 IntervalVar* const interval_var, int64_t duration, int64_t offset) {
2446 return RegisterIntervalVar(
2447 RevAlloc(new FixedDurationIntervalVarStartSyncedOnStart(
2448 interval_var, duration, CapSub(offset, duration))));
2449 }
2450
MakeFixedDurationEndSyncedOnEndIntervalVar(IntervalVar * const interval_var,int64_t duration,int64_t offset)2451 IntervalVar* Solver::MakeFixedDurationEndSyncedOnEndIntervalVar(
2452 IntervalVar* const interval_var, int64_t duration, int64_t offset) {
2453 return RegisterIntervalVar(
2454 RevAlloc(new FixedDurationIntervalVarStartSyncedOnEnd(
2455 interval_var, duration, CapSub(offset, duration))));
2456 }
2457 } // namespace operations_research
2458