// SparseMatrix.cpp
// Author : Saket Soni
// Dated : 02-10-04
// Note : Class Assignment for Data & File Structures (MTech 1st Year)
// Platform : Win 98, Visual C++ 6.0
#include
#include
#include
using namespace std;
/////////////////////////
//
// Macro Definitions
// Following macro definitons modify the behaviour of the program, as
// commented against each macro definition.
//
/////////////////////////
//#define OUTPUT // enable this macro if you want to some file
//#define STRICT_TYPING // enable this macro if you want implement
// strict typing rules for input
#define SILENT_INPUT // enable this macro if you want to disable
// echoing of commands during input of matrix
// elements
/////////////////////////
//
// Macro Dependency Check
// Following code check the various dependencies between the macros, as
// commented against each dependency check.
//
/////////////////////////
#ifdef OUTPUT // if OUTPUT is enabled then strict typing rules
#ifdef STRICT_TYPING // cause problem, hence disabling STRICT_TYPING
#undef STRICT_TYPING
#endif
#endif
#ifdef SILENT_INPUT // if SILENT_INPUT is enabled, then STRICT_TYPING
#ifdef STRICT_TYPING // and OUTPUT cause problem, hence disabling them.
#undef STRICT_TYPING
#endif
#ifdef OUTPUT
#undef OUTPUT
#endif
#endif
/////////////////////////
//
// Class SparseMatrix Declaration
// This class provides functions for inserting elements into a sparse matrix
// and to multiply two sparse matrices.
//
/////////////////////////
class SparseMatrix
{
private:
class Ele; // This class models the elements of the matrix.
private:
const unsigned int iMaxRow; // Dimension of the matrix, it is constant
const unsigned int iMaxCol; // for each object of this class.
Ele **pRow; // To store the base address of the array which stores the
// starting address of each row.
Ele **pCol; // To store the base address of the array which stores the
// starting address of each col.
public:
class SparseMError; // Member function of the SparseMatrix class throw
// exceptions of this class type.
public:
static void setErrorNo (SparseMError & e, int errno) throw();
// This function is friend to class SparseMError
// and is used to set the ErrNo which is private
// in SparseMError and hence unaccessable from
// SparseMatrix class.
private:
void DeleteAllElements() throw();
// to delete all elements in the array. Just deleting
// all elements is not sufficient to covert the matrix
// into a null matrix.
private:
SparseMatrix(SparseMatrix &m)
:iMaxRow(m.iMaxRow),iMaxCol(m.iMaxCol),pRow(m.pRow),pCol(m.pCol) /// throw()
// Copy constructor. It is made private so as
// to prevent copy initialization of objects
// from outside the class
{}
private:
void Nullify() throw();
Ele * ReadNewElement() throw(const SparseMError &);
// Creates a new object of type Ele and reads
// input into it from the user, and then
// returns its reference as a pointer.
void InsertElement(Ele * const) throw();
// Adds the new element into the matrix or replaces the old element with the
// new value, but if the element allready exists and the value of new
// element is zero then, that element is deleted from the matrix.
// If no corresponding element exits, and the value of new element is zero,
// then nothing is done and new element is deleted, i.e. we can say
// this function both inserts and deletes elements from the matrix.
public:
SparseMatrix(int row = 3, int col = 3); /// throw(const SparseMError &);
// Default constructor, it initializes the new created matrix as
// null matrix.
~SparseMatrix() throw();
// destructor.
void ReadMatrix() throw(const SparseMError &);
// For reading the whole matrix from the user. It uses InsertElement()
// for reading individual elements.
SparseMatrix & MultiplyMatrix (SparseMatrix &, SparseMatrix &) throw(const SparseMError&);
// For multiplying two matrices. The result is stored in the object
// which calls this function.
void ShowMatrix();
// For displaying the contents of a matrix.
};
/////////////////////////
//
// Class Ele Declaraton
// This class is a private member of SparseMatrix class, and hence unaccessable from
// outside. It is used to model individual elements of the SparseMatrix class. All members
// of this class are public and hence freely accessable with SparseMatrix class.
//
/////////////////////////
class SparseMatrix::Ele
{
public:
float fValue; // for value of the element
int iRowOfEle; // for row number of the element
int iColOfEle; // for col number of the element
Ele *pRight; // pointer to next right non zero element on the same row.
Ele *pDown; // pointer to next down non zero element on the same col.
public:
Ele(int val = 0, int row = -1, int col = -1):
fValue(val),iRowOfEle(row),iColOfEle(col),pRight(0),pDown(0) /// throw()
{} // Default constructor for the Ele class
};
/////////////////////////
// Class SparseMError Declaration
// This class is a public member of SparseMatrix class, hence its public members are
// freely accessable from outside. Member functions of SparseMatrix class throw
// objects of this class as exception. That is this class models the error handling
// mechanism of the SparseMatrix class.
//
/////////////////////////
class SparseMatrix::SparseMError : public std::exception
{ // publically inherited from the standard
// exception class.
private:
int iErrNo; // Defines the particular error.
public:
SparseMError():iErrNo(7) /// throw()
{} // default value is for "undefined error"
operator int () const throw() { // enables the outside world to read the
return iErrNo; // the iErrNo.
}
const char* what() const throw() // returns an error message
{ // corresponding to iErrNo.
static char *pErrMsg[] = {
"Sparse Matrix : no error", // 0
"Sparse Matrix : cannot allocate memory for row header", // 1
"Sparse Matrix : cannot allocate memory for col header", // 2
"Sparse Matrix : cannot allocate memory for element", // 3
"Sparse Matrix : row index of element is out of permissible range", // 4
"Sparse Matrix : col index of element is out of permissible range", // 5
"Sparse Matrix : cannot multiply inconsistent matrices", // 6
"Sparse Matrix : undefined error", // 7
};
return pErrMsg[iErrNo];
}
friend void SparseMatrix::setErrorNo(SparseMError & e,int errno) throw();
// This is member function of SparseMatrix class, declared
// friend over here. It is used for setting the iErrNo from
// within the member functions of SparseMatrix class.
};
/////////////////////////
//
// Function Definitions of the SparseMatrix class follows ...
//
/////////////////////////
void SparseMatrix::setErrorNo (SparseMError & e, int errno) throw()
{
e.iErrNo = errno; // set the error no of the error object.
}
SparseMatrix::SparseMatrix(int row, int col):iMaxRow(row),iMaxCol(col)
/// throw(const SparseMError &e)
{
SparseMError e;
try { pRow = new Ele*[iMaxRow]; } // create array to starting
catch(const bad_alloc & ) // ne) // address of each row.
{
setErrorNo(e,1);
throw e;
}
try { pCol = new Ele*[iMaxCol]; } // create array to starting address
catch(const bad_alloc & ) // ne) // of each col.
{
setErrorNo(e,2);
throw e;
}
// initialize the row and col starting address with NULL.
int iSmallMax = ( iMaxRow > iMaxCol ) ? iMaxCol : iMaxRow ;
for ( int j = 0 ; j < iSmallMax ; j++ ) {
pRow[j] = NULL; pCol[j] = NULL;
}
j = iSmallMax;
if ( iMaxRow > iMaxCol )
for ( ; j < iMaxRow ; j++ )
pRow[j] = NULL;
else
for ( ; j < iMaxCol ; j++ )
pCol[j] = NULL;
}
SparseMatrix::~SparseMatrix() throw()
{
DeleteAllElements(); // to delete all elements in the array.
delete[] pRow; // to delete the array of starting row address.
delete[] pCol; // to delete the array of starting col address.
}
void SparseMatrix::DeleteAllElements() throw()
// to delete all elements in the array. Just deleting
// all elements is not sufficient to covert the matrix
// into a null matrix.
{
int j;
Ele *ptr, *tptr;
for ( j = 0 ; j < iMaxRow ; j++ ) {
ptr = pRow[j];
while ( ptr ) {
tptr = ptr->pRight;
delete ptr;
ptr = tptr;
}
}
}
void SparseMatrix::Nullify() throw()
// converts the matrix into a null matrix, by first deleting
// all elements in the matrix, and then setting each element
// of the two array of address to NULL.
{
DeleteAllElements(); // to delete all elements in the array.
// setting all starting row and col address to NULL.
int iSmallMax = ( iMaxRow > iMaxCol ) ? iMaxCol : iMaxRow ;
for ( int j = 0 ; j < iSmallMax ; j++ ) {
pRow[j] = NULL; pCol[j] = NULL;
}
j = iSmallMax;
if ( iMaxRow > iMaxCol )
for ( ; j < iMaxRow ; j++ )
pRow[j] = NULL;
else
for ( ; j < iMaxCol ; j++ )
pCol[j] = NULL;
}
void SparseMatrix::ReadMatrix() throw(const SparseMError & )
// reads the whole matrix from the user.
{
Nullify(); // first convert to null matrix, so that
// all previous enteries are deleted
char ch = 'y';
Ele *nptr, ptr, lptr;
do {
try { nptr = ReadNewElement(); } // create new Ele and then read
// input into it from the user.
catch ( const SparseMError & e ) { // if error in reading input then
if ( e == 4 || e == 5 ) { // show error message and then retry.
cout << e.what() << endl;
continue;
}
else
throw e;
}
InsertElement(nptr); // add read Ele to the matrix.
#ifndef SILENT_INPUT
cout << "Enter another ? "; // ask for another input
#endif
cin >> ch;
#ifdef STRICT_TYPING
while ( cin.get() != '\n' );
#endif
#ifdef OUTPUT
if ( ch == 'n' || ch == 'N' )
cout << "no" << endl;
else
cout << "yes" << endl;
#endif
} while ( ch != 'n' && ch != 'N' ); // repeat while not no
}
SparseMatrix::Ele * SparseMatrix::ReadNewElement() throw(const SparseMError &)
// creates a new Ele and reads
// input into it from the user,
// and then returns its address.
{
SparseMError e;
Ele *ptr;
try { ptr = new Ele; } // create new Ele
catch ( const bad_alloc & ) // ne)
{
setErrorNo(e,3);
throw e;
}
#ifndef SILENT_INPUT
cout << "Enter Row No : ";
#endif
cin >> ptr->iRowOfEle; // reading row number of new element
while ( cin.fail() == true ) { // for typographical errors
cin.clear();
cerr << "Invalid Row No!" << endl;
while ( cin.get() != '\n' );
#ifndef SILENT_INPUT
cout << "Enter Row No : ";
#endif
cin >> ptr->iRowOfEle;
}
if ( (ptr->iRowOfEle < 0) || (ptr->iRowOfEle >= iMaxRow) ) {
delete ptr; // if row number is out of the
setErrorNo(e,4); // bound then throw exception.
throw e;
}
#ifdef STRICT_TYPING
while ( cin.get() != '\n' );
#endif
#ifdef OUTPUT
cout << ptr->iRowOfEle << endl;
#endif
#ifndef SILENT_INPUT
cout << "Enter Col No : ";
#endif
cin >> ptr->iColOfEle; // reading col number of new element
while ( cin.fail() == true ) { // for typographical errors
cin.clear();
cerr << "Invalid Col No!" << endl;
while ( cin.get() != '\n' );
#ifndef SILENT_INPUT
cout << "Enter Col No : ";
#endif
cin >> ptr->iColOfEle;
}
if ( (ptr->iColOfEle < 0) || (ptr->iColOfEle >= iMaxCol) ) {
delete ptr; // if col number is out of the
setErrorNo(e,5); // bound then throw exception.
throw e;
}
#ifdef STRICT_TYPING
while ( cin.get() != '\n' );
#endif
#ifdef OUTPUT
cout << ptr->iColOfEle << endl;
#endif
#ifndef SILENT_INPUT
cout << "Enter Value : ";
#endif
cin >> ptr->fValue; // reading value of new element
while ( cin.fail() == true ) { // for typographical errors
cin.clear();
cerr << "Invalid Value!" << endl;
while ( cin.get() != '\n' );
#ifndef SILENT_INPUT
cout << "Enter Value : ";
#endif
cin >> ptr->fValue;
}
#ifdef STRICT_TYPING
while ( cin.get() != '\n' );
#endif
#ifdef OUTPUT
cout << ptr->fValue << endl;
#endif
return ptr;
}
void SparseMatrix::InsertElement(Ele * const ele) throw()
// Adds the new element into the matrix or replaces the old element with the
// new value, but if the element allready exists and the value of new
// element is zero then, that element is deleted from the matrix.
// If no corresponding element exits, and the value of new element is zero,
// then nothing is done
{
Ele *ptr, *lptr;
// to find the existence of ele in the matrix, and the preceding non zero element in
// the ele's row.
lptr = NULL; // keeps track of preceding element
ptr = pRow[ele->iRowOfEle]; // to venture into the new element
while ( ptr != NULL && ptr->iColOfEle < ele->iColOfEle ) {
lptr = ptr; // check only till the col no of current
ptr = ptr->pRight; // element is less than that of ele
}
if ( ptr == NULL && ele->fValue == 0 ) // the element dosen't exists
return; // and hence cannot be deleted
else if ( ptr != NULL && ptr->iColOfEle == ele->iColOfEle )
{
if ( ele->fValue ) // element exists and has to be replaced
{
ptr->fValue = ele->fValue;
delete ele;
}
else { // element exists and has to be deleted
Ele * lcptr = NULL;
Ele * tptr = pCol[ptr->iColOfEle];
while ( tptr != ptr ) { // to delete first find the preceding
lcptr = tptr; // non-zero element in the ele's col.
tptr = tptr->pDown;
}
lcptr->pDown = ptr->pDown;
lptr ->pRight = ptr->pRight;
delete ptr;
delete ele;
}
}
else { // if element dosen't exist and has to be inserted.
ele->pRight = ptr; // insert ele in the row list.
if ( lptr )
lptr->pRight = ele;
else
pRow[ele->iRowOfEle] = ele;
lptr = NULL; // to insert first find the preceding
ptr = pCol[ele->iColOfEle]; // non-zero element in the ele's col.
while ( ptr != NULL && ptr->iRowOfEle < ele->iRowOfEle ) {
lptr = ptr;
ptr = ptr->pDown;
}
ele->pDown = ptr; // insert ele in the col list
if ( lptr )
lptr->pDown = ele;
else
pCol[ele->iColOfEle] = ele;
}
}
void SparseMatrix::ShowMatrix() // to display the contents of the matrix
{
Ele *ptr;
for ( int j = 0 ; j < iMaxRow ; j++ ) // loop - iterates j for each row.
{
ptr = pRow[j]; // initialize ptr with starting row address
int k = 0; // k is for col
while ( ptr )
{
while ( k++ < ptr->iColOfEle )// display zeros for non-existent elements
cout << setw(10) << '0' << " ";
cout << setw(10) << ptr->fValue << " ";// display the existing element
ptr = ptr->pRight; // go to next non-zero element
}
while ( k++ < iMaxCol ) // display zeros for non-existent
cout << setw(10) << '0' << " "; // elements which are after the last
cout << endl; // existing element in the row.
}
}
SparseMatrix & SparseMatrix::MultiplyMatrix (SparseMatrix & M1, SparseMatrix & M2)
throw(const SparseMError&)
// For multiplying two matrices. The result is stored in the object
// which calls this function.
{
if ( M1.iMaxCol != M2.iMaxRow ) { // first check if the two matrices are
SparseMError e; // consistent or not, if inconsistent
setErrorNo(e,6); // then throw exception.
throw e;
}
Nullify(); // convert the resultant matrix to null matrix.
Ele *ptr1, *ptr2;
float sum;
for ( int ir = 0, ic ; ir < iMaxRow ; ir++ ) // iterate ir for each row
{
for ( ic = 0 ; ic < iMaxCol ; ic++ ) // iterate ic for each col
{
sum = 0; // initialize with zero
ptr1 = M1.pRow[ir]; // starting of the ir th row
ptr2 = M2.pCol[ic]; // starting of the ic th col
while ( ptr1 != NULL && ptr2 != NULL ) // repeat while atleast one of the two
// becomes null
{
while ( ptr1 != NULL && ptr2 != NULL &&// find matching non-zero
ptr1->iColOfEle != ptr2->iRowOfEle ) // elements
{
if ( ptr1->iColOfEle < ptr2->iRowOfEle )
ptr1 = ptr1->pRight;
else
ptr2 = ptr2->pDown;
}
if ( ptr1 != NULL && ptr2 != NULL && // if found, add their
ptr1->iColOfEle == ptr2->iRowOfEle ) // product into the sum
{ // variable
sum += ptr1->fValue * ptr2->fValue;
ptr1 = ptr1->pRight;
ptr2 = ptr2->pDown;
}
}
if ( sum ) { // insert element only if sum is non zero
try {
ptr1 = new Ele; // create new element for insertion
}
catch (const bad_alloc &) // ne)
{
SparseMError e;
setErrorNo(e,3);
throw e;
}
ptr1->fValue = sum; // copy values into the new element
ptr1->iRowOfEle = ir;
ptr1->iColOfEle = ic;
InsertElement(ptr1); // insert the new element
}
}
}
return *this;
}
/////////////////////////
//
// main function
// It is the Application entry point.
//
/////////////////////////
int main()
{
int nRowsInA, nColsInA, nRowsInB, nColsInB;
try { // start of try block
cout << "Enter order of Matrix A : "; // reading order of matrix A
cin >> nRowsInA >> nColsInA;
while ( cin.fail() == true ) { // for typographical errors
cin.clear();
cerr << "Invalid Input for Order of Matrix A!" << endl;
while ( cin.get() != '\n' );
cout << "Enter order of Matrix A : ";
cin >> nRowsInA >> nColsInA;
}
#ifdef STRICT_TYPING
while ( cin.get() != '\n' );
#endif
#ifdef OUTPUT
cout << nRowsInA << " " << nColsInA << endl;
#endif
cout << "Enter order of Matrix B : "; // reading order of Matrix B
cin >> nRowsInB >> nColsInB;
while ( cin.fail() == true ) { // for typographical errrors
cin.clear();
cerr << "Invalid Input for Order of Matrix B!" << endl;
while ( cin.get() != '\n' );
cout << "Enter order of Matrix B : ";
cin >> nRowsInB >> nColsInB;
}
#ifdef STRICT_TYPING
while ( cin.get() != '\n' );
#endif
#ifdef OUTPUT
cout << nRowsInB << " " << nColsInB << endl;
#endif
if ( nColsInA != nRowsInB ) { // if matrices are inconsistent
SparseMatrix::SparseMError e; // for multiplication throw
SparseMatrix::setErrorNo(e,6); // exception
throw e;
}
} // end of try block
catch(const SparseMatrix::SparseMError & e) // if any error occurs
{ // show corresponding
cerr << e.what(); // error messages.
return 1;
}
try { // start of try block
SparseMatrix A(nRowsInA,nColsInA);
SparseMatrix B(nRowsInB,nColsInB);
SparseMatrix C(nRowsInA,nColsInB); // create three matrices
// read input into A
cout << endl << "Enter Matrix A ..." << endl;
A.ReadMatrix();
// read input into B
cout << endl << "Enter Matrix B ..." << endl;
B.ReadMatrix();
cout << endl << "A is ..." << endl; // show matrix A
A.ShowMatrix();
cout << endl << "B is ..." << endl; // show matrix B
B.ShowMatrix();
C.MultiplyMatrix(A,B); // calculate the product
cout << endl << "A X B is ..." << endl;
C.ShowMatrix(); // display the product
} // end of try block
catch(const SparseMatrix::SparseMError & e) // if any error occurs
{ // show corresponding
cerr << e.what(); // error messages.
return 1;
}
// cin.get();
return 0;
}