/*
 * 	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
 */ 

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)));					
	}
			
	public SparseMatrix (Matrix x ) 
	{
	}
	
    /**
     * 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);  							
 			} 			
 		} 		
 	}		
 	
 	public Object get (int r, int c)
	{ 		
 		return null;	
	}	
	public void addRow (int r)
	{			
	}	
	
	public void addCol (int c)
	{	
	}
		
	public Matrix getRow (int r)
	{
		return null;
	
	} 
	
	public Matrix getCol (int c)
	{
		return null;
	}
		
	public Matrix removeRow (int r)
	{
		return null;
	}
	
	public Matrix removeCol (int c) 
	{
		return null;
	}	
	
	//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();
    }
        
    //The functions below are only used 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)));
 			}
 		}    	
    }
}