Problem 2: Sparse Matrix Using Linked List (5 pts)

Implement the linked list sparse matrix class (LLSparseMat.java) so that LLMainClass can be executed with MAT argument.

RowHead nodes correspond to nonzero rows. Each rowhead node stores a LLSparseVec, storing a nonzero row. It also has a pointer to the next rowhead.

When a row becomes empty (no nonzero elements), the rowhead should be removed.

Implement the constructor, accessor methods:

getElement, setElement, clearElement, numElements (returns number of non-zero elements).

getRowIndices returns an array of indices of rows with nonzero elements.

getOneRowColIndices returns an array of nonzero column indices of the row. Use LLSparseVec.getAllIndices().

getOneRowValues returns an array of nonzero values. Use LLSparseVec.getAllValues().

NOTE that these methods should all be linear to the number of nonzero rows or nonzero elements.

Sanity check: when LLMainClass is called using MAT argument and with a single input file, the program should be able to run correctly and give the same output as ArrayMainClass.

//Linked List Sparse Matrix Class

public class LLSparseM implements SparseM {

public LLSparseM(int nr, int nc){

return;

}

@Override

public int nrows() {

// TODO Auto-generated method stub

return 0;

}

@Override

public int ncols() {

// TODO Auto-generated method stub

return 0;

}

@Override

public int numElements() {

// TODO Auto-generated method stub

return 0;

}

@Override

public int getElement(int ridx, int cidx) {

// TODO Auto-generated method stub

return 0;

}

@Override

public void clearElement(int ridx, int cidx) {

// TODO Auto-generated method stub

}

@Override

public void setElement(int ridx, int cidx, int val) {

// TODO Auto-generated method stub

}

@Override

public int[] getRowIndices() {

// TODO Auto-generated method stub

return null;

}

@Override

public int[] getColIndices() {

// TODO Auto-generated method stub

return null;

}

@Override

public int[] getOneRowColIndices(int ridx) {

// TODO Auto-generated method stub

return null;

}

@Override

public int[] getOneRowValues(int ridx) {

// TODO Auto-generated method stub

return null;

}

@Override

public int[] getOneColRowIndices(int cidx) {

// TODO Auto-generated method stub

return null;

}

@Override

public int[] getOneColValues(int cidx) {

// TODO Auto-generated method stub

return null;

}

@Override

public SparseM addition(SparseM otherM) {

// TODO Auto-generated method stub

return null;

}

@Override

public SparseM substraction(SparseM otherM) {

// TODO Auto-generated method stub

return null;

}

@Override

public SparseM multiplication(SparseM otherM) {

// TODO Auto-generated method stub

return null;

}

}

//LLMainClass

import java.util.Scanner; import java.io.File;

public class LLMainClass {

public static SparseM ParseMatrix(String file_name){ Scanner sc = null; String tmps; SparseM M = null; try { sc = new Scanner(new File(file_name)); while (sc.hasNext()) { tmps = sc.next(); if(tmps.equals("MATRIX")){ // initialize the matrix int nr = sc.nextInt(); int nc = sc.nextInt(); M = new LLSparseM(nr,nc); }else if(tmps.equals("END")){ // finished, return the matrix sc.close(); return M; }else if(tmps.equals("SET")){ // set an element int ridx = sc.nextInt(); // row index int cidx = sc.nextInt(); // col index int val = sc.nextInt(); // value M.setElement(ridx, cidx, val); }else if(tmps.equals("CLEAR")){ // clear an element int ridx = sc.nextInt(); // row index int cidx = sc.nextInt(); // col index M.clearElement(ridx, cidx); } } sc.close(); return M; } catch (Exception e) { return null; } } public static SparseVec ParseVector(String file_name){ Scanner sc = null; String tmps; SparseVec V = null; try { sc = new Scanner(new File(file_name)); while (sc.hasNext()) { tmps = sc.next(); if(tmps.equals("VECTOR")){ // initialize the matrix int len = sc.nextInt(); V = new LLSparseVec(len); }else if(tmps.equals("END")){ // finished, return the matrix sc.close(); return V; }else if(tmps.equals("SET")){ // set an element int idx = sc.nextInt(); // index int val = sc.nextInt(); // value V.setElement(idx, val); }else if(tmps.equals("CLEAR")){ // clear an element int idx = sc.nextInt(); // index V.clearElement(idx); } } sc.close(); return V; } catch (Exception e) { return null; } } public static void main(String[] args) { try{ int n = args.length; if(n < 2){ System.out.println("java LLMainClass VEC/MAT File1 A/S/M File2 ..."); return; } String fname; String operator; String dtype = args[0]; // matrix or vector if(dtype.equals("VEC")){ fname = args[1]; SparseVec V = ParseVector(fname); // read V from the first file if(V == null){ // if invalid input file, print NULL and exit System.out.println("NULL: Illegal Input File "+fname); return; } SparseVec tmpV; for(int i = 2; i < n; i+=2){ operator = args[i]; fname = args[i+1]; tmpV = ParseVector(fname); // read tmpM from the next file if(tmpV == null) // if the file is invalid, skip { System.out.println("NULL: Illegal Input File "+fname); return; } if(operator.equals("A")) V = V.addition(tmpV); // add tmpV to V else if(operator.equals("S")) V = V.substraction(tmpV); // substract tmpV from V else if(operator.equals("M")) V = V.multiplication(tmpV); // multiply tmpV to V else{ System.out.println("NULL: Illegal operator: " + operator ); return; } if(V == null) // operation failed { System.out.println("NULL: Operator "+operator+" Failed, Fname "+fname); return; } } // output the final matrix System.out.println("Final_Vector"); int[] idx = V.getAllIndices(); int[] val = V.getAllValues(); int len, ne; len = V.getLength(); // length ne = V.numElements(); // number of elements System.out.println("LENGTH " + len + " NELEMS " + ne); for(int i = 0; i < ne; i++) System.out.println("IDX " + idx[i] + " VAL " + val[i]); System.out.println("END"); }else if(dtype.equals("MAT")){ fname = args[1]; SparseM M = ParseMatrix(fname); // read M from the first file if(M == null){ // if invalid input file, print NULL and exit System.out.println("NULL: Illegal Matrix Input, Fname " + fname); return; } SparseM tmpM; for(int i = 2; i < n; i+=2){ operator = args[i]; fname = args[i+1]; tmpM = ParseMatrix(fname); // read tmpM from the next file if(tmpM == null) // if the file is invalid, skip { System.out.println("NULL: Illegal Input, Fname " + fname); return; } if(operator.equals("A")) M = M.addition(tmpM); // add tmpM to M else if(operator.equals("S")) M = M.substraction(tmpM); // substract tmpM from M else if(operator.equals("M")) M = M.multiplication(tmpM); // multiply tmpM to M else{ System.out.println("NULL: Illegal operator: " + operator ); return; } if(M == null) // if the file is invalid, skip { System.out.println("NULL: Operation "+operator + " Failed, Fname "+ fname); return; } } // output the final matrix System.out.println("FINAL_MATRIX"); int nr, nc, ne; nr = M.nrows(); // number of rows nc = M.ncols(); // number of columns ne = M.numElements(); // number of elements System.out.println("NROWS " + nr + " NCOLS " + nc + " NELEMS " + ne); // print the matrix in rows int[] ridx_list = M.getRowIndices(); System.out.println("NUM_ROWS "+ridx_list.length); for(int ridx : ridx_list){ System.out.println("ROW "+ridx); int[] one_row_cidx_list = M.getOneRowColIndices(ridx); int[] one_row_vals_list = M.getOneRowValues(ridx); for(int i = 0; i < one_row_cidx_list.length; ++i) System.out.println("RIDX "+ridx+" CIDX " + one_row_cidx_list[i] + " VAL " + one_row_vals_list[i]); } // print the matrix in cols int[] cidx_list = M.getColIndices(); System.out.println("NUM_COLS "+cidx_list.length); for(int cidx : cidx_list){ System.out.println("COL "+cidx); int[] one_col_ridx_list = M.getOneColRowIndices(cidx); int[] one_col_vals_list = M.getOneColValues(cidx); for(int i = 0; i < one_col_ridx_list.length; ++i) System.out.println("RIDX "+one_col_ridx_list[i]+" CIDX " + cidx + " VAL " + one_col_vals_list[i]); } System.out.println("END"); }else{ System.out.println("The first argument has to be either VEC or MAT, meaning the data is Vector or Matrix"); return; } } catch (Exception e) { System.out.println("NULL: Something is wrong"); return; } } }

// LL Sparse Vec

public class LLSparseVec implements SparseVec {

public LLSparseVec(int len){ return; }

@Override public int getLength() { // TODO Auto-generated method stub return 0; }

@Override public int numElements() { // TODO Auto-generated method stub return 0; }

@Override public int getElement(int idx) { // TODO Auto-generated method stub return 0; }

@Override public void clearElement(int idx) { // TODO Auto-generated method stub

}

@Override public void setElement(int idx, int val) { // TODO Auto-generated method stub

}

@Override public int[] getAllIndices() { // TODO Auto-generated method stub return null; }

@Override public int[] getAllValues() { // TODO Auto-generated method stub return null; }

@Override public SparseVec addition(SparseVec otherV) { // TODO Auto-generated method stub return null; }

@Override public SparseVec substraction(SparseVec otherV) { // TODO Auto-generated method stub return null; }

@Override public SparseVec multiplication(SparseVec otherV) { // TODO Auto-generated method stub return null; }

}