/*
* 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;
* @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);
}
}
}
/**
* Fetch an element from the matrix.
* @pre 0 <= row < height(), 0 <= col < width()
* @post returns object at (row, col)
*
* @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=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=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_col0)
{
for(int i=0;i0)
{
for(i=0;i
* @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= r
for(i=0;i=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
* @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\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=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