Instructions:
- A two-dimensional array of integers in which most elements are zero is called a sparse array.
- Memory can be saved by storing only the non-zero values along with their row and column indexes.
- The
SparseArrayEntryclass is used to represent non-zero elements in a sparse array. - A
SparseArrayEntryobject cannot be modified after it has been constructed.
(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.
(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.
Reflection
THis tested my knowlege of array lists and implements tation of how to append and traverse through an array list I struggled most at the part wher I had to test the data and see if my methods were actually working. I sturggled mostly on part B to get the actual value and remove it from the sparsed array.
Part A
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
SparseArray sparseArray = new SparseArray(4, 4);
// Add some test data
sparseArray.setValueAt(1, 1, 5); // Row 1, Column 1: Value 5
sparseArray.setValueAt(2, 0, 1); // Row 2, Column 0: Value 1
sparseArray.setValueAt(3, 1, -9); // Row 3, Column 1: Value -9
// Test the getValueAt method
System.out.println("Value at (1, 1): " + sparseArray.getValueAt(1, 1));
System.out.println("Value at (3, 1): " + sparseArray.getValueAt(3, 1));
System.out.println("Value at (3, 3): " + sparseArray.getValueAt(3, 3));
}
public static class SparseArray {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
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 setValueAt(int row, int col, int value) {
// Check if there's already an entry at the specified row and column
for (SparseArrayEntry entry : entries) {
if (entry.getRow() == row && entry.getCol() == col) {
// If so, update the value and return
entry.setValue(value);
return;
}
}
entries.add(new SparseArrayEntry(row, col, value));
}
public void removeColumn(int col) {
}
}
public static 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;
}
public void setValue(int value) {
this.value = value;
}
}
}
Main.main(null)
Value at (1, 1): 5
Value at (3, 1): -9
Value at (3, 3): 0
Part B
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Main {
public static void main(String[] args) {
// Create a SparseArray object with 4 rows and 4 columns
SparseArray sparseArray = new SparseArray(4, 4);
// Add some test data
sparseArray.setValueAt(1, 1, 5); // Row 1, Column 1: Value 5
sparseArray.setValueAt(2, 0, 1); // Row 2, Column 0: Value 1
sparseArray.setValueAt(3, 1, -9); // Row 3, Column 1: Value -9
sparseArray.setValueAt(1, 4, 4); // Row 1, Column 4: Value 4
System.out.println("Original Sparse Array:");
displaySparseArray(sparseArray);
// remove function
sparseArray.removeColumn(1);
System.out.println("\nSparse Array after removing column 1:");
displaySparseArray(sparseArray);
}
private static void displaySparseArray(SparseArray sparseArray) {
for (int row = 0; row < sparseArray.getNumRows(); row++) {
for (int col = 0; col < sparseArray.getNumCols(); col++) {
System.out.print(sparseArray.getValueAt(row, col) + "\t");
}
System.out.println();
}
}
public static class SparseArray {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
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 setValueAt(int row, int col, int value) {
Iterator<SparseArrayEntry> iterator = entries.iterator();
while (iterator.hasNext()) {
SparseArrayEntry entry = iterator.next();
if (entry.getRow() == row && entry.getCol() == col) {
// If so, update the value and return
entry.setValue(value);
return;
}
}
entries.add(new SparseArrayEntry(row, col, value));
}
public void removeColumn(int col) {
if (col < 0 || col >= numCols) {
throw new IllegalArgumentException("Invalid column index");
}
// Remove entries with matching column index and update remaining entries
Iterator<SparseArrayEntry> iterator = entries.iterator();
while (iterator.hasNext()) {
SparseArrayEntry entry = iterator.next();
if (entry.getCol() == col) {
iterator.remove();
} else if (entry.getCol() > col) {
entry.setCol(entry.getCol() - 1);
}
}
numCols--;
}
public static 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;
}
public void setValue(int value) {
this.value = value;
}
public void setCol(int col) {
this.col = col;
}
}
}
}
Main.main(null)
Original Sparse Array:
0 0 0 0
0 5 0 0
1 0 0 0
0 -9 0 0
Sparse Array after removing column 1:
0 0 0
0 0 0
1 0 0
0 0 0