16#include "absl/container/flat_hash_map.h"
17#include "absl/container/flat_hash_set.h"
18#include "absl/strings/str_format.h"
19#include "absl/strings/str_join.h"
50 if (bits_.
Value() == 0) {
61 bits_(new
uint64[length_]),
62 stamps_(new
uint64[length_]) {
64 memset(bits_, 0,
sizeof(*bits_) * length_);
65 memset(stamps_, 0,
sizeof(*stamps_) * length_);
73void RevBitSet::Save(
Solver*
const solver,
int offset) {
75 if (current_stamp > stamps_[offset]) {
76 stamps_[offset] = current_stamp;
86 if (!(bits_[offset] &
OneBit64(pos))) {
99 bits_[offset] &= ~OneBit64(pos);
111 for (
int i = 0; i < length_; ++i) {
118 for (
int i = 0; i < length_; ++i) {
127 bool found_one =
false;
128 for (
int i = 0; i < length_; ++i) {
129 const uint64 partial = bits_[i];
131 if (!(partial & (partial - 1))) {
149 for (
int offset = 0; offset < length_; ++offset) {
151 Save(solver, offset);
152 bits_[offset] = uint64_t{0};
160 :
RevBitSet(rows * columns), rows_(rows), columns_(columns) {
186 const int start =
row * columns_;
196 const int start =
row * columns_;
205 const int beginning =
row * columns_;
206 const int end = beginning + columns_ - 1;
208 if (position == -1) {
211 return position - beginning;
222 : bit_size_(bit_size),
224 bits_(word_size_, 0),
225 active_words_(word_size_) {}
228 const std::vector<uint64>& mask) {
230 for (
int i = 0; i < mask.size(); ++i) {
233 active_words_.
Insert(solver, i);
239 const std::vector<uint64>& mask) {
240 bool changed =
false;
242 for (
int index : active_words_) {
248 to_remove_.push_back(
index);
253 CleanUpActives(solver);
257void UnsortedNullableRevBitset::CleanUpActives(
Solver*
const solver) {
260 for (
int i = to_remove_.size() - 1; i >= 0; --i) {
261 active_words_.
Remove(solver, to_remove_[i]);
266 const std::vector<uint64>& mask) {
267 bool changed =
false;
269 for (
int index : active_words_) {
270 if (
index < mask.size()) {
276 to_remove_.push_back(
index);
283 to_remove_.push_back(
index);
286 CleanUpActives(solver);
291 int* support_index) {
294 if (mask[*support_index] & bits_[*support_index]) {
297 for (
int index : active_words_) {
299 *support_index =
index;
311 PrintModelVisitor() : indent_(0) {}
312 ~PrintModelVisitor()
override {}
315 void BeginVisitModel(
const std::string& solver_name)
override {
316 LOG(
INFO) <<
"Model " << solver_name <<
" {";
320 void EndVisitModel(
const std::string& solver_name)
override {
326 void BeginVisitConstraint(
const std::string& type_name,
327 const Constraint*
const constraint)
override {
328 LOG(
INFO) << Spaces() << type_name;
332 void EndVisitConstraint(
const std::string& type_name,
333 const Constraint*
const constraint)
override {
337 void BeginVisitIntegerExpression(
const std::string& type_name,
338 const IntExpr*
const expr)
override {
339 LOG(
INFO) << Spaces() << type_name;
343 void EndVisitIntegerExpression(
const std::string& type_name,
344 const IntExpr*
const expr)
override {
348 void BeginVisitExtension(
const std::string& type_name)
override {
349 LOG(
INFO) << Spaces() << type_name;
353 void EndVisitExtension(
const std::string& type_name)
override { Decrease(); }
355 void VisitIntegerVariable(
const IntVar*
const variable,
356 IntExpr*
const delegate)
override {
357 if (delegate !=
nullptr) {
358 delegate->Accept(
this);
360 if (variable->Bound() && variable->name().empty()) {
361 LOG(
INFO) << Spaces() << variable->Min();
363 LOG(
INFO) << Spaces() << variable->DebugString();
368 void VisitIntegerVariable(
const IntVar*
const variable,
370 IntVar*
const delegate)
override {
371 LOG(
INFO) << Spaces() <<
"IntVar";
374 LOG(
INFO) << Spaces() << operation;
375 delegate->Accept(
this);
379 void VisitIntervalVariable(
const IntervalVar*
const variable,
381 IntervalVar*
const delegate)
override {
382 if (delegate !=
nullptr) {
383 LOG(
INFO) << Spaces() << operation <<
" <" <<
value <<
", ";
385 delegate->Accept(
this);
389 LOG(
INFO) << Spaces() << variable->DebugString();
393 void VisitSequenceVariable(
const SequenceVar*
const sequence)
override {
394 LOG(
INFO) << Spaces() << sequence->DebugString();
398 void VisitIntegerArgument(
const std::string& arg_name,
int64 value)
override {
402 void VisitIntegerArrayArgument(
const std::string& arg_name,
403 const std::vector<int64>& values)
override {
404 LOG(
INFO) << Spaces() << arg_name <<
": [" << absl::StrJoin(values,
", ")
408 void VisitIntegerMatrixArgument(
const std::string& arg_name,
409 const IntTupleSet& values)
override {
410 const int rows = values.NumTuples();
411 const int columns = values.Arity();
412 std::string array =
"[";
413 for (
int i = 0; i < rows; ++i) {
418 for (
int j = 0; j < columns; ++j) {
422 absl::StrAppendFormat(&array,
"%d", values.Value(i, j));
427 LOG(
INFO) << Spaces() << arg_name <<
": " << array;
430 void VisitIntegerExpressionArgument(
const std::string& arg_name,
431 IntExpr*
const argument)
override {
432 set_prefix(absl::StrFormat(
"%s: ", arg_name));
434 argument->Accept(
this);
438 void VisitIntegerVariableArrayArgument(
439 const std::string& arg_name,
440 const std::vector<IntVar*>& arguments)
override {
441 LOG(
INFO) << Spaces() << arg_name <<
": [";
443 for (
int i = 0; i < arguments.size(); ++i) {
444 arguments[i]->Accept(
this);
451 void VisitIntervalArgument(
const std::string& arg_name,
452 IntervalVar*
const argument)
override {
453 set_prefix(absl::StrFormat(
"%s: ", arg_name));
455 argument->Accept(
this);
459 virtual void VisitIntervalArgumentArray(
460 const std::string& arg_name,
const std::vector<IntervalVar*>& arguments) {
461 LOG(
INFO) << Spaces() << arg_name <<
": [";
463 for (
int i = 0; i < arguments.size(); ++i) {
464 arguments[i]->Accept(
this);
471 void VisitSequenceArgument(
const std::string& arg_name,
472 SequenceVar*
const argument)
override {
473 set_prefix(absl::StrFormat(
"%s: ", arg_name));
475 argument->Accept(
this);
479 virtual void VisitSequenceArgumentArray(
480 const std::string& arg_name,
const std::vector<SequenceVar*>& arguments) {
481 LOG(
INFO) << Spaces() << arg_name <<
": [";
483 for (
int i = 0; i < arguments.size(); ++i) {
484 arguments[i]->Accept(
this);
490 std::string DebugString()
const override {
return "PrintModelVisitor"; }
493 void Increase() { indent_ += 2; }
495 void Decrease() { indent_ -= 2; }
497 std::string Spaces() {
499 for (
int i = 0; i < indent_ - 2 * (!prefix_.empty()); ++i) {
502 if (!prefix_.empty()) {
503 result.append(prefix_);
509 void set_prefix(
const std::string& prefix) { prefix_ = prefix; }
517class ModelStatisticsVisitor :
public ModelVisitor {
519 ModelStatisticsVisitor()
520 : num_constraints_(0),
526 num_extensions_(0) {}
528 ~ModelStatisticsVisitor()
override {}
531 void BeginVisitModel(
const std::string& solver_name)
override {
533 num_constraints_ = 0;
535 num_expressions_ = 0;
540 already_visited_.clear();
541 constraint_types_.clear();
542 expression_types_.clear();
543 extension_types_.clear();
546 void EndVisitModel(
const std::string& solver_name)
override {
549 LOG(
INFO) <<
" - " << num_constraints_ <<
" constraints.";
550 for (
const auto& it : constraint_types_) {
551 LOG(
INFO) <<
" * " << it.second <<
" " << it.first;
553 LOG(
INFO) <<
" - " << num_variables_ <<
" integer variables.";
554 LOG(
INFO) <<
" - " << num_expressions_ <<
" integer expressions.";
555 for (
const auto& it : expression_types_) {
556 LOG(
INFO) <<
" * " << it.second <<
" " << it.first;
558 LOG(
INFO) <<
" - " << num_casts_ <<
" expressions casted into variables.";
559 LOG(
INFO) <<
" - " << num_intervals_ <<
" interval variables.";
560 LOG(
INFO) <<
" - " << num_sequences_ <<
" sequence variables.";
561 LOG(
INFO) <<
" - " << num_extensions_ <<
" model extensions.";
562 for (
const auto& it : extension_types_) {
563 LOG(
INFO) <<
" * " << it.second <<
" " << it.first;
567 void BeginVisitConstraint(
const std::string& type_name,
568 const Constraint*
const constraint)
override {
570 AddConstraintType(type_name);
573 void BeginVisitIntegerExpression(
const std::string& type_name,
574 const IntExpr*
const expr)
override {
575 AddExpressionType(type_name);
579 void BeginVisitExtension(
const std::string& type_name)
override {
580 AddExtensionType(type_name);
584 void VisitIntegerVariable(
const IntVar*
const variable,
585 IntExpr*
const delegate)
override {
590 VisitSubArgument(delegate);
594 void VisitIntegerVariable(
const IntVar*
const variable,
596 IntVar*
const delegate)
override {
600 VisitSubArgument(delegate);
603 void VisitIntervalVariable(
const IntervalVar*
const variable,
605 IntervalVar*
const delegate)
override {
608 VisitSubArgument(delegate);
612 void VisitSequenceVariable(
const SequenceVar*
const sequence)
override {
614 for (
int i = 0; i < sequence->size(); ++i) {
615 VisitSubArgument(sequence->Interval(i));
620 void VisitIntegerExpressionArgument(
const std::string& arg_name,
621 IntExpr*
const argument)
override {
622 VisitSubArgument(argument);
625 void VisitIntegerVariableArrayArgument(
626 const std::string& arg_name,
627 const std::vector<IntVar*>& arguments)
override {
628 for (
int i = 0; i < arguments.size(); ++i) {
629 VisitSubArgument(arguments[i]);
634 void VisitIntervalArgument(
const std::string& arg_name,
635 IntervalVar*
const argument)
override {
636 VisitSubArgument(argument);
639 void VisitIntervalArrayArgument(
640 const std::string& arg_name,
641 const std::vector<IntervalVar*>& arguments)
override {
642 for (
int i = 0; i < arguments.size(); ++i) {
643 VisitSubArgument(arguments[i]);
648 void VisitSequenceArgument(
const std::string& arg_name,
649 SequenceVar*
const argument)
override {
650 VisitSubArgument(argument);
653 void VisitSequenceArrayArgument(
654 const std::string& arg_name,
655 const std::vector<SequenceVar*>& arguments)
override {
656 for (
int i = 0; i < arguments.size(); ++i) {
657 VisitSubArgument(arguments[i]);
661 std::string DebugString()
const override {
return "ModelStatisticsVisitor"; }
664 void Register(
const BaseObject*
const object) {
665 already_visited_.insert(
object);
668 bool AlreadyVisited(
const BaseObject*
const object) {
673 template <
typename T>
674 void VisitSubArgument(T*
object) {
675 if (!AlreadyVisited(
object)) {
677 object->Accept(
this);
681 void AddConstraintType(
const std::string& constraint_type) {
682 constraint_types_[constraint_type]++;
685 void AddExpressionType(
const std::string& expression_type) {
686 expression_types_[expression_type]++;
689 void AddExtensionType(
const std::string& extension_type) {
690 extension_types_[extension_type]++;
693 absl::flat_hash_map<std::string, int> constraint_types_;
694 absl::flat_hash_map<std::string, int> expression_types_;
695 absl::flat_hash_map<std::string, int> extension_types_;
696 int num_constraints_;
698 int num_expressions_;
703 absl::flat_hash_set<const BaseObject*> already_visited_;
708class VariableDegreeVisitor :
public ModelVisitor {
710 explicit VariableDegreeVisitor(
711 absl::flat_hash_map<const IntVar*, int>*
const map)
714 ~VariableDegreeVisitor()
override {}
717 void VisitIntegerVariable(
const IntVar*
const variable,
718 IntExpr*
const delegate)
override {
719 IntVar*
const var =
const_cast<IntVar*
>(variable);
724 VisitSubArgument(delegate);
728 void VisitIntegerVariable(
const IntVar*
const variable,
730 IntVar*
const delegate)
override {
731 IntVar*
const var =
const_cast<IntVar*
>(variable);
735 VisitSubArgument(delegate);
738 void VisitIntervalVariable(
const IntervalVar*
const variable,
740 IntervalVar*
const delegate)
override {
742 VisitSubArgument(delegate);
746 void VisitSequenceVariable(
const SequenceVar*
const sequence)
override {
747 for (
int i = 0; i < sequence->size(); ++i) {
748 VisitSubArgument(sequence->Interval(i));
753 void VisitIntegerExpressionArgument(
const std::string& arg_name,
754 IntExpr*
const argument)
override {
755 VisitSubArgument(argument);
758 void VisitIntegerVariableArrayArgument(
759 const std::string& arg_name,
760 const std::vector<IntVar*>& arguments)
override {
761 for (
int i = 0; i < arguments.size(); ++i) {
762 VisitSubArgument(arguments[i]);
767 void VisitIntervalArgument(
const std::string& arg_name,
768 IntervalVar*
const argument)
override {
769 VisitSubArgument(argument);
772 void VisitIntervalArrayArgument(
773 const std::string& arg_name,
774 const std::vector<IntervalVar*>& arguments)
override {
775 for (
int i = 0; i < arguments.size(); ++i) {
776 VisitSubArgument(arguments[i]);
781 void VisitSequenceArgument(
const std::string& arg_name,
782 SequenceVar*
const argument)
override {
783 VisitSubArgument(argument);
786 void VisitSequenceArrayArgument(
787 const std::string& arg_name,
788 const std::vector<SequenceVar*>& arguments)
override {
789 for (
int i = 0; i < arguments.size(); ++i) {
790 VisitSubArgument(arguments[i]);
794 std::string DebugString()
const override {
return "VariableDegreeVisitor"; }
798 template <
typename T>
799 void VisitSubArgument(T*
object) {
800 object->Accept(
this);
803 absl::flat_hash_map<const IntVar*, int>*
const map_;
808 return RevAlloc(
new PrintModelVisitor);
812 return RevAlloc(
new ModelStatisticsVisitor);
816 absl::flat_hash_map<const IntVar*, int>*
const map) {
817 return RevAlloc(
new VariableDegreeVisitor(map));
823 std::vector<int64> result(
input.size());
824 for (
int i = 0; i <
input.size(); ++i) {
825 result[i] =
input[i];
#define DCHECK_LE(val1, val2)
#define CHECK_EQ(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define CHECK_LE(val1, val2)
void SetValue(Solver *const s, int index, const T &val)
int64 GetFirstBit(int row, int start) const
Returns the first bit in the row 'row' which position is >= 'start'.
void SetToOne(Solver *const solver, int64 row, int64 column)
Sets the 'column' bit in the 'row' row.
void ClearAll(Solver *const solver)
Cleans all bits.
void SetToZero(Solver *const solver, int64 row, int64 column)
Erases the 'column' bit in the 'row' row.
This class represents a reversible bitset.
bool IsCardinalityOne() const
Does it contains only one bit set?
bool IsSet(int64 index) const
Returns whether the 'index' bit is set.
void SetToOne(Solver *const solver, int64 index)
Sets the 'index' bit.
int64 GetFirstBit(int start) const
Gets the index of the first bit set starting from start.
void ClearAll(Solver *const solver)
Cleans all bits.
friend class RevBitMatrix
bool IsCardinalityZero() const
Is bitset null?
int64 Cardinality() const
Returns the number of bits set to one.
void SetToZero(Solver *const solver, int64 index)
Erases the 'index' bit.
void SetValue(Solver *const s, const T &val)
void Insert(Solver *const solver, const T &elt)
void Remove(Solver *const solver, const T &value_index)
void SetToZero(Solver *const solver, int64 pos)
Erases the 'pos' bit.
void SetToOne(Solver *const solver, int64 pos)
Sets the 'pos' bit.
int64 GetFirstOne() const
Gets the index of the first bit set starting from 0.
SmallRevBitSet(int64 size)
int64 Cardinality() const
Returns the number of bits set to one.
void SaveValue(T *o)
reversibility
ModelVisitor * MakeVariableDegreeVisitor(absl::flat_hash_map< const IntVar *, int > *const map)
Compute the number of constraints a variable is attached to.
uint64 stamp() const
The stamp indicates how many moves in the search tree we have performed.
ModelVisitor * MakePrintModelVisitor()
Prints the model.
T * RevAlloc(T *object)
Registers the given object as being reversible.
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
bool RevSubtract(Solver *const solver, const std::vector< uint64 > &mask)
This method subtracts the mask from the active bitset.
bool RevAnd(Solver *const solver, const std::vector< uint64 > &mask)
This method ANDs the mask with the active bitset.
bool Intersects(const std::vector< uint64 > &mask, int *support_index)
This method returns true iff the mask and the active bitset have a non null intersection.
void Init(Solver *const solver, const std::vector< uint64 > &mask)
This methods overwrites the active bitset with the mask.
UnsortedNullableRevBitset(int bit_size)
Size is the number of bits to store in the bitset.
bool ContainsKey(const Collection &collection, const Key &key)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
uint64 BitLength64(uint64 size)
bool IsBitSet64(const uint64 *const bitset, uint64 pos)
uint32 BitPos64(uint64 pos)
uint64 BitOffset64(uint64 pos)
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
int LeastSignificantBitPosition64(uint64 n)
uint64 BitCountRange64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 BitCount64(uint64 n)
bool IsEmptyRange64(const uint64 *const bitset, uint64 start, uint64 end)
static int input(yyscan_t yyscanner)