Created
October 26, 2014 12:49
-
-
Save taida957789/647147d2b069bb4f8e37 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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