27 #include "absl/strings/str_format.h"
37 class TreeArrayConstraint :
public Constraint {
39 enum PerformedStatus { UNPERFORMED, PERFORMED, UNDECIDED };
41 TreeArrayConstraint(Solver*
const solver,
42 const std::vector<IntervalVar*>& vars,
43 IntervalVar*
const target_var)
47 block_size_(solver->
parameters().array_split_size()) {
48 std::vector<int> lengths;
49 lengths.push_back(
vars_.size());
50 while (lengths.back() > 1) {
51 const int current = lengths.back();
52 lengths.push_back((current + block_size_ - 1) / block_size_);
54 tree_.resize(lengths.size());
55 for (
int i = 0; i < lengths.size(); ++i) {
56 tree_[i].resize(lengths[lengths.size() - i - 1]);
60 root_node_ = &tree_[0][0];
63 std::string DebugStringInternal(
const std::string&
name)
const {
68 void AcceptInternal(
const std::string&
name,
69 ModelVisitor*
const visitor)
const {
70 visitor->BeginVisitConstraint(
name,
this);
74 visitor->EndVisitConstraint(
name,
this);
78 void ReduceDomain(
int depth,
int position,
int64 new_start_min,
81 NodeInfo*
const info = &tree_[depth][position];
82 if (new_start_min > info->start_min.Value()) {
83 info->start_min.SetValue(solver(), new_start_min);
85 if (new_start_max < info->
start_max.Value()) {
86 info->start_max.SetValue(solver(), new_start_max);
88 if (new_end_min > info->end_min.Value()) {
89 info->end_min.SetValue(solver(), new_end_min);
91 if (new_end_max < info->
end_max.Value()) {
92 info->end_max.SetValue(solver(), new_end_max);
96 info->performed.Value() == UNDECIDED);
97 info->performed.SetValue(solver(),
performed);
109 tree_[depth][position].start_min.SetValue(solver(),
start_min);
110 tree_[depth][position].start_max.SetValue(solver(),
start_max);
111 tree_[depth][position].end_min.SetValue(solver(),
end_min);
112 tree_[depth][position].end_max.SetValue(solver(),
end_max);
113 tree_[depth][position].performed.SetValue(solver(),
117 int64 StartMin(
int depth,
int position)
const {
118 return tree_[depth][position].start_min.Value();
121 int64 StartMax(
int depth,
int position)
const {
122 return tree_[depth][position].start_max.Value();
125 int64 EndMax(
int depth,
int position)
const {
126 return tree_[depth][position].end_max.Value();
129 int64 EndMin(
int depth,
int position)
const {
130 return tree_[depth][position].end_min.Value();
133 PerformedStatus Performed(
int depth,
int position)
const {
134 const int p = tree_[depth][position].performed.Value();
137 return static_cast<PerformedStatus
>(p);
140 int64 RootStartMin()
const {
return root_node_->start_min.Value(); }
142 int64 RootStartMax()
const {
return root_node_->start_max.Value(); }
144 int64 RootEndMin()
const {
return root_node_->end_min.Value(); }
146 int64 RootEndMax()
const {
return root_node_->end_max.Value(); }
148 PerformedStatus RootPerformed()
const {
return Performed(0, 0); }
152 int64 VarStartMin(
int position)
const {
153 return vars_[position]->MayBePerformed() ?
vars_[position]->StartMin() : 0;
156 int64 VarStartMax(
int position)
const {
157 return vars_[position]->MayBePerformed() ?
vars_[position]->StartMax() : 0;
160 int64 VarEndMin(
int position)
const {
161 return vars_[position]->MayBePerformed() ?
vars_[position]->EndMin() : 0;
164 int64 VarEndMax(
int position)
const {
165 return vars_[position]->MayBePerformed() ?
vars_[position]->EndMax() : 0;
168 int64 TargetVarStartMin()
const {
172 int64 TargetVarStartMax()
const {
176 int64 TargetVarEndMin()
const {
180 int64 TargetVarEndMax()
const {
186 PerformedStatus VarPerformed(
int position)
const {
187 IntervalVar*
const var =
vars_[position];
188 if (
var->MustBePerformed()) {
190 }
else if (
var->MayBePerformed()) {
198 PerformedStatus TargetVarPerformed()
const {
209 int Parent(
int position)
const {
return position / block_size_; }
212 int ChildStart(
int position)
const {
return position * block_size_; }
217 int ChildEnd(
int depth,
int position)
const {
219 return std::min((position + 1) * block_size_ - 1, Width(depth + 1) - 1);
222 bool IsLeaf(
int depth)
const {
return depth == MaxDepth(); }
224 int MaxDepth()
const {
return tree_.size() - 1; }
226 int Width(
int depth)
const {
return tree_[depth].size(); }
229 const std::vector<IntervalVar*>
vars_;
248 std::vector<std::vector<NodeInfo> > tree_;
249 const int block_size_;
250 NodeInfo* root_node_;
254 class CoverConstraint :
public TreeArrayConstraint {
256 CoverConstraint(Solver*
const solver,
const std::vector<IntervalVar*>& vars,
257 IntervalVar*
const cover_var)
258 : TreeArrayConstraint(solver, vars, cover_var), cover_demon_(
nullptr) {}
260 ~CoverConstraint()
override {}
262 void Post()
override {
263 for (
int i = 0; i <
vars_.size(); ++i) {
265 solver(),
this, &CoverConstraint::LeafChanged,
"LeafChanged", i);
266 vars_[i]->WhenStartRange(demon);
267 vars_[i]->WhenEndRange(demon);
268 vars_[i]->WhenPerformedBound(demon);
271 solver(),
this, &CoverConstraint::CoverVarChanged,
"CoverVarChanged"));
277 void InitialPropagate()
override {
279 for (
int i = 0; i <
vars_.size(); ++i) {
280 InitLeaf(i, VarStartMin(i), VarStartMax(i), VarEndMin(i), VarEndMax(i),
285 for (
int i = MaxDepth() - 1; i >= 0; --i) {
286 for (
int j = 0; j < Width(i); ++j) {
291 bool one_undecided =
false;
292 const PerformedStatus up_performed = ComputePropagationUp(
293 i, j, &bucket_start_min, &bucket_start_max, &bucket_end_min,
294 &bucket_end_max, &one_undecided);
295 InitNode(i, j, bucket_start_min, bucket_start_max, bucket_end_min,
296 bucket_end_max, up_performed);
303 void PropagateRoot() {
305 switch (RootPerformed()) {
311 ABSL_FALLTHROUGH_INTENDED;
313 target_var_->SetStartRange(RootStartMin(), RootStartMax());
314 target_var_->SetEndRange(RootEndMin(), RootEndMax());
324 void CoverVarChanged() {
325 PushDown(0, 0, TargetVarStartMin(), TargetVarStartMax(), TargetVarEndMin(),
326 TargetVarEndMax(), TargetVarPerformed());
329 void PushDown(
int depth,
int position,
int64 new_start_min,
334 if (new_start_min <= StartMin(depth, position) &&
335 new_start_max >= StartMax(depth, position) &&
336 new_end_min <= EndMin(depth, position) &&
337 new_end_max >= EndMax(depth, position) &&
345 vars_[position]->SetPerformed(
false);
348 vars_[position]->SetPerformed(
true);
349 ABSL_FALLTHROUGH_INTENDED;
351 vars_[position]->SetStartRange(new_start_min, new_start_max);
352 vars_[position]->SetEndRange(new_end_min, new_end_max);
357 const int block_start = ChildStart(position);
358 const int block_end = ChildEnd(depth, position);
362 for (
int i = block_start; i <= block_end; ++i) {
363 PushDown(depth + 1, i, new_start_min, new_start_max, new_end_min,
364 new_end_max, UNPERFORMED);
370 int may_be_performed_count = 0;
371 int must_be_performed_count = 0;
372 for (
int i = block_start; i <= block_end; ++i) {
373 switch (Performed(depth + 1, i)) {
377 must_be_performed_count++;
378 ABSL_FALLTHROUGH_INTENDED;
380 may_be_performed_count++;
384 if (may_be_performed_count == 0) {
386 }
else if (may_be_performed_count == 1) {
387 PushDown(depth + 1, candidate, new_start_min, new_start_max,
388 new_end_min, new_end_max, PERFORMED);
390 for (
int i = block_start; i <= block_end; ++i) {
395 PushDown(depth + 1, i, new_start_min, new_end_max, new_start_min,
396 new_end_max, UNDECIDED);
402 for (
int i = block_start; i <= block_end; ++i) {
407 PushDown(depth + 1, i, new_start_min, new_end_max, new_start_min,
408 new_end_max, UNDECIDED);
414 void LeafChanged(
int term_index) {
415 ReduceDomain(MaxDepth(), term_index, VarStartMin(term_index),
416 VarStartMax(term_index), VarEndMin(term_index),
417 VarEndMax(term_index), VarPerformed(term_index));
419 const int parent = Parent(term_index);
420 const int parent_depth = MaxDepth() - 1;
421 const int64 parent_start_min = StartMin(parent_depth, parent);
422 const int64 parent_start_max = StartMax(parent_depth, parent);
423 const int64 parent_end_min = EndMin(parent_depth, parent);
424 const int64 parent_end_max = EndMax(parent_depth, parent);
425 IntervalVar*
const var =
vars_[term_index];
426 const bool performed_bound =
var->IsPerformedBound();
427 const bool was_performed_bound =
var->WasPerformedBound();
428 if (performed_bound == was_performed_bound &&
var->MayBePerformed() &&
429 var->OldStartMin() != parent_start_min &&
430 var->OldStartMax() != parent_start_max &&
431 var->OldEndMin() != parent_end_min &&
432 var->OldEndMax() != parent_end_max) {
440 void PushUp(
int position) {
441 int depth = MaxDepth();
443 const int parent = Parent(position);
444 const int parent_depth = depth - 1;
449 bool one_undecided =
false;
450 const PerformedStatus status_up = ComputePropagationUp(
451 parent_depth, parent, &bucket_start_min, &bucket_start_max,
452 &bucket_end_min, &bucket_end_max, &one_undecided);
453 if (bucket_start_min > StartMin(parent_depth, parent) ||
454 bucket_start_max < StartMax(parent_depth, parent) ||
455 bucket_end_min > EndMin(parent_depth, parent) ||
456 bucket_end_max < EndMax(parent_depth, parent) ||
457 status_up != Performed(parent_depth, parent)) {
458 ReduceDomain(parent_depth, parent, bucket_start_min, bucket_start_max,
459 bucket_end_min, bucket_end_max, status_up);
461 if (one_undecided && TargetVarPerformed() == PERFORMED) {
469 depth = parent_depth;
476 std::string DebugString()
const override {
480 void Accept(ModelVisitor*
const visitor)
const override {
485 PerformedStatus ComputePropagationUp(
int parent_depth,
int parent_position,
486 int64*
const bucket_start_min,
487 int64*
const bucket_start_max,
488 int64*
const bucket_end_min,
489 int64*
const bucket_end_max,
490 bool* one_undecided) {
496 int may_be_performed_count = 0;
497 int must_be_performed_count = 0;
498 const int block_start = ChildStart(parent_position);
499 const int block_end = ChildEnd(parent_depth, parent_position);
500 for (
int k = block_start; k <= block_end; ++k) {
501 const PerformedStatus
performed = Performed(parent_depth + 1, k);
504 std::min(*bucket_start_min, StartMin(parent_depth + 1, k));
506 std::max(*bucket_end_max, EndMax(parent_depth + 1, k));
507 may_be_performed_count++;
510 std::min(*bucket_start_max, StartMax(parent_depth + 1, k));
512 std::max(*bucket_end_min, EndMin(parent_depth + 1, k));
513 must_be_performed_count++;
517 const PerformedStatus up_performed =
518 must_be_performed_count > 0
520 : (may_be_performed_count > 0 ? UNDECIDED : UNPERFORMED);
522 (may_be_performed_count == 1) && (must_be_performed_count == 0);
529 class IntervalEquality :
public Constraint {
531 IntervalEquality(Solver*
const solver, IntervalVar*
const var1,
532 IntervalVar*
const var2)
533 : Constraint(solver), var1_(var1), var2_(var2) {}
535 ~IntervalEquality()
override {}
537 void Post()
override {
538 Demon*
const demon = solver()->MakeConstraintInitialPropagateCallback(
this);
539 var1_->WhenAnything(demon);
540 var2_->WhenAnything(demon);
543 void InitialPropagate()
override {
545 if (!var1_->MayBePerformed()) {
546 var2_->SetPerformed(
false);
548 if (var1_->MustBePerformed()) {
549 var2_->SetPerformed(
true);
551 var2_->SetStartRange(var1_->StartMin(), var1_->StartMax());
552 var2_->SetDurationRange(var1_->DurationMin(), var1_->DurationMax());
553 var2_->SetEndRange(var1_->EndMin(), var1_->EndMax());
555 if (!var2_->MayBePerformed()) {
556 var1_->SetPerformed(
false);
558 if (var2_->MustBePerformed()) {
559 var1_->SetPerformed(
true);
561 var1_->SetStartRange(var2_->StartMin(), var2_->StartMax());
562 var1_->SetDurationRange(var2_->DurationMin(), var2_->DurationMax());
563 var1_->SetEndRange(var2_->EndMin(), var2_->EndMax());
567 std::string DebugString()
const override {
568 return absl::StrFormat(
"Equality(%s, %s)", var1_->DebugString(),
569 var2_->DebugString());
572 void Accept(ModelVisitor*
const visitor)
const override {
580 IntervalVar*
const var1_;
581 IntervalVar*
const var2_;
587 CHECK(!vars.empty());
588 if (vars.size() == 1) {
591 return RevAlloc(
new CoverConstraint(
this, vars, target_var));
597 return RevAlloc(
new IntervalEquality(
this, var1, var2));