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.
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.
(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.
import java.util.ArrayList;
import java.util.List;
class SparseArrayEntry { // class representing an entry in a sparse array
private int row;
private int col;
private int value;
public SparseArrayEntry(int row, int col, int value) { // constructor to initialize row, col, and value
this.row = row;
this.col = col;
this.value = value;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
class SparseArray { // class representing a sparse array
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries; // list to store non-zero entries in the sparse array
public SparseArray() {
entries = new ArrayList<>();
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry entry : entries) { // iterate through the entries
if (entry.getRow() == row && entry.getCol() == col) { // if the entry matches the specified row and column
return entry.getValue(); // return the value of the entry
}
}
return 0; // if no entry found for specified row and column, return 0
}
public void newEntry(SparseArrayEntry entry) { // add an entry to the sparse array
entries.add(entry); // add entry to list of entries
numRows = Math.max(numRows, entry.getRow() + 1); // update the number of rows if necessary
numCols = Math.max(numCols, entry.getCol() + 1); // update the number of columns if necessary
}
}
// Testing my code :D
public class Main {
public static void main(String[] args) {
SparseArray sparse = new SparseArray();
sparse.newEntry(new SparseArrayEntry(1, 4, 4));
sparse.newEntry(new SparseArrayEntry(2, 0, 1));
sparse.newEntry(new SparseArrayEntry(3, 1, -9));
sparse.newEntry(new SparseArrayEntry(1, 1, 5));
System.out.println("(1,4) value: " + sparse.getValueAt(1, 4)); // entry
System.out.println("(2,0) value: " + sparse.getValueAt(2, 0)); // entry
System.out.println("(12,23) value: " + sparse.getValueAt(12, 23)); // not an entry
}
}
Main.main(null);
(1,4) value: 4
(2,0) value: 1
(12,23) value: 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.
The sample object sparse from the beginning of the question is repeated for your convenience.
The shaded entries in entries, below, correspond to the shaded column above.
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.
class SparseArray { // class representing a sparse array
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries; // list to store non-zero entries in the sparse array
public SparseArray() {
entries = new ArrayList<>();
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry entry : entries) { // iterate through the entries
if (entry.getRow() == row && entry.getCol() == col) { // if the entry matches the specified row and column
return entry.getValue(); // return the value of the entry
}
}
return 0; // if no entry found for specified row and column, return 0
}
public void newEntry(SparseArrayEntry entry) { // add an entry to the sparse array
entries.add(entry); // add entry to list of entries
numRows = Math.max(numRows, entry.getRow() + 1); // update the number of rows if necessary
numCols = Math.max(numCols, entry.getCol() + 1); // update the number of columns if necessary
}
public void removeColumn(int col) { // method to remove a column from sparse array
List<SparseArrayEntry> newEntries = new ArrayList<>(); // create a new list to store updated entries
for (SparseArrayEntry entry : entries) { // iterate through entries
if (entry.getCol() != col) { // if the entry's column is not the one to be removed
if (entry.getCol() > col) { // if the entry's column is greater than the one to be removed
newEntries.add(new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue())); // decrement column index by one
} else {
newEntries.add(new SparseArrayEntry(entry.getRow(), entry.getCol(), entry.getValue())); // keep entry as is
}
}
}
entries = newEntries;
numCols--; // decrement the number of columns
}
}
// Testing my code :D
public class Main {
public static void main(String[] args) {
SparseArray sparse = new SparseArray();
sparse.newEntry(new SparseArrayEntry(1, 4, 4));
sparse.newEntry(new SparseArrayEntry(2, 0, 1));
sparse.newEntry(new SparseArrayEntry(3, 1, -9));
sparse.newEntry(new SparseArrayEntry(1, 1, 5));
System.out.println("Before column removal:");
System.out.println("(1, 4) value: " + sparse.getValueAt(1, 4)); // entry
System.out.println("(2, 0) value: " + sparse.getValueAt(2, 0)); // entry
System.out.println("(12, 23) value: " + sparse.getValueAt(12, 23)); // not an entry
sparse.removeColumn(1); // remove column 1
System.out.println("\nAfter column removal:");
System.out.println("(1, 3) value: " + sparse.getValueAt(1, 3)); // entry shifted left
System.out.println("(2, 0) value: " + sparse.getValueAt(2, 0)); // entry unchanged
System.out.println("(12, 23) value: " + sparse.getValueAt(20, 24)); // not an entry
}
}
Main.main(null);
Before column removal:
(1, 4) value: 4
(2, 0) value: 1
(12, 23) value: 0
After column removal:
(1, 3) value: 4
(2, 0) value: 1
(12, 23) value: 0