One way to map an upper triangular matrix into a one dimensional array
is by columns beginning with column one of the upper triangle.
The order of elements is (1,1), (1,2), (2,2), (1,3), (2,3), (3,3), ....
Preceding the column j elements, we have one element from column 1,
two from column 2, three form column 3, ..., and
j-1 from column j. So, in this mapping, element (i,j) is the
j(j-1)/2+ith element. Hence, it is stored in array position
j(j-1)/2+i-1.
With these observations in mind, we arrive at the following
code:
public class UpperTriangularMatrix
{
// data members
int rows; // matrix dimension
Object zero; // zero element
Object [] element; // element array
// constructor
public UpperTriangularMatrix(int theRows, Object theZero)
{
// validate theRows
if (theRows < 1)
throw new IllegalArgumentException
("number of rows must be > 0");
// create and initialize the matrix
rows = theRows;
zero = theZero;
element = new Object [rows * (rows + 1) / 2];
for (int i = 0; i < rows * (rows + 1) / 2; i++)
element[i] = zero;
}
/** throws IndexOutOfBoundsException when i < 1
* or j < 1 or i > rows or j > rows */
void checkIndex(int i, int j)
{
if (i < 1 || j < 1 || i > rows || j > rows)
throw new IndexOutOfBoundsException
("i = " + i + " j = " + j +
" rows = " + rows + " cols = " + rows);
}
// methods
/** return the element this(i,j)
* throws IndexOutOfBoundsException when i or j invalid */
public Object get(int i, int j)
{
checkIndex(i, j);
// (i,j) in upper triangle iff i <= j
if (i <= j) return element[j * (j - 1) / 2 + i - 1];
else return zero;
}
/** set this(i,j) = newValue
* throws IndexOutOfBoundsException when i or j invalid */
public void set(int i, int j, Object newValue)
{
checkIndex(i, j);
// store newValue
// (i,j) in upper triangle iff i <= j
if (i <= j) element[j * (j - 1) / 2 + i - 1] = newValue;
else if (!((Zero) newValue).equalsZero())
throw new IllegalArgumentException
("elements not in upper triangle must be zero");
}
}