You could use an index based on the [row,col] of the cell. Since the data is on a diagonal, the typical approach of storing the row index and the associated column indeces with data is not optimal. Here is some code you could use to do it:
public class SparseMatrix<T>
{
public int Width { get; private set; }
public int Height { get; private set; }
public long Size { get; private set; }
private Dictionary<long, T> _cells = new Dictionary<long, T>();
public SparseMatrix(int w, int h)
{
this.Width = w;
this.Height = h;
this.Size = w * h;
}
public bool IsCellEmpty(int row, int col)
{
long index = row * Width + col;
return _cells.ContainsKey(index);
}
public T this[int row, int col]
{
get
{
long index = row * Width + col;
T result;
_cells.TryGetValue(index, out result);
return result;
}
set
{
long index = row * Width + col;
_cells[index] = value;
}
}
}
static void Main()
{
var sm = new SparseMatrix<int>(512, 512);
sm[42, 42] = 42;
int val1 = sm[13, 13];
int val2 = sm[42, 42];
Console.WriteLine("VAL1 = " + val1); // prints out 0
Console.WriteLine("VAL2 = " + val2); // prints out 42
Console.ReadLine();
}
Note that when T is a struct, you might have to call the IsCellEmpty since getting the contents of a cell will not be null and will have the default value for that type. You can also expand the code to give you a quick "SparseRatio" based on the Size property and _cells.Count.
EDIT:
Well, if you are interesting is speed, you can do the trade-off of space vs speed. Instead of having only one dictionary, have three! It triples your space, but it makes enumerating in any way you want real easy. Here is some new code that shows that:
public class SparseMatrix<T>
{
public int Width { get; private set; }
public int Height { get; private set; }
public long MaxSize { get; private set; }
public long Count { get { return _cells.Count; } }
private Dictionary<long, T> _cells = new Dictionary<long, T>();
private Dictionary<int, Dictionary<int, T>> _rows =
new Dictionary<int, Dictionary<int, T>>();
private Dictionary<int, Dictionary<int, T>> _columns =
new Dictionary<int, Dictionary<int, T>>();
public SparseMatrix(int w, int h)
{
this.Width = w;
this.Height = h;
this.MaxSize = w * h;
}
public bool IsCellEmpty(int row, int col)
{
long index = row * Width + col;
return _cells.ContainsKey(index);
}
public T this[int row, int col]
{
get
{
long index = row * Width + col;
T result;
_cells.TryGetValue(index, out result);
return result;
}
set
{
long index = row * Width + col;
_cells[index] = value;
UpdateValue(col, row, _columns, value);
UpdateValue(row, col, _rows, value);
}
}
private void UpdateValue(int index1, int index2,
Dictionary<int, Dictionary<int, T>> parent, T value)
{
Dictionary<int, T> dict;
if (!parent.TryGetValue(index1, out dict))
{
parent[index2] = dict = new Dictionary<int, T>();
}
dict[index2] = value;
}
}
If you want to iterate over all the entries, use _cells. If you want all the rows for a given column use _columns. If you want all the columns in a given row use _rows.
If you want to iterate in sorted order, you can start to add LINQ into the mix and/or use a sorted list with an inner class that encapsulates an entry (which would have to store the row or column and implement IComparable<T> for sorting to work).