Google OR-Tools: ortools/constraint_solver/utilities.cc Source File

14#include <cstdint>

15#include <string>

16#include <vector>

18#include "absl/container/flat_hash_map.h"

19#include "absl/container/flat_hash_set.h"

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

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

22#include "absl/strings/str_join.h"

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

35 DCHECK_GT(size, 0);

36 DCHECK_LE(size, 64);

37}

40 DCHECK_GE(pos, 0);

41 bits_.SetValue(solver, bits_.Value() | OneBit64(pos));

42}

45 DCHECK_GE(pos, 0);

46 bits_.SetValue(solver, bits_.Value() & ~OneBit64(pos));

47}

54 if (bits_.Value() == 0) {

55 return -1;

56 }

58}

63 : size_(size),

65 bits_(new uint64_t[length_]),

66 stamps_(new uint64_t[length_]) {

67 DCHECK_GE(size, 1);

68 memset(bits_.get(), 0, sizeof(bits_[0]) * length_);

69 memset(stamps_.get(), 0, sizeof(stamps_[0]) * length_);

70}

72void RevBitSet::Save(Solver* const solver, int offset) {

73 const uint64_t current_stamp = solver->stamp();

74 if (current_stamp > stamps_[offset]) {

75 stamps_[offset] = current_stamp;

76 solver->SaveValue(&bits_[offset]);

77 }

78}

81 DCHECK_GE(index, 0);

82 DCHECK_LT(index, size_);

83 const int64_t offset = BitOffset64(index);

84 const int64_t pos = BitPos64(index);

85 if (!(bits_[offset] & OneBit64(pos))) {

86 Save(solver, offset);

87 bits_[offset] |= OneBit64(pos);

88 }

89}

92 DCHECK_GE(index, 0);

93 DCHECK_LT(index, size_);

94 const int64_t offset = BitOffset64(index);

95 const int64_t pos = BitPos64(index);

96 if (bits_[offset] & OneBit64(pos)) {

97 Save(solver, offset);

99 }

100}

101

103 DCHECK_GE(index, 0);

104 DCHECK_LT(index, size_);

105 return IsBitSet64(bits_.get(), index);

106}

107

109 int64_t card = 0;

110 for (int i = 0; i < length_; ++i) {

112 }

113 return card;

114}

115

117 for (int i = 0; i < length_; ++i) {

118 if (bits_[i]) {

119 return false;

120 }

121 }

122 return true;

123}

124

126 bool found_one = false;

127 for (int i = 0; i < length_; ++i) {

128 const uint64_t partial = bits_[i];

129 if (partial) {

130 if (!(partial & (partial - 1))) {

131 if (found_one) {

132 return false;

133 }

134 found_one = true;

135 } else {

136 return false;

137 }

138 }

139 }

140 return found_one;

141}

142

146

148 for (int offset = 0; offset < length_; ++offset) {

149 if (bits_[offset]) {

150 Save(solver, offset);

151 bits_[offset] = uint64_t{0};

152 }

153 }

154}

155

156

157

159 : RevBitSet(rows * columns), rows_(rows), columns_(columns) {

160 DCHECK_GE(rows, 1);

161 DCHECK_GE(columns, 1);

162}

163

165

167 DCHECK_GE(row, 0);

168 DCHECK_LT(row, rows_);

169 DCHECK_GE(column, 0);

170 DCHECK_LT(column, columns_);

172}

173

175 int64_t column) {

176 DCHECK_GE(row, 0);

177 DCHECK_LT(row, rows_);

178 DCHECK_GE(column, 0);

179 DCHECK_LT(column, columns_);

181}

182

184 DCHECK_GE(row, 0);

185 DCHECK_LT(row, rows_);

186 const int start = row * columns_;

187 return BitCountRange64(bits_.get(), start, start + columns_ - 1);

188}

189

194

196 const int start = row * columns_;

197 return IsEmptyRange64(bits_.get(), start, start + columns_ - 1);

198}

199

201 DCHECK_GE(start, 0);

202 DCHECK_GE(row, 0);

203 DCHECK_LT(row, rows_);

204 DCHECK_LT(start, columns_);

205 const int beginning = row * columns_;

206 const int end = beginning + columns_ - 1;

207 int64_t position =

209 if (position == -1) {

210 return -1;

211 } else {

212 return position - beginning;

213 }

214}

215

219

220

221

225 bits_(word_size_, 0),

226 active_words_(word_size_) {}

227

229 const std::vector<uint64_t>& mask) {

230 CHECK_LE(mask.size(), word_size_);

231 for (int i = 0; i < mask.size(); ++i) {

232 if (mask[i]) {

233 bits_.SetValue(solver, i, mask[i]);

234 active_words_.Insert(solver, i);

235 }

236 }

237}

238

240 const std::vector<uint64_t>& mask) {

241 bool changed = false;

242 to_remove_.clear();

243 for (int index : active_words_) {

244 if (index < mask.size() && (bits_[index] & mask[index]) != 0) {

245 changed = true;

246 const uint64_t result = bits_[index] & ~mask[index];

247 bits_.SetValue(solver, index, result);

248 if (result == 0) {

249 to_remove_.push_back(index);

250 }

251 }

252 }

253

254 CleanUpActives(solver);

255 return changed;

256}

257

258void UnsortedNullableRevBitset::CleanUpActives(Solver* const solver) {

259

260

261 for (int i = to_remove_.size() - 1; i >= 0; --i) {

262 active_words_.Remove(solver, to_remove_[i]);

263 }

264}

265

267 const std::vector<uint64_t>& mask) {

268 bool changed = false;

269 to_remove_.clear();

270 for (int index : active_words_) {

271 if (index < mask.size()) {

272 if ((bits_[index] & ~mask[index]) != 0) {

273 changed = true;

274 const uint64_t result = bits_[index] & mask[index];

275 bits_.SetValue(solver, index, result);

276 if (result == 0) {

277 to_remove_.push_back(index);

278 }

279 }

280 } else {

281

282 changed = true;

283 bits_.SetValue(solver, index, 0);

284 to_remove_.push_back(index);

285 }

286 }

287 CleanUpActives(solver);

288 return changed;

289}

290

292 int* support_index) {

293 DCHECK_GE(*support_index, 0);

294 DCHECK_LT(*support_index, word_size_);

295 if (mask[*support_index] & bits_[*support_index]) {

296 return true;

297 }

298 for (int index : active_words_) {

299 if (bits_[index] & mask[index]) {

300 *support_index = index;

301 return true;

302 }

303 }

304 return false;

305}

306

307

308

309namespace {

310class PrintModelVisitor : public ModelVisitor {

311 public:

312 PrintModelVisitor() : indent_(0) {}

313 ~PrintModelVisitor() override {}

314

315

316 void BeginVisitModel(const std::string& solver_name) override {

317 LOG(INFO) << "Model " << solver_name << " {";

318 Increase();

319 }

320

321 void EndVisitModel(const std::string& solver_name) override {

322 LOG(INFO) << "}";

323 Decrease();

324 CHECK_EQ(0, indent_);

325 }

326

327 void BeginVisitConstraint(const std::string& type_name,

328 const Constraint* const constraint) override {

329 LOG(INFO) << Spaces() << type_name;

330 Increase();

331 }

332

333 void EndVisitConstraint(const std::string& type_name,

334 const Constraint* const constraint) override {

335 Decrease();

336 }

337

338 void BeginVisitIntegerExpression(const std::string& type_name,

339 const IntExpr* const expr) override {

340 LOG(INFO) << Spaces() << type_name;

341 Increase();

342 }

343

344 void EndVisitIntegerExpression(const std::string& type_name,

345 const IntExpr* const expr) override {

346 Decrease();

347 }

348

349 void BeginVisitExtension(const std::string& type_name) override {

350 LOG(INFO) << Spaces() << type_name;

351 Increase();

352 }

353

354 void EndVisitExtension(const std::string& type_name) override { Decrease(); }

355

356 void VisitIntegerVariable(const IntVar* const variable,

357 IntExpr* const delegate) override {

358 if (delegate != nullptr) {

359 delegate->Accept(this);

360 } else {

361 if (variable->Bound() && variable->name().empty()) {

362 LOG(INFO) << Spaces() << variable->Min();

363 } else {

364 LOG(INFO) << Spaces() << variable->DebugString();

365 }

366 }

367 }

368

369 void VisitIntegerVariable(const IntVar* const variable,

370 const std::string& operation, int64_t value,

371 IntVar* const delegate) override {

372 LOG(INFO) << Spaces() << "IntVar";

373 Increase();

374 LOG(INFO) << Spaces() << value;

375 LOG(INFO) << Spaces() << operation;

376 delegate->Accept(this);

377 Decrease();

378 }

379

380 void VisitIntervalVariable(const IntervalVar* const variable,

381 const std::string& operation, int64_t value,

382 IntervalVar* const delegate) override {

383 if (delegate != nullptr) {

384 LOG(INFO) << Spaces() << operation << " <" << value << ", ";

385 Increase();

386 delegate->Accept(this);

387 Decrease();

388 LOG(INFO) << Spaces() << ">";

389 } else {

390 LOG(INFO) << Spaces() << variable->DebugString();

391 }

392 }

393

394 void VisitSequenceVariable(const SequenceVar* const sequence) override {

395 LOG(INFO) << Spaces() << sequence->DebugString();

396 }

397

398

399 void VisitIntegerArgument(const std::string& arg_name,

400 int64_t value) override {

401 LOG(INFO) << Spaces() << arg_name << ": " << value;

402 }

403

404 void VisitIntegerArrayArgument(const std::string& arg_name,

405 const std::vector<int64_t>& values) override {

406 LOG(INFO) << Spaces() << arg_name << ": [" << absl::StrJoin(values, ", ")

407 << "]";

408 }

409

410 void VisitIntegerMatrixArgument(const std::string& arg_name,

411 const IntTupleSet& values) override {

412 const int rows = values.NumTuples();

413 const int columns = values.Arity();

414 std::string array = "[";

415 for (int i = 0; i < rows; ++i) {

416 if (i != 0) {

417 array.append(", ");

418 }

419 array.append("[");

420 for (int j = 0; j < columns; ++j) {

421 if (j != 0) {

422 array.append(", ");

423 }

424 absl::StrAppendFormat(&array, "%d", values.Value(i, j));

425 }

426 array.append("]");

427 }

428 array.append("]");

429 LOG(INFO) << Spaces() << arg_name << ": " << array;

430 }

431

432 void VisitIntegerExpressionArgument(const std::string& arg_name,

433 IntExpr* const argument) override {

434 set_prefix(absl::StrFormat("%s: ", arg_name));

435 Increase();

436 argument->Accept(this);

437 Decrease();

438 }

439

440 void VisitIntegerVariableArrayArgument(

441 const std::string& arg_name,

442 const std::vector<IntVar*>& arguments) override {

443 LOG(INFO) << Spaces() << arg_name << ": [";

444 Increase();

445 for (int i = 0; i < arguments.size(); ++i) {

446 arguments[i]->Accept(this);

447 }

448 Decrease();

449 LOG(INFO) << Spaces() << "]";

450 }

451

452

453 void VisitIntervalArgument(const std::string& arg_name,

454 IntervalVar* const argument) override {

455 set_prefix(absl::StrFormat("%s: ", arg_name));

456 Increase();

457 argument->Accept(this);

458 Decrease();

459 }

460

461 virtual void VisitIntervalArgumentArray(

462 const std::string& arg_name, const std::vector<IntervalVar*>& arguments) {

463 LOG(INFO) << Spaces() << arg_name << ": [";

464 Increase();

465 for (int i = 0; i < arguments.size(); ++i) {

466 arguments[i]->Accept(this);

467 }

468 Decrease();

469 LOG(INFO) << Spaces() << "]";

470 }

471

472

473 void VisitSequenceArgument(const std::string& arg_name,

474 SequenceVar* const argument) override {

475 set_prefix(absl::StrFormat("%s: ", arg_name));

476 Increase();

477 argument->Accept(this);

478 Decrease();

479 }

480

481 virtual void VisitSequenceArgumentArray(

482 const std::string& arg_name, const std::vector<SequenceVar*>& arguments) {

483 LOG(INFO) << Spaces() << arg_name << ": [";

484 Increase();

485 for (int i = 0; i < arguments.size(); ++i) {

486 arguments[i]->Accept(this);

487 }

488 Decrease();

489 LOG(INFO) << Spaces() << "]";

490 }

491

492 std::string DebugString() const override { return "PrintModelVisitor"; }

493

494 private:

495 void Increase() { indent_ += 2; }

496

497 void Decrease() { indent_ -= 2; }

498

499 std::string Spaces() {

500 std::string result;

501 for (int i = 0; i < indent_ - 2 * (!prefix_.empty()); ++i) {

502 result.append(" ");

503 }

504 if (!prefix_.empty()) {

505 result.append(prefix_);

506 prefix_ = "";

507 }

508 return result;

509 }

510

511 void set_prefix(absl::string_view prefix) { prefix_ = prefix; }

512

513 int indent_;

514 std::string prefix_;

515};

516

517

518

519class ModelStatisticsVisitor : public ModelVisitor {

520 public:

521 ModelStatisticsVisitor()

522 : num_constraints_(0),

523 num_variables_(0),

524 num_expressions_(0),

525 num_casts_(0),

526 num_intervals_(0),

527 num_sequences_(0),

528 num_extensions_(0) {}

529

530 ~ModelStatisticsVisitor() override {}

531

532

533 void BeginVisitModel(const std::string& solver_name) override {

534

535 num_constraints_ = 0;

536 num_variables_ = 0;

537 num_expressions_ = 0;

538 num_casts_ = 0;

539 num_intervals_ = 0;

540 num_sequences_ = 0;

541 num_extensions_ = 0;

542 already_visited_.clear();

543 constraint_types_.clear();

544 expression_types_.clear();

545 extension_types_.clear();

546 }

547

548 void EndVisitModel(const std::string& solver_name) override {

549

550 LOG(INFO) << "Model has:";

551 LOG(INFO) << " - " << num_constraints_ << " constraints.";

552 for (const auto& it : constraint_types_) {

553 LOG(INFO) << " * " << it.second << " " << it.first;

554 }

555 LOG(INFO) << " - " << num_variables_ << " integer variables.";

556 LOG(INFO) << " - " << num_expressions_ << " integer expressions.";

557 for (const auto& it : expression_types_) {

558 LOG(INFO) << " * " << it.second << " " << it.first;

559 }

560 LOG(INFO) << " - " << num_casts_ << " expressions casted into variables.";

561 LOG(INFO) << " - " << num_intervals_ << " interval variables.";

562 LOG(INFO) << " - " << num_sequences_ << " sequence variables.";

563 LOG(INFO) << " - " << num_extensions_ << " model extensions.";

564 for (const auto& it : extension_types_) {

565 LOG(INFO) << " * " << it.second << " " << it.first;

566 }

567 }

568

569 void BeginVisitConstraint(const std::string& type_name,

570 const Constraint* const constraint) override {

571 num_constraints_++;

572 AddConstraintType(type_name);

573 }

574

575 void BeginVisitIntegerExpression(const std::string& type_name,

576 const IntExpr* const expr) override {

577 AddExpressionType(type_name);

578 num_expressions_++;

579 }

580

581 void BeginVisitExtension(const std::string& type_name) override {

582 AddExtensionType(type_name);

583 num_extensions_++;

584 }

585

586 void VisitIntegerVariable(const IntVar* const variable,

587 IntExpr* const delegate) override {

588 num_variables_++;

589 Register(variable);

590 if (delegate) {

591 num_casts_++;

592 VisitSubArgument(delegate);

593 }

594 }

595

596 void VisitIntegerVariable(const IntVar* const variable,

597 const std::string& operation, int64_t value,

598 IntVar* const delegate) override {

599 num_variables_++;

600 Register(variable);

601 num_casts_++;

602 VisitSubArgument(delegate);

603 }

604

605 void VisitIntervalVariable(const IntervalVar* const variable,

606 const std::string& operation, int64_t value,

607 IntervalVar* const delegate) override {

608 num_intervals_++;

609 if (delegate) {

610 VisitSubArgument(delegate);

611 }

612 }

613

614 void VisitSequenceVariable(const SequenceVar* const sequence) override {

615 num_sequences_++;

616 for (int i = 0; i < sequence->size(); ++i) {

617 VisitSubArgument(sequence->Interval(i));

618 }

619 }

620

621

622 void VisitIntegerExpressionArgument(const std::string& arg_name,

623 IntExpr* const argument) override {

624 VisitSubArgument(argument);

625 }

626

627 void VisitIntegerVariableArrayArgument(

628 const std::string& arg_name,

629 const std::vector<IntVar*>& arguments) override {

630 for (int i = 0; i < arguments.size(); ++i) {

631 VisitSubArgument(arguments[i]);

632 }

633 }

634

635

636 void VisitIntervalArgument(const std::string& arg_name,

637 IntervalVar* const argument) override {

638 VisitSubArgument(argument);

639 }

640

641 void VisitIntervalArrayArgument(

642 const std::string& arg_name,

643 const std::vector<IntervalVar*>& arguments) override {

644 for (int i = 0; i < arguments.size(); ++i) {

645 VisitSubArgument(arguments[i]);

646 }

647 }

648

649

650 void VisitSequenceArgument(const std::string& arg_name,

651 SequenceVar* const argument) override {

652 VisitSubArgument(argument);

653 }

654

655 void VisitSequenceArrayArgument(

656 const std::string& arg_name,

657 const std::vector<SequenceVar*>& arguments) override {

658 for (int i = 0; i < arguments.size(); ++i) {

659 VisitSubArgument(arguments[i]);

660 }

661 }

662

663 std::string DebugString() const override { return "ModelStatisticsVisitor"; }

664

665 private:

666 void Register(const BaseObject* const object) {

667 already_visited_.insert(object);

668 }

669

670 bool AlreadyVisited(const BaseObject* const object) {

671 return already_visited_.contains(object);

672 }

673

674

675 template <typename T>

676 void VisitSubArgument(T* object) {

677 if (!AlreadyVisited(object)) {

678 Register(object);

679 object->Accept(this);

680 }

681 }

682

683 void AddConstraintType(absl::string_view constraint_type) {

684 constraint_types_[constraint_type]++;

685 }

686

687 void AddExpressionType(absl::string_view expression_type) {

688 expression_types_[expression_type]++;

689 }

690

691 void AddExtensionType(absl::string_view extension_type) {

692 extension_types_[extension_type]++;

693 }

694

695 absl::flat_hash_map<std::string, int> constraint_types_;

696 absl::flat_hash_map<std::string, int> expression_types_;

697 absl::flat_hash_map<std::string, int> extension_types_;

698 int num_constraints_;

699 int num_variables_;

700 int num_expressions_;

701 int num_casts_;

702 int num_intervals_;

703 int num_sequences_;

704 int num_extensions_;

705 absl::flat_hash_set<const BaseObject*> already_visited_;

706};

707

708

709

710class VariableDegreeVisitor : public ModelVisitor {

711 public:

712 explicit VariableDegreeVisitor(

713 absl::flat_hash_map<const IntVar*, int>* const map)

714 : map_(map) {}

715

716 ~VariableDegreeVisitor() override {}

717

718

719 void VisitIntegerVariable(const IntVar* const variable,

720 IntExpr* const delegate) override {

721 IntVar* const var = const_cast<IntVar*>(variable);

722 if (map_->contains(var)) {

723 (*map_)[var]++;

724 }

725 if (delegate) {

726 VisitSubArgument(delegate);

727 }

728 }

729

730 void VisitIntegerVariable(const IntVar* const variable,

731 const std::string& operation, int64_t value,

732 IntVar* const delegate) override {

733 IntVar* const var = const_cast<IntVar*>(variable);

734 if (map_->contains(var)) {

735 (*map_)[var]++;

736 }

737 VisitSubArgument(delegate);

738 }

739

740 void VisitIntervalVariable(const IntervalVar* const variable,

741 const std::string& operation, int64_t value,

742 IntervalVar* const delegate) override {

743 if (delegate) {

744 VisitSubArgument(delegate);

745 }

746 }

747

748 void VisitSequenceVariable(const SequenceVar* const sequence) override {

749 for (int i = 0; i < sequence->size(); ++i) {

750 VisitSubArgument(sequence->Interval(i));

751 }

752 }

753

754

755 void VisitIntegerExpressionArgument(const std::string& arg_name,

756 IntExpr* const argument) override {

757 VisitSubArgument(argument);

758 }

759

760 void VisitIntegerVariableArrayArgument(

761 const std::string& arg_name,

762 const std::vector<IntVar*>& arguments) override {

763 for (int i = 0; i < arguments.size(); ++i) {

764 VisitSubArgument(arguments[i]);

765 }

766 }

767

768

769 void VisitIntervalArgument(const std::string& arg_name,

770 IntervalVar* const argument) override {

771 VisitSubArgument(argument);

772 }

773

774 void VisitIntervalArrayArgument(

775 const std::string& arg_name,

776 const std::vector<IntervalVar*>& arguments) override {

777 for (int i = 0; i < arguments.size(); ++i) {

778 VisitSubArgument(arguments[i]);

779 }

780 }

781

782

783 void VisitSequenceArgument(const std::string& arg_name,

784 SequenceVar* const argument) override {

785 VisitSubArgument(argument);

786 }

787

788 void VisitSequenceArrayArgument(

789 const std::string& arg_name,

790 const std::vector<SequenceVar*>& arguments) override {

791 for (int i = 0; i < arguments.size(); ++i) {

792 VisitSubArgument(arguments[i]);

793 }

794 }

795

796 std::string DebugString() const override { return "VariableDegreeVisitor"; }

797

798 private:

799

800 template <typename T>

801 void VisitSubArgument(T* object) {

802 object->Accept(this);

803 }

804

805 absl::flat_hash_map<const IntVar*, int>* const map_;

806};

807}

808

810 return RevAlloc(new PrintModelVisitor);

811}

812

814 return RevAlloc(new ModelStatisticsVisitor);

815}

816

818 absl::flat_hash_map<const IntVar*, int>* const map) {

819 return RevAlloc(new VariableDegreeVisitor(map));

820}

821

822

823

825 std::vector<int64_t> result(input.size());

826 for (int i = 0; i < input.size(); ++i) {

827 result[i] = input[i];

828 }

829 return result;

830}

831}

~RevBitMatrix()

Definition utilities.cc:164

void ClearAll(Solver *solver)

Cleans all bits.

Definition utilities.cc:216

int64_t GetFirstBit(int row, int start) const

Definition utilities.cc:200

void SetToZero(Solver *solver, int64_t row, int64_t column)

Erases the 'column' bit in the 'row' row.

Definition utilities.cc:174

void SetToOne(Solver *solver, int64_t row, int64_t column)

Sets the 'column' bit in the 'row' row.

Definition utilities.cc:166

int64_t Cardinality() const

Returns the number of bits set to one.

Definition utilities.cc:108

void ClearAll(Solver *solver)

Cleans all bits.

Definition utilities.cc:147

RevBitSet(int64_t size)

Definition utilities.cc:62

void SetToZero(Solver *solver, int64_t index)

Erases the 'index' bit.

Definition utilities.cc:91

bool IsCardinalityOne() const

Does it contains only one bit set?

Definition utilities.cc:125

void SetToOne(Solver *solver, int64_t index)

Sets the 'index' bit.

Definition utilities.cc:80

friend class RevBitMatrix

bool IsSet(int64_t index) const

Returns whether the 'index' bit is set.

Definition utilities.cc:102

int64_t GetFirstBit(int start) const

Definition utilities.cc:143

bool IsCardinalityZero() const

Is bitset null?

Definition utilities.cc:116

void Remove(Solver *const solver, const T &value_index)

void SetToZero(Solver *solver, int64_t pos)

Erases the 'pos' bit.

Definition utilities.cc:44

SmallRevBitSet(int64_t size)

Definition utilities.cc:34

void SetToOne(Solver *solver, int64_t pos)

Sets the 'pos' bit.

Definition utilities.cc:39

int64_t Cardinality() const

Returns the number of bits set to one.

Definition utilities.cc:49

int64_t GetFirstOne() const

Definition utilities.cc:53

ModelVisitor * MakeVariableDegreeVisitor(absl::flat_hash_map< const IntVar *, int > *map)

Compute the number of constraints a variable is attached to.

Definition utilities.cc:817

ModelVisitor * MakePrintModelVisitor()

Prints the model.

Definition utilities.cc:809

void SaveValue(T *o)

reversibility

ModelVisitor * MakeStatisticsModelVisitor()

Displays some nice statistics on the model.

Definition utilities.cc:813

bool Intersects(const std::vector< uint64_t > &mask, int *support_index)

Definition utilities.cc:291

bool RevSubtract(Solver *solver, const std::vector< uint64_t > &mask)

Definition utilities.cc:239

void Init(Solver *solver, const std::vector< uint64_t > &mask)

Definition utilities.cc:228

int64_t bit_size() const

Returns the number of bits given in the constructor of the bitset.

UnsortedNullableRevBitset(int bit_size)

Size is the number of bits to store in the bitset.

Definition utilities.cc:222

bool RevAnd(Solver *solver, const std::vector< uint64_t > &mask)

Definition utilities.cc:266

ClosedInterval::Iterator end(ClosedInterval interval)

std::vector< int64_t > ToInt64Vector(const std::vector< int > &input)

Definition utilities.cc:824

uint32_t BitPos64(uint64_t pos)

uint64_t BitCountRange64(const uint64_t *bitset, uint64_t start, uint64_t end)

uint64_t BitCount64(uint64_t n)

bool IsBitSet64(const uint64_t *const bitset, uint64_t pos)

uint64_t OneBit64(int pos)

uint64_t BitOffset64(uint64_t pos)

bool IsEmptyRange64(const uint64_t *bitset, uint64_t start, uint64_t end)

uint64_t BitLength64(uint64_t size)

int LeastSignificantBitPosition64(uint64_t n)

static int input(yyscan_t yyscanner)