Question 3: Arrays/ArrayLists

“Students will be asked to write program code to satisfy method specifications using expressions, conditional statements, and iterative statements and create, traverse, and manipulate elements in 1D array or ArrayList objects.”

While this ends up being sort of a 2D arrays-esque question, as the Sparse Array essentially represents a mostly empty 2D array, the way that entries are stored as separate objects within an ArrayList of the larger object makes it more focused on the one-dimensional.

Question Description

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.

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

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

Code

The code cell below contains the SparseArrayEntry class, which hasn’t been modified, but must be included for the following code, the SparseArray class, which has been visibly modified, to fully function.

public class SparseArrayEntry {
    // initial declarations
    private int row;
    private int col;
    private int value;

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

    // getters, as implemented by CB
    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getValue() {
        return value;
    }
}

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

    // no argument constructor
    public SparseArray() {
        entries = new ArrayList<SparseArrayEntry>();
    }

    // added argument constructor for testing, which may exist according to CB specifications
    public SparseArray(int nR, int nC) {
        numRows = nR;
        numCols = nC;
        entries = new ArrayList<SparseArrayEntry>();
    }

    // getters
    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }

    // added methods for testing
    public List<SparseArrayEntry> getEntries() {
        return entries;
    }

    public void addEntry(SparseArrayEntry entry) {
        entries.add(entry);
    }

    // Method for part (a): returns the value of the element at row index `row` and column index `col` in the sparse array.
    // Precondition: 0 <= row < getNumRows() AND 0 <= col < getNumCols()
    public int getValueAt(int row, int col) {
        for (SparseArrayEntry entry : entries) { // iterating through all entries
            if ((entry.getRow() == row) && (entry.getCol() == col)) { // if the row and column match
                return entry.getValue(); // returning the value at the corresponding row and column
            }
        }
        return 0; // returns 0 if no entry is found for the given row and col
    }

    // Method for part (b): removes the column col from the sparse array.
    // Precondition: 0 <= col < getNumCols()
    public void removeColumn(int col) {
        for (int i = entries.size() - 1; i >= 0; i--) {
            SparseArrayEntry entry = entries.get(i);
            if (entry.getCol() >= col) {
                if (entry.getCol() != col) { // if the column must be replaced
                    entries.add(new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue())); // decrementing without access to a col setter
                }
                entries.remove(i); // removing matching entry from list
            }
        }
        numCols--;
    }

    public static void main(String[] args) {
        // testing part (a) method, getValueAt
        SparseArray aTest = new SparseArray();
        aTest.addEntry(new SparseArrayEntry(3, 4, 8));
        aTest.addEntry(new SparseArrayEntry(2, 1, 3));
        System.out.println("Testing call with entry: Entry at r3 and c4 (val = 8) returns: " + aTest.getValueAt(3, 4));
        System.out.println("Testing call without entry: Entry at r1 and c2 (no val, no entry) returns: " + aTest.getValueAt(1, 2));

        // testing part (b) method, removeColumn
        SparseArray bTest = new SparseArray(5, 5);
        bTest.addEntry(new SparseArrayEntry(3, 4, 8));
        bTest.addEntry(new SparseArrayEntry(3, 3, 5));
        bTest.addEntry(new SparseArrayEntry(2, 1, 3));
        System.out.println("\nBefore column deletion:");
        System.out.println("\tNumber of columns: " + bTest.getNumCols());
        for (SparseArrayEntry entry : bTest.getEntries()) {
            System.out.println("\tEntry: Row " + entry.getRow() + ", Column " + entry.getCol() + ", Value " + entry.getValue());
        }
        bTest.removeColumn(3); // removing column
        System.out.println("After column deletion:");
        System.out.println("\tNumber of columns: " + bTest.getNumCols());
        for (SparseArrayEntry entry : bTest.getEntries()) {
            System.out.println("\tEntry: Row " + entry.getRow() + ", Column " + entry.getCol() + ", Value " + entry.getValue());
        }
    }
}

SparseArray.main(null);

Testing call with entry: Entry at r3 and c4 (val = 8) returns: 8
Testing call without entry: Entry at r1 and c2 (no val, no entry) returns: 0

Before column deletion:
	Number of columns: 5
	Entry: Row 3, Column 4, Value 8
	Entry: Row 3, Column 3, Value 5
	Entry: Row 2, Column 1, Value 3
After column deletion:
	Number of columns: 4
	Entry: Row 2, Column 1, Value 3
	Entry: Row 3, Column 3, Value 8

Reflection

For the most part, this was a pretty easy task to pull off.

Part (a) ended up being very similar to the iterative processes in Question 1, as it was just checking each entry for corresponding row and column. Being able to assume that all unentered entries have values of 0 made this more linear approach significantly more efficient than iterating through an actual 2D array.

Once again, I was able to use a for-each loop to iterate through the entries list and check for info. I used the && operator to avoid nesting conditionals, as both the row index and column needed to match for the entry to be properly identified.

Part (b) had significantly more to talk about. The main thing I wanted to point out was that I iterated backward through the ArrayList. This prevented ConcurrentModificationExceptions that would make deleting during the iterative process painful and inconsistent between different column deletions.

for (int i = entries.size() - 1; i >= 0; i--)

I was able to decrease the number of .get() calls to the current entry in the iteration by defining it as a variable at the beginning of each iteration. Unfortunately, however, because we weren’t provided with a usable setter method for the SparseArrayEntry class that would allow for the direct decrementation of the col variable, the roundabout recreation method below was used instead.

SparseArrayEntry entry = entries.get(i);
if (entry.getCol() >= col) {
    if (entry.getCol() != col) { // if the column must be replaced
        entries.add(new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue())); // decrementing
    }
    entries.remove(i); // removing matching entry from list
}

If I could simply use a setter, it would look like this instead:

if (entry.getCol() == col) {
    entries.remove(i); // removing matching entry from list
} else if (entry.getCol() > col) {
    entry.setCol(entry.getCol() - 1); // direct decrementation
}

I spent more time than I probably should’ve on the main tester method.

Overall Notes and Reminders

  • When implementing a for-each loop in Java, remember to use the proper data type for the entry variable so that it can be interacted with properly.
  • When deleting values during an iterative process, iterating backward through an array might be a good idea.
  • In an iterative process where a soon-to-be-deleted element needs to have its information interacted with/compared to, make sure to extract that information prior to deletion or wait to delete until all relevant information has been parsed or considered.
  • Consider differences in how to interact with arrays vs. ArrayLists.
    • .get() vs using indexes with []
    • .add()
    • .size() instead of .length (getter rather than direct attribute access)

Revision

After crossover grading with Alex, I wanted to go back and change an aspect of my answer here to preserve the order of the ArrayList of entries. While this wasn’t specified to matter, I only chose a solution that didn’t preserve order because I didn’t see the possibility of using the ArrayList set method. I think revising would be good practice.

public void removeColumn(int col) {
    for (int i = entries.size() - 1; i >= 0; i--) {
        SparseArrayEntry entry = entries.get(i);
        if (entry.getCol() == col) {
            entries.remove(i); // removing matching entry from list
        } else if (entry.getCol() > col) {
            entries.set(i, new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue())); // decrementing without access to a col setter
        }
    }
    numCols--;
}

See evidence of it working below:

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

    // no argument constructor
    public SparseArray() {
        entries = new ArrayList<SparseArrayEntry>();
    }

    // added argument constructor for testing, which may exist according to CB specifications
    public SparseArray(int nR, int nC) {
        numRows = nR;
        numCols = nC;
        entries = new ArrayList<SparseArrayEntry>();
    }

    // getters
    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }

    // added methods for testing
    public List<SparseArrayEntry> getEntries() {
        return entries;
    }

    public void addEntry(SparseArrayEntry entry) {
        entries.add(entry);
    }

    // Method for part (a): returns the value of the element at row index `row` and column index `col` in the sparse array.
    // Precondition: 0 <= row < getNumRows() AND 0 <= col < getNumCols()
    public int getValueAt(int row, int col) {
        for (SparseArrayEntry entry : entries) { // iterating through all entries
            if ((entry.getRow() == row) && (entry.getCol() == col)) { // if the row and column match
                return entry.getValue(); // returning the value at the corresponding row and column
            }
        }
        return 0; // returns 0 if no entry is found for the given row and col
    }

    // Method for part (b): removes the column col from the sparse array.
    // Precondition: 0 <= col < getNumCols()
    public void removeColumn(int col) {
        for (int i = entries.size() - 1; i >= 0; i--) {
            SparseArrayEntry entry = entries.get(i);
            if (entry.getCol() == col) {
                entries.remove(i); // removing matching entry from list
            } else if (entry.getCol() > col) {
                entries.set(i, new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue())); // decrementing without access to a col setter
            }
        }
        numCols--;
    }

    public static void main(String[] args) {
        // testing part (a) method, getValueAt
        SparseArray aTest = new SparseArray();
        aTest.addEntry(new SparseArrayEntry(3, 4, 8));
        aTest.addEntry(new SparseArrayEntry(2, 1, 3));
        System.out.println("Testing call with entry: Entry at r3 and c4 (val = 8) returns: " + aTest.getValueAt(3, 4));
        System.out.println("Testing call without entry: Entry at r1 and c2 (no val, no entry) returns: " + aTest.getValueAt(1, 2));

        // testing part (b) method, removeColumn
        SparseArray bTest = new SparseArray(5, 5);
        bTest.addEntry(new SparseArrayEntry(3, 4, 8));
        bTest.addEntry(new SparseArrayEntry(2, 2, 3));
        bTest.addEntry(new SparseArrayEntry(3, 3, 5));
        bTest.addEntry(new SparseArrayEntry(2, 1, 3));
        System.out.println("\nBefore column deletion:");
        System.out.println("\tNumber of columns: " + bTest.getNumCols());
        for (SparseArrayEntry entry : bTest.getEntries()) {
            System.out.println("\tEntry: Row " + entry.getRow() + ", Column " + entry.getCol() + ", Value " + entry.getValue());
        }
        bTest.removeColumn(3); // removing column
        System.out.println("After column deletion:");
        System.out.println("\tNumber of columns: " + bTest.getNumCols());
        for (SparseArrayEntry entry : bTest.getEntries()) {
            System.out.println("\tEntry: Row " + entry.getRow() + ", Column " + entry.getCol() + ", Value " + entry.getValue());
        }
    }
}

SparseArray.main(null);

Testing call with entry: Entry at r3 and c4 (val = 8) returns: 8
Testing call without entry: Entry at r1 and c2 (no val, no entry) returns: 0

Before column deletion:
	Number of columns: 5
	Entry: Row 3, Column 4, Value 8
	Entry: Row 2, Column 2, Value 3
	Entry: Row 3, Column 3, Value 5
	Entry: Row 2, Column 1, Value 3
After column deletion:
	Number of columns: 4
	Entry: Row 3, Column 3, Value 8
	Entry: Row 2, Column 2, Value 3
	Entry: Row 2, Column 1, Value 3