// 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;
  }

}