30 #ifndef OR_TOOLS_LP_DATA_SPARSE_VECTOR_H_
31 #define OR_TOOLS_LP_DATA_SPARSE_VECTOR_H_
38 #include "absl/strings/str_format.h"
49 template <
typename IndexType>
50 class SparseVectorEntry;
81 template <
typename IndexType,
82 typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>
91 using Entry =
typename Iterator::Entry;
101 #if !defined(_MSC_VER)
106 #if !defined(_MSC_VER)
303 return ::util::IntegerRange<EntryIndex>(EntryIndex(0),
num_entries_);
394 void AddMultipleToSparseVectorInternal(
410 template <
typename IndexType>
445 template <
typename IndexType,
typename IteratorType>
447 return Iterator(this->index_, this->coefficient_, EntryIndex(0));
450 template <
typename IndexType,
typename IteratorType>
452 return Iterator(this->index_, this->coefficient_, num_entries_);
458 template <
typename IndexType,
typename IteratorType>
463 coefficient_(nullptr),
464 may_contain_duplicates_(false) {}
466 template <
typename IndexType,
typename IteratorType>
468 PopulateFromSparseVector(other);
471 template <
typename IndexType,
typename IteratorType>
474 PopulateFromSparseVector(other);
478 template <
typename IndexType,
typename IteratorType>
480 num_entries_ = EntryIndex(0);
481 may_contain_duplicates_ =
false;
484 template <
typename IndexType,
typename IteratorType>
486 capacity_ = EntryIndex(0);
487 num_entries_ = EntryIndex(0);
489 coefficient_ =
nullptr;
491 may_contain_duplicates_ =
false;
494 template <
typename IndexType,
typename IteratorType>
496 if (new_capacity <= capacity_)
return;
500 if (new_capacity.value() & 3) {
501 new_capacity += EntryIndex(4 - (new_capacity.value() & 3));
504 const size_t index_buffer_size = new_capacity.value() *
sizeof(
Index);
505 const size_t value_buffer_size = new_capacity.value() *
sizeof(
Fractional);
506 const size_t new_buffer_size = index_buffer_size + value_buffer_size;
507 std::unique_ptr<char[]> new_buffer(
new char[new_buffer_size]);
508 IndexType*
const new_index =
reinterpret_cast<Index*
>(new_buffer.get());
510 reinterpret_cast<Fractional*
>(new_index + new_capacity.value());
513 if (num_entries_ > 0) {
518 std::memmove(new_index, index_,
sizeof(IndexType) * num_entries_.value());
519 std::memmove(new_coefficient, coefficient_,
522 std::swap(buffer_, new_buffer);
524 coefficient_ = new_coefficient;
525 capacity_ = new_capacity;
528 template <
typename IndexType,
typename IteratorType>
530 return num_entries_ == EntryIndex(0);
533 template <
typename IndexType,
typename IteratorType>
535 std::swap(buffer_, other->
buffer_);
539 std::swap(index_, other->
index_);
543 template <
typename IndexType,
typename IteratorType>
555 std::vector<std::pair<Index, Fractional>> entries;
556 entries.reserve(num_entries_.value());
557 for (EntryIndex i(0); i < num_entries_; ++i) {
561 entries.begin(), entries.end(),
562 [](
const std::pair<Index, Fractional>&
a,
563 const std::pair<Index, Fractional>&
b) { return a.first < b.first; });
565 EntryIndex new_size(0);
566 for (
int i = 0; i < num_entries_; ++i) {
567 const std::pair<Index, Fractional> entry = entries[i];
568 if (entry.second == 0.0)
continue;
569 if (i + 1 == num_entries_ || entry.first != entries[i + 1].first) {
570 MutableIndex(new_size) = entry.first;
571 MutableCoefficient(new_size) = entry.second;
575 ResizeDown(new_size);
576 may_contain_duplicates_ =
false;
579 template <
typename IndexType,
typename IteratorType>
581 Index previous_index(-1);
582 for (
const EntryIndex i : AllEntryIndices()) {
585 previous_index =
index;
587 may_contain_duplicates_ =
false;
591 template <
typename IndexType,
typename IteratorType>
604 std::memmove(index_, sparse_vector.
index_,
612 template <
typename IndexType,
typename IteratorType>
616 const Index num_indices(dense_vector.
size());
618 if (dense_vector[
index] != 0.0) {
622 may_contain_duplicates_ =
false;
625 template <
typename IndexType,
typename IteratorType>
633 may_contain_duplicates_ =
true;
636 template <
typename IndexType,
typename IteratorType>
642 if (!may_contain_duplicates_ || num_entries_ <= 1)
return true;
645 const Index max_index =
646 *std::max_element(index_, index_ + num_entries_.value());
647 if (boolean_vector->
size() <= max_index) {
648 boolean_vector->
resize(max_index + 1,
false);
651 may_contain_duplicates_ =
false;
652 for (
const EntryIndex i : AllEntryIndices()) {
654 if ((*boolean_vector)[
index]) {
655 may_contain_duplicates_ =
true;
658 (*boolean_vector)[
index] =
true;
662 for (
const EntryIndex i : AllEntryIndices()) {
663 (*boolean_vector)[GetIndex(i)] =
false;
665 return !may_contain_duplicates_;
668 template <
typename IndexType,
typename IteratorType>
672 if (!may_contain_duplicates_ || num_entries_ <= 1)
return true;
674 return CheckNoDuplicates(&boolean_vector);
679 template <
typename IndexType,
typename IteratorType>
683 may_contain_duplicates_ =
true;
686 template <
typename IndexType,
typename IteratorType>
688 DCHECK(CheckNoDuplicates());
691 while (i < end && GetIndex(i) !=
index) {
694 if (i == end)
return;
695 const int num_moved_entries = (num_entries_ - i).
value() - 1;
696 std::memmove(index_ + i.value(), index_ + i.value() + 1,
697 sizeof(
Index) * num_moved_entries);
698 std::memmove(coefficient_ + i.value(), coefficient_ + i.value() + 1,
703 template <
typename IndexType,
typename IteratorType>
706 DCHECK(CheckNoDuplicates());
707 EntryIndex new_index(0);
708 for (
const EntryIndex i : AllEntryIndices()) {
710 if (magnitude > threshold) {
711 MutableIndex(new_index) = GetIndex(i);
716 ResizeDown(new_index);
719 template <
typename IndexType,
typename IteratorType>
722 DCHECK(CheckNoDuplicates());
723 EntryIndex new_index(0);
724 for (
const EntryIndex i : AllEntryIndices()) {
726 MutableIndex(new_index) = GetIndex(i);
731 ResizeDown(new_index);
734 template <
typename IndexType,
typename IteratorType>
737 DCHECK(CheckNoDuplicates());
738 for (
const EntryIndex i : AllEntryIndices()) {
739 if (GetIndex(i) ==
index) {
740 std::swap(MutableIndex(EntryIndex(0)), MutableIndex(i));
741 std::swap(MutableCoefficient(EntryIndex(0)), MutableCoefficient(i));
747 template <
typename IndexType,
typename IteratorType>
750 DCHECK(CheckNoDuplicates());
752 for (
const EntryIndex i : AllEntryIndices()) {
753 if (GetIndex(i) ==
index) {
754 std::swap(MutableIndex(last_entry), MutableIndex(i));
755 std::swap(MutableCoefficient(last_entry), MutableCoefficient(i));
761 template <
typename IndexType,
typename IteratorType>
764 for (
const EntryIndex i : AllEntryIndices()) {
765 MutableCoefficient(i) *= factor;
769 template <
typename IndexType,
typename IteratorType>
772 for (
const EntryIndex i : AllEntryIndices()) {
773 MutableCoefficient(i) *= factors[GetIndex(i)];
777 template <
typename IndexType,
typename IteratorType>
780 for (
const EntryIndex i : AllEntryIndices()) {
781 MutableCoefficient(i) /= factor;
785 template <
typename IndexType,
typename IteratorType>
788 for (
const EntryIndex i : AllEntryIndices()) {
789 MutableCoefficient(i) /= factors[GetIndex(i)];
793 template <
typename IndexType,
typename IteratorType>
798 for (
const EntryIndex i : AllEntryIndices()) {
803 template <
typename IndexType,
typename IteratorType>
809 for (
const EntryIndex i : AllEntryIndices()) {
814 template <
typename IndexType,
typename IteratorType>
818 if (multiplier == 0.0)
return;
819 for (
const EntryIndex i : AllEntryIndices()) {
824 template <
typename IndexType,
typename IteratorType>
829 AddMultipleToSparseVectorInternal(
true, multiplier, removed_common_index,
830 drop_tolerance, accumulator_vector);
833 template <
typename IndexType,
typename IteratorType>
838 AddMultipleToSparseVectorInternal(
false, multiplier, removed_common_index,
839 drop_tolerance, accumulator_vector);
842 template <
typename IndexType,
typename IteratorType>
849 DCHECK(CheckNoDuplicates());
851 DCHECK_NE(0.0, LookUpCoefficient(common_index));
865 const EntryIndex size_a =
a.num_entries();
866 const EntryIndex size_b =
b.num_entries();
867 const int size_adjustment = delete_common_index ? -2 : 0;
868 const EntryIndex new_size_upper_bound = size_a + size_b + size_adjustment;
869 c.
Reserve(new_size_upper_bound);
871 while ((ia < size_a) && (ib < size_b)) {
872 const Index index_a =
a.GetIndex(ia);
873 const Index index_b =
b.GetIndex(ib);
876 if (index_a == index_b) {
877 if (index_a != common_index) {
878 const Fractional a_coeff_mul = multiplier *
a.GetCoefficient(ia);
884 if (std::abs(sum) > drop_tolerance) {
889 }
else if (!delete_common_index) {
896 }
else if (index_a < index_b) {
908 while (ia < size_a) {
914 while (ib < size_b) {
922 c.
Swap(accumulator_vector);
925 template <
typename IndexType,
typename IteratorType>
928 for (
const EntryIndex i : AllEntryIndices()) {
929 MutableIndex(i) = index_perm[GetIndex(i)];
933 template <
typename IndexType,
typename IteratorType>
936 EntryIndex new_index(0);
937 for (
const EntryIndex i : AllEntryIndices()) {
939 if (index_perm[
index] >= 0) {
940 MutableIndex(new_index) = index_perm[
index];
945 ResizeDown(new_index);
948 template <
typename IndexType,
typename IteratorType>
953 const EntryIndex end(num_entries_);
956 if (i >= end)
return;
957 if (index_perm[GetIndex(i)] >= 0)
break;
961 for (EntryIndex j(i + 1); j < end; ++j) {
962 if (index_perm[GetIndex(j)] < 0) {
963 MutableIndex(i) = GetIndex(j);
978 template <
typename IndexType,
typename IteratorType>
982 for (
const EntryIndex i : AllEntryIndices()) {
983 if (GetIndex(i) ==
index) {
994 template <
typename IndexType,
typename IteratorType>
999 for (
const EntryIndex i : AllEntryIndices()) {
1000 if (GetIndex(i) != other.
GetIndex(i))
return false;
1006 template <
typename IndexType,
typename IteratorType>
1009 for (
const EntryIndex i : AllEntryIndices()) {
1010 if (i != 0) s +=
", ";
1011 absl::StrAppendFormat(&s,
"[%d]=%g", GetIndex(i).
value(),
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
Fractional coefficient() const
const Fractional * coefficient_
SparseVectorEntry(const Index *indices, const Fractional *coefficients, EntryIndex i)
void ComponentWiseMultiply(const DenseVector &factors)
std::unique_ptr< char[]> buffer_
void PopulateFromDenseVector(const DenseVector &dense_vector)
Fractional & MutableCoefficient(EntryIndex i)
void MoveTaggedEntriesTo(const IndexPermutation &index_perm, SparseVector *output)
void Swap(SparseVector *other)
void ApplyIndexPermutation(const IndexPermutation &index_perm)
Index GetIndex(EntryIndex i) const
bool CheckNoDuplicates() const
void CopyToDenseVector(Index num_indices, DenseVector *dense_vector) const
Fractional LookUpCoefficient(Index index) const
SparseVector & operator=(const SparseVector &other)
::util::IntegerRange< EntryIndex > AllEntryIndices() const
void AddMultipleToDenseVector(Fractional multiplier, DenseVector *dense_vector) const
void ResizeDown(EntryIndex new_size)
void RemoveNearZeroEntriesWithWeights(Fractional threshold, const DenseVector &weights)
void PermutedCopyToDenseVector(const IndexPermutation &index_perm, Index num_indices, DenseVector *dense_vector) const
void AddMultipleToSparseVectorAndDeleteCommonIndex(Fractional multiplier, Index removed_common_index, Fractional drop_tolerance, SparseVector *accumulator_vector) const
bool may_contain_duplicates_
Fractional * coefficient_
std::string DebugString() const
void DivideByConstant(Fractional factor)
Index GetLastIndex() const
Index GetFirstIndex() const
void MultiplyByConstant(Fractional factor)
SparseVector(SparseVector &&other)=default
void ComponentWiseDivide(const DenseVector &factors)
typename Iterator::Entry Entry
void ApplyPartialIndexPermutation(const IndexPermutation &index_perm)
SparseVector & operator=(SparseVector &&other)=default
Permutation< Index > IndexPermutation
void AddMultipleToSparseVectorAndIgnoreCommonIndex(Fractional multiplier, Index removed_common_index, Fractional drop_tolerance, SparseVector *accumulator_vector) const
void RemoveNearZeroEntries(Fractional threshold)
void MoveEntryToFirstPosition(Index index)
bool CheckNoDuplicates(StrictITIVector< Index, bool > *boolean_vector) const
void MoveEntryToLastPosition(Index index)
void AddEntry(Index index, Fractional value)
Fractional GetLastCoefficient() const
bool IsEqualTo(const SparseVector &other) const
Fractional GetFirstCoefficient() const
void Reserve(EntryIndex new_capacity)
void DeleteEntry(Index index)
void AppendEntriesWithOffset(const SparseVector &sparse_vector, Index offset)
Fractional GetCoefficient(EntryIndex i) const
void SetCoefficient(Index index, Fractional value)
void PopulateFromSparseVector(const SparseVector &sparse_vector)
StrictITIVector< Index, Fractional > DenseVector
SparseVector(const SparseVector &other)
EntryIndex num_entries() const
Index & MutableIndex(EntryIndex i)
void AssignToZero(IntType size)
void resize(IntType size)
IntegerValue GetCoefficient(const IntegerVariable var, const LinearExpression &expr)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
#define RETURN_IF_NULL(x)
#define RETURN_VALUE_IF_NULL(x, v)
std::vector< double > coefficients