FRQ 3
(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.
A 5-line code segment reads as follows. Line 1: forward slash, asterisk, asterisk, Returns the value of the element at row index row and column index col in the sparse array. Line 2: asterisk, Precondition, colon, 0 less than or equal to row less than get Num Rows, open parenthesis, close parenthesis. Line 3: asterisk, 0 less than or equal to col less than get Num Cols, open parenthesis, close parenthesis. Line 4: asterisk, forward slash. Line 5: public int get Value At, open parenthesis, int row comma int col, close parenthesis.
(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.
The sample object sparse from the beginning of the question is repeated for your convenience.
A table is shown with five columns and six rows. From the upper left the columns are labeled 0 through 4 and the rows 0 through 5. Using these labels, the number 5 is in row 1 column 1, the number 1 is in row 2 column 0, the number negative 9 is in row 3 column 1, and the number 4 is in row 1 column 4. The rest of the entries are blank. Column 1 is shaded grey.
The shaded entries in entries, below, correspond to the shaded column above.
An array labeled entries is shown that is a horizontal row with four boxes. In the first box it reads row 1, column 4, value 4. In the second box it reads row 2, column 0, value 1. In the third box it reads row 3, column 1, value negative 9. In the fourth box it reads row 1, column 1, value 5. The last two boxes are shaded grey.
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.
An array labeled entries is shown that is a horizontal row with two boxes. In the first box it reads row 1, column 3, value 4. In the second box it reads row 2, column 0, value 1. The first box is shaded grey. A box with text at the top that reads, Class information repeated from the beginning of the question. A 17-line code segment reads as follows. Line 1: public class Sparse Array Entry (underlined). Line 2: blank. Line 3: public Sparse Array Entry, open parenthesis, int r comma int c comma int v, close parenthesis. Line 4: public int get Row, open parenthesis, close parenthesis. Line 5: public int get Col, open parenthesis, close parenthesis. Line 6: public int get Value, open parenthesis, close parenthesis. Line 7: blank. Line 8: public class Sparse Array (underlined). Line 9: blank. Line 10: private int num Rows. Line 11: private int num Cols. Line 12: private List, open angular bracket, Sparse Array Entry, close angular bracket, entries. Line 13: public int get Num Rows, open parenthesis, close parenthesis. Line 14: public int get Num Cols, open parenthesis, close parenthesis. Line 15: public int get Value At, open parenthesis, int row comma int col, close parenthesis. Line 16: public void remove Column, open parenthesis, int col, close parenthesis.
import java.util.ArrayList;
public class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int r, int c, int v) {
row = r;
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;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray() {
entries = new ArrayList<SparseArrayEntry>();
}
public void add(SparseArrayEntry entry) {
entries.add(entry);
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
public int getValueAt(int row, int col) //Part A
{
for (SparseArrayEntry i: entries)
{
if (i.getRow() == row && i.getCol() == col)
{
return i.getValue();
}
}
return 0;
}
public void removeColumn(int col) { //Part B
int i = 0;
while (i < entries.size())
{
SparseArrayEntry entry = entries.get(i);
if (entry.getCol() == col)
{
entries.remove(i);
}
else if (entry.getCol() > col)
{
entries.set(i, new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue()));
i++;
}
else
{
i++;
}
}
numCols--;
}
public void printEntries() {
for (SparseArrayEntry entry : entries) {
System.out.println("Row: " + entry.getRow() + ", Column: " + entry.getCol() + ", Value: " + entry.getValue());
}
}
}
public class Main {
public static void main(String[] args)
{
SparseArray sparseArray = new SparseArray();
sparseArray.add(new SparseArrayEntry(1, 2, 3));
sparseArray.add(new SparseArrayEntry(1, 1, 2));
sparseArray.add(new SparseArrayEntry(1, 8, 6));
sparseArray.add(new SparseArrayEntry(2, 1, 4));
sparseArray.add(new SparseArrayEntry(5, 1, 5));
sparseArray.add(new SparseArrayEntry(2, 2, 5));
sparseArray.add(new SparseArrayEntry(2, 3, 6));
sparseArray.add(new SparseArrayEntry(3, 1, -9));
System.out.println("Before Column Remove: ");
sparseArray.printEntries();
sparseArray.removeColumn(1); // Remove column 1
System.out.println("After Column Remove: ");
sparseArray.printEntries();
}
}
Main.main(null);
Before Column Remove:
Row: 1, Column: 2, Value: 3
Row: 1, Column: 1, Value: 2
Row: 1, Column: 8, Value: 6
Row: 2, Column: 1, Value: 4
Row: 5, Column: 1, Value: 5
Row: 2, Column: 2, Value: 5
Row: 2, Column: 3, Value: 6
Row: 3, Column: 1, Value: -9
After Column Remove:
Row: 1, Column: 1, Value: 3
Row: 1, Column: 7, Value: 6
Row: 2, Column: 1, Value: 5
Row: 2, Column: 2, Value: 6