CppNoddy  0.85
 All Classes Namespaces Files Functions Variables Typedefs Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
CppNoddy::SparseVector< _Type > Class Template Reference

An SparseVector class – a sparse vector object. More...

#include <SparseVector.h>

Public Member Functions

 SparseVector (const std::size_t &max)
 Constructor for a non-filled vector, to be filled by the user.
 SparseVector (const SparseVector &source)
 Copy constructor.
SparseVectoroperator= (const SparseVector &source)
 Assignment operator.
iter begin ()
 Not a full iterator implementation – just a pass through to the storage container.
citer begin () const
 Not a full iterator implementation – just a pass through to the storage container.
iter end ()
 Not a full iterator implementation – just a pass through to the storage container.
citer end () const
 Not a full iterator implementation – just a pass through to the storage container.
void resize (const std::size_t &length)
 Resize the maximum length of the sparse vector.
void clear ()
 Remove all elements from the sparse vector.
void erase (const iter &pos)
 Erase an element from the vector.
void erase (const std::size_t &index)
 Erase an element from th vector.
void swap (const std::size_t &i, const std::size_t &j)
 Swap elements i and j.
void swap (SparseVector< _Type > &X)
 Swap ALL elements with those of another SparseVector.
std::size_t size () const
 Find the (max) size of the vector.
std::size_t nelts () const
 Find the number of non-zero elements in the vector.
_Type & set (const std::size_t &i)
 Set an element of the vector.
const _Type & get (const std::size_t &i) const
 Get an element of the vector.
const _Type & operator[] (const std::size_t &i) const
 Equivalent to the 'get' method.
_Type & operator[] (const std::size_t &i)
 Equivalent to the 'set' method.
SparseVector< _Type > operator+ (const SparseVector< _Type > &X) const
 Operator overloading for sparse vector addition.
SparseVector< _Type > operator+ () const
 Overloading for +.
SparseVector< _Type > operator- (const SparseVector< _Type > &X) const
 Operator overloading for sparse vector subtraction.
SparseVector< _Type > operator- () const
 Overloading for -.
SparseVector< _Type > operator* (const _Type &m) const
 Overloading multiplication for a scalar.
SparseVector< _Type > & operator*= (const _Type &m)
 Overloading *= for scalar multiplication.
SparseVector< _Type > & operator-= (const SparseVector< _Type > &X)
 Overloading -= for sparse vectors.
SparseVector< _Type > & operator+= (const SparseVector< _Type > &X)
 Overloading += for sparse vectors.
citer find (std::size_t i) const
 Look for an element index.
const _Type dot (const SparseVector< _Type > &x) const
 A dot product.
double one_norm () const
 l1-norm.
double two_norm () const
 l2-norm.
double inf_norm () const
 Infinity norm.
void scale (const _Type &scale)
 Scale each element of the vector.
void add (const SparseVector< _Type > &X)
 Add a vector, element wise.
void sub (const SparseVector< _Type > &X)
 Subtract a vector, element wise.
std::size_t nearest_index (const _Type &value) const
 Find the index of the element NEAREST in value to that specified.
std::size_t maxabs_index () const
 Find the index of the maximum element in the vector.
std::size_t minabs_index () const
 Find the index of the maximum element in the vector.
void dump () const
 Output the sparse vector's contents.

Detailed Description

template<typename _Type>
class CppNoddy::SparseVector< _Type >

An SparseVector class – a sparse vector object.

This is templated but intended ONLY for double or std::complex<double>.

Definition at line 17 of file SparseVector.h.

Constructor & Destructor Documentation

template<typename _Type >
CppNoddy::SparseVector< _Type >::SparseVector ( const std::size_t &  max)
explicit

Constructor for a non-filled vector, to be filled by the user.

Parameters
maxA maximum size for the sparse vector, used in geometry checking.

Definition at line 19 of file SparseVector.cpp.

: ZERO( 0.0 ), MAX_SIZE( max )
{}
template<typename _Type >
CppNoddy::SparseVector< _Type >::SparseVector ( const SparseVector< _Type > &  source)

Copy constructor.

Parameters
sourceThe source object to be copied

Definition at line 23 of file SparseVector.cpp.

References CppNoddy::Example::source().

{
*this = source;
}

Member Function Documentation

template<typename _Type >
void CppNoddy::SparseVector< _Type >::add ( const SparseVector< _Type > &  X)

Add a vector, element wise.

Parameters
XThe vector to be added to this object.

Definition at line 295 of file SparseVector.cpp.

{
*this += X;
}
template<typename _Type >
std::map< std::size_t, _Type >::iterator CppNoddy::SparseVector< _Type >::begin ( )
inline

Not a full iterator implementation – just a pass through to the storage container.

Return an iterator pointing to the beginning of the encpsulated STL map storage

Definition at line 216 of file SparseVector.h.

{
return VEC.begin();
}
template<typename _Type >
std::map< std::size_t, _Type >::const_iterator CppNoddy::SparseVector< _Type >::begin ( ) const
inline

Not a full iterator implementation – just a pass through to the storage container.

Return a constant iterator pointing to the beginning of the encapsulated STL map storage

Definition at line 222 of file SparseVector.h.

{
return VEC.begin();
}
template<typename _Type >
void CppNoddy::SparseVector< _Type >::clear ( )

Remove all elements from the sparse vector.

Definition at line 213 of file SparseVector.cpp.

{
VEC.clear();
}
template<typename _Type >
const _Type CppNoddy::SparseVector< _Type >::dot ( const SparseVector< _Type > &  x) const

A dot product.

Parameters
xThe vector to be "dotted" with.
Todo:
Using a 'get' (aka find) here is slooow
  • obviously this can be improved.

Definition at line 219 of file SparseVector.cpp.

References CppNoddy::SparseVector< _Type >::size().

{
#ifdef PARANOID
if ( X.size() != size() )
{
std::string problem;
problem = " The SparseVector.dot method is trying to use \n";
problem += " two vectors of unequal length \n";
throw ExceptionGeom( problem, size(), X.size() );
}
#endif
SparseVector<_Type> temp( X );
_Type sum( 0.0 );
for ( iter pos = temp.VEC.begin(); pos != temp.VEC.end(); ++pos )
{
std::size_t index = pos -> first;
/// \todo Using a 'get' (aka find) here is slooow
/// - obviously this can be improved.
// the get method returns 0.0 if not stored
temp[ index ] *= get( index );
}
return sum;
}
template<typename _Type >
void CppNoddy::SparseVector< _Type >::dump ( ) const

Output the sparse vector's contents.

Definition at line 375 of file SparseVector.cpp.

{
if ( VEC.begin() == VEC.end() )
{
std::cout << "[ Empty vector ]\n";
}
else
{
for ( citer pos = VEC.begin(); pos != VEC.end(); ++pos )
{
std::cout << "[ " << pos -> first << " ]" << " = " << pos -> second << " ";
}
std::cout << "\n";
}
}
template<typename _Type >
std::map< std::size_t, _Type >::iterator CppNoddy::SparseVector< _Type >::end ( )
inline

Not a full iterator implementation – just a pass through to the storage container.

Return an iterator pointing to the end of the encapsulated STL map storage

Definition at line 228 of file SparseVector.h.

{
return VEC.end();
}
template<typename _Type >
std::map< std::size_t, _Type >::const_iterator CppNoddy::SparseVector< _Type >::end ( ) const
inline

Not a full iterator implementation – just a pass through to the storage container.

Return a constant iterator pointing to the end of the encapsulated STL map storage

Definition at line 234 of file SparseVector.h.

{
return VEC.end();
}
template<typename _Type >
void CppNoddy::SparseVector< _Type >::erase ( const iter &  pos)
inline

Erase an element from the vector.

Parameters
posAn std::map< std::size_t, _Type >::iterator to the map element

Definition at line 327 of file SparseVector.h.

{
VEC.erase( pos );
}
template<typename _Type >
void CppNoddy::SparseVector< _Type >::erase ( const std::size_t &  index)
inline

Erase an element from th vector.

Parameters
indexThe index of the element to be erased

Definition at line 321 of file SparseVector.h.

{
VEC.erase( index );
}
template<typename _Type>
citer CppNoddy::SparseVector< _Type >::find ( std::size_t  i) const
inline

Look for an element index.

Parameters
iThe index of the element to search for

Definition at line 151 of file SparseVector.h.

{
citer pos;
pos = VEC.find( i );
return pos;
}
template<typename _Type >
const _Type & CppNoddy::SparseVector< _Type >::get ( const std::size_t &  i) const
inline

Get an element of the vector.

Parameters
iThe index to be accessed
Returns
The contents of the element, including a zero if the element has not been set

Definition at line 285 of file SparseVector.h.

{
#ifdef PARANOID
if ( i >= size() )
{
std::string problem;
problem = " The SparseVector.get method is trying to access \n";
problem += " outside the container. \n";
throw ExceptionRange( problem, size(), i );
}
#endif
citer pos;
pos = VEC.find( i );
if ( pos != VEC.end() )
{
return pos -> second;
}
else
{
return ZERO;
}
}
template<typename _Type >
double CppNoddy::SparseVector< _Type >::inf_norm ( ) const

Infinity norm.

Returns
The maximum (abs) element in the vector.

Definition at line 270 of file SparseVector.cpp.

{
double max( 0.0 );
// Return the maximum (abs) element in the vector
for ( citer pos = VEC.begin(); pos != VEC.end(); ++pos )
{
if ( std::abs( pos -> second ) > max )
{
max = std::abs( pos -> second );
}
}
return max;
}
template<typename _Type >
std::size_t CppNoddy::SparseVector< _Type >::maxabs_index ( ) const

Find the index of the maximum element in the vector.

Returns
The index of the maximum element.

Definition at line 325 of file SparseVector.cpp.

{
citer location( VEC.begin() );
double max( std::abs( location -> second ) );
citer start( ++location );
for ( citer pos = start; pos != VEC.end(); ++pos )
{
if ( std::abs( pos -> second ) > max )
{
max = std::abs( pos -> second );
location = pos;
}
}
return location -> first;
}
template<typename _Type >
std::size_t CppNoddy::SparseVector< _Type >::minabs_index ( ) const

Find the index of the maximum element in the vector.

Returns
The index of the maximum element.

Definition at line 342 of file SparseVector.cpp.

{
citer location( VEC.begin() );
double min( std::abs( location -> second ) );
citer start( ++location );
for ( citer pos = start; pos != VEC.end(); ++pos )
{
if ( std::abs( pos -> second ) < min )
{
min = std::abs( pos -> second );
location = pos;
}
}
return location -> first;
}
template<typename _Type >
std::size_t CppNoddy::SparseVector< _Type >::nearest_index ( const _Type &  value) const

Find the index of the element NEAREST in value to that specified.

Parameters
valueThe value to search for.
Returns
The index of the element with value that minimises the difference.

Definition at line 307 of file SparseVector.cpp.

{
citer location( VEC.begin() );
_Type min_diff( location -> second - value );
citer start( ++location );
for ( citer pos = start; pos != VEC.end(); ++pos )
{
_Type diff( pos -> second - value );
if ( std::abs( diff ) < std::abs( min_diff ) )
{
min_diff = diff;
location = pos;
}
}
return location -> first;
}
template<typename _Type >
std::size_t CppNoddy::SparseVector< _Type >::nelts ( ) const
inline

Find the number of non-zero elements in the vector.

Definition at line 315 of file SparseVector.h.

Referenced by CppNoddy::Utility::fill_random().

{
return VEC.size();
}
template<typename _Type >
double CppNoddy::SparseVector< _Type >::one_norm ( ) const

l1-norm.

Returns
The square-root of the sum of the squares divided by number of elts.

Definition at line 244 of file SparseVector.cpp.

Referenced by main().

{
// Accumulate the ABS values of the container entries
// using a fuction object.
double sum( 0.0 );
for ( citer pos = VEC.begin(); pos != VEC.end(); ++pos )
{
sum += std::abs( pos -> second );
}
return sum;
}
template<typename _Type >
SparseVector< _Type > CppNoddy::SparseVector< _Type >::operator* ( const _Type &  m) const

Overloading multiplication for a scalar.

Parameters
mThe scalar to multiply by
Returns
The scalar multiplication of the vector

Definition at line 198 of file SparseVector.cpp.

References m.

{
SparseVector<_Type> temp( *this );
temp *= m;
return temp;
}
template<typename _Type >
SparseVector< _Type > & CppNoddy::SparseVector< _Type >::operator*= ( const _Type &  m)

Overloading *= for scalar multiplication.

Parameters
mThe scalar to multiply by

Definition at line 40 of file SparseVector.cpp.

References m.

{
for ( iter pos = VEC.begin(); pos != VEC.end(); ++pos )
{
pos -> second *= m;
}
return *this;
}
template<typename _Type >
SparseVector< _Type > CppNoddy::SparseVector< _Type >::operator+ ( const SparseVector< _Type > &  X) const

Operator overloading for sparse vector addition.

Parameters
XA sparse vector to be added
Returns
The sum of this and the passed vector X

Definition at line 156 of file SparseVector.cpp.

References CppNoddy::SparseVector< _Type >::size().

{
#ifdef PARANOID
if ( X.size() != size() )
{
std::string problem;
problem = " The SparseVector.operator+ method is trying to use \n";
problem += " two vectors of unequal length \n";
throw ExceptionGeom( problem, size(), X.size() );
}
#endif
SparseVector<_Type> temp( *this );
temp += X;
return temp;
}
template<typename _Type >
SparseVector< _Type > CppNoddy::SparseVector< _Type >::operator+ ( ) const
inline

Overloading for +.

Returns
+this

Definition at line 348 of file SparseVector.h.

{
return * this;
}
template<typename _Type >
SparseVector< _Type > & CppNoddy::SparseVector< _Type >::operator+= ( const SparseVector< _Type > &  X)

Overloading += for sparse vectors.

Parameters
XThe sparse vector to be added
Returns
Adds X to the 'this' vector

Definition at line 103 of file SparseVector.cpp.

References CppNoddy::SparseVector< _Type >::size().

{
#ifdef PARANOID
if ( X.size() != size() )
{
std::string problem;
problem = " The SparseVector.operator+= method is trying to use \n";
problem += " two vectors of unequal length \n";
throw ExceptionGeom( problem, size(), X.size() );
}
#endif
citer pos_ro = X.VEC.begin();
iter pos_rw = VEC.begin();
do
{
std::size_t index_rw = pos_rw -> first;
std::size_t index_ro = pos_ro -> first;
if ( index_rw == index_ro )
{
// element in both vectors
pos_rw -> second += pos_ro -> second;
++pos_rw;
++pos_ro;
}
if ( index_rw > index_ro )
{
// element is in X but not 'this'
set
( index_ro ) = pos_ro -> second;
++pos_ro;
}
if ( index_rw < index_ro )
{
// element is in 'this' but not X
++pos_rw;
}
}
while ( pos_ro != X.VEC.end() && pos_rw != VEC.end() );
if ( pos_ro != X.VEC.end() )
{
// need to finish the X data
do
{
set
( pos_ro -> first ) = pos_ro -> second;
++pos_ro;
}
while ( pos_ro != X.VEC.end() );
}
return *this;
}
template<typename _Type >
SparseVector< _Type > CppNoddy::SparseVector< _Type >::operator- ( const SparseVector< _Type > &  X) const

Operator overloading for sparse vector subtraction.

Parameters
XA sparse vector to be subtracted
Returns
The subtraction of this and the passed vector X

Definition at line 173 of file SparseVector.cpp.

References CppNoddy::SparseVector< _Type >::size().

{
#ifdef PARANOID
if ( X.size() != size() )
{
std::string problem;
problem = " The SparseVector.operator- method is trying to use \n";
problem += " two vectors of unequal length \n";
throw ExceptionGeom( problem, size(), X.size() );
}
#endif
SparseVector<_Type> temp( *this );
temp -= X;
return temp;
}
template<typename _Type >
SparseVector< _Type > CppNoddy::SparseVector< _Type >::operator- ( ) const

Overloading for -.

Returns
The negative of the vector

Definition at line 190 of file SparseVector.cpp.

{
SparseVector<_Type> temp( *this );
temp *= -1.0;
return temp;
}
template<typename _Type >
SparseVector< _Type > & CppNoddy::SparseVector< _Type >::operator-= ( const SparseVector< _Type > &  X)

Overloading -= for sparse vectors.

Parameters
XThe sparse vector to be subtracted
Returns
Subtracts X from the 'this' vector

Definition at line 50 of file SparseVector.cpp.

References CppNoddy::SparseVector< _Type >::size().

{
#ifdef PARANOID
if ( X.size() != size() )
{
std::string problem;
problem = " The SparseVector.operator-= method is trying to use \n";
problem += " two vectors of unequal length \n";
throw ExceptionGeom( problem, size(), X.size() );
}
#endif
citer pos_ro = X.VEC.begin();
iter pos_rw = VEC.begin();
do
{
std::size_t index_rw = pos_rw -> first;
std::size_t index_ro = pos_ro -> first;
if ( index_rw == index_ro )
{
// element in both vectors
pos_rw -> second -= pos_ro -> second;
++pos_rw;
++pos_ro;
}
if ( index_rw > index_ro )
{
// element is in X but not 'this'
set
( index_ro ) = -( pos_ro -> second );
++pos_ro;
}
if ( index_rw < index_ro )
{
// element is in 'this' but not X
++pos_rw;
}
}
while ( pos_ro != X.VEC.end() && pos_rw != VEC.end() );
if ( pos_ro != X.VEC.end() )
{
// need to finish the X data
do
{
set
( pos_ro -> first ) = -( pos_ro -> second );
++pos_ro;
}
while ( pos_ro != X.VEC.end() );
}
return *this;
}
template<typename _Type >
SparseVector< _Type > & CppNoddy::SparseVector< _Type >::operator= ( const SparseVector< _Type > &  source)

Assignment operator.

Parameters
sourceThe source object for the assignment
Returns
The newly assigned object

Definition at line 29 of file SparseVector.cpp.

{
if ( this == &source )
return * this;
VEC = source.VEC;
ZERO = source.ZERO;
MAX_SIZE = source.MAX_SIZE;
return *this;
}
template<typename _Type >
const _Type & CppNoddy::SparseVector< _Type >::operator[] ( const std::size_t &  i) const
inline

Equivalent to the 'get' method.

Definition at line 255 of file SparseVector.h.

{
#ifdef PARANOID
if ( i >= size() )
{
std::string problem;
problem = " The SparseVector.operator[] method is trying to access \n";
problem += " outside the container. \n";
throw ExceptionRange( problem, size(), i );
}
#endif
return get( i );
}
template<typename _Type >
_Type & CppNoddy::SparseVector< _Type >::operator[] ( const std::size_t &  i)
inline

Equivalent to the 'set' method.

Definition at line 240 of file SparseVector.h.

{
#ifdef PARANOID
if ( i >= size() )
{
std::string problem;
problem = " The SparseVector.operator[] method is trying to access \n";
problem += " outside the container. \n";
throw ExceptionRange( problem, size(), i );
}
#endif
return VEC[ i ];
}
template<typename _Type >
void CppNoddy::SparseVector< _Type >::resize ( const std::size_t &  length)

Resize the maximum length of the sparse vector.

The maximum length is used in geometry checking.

Parameters
lengthThe new maximum length of the vector

Definition at line 207 of file SparseVector.cpp.

{
MAX_SIZE = length;
}
template<typename _Type >
void CppNoddy::SparseVector< _Type >::scale ( const _Type &  scale)

Scale each element of the vector.

Parameters
scaleThe value to scale each element by.

Definition at line 285 of file SparseVector.cpp.

{
for ( iter pos = VEC.begin(); pos != VEC.end(); ++pos )
{
pos -> second *= scale;
}
}
template<typename _Type >
_Type & CppNoddy::SparseVector< _Type >::set ( const std::size_t &  i)
inline

Set an element of the vector.

Parameters
iThe index to be accessed
Returns
A reference to the element

Definition at line 270 of file SparseVector.h.

{
#ifdef PARANOID
if ( i >= size() )
{
std::string problem;
problem = " The SparseVector.set method is trying to access \n";
problem += " outside the container. \n";
throw ExceptionRange( problem, size(), i );
}
#endif
return VEC[ i ];
}
template<typename _Type >
std::size_t CppNoddy::SparseVector< _Type >::size ( ) const
inline
template<typename _Type >
void CppNoddy::SparseVector< _Type >::sub ( const SparseVector< _Type > &  X)

Subtract a vector, element wise.

Parameters
XThe vector to be subtracted from this object.

Definition at line 301 of file SparseVector.cpp.

{
*this -= X;
}
template<typename _Type >
void CppNoddy::SparseVector< _Type >::swap ( const std::size_t &  i,
const std::size_t &  j 
)

Swap elements i and j.

Parameters
iThe index of the element to swap.
jThe index of the other element to swap.

Definition at line 359 of file SparseVector.cpp.

{
#ifdef PARANOID
if ( i >= size() || j >= size() )
{
std::string problem;
problem = " The SparseVector.swap method is trying to access \n";
problem += " outside the container. \n";
throw ExceptionRange( problem, size(), std::max( i, j ) );
}
#endif
std::swap<_Type>( VEC[ i ], VEC[ j ] );
}
template<typename _Type >
void CppNoddy::SparseVector< _Type >::swap ( SparseVector< _Type > &  X)
inline

Swap ALL elements with those of another SparseVector.

Parameters
XThe sparse vector to exchange with

Definition at line 333 of file SparseVector.h.

References CppNoddy::SparseVector< _Type >::size().

{
#ifdef PARANOID
if ( X.size() != size() )
{
std::string problem;
problem = " The SparseVector.swap method is trying to use \n";
problem += " two vectors of unequal length \n";
throw ExceptionGeom( problem, size(), X.size() );
}
#endif
VEC.swap( X.VEC );
}
template<typename _Type >
double CppNoddy::SparseVector< _Type >::two_norm ( ) const

l2-norm.

No attention paid to possible overflow for large vectors.

Returns
The square-root of the sum of the squares divided by number of elts.

Definition at line 257 of file SparseVector.cpp.

{
// Accumulate the ABS values of the container entries SQUARED
// using a fuction object.
double sum( 0.0 );
for ( citer pos = VEC.begin(); pos != VEC.end(); ++pos )
{
sum += std::pow( std::abs( pos -> second ), 2 );
}
return sum;
}

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

© 2012

R.E. Hewitt