/*
 * 	22C:021 Java Structures 
 *	Project 1 - SparseMatrix Implementaions 
 * 	By TA: Zhihong Wang (2004-10-25)
 * 
 * 	Methods implemented:
 * 	- SparseMatrix(int row,int col)
 * 	- set (int r, int c, Object val)
 *	- width()
 *	- height()
 *	- dump() to print out the 3 Vectors
 *	
 *	- get(int r,int c)
 *	- print() to print out the matrix row by row 
 *	- addRow(int r)
 *	- addCol(int c)
 *	- SparseMatrix(Matrix x)
 *
 *	- getRow(int r)
 *	- getCol(int c)
 *	- removeRow(int r)
 *	- removeCol(int c)
 */ 

import structure.*;
public class SparseMatrix
{
	protected Vector values, columnPointers, rowIndices;
	protected int width, height;	
	
	/**
     * Constructs a sparse matrix such that all values are zeros.
     *
     * @pre row >= 0, col >= 0;<br>
     * @post constructs an h row by w column matrix<br>
     *
     * @param row Height of the matrix.
     * @param col Width of the matrix.
     */	
	public SparseMatrix (int row, int col)
	{		
		height = row;
		width = col;
		
		//Initialize the three Vector variables
		values = new Vector();		
		rowIndices = new Vector();
		//Initialize all values in columnPointers to be -1
		columnPointers = new Vector(col);
		for(int i=0;i<col;i++)
			columnPointers.add((new Integer(-1)));					
	}
	
		
	/**
     * Constructs an equivalent SparseMatrix representaion of x
     *
     * @pre x is not null
     * @post onstructs a sparse matrix identical to given Matrix object
     *
     * @param x The Matrix object used to construct the sparse matrix.
     */	
	public SparseMatrix (Matrix x ) 
	{
		Assert.pre(x!=null, "Non-null Matrix reference to constructor.");
		height = x.height();
		width = x.width();
		
		//Initialize the three Vector variables
		values = new Vector();		
		rowIndices = new Vector();
		columnPointers = new Vector(width);
		for(int i=0;i<width;i++)
			columnPointers.add((new Integer(-1)));
		
		//Set all non-zero entries
		for(int i=0;i<height;i++)
		{
			for(int j=0;j<width;j++)
			{
				int val = ((Integer)x.get(i,j)).intValue();	
				if(val!=0)
					set(i,j,(new Integer(val)));
			}
		}
	}
	
	 /**
     * Return the width of the sparse matrix.      
     */
	public int width(){return width;}
	 
	 /**
     * Return the height of the sparse matrix.
     */
	public int height(){return height;}
		
	
	/**
     * Change the value at location (r, c) to val
     * @pre 0 <= r < height(), 0 <= c < width()
     * @post changes location (row, col) to val
     *
     * @param value The new Object reference (possibly null).
     * @param r The row of the value to be changed.
     * @param c The column of the value to be changed.	
     */	
 	public void set (int r, int c, Object val)
 	{ 	
		Assert.pre(0 <= r && r < height, "Row in bounds.");
		Assert.pre(0 <= c && c < width,"Column in bounds");
 	 	
 	 	//Get the integer value of parameter val	
 		int int_val = ((Integer)val).intValue();
 		
 		//Locate element at (r,c) in Vector values; 
 		//If the value at (r,c) was non-zero, then loc is the inserting position. 		
 		int loc = locate(r, c);
 		
 		//next_c is the first column behind c whose value in columnPointers is not -1.
 		//next_c = width if there is no such column. next_loc is the value for next_c in
 		//columnPointers.
 		int next_c = (c==width-1)? width : locateNonNegative(columnPointers, c+1, width-1);
 		int next_loc = (next_c==width)? values.size() : 
 						((Integer)columnPointers.get(next_c)).intValue(); 
 		 		
 		if( next_loc>loc && ((Integer)rowIndices.get(loc)).intValue()==r)//Value at (r,c) was non-zero. 		 
 		{
 			if(int_val != 0) //New value is also non-zero
 			{
 				values.set(loc, val);
 			}
 			else //New value is zero
 			{
 				//Remove it from values and update rowIndices and columnPointers.
 				values.remove(loc);
 				rowIndices.remove(loc); 				 				 
 				
 				int from = ((Integer)columnPointers.get(c)).intValue();
 				if((next_loc - from)==1) //Remove the only non-zero in column c
 				{
 					columnPointers.set(c, new Integer(-1));
 				}		
 				
 				//Increment columnPointers[c+1..width-1] by 1 if needed 								
 				decrementColumnPointersFrom(c+1);  							
 					 				
 			}
 		}
 		else //Value at (r,c) was zero
 		{
 			if(int_val != 0) //New value is non-zero
 			{
 				//Add it to Vector values and update rowIndices and columnPointers.
 				values.add(loc, val);
 				
 				rowIndices.add(loc, new Integer(r));
 				
 				int from = ((Integer)columnPointers.get(c)).intValue();
 				if(from == -1) //There was no non-zero in column c
 					columnPointers.set(c, new Integer(loc));
 				 							
 				//Increment columnPointers[c+1..width-1] by 1 if needed 
 				incrementColumnPointersFrom(c+1);  							
 			} 			
 		} 		
 	}	
 	
 	/**
     * Fetch an element from the matrix.
     * @pre 0 <= row < height(), 0 <= col < width()<br>
     * @post returns object at (row, col)<br>
     *
     * @param row The row of the element
     * @param col The column of the element
     * @return Object located at matrix position (row, col)
     */	
	public Object get (int r, int c)
	{
		Assert.pre(0 <= r && r < height, "Row in bounds.");
		Assert.pre(0 <= c && c < width,"Col in bounds");
			
		int from = ((Integer)columnPointers.get(c)).intValue();
		
		if (from==-1) //column c are all zeros
		{
			return new Integer(0);
		}
				
 		//next_c is the first column behind c whose value in columnPointers is not -1.
 		//next_c = width if there is no such column. next_loc is the value for next_c in
 		//columnPointers, which equals to values.size() if next_c = width.
 		int next_c = (c==width-1)? width : locateNonNegative(columnPointers, c+1, width-1);
 		int next_loc = (next_c==width)? values.size() : 
 						((Integer)columnPointers.get(next_c)).intValue(); 
 		
 		//search rowIndices[from..next_loc-1] for r 
 		int loc =  locateNoSmaller(rowIndices, from, next_loc-1, r);
 		
 		if(loc<next_loc && ((Integer)rowIndices.get(loc)).intValue()==r) 
 		{
 			//Value at (r,c) is non-zero.
 			return values.get(loc); 			
 		}
 		else //Value at (r,c) is zero.
 		{
 			return new Integer(0);
 		}	
	}
	
	
	/**
     * Add a new row of zeros, whose index will be r.
     *
     * @pre 0 <= r < height()
     * @post inserts row of null values to be row r
     *
     * @param r The index of the  newly inserted row.
     */	
	public void addRow (int r)
	{		
		Assert.pre(0 <= r && r < height, "Row in bounds.");		
		
		height++;
		for(int i=0;i<rowIndices.size();i++)
		{
			int row_index = ((Integer)rowIndices.get(i)).intValue();
			
			//Increase those row indices greater than 'r' by 1. 
			if(row_index>=r)
			{
				row_index++;
				rowIndices.set(i,(new Integer(row_index)));				
			}
		}		
	}
	
	/**
     * Add a new column of zeros, whose index will be c.
     *
     * @pre 0 <= c < width()
     * @post inserts column of null values to be column c
     *
     * @param c The index of the newly inserted column.
     */
	public void addCol (int c)
	{		
		Assert.pre(0 <= c && c < width,"Col in bounds");
		
		width++;
		columnPointers.add(c,(new Integer(-1)));
	}
		
  	/**
     * Get row r .
     * @pre 0 <= r < height()
     * @param r The index of the newly inserted column.
     * return a 2-row Matrix of non-zero values in row r and their column indices.
     */	
	public Matrix getRow (int r)
	{
		Assert.pre(0 <= r && r < height, "Row in bounds.");	
		
		//row_val_vect stores non-zeros in row r
		Vector row_val_vect = new Vector(); 		
		//col_vect stores column indices of non-zeros in row r
		Vector col_vect = new Vector(); 		
				
		int cur_col, next_col,next_col_loc;		
		//Find the first column in columnPointers not equal to "-1"		
		cur_col = locateNonNegative(columnPointers, 0, width-1);	
		if(cur_col== width) //matrix are all zeros
		{		
			return new Matrix(2,0);
		}			
				
		//Find the column behind cur_col in column Pointers which is not -1.
		next_col = (cur_col==width-1)? width : locateNonNegative(columnPointers, cur_col+1, width-1);
		if(next_col<width)
			next_col_loc = ((Integer)columnPointers.get(next_col)).intValue();
		else
			next_col_loc = values.size();
		
		//Traverse rowIndices for values in row r
		for(int i=0;i<rowIndices.size();i++)
		{
			int row_index = ((Integer)rowIndices.get(i)).intValue();		
			if(row_index==r) 
			{
				//Found a non-zero in row 'r', add into row_val_vect
				row_val_vect.add(values.get(i));
				
				//Get its column index
				if(i>=next_col_loc)
				{						
					//Get next_loc with location > i.				
					//values[i] is in column cur_col, the non-zero column before next_loc.
					while(i>=next_col_loc && next_col<width)
					{						
						cur_col = next_col;
						next_col = (cur_col==width-1)? width : locateNonNegative(columnPointers, cur_col+1, width-1);
						if(next_col<width)
						{ next_col_loc = ((Integer)columnPointers.get(next_col)).intValue();}
						else
						{ next_col_loc = values.size();}													
					}
				}				
				//So the value in row r just found is in column cur_col 					
				col_vect.add((new Integer(cur_col)));								
			}			
		}
		
		//Construct the returning matrix				, 
		Matrix ret_mat = new Matrix(2,row_val_vect.size());
		if(row_val_vect.size()>0)
		{
			for(int i=0;i<row_val_vect.size();i++)
			{
				ret_mat.set(0,i,row_val_vect.get(i));
				ret_mat.set(1,i,col_vect.get(i));
			}			
		}		
		return ret_mat;		
	} 
	
	/**
     * Get column c .
     * @pre 0 <= c < width()
     * @param c The index of the newly inserted column.
     * return a 2-column Matrix of non-zero values in column c and their row indices.
     */	
	public Matrix getCol (int c)
	{
		Assert.pre(0 <= c && c < width,"Col in bounds");	
		
		//col_val_vect stores non-zero value in column c 
		Vector col_val_vect = new Vector(); 
		//row_id_vect stores row indices for non-zeros in column c
		Vector row_id_vect = new Vector();
		int i,j;
		
		//Find the location of column c and next non-zero column behind c
		int start_loc, next_col, next_start_loc;		
		start_loc = ((Integer)columnPointers.get(c)).intValue();
	
		next_col = (c==width-1)? width : locateNonNegative(columnPointers, c+1, width-1);
		if(next_col<width)
		{
			next_start_loc = ((Integer)columnPointers.get(next_col)).intValue();
		}
		else
		{
			next_start_loc = values.size();
		}
		
		//Get values in column c and record in col_val_vect and row_id_vect
		if(start_loc!=-1)
		{
			for(i=start_loc;i<next_start_loc;i++)
			{
				col_val_vect.add(values.get(i));
				row_id_vect.add(rowIndices.get(i));								
			}						
		}
		 
		//Construct the returning matrix 		
		int nonzero_num =col_val_vect.size();
		Matrix ret_mat = new Matrix(nonzero_num,2);
		if(nonzero_num>0)
		{
			for(i=0;i<nonzero_num;i++)
			{
				ret_mat.set(i,0,col_val_vect.get(i));
				ret_mat.set(i,1,row_id_vect.get(i));
			}
		}
				
		return ret_mat;
	
	}
			
	/**
     * Remove the row whose index is r.
     * The row is returned as a vector.
     * @pre 0 <= r < height()<br>
     * @post removes row r and returns it as a matrix 
     *
     * @param r The index of the to-be-removed row.
     * @return a 2-row matrix of non-zero values once in the row 
     *  and their column indices
     */
	public Matrix removeRow (int r)
	{
		
		//Get non-zero values in row r and their column indices
		Matrix ret_mat = getRow(r);
		
		//Set all values in row r to be zeros
		// By this, we are removing these non-zeros from Vector values. 		
		int val_num = ret_mat.width();
		int i;
		for(i =0;i<val_num;i++)
		{
			int col = ((Integer)ret_mat.get(1,i)).intValue();
			set(r, col, (new Integer(0)));
		}
		
		//Decrement values in rowIndices >= r
		for(i=0;i<rowIndices.size();i++)
		{
			int row_int = ((Integer)rowIndices.get(i)).intValue();
			if(row_int>=r) //(actually only >r)
			{
				row_int --;
				rowIndices.set(i,(new Integer(row_int)));
			}
		}
				
		height--;
		
		return ret_mat;
	}
	
	/**
     * Remove a column, whose index is c.
     * @pre 0 <= c < width<br>
     * @post removes column c and returns it as a matrix
     *
     * @param c The index of the column to be removed.
     * @return a 2-column matrix storing the non-zero values once in column c 
     *  and their row indices.
     */
	public Matrix removeCol (int c) 
	{
		Assert.pre(0 <= c && c < width,"Col in bounds");
			
		//Get non-zero values in column c and their row indices
		Matrix ret_mat = getCol(c);
		
		//Set all values in column c to be zeros.
		// By this, we are removing these non-zeros from Vector values. 		
		int val_num = ret_mat.height();
		int i;
		for(i =0;i<val_num;i++)
		{
			int row = ((Integer)ret_mat.get(i,1)).intValue();
			set(row, c, (new Integer(0)));
		}
		
		//Remove the column from columnPointers.		
		columnPointers.remove(c);		
		width--;
						
		return ret_mat;		
	}   
	
	//Print values in the three Vectors
	public String dump()
    {
    	StringBuffer s = new StringBuffer();

		s.append("values: ");
		s.append("size = "+(new Integer(values.size())).toString());
		s.append(" capacity = "+(new Integer(values.capacity())).toString() +"\n");				
		s.append(values.toString()+"\n");

		s.append("columnPointers: ");
		s.append("size = "+(new Integer(columnPointers.size())).toString());
		s.append(" capacity = "+(new Integer(columnPointers.capacity())).toString() +"\n");
		s.append(columnPointers.toString()+"\n");

		s.append("rowIndices: ");
		s.append("size = "+(new Integer(rowIndices.size())).toString());
		s.append(" capacity = "+(new Integer(rowIndices.capacity())).toString() +"\n");
		s.append(rowIndices.toString()+"\n");
		
    	return s.toString();
    }
    
  
    //Print out the whole matrix
	public String print()
    {
		StringBuffer s = new StringBuffer();
		s.append("<Sparse Matrix:\n");
		for (int r = 0; r < height; r++)
		{
		    for (int c = 0; c < width; c++)
		    {
				//s.append("  <Row "+r+", Col "+c+", value=");
				Integer val_obj = (Integer)get(r,c);
				if(val_obj!=null)
				{	s.append(get(r,c)+"	"); }
				else
				{	s.append("0	"); }
		    }
		    s.append("\n");
		}
		s.append(">\n");
		return s.toString();
    }
    
    //The functions below are  used only by methods in the same class.
        
     /**
     * Locate element at (r,c) in Vector values (or rowIndices). 
     * @pre 0 <= r < height(), 0 <= c < width()
     *
     * @param r The row of the element
     * @param c The column of the element
     * @return the location of element (r,c) in Vector values if the value is non-zero;
     *  otherwise return a position where this value would be located if it is inserted.
     */	
    private int locate(int r, int c)
    {    	
		Assert.pre(0 <= r && r < height, "Row in bounds.");
		Assert.pre(0 <= c && c < width,"Column in bounds");    	
				
		//Find the first col starting from c whose value in columnPointers is not -1
		int c1 = locateNonNegative(columnPointers, c, width-1);
	
		int from,to;
		from = (c1==width)? values.size() : ((Integer)columnPointers.get(c1)).intValue();
				
		if(c1==c) //column c has non-zeros
		{
			//Find the col behind c whose value in columnPointers is not -1	
			int c2 = (c1==width-1)? width : locateNonNegative(columnPointers, c+1, width-1);	
								
			to = (c2==width)? 
				values.size():((Integer)columnPointers.get(c2)).intValue();		
			
			//Search rowIndices[from..to-1] for a value at least as large as r			
			return (locateNoSmaller(rowIndices, from, to-1, r));		
		}
		else
		{
			return from;
		}		
    }
    
    /**
     * Search sub-Vector data[left..right] for a non-negative integer.
     * @pre (data!=null)&&(0 <= left <= right < data.size())
     * @param data The Vector to be searched
     * @param left Start of searching
     * @param right End of searching 
     * @returns an index of the first non-negative integer found.
     * If data[left..right] contains no non-negative integer, it returns right+1.
     */	
    protected int locateNonNegative(Vector data, int left, int right)
    {
    	Assert.pre(data!=null, "Non-empty vector");
    	Assert.pre(0<=left && left<=right && right<data.size(),"Reasonable searching range");
    	    	
    	for(int i=left; i<= right; i++)
    	{
    		int val = ((Integer)data.get(i)).intValue();
    		if(val>=0)
    			return  i;   		
    	}    	
    	return right+1;    	
    }
    
    
    /**
     * Suppose Vector data is a sorted in increasing order, search data[left..right]
     * for an integer at least as large as x.
     * @pre (data!=null)&&(0 <= left <= right < data.size())
     * @param data The Vector to be searched
     * @param left Start of searching
     * @param right End of searching 
     * @param x The value to be compared to
     * @returns an index i of the first integer found at least as large as x.  
     *  If data[left..right] contains no such integer, it returns right+1;
     */	    
    protected int locateNoSmaller(Vector data, int left, int right, int x)
    {
    	Assert.pre(data!=null, "Non-empty vector");
    	Assert.pre(0<=left && left<=right &&  right<data.size(),"Reasonable searching range");    	
    	
    	for(int i=left; i<= right; i++)
    	{
    		int val = ((Integer)data.get(i)).intValue();
    		if(val>=x)
    		{
    			return i;
    		}
    	}
    	return right+1;    	
    }
       
    
    //Increment columnPointers[j](c<=j<width)by c if column j has non-zeros.    
    private void incrementColumnPointersFrom(int c)
    {
    	Assert.pre(1 <= c && c <= width," Input between 1 and width");
    	for(int j=c;j<width;j++)
 		{
 			int int_loc = ((Integer)columnPointers.get(j)).intValue();
 			if(int_loc!=-1)
 			{
 				int_loc++;
 				columnPointers.set(j,(new Integer(int_loc)));
 			}
 		}    	
    }
    
    //Decrement columnPointers[j](c<=j<width)by 1 if column j has non-zeros.
    private void decrementColumnPointersFrom(int c)
    {
    	Assert.pre(1 <= c && c <= width," Input between 1 and width");
    	for(int j=c;j<width;j++)
 		{
 			int int_loc = ((Integer)columnPointers.get(j)).intValue();
 			if(int_loc!=-1)
 			{
 				int_loc--;
 				columnPointers.set(j,(new Integer(int_loc)));
 			}
 		}    	
    }
}