2015 FRQ 3

1. (a) Write the SparseArray method getValueAt. The method returns the value of the sparse array element at a given row and column in the sparse array. If the list entries contains an entry with the specified row and column, the value associated with the entry is returned. If there is no entry in entries corresponding to the specified row and column, 0 is returned.

i test this code in part b!

//getRow and getCol are predefined methods in another class. gets the index of the row/col

public int getValueAt(int row, int col){
    //SparseArrayEntry is a list. this for loop iterates through each list(entry) in the array (SparseArray)
    for (SparseArrayEntry e : entries){
        //checks whether the current SparseArrayEntry object (e) has the same row and column indices as the specified row and col parameters.
        if (e.getRow() == row && e.getCol() == col){
            return e.getValue();
        }
    }
    return 0;
}

(b) Write the SparseArray method removeColumn. After removing a specified column from a sparsearray:

• All entries in the list entries with column indexes matching col are removed from the list.
• All entries in the list entries with column indexes greater than col are replaced by entries with column indexes that are decremented by one (moved one column to the left).
• The number of columns in the sparse array is adjusted to reflect the column removed.

public class SparseArrayEntry{
    private int row;
    private int col;
    private int value;

    public SparseArrayEntry(int r, int c, int v){
        this.row = r;
        this.col = c;
        this.value = v;
    }

    public int getRow(){
        return row;
    }

    public int getCol(){
        return col;
    }

    public int getValue(){
        return value;
    }

    public void setCol(int c) {
        this.col = c;
    }

    public void setRow(int r) { 
        this.row = r;
    }
}

public class SparseArray {
    private int numRows;
    private int numCols;
    private List<SparseArrayEntry> entries;

    public SparseArray(ArrayList<SparseArrayEntry> entries, int numRows, int numCols) {
        this.entries = entries;
        this.numRows = numRows;
        this.numCols = numCols;
    }

    // part a
    public int getValueAt(int row, int col){
        for (SparseArrayEntry entry : entries){ // entries stores ArrayList not 2D array!!
            if (entry.getRow() == row && entry.getCol() == col){
                return entry.getValue();
            }
        }
        return 0;
    }

    // part b
    public void removeColumn(int col){
        //iterating from the end of the list to avoid issues related to removing entries in the middle of the list and make the logic simpler.
        for (int i = entries.size() - 1; i >= 0; i--){
            SparseArrayEntry entry = entries.get(i);
            if (entry.getCol() == col){
                entries.remove(i);
            }
            else if(entry.getCol() > col){
                entry.setCol(entry.getCol() - 1);
            }
        }
        numCols--;
    }

    public void printArray() {
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                System.out.print(getValueAt(i, j) + " ");
            }
            System.out.println();
        }
    }

    // test
    public static void main(String[] args) {
        ArrayList<SparseArrayEntry> entries = new ArrayList<>();

        //adds entries where sparse array is not 0
        entries.add(new SparseArrayEntry(1, 1, 4));
        entries.add(new SparseArrayEntry(2, 4, 3));
        entries.add(new SparseArrayEntry(2, 2, 9));
        
        //creates array
        SparseArray arr = new SparseArray(entries, 5, 5);

        // test part a
        System.out.println("(1,1): " + arr.getValueAt(1, 1));

        // test part b
        arr.printArray();
        arr.removeColumn(2);

        System.out.println("Remove Column 2:");
        arr.printArray();
    }
        
}

SparseArray.main(null);

(1,1): 4
0 0 0 0 0 
0 4 0 0 0 
0 0 9 0 3 
0 0 0 0 0 
0 0 0 0 0 
Remove Column 2:
0 0 0 0 
0 4 0 0 
0 0 0 3 
0 0 0 0 
0 0 0 0