OR-Tools  8.1
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
operations_research::IntVar
The class IntVar is a subset of IntExpr.
Definition: constraint_solver.h:3992
var
IntVar * var
Definition: expr_array.cc:1858
operations_research::BuildEndExpr
IntExpr * BuildEndExpr(IntervalVar *var)
Definition: sched_expr.cc:172
min
int64 min
Definition: alldiff_cst.cc:138
integral_types.h
operations_research::CapSub
int64 CapSub(int64 x, int64 y)
Definition: saturated_arithmetic.h:154
max
int64 max
Definition: alldiff_cst.cc:139
operations_research::LinkVarExpr
void LinkVarExpr(Solver *const s, IntExpr *const expr, IntVar *const var)
Definition: expressions.cc:7396
operations_research::IntervalVar::kMaxValidValue
static const int64 kMaxValidValue
The largest acceptable value to be returned by EndMax()
Definition: constraint_solver.h:4394
operations_research::BuildSafeStartExpr
IntExpr * BuildSafeStartExpr(IntervalVar *var, int64 unperformed_value)
Definition: sched_expr.cc:182
LOG
#define LOG(severity)
Definition: base/logging.h:420
operations_research::Solver::DELAYED_PRIORITY
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
Definition: constraint_solver.h:611
end_max
Rev< int64 > end_max
Definition: sched_constraints.cc:244
FATAL
const int FATAL
Definition: log_severity.h:32
CHECK_GE
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
start_min
Rev< int64 > start_min
Definition: sched_constraints.cc:241
logging.h
operations_research::BuildSafeDurationExpr
IntExpr * BuildSafeDurationExpr(IntervalVar *var, int64 unperformed_value)
Definition: sched_expr.cc:187
operations_research::IntExpr::Min
virtual int64 Min() const =0
CHECK_GT
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
macros.h
saturated_arithmetic.h
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::InternalSaveBooleanVarValue
void InternalSaveBooleanVarValue(Solver *const solver, IntVar *const var)
Definition: constraint_solver.cc:947
operations_research::BuildStartExpr
IntExpr * BuildStartExpr(IntervalVar *var)
Definition: sched_expr.cc:152
int64
int64_t int64
Definition: integral_types.h:34
constraint_solveri.h
operations_research::RegisterDemon
void RegisterDemon(Solver *const solver, Demon *const demon, DemonProfiler *const monitor)
Definition: demon_profiler.cc:460
offset_
const int64 offset_
Definition: interval.cc:2076
operations_research::IntExpr::Bound
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
Definition: constraint_solver.h:3857
DCHECK_NE
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
constraint_solver.h
handler_
Handler handler_
Definition: interval.cc:420
operations_research::CapAdd
int64 CapAdd(int64 x, int64 y)
Definition: saturated_arithmetic.h:124
cleaner_
Solver::Action cleaner_
Definition: interval.cc:421
CHECK_EQ
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
operations_research::ModelVisitor::kRelaxedMinOperation
static const char kRelaxedMinOperation[]
Definition: constraint_solver.h:3495
start_max
Rev< int64 > start_max
Definition: sched_constraints.cc:242
operations_research::Solver::Action
std::function< void(Solver *)> Action
Definition: constraint_solver.h:754
DCHECK
#define DCHECK(condition)
Definition: base/logging.h:884
operations_research::IntervalVar
Interval variables are often used in scheduling.
Definition: constraint_solver.h:4389
performed
Rev< int > performed
Definition: sched_constraints.cc:245
operations_research::IntervalVar::kMinValidValue
static const int64 kMinValidValue
The smallest acceptable value to be returned by StartMin()
Definition: constraint_solver.h:4392
operations_research::IntervalVar::MustBePerformed
virtual bool MustBePerformed() const =0
These methods query, set, and watch the performed status of the interval var.
operations_research::Demon
A Demon is the base element of a propagation queue.
Definition: constraint_solver.h:3296
end_min
Rev< int64 > end_min
Definition: sched_constraints.cc:243
operations_research::BuildSafeEndExpr
IntExpr * BuildSafeEndExpr(IntervalVar *var, int64 unperformed_value)
Definition: sched_expr.cc:192
in_process_
bool in_process_
Definition: interval.cc:419
operations_research::Solver::VAR_PRIORITY
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
Definition: constraint_solver.h:614
DCHECK_EQ
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
DISALLOW_COPY_AND_ASSIGN
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
interval
IntervalVar * interval
Definition: resource.cc:98
absl
Definition: cleanup.h:22
operations_research::BuildDurationExpr
IntExpr * BuildDurationExpr(IntervalVar *var)
Definition: sched_expr.cc:162
operations_research::MakeConstraintDemon0
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
Definition: constraint_solveri.h:525
operations_research::ModelVisitor::kMirrorOperation
static const char kMirrorOperation[]
Operations.
Definition: constraint_solver.h:3493
operations_research::Solver::DemonPriority
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
Definition: constraint_solver.h:608
CHECK
#define CHECK(condition)
Definition: base/logging.h:495
name
const std::string name
Definition: default_search.cc:808
operations_research::ModelVisitor::kRelaxedMaxOperation
static const char kRelaxedMaxOperation[]
Definition: constraint_solver.h:3494
kint64max
static const int64 kint64max
Definition: integral_types.h:62