1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24#include <algorithm>

25#include <cstdint>

26#include <limits>

27#include <string>

28#include <vector>

29

30#include "absl/base/attributes.h"

31#include "absl/log/check.h"

32#include "absl/strings/str_format.h"

33#include "absl/strings/string_view.h"

37

39namespace {

40class TreeArrayConstraint : public Constraint {

41 public:

42 enum PerformedStatus { UNPERFORMED, PERFORMED, UNDECIDED };

43

44 TreeArrayConstraint(Solver* const solver,

45 const std::vector<IntervalVar*>& vars,

46 IntervalVar* const target_var)

47 : Constraint(solver),

48 vars_(vars),

49 target_var_(target_var),

50 block_size_(solver->parameters().array_split_size()) {

51 std::vector<int> lengths;

52 lengths.push_back(vars_.size());

53 while (lengths.back() > 1) {

54 const int current = lengths.back();

55 lengths.push_back((current + block_size_ - 1) / block_size_);

56 }

57 tree_.resize(lengths.size());

58 for (int i = 0; i < lengths.size(); ++i) {

59 tree_[i].resize(lengths[lengths.size() - i - 1]);

60 }

61 DCHECK_GE(tree_.size(), 1);

62 DCHECK_EQ(1, tree_[0].size());

63 root_node_ = &tree_[0][0];

64 }

65

66 std::string DebugStringInternal(absl::string_view name) const {

67 return absl::StrFormat("Cover(%s) == %s", JoinDebugStringPtr(vars_, ", "),

68 target_var_->DebugString());

69 }

70

71 void AcceptInternal(const std::string& name,

72 ModelVisitor* const visitor) const {

73 visitor->BeginVisitConstraint(name, this);

75 vars_);

77 visitor->EndVisitConstraint(name, this);

78 }

79

80

81 void ReduceDomain(int depth, int position, int64_t new_start_min,

82 int64_t new_start_max, int64_t new_end_min,

83 int64_t new_end_max, PerformedStatus performed) {

84 NodeInfo* const info = &tree_[depth][position];

85 if (new_start_min > info->start_min.Value()) {

86 info->start_min.SetValue(solver(), new_start_min);

87 }

88 if (new_start_max < info->start_max.Value()) {

89 info->start_max.SetValue(solver(), new_start_max);

90 }

91 if (new_end_min > info->end_min.Value()) {

92 info->end_min.SetValue(solver(), new_end_min);

93 }

94 if (new_end_max < info->end_max.Value()) {

95 info->end_max.SetValue(solver(), new_end_max);

96 }

97 if (performed != UNDECIDED) {

98 CHECK(performed == info->performed.Value() ||

99 info->performed.Value() == UNDECIDED);

100 info->performed.SetValue(solver(), performed);

101 }

102 }

103

104 void InitLeaf(int position, int64_t start_min, int64_t start_max,

105 int64_t end_min, int64_t end_max, PerformedStatus performed) {

106 InitNode(MaxDepth(), position, start_min, start_max, end_min, end_max,

107 performed);

108 }

109

110 void InitNode(int depth, int position, int64_t start_min, int64_t start_max,

111 int64_t end_min, int64_t end_max, PerformedStatus performed) {

112 tree_[depth][position].start_min.SetValue(solver(), start_min);

113 tree_[depth][position].start_max.SetValue(solver(), start_max);

114 tree_[depth][position].end_min.SetValue(solver(), end_min);

115 tree_[depth][position].end_max.SetValue(solver(), end_max);

116 tree_[depth][position].performed.SetValue(solver(),

117 static_cast<int>(performed));

118 }

119

120 int64_t StartMin(int depth, int position) const {

121 return tree_[depth][position].start_min.Value();

122 }

123

124 int64_t StartMax(int depth, int position) const {

125 return tree_[depth][position].start_max.Value();

126 }

127

128 int64_t EndMax(int depth, int position) const {

129 return tree_[depth][position].end_max.Value();

130 }

131

132 int64_t EndMin(int depth, int position) const {

133 return tree_[depth][position].end_min.Value();

134 }

135

136 PerformedStatus Performed(int depth, int position) const {

137 const int p = tree_[depth][position].performed.Value();

138 CHECK_GE(p, UNPERFORMED);

139 CHECK_LE(p, UNDECIDED);

140 return static_cast<PerformedStatus>(p);

141 }

142

143 int64_t RootStartMin() const { return root_node_->start_min.Value(); }

144

145 int64_t RootStartMax() const { return root_node_->start_max.Value(); }

146

147 int64_t RootEndMin() const { return root_node_->end_min.Value(); }

148

149 int64_t RootEndMax() const { return root_node_->end_max.Value(); }

150

151 PerformedStatus RootPerformed() const { return Performed(0, 0); }

152

153

154

155 int64_t VarStartMin(int position) const {

156 return vars_[position]->MayBePerformed() ? vars_[position]->StartMin() : 0;

157 }

158

159 int64_t VarStartMax(int position) const {

160 return vars_[position]->MayBePerformed() ? vars_[position]->StartMax() : 0;

161 }

162

163 int64_t VarEndMin(int position) const {

164 return vars_[position]->MayBePerformed() ? vars_[position]->EndMin() : 0;

165 }

166

167 int64_t VarEndMax(int position) const {

168 return vars_[position]->MayBePerformed() ? vars_[position]->EndMax() : 0;

169 }

170

171 int64_t TargetVarStartMin() const {

172 return target_var_->MayBePerformed() ? target_var_->StartMin() : 0;

173 }

174

175 int64_t TargetVarStartMax() const {

176 return target_var_->MayBePerformed() ? target_var_->StartMax() : 0;

177 }

178

179 int64_t TargetVarEndMin() const {

180 return target_var_->MayBePerformed() ? target_var_->EndMin() : 0;

181 }

182

183 int64_t TargetVarEndMax() const {

184 return target_var_->MayBePerformed() ? target_var_->EndMax() : 0;

185 }

186

187

188

189 PerformedStatus VarPerformed(int position) const {

190 IntervalVar* const var = vars_[position];

191 if (var->MustBePerformed()) {

192 return PERFORMED;

193 } else if (var->MayBePerformed()) {

194 return UNDECIDED;

195 } else {

196 return UNPERFORMED;

197 }

198 }

199

200

201 PerformedStatus TargetVarPerformed() const {

202 if (target_var_->MustBePerformed()) {

203 return PERFORMED;

204 } else if (target_var_->MayBePerformed()) {

205 return UNDECIDED;

206 } else {

207 return UNPERFORMED;

208 }

209 }

210

211

212 int Parent(int position) const { return position / block_size_; }

213

214

215 int ChildStart(int position) const { return position * block_size_; }

216

217

218

219

220 int ChildEnd(int depth, int position) const {

221 DCHECK_LT(depth + 1, tree_.size());

222 return std::min((position + 1) * block_size_ - 1, Width(depth + 1) - 1);

223 }

224

225 bool IsLeaf(int depth) const { return depth == MaxDepth(); }

226

227 int MaxDepth() const { return tree_.size() - 1; }

228

229 int Width(int depth) const { return tree_[depth].size(); }

230

231 protected:

232 const std::vector<IntervalVar*> vars_;

233 IntervalVar* const target_var_;

234

235 private:

236 struct NodeInfo {

237 NodeInfo()

238 : start_min(0),

239 start_max(0),

240 end_min(0),

241 end_max(0),

242 performed(UNDECIDED) {}

243

244 Rev<int64_t> start_min;

245 Rev<int64_t> start_max;

246 Rev<int64_t> end_min;

247 Rev<int64_t> end_max;

248 Rev<int> performed;

249 };

250

251 std::vector<std::vector<NodeInfo> > tree_;

252 const int block_size_;

253 NodeInfo* root_node_;

254};

255

256

257class CoverConstraint : public TreeArrayConstraint {

258 public:

259 CoverConstraint(Solver* const solver, const std::vector<IntervalVar*>& vars,

260 IntervalVar* const cover_var)

261 : TreeArrayConstraint(solver, vars, cover_var), cover_demon_(nullptr) {}

262

263 ~CoverConstraint() override {}

264

265 void Post() override {

266 for (int i = 0; i < vars_.size(); ++i) {

268 solver(), this, &CoverConstraint::LeafChanged, "LeafChanged", i);

269 vars_[i]->WhenStartRange(demon);

270 vars_[i]->WhenEndRange(demon);

271 vars_[i]->WhenPerformedBound(demon);

272 }

274 solver(), this, &CoverConstraint::CoverVarChanged, "CoverVarChanged"));

275 target_var_->WhenStartRange(cover_demon_);

276 target_var_->WhenEndRange(cover_demon_);

277 target_var_->WhenPerformedBound(cover_demon_);

278 }

279

280 void InitialPropagate() override {

281

282 for (int i = 0; i < vars_.size(); ++i) {

283 InitLeaf(i, VarStartMin(i), VarStartMax(i), VarEndMin(i), VarEndMax(i),

284 VarPerformed(i));

285 }

286

287

288 for (int i = MaxDepth() - 1; i >= 0; --i) {

289 for (int j = 0; j < Width(i); ++j) {

290 int64_t bucket_start_min = std::numeric_limits<int64_t>::max();

291 int64_t bucket_start_max = std::numeric_limits<int64_t>::max();

292 int64_t bucket_end_min = std::numeric_limits<int64_t>::min();

293 int64_t bucket_end_max = std::numeric_limits<int64_t>::min();

294 bool one_undecided = false;

295 const PerformedStatus up_performed = ComputePropagationUp(

296 i, j, &bucket_start_min, &bucket_start_max, &bucket_end_min,

297 &bucket_end_max, &one_undecided);

298 InitNode(i, j, bucket_start_min, bucket_start_max, bucket_end_min,

299 bucket_end_max, up_performed);

300 }

301 }

302

303 PropagateRoot();

304 }

305

306 void PropagateRoot() {

307

308 switch (RootPerformed()) {

309 case UNPERFORMED:

310 target_var_->SetPerformed(false);

311 break;

312 case PERFORMED:

313 target_var_->SetPerformed(true);

314 ABSL_FALLTHROUGH_INTENDED;

315 case UNDECIDED:

316 target_var_->SetStartRange(RootStartMin(), RootStartMax());

317 target_var_->SetEndRange(RootEndMin(), RootEndMax());

318 break;

319 }

320

321

322

323 CoverVarChanged();

324 }

325

326

327 void CoverVarChanged() {

328 PushDown(0, 0, TargetVarStartMin(), TargetVarStartMax(), TargetVarEndMin(),

329 TargetVarEndMax(), TargetVarPerformed());

330 }

331

332 void PushDown(int depth, int position, int64_t new_start_min,

333 int64_t new_start_max, int64_t new_end_min, int64_t new_end_max,

334 PerformedStatus performed) {

335

336

337 if (new_start_min <= StartMin(depth, position) &&

338 new_start_max >= StartMax(depth, position) &&

339 new_end_min <= EndMin(depth, position) &&

340 new_end_max >= EndMax(depth, position) &&

341 (performed == UNDECIDED || performed == Performed(depth, position))) {

342 return;

343 }

344

345 if (IsLeaf(depth)) {

346 switch (performed) {

347 case UNPERFORMED:

348 vars_[position]->SetPerformed(false);

349 break;

350 case PERFORMED:

351 vars_[position]->SetPerformed(true);

352 ABSL_FALLTHROUGH_INTENDED;

353 case UNDECIDED:

354 vars_[position]->SetStartRange(new_start_min, new_start_max);

355 vars_[position]->SetEndRange(new_end_min, new_end_max);

356 }

357 return;

358 }

359

360 const int block_start = ChildStart(position);

361 const int block_end = ChildEnd(depth, position);

362

363 switch (performed) {

364 case UNPERFORMED: {

365 for (int i = block_start; i <= block_end; ++i) {

366 PushDown(depth + 1, i, new_start_min, new_start_max, new_end_min,

367 new_end_max, UNPERFORMED);

368 }

369 break;

370 }

371 case PERFORMED: {

372 int candidate = -1;

373 int may_be_performed_count = 0;

374 int must_be_performed_count = 0;

375 for (int i = block_start; i <= block_end; ++i) {

376 switch (Performed(depth + 1, i)) {

377 case UNPERFORMED:

378 break;

379 case PERFORMED:

380 must_be_performed_count++;

381 ABSL_FALLTHROUGH_INTENDED;

382 case UNDECIDED:

383 may_be_performed_count++;

384 candidate = i;

385 }

386 }

387 if (may_be_performed_count == 0) {

388 solver()->Fail();

389 } else if (may_be_performed_count == 1) {

390 PushDown(depth + 1, candidate, new_start_min, new_start_max,

391 new_end_min, new_end_max, PERFORMED);

392 } else {

393 for (int i = block_start; i <= block_end; ++i) {

394

395

396

397

398 PushDown(depth + 1, i, new_start_min, new_end_max, new_start_min,

399 new_end_max, UNDECIDED);

400 }

401 }

402 break;

403 }

404 case UNDECIDED: {

405 for (int i = block_start; i <= block_end; ++i) {

406

407

408

409

410 PushDown(depth + 1, i, new_start_min, new_end_max, new_start_min,

411 new_end_max, UNDECIDED);

412 }

413 }

414 }

415 }

416

417 void LeafChanged(int term_index) {

418 ReduceDomain(MaxDepth(), term_index, VarStartMin(term_index),

419 VarStartMax(term_index), VarEndMin(term_index),

420 VarEndMax(term_index), VarPerformed(term_index));

421

422 const int parent = Parent(term_index);

423 const int parent_depth = MaxDepth() - 1;

424 const int64_t parent_start_min = StartMin(parent_depth, parent);

425 const int64_t parent_start_max = StartMax(parent_depth, parent);

426 const int64_t parent_end_min = EndMin(parent_depth, parent);

427 const int64_t parent_end_max = EndMax(parent_depth, parent);

428 IntervalVar* const var = vars_[term_index];

429 const bool performed_bound = var->IsPerformedBound();

430 const bool was_performed_bound = var->WasPerformedBound();

431 if (performed_bound == was_performed_bound && var->MayBePerformed() &&

432 var->OldStartMin() != parent_start_min &&

433 var->OldStartMax() != parent_start_max &&

434 var->OldEndMin() != parent_end_min &&

435 var->OldEndMax() != parent_end_max) {

436

437

438 return;

439 }

440 PushUp(term_index);

441 }

442

443 void PushUp(int position) {

444 int depth = MaxDepth();

445 while (depth > 0) {

446 const int parent = Parent(position);

447 const int parent_depth = depth - 1;

448 int64_t bucket_start_min = std::numeric_limits<int64_t>::max();

449 int64_t bucket_start_max = std::numeric_limits<int64_t>::max();

450 int64_t bucket_end_min = std::numeric_limits<int64_t>::min();

451 int64_t bucket_end_max = std::numeric_limits<int64_t>::min();

452 bool one_undecided = false;

453 const PerformedStatus status_up = ComputePropagationUp(

454 parent_depth, parent, &bucket_start_min, &bucket_start_max,

455 &bucket_end_min, &bucket_end_max, &one_undecided);

456 if (bucket_start_min > StartMin(parent_depth, parent) ||

457 bucket_start_max < StartMax(parent_depth, parent) ||

458 bucket_end_min > EndMin(parent_depth, parent) ||

459 bucket_end_max < EndMax(parent_depth, parent) ||

460 status_up != Performed(parent_depth, parent)) {

461 ReduceDomain(parent_depth, parent, bucket_start_min, bucket_start_max,

462 bucket_end_min, bucket_end_max, status_up);

463 } else {

464 if (one_undecided && TargetVarPerformed() == PERFORMED) {

465

466

467 PropagateRoot();

468 }

469

470 return;

471 }

472 depth = parent_depth;

473 position = parent;

474 }

475 DCHECK_EQ(0, depth);

476 PropagateRoot();

477 }

478

479 std::string DebugString() const override {

481 }

482

483 void Accept(ModelVisitor* const visitor) const override {

485 }

486

487 private:

488 PerformedStatus ComputePropagationUp(int parent_depth, int parent_position,

489 int64_t* const bucket_start_min,

490 int64_t* const bucket_start_max,

491 int64_t* const bucket_end_min,

492 int64_t* const bucket_end_max,

493 bool* one_undecided) {

494 *bucket_start_min = std::numeric_limits<int64_t>::max();

495 *bucket_start_max = std::numeric_limits<int64_t>::max();

496 *bucket_end_min = std::numeric_limits<int64_t>::min();

497 *bucket_end_max = std::numeric_limits<int64_t>::min();

498

499 int may_be_performed_count = 0;

500 int must_be_performed_count = 0;

501 const int block_start = ChildStart(parent_position);

502 const int block_end = ChildEnd(parent_depth, parent_position);

503 for (int k = block_start; k <= block_end; ++k) {

504 const PerformedStatus performed = Performed(parent_depth + 1, k);

505 if (performed != UNPERFORMED) {

506 *bucket_start_min =

507 std::min(*bucket_start_min, StartMin(parent_depth + 1, k));

508 *bucket_end_max =

509 std::max(*bucket_end_max, EndMax(parent_depth + 1, k));

510 may_be_performed_count++;

511 if (performed == PERFORMED) {

512 *bucket_start_max =

513 std::min(*bucket_start_max, StartMax(parent_depth + 1, k));

514 *bucket_end_min =

515 std::max(*bucket_end_min, EndMin(parent_depth + 1, k));

516 must_be_performed_count++;

517 }

518 }

519 }

520 const PerformedStatus up_performed =

521 must_be_performed_count > 0

522 ? PERFORMED

523 : (may_be_performed_count > 0 ? UNDECIDED : UNPERFORMED);

524 *one_undecided =

525 (may_be_performed_count == 1) && (must_be_performed_count == 0);

526 return up_performed;

527 }

528

529 Demon* cover_demon_;

530};

531

532class IntervalEquality : public Constraint {

533 public:

534 IntervalEquality(Solver* const solver, IntervalVar* const var1,

535 IntervalVar* const var2)

536 : Constraint(solver), var1_(var1), var2_(var2) {}

537

538 ~IntervalEquality() override {}

539

540 void Post() override {

541 Demon* const demon = solver()->MakeConstraintInitialPropagateCallback(this);

542 var1_->WhenAnything(demon);

543 var2_->WhenAnything(demon);

544 }

545

546 void InitialPropagate() override {

547

548 if (!var1_->MayBePerformed()) {

549 var2_->SetPerformed(false);

550 } else {

551 if (var1_->MustBePerformed()) {

552 var2_->SetPerformed(true);

553 }

554 var2_->SetStartRange(var1_->StartMin(), var1_->StartMax());

555 var2_->SetDurationRange(var1_->DurationMin(), var1_->DurationMax());

556 var2_->SetEndRange(var1_->EndMin(), var1_->EndMax());

557 }

558 if (!var2_->MayBePerformed()) {

559 var1_->SetPerformed(false);

560 } else {

561 if (var2_->MustBePerformed()) {

562 var1_->SetPerformed(true);

563 }

564 var1_->SetStartRange(var2_->StartMin(), var2_->StartMax());

565 var1_->SetDurationRange(var2_->DurationMin(), var2_->DurationMax());

566 var1_->SetEndRange(var2_->EndMin(), var2_->EndMax());

567 }

568 }

569

570 std::string DebugString() const override {

571 return absl::StrFormat("Equality(%s, %s)", var1_->DebugString(),

572 var2_->DebugString());

573 }

574

575 void Accept(ModelVisitor* const visitor) const override {

580 }

581

582 private:

583 IntervalVar* const var1_;

584 IntervalVar* const var2_;

585};

586}

587

597

602}