package graph;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

// represents a sparse matrix using adjacency lists

public class SparseMatrix<K extends Comparable<? super K>, W> {

	Class<W> classOfW;
	Map<K, Map<K, W>> matrix;
	
	public SparseMatrix(Class<W> classOfW) {
		this.classOfW = classOfW;
		matrix = new HashMap<K, Map<K, W>>();
	}
	
	public void add(K rowKey, K columnKey, W weight) {
		Map<K, W> row;
		if (!matrix.containsKey(rowKey)) {
			row = new HashMap<K, W>();
			matrix.put(rowKey, row);
		} else {
			row = matrix.get(rowKey);
		}

		row.put(columnKey, weight);
	}
	
	public W get(K rowKey, K columnKey) throws InstantiationException, IllegalAccessException {
		try {
			return matrix.get(rowKey).get(columnKey);
		}
		catch (Exception e) {
			return classOfW.newInstance();
		}
	}

	public Set<K> getRowKeys() {
		return matrix.keySet();
	}

	public SortedSet<K> getRowKeysSorted() {
		return new TreeSet<K>(getRowKeys());
	}

	public Set<K> getColumnKeys(K rowKey) {
		try {
			return matrix.get(rowKey).keySet();
		}
		catch (Exception e) {
			return new TreeSet<K>();
		}
	}

	public SortedSet<K> getColumnKeysSorted(K rowKey) {
		return new TreeSet<K>(getColumnKeys(rowKey));
	}

	public void clear() {
		matrix.clear();
	}

	public boolean containsKey(K rowKey, K columnKey) {
		try {
			return matrix.get(rowKey).containsKey(columnKey);
		}
		catch (Exception e) {
			return false;
		}
	}

	public boolean isEmpty() {
		for (K key : matrix.keySet()) {
			if (matrix.get(key).size() > 0) {
				return false;
			}
		}
		return true;
	}

	public void remove(K rowKey, K columnKey) {
	}

	public int size() {
		int size = 0;
		for (K key : matrix.keySet()) {
			size += matrix.get(key).size();
		}
		return size;
	}
}

@@ -700,65 +700,11 @@
 Key)
- throws InstantiationException, IllegalAccessException
  %7B%0A
+
 %09%09tr
@@ -772,32 +772,42 @@
 (Exception e) %7B%0A
+%09%09%09try %7B%0A%09
 %09%09%09return classO
@@ -820,24 +820,74 @@
 Instance();%0A
+%09%09%09%7D catch (Exception e1) %7B%0A%09%09%09%09return null;%0A%09%09%09%7D%0A
 %09%09%7D%0A%09%7D%0A%0A%09pub

return empty weight rather than throw exception if no element found for keys