Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <iostream>
#include <iomanip>
using namespace std;
#include "SparseMatrix.h"
int compare( const int x, const int y )
{
if( x < y )
return -1;
else if( x == y )
return 0;
else
return 1;
}
ostream &operator<<( ostream &output, const SparseMatrix &sparseMatrix )
{
int numRows = sparseMatrix.node->u.entry.row; // get the count of row
int numCols = sparseMatrix.node->u.entry.col; // get the count of col
MatrixNode * headers = sparseMatrix.node->right; // declare a pointer that point to header list
MatrixNode* current = headers->right; // declare a pointer that point to the first node in matrix
for ( int i = 0 ; i < numRows ; i++) // for loop excutes numRows times
{
for ( int j = 0 ; j < numCols ; j ++) // inner for loop excutes numCols times
{
if ( j == current->u.entry.col && i == current->u.entry.row ) // if the row and the col are equal i , j respectively , print value of node
{
cout << " " << current->u.entry.value ;
current = current->right ;
}
else
cout << " 0";
}
while ( current->u.next != sparseMatrix.node && current->tag == head )
current = current->u.next->right;
cout << endl;
}
return output;
}
SparseMatrix::SparseMatrix()
: node( 0 )
{
}
void SparseMatrix:: create( entryNode A[] )
{
node = new MatrixNode();
/* Create node */
node->tag = entry;
int numRow = node->u.entry.row = A[0].row;
int numCol = node->u.entry.col = A[0].col;
int numTerms = node->u.entry.value = A[0].value;
/* Create HeaderList */
int NumHeads = numRow > numCol ? numRow : numCol;
if ( NumHeads == 0 )
{
node->right = node; //if Matrix is empty , assign its self to the ertry node;
}
else
{
MatrixNode * heads = new MatrixNode[NumHeads]; //Allocate the needed node space from memory
for ( int i = 0 ; i < NumHeads ; i++)
{
heads[i].right = &heads[i]; // initialize the circular list header to point to itself
heads[i].down = &heads[i]; // initialize the circular list header to point to itself
heads[i].u.next = &heads[i]; // initialize the circular list header to point to itself
heads[i].tag = head;
}
int row ;
int col;
int value;
int currentRow = 0; // initialize the currently processed row with 0
MatrixNode * last = NULL;
MatrixNode * temp = NULL;
last = &heads[currentRow]; // initialize the last processed node with the first header
for ( int i = 0 ; i < numTerms ; i++)
{
row = A[i+1].row;
col = A[i+1].col;
value = A[i+1].value;
if (row > currentRow)
{
last->right = &heads[currentRow]; // if the row of current node is unequeal to current row then make last point to the row
currentRow = row;
last = &heads[row];
}
temp = new MatrixNode();
temp->tag = entry; // the type of insert node is entry
temp->u.entry.row = row;
temp->u.entry.col = col;
temp->u.entry.value = value;
last->right = temp; // last is point to the last node of current row ,assign temp to it's right pointer
last = temp; // the last node is changing
heads[col].u.next->down = temp; // let it pointer of down point to the last node of col
heads[col].u.next = temp;
}
last->right = &heads[currentRow];
for ( int i = 0; i < NumHeads; i++)
heads[i].u.next->down = &heads[i]; // let the last node of each col circular list point back to header
for ( int i = 0; i < NumHeads-1; i++)
heads[i].u.next = &heads[i+1]; // linked each header
heads[NumHeads-1].u.next = node; // let the last header point back to node
node->right = &heads[0]; // let node linked to headers
}
}
SparseMatrix SparseMatrix::operator+( SparseMatrix &op2 )
{
SparseMatrix sum ;
sum.node = new MatrixNode ;
sum.node -> tag = entry ;
sum.node -> u.entry.row = node -> u.entry.row ;
sum.node -> u.entry.col = node -> u.entry.col ;
int numCol = node -> u.entry.col ;
int numRow = node -> u.entry.row ;
int maxTerms = node -> u.entry.value + op2.node -> u.entry.value;
int numHeads = ( numCol > numRow ) ? numCol :numRow ;
/* Create HeaderList */
int NumHeads = numRow > numCol ? numRow : numCol;
if ( maxTerms == 0 )
{
sum.node->right = sum.node; //if Matrix is empty , assign its self to the ertry node;
}
else
{
MatrixNode * heads = new MatrixNode[NumHeads]; //Allocate the needed node space from memory
for ( int i = 0 ; i < NumHeads ; i++)
{
heads[i].right = &heads[i]; // initialize the circular list header to point to itself
heads[i].down = &heads[i]; // initialize the circular list header to point to itself
heads[i].u.next = &heads[i]; // initialize the circular list header to point to itself
heads[i].tag = head;
}
int row ;
int col;
int value;
int currentRow = 0; // initialize the currently processed row with 0
MatrixNode * last = NULL;
MatrixNode * temp = NULL;
last = &heads[currentRow]; // initialize the last processed node with the first header
MatrixNode * nodeA = node->right->right;
MatrixNode * nodeB = op2.node->right->right;
while ( nodeA != node && nodeA->tag == head )
nodeA = nodeA->u.next->right;
while ( nodeB != op2.node && nodeB->tag == head )
nodeB = nodeB->u.next->right;
do
{
if ( nodeA->tag == entry && nodeB->tag == entry )
{
if ( nodeA->u.entry.row == nodeB->u.entry.row )
{
switch ( compare( nodeA->u.entry.col , nodeB->u.entry.col ))
{
case -1:
row = nodeA->u.entry.row;
col = nodeA->u.entry.col;
value = nodeA->u.entry.value;
nodeA = nodeA->right;
break;
case 0 :
value = nodeA->u.entry.value + nodeB->u.entry.value;
row = nodeA->u.entry.row;
col = nodeA->u.entry.col;
nodeA = nodeA->right;
nodeB = nodeB->right;
break;
case 1:
row = nodeB->u.entry.row;
col = nodeB->u.entry.col;
value = nodeB->u.entry.value;
nodeB = nodeB->right;
break;
default:
break;
}
}
else if ( nodeA->u.entry.row < nodeB->u.entry.row )
{
/* if only A is entry and the row of nodeA is smaller than nodeB's , add nodeA to sum */
row = nodeA->u.entry.row;
col = nodeA->u.entry.col;
value = nodeA->u.entry.value;
nodeA = nodeA->right;
}
else if ( nodeA->u.entry.row > nodeB->u.entry.row )
{
row = nodeB->u.entry.row;
col = nodeB->u.entry.col;
value = nodeB->u.entry.value;
nodeB = nodeB->right;
}
}
if (row > currentRow)
{
last->right = &heads[currentRow]; // if the row of current node is unequeal to current row then make last point to the row
currentRow = row;
last = &heads[row];
}
temp = new MatrixNode();
temp->tag = entry; // the type of insert node is entry
temp->u.entry.row = row;
temp->u.entry.col = col;
temp->u.entry.value = value;
last->right = temp; // last is point to the last node of current row ,assign temp to it's right pointer
last = temp; // the last node is changing
heads[col].u.next->down = temp; // let it pointer of down point to the last node of col
heads[col].u.next = temp;
while ( nodeA->u.next != node && nodeA->tag == head )
nodeA = nodeA->u.next->right;
while ( nodeB->u.next != op2.node && nodeB->tag == head )
nodeB = nodeB->u.next->right;
}while ( nodeA->u.next != node && nodeB->u.next != op2.node );
while ( nodeA->u.next != node ) // ensure that all of MatrixA's nodes added in sum;
{
while ( nodeA ->u.next != node && nodeA->tag == head )
nodeA = nodeA->u.next->right;
if (nodeA->u.next == node) break;
row = nodeA->u.entry.row;
col = nodeA->u.entry.col;
value = nodeA->u.entry.value;
nodeA = nodeA->right;
if (row > currentRow)
{
last->right = &heads[currentRow]; // if the row of current node is unequeal to current row then make last point to the row
currentRow = row;
last = &heads[row];
}
temp = new MatrixNode();
temp->tag = entry; // the type of insert node is entry
temp->u.entry.row = row;
temp->u.entry.col = col;
temp->u.entry.value = value;
last->right = temp; // last is point to the last node of current row ,assign temp to it's right pointer
last = temp; // the last node is changing
heads[col].u.next->down = temp; // let it pointer of down point to the last node of col
heads[col].u.next = temp;
}
while ( nodeB->u.next != op2.node ) // ensure that all of MatrixB's nodes added in sum;
{
while ( nodeB ->u.next != op2.node && nodeB->tag == head )
nodeB = nodeB->u.next->right;
if (nodeB->u.next == op2.node) break;
row = nodeB->u.entry.row;
col = nodeB->u.entry.col;
value = nodeB->u.entry.value;
nodeB = nodeB->right;
if (row > currentRow)
{
last->right = &heads[currentRow]; // if the row of current node is unequeal to current row then make last point to the row
currentRow = row;
last = &heads[row];
}
temp = new MatrixNode();
temp->tag = entry; // the type of insert node is entry
temp->u.entry.row = row;
temp->u.entry.col = col;
temp->u.entry.value = value;
last->right = temp; // last is point to the last node of current row ,assign temp to it's right pointer
last = temp; // the last node is changing
heads[col].u.next->down = temp; // let it pointer of down point to the last node of col
heads[col].u.next = temp;
}
last->right = &heads[currentRow];
for ( int i = 0; i < NumHeads; i++)
heads[i].u.next->down = &heads[i]; // let the last node of each col circular list point back to header
for ( int i = 0; i < NumHeads-1; i++)
heads[i].u.next = &heads[i+1]; // linked each header
heads[NumHeads-1].u.next = sum.node; // let the last header point back to node
sum.node->right = &heads[0]; // let node linked to headers
}
return sum;
}
SparseMatrix SparseMatrix::operator*( SparseMatrix &op2 )
{
SparseMatrix product ;
product.node = new MatrixNode ;
product.node -> tag = entry ;
product.node -> u.entry.row = node -> u.entry.row ;
product.node -> u.entry.col = op2.node -> u.entry.col ;
int numCol = product.node -> u.entry.col ;
int numRow = product.node -> u.entry.row ;
int maxTerms = product.node -> u.entry.row * product.node -> u.entry.col;
int numHeads = ( numCol > numRow ) ? numCol :numRow ;
/* Create HeaderList */
int NumHeads = numRow > numCol ? numRow : numCol;
if ( maxTerms == 0 )
{
product.node->right = product.node; //if Matrix is empty , assign its self to the ertry node;
}
else
{
MatrixNode * heads = new MatrixNode[NumHeads]; //Allocate the needed node space from memory
for ( int i = 0 ; i < NumHeads ; i++)
{
heads[i].right = &heads[i]; // initialize the circular list header to point to itself
heads[i].down = &heads[i]; // initialize the circular list header to point to itself
heads[i].u.next = &heads[i]; // initialize the circular list header to point to itself
heads[i].tag = head;
}
int row ;
int col;
int value;
int currentRow = 0; // initialize the currently processed row with 0
MatrixNode * last = NULL;
MatrixNode * temp = NULL;
last = &heads[currentRow]; // initialize the last processed node with the first header
MatrixNode * rowA = node->right->right;
MatrixNode * colB = op2.node->right->down;
int cRow = 0;
int cCol = 0;
do
{
value = 0;
while ( rowA->tag == entry && colB->tag == entry ) // ensure that two node are entry
{
switch (compare( rowA->u.entry.col , colB->u.entry.row ) ) // compare col of A and row of B , the smaller will point to next node
{
case -1:
rowA = rowA->right;
break;
case 0: // if equal , this node can be multed
row = rowA->u.entry.row;
col = colB->u.entry.col;
value += rowA->u.entry.value * colB->u.entry.value;
rowA = rowA->right;
colB = colB->down;
break;
case 1:
colB = colB->down;
default:
break;
}
}
if ( value != 0) // ensure the value of addition is bigger than 0
{
if (row > currentRow)
{
last->right = &heads[currentRow]; // if the row of current node is unequeal to current row then make last point to the row
currentRow = row;
last = &heads[row];
}
temp = new MatrixNode();
temp->tag = entry; // the type of insert node is entry
temp->u.entry.row = row;
temp->u.entry.col = col;
temp->u.entry.value = value;
last->right = temp; // last is point to the last node of current row ,assign temp to it's right pointer
last = temp; // the last node is changing
heads[col].u.next->down = temp; // let it pointer of down point to the last node of col
heads[col].u.next = temp;
}
if ( rowA->tag == head || colB->tag == head ) // if one of rowA or colB is end , then change to next colume of B or change to next row of A
{
cCol += 1;
if ( cCol < numCol ) // change to next colume of B
{
rowA = node->right[cRow].right;
colB = op2.node->right[cCol].down;
}
else // change to next row of A
{
cCol = 0;
cRow += 1;
rowA = node->right[cRow].right;
colB = op2.node->right[cCol].down;
}
}
}while ( cRow <= 5 ); // while_loop excute when cRow smaller than amount of row
last->right = &heads[currentRow];
for ( int i = 0; i < NumHeads; i++)
heads[i].u.next->down = &heads[i]; // let the last node of each col circular list point back to header
for ( int i = 0; i < NumHeads-1; i++)
heads[i].u.next = &heads[i+1]; // linked each header
heads[NumHeads-1].u.next = product.node; // let the last header point back to node
product.node->right = &heads[0]; // let node linked to headers
}
return product;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment