gistfile1.cpp

#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; 
}