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