#include <sparse_vector.h>

Public Types
typedef IndexType	Index

typedef StrictITIVector< Index, Fractional >	DenseVector

typedef Permutation< Index >	IndexPermutation

using	Iterator = IteratorType

using	Entry = typename Iterator::Entry

Public Member Functions
	SparseVector ()

	SparseVector (const SparseVector &other)

	SparseVector (SparseVector &&other)=default

SparseVector &	operator= (const SparseVector &other)

SparseVector &	operator= (SparseVector &&other)=default

Iterator	begin () const

Iterator	end () const

void	Clear ()
	Clears the vector, i.e. removes all entries.

void	ClearAndRelease ()
	Clears the vector and releases the memory it uses.

void	Reserve (EntryIndex new_capacity)
	Reserve the underlying storage for the given number of entries.

bool	IsEmpty () const
	Returns true if the vector is empty.

void	CleanUp ()

bool	IsCleanedUp () const

void	Swap (SparseVector *other)

void	PopulateFromSparseVector (const SparseVector &sparse_vector)

void	PopulateFromDenseVector (const DenseVector &dense_vector)

void	AppendEntriesWithOffset (const SparseVector &sparse_vector, Index offset)

bool	CheckNoDuplicates () const

bool	CheckNoDuplicates (StrictITIVector< Index, bool > *boolean_vector) const

void	SetCoefficient (Index index, Fractional value)
	Defines the coefficient at index, i.e. vector[index] = value;.

void	DeleteEntry (Index index)

void	RemoveNearZeroEntries (Fractional threshold)

void	RemoveNearZeroEntriesWithWeights (Fractional threshold, const DenseVector &weights)

void	MoveEntryToFirstPosition (Index index)

void	MoveEntryToLastPosition (Index index)

void	MultiplyByConstant (Fractional factor)

void	ComponentWiseMultiply (const DenseVector &factors)

void	DivideByConstant (Fractional factor)

void	ComponentWiseDivide (const DenseVector &factors)

void	CopyToDenseVector (Index num_indices, DenseVector *dense_vector) const

void	PermutedCopyToDenseVector (const IndexPermutation &index_perm, Index num_indices, DenseVector *dense_vector) const

void	AddMultipleToDenseVector (Fractional multiplier, DenseVector *dense_vector) const

void	AddMultipleToSparseVectorAndDeleteCommonIndex (Fractional multiplier, Index removed_common_index, Fractional drop_tolerance, SparseVector *accumulator_vector) const

void	AddMultipleToSparseVectorAndIgnoreCommonIndex (Fractional multiplier, Index removed_common_index, Fractional drop_tolerance, SparseVector *accumulator_vector) const

void	ApplyIndexPermutation (const IndexPermutation &index_perm)
	Applies the index permutation to all entries: index = index_perm[index];.

void	ApplyPartialIndexPermutation (const IndexPermutation &index_perm)

void	MoveTaggedEntriesTo (const IndexPermutation &index_perm, SparseVector *output)

Fractional	LookUpCoefficient (Index index) const

EntryIndex	num_entries () const
	Note this method can only be used when the vector has no duplicates.

Index	GetFirstIndex () const

Fractional	GetFirstCoefficient () const

Index	GetLastIndex () const
	Like GetFirst*, but for the last entry.

Fractional	GetLastCoefficient () const

::util::IntegerRange< EntryIndex >	AllEntryIndices () const

bool	IsEqualTo (const SparseVector &other) const

std::string	DebugString () const

Protected Member Functions
void	AddEntry (Index index, Fractional value)

void	ResizeDown (EntryIndex new_size)

Index	GetIndex (EntryIndex i) const

Fractional	GetCoefficient (EntryIndex i) const

Index &	MutableIndex (EntryIndex i)

Fractional &	MutableCoefficient (EntryIndex i)

Protected Attributes
std::unique_ptr< char[]>	buffer_

EntryIndex	num_entries_

EntryIndex	capacity_

Index *	index_ = nullptr
	Pointers to the first elements of the index and coefficient arrays.

Fractional *	coefficient_ = nullptr

bool	may_contain_duplicates_

Detailed Description

template<typename IndexType, typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>
class operations_research::glop::SparseVector< IndexType, IteratorType >

SparseVector This class allows to store a vector taking advantage of its sparsity. Space complexity is in O(num_entries). In the current implementation, entries are stored in a first-in order (order of SetCoefficient() calls) when they are added; then the "cleaning" process sorts them by index (and duplicates are removed: the last entry takes precedence). Many methods assume that the entries are sorted by index and without duplicates, and DCHECK() that.

Default copy construction is fully supported.

This class uses strong integer types (i.e. no implicit cast to/from other integer types) for both:

the index of entries (eg. SparseVector<RowIndex> is a SparseColumn, see ./sparse_column.h).
the internal indices of entries in the internal storage, which is an entirely different type: EntryType. This class can be extended with a custom iterator/entry type for the iterator-based API. This can be used to extend the interface with additional methods for the entries returned by the iterators; for an example of such extension, see SparseColumnEntry in sparse_column.h. The custom entries and iterators should be derived from SparseVectorEntry and SparseVectorIterator, or at least provide the same public and protected interface.

Todo
(user): un-expose this type to client; by getting rid of the index-based APIs and leveraging iterator-based APIs; if possible.

Definition at line 87 of file sparse_vector.h.

Member Typedef Documentation

◆ DenseVector

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

StrictITIVector<Index, Fractional> operations_research::glop::SparseVector< IndexType, IteratorType >::DenseVector

Definition at line 91 of file sparse_vector.h.

◆ Entry

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

using operations_research::glop::SparseVector< IndexType, IteratorType >::Entry = typename Iterator::Entry

Definition at line 95 of file sparse_vector.h.

◆ Index

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

IndexType operations_research::glop::SparseVector< IndexType, IteratorType >::Index

Definition at line 89 of file sparse_vector.h.

◆ IndexPermutation

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Permutation<Index> operations_research::glop::SparseVector< IndexType, IteratorType >::IndexPermutation

Definition at line 92 of file sparse_vector.h.

◆ Iterator

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

using operations_research::glop::SparseVector< IndexType, IteratorType >::Iterator = IteratorType

Definition at line 94 of file sparse_vector.h.

Constructor & Destructor Documentation

◆ SparseVector() [1/3]

template<typename IndexType , typename IteratorType >

operations_research::glop::SparseVector< IndexType, IteratorType >::SparseVector ( )

SparseVector implementation

Definition at line 467 of file sparse_vector.h.

◆ SparseVector() [2/3]

template<typename IndexType , typename IteratorType >

operations_research::glop::SparseVector< IndexType, IteratorType >::SparseVector ( const SparseVector< IndexType, IteratorType > & other )

NOTE(user): STL uses the expensive copy constructor when relocating elements of a vector, unless the move constructor exists and it is marked as noexcept. However, the noexcept annotation is banned by the style guide, and the only way to get it is by using the default move constructor and assignment operator generated by the compiler.

Definition at line 475 of file sparse_vector.h.

◆ SparseVector() [3/3]

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

operations_research::glop::SparseVector< IndexType, IteratorType >::SparseVector ( SparseVector< IndexType, IteratorType > && other )

default

Member Function Documentation

◆ AddEntry()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

void operations_research::glop::SparseVector< IndexType, IteratorType >::AddEntry	(	Index	index,
		Fractional	value )

inlineprotected

Adds a new entry to the sparse vector, growing the internal buffer if needed. It does not set may_contain_duplicates_ to true.

Grow the internal storage if there is no space left for the new entry. We increase the size to max(4, 1.5*current capacity).

Reserve(capacity_ == 0 ? EntryIndex(4) : EntryIndex(2 * capacity_.value()));

Definition at line 321 of file sparse_vector.h.

◆ AddMultipleToDenseVector()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::AddMultipleToDenseVector	(	Fractional	multiplier,
		DenseVector *	dense_vector ) const

Performs the operation dense_vector += multiplier * this. This is known as multiply-accumulate or (fused) multiply-add.

Definition at line 828 of file sparse_vector.h.

◆ AddMultipleToSparseVectorAndDeleteCommonIndex()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::AddMultipleToSparseVectorAndDeleteCommonIndex	(	Fractional	multiplier,
		Index	removed_common_index,
		Fractional	drop_tolerance,
		SparseVector< IndexType, IteratorType > *	accumulator_vector ) const

Warning: BOTH vectors (the current and the destination) MUST be "clean", i.e. sorted and without duplicates. Performs the operation accumulator_vector += multiplier * this, removing a given index which must be in both vectors, and pruning new entries whose absolute value are under the given drop_tolerance.

Definition at line 838 of file sparse_vector.h.

◆ AddMultipleToSparseVectorAndIgnoreCommonIndex()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::AddMultipleToSparseVectorAndIgnoreCommonIndex	(	Fractional	multiplier,
		Index	removed_common_index,
		Fractional	drop_tolerance,
		SparseVector< IndexType, IteratorType > *	accumulator_vector ) const

Same as AddMultipleToSparseVectorAndDeleteCommonIndex() but instead of deleting the common index, leave it unchanged.

Definition at line 847 of file sparse_vector.h.

◆ AllEntryIndices()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

::util::IntegerRange< EntryIndex > operations_research::glop::SparseVector< IndexType, IteratorType >::AllEntryIndices ( ) const

inline

Allows to loop over the entry indices like this: for (const EntryIndex i : sparse_vector.AllEntryIndices()) { ... }

Todo: (user): consider removing this, in favor of the natural range iteration.

Definition at line 306 of file sparse_vector.h.

◆ AppendEntriesWithOffset()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::AppendEntriesWithOffset	(	const SparseVector< IndexType, IteratorType > &	sparse_vector,
		Index	offset )

Appends all entries from sparse_vector to the current vector; the indices of the appended entries are increased by offset. If the current vector already has a value at an index changed by this method, this value is overwritten with the value from sparse_vector.

Note: while offset may be negative itself, the indices of all entries after applying the offset must be non-negative.

Definition at line 639 of file sparse_vector.h.

◆ ApplyIndexPermutation()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::ApplyIndexPermutation ( const IndexPermutation & index_perm )

Applies the index permutation to all entries: index = index_perm[index];.

Definition at line 946 of file sparse_vector.h.

◆ ApplyPartialIndexPermutation()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::ApplyPartialIndexPermutation ( const IndexPermutation & index_perm )

Same as ApplyIndexPermutation but deletes the index if index_perm[index] is negative.

Definition at line 954 of file sparse_vector.h.

◆ begin()

template<typename IndexType , typename IteratorType >

IteratorType operations_research::glop::SparseVector< IndexType, IteratorType >::begin ( ) const

Read-only API for a given SparseVector entry. The typical way for a client to use this is to use the natural range iteration defined by the Iterator class below: SparseVector<int> v; ... for (const SparseVector<int>::Entry e : v) { LOG(INFO) << "Index: " << e.index() << ", Coeff: " << e.coefficient(); }

Note: this can only be used when the vector has no duplicates.

Note(user): using either "const SparseVector<int>::Entry&" or "const SparseVector<int>::Entry" yields the exact same performance on the netlib, thus we recommend to use the latter version, for consistency.

Definition at line 452 of file sparse_vector.h.

◆ CheckNoDuplicates() [1/2]

template<typename IndexType , typename IteratorType >

bool operations_research::glop::SparseVector< IndexType, IteratorType >::CheckNoDuplicates ( ) const

Returns true when the vector contains no duplicates. Runs in O(max_index + num_entries), max_index being the largest index in entry. This method allocates (and deletes) a Boolean array of size max_index.

Note: we use a mutable Boolean to make subsequent call runs in O(1).

Using num_entries() or any function in that will call CheckNoDuplicates() again will cause an infinite loop!

Definition at line 682 of file sparse_vector.h.

◆ CheckNoDuplicates() [2/2]

template<typename IndexType , typename IteratorType >

bool operations_research::glop::SparseVector< IndexType, IteratorType >::CheckNoDuplicates ( StrictITIVector< Index, bool > * boolean_vector ) const

Same as CheckNoDuplicates() except it uses a reusable boolean vector to make the code more efficient. Runs in O(num_entries).

Note: boolean_vector should be initialized to false before calling this method; It will remain equal to false after calls to CheckNoDuplicates().; we use a mutable Boolean to make subsequent call runs in O(1).

Note(user): Using num_entries() or any function that call CheckNoDuplicates() again will cause an infinite loop!

Update size if needed.

Reset boolean_vector to false.

Definition at line 650 of file sparse_vector.h.

◆ CleanUp()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::CleanUp ( )

Cleans the vector, i.e. removes zero-values entries, removes duplicates entries and sorts remaining entries in increasing index order. Runs in O(num_entries * log(num_entries)).

Todo: (user): Implement in-place sorting of the entries and cleanup. The current version converts the data to an array-of-pairs representation that can be sorted easily with std::stable_sort, and the converts the sorted data back to the struct-of-arrays implementation. The current version is ~20% slower than the in-place sort on the array-of-struct representation. It is not visible on GLOP benchmarks, but it increases peak memory usage by ~8%. Implementing in-place search will require either implementing a custom sorting code, or custom iterators that abstract away the internal representation.

Definition at line 552 of file sparse_vector.h.

◆ Clear()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::Clear ( )

Clears the vector, i.e. removes all entries.

Definition at line 487 of file sparse_vector.h.

◆ ClearAndRelease()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::ClearAndRelease ( )

Clears the vector and releases the memory it uses.

Definition at line 493 of file sparse_vector.h.

◆ ComponentWiseDivide()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::ComponentWiseDivide ( const DenseVector & factors )

Divides all entries by its corresponding factor, i.e. entry.coefficient /= factors[entry.index].

Definition at line 799 of file sparse_vector.h.

◆ ComponentWiseMultiply()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::ComponentWiseMultiply ( const DenseVector & factors )

Multiplies all entries by its corresponding factor, i.e. entry.coefficient *= factors[entry.index].

Definition at line 783 of file sparse_vector.h.

◆ CopyToDenseVector()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::CopyToDenseVector	(	Index	num_indices,
		DenseVector *	dense_vector ) const

Populates a dense vector from the sparse vector. Runs in O(num_indices) as the dense vector values have to be reset to 0.0.

Definition at line 807 of file sparse_vector.h.

◆ DebugString()

template<typename IndexType , typename IteratorType >

std::string operations_research::glop::SparseVector< IndexType, IteratorType >::DebugString ( ) const

An exhaustive, pretty-printed listing of the entries, in their internal order. a.DebugString() == b.DebugString() iff a.IsEqualTo(b).

Definition at line 1027 of file sparse_vector.h.

◆ DeleteEntry()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::DeleteEntry ( Index index )

Removes an entry from the vector if present. The order of the other entries is preserved. Runs in O(num_entries).

Definition at line 700 of file sparse_vector.h.

◆ DivideByConstant()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::DivideByConstant ( Fractional factor )

Divides all entries by factor. i.e. entry.coefficient /= factor.

Definition at line 791 of file sparse_vector.h.

◆ end()

template<typename IndexType , typename IteratorType >

IteratorType operations_research::glop::SparseVector< IndexType, IteratorType >::end ( ) const

Definition at line 457 of file sparse_vector.h.

◆ GetCoefficient()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Fractional operations_research::glop::SparseVector< IndexType, IteratorType >::GetCoefficient ( EntryIndex i ) const

inlineprotected

Definition at line 353 of file sparse_vector.h.

◆ GetFirstCoefficient()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Fractional operations_research::glop::SparseVector< IndexType, IteratorType >::GetFirstCoefficient ( ) const

inline

Definition at line 287 of file sparse_vector.h.

◆ GetFirstIndex()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Index operations_research::glop::SparseVector< IndexType, IteratorType >::GetFirstIndex ( ) const

inline

Returns the first entry's index and coefficient; note that 'first' doesn't mean 'entry with the smallest index'. Runs in O(1). Note this method can only be used when the vector has no duplicates.

Definition at line 283 of file sparse_vector.h.

◆ GetIndex()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Index operations_research::glop::SparseVector< IndexType, IteratorType >::GetIndex ( EntryIndex i ) const

inlineprotected

Read-only access to the indices and coefficients of the entries of the sparse vector.

Definition at line 348 of file sparse_vector.h.

◆ GetLastCoefficient()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Fractional operations_research::glop::SparseVector< IndexType, IteratorType >::GetLastCoefficient ( ) const

inline

Definition at line 297 of file sparse_vector.h.

◆ GetLastIndex()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Index operations_research::glop::SparseVector< IndexType, IteratorType >::GetLastIndex ( ) const

inline

Like GetFirst*, but for the last entry.

Definition at line 293 of file sparse_vector.h.

◆ IsCleanedUp()

template<typename IndexType , typename IteratorType >

bool operations_research::glop::SparseVector< IndexType, IteratorType >::IsCleanedUp ( ) const

Returns true if the entries of this SparseVector are in strictly increasing index order and if the vector contains no duplicates nor zero coefficients. Runs in O(num_entries). It is not const because it modifies possibly_contains_duplicates_.

Definition at line 588 of file sparse_vector.h.

◆ IsEmpty()

template<typename IndexType , typename IteratorType >

bool operations_research::glop::SparseVector< IndexType, IteratorType >::IsEmpty ( ) const

Returns true if the vector is empty.

Definition at line 537 of file sparse_vector.h.

◆ IsEqualTo()

template<typename IndexType , typename IteratorType >

bool operations_research::glop::SparseVector< IndexType, IteratorType >::IsEqualTo ( const SparseVector< IndexType, IteratorType > & other ) const

Returns true if this vector is exactly equal to the given one, i.e. all its index indices and coefficients appear in the same order and are equal.

We do not take into account the mutable value may_contain_duplicates_.

Definition at line 1015 of file sparse_vector.h.

◆ LookUpCoefficient()

template<typename IndexType , typename IteratorType >

Fractional operations_research::glop::SparseVector< IndexType, IteratorType >::LookUpCoefficient ( Index index ) const

Returns the coefficient at position index. Call with care: runs in O(number-of-entries) as entries may not be sorted.

Keep in mind the vector may contains several entries with the same index. In such a case the last one is returned.

Todo: (user): investigate whether an optimized version of LookUpCoefficient for "clean" columns yields speed-ups.

Definition at line 999 of file sparse_vector.h.

◆ MoveEntryToFirstPosition()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::MoveEntryToFirstPosition ( Index index )

Moves the entry with given Index to the first position in the vector. If the entry is not present, nothing happens.

Definition at line 748 of file sparse_vector.h.

◆ MoveEntryToLastPosition()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::MoveEntryToLastPosition ( Index index )

Moves the entry with given Index to the last position in the vector. If the entry is not present, nothing happens.

Definition at line 761 of file sparse_vector.h.

◆ MoveTaggedEntriesTo()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::MoveTaggedEntriesTo	(	const IndexPermutation &	index_perm,
		SparseVector< IndexType, IteratorType > *	output )

Removes the entries for which index_perm[index] is non-negative and appends them to output. Note that the index of the entries are NOT permuted.

Note: this function is called many times, so performance does matter and it is why we optimized the "nothing to do" case.

Todo: (user): In the way we use this function, we know that will not happen, but it is better to be careful so we can check that properly in debug mode.

Definition at line 969 of file sparse_vector.h.

◆ MultiplyByConstant()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::MultiplyByConstant ( Fractional factor )

Multiplies all entries by factor. i.e. entry.coefficient *= factor.

Definition at line 775 of file sparse_vector.h.

◆ MutableCoefficient()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Fractional & operations_research::glop::SparseVector< IndexType, IteratorType >::MutableCoefficient ( EntryIndex i )

inlineprotected

Definition at line 366 of file sparse_vector.h.

◆ MutableIndex()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Index & operations_research::glop::SparseVector< IndexType, IteratorType >::MutableIndex ( EntryIndex i )

inlineprotected

Mutable access to the indices and coefficients of the entries of the sparse vector.

Definition at line 361 of file sparse_vector.h.

◆ num_entries()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

EntryIndex operations_research::glop::SparseVector< IndexType, IteratorType >::num_entries ( ) const

inline

Note this method can only be used when the vector has no duplicates.

Definition at line 274 of file sparse_vector.h.

◆ operator=() [1/2]

template<typename IndexType , typename IteratorType >

SparseVector< IndexType, IteratorType > & operations_research::glop::SparseVector< IndexType, IteratorType >::operator= ( const SparseVector< IndexType, IteratorType > & other )

Definition at line 481 of file sparse_vector.h.

◆ operator=() [2/2]

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

SparseVector & operations_research::glop::SparseVector< IndexType, IteratorType >::operator= ( SparseVector< IndexType, IteratorType > && other )

default

◆ PermutedCopyToDenseVector()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::PermutedCopyToDenseVector	(	const IndexPermutation &	index_perm,
		Index	num_indices,
		DenseVector *	dense_vector ) const

Populates a dense vector from the permuted sparse vector. Runs in O(num_indices) as the dense vector values have to be reset to 0.0.

Definition at line 817 of file sparse_vector.h.

◆ PopulateFromDenseVector()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::PopulateFromDenseVector ( const DenseVector & dense_vector )

Populates the current vector from dense_vector. Runs in O(num_indices_in_dense_vector).

Definition at line 626 of file sparse_vector.h.

◆ PopulateFromSparseVector()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::PopulateFromSparseVector ( const SparseVector< IndexType, IteratorType > & sparse_vector )

Populates the current vector from sparse_vector. Runs in O(num_entries).

Clear the sparse vector before reserving the new capacity. If we didn't do this, Reserve would have to copy the current contents of the vector if it allocated a new buffer. This would be wasteful, since we overwrite it in the next step anyway.

If there are no entries, then sparse_vector.index_ or .coefficient_ may be nullptr or invalid, and accessing them in memmove is UB, even if the moved size is zero.

NOTE(user): Using a single memmove would be slightly faster, but it would not work correctly if this already had a greater capacity than sparse_vector, because the coefficient_ pointer would be positioned incorrectly.

Definition at line 600 of file sparse_vector.h.

◆ RemoveNearZeroEntries()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::RemoveNearZeroEntries ( Fractional threshold )

Sets to 0.0 (i.e. remove) all entries whose fabs() is lower or equal to the given threshold.

Definition at line 717 of file sparse_vector.h.

◆ RemoveNearZeroEntriesWithWeights()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::RemoveNearZeroEntriesWithWeights	(	Fractional	threshold,
		const DenseVector &	weights )

Same as RemoveNearZeroEntries, but the entry magnitude of each row is multiplied by weights[row] before being compared with threshold.

Definition at line 733 of file sparse_vector.h.

◆ Reserve()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::Reserve ( EntryIndex new_capacity )

Reserve the underlying storage for the given number of entries.

Round up the capacity to a multiple of four. This way, the start of the coefficient array will be aligned to 16-bytes, provided that the buffer used for storing the data is aligned in that way.

Avoid copying the data if the vector is empty.

NOTE(user): We use memmove instead of std::copy, because the latter leads to naive copying code when used with strong ints (a loop that copies a single 32-bit value in each iteration), and as of 06/2016, memmove is 3-4x faster on Haswell.

Definition at line 503 of file sparse_vector.h.

◆ ResizeDown()

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

void operations_research::glop::SparseVector< IndexType, IteratorType >::ResizeDown ( EntryIndex new_size )

inlineprotected

Resizes the sparse vector to a smaller size, without re-allocating the internal storage.

Definition at line 340 of file sparse_vector.h.

◆ SetCoefficient()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::SetCoefficient	(	Index	index,
		Fractional	value )

Defines the coefficient at index, i.e. vector[index] = value;.

Do not filter out zero values, as a zero value can be added to reset a previous value. Zero values and duplicates will be removed by CleanUp.

Definition at line 693 of file sparse_vector.h.

◆ Swap()

template<typename IndexType , typename IteratorType >

void operations_research::glop::SparseVector< IndexType, IteratorType >::Swap ( SparseVector< IndexType, IteratorType > * other )

Swaps the content of this sparse vector with the one passed as argument. Works in O(1).

Definition at line 542 of file sparse_vector.h.

Member Data Documentation

◆ buffer_

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

std::unique_ptr<char[]> operations_research::glop::SparseVector< IndexType, IteratorType >::buffer_

protected

The internal storage of the sparse vector. Both the indices and the coefficients are stored in the same buffer; the first sizeof(Index)*capacity_ bytes are used for storing the indices, the following sizeof(Fractional)*capacity_ bytes contain the values. This representation ensures that for small vectors, both the indices and the coefficients are in the same page/cache line. We use a single buffer for both arrays. The amount of data copied during relocations is the same in both cases, and it is much smaller than the cost of an additional allocation - especially when the vectors are small. Moreover, using two separate vectors/buffers would mean that even small vectors would be spread across at least two different cache lines.

Definition at line 383 of file sparse_vector.h.

◆ capacity_

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

EntryIndex operations_research::glop::SparseVector< IndexType, IteratorType >::capacity_

protected

Definition at line 385 of file sparse_vector.h.

◆ coefficient_

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Fractional* operations_research::glop::SparseVector< IndexType, IteratorType >::coefficient_ = nullptr

protected

Definition at line 389 of file sparse_vector.h.

◆ index_

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

Index* operations_research::glop::SparseVector< IndexType, IteratorType >::index_ = nullptr

protected

Pointers to the first elements of the index and coefficient arrays.

Definition at line 388 of file sparse_vector.h.

◆ may_contain_duplicates_

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

bool operations_research::glop::SparseVector< IndexType, IteratorType >::may_contain_duplicates_

mutableprotected

This is here to speed up the CheckNoDuplicates() methods and is mutable so we can perform checks on const argument.

Definition at line 393 of file sparse_vector.h.

◆ num_entries_

template<typename IndexType , typename IteratorType = VectorIterator<SparseVectorEntry<IndexType>>>

EntryIndex operations_research::glop::SparseVector< IndexType, IteratorType >::num_entries_

protected

Definition at line 384 of file sparse_vector.h.

The documentation for this class was generated from the following file:

ortools/lp_data/sparse_vector.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ DenseVector

◆ Entry

◆ Index

◆ IndexPermutation

◆ Iterator

Constructor & Destructor Documentation

◆ SparseVector() [1/3]

◆ SparseVector() [2/3]

◆ SparseVector() [3/3]

Member Function Documentation

◆ AddEntry()

◆ AddMultipleToDenseVector()

◆ AddMultipleToSparseVectorAndDeleteCommonIndex()

◆ AddMultipleToSparseVectorAndIgnoreCommonIndex()

◆ AllEntryIndices()

◆ AppendEntriesWithOffset()

◆ ApplyIndexPermutation()

◆ ApplyPartialIndexPermutation()

◆ begin()

◆ CheckNoDuplicates() [1/2]

◆ CheckNoDuplicates() [2/2]

◆ CleanUp()

◆ Clear()

◆ ClearAndRelease()

◆ ComponentWiseDivide()

◆ ComponentWiseMultiply()

◆ CopyToDenseVector()

◆ DebugString()

◆ DeleteEntry()

◆ DivideByConstant()

◆ end()

◆ GetCoefficient()

◆ GetFirstCoefficient()

◆ GetFirstIndex()

◆ GetIndex()

◆ GetLastCoefficient()

◆ GetLastIndex()

◆ IsCleanedUp()

◆ IsEmpty()

◆ IsEqualTo()

◆ LookUpCoefficient()

◆ MoveEntryToFirstPosition()

◆ MoveEntryToLastPosition()

◆ MoveTaggedEntriesTo()

◆ MultiplyByConstant()

◆ MutableCoefficient()

◆ MutableIndex()

◆ num_entries()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ PermutedCopyToDenseVector()

◆ PopulateFromDenseVector()

◆ PopulateFromSparseVector()

◆ RemoveNearZeroEntries()

◆ RemoveNearZeroEntriesWithWeights()

◆ Reserve()

◆ ResizeDown()

◆ SetCoefficient()

◆ Swap()

Member Data Documentation

◆ buffer_

◆ capacity_

◆ coefficient_

◆ index_

◆ may_contain_duplicates_

◆ num_entries_