1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16#include <algorithm>

17#include <cstdint>

18#include <memory>

19#include <string>

20#include <utility>

21#include <vector>

22

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

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

29

31namespace {

32

33class BaseAllDifferent : public Constraint {

34 public:

35 BaseAllDifferent(Solver* const s, const std::vector<IntVar*>& vars)

36 : Constraint(s), vars_(vars) {}

37 ~BaseAllDifferent() override {}

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

39 return absl::StrFormat("%s(%s)", name, JoinDebugStringPtr(vars_, ", "));

40 }

41

42 protected:

43 const std::vector<IntVar*> vars_;

44 int64_t size() const { return vars_.size(); }

45};

46

47

48

49

50class ValueAllDifferent : public BaseAllDifferent {

51 public:

52 ValueAllDifferent(Solver* const s, const std::vector<IntVar*>& vars)

53 : BaseAllDifferent(s, vars) {}

54 ~ValueAllDifferent() override {}

55

56 void Post() override;

57 void InitialPropagate() override;

58 void OneMove(int index);

59 bool AllMoves();

60

61 std::string DebugString() const override {

62 return DebugStringInternal("ValueAllDifferent");

63 }

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

67 vars_);

70 }

71

72 private:

73 RevSwitch all_instantiated_;

74};

75

76void ValueAllDifferent::Post() {

77 for (int i = 0; i < size(); ++i) {

78 IntVar* var = vars_[i];

80 "OneMove", i);

81 var->WhenBound(d);

82 }

83}

84

85void ValueAllDifferent::InitialPropagate() {

86 for (int i = 0; i < size(); ++i) {

87 if (vars_[i]->Bound()) {

88 OneMove(i);

89 }

90 }

91}

92

93void ValueAllDifferent::OneMove(int index) {

94 if (!AllMoves()) {

95 const int64_t val = vars_[index]->Value();

96 for (int j = 0; j < size(); ++j) {

97 if (index != j) {

98 if (vars_[j]->Size() < 0xFFFFFF) {

99 vars_[j]->RemoveValue(val);

100 } else {

101 solver()->AddConstraint(solver()->MakeNonEquality(vars_[j], val));

102 }

103 }

104 }

105 }

106}

107

108bool ValueAllDifferent::AllMoves() {

109 if (all_instantiated_.Switched() || size() == 0) {

110 return true;

111 }

112 for (int i = 0; i < size(); ++i) {

113 if (!vars_[i]->Bound()) {

114 return false;

115 }

116 }

117 std::unique_ptr<int64_t[]> values(new int64_t[size()]);

118 for (int i = 0; i < size(); ++i) {

119 values[i] = vars_[i]->Value();

120 }

121 std::sort(values.get(), values.get() + size());

122 for (int i = 0; i < size() - 1; ++i) {

123 if (values[i] == values[i + 1]) {

124 values.reset();

125 solver()->Fail();

126 }

127 }

128 all_instantiated_.Switch(solver());

129 return true;

130}

131

132

133

134

135class RangeBipartiteMatching {

136 public:

137 struct Interval {

138 int64_t min;

139 int64_t max;

140 int min_rank;

141 int max_rank;

142 };

143

144 RangeBipartiteMatching(Solver* const solver, int size)

145 : solver_(solver),

146 size_(size),

147 intervals_(new Interval[size + 1]),

148 min_sorted_(new Interval*[size]),

149 max_sorted_(new Interval*[size]),

150 bounds_(new int64_t[2 * size + 2]),

151 tree_(new int[2 * size + 2]),

152 diff_(new int64_t[2 * size + 2]),

153 hall_(new int[2 * size + 2]),

154 active_size_(0) {

155 for (int i = 0; i < size; ++i) {

156 max_sorted_[i] = &intervals_[i];

157 min_sorted_[i] = max_sorted_[i];

158 }

159 }

160

161 void SetRange(int index, int64_t imin, int64_t imax) {

162 intervals_[index].min = imin;

163 intervals_[index].max = imax;

164 }

165

166 bool Propagate() {

167 SortArray();

168

169 const bool modified1 = PropagateMin();

170 const bool modified2 = PropagateMax();

171 return modified1 || modified2;

172 }

173

174 int64_t Min(int index) const { return intervals_[index].min; }

175

176 int64_t Max(int index) const { return intervals_[index].max; }

177

178 private:

179

180

181 void SortArray() {

182 std::sort(min_sorted_.get(), min_sorted_.get() + size_,

183 CompareIntervalMin());

184 std::sort(max_sorted_.get(), max_sorted_.get() + size_,

185 CompareIntervalMax());

186

187 int64_t min = min_sorted_[0]->min;

188 int64_t max = max_sorted_[0]->max + 1;

189 int64_t last = min - 2;

190 bounds_[0] = last;

191

192 int i = 0;

193 int j = 0;

194 int nb = 0;

195 for (;;) {

196 if (i < size_ && min <= max) {

197 if (min != last) {

198 last = min;

199 bounds_[++nb] = last;

200 }

201 min_sorted_[i]->min_rank = nb;

202 if (++i < size_) {

203 min = min_sorted_[i]->min;

204 }

205 } else {

206 if (max != last) {

207 last = max;

208 bounds_[++nb] = last;

209 }

210 max_sorted_[j]->max_rank = nb;

211 if (++j == size_) {

212 break;

213 }

214 max = max_sorted_[j]->max + 1;

215 }

216 }

217 active_size_ = nb;

218 bounds_[nb + 1] = bounds_[nb] + 2;

219 }

220

221

222 bool PropagateMin() {

223 bool modified = false;

224

225 for (int i = 1; i <= active_size_ + 1; ++i) {

226 hall_[i] = i - 1;

227 tree_[i] = i - 1;

228 diff_[i] = bounds_[i] - bounds_[i - 1];

229 }

230

231 for (int i = 0; i < size_; ++i) {

232 const int x = max_sorted_[i]->min_rank;

233 const int y = max_sorted_[i]->max_rank;

234 int z = PathMax(tree_.get(), x + 1);

235 int j = tree_[z];

236 if (--diff_[z] == 0) {

237 tree_[z] = z + 1;

238 z = PathMax(tree_.get(), z + 1);

239 tree_[z] = j;

240 }

241 PathSet(x + 1, z, z, tree_.get());

242 if (diff_[z] < bounds_[z] - bounds_[y]) {

243 solver_->Fail();

244 }

245 if (hall_[x] > x) {

246 int w = PathMax(hall_.get(), hall_[x]);

247 max_sorted_[i]->min = bounds_[w];

248 PathSet(x, w, w, hall_.get());

249 modified = true;

250 }

251 if (diff_[z] == bounds_[z] - bounds_[y]) {

252 PathSet(hall_[y], j - 1, y, hall_.get());

253 hall_[y] = j - 1;

254 }

255 }

256 return modified;

257 }

258

259 bool PropagateMax() {

260 bool modified = false;

261

262 for (int i = 0; i <= active_size_; i++) {

263 tree_[i] = i + 1;

264 hall_[i] = i + 1;

265 diff_[i] = bounds_[i + 1] - bounds_[i];

266 }

267

268 for (int i = size_ - 1; i >= 0; --i) {

269 const int x = min_sorted_[i]->max_rank;

270 const int y = min_sorted_[i]->min_rank;

271 int z = PathMin(tree_.get(), x - 1);

272 int j = tree_[z];

273 if (--diff_[z] == 0) {

274 tree_[z] = z - 1;

275 z = PathMin(tree_.get(), z - 1);

276 tree_[z] = j;

277 }

278 PathSet(x - 1, z, z, tree_.get());

279 if (diff_[z] < bounds_[y] - bounds_[z]) {

280 solver_->Fail();

281

282 }

283 if (hall_[x] < x) {

284 int w = PathMin(hall_.get(), hall_[x]);

285 min_sorted_[i]->max = bounds_[w] - 1;

286 PathSet(x, w, w, hall_.get());

287 modified = true;

288 }

289 if (diff_[z] == bounds_[y] - bounds_[z]) {

290 PathSet(hall_[y], j + 1, y, hall_.get());

291 hall_[y] = j + 1;

292 }

293 }

294 return modified;

295 }

296

297

298

299

300

301 struct CompareIntervalMin {

302 bool operator()(const Interval* i1, const Interval* i2) const {

303 return (i1->min < i2->min);

304 }

305 };

306

307

308 struct CompareIntervalMax {

309 bool operator()(const Interval* i1, const Interval* i2) const {

310 return (i1->max < i2->max);

311 }

312 };

313

314 void PathSet(int start, int end, int to, int* const tree) {

315 int l = start;

316 while (l != end) {

317 int k = l;

318 l = tree[k];

319 tree[k] = to;

320 }

321 }

322

323 int PathMin(const int* const tree, int index) {

324 int i = index;

325 while (tree[i] < i) {

326 i = tree[i];

327 }

328 return i;

329 }

330

331 int PathMax(const int* const tree, int index) {

332 int i = index;

333 while (tree[i] > i) {

334 i = tree[i];

335 }

336 return i;

337 }

338

339 Solver* const solver_;

340 const int size_;

341 std::unique_ptr<Interval[]> intervals_;

342 std::unique_ptr<Interval*[]> min_sorted_;

343 std::unique_ptr<Interval*[]> max_sorted_;

344

345

346 std::unique_ptr<int64_t[]> bounds_;

347 std::unique_ptr<int[]> tree_;

348 std::unique_ptr<int64_t[]> diff_;

349 std::unique_ptr<int[]> hall_;

350 int active_size_;

351};

352

353class BoundsAllDifferent : public BaseAllDifferent {

354 public:

355 BoundsAllDifferent(Solver* const s, const std::vector<IntVar*>& vars)

356 : BaseAllDifferent(s, vars), matching_(s, vars.size()) {}

357

358 ~BoundsAllDifferent() override {}

359

360 void Post() override {

362 solver(), this, &BoundsAllDifferent::IncrementalPropagate,

363 "IncrementalPropagate");

364

365 for (int i = 0; i < size(); ++i) {

366 vars_[i]->WhenRange(range);

368 &BoundsAllDifferent::PropagateValue,

369 "PropagateValue", i);

370 vars_[i]->WhenBound(bound);

371 }

372 }

373

374 void InitialPropagate() override {

375 IncrementalPropagate();

376 for (int i = 0; i < size(); ++i) {

377 if (vars_[i]->Bound()) {

378 PropagateValue(i);

379 }

380 }

381 }

382

383 virtual void IncrementalPropagate() {

384 for (int i = 0; i < size(); ++i) {

385 matching_.SetRange(i, vars_[i]->Min(), vars_[i]->Max());

386 }

387

388 if (matching_.Propagate()) {

389 for (int i = 0; i < size(); ++i) {

390 vars_[i]->SetRange(matching_.Min(i), matching_.Max(i));

391 }

392 }

393 }

394

395 void PropagateValue(int index) {

396 const int64_t to_remove = vars_[index]->Value();

397 for (int j = 0; j < index; j++) {

398 if (vars_[j]->Size() < 0xFFFFFF) {

399 vars_[j]->RemoveValue(to_remove);

400 } else {

401 solver()->AddConstraint(solver()->MakeNonEquality(vars_[j], to_remove));

402 }

403 }

404 for (int j = index + 1; j < size(); j++) {

405 if (vars_[j]->Size() < 0xFFFFFF) {

406 vars_[j]->RemoveValue(to_remove);

407 } else {

408 solver()->AddConstraint(solver()->MakeNonEquality(vars_[j], to_remove));

409 }

410 }

411 }

412

413 std::string DebugString() const override {

414 return DebugStringInternal("BoundsAllDifferent");

415 }

416

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

418 visitor->BeginVisitConstraint(ModelVisitor::kAllDifferent, this);

419 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,

420 vars_);

421 visitor->VisitIntegerArgument(ModelVisitor::kRangeArgument, 1);

422 visitor->EndVisitConstraint(ModelVisitor::kAllDifferent, this);

423 }

424

425 private:

426 RangeBipartiteMatching matching_;

427};

428

429class SortConstraint : public Constraint {

430 public:

431 SortConstraint(Solver* const solver,

432 const std::vector<IntVar*>& original_vars,

433 const std::vector<IntVar*>& sorted_vars)

434 : Constraint(solver),

435 ovars_(original_vars),

436 svars_(sorted_vars),

437 mins_(original_vars.size(), 0),

438 maxs_(original_vars.size(), 0),

439 matching_(solver, original_vars.size()) {}

440

441 ~SortConstraint() override {}

442

443 void Post() override {

444 Demon* const demon =

445 solver()->MakeDelayedConstraintInitialPropagateCallback(this);

446 for (int i = 0; i < size(); ++i) {

447 ovars_[i]->WhenRange(demon);

448 svars_[i]->WhenRange(demon);

449 }

450 }

451

452 void InitialPropagate() override {

453 for (int i = 0; i < size(); ++i) {

454 int64_t vmin = 0;

455 int64_t vmax = 0;

456 ovars_[i]->Range(&vmin, &vmax);

457 mins_[i] = vmin;

458 maxs_[i] = vmax;

459 }

460

461 std::sort(mins_.begin(), mins_.end());

462 std::sort(maxs_.begin(), maxs_.end());

463 for (int i = 0; i < size(); ++i) {

464 svars_[i]->SetRange(mins_[i], maxs_[i]);

465 }

466

467 for (int i = 0; i < size() - 1; ++i) {

468 svars_[i + 1]->SetMin(svars_[i]->Min());

469 }

470 for (int i = size() - 1; i > 0; --i) {

471 svars_[i - 1]->SetMax(svars_[i]->Max());

472 }

473

474 for (int i = 0; i < size(); ++i) {

475 int64_t imin = 0;

476 int64_t imax = 0;

477 FindIntersectionRange(i, &imin, &imax);

478 matching_.SetRange(i, imin, imax);

479 }

480 matching_.Propagate();

481 for (int i = 0; i < size(); ++i) {

482 const int64_t vmin = svars_[matching_.Min(i)]->Min();

483 const int64_t vmax = svars_[matching_.Max(i)]->Max();

484 ovars_[i]->SetRange(vmin, vmax);

485 }

486 }

487

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

489 visitor->BeginVisitConstraint(ModelVisitor::kSortingConstraint, this);

490 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,

491 ovars_);

492 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kTargetArgument,

493 svars_);

494 visitor->EndVisitConstraint(ModelVisitor::kSortingConstraint, this);

495 }

496

497 std::string DebugString() const override {

498 return absl::StrFormat("Sort(%s, %s)", JoinDebugStringPtr(ovars_, ", "),

500 }

501

502 private:

503 int64_t size() const { return ovars_.size(); }

504

505 void FindIntersectionRange(int index, int64_t* const range_min,

506 int64_t* const range_max) const {

507

508

509 int64_t imin = 0;

510 while (imin < size() && NotIntersect(index, imin)) {

511 imin++;

512 }

513 if (imin == size()) {

514 solver()->Fail();

515 }

516 int64_t imax = size() - 1;

517 while (imax > imin && NotIntersect(index, imax)) {

518 imax--;

519 }

520 *range_min = imin;

521 *range_max = imax;

522 }

523

524 bool NotIntersect(int oindex, int sindex) const {

525 return ovars_[oindex]->Min() > svars_[sindex]->Max() ||

526 ovars_[oindex]->Max() < svars_[sindex]->Min();

527 }

528

529 const std::vector<IntVar*> ovars_;

530 const std::vector<IntVar*> svars_;

531 std::vector<int64_t> mins_;

532 std::vector<int64_t> maxs_;

533 RangeBipartiteMatching matching_;

534};

535

536

537

538class AllDifferentExcept : public Constraint {

539 public:

540 AllDifferentExcept(Solver* const s, std::vector<IntVar*> vars,

541 int64_t escape_value)

542 : Constraint(s), vars_(std::move(vars)), escape_value_(escape_value) {}

543

544 ~AllDifferentExcept() override {}

545

546 void Post() override {

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

548 IntVar* const var = vars_[i];

550 solver(), this, &AllDifferentExcept::Propagate, "Propagate", i);

551 var->WhenBound(d);

552 }

553 }

554

555 void InitialPropagate() override {

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

557 if (vars_[i]->Bound()) {

558 Propagate(i);

559 }

560 }

561 }

562

563 void Propagate(int index) {

564 const int64_t val = vars_[index]->Value();

565 if (val != escape_value_) {

566 for (int j = 0; j < vars_.size(); ++j) {

567 if (index != j) {

568 vars_[j]->RemoveValue(val);

569 }

570 }

571 }

572 }

573

574 std::string DebugString() const override {

575 return absl::StrFormat("AllDifferentExcept([%s], %d",

577 }

578

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

580 visitor->BeginVisitConstraint(ModelVisitor::kAllDifferent, this);

581 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,

582 vars_);

583 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, escape_value_);

584 visitor->EndVisitConstraint(ModelVisitor::kAllDifferent, this);

585 }

586

587 private:

588 std::vector<IntVar*> vars_;

589 const int64_t escape_value_;

590};

591

592

593

594

595

596

597class NullIntersectArrayExcept : public Constraint {

598 public:

599 NullIntersectArrayExcept(Solver* const s, std::vector<IntVar*> first_vars,

600 std::vector<IntVar*> second_vars,

601 int64_t escape_value)

602 : Constraint(s),

603 first_vars_(std::move(first_vars)),

604 second_vars_(std::move(second_vars)),

605 escape_value_(escape_value),

606 has_escape_value_(true) {}

607

608 NullIntersectArrayExcept(Solver* const s, std::vector<IntVar*> first_vars,

609 std::vector<IntVar*> second_vars)

610 : Constraint(s),

611 first_vars_(std::move(first_vars)),

612 second_vars_(std::move(second_vars)),

613 escape_value_(0),

614 has_escape_value_(false) {}

615

616 ~NullIntersectArrayExcept() override {}

617

618 void Post() override {

619 for (int i = 0; i < first_vars_.size(); ++i) {

620 IntVar* const var = first_vars_[i];

622 solver(), this, &NullIntersectArrayExcept::PropagateFirst,

623 "PropagateFirst", i);

624 var->WhenBound(d);

625 }

626 for (int i = 0; i < second_vars_.size(); ++i) {

627 IntVar* const var = second_vars_[i];

629 solver(), this, &NullIntersectArrayExcept::PropagateSecond,

630 "PropagateSecond", i);

631 var->WhenBound(d);

632 }

633 }

634

635 void InitialPropagate() override {

636 for (int i = 0; i < first_vars_.size(); ++i) {

637 if (first_vars_[i]->Bound()) {

638 PropagateFirst(i);

639 }

640 }

641 for (int i = 0; i < second_vars_.size(); ++i) {

642 if (second_vars_[i]->Bound()) {

643 PropagateSecond(i);

644 }

645 }

646 }

647

648 void PropagateFirst(int index) {

649 const int64_t val = first_vars_[index]->Value();

650 if (!has_escape_value_ || val != escape_value_) {

651 for (int j = 0; j < second_vars_.size(); ++j) {

652 second_vars_[j]->RemoveValue(val);

653 }

654 }

655 }

656

657 void PropagateSecond(int index) {

658 const int64_t val = second_vars_[index]->Value();

659 if (!has_escape_value_ || val != escape_value_) {

660 for (int j = 0; j < first_vars_.size(); ++j) {

661 first_vars_[j]->RemoveValue(val);

662 }

663 }

664 }

665

666 std::string DebugString() const override {

667 return absl::StrFormat("NullIntersectArray([%s], [%s], escape = %d",

670 escape_value_);

671 }

672

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

674 visitor->BeginVisitConstraint(ModelVisitor::kNullIntersect, this);

675 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kLeftArgument,

676 first_vars_);

677 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kRightArgument,

678 second_vars_);

679 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, escape_value_);

680 visitor->EndVisitConstraint(ModelVisitor::kNullIntersect, this);

681 }

682

683 private:

684 std::vector<IntVar*> first_vars_;

685 std::vector<IntVar*> second_vars_;

686 const int64_t escape_value_;

687 const bool has_escape_value_;

688};

689}

690