// Triangle Matrix Helper
// Ben Axelrod
// 01/08/06


#include <iostream>
#include <cstdlib>
using namespace std;

//
// USAGE
//
// Trag_eq() and Trag_noeq() give you the indicies of a 1D array as if it
// where a triagular 2D matrix.  A good usage of this is when you have
// a large distance matrix or another sort of symetric similarity matrix.
// You can store it with half the space by using these techniques.  There
// are two cases one might be interested in, when the row is allowed to be
// equal to the column, and when they are not.  
//
// NOTE: max 1D array size for row = col case: ((N*N)-N)/2+N
// NOTE: max 1D array size for row != col case: ((N*N)-N)/2


//
// ABOUT DERIVATION
//
// The first key number on each row was noticed to be row*N-TriangleNumber
// Where: row is the row number (starting with 0)
//        N is the size of the matrix (elements per side)
//        and TriangleNumber is an integer sequence defined by: N(N+1)/2
// See: http://www.research.att.com/~njas/sequences/A000217 for more info.
//
// For example when N=4, and the row can equal the column, the key numbers 
// are 0, 4, 7, and 9.  Creating this diagram:
//
//   0 1 2 3
// 0 0 1 2 3
// 1   4 5 6
// 2     7 8
// 3       9
//
// From this equation: row*N-N(N+1)/2, it is easy to get the rest of the 
// indecies.
//


int Trag_noeq(int row, int col, int N)
{      
	//assert(row != col); //You can add this in if you like
	if (row<col)
		return row*(N-1) - (row-1)*((row-1) + 1)/2 + col - row - 1;
	else if (col<row)
		return col*(N-1) - (col-1)*((col-1) + 1)/2 + row - col - 1;
	else
		return -1;
}


int Trag_eq(int row, int col, int N)
{      
	if (row <= col)
		return row*N - (row-1)*((row-1) + 1)/2 + col - row;
	else if (col<row)
		return col*N - (col-1)*((col-1) + 1)/2 + row - col;
}

int main( int argc, char *argv[])
{
	int i, j, N;
	int maxcell_eq, maxcell_noeq;

	if (argc == 1)
		N = 5;
	else if (argc == 2)
		N = atoi(argv[1]);
	else
	{
		cout << "\n ERROR: Usage: trag N\n";
		cout << "where N = side of matrix\n\n";
		exit(1);
	}


	cout << "\nTrag_eq indicies:\n";
	for(j=0; j<N; j++)
	{
		for(i=0; i<N; i++)
		{
			cout.width(4);
			cout << Trag_eq(j,i,N);
		}
		cout << endl;
	}

	cout << "\nTrag_noeq indicies:\n";
	for(j=0; j<N; j++)
	{
		for(i=0; i<N; i++)
		{
			cout.width(4);
			cout << Trag_noeq(j,i,N);
		}
		cout << endl;
	}


	//
	// Trag_eq example usage
	//
	cout << "\nTrag_eq example:\n";
	cout << "cell (0,0) = 11\n";
	cout << "cell (0,1) = 12\n";
	cout << "cell (1,2) = 13\n";

	// declare halfsize 1D array
	maxcell_eq = ((N*N)-N)/2+N;
	int array1[maxcell_eq];

	//clear array
	for(i=0; i<maxcell_eq; i++)
		array1[i] = 0;

	//set some cells
	array1[Trag_eq(0,0,N)] = 11;
	array1[Trag_eq(0,1,N)] = 12;
	array1[Trag_eq(1,2,N)] = 13;

	//read a cell
	int firstcell1 = array1[Trag_eq(0,0,N)];

	cout << "\nThe full matrix:\n";

	//print entire matrix
	for(j=0; j<N; j++)
	{
		for(i=0; i<N; i++)
		{
			cout.width(4);
			cout << array1[Trag_eq(j,i,N)];
		}
		cout << endl;
	}


	//
	// Trag_noeq example usage
	//
	cout << "\nTrag_noeq example:\n";
	cout << "cell (0,1) = 11\n";
	cout << "cell (0,2) = 12\n";
	cout << "cell (1,2) = 13\n";

	// declare halfsize 1D array
	maxcell_noeq = ((N*N)-N)/2;
	int array2[maxcell_noeq];

	//clear array
	for(i=0; i<maxcell_noeq; i++)
		array2[i] = 0;

	//set some cells
	array2[Trag_noeq(0,1,N)] = 11;
	array2[Trag_noeq(0,2,N)] = 12;
	array2[Trag_noeq(1,2,N)] = 13;

	//read a cell
	int firstcell2 = array2[Trag_noeq(0,0,N)];

	cout << "\nTrag_noeq example:\n";

	//print entire matrix
	for(j=0; j<N; j++)
	{
		for(i=0; i<N; i++)
		{
			cout.width(4);
			if (Trag_noeq(j,i,N) < 0)
				cout << " ";
			else
				cout << array2[Trag_noeq(j,i,N)];
		}
		cout << endl;
	}

}