// Arup Guha
// 4/24/2016
// Solution to 2015 AP CS A Free Response Question 3: Sparse Array Storage

import java.util.*;

public class SparseArray {

	private int numRows;
	private int numCols;
	private List<SparseArrayEntry> entries;

	/*** Note: The AP People messed up here. In their example, their array was a 6 x 5, but had all 0s in rows 4 and 5. If you create an empty
	 *         one of these, like they had and then change numRows and numCols dynamically after each entry add and deletion, then for their
	 *         example, the array would be size 4 x 5 then 4 x 4. But, they wanted it to be 6 x 5. This indicates to me that these values HAVE
	 *         to be set independently of the actual non-zero entries. So, I just put them in the constructor...
	 ***/
	public SparseArray(int rows, int cols) {
		entries = new ArrayList<SparseArrayEntry>();
		numRows = rows;
		numCols = cols;
	}

	public int getNumRows() {
		return numRows;
	}

	public int getNumCols() {
		return numCols;
	}

	public void addEntry(SparseArrayEntry e) {
		entries.add(e);
	}

	public int getValueAt(int row, int col) {

		// No better solution (with this storage) - we have to look through our whole list to match row and column.
		for (SparseArrayEntry item: entries)
			if (item.getRow() == row && item.getCol() == col)
				return item.getValue();

		// If we get here, it's a 0 entry!
		return 0;
	}

	public void removeColumn(int col) {

		int i = 0;

		// This is annoying, go through and find all column values that match. Remove these entries, but
		// when you remove, don't advance in the list.
		while (i < entries.size()) {
			if (entries.get(i).getCol() == col)
				entries.remove(i);
			else
				i++;
		}

		i = 0;

		// Now, we must adjust all old columns to the right of col by deleting the appropriate entries and creating new
		// entries one column over. I temporarily store these in newList.
		ArrayList<SparseArrayEntry> newList = new ArrayList<SparseArrayEntry>();
		while (i < entries.size()) {
			SparseArrayEntry item = entries.get(i);

			// This entry has to be moved.
			if (item.getCol() > col) {

				// First add the new item.
				newList.add(new SparseArrayEntry(item.getRow(), item.getCol()-1, item.getValue()));

				// Now get rid of the old one.
				entries.remove(i);
			}

			// Nothing to do, so we just advance.
			else
				i++;
		}

		// Now, add these into the original list.
		for (SparseArrayEntry item: newList)
			entries.add(item);

		// Very easy to forget this.
		numCols--;
	}

	// Just for testing.
	public String toString() {
		String res = "Array is "+numRows+" x "+numCols+"\n";
		for (int i=0; i<entries.size(); i++)
			res = res + entries.get(i) + "\n";
		return res;
	}

	// Just the test on the test.
	public static void main(String[] args) {
		SparseArray arr = new SparseArray(6, 5);
		arr.addEntry(new SparseArrayEntry(2, 0, 1));
		arr.addEntry(new SparseArrayEntry(1, 1, 5));
		arr.addEntry(new SparseArrayEntry(3, 1, -9));
		arr.addEntry(new SparseArrayEntry(1, 4, 4));
		System.out.println("The original array:");
		System.out.println(arr);
		arr.removeColumn(1);
		System.out.println("New array is:");
		System.out.println(arr);
	}
}

// Made default and not public since I wanted to code the whole solution in one file. This is their included class.
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 String toString() {
		return "A["+row+"]["+col+"] = "+value;
	}
}