Quesiton 3
Type: List/List Iteration
Blog I learned from this question to go over how lists were used in classes to manipulate data. In order to demonstrate the significance of list iteration and modification in data structure management, I was tested on traversing and modifying a list of SparseArrayEntry objects to retrieve values and remove columns. A sparse array is an effective way to store and manipulate data with a significant number of zero or null values. This relates to list iteration because, although these list operations were straightforward, the complexity of the question increased because they had to be carried out over multiple classes.
Part A
Value Retrieval - Iterate through a list of SparseArrayEntry objects to find the value at a specific row and column.
import java.util.HashMap;
import java.util.Map;
// Class to represent an entry in the sparse array
class SparseArrayEntry {
private final int row;
private final int col;
private final int value;
public SparseArrayEntry(int row, int col, int 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 to represent the sparse array
class SparseArray {
private final Map<Integer, SparseArrayEntry> entries;
private final int numRows;
private final int numCols;
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
entries = new HashMap<>();
}
public void addEntry(int row, int col, int value) {
if (isValidIndex(row, col)) {
entries.put(generateKey(row, col), new SparseArrayEntry(row, col, value));
} else {
throw new IllegalArgumentException("Invalid index");
}
}
public int getValueAt(int row, int col) {
SparseArrayEntry entry = entries.get(generateKey(row, col));
return entry != null ? entry.getValue() : 0;
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
private boolean isValidIndex(int row, int col) {
return row >= 0 && row < numRows && col >= 0 && col < numCols;
}
private int generateKey(int row, int col) {
return row * numCols + col;
}
}
// Example usage
public class MainTesting {
public static void main(String[] args) {
SparseArray sparseArray = new SparseArray(5, 5); // 5x5 sparse array
sparseArray.addEntry(1, 2, 3); // Add an entry at row 1, column 2 with value 3
sparseArray.addEntry(3, 4, 5); // Add another entry at row 3, column 4 with value 5
System.out.println("Should print 3:");
System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
System.out.println("Should print 5:");
System.out.println(sparseArray.getValueAt(3, 4)); // Should print 5
System.out.println("Should print 0:");
System.out.println(sparseArray.getValueAt(0, 0)); // Should print 0 (default value)
}
}
MainTesting.main(null)
Should print 3:
3
Should print 5:
5
Should print 0:
0
Part B
Column Removal - Modify the list of SparseArrayEntry objects to remove entries in a specific column and adjust the column indices of remaining entries.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
// Class representing an entry in the sparse array
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int row, int col, int 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 representing a sparse array
class SparseArray {
private List<SparseArrayEntry> entries; // List to store sparse array entries
private int numRows; // Number of rows in the sparse array
private int numCols; // Number of columns in the sparse array
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
entries = new ArrayList<>();
}
// Method to add an entry to the sparse array
public void addEntry(int row, int col, int value) {
entries.add(new SparseArrayEntry(row, col, value));
}
// Method to get the value at a specific position in the sparse array
public int getValueAt(int row, int col) {
for (SparseArrayEntry entry : entries) {
if (entry.getRow() == row && entry.getCol() == col) {
return entry.getValue();
}
}
return 0; // Return 0 if no value is found at the specified position
}
// Method to remove a column from the sparse array
public void removeColumn(int col) {
numCols--; // Decrease the number of columns
// Using iterator to remove entries while iterating over the list
Iterator<SparseArrayEntry> iterator = entries.iterator();
while (iterator.hasNext()) {
SparseArrayEntry entry = iterator.next();
if (entry.getCol() == col) {
iterator.remove(); // Remove the entry if it belongs to the specified column
} else if (entry.getCol() > col) {
// If the column of the entry is greater than the removed column,
// decrease the column index of the entry by 1
entry = new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue());
iterator.remove(); // Remove the old entry
entries.add(entry); // Add the modified entry
}
}
}
// Method to get the number of rows in the sparse array
public int getNumRows() {
return numRows;
}
// Method to get the number of columns in the sparse array
public int getNumCols() {
return numCols;
}
}
// Class containing the main method for testing the SparseArray class
public class MainTesting {
public static void main(String[] args) {
// Creating a sparse array and adding entries
SparseArray sparseArray = new SparseArray(5, 5);
sparseArray.addEntry(1, 2, 3);
sparseArray.addEntry(3, 4, 5);
sparseArray.addEntry(2, 3, 7);
// Printing original array
System.out.println("Original Array");
System.out.println("Should print 3:");
System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
System.out.println("Should print 5:");
System.out.println(sparseArray.getValueAt(3, 4)); // Should print 5
System.out.println("Should print 7:");
System.out.println(sparseArray.getValueAt(2, 3)); // Should print 7
System.out.println();
}
}
MainTesting.main(null)
Original Array
Should print 3:
3
Should print 5:
5
Should print 7:
7