sparse vector set.Class SVSet provides a set of sparse vectors SVector. All SVectors in a SVSet share one big memory block for their nonzeros. This memory is reffered to as the nonzero memory. The SVectors themselfs are saved in another memory block refered to as the vector memory. Both memory blocks will grow automatically if required, when adding more SVectors to the set or enlarging SVectors within the set. For controlling memory consumption, methods are provided to inquire and reset the size of the memory blocks used for vectors and nonzeros. More...

#include <svset.h>

Inheritance diagram for SVSet:

[legend]

Classes
class	DLPSV
	SVector with prev/next pointers. More...

Public Member Functions
Extension
void	add (const SVector &svec)
	Add `svec` to the set.

void	add (DataKey &nkey, const SVector &svec)
	Add `svec` to SVSet.

void	add (const SVector svec[], int n)
	Add all `n` SVectors in the array `svec` to the set.

void	add (DataKey nkey[], const SVector svec[], int n)
	Add n SVectors to SVSet.

void	add (const SVSet &pset)
	Add all SVectors in `pset` to an SVSet.

void	add (DataKey nkey[], const SVSet &pset)
	Add all SVectors of `pset` to SVSet.

SVector *	create (int idxmax=-1)
	Creates new SVector in set.

SVector *	create (DataKey &nkey, int idxmax=-1)
	Creates new SVector in set.

void	xtend (SVector &svec, int newmax)
	Extend `svec` to fit `newmax` nonzeros.

void	add2 (SVector &svec, int idx, Real val)
	Add nonzero (`idx`, `val`) to `svec` of this SVSet.

void	add2 (SVector &svec, int n, const int idx[], const Real val[])
	Add `n` nonzeros to `svec` of this SVSet.

Shrinking
void	remove (const DataKey &removekey)
	removes the vector with key `removekey` from the set

void	remove (int removenum)
	removes the vector with number `removenum` from the set

void	remove (const SVector *svec)
	remove one SVector from set.

void	remove (int perm[])
	remove multiple elements.

void	remove (const DataKey keys[], int n)
	Remove `n` SVectors from set.

void	remove (const int nums[], int n)
	Remove `n` SVectors from set.

void	remove (const DataKey keys[], int n, int *perm)

void	remove (const int nums[], int n, int *perm)
	Remove `n` SVectors from set.

void	clear ()
	remove all SVectors from set.

Access
SVector &	operator[] (int n)
	get SVector by number, writeable

const SVector &	operator[] (int n) const
	get SVector by number

SVector &	operator[] (const DataKey &k)
	get SVector by DataKey, writeable

const SVector &	operator[] (const DataKey &k) const
	get SVector by DataKey

Inquiry
int	num () const
	current number of SVectors.

int	max () const
	current maximum number of SVectors.

DataKey	key (int n) const
	get DataKey of vector number

DataKey	key (const SVector *svec) const
	get DataKey of SVector

int	number (const DataKey &k) const
	get vector number of DataKey

int	number (const SVector *svec) const
	get vector number of SVector

bool	has (const DataKey &k) const
	true iff SVSet contains a SVector for DataKey `k`

bool	has (int n) const
	true iff SVSet contains a SVector for vector number n

bool	has (const SVector *svec) const
	is an SVector in the set.

Memory Management
int	memSize () const
	used nonzero memory.

int	memMax () const
	length of nonzero memory.

void	memRemax (int newmax)
	reset length of nonzero memory.

void	memPack ()
	garbage collection in nonzero memory.

Miscellaneous
void	reMax (int newmax=0)
	reset maximum number of SVectors.

bool	isConsistent () const
	consistency check.

Constructors / destructors
	SVSet (int pmax=-1, int pmemmax=-1, Real pfac=1.1, Real pmemFac=1.2)
	default constructor.

	~SVSet ()
	destructor

SVSet &	operator= (const SVSet &rhs)
	assignment operator.

	SVSet (const SVSet &old)
	copy constructor.

Private Member Functions
Helpers
void	ensurePSVec (int n)
	provides enough vector memory for `n` more SVectors.

void	ensureMem (int n)
	provides enough nonzero memory for `n` more Elementss.

void	deleteVec (DLPSV *ps)
	deleting a vector from the dataarray

Private Attributes
Data
DataSet< DLPSV >	set
	set of SVectors

IdList< DLPSV >	list
	doubly linked list for non-zero management

int	possiblyUnusedMem
	an estimate of the used memory due to xtends

Control Parameters
Real	factor
	Sparse vector memory enlargment factor.

Additional Inherited Members
Protected Member Functions inherited from DataArray< T >
T &	operator[] (int n)
	reference `n` 'th element.

const T &	operator[] (int n) const
	reference `n` 'th const element.

T &	last ()
	reference last element.

const T &	last () const
	reference last const element.

T *	get_ptr ()
	get a C pointer to the data.

const T *	get_const_ptr () const
	get a const C pointer to the data.

void	append (const T &t)
	append element `t`.

void	append (int n, const T t[])
	append `n` elements from `t`.

void	append (const DataArray< T > &t)
	append all elements from `t`.

void	insert (int i, int n)
	insert `n` uninitialized elements before `i` 'th element.

void	insert (int i, int n, const T t[])
	insert `n` elements from `t` before `i` 'the element.

void	insert (int i, const DataArray< T > &t)
	insert all elements from `t` before `i` 'th element.

void	remove (int n=0, int m=1)
	remove `m` elements starting at `n`.

void	removeLast (int m=1)
	remove `m` last elements.

void	clear ()
	remove all elements.

int	size () const
	return nr. of elements.

void	reSize (int newsize)
	reset size to `newsize`.

int	max () const
	return maximum number of elements.

ptrdiff_t	reMax (int newMax=1, int newSize=-1)
	reset maximum number of elements.

DataArray &	operator= (const DataArray &rhs)
	assignment operator

bool	isConsistent () const
	consistency check

	DataArray (const DataArray &old)
	copy constructor

	DataArray (int p_size=0, int p_max=0, Real p_fac=1.2)
	default constructor.

	~DataArray ()
	destructor

Detailed Description

sparse vector set.

Class SVSet provides a set of sparse vectors SVector. All SVectors in a SVSet share one big memory block for their nonzeros. This memory is reffered to as the nonzero memory. The SVectors themselfs are saved in another memory block refered to as the vector memory. Both memory blocks will grow automatically if required, when adding more SVectors to the set or enlarging SVectors within the set. For controlling memory consumption, methods are provided to inquire and reset the size of the memory blocks used for vectors and nonzeros.

SVectors in an SVSet are numbered from 0 thru num()-1. They can be accessed using the index operator[](). When removing SVectors of a SVSet the remaining ones will be renumbered. However, all SVector with a smaller number than the lowest number of the removed SVectors will remain unchanged.

For providing a uniform access to SVectors in a set even if others are removed or added, SVSet assigns a DataKey to each SVector in the set. Such a DataKey remains unchanged as long as the corresponding SVector is in the SVSet, no matter what other SVectors are added to or removed from the SVSet. Methods are provided for getting the DataKey to a SVector or its number and vice versa. Further, each add() method for enlarging an SVSet is provided with two signatures. One of them returns the DataKeys assigned to the SVectors added to the SVSet.

Definition at line 65 of file svset.h.

Constructor & Destructor Documentation

SVSet	(	int	pmax = `-1`,
		int	pmemmax = `-1`,
		Real	pfac = `1.1`,
		Real	pmemFac = `1.2`
	)

explicit

default constructor.

Definition at line 465 of file svset.h.

References SVSet::isConsistent().

~SVSet ( )

destructor

Definition at line 478 of file svset.h.

SVSet ( const SVSet & old )

copy constructor.

Definition at line 399 of file svset.cpp.

References SVSet::isConsistent().

Member Function Documentation

void add ( const SVector & svec )

Add svec to the set.

This includes copying its nonzeros to the sets nonzero memory and creating an additional SVector entry in vector memory. If neccessary, the memory blocks are enlarged appropriately.

Definition at line 181 of file svset.h.

References SVSet::create(), SVSet::ensurePSVec(), and SVector::size().

Referenced by SVSet::add(), LPColSet::add(), and LPRowSet::add().

void add	(	DataKey &	nkey,
		const SVector &	svec
	)

Add svec to SVSet.

Adds SVector svec to the set. This includes copying its nonzeros to the sets nonzero memory and creating an additional SVector entry in vector memory. If neccessary, the memory blocks are enlarged appropriately.

Returns: nkey contains the DataKey, that the SVSet has assosicated to the new SVector.

Definition at line 196 of file svset.h.

References SVSet::create(), SVSet::ensurePSVec(), and SVector::size().

void add	(	const SVector	svec[],
		int	n
	)

Add all n SVectors in the array svec to the set.

Precondition: svec must be not larger than n

Definition at line 35 of file svset.cpp.

References SVSet::create(), SVSet::ensureMem(), SVSet::ensurePSVec(), and DataArray< T >::size().

void add	(	DataKey	nkey[],
		const SVector	svec[],
		int	n
	)

Add n SVectors to SVSet.

Adds all n SVectors in the array svec to the set.

Returns: nkey contains the DataKeys, that the SVSet has assosicated to the new SVectors.

Precondition: nkey must be large enough to fit n DataKeys.

Definition at line 50 of file svset.cpp.

References SVSet::add(), SVSet::key(), and SVSet::num().

void add ( const SVSet & pset )

Add all SVectors in pset to an SVSet.

Definition at line 57 of file svset.cpp.

References SVSet::create(), SVSet::ensureMem(), SVSet::ensurePSVec(), SVSet::num(), and DataArray< T >::size().

void add	(	DataKey	nkey[],
		const SVSet &	pset
	)

Add all SVectors of pset to SVSet.

Adds all n SVectors in the pset to an SVSet.

Returns: nkey contains the DataKeys, that the SVSet has assosicated to the new SVectors.

Precondition: nkey must be large enough to fit pset.num() DataKeys.

Definition at line 71 of file svset.cpp.

References SVSet::add(), SVSet::key(), and DataArray< T >::size().

void add2	(	SVector &	svec,
		int	idx,
		Real	val
	)

Add nonzero (idx, val) to svec of this SVSet.

Adds one nonzero (idx, val) to SVector svec in the SVSet. If svec is not large enough to hold the additional nonzero, it will be automatically enlarged within the set.

Precondition: svec must be an SVector of the SVSet.

Definition at line 166 of file svset.cpp.

References SVector::add(), SVector::size(), and SVSet::xtend().

Referenced by LPColSet::add2(), and LPRowSet::add2().

void add2	(	SVector &	svec,
		int	n,
		const int	idx[],
		const Real	val[]
	)

Add n nonzeros to svec of this SVSet.

Adds n nonzeros to SVector svec in the SVSet. If svec is not large enough to hold the additional nonzeros, it will be automatically enlarged within the set.

Precondition: svec must be an SVector of the SVSet.

Definition at line 172 of file svset.cpp.

References SVector::add(), SVector::size(), and SVSet::xtend().

void clear ( )

remove all SVectors from set.

Definition at line 330 of file svset.h.

References SVSet::list, and SVSet::reMax().

Referenced by LPColSet::clear(), LPRowSet::clear(), and SVSet::operator=().

SVector * create ( int idxmax = -1 )

Creates new SVector in set.

The new SVector will be ready to fit at least idxmax nonzeros.

resize the dataarray

Definition at line 82 of file svset.cpp.

References SVSet::ensureMem(), SVSet::ensurePSVec(), DataArray< T >::last(), SVSet::list, SVector::max(), SVSet::memMax(), SVSet::memSize(), DataArray< T >::removeLast(), DataArray< T >::reSize(), SVector::set_max(), SVector::setMem(), and SVector::size().

Referenced by SVSet::add(), SVSet::create(), LPColSet::create(), and LPRowSet::create().

SVector * create	(	DataKey &	nkey,
		int	idxmax = `-1`
	)

Creates new SVector in set.

The new SVector will be ready to fit at least idxmax nonzeros.

Returns: nkey contains the DataKey associated to the new SVector.

Definition at line 114 of file svset.cpp.

References SVSet::create(), SVSet::key(), and SVSet::num().

void deleteVec ( DLPSV * ps )

private

deleting a vector from the dataarray

Definition at line 178 of file svset.cpp.

References SVSet::list, SVector::max(), SVector::mem(), SVSet::DLPSV::next(), DataArray< T >::operator[](), SVSet::DLPSV::prev(), DataArray< T >::removeLast(), SVector::set_size(), SVector::setMem(), SVector::size(), and DataArray< T >::size().

Referenced by SVSet::remove().

void ensureMem ( int n )

private

provides enough nonzero memory for n more Elementss.

Definition at line 24 of file svset.cpp.

References DataArray< T >::memFactor, SVSet::memMax(), SVSet::memRemax(), and SVSet::memSize().

Referenced by SVSet::add(), SVSet::create(), and SVSet::xtend().

void ensurePSVec ( int n )

private

provides enough vector memory for n more SVectors.

Definition at line 146 of file svset.h.

References SVSet::factor, SVSet::max(), SVSet::num(), and SVSet::reMax().

Referenced by SVSet::add(), and SVSet::create().

bool has ( const DataKey & k ) const

true iff SVSet contains a SVector for DataKey k

Definition at line 409 of file svset.h.

Referenced by LPColSet::has(), LPRowSet::has(), and SVSet::xtend().

bool has ( int n ) const

true iff SVSet contains a SVector for vector number n

Definition at line 415 of file svset.h.

bool has ( const SVector * svec ) const

is an SVector in the set.

Definition at line 421 of file svset.h.

bool isConsistent ( ) const

consistency check.

Definition at line 340 of file svset.cpp.

References SVector::isConsistent(), DataArray< T >::last(), SVSet::list, SVector::max(), SVector::mem(), and MSGinconsistent.

Referenced by LPColSet::isConsistent(), LPRowSet::isConsistent(), SVSet::operator=(), and SVSet::SVSet().

DataKey key ( int n ) const

get DataKey of vector number

Definition at line 385 of file svset.h.

Referenced by SVSet::add(), SVSet::create(), LPColSet::key(), LPRowSet::key(), and SVSet::remove().

DataKey key ( const SVector * svec ) const

get DataKey of SVector

Definition at line 391 of file svset.h.

int max ( ) const

current maximum number of SVectors.

Definition at line 379 of file svset.h.

Referenced by SVSet::ensurePSVec(), LPRowSet::max(), LPColSet::max(), and SVSet::memMax().

int memMax ( ) const

length of nonzero memory.

Definition at line 437 of file svset.h.

References SVSet::max().

Referenced by SPxLP::added2Set(), SVSet::create(), SVSet::ensureMem(), LPColSet::memMax(), and LPRowSet::memMax().

void memPack ( )

garbage collection in nonzero memory.

Pack the svectors together as tightly as possible. This removes all additional unused memory, i.e., size = max for every svector after the call.

Note: do not call isConsistent() here, because the following might happen: In SPxLP::doAddRows(const LPRowSet& p_set), when adding rows, the sizes of the vectors for the columns of the LP are increased (without yet filling in the data) to recieve the additional entries. This is done by calling xtend() above. xtend() in turn might call this method, which checks the yet unfilled positions, i.e., isConsistent() is likely to fail. In general, isConsistent() should not be called within this class, but in classes further up in the hierarchy.

Definition at line 314 of file svset.cpp.

References SVSet::list, SVector::mem(), DataArray< T >::operator[](), SVSet::possiblyUnusedMem, DataArray< T >::reSize(), SVector::set_max(), SVector::set_size(), SVector::setMem(), and SVector::size().

Referenced by LPColSet::memPack(), LPRowSet::memPack(), and SVSet::xtend().

void memRemax ( int newmax )

reset length of nonzero memory.

Definition at line 280 of file svset.cpp.

References SVector::Element::idx, SVSet::list, SVSet::reMax(), and SVector::Element::val.

Referenced by SPxLP::added2Set(), SVSet::ensureMem(), LPColSet::memRemax(), and LPRowSet::memRemax().

int memSize ( ) const

used nonzero memory.

Definition at line 431 of file svset.h.

References DataArray< T >::size().

Referenced by SSVector::assign2product4setup(), SVSet::create(), SVSet::ensureMem(), LPColSet::memSize(), LPRowSet::memSize(), and SVSet::xtend().

int num ( ) const

current number of SVectors.

Definition at line 373 of file svset.h.

Referenced by SVSet::add(), SPxLP::added2Set(), SSVector::assign2product(), SSVector::assign2product4setup(), SPxScaler::computeScalingVecs(), SVSet::create(), SVSet::ensurePSVec(), LPRowSet::num(), LPColSet::num(), and SVSet::remove().

int number ( const DataKey & k ) const

get vector number of DataKey

Definition at line 397 of file svset.h.

Referenced by LPColSet::number(), LPRowSet::number(), SVSet::operator=(), and SVSet::remove().

int number ( const SVector * svec ) const

get vector number of SVector

Definition at line 403 of file svset.h.

SVSet & operator= ( const SVSet & rhs )

assignment operator.

Definition at line 363 of file svset.cpp.

References SVSet::clear(), SVSet::isConsistent(), SVSet::list, SVector::max(), SVector::mem(), SVSet::number(), SVSet::set, SVector::set_size(), SVector::setMem(), SVector::size(), and DataArray< T >::size().

Referenced by LPColSet::operator=(), and LPRowSet::operator=().

SVector& operator[] ( int n )

get SVector by number, writeable

Definition at line 344 of file svset.h.

Referenced by LPColSet::colVector(), LPColSet::colVector_w(), LPRowSet::rowVector(), and LPRowSet::rowVector_w().

const SVector& operator[] ( int n ) const

get SVector by number

Definition at line 350 of file svset.h.

SVector& operator[] ( const DataKey & k )

get SVector by DataKey, writeable

Definition at line 356 of file svset.h.

const SVector& operator[] ( const DataKey & k ) const

get SVector by DataKey

Definition at line 362 of file svset.h.

void reMax ( int newmax = 0 )

reset maximum number of SVectors.

Definition at line 275 of file svset.cpp.

References SVSet::list.

Referenced by SVSet::clear(), SVSet::ensurePSVec(), SVSet::memRemax(), LPColSet::reMax(), and LPRowSet::reMax().

void remove ( const DataKey & removekey )

removes the vector with key removekey from the set

Precondition: removekey must be a key from SVSet

Definition at line 231 of file svset.cpp.

References SVSet::deleteVec().

Referenced by LPColSet::remove(), and LPRowSet::remove().

void remove ( int removenum )

removes the vector with number removenum from the set

Precondition: removenum must be a valid vector number from SVSet

Definition at line 274 of file svset.h.

References SVSet::key().

void remove ( const SVector * svec )

remove one SVector from set.

Precondition: svec must be from SVSet

Definition at line 281 of file svset.h.

References SVSet::key().

void remove ( int perm[] )

remove multiple elements.

Removes all SVectors for the SVSet with an index i such that perm[i] < 0. Upon completion, perm[i] >= 0 indicates the new index where the i 'th SVector has been moved to due to this removal.

Precondition: perm must point to an array of at least num() integers.

Definition at line 237 of file svset.cpp.

References SVSet::deleteVec(), and SVSet::num().

void remove	(	const DataKey	keys[],
		int	n
	)

Remove n SVectors from set.

Precondition: keys must be at least of size n and valid keys

Definition at line 300 of file svset.h.

References DataArray< T >::get_ptr(), and SVSet::num().

void remove	(	const int	nums[],
		int	n
	)

Remove n SVectors from set.

Precondition: nums must be at least of size n and valid vector numbers

Definition at line 310 of file svset.h.

References DataArray< T >::get_ptr(), and SVSet::num().

void remove	(	const DataKey	keys[],
		int	n,
		int *	perm
	)

Definition at line 254 of file svset.cpp.

References SVSet::num(), and SVSet::number().

void remove	(	const int	nums[],
		int	n,
		int *	perm
	)

Remove n SVectors from set.

Precondition: perm must be at least of size num(); nums must be at least of size n

Returns: perm is the permutations resulting from this removal: perm[i] < 0 indicates, that the element to index i has been removed. Otherwise, perm[i] is the new index of the element with index i before the removal.

Definition at line 263 of file svset.cpp.

References SVSet::num().