(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.
Solutions
the code defines classes to represent entries and sparse arrays. Entries are individual elements in the sparse array that have non-zero values. The sparse array efficiently stores these entries. The Main class tests the functionality of the sparse array by adding entries and retrieving values at specific positions.
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;
// constructor to initialize row, col, and value
public SparseArrayEntry(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
// getter method for row
public int getRow() {
return row;
}
// getter method for column
public int getCol() {
return col;
}
// getter method for value
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
// Constructor initializing entries as an empty ArrayList
public SparseArray() {
entries = new ArrayList<>();
}
// store the number of rows in the sparse array
public int getNumRows() {
return numRows;
}
// store the number of columns in the sparse array
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(); // if found will return the value of the entry
}
}
return 0; // if no entry found for specified row and column, return 0
}
// method for adding an entry to the sparse array
public void newEntry(SparseArrayEntry entry) {
// add entry to list of entries (within the ArrayList)
entries.add(entry);
// update the number of rows if necessary
numRows = Math.max(numRows, entry.getRow() + 1);
// update the number of columns if necessary
numCols = Math.max(numCols, entry.getCol() + 1);
}
}
public class Main {
public static void main(String[] args) {
// creates an instance of SparseArray named sparse.
SparseArray sparse = new SparseArray();
// adds four entries to the sparse array using the newEntry method.
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));
// prints the values of specific entries using the getValueAt method.
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.
Solution
the code defines classes to represent sparse arrays and their entries. Entries are individual elements in the sparse array that have non-zero values. The sparse array efficiently stores these entries. The Main class tests the functionality of the sparse array by adding entries, retrieving values, and removing columns.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
class SparseArray {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
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) {
if (entry.getRow() == row && entry.getCol() == col) {
return entry.getValue();
}
}
return 0;
}
public void addEntry(SparseArrayEntry entry) {
entries.add(entry);
numRows = Math.max(numRows, entry.getRow() + 1);
numCols = Math.max(numCols, entry.getCol() + 1);
}
public void removeColumn(int col) {
Iterator<SparseArrayEntry> iterator = entries.iterator();
while (iterator.hasNext()) {
SparseArrayEntry entry = iterator.next();
if (entry.getCol() == col) {
iterator.remove();
for (SparseArrayEntry e : entries) {
if (e.getCol() > col) {
e.setCol(e.getCol() - 1);
}
}
numCols--;
}
}
}
}
public class Main {
public static void main(String[] args) {
SparseArray sparse = new SparseArray();
sparse.addEntry(new SparseArrayEntry(1, 4, 4));
sparse.addEntry(new SparseArrayEntry(2, 0, 1));
sparse.addEntry(new SparseArrayEntry(3, 1, -9));
sparse.addEntry(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(12, 23)); // not an entry
}
}
Main.main(null);
Key Learnings and Reflection
Firstly, through this exercise, I learned about sparse arrays, which are used to efficiently store and manipulate large arrays with mostly empty or zero values. In a sparse array, only non-zero or non-default values are stored, along with their corresponding indices. Secondly, This exercise introduced me to the concept of using a list of SparseArrayEntry objects to represent a sparse array. Each SparseArrayEntry contains the row, column, and value of a non-zero element in the array. Lastly, I was able to learn how to iterate through SparseArrays, I used iterators to traverse and modify the list of SparseArrayEntry objects was a key aspect of this exercise. I employed an iterator to remove entries corresponding to a specific column and update the column indices of remaining entries accordingly.