A two-dimensional array of integers in which most elements are zero is called a sparse array. Because most elements have a value of zero, memory can be saved by storing only the non-zero values along with their row and column indexes. The following complete SparseArrayEntry class is used to represent non-zero elements in a sparse array. A SparseArrayEntry object cannot be modified after it has been constructed.

The SparseArray class represents a sparse array. It contains a list of SparseArrayEntry objects, each of which represents one of the non-zero elements in the array. The entries representing the non-zero elements are stored in the list in no particular order. Each non-zero element is represented by exactly one entry in the list.

The following table shows an example of a two-dimensional sparse array. Empty cells in the table indicate zero values.

(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. In the example above, the call sparse.getValueAt(3, 1) would return -9, and sparse.getValueAt(3, 3) would return 0.

Complete method getValueAt below.

(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.

When sparse has the state shown above, the call sparse.removeColumn(1) could result insparse having the following values in its instance variables (since entries is in no particular order, itwould be equally valid to reverse the order of its two items). The shaded areas below show the changes.

public class SparseEntry {
    private int rowPosition;
    private int colPosition;
    private int entryValue; 

    public SparseEntry(int row, int col, int value) {
        this.rowPosition = row;
        this.colPosition = col;
        this.entryValue = value; 
    }

    public int getRowPosition() {
        return this.rowPosition;
    } 

    public int getColPosition() {
        return this.colPosition;
    } 

    public int getEntryValue() {
        return this.entryValue;
    }
}

public class SparseMatrix {
    private int totalRows;
    private int totalCols; 
    private List<SparseEntry> entryList; 

    public SparseMatrix() {
        this.entryList = new ArrayList<SparseEntry>(); 
    }

    public void addEntry(SparseEntry entry) {
        this.entryList.add(entry);
    }

    public int getTotalRows() {
        return this.totalRows;
    }

    public int getTotalCols() {
        return this.totalCols;
    }

    public int getValueAtPosition(int row, int col) {
        for (SparseEntry entry : this.entryList) {
            if (entry.getRowPosition() == row && entry.getColPosition() == col) {
                return entry.getEntryValue();
            }
        }
        return 0;
    }

    public void removeCol(int col) {
        int index = 0;
        while (index < this.entryList.size()) {
            SparseEntry currentEntry = this.entryList.get(index);
            if (currentEntry.getColPosition() == col) {
                this.entryList.remove(index);
            } else if (currentEntry.getColPosition() > col) {
                this.entryList.set(index, new SparseEntry(currentEntry.getRowPosition(), currentEntry.getColPosition() - 1, currentEntry.getEntryValue()));
                index++;
            } else {
                index++;
            }
        }
        this.totalCols--;
    }

    public void displayEntries() {
        for (SparseEntry entry : this.entryList) {
            System.out.println("Row: " + entry.getRowPosition() + ", Column: " + entry.getColPosition() + ", Value: " + entry.getEntryValue());
        }
    }     
}

public class TestSparseMatrix {
    public static void main(String[] args) {
        SparseMatrix sparseMatrix = new SparseMatrix();
        sparseMatrix.addEntry(new SparseEntry(1, 1, 5));
        sparseMatrix.addEntry(new SparseEntry(1, 4, 4));
        sparseMatrix.addEntry(new SparseEntry(2, 0, 1));
        sparseMatrix.addEntry(new SparseEntry(3, 1, -9));
        System.out.println("Before Removal: ");
        sparseMatrix.displayEntries();

        sparseMatrix.removeCol(1); // Remove column 1
        System.out.println("After Removal: ");
        sparseMatrix.displayEntries();
    }
}

TestSparseMatrix.main(null);

Before Removal: 
Row: 1, Column: 1, Value: 5
Row: 1, Column: 4, Value: 4
Row: 2, Column: 0, Value: 1
Row: 3, Column: 1, Value: -9
After Removal: 
Row: 1, Column: 3, Value: 4
Row: 2, Column: 0, Value: 1