/*
* 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;
* @post constructs an h row by w column matrix
*
* @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
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=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=x)
{
return i;
}
}
return right+1;
}
//Increment columnPointers[j](c<=j