Question 3:
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.
public class SparseArrayEntry { /** The row index and column index for this entry in the sparse array */ private int row; private int col; /** The value of this entry in the sparse array */ private int value; /** Constructs a SparseArrayEntry object that represents a sparse array element with row index r and column index c, containing value v. / public SparseArrayEntry(int r, int c, int v) { row = r; col = c; value = v; } / Returns the row index of this sparse array element. */ public int getRow() { return row; } /** Returns the column index of this sparse array element. */ public int getCol() { return col; } /** Returns the value of this sparse array element. */ public int getValue() { return value; } }
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.
public class SparseArray
/** The number of rows and columns in the sparse array. */ private int numRows; private int numCols; /** The list of entries representing the non-zero elements of the sparse array. Entries are stored in the
- list in no particular order. Each non-zero element is represented by exactly one entry in the list.
*/
private List
entries; /** Constructs an empty SparseArray. */ public SparseArray() { entries = new ArrayList (); } /** Returns the number of rows in the sparse array. */ public int getNumRows() { return numRows; } /** Returns the number of columns in the sparse array. */ public int getNumCols() { return numCols; } /** Returns the value of the element at row index row and column index col in the sparse array. - Precondition: 0 row < getNumRows()
- 0 col < getNumCols() / public int getValueAt(int row, int col) { / to be implemented in part (a) */ } /** Removes the column col from the sparse array.
- Precondition: 0 col < getNumCols() / public void removeColumn(int col) { / to be implemented in part (b) */ } // There may be instance variables, constructors, and methods that are not shown
The following table shows an example of a two-dimensional sparse array. Empty cells in the table indicate zero values. The sample array can be represented by a SparseArray object, sparse, with the following instance variable values. The items in entries are in no particular order; one possible ordering is shown below.
Part 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.
Part B:
Write the SparseArray method removeColumn. After removing a specified column from a sparse array:
- 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. The sample object sparse from the beginning of the question is repeated for your convenience.
When sparse has the state shown above, the call sparse.removeColumn(1) could result in sparse having the following values in its instance variables (since entries is in no particular order, it would be equally valid to reverse the order of its two items). The shaded areas below show the changes.
Class information:
public class SparseArrayEntry
public SparseArrayEntry(int r, int c, int v) public int getRow() public int getCol() public int getValue()
public class SparseArray
private int numRows
private int numCols
private List
Question Type:
- Arraylists and 2D Arrays
Overall Objectives:
- Create a
getValueAtmethod - Create a
removeColumnmethod - Create a
SparseArrayEntryclass that has variables and constructors and displays the SparseArray - Create a
SparseArrayclass that takes the values we dont’t want and gets rid of them and returns a new complete array
import java.util.ArrayList;
import java.util.List;
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int r, int c, int v) {
row = r; // The constructors for the SparseArrayEntry
col = c;
value = v;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
public class SparseArray {
private int numRows; // Variables
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray() {
numRows = 4;
numCols = 5;
entries = new ArrayList<>();
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
public int getValueAt(int row, int col) { // A (Create a `getValueAt` method)
for (SparseArrayEntry entry : entries) {
if (entry.getRow() == row && entry.getCol() == col) {
return entry.getValue();
}
}
return 0;
}
public void removeColumn(int col) { // B (Create a `removeColumn` method)
List<SparseArrayEntry> updatedEntries = new ArrayList<>();
for (SparseArrayEntry entry : entries) {
if (entry.getCol() == col) {
continue;
} else if (entry.getCol() > col) {
updatedEntries.add(new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue()));
} else {
updatedEntries.add(entry);
}
}
entries = updatedEntries;
numCols--;
}
public static void main(String[] args) {
SparseArray sparse = new SparseArray();
sparse.entries.add(new SparseArrayEntry(1, 4, 4));
sparse.entries.add(new SparseArrayEntry(2, 0, 1));
sparse.entries.add(new SparseArrayEntry(3, 1, -9));
sparse.entries.add(new SparseArrayEntry(1, 1, 5));
System.out.println("Sparse Array (original):"); // original array
for (int i = 0; i < sparse.getNumRows(); i++) {
for (int j = 0; j < sparse.getNumCols(); j++) {
System.out.print(sparse.getValueAt(i, j) + "\t");
}
System.out.println();
}
sparse.removeColumn(1);
System.out.println("\nSparse Array (updated):"); // updated array
for (int i = 0; i < sparse.getNumRows(); i++) {
for (int j = 0; j < sparse.getNumCols(); j++) {
System.out.print(sparse.getValueAt(i, j) + "\t");
}
System.out.println();
}
}
}
SparseArray.main(null);
Initial Sparse Array:
0 0 0 0 0
0 5 0 0 4
1 0 0 0 0
0 -9 0 0 0
Sparse Array after removing column 1:
0 0 0 0
0 0 0 4
1 0 0 0
0 0 0 0
Reflection:
- This question by far was the hardest question out of all the questions that we had and it was one that I really struggled with and I had to get lots of external help
- One of my main challenges was that I didn’t know what the heck a SpareArray and I spent more the college board alloted time trying to understand what the SparseArray was and how does it work, but eventually I figured out that the SparseArray is basically a way to store and represent large arrays with lots of different elements and they are used to store lots of default values and typically get rid of the non default values out of the array
- One thing that was pretty easy tho was setting up the constructors and variables but I struggled a lot afterwards trying to figure out how to work them.
- I also easily understood that the columns and rows were preset and all I had to do was manipulate this sparse array
- Part A was pretty alright to do, you just simply had to write a function that iterated through the different rows and columns and return either 0 or the value that was found
- Part B was where I struggled a lot, I understood that in order to make the remove column method, I would have to make it so you can preset the method so that it gets rid of a certain column and then remove that column but what I struggled with in particluar was how to update the column and make it get rid of the entry and move all the array entries down a column