/**
 * This class implements a several methdos related two dimensional arrays.  
 * Please see the Lab 14 write-up for more detail.
 */

public class MatrixFunSol { 
  // Boolean constants to determine which methods to test
  private static final boolean TEST_largestColumnFirst = true;     // Set to false to avoid testing largetsColumnFirst()
  private static final boolean TEST_transpose          = true;     // Set to false to avoid testing transpose()
  private static final boolean TEST_triToSym           = true;     // Set to false to avoid testing triToSym()
  private static final boolean TEST_raggedToSquare     = true;     // Set to true to test raggedToSquare()
    
  /* Swap the largest-sum column of a rectangular matrix with the first column. */
  public static void largestColumnFirst(int[][] M) {
    int maxSumCol = -1;
    int maxSum = Integer.MIN_VALUE;    // Make the sum as small as possible initially
    int nrows  = M.length;             
    int ncols  = M[0].length;
    
    // Iterate over all columns, trying to find the one with the highest sum
    for (int j=0; j<ncols; j++) {
      int colSum = 0;
      for (int i=0; i<nrows; i++)   // Iterate over rows, add up elements in the column
        colSum += M[i][j];
      if (colSum > maxSum) {        // New maximum sum found in column j
        maxSum = colSum;
        maxSumCol = j;
      }
    }
    
    /* Now that we know the maximum-sum column, iterate over the column, swapping
     * corresponding elements with the first column.  If the first column is maximum-sum,
     * don't do anything. */
    if (maxSumCol > 0) {
      for (int i=0; i<nrows; i++) {
        int tmp = M[i][maxSumCol];
        M[i][maxSumCol] = M[i][0];
        M[i][0] = tmp;
      }
    }
  }
  
  /* Transpose elements of a square matrix, reflecting it over the main diagonal. */
  public static void transpose(int[][] M) {
    int n = M.length;
    for (int i=0; i<n; i++) {     // Iterate over all the rows
      for (int j=0; j<i; j++) {   // Iterate up to the diagonal over columns
        int tmp = M[i][j];        // Swap the elements
        M[i][j] = M[j][i];
        M[j][i] = tmp;
      }
    }
  }
  
  /* Translate a lower triangular matrix to a square symmetric matrix */ 
  public static int[][] triToSym(int[][] T) {
    int n = T.length;
    int[][] M = new int[n][n];  // Initialize the new nxn square matrix
    
    for (int i=0; i<n; i++) {
      /* If the length of the current row is not exactly up to the main diagonal,
       * T is not a lower triangualar matrix, so return null */
      if (T[i].length != (i+1))
        return null;
    
      /* Iterate over the columns in each row, and place the elements above and below
       * the main diagonal in the new matrix M */
      for (int j=0; j<i; j++) {
        M[i][j] = T[i][j];
        M[j][i] = T[i][j];
      }
      M[i][i] = T[i][i];    // Place an entry on the main diagonal itself
    }
      
    return M;     // Return the new matrix
  }
  
  /* CHALLENGE EXERCISE: Create a square matrix from a ragged matrix, and fill the
   * missing coordinates with random values.
   */
  public static int[][] raggedToSquare(int[][] R) {
    int nrows   = R.length;             // Get the number of rows
    int maxCols = -1;                   
    int minVal  = Integer.MAX_VALUE;
    int maxVal  = Integer.MIN_VALUE;
    
    // Iterate over all rows.  See which row has the most colums
    for (int i=0; i<nrows; i++) {
      if (R[i].length > maxCols)
        maxCols = R[i].length;
      
      /* Now, iterate over every column, to find the minimum and maximum
       * value in the matrix */
      for (int j=0; j<R[i].length; j++) {
        if (R[i][j] > maxVal)
          maxVal = R[i][j];         // Found new maximum value
        if (R[i][j] < minVal)
          minVal = R[i][j];         // Found new minimum value
      }
    }
    
    /* Create a new square matrix, with number of rows and column determined
     * by the maximum of rows or columns in R */
    int n = Math.max(nrows, maxCols);
    int[][] M = new int[n][n];
    
    /* Populate the new matrix, either with elements from corresponding cells of R,
     * or with randomly generated values between minVal nad MaxVal */
    for (int i=0; i<n; i++) {
      for (int j=0; j<n; j++) {
        // Check if the coordinate (i,j) is present in the original R.
        if ( (i+1) <= R.length && (j+1) <= R[i].length )
          M[i][j] = R[i][j];
        else
          M[i][j] = (int)(Math.random() * (maxVal - minVal + 1)) + minVal;
      }
    }
    
    return M;
  }
  
  
  /* Print the contents of a 2-D array. */
  public static void printMatrix(int[][] M) {
    if (M==null) {
      System.out.println("\tnull");
      return;
    }
    
    for (int i=0; i<M.length; i++) {         // Go through all the rows
      for (int j=0; j<M[i].length; j++) {    // Go through the columns of each row
        System.out.print("\t");              // Print a tab
        if (M[i][j]<0)
          System.out.print(M[i][j]);
        else
          System.out.print(" "+M[i][j]);     // Add space, so that numbers can align nicely
      }
      System.out.println();   // Finish off the line
    }
  }
    
  // Constants for random matrix definition:  Please see below
  public static final int MATRIX_TYPE_SQUARE = 0;     // Square matrix
  public static final int MATRIX_TYPE_RECT   = 1;     // Rectangular matrix
  public static final int MATRIX_TYPE_TRIL   = 2;     // Lower triangular
  public static final int MATRIX_TYPE_RAGGED = 3;     // General ragged matrix
  
  /* Generate a 2-D array matrix of random integers.   
   * Parameters:
   *   maxN:   The maximum number of either rows or columns in the matrix
   *   minVal: The minimal integer value in the matrix
   *   maxVal: The maximum integer value in the matrix 
   *   type:   Type of matrix (see constant definitions above)
   * Returns:
   *   The newly generated random matrix
   */
  public static int[][] genRandomMatrix(int maxN, int minVal, int maxVal, int type) {
    int nrows = (int)(Math.random() * maxN) + 1;    // Generate a random number of rows    
    int[][] M = new int[nrows][];    // Initialize array of rows
    int ncols = 0;
       
    if (type == MATRIX_TYPE_SQUARE) {
      ncols = nrows;   // The number of rows and columns is the same
    } else if (type == MATRIX_TYPE_RECT) {
      ncols = (int)(Math.random() * maxN) + 1;      // Generate a random number of columns
    }

    for (int i=0; i<nrows; i++) {
      if (type == MATRIX_TYPE_TRIL)
        ncols = i+1;    // Number of columns increases by one with each row
      else if (type == MATRIX_TYPE_RAGGED) 
        ncols = (int)(Math.random() * maxN) + 1;    // Number of columns is random for each row
                
      M[i] = new int[ncols];        // Initialize array of columns for each row
      for (int j=0; j<ncols; j++)   // Populate each cell in the matrix
        M[i][j] = (int)(Math.random() * (maxVal - minVal + 1)) + minVal;
    }
    
    // Return the newly created random matrix
    return M;
  }
  
  
  /* The main() method */
  public static void main(String args[]) {
    // Test the largestColumnFirst() method, if desired
    if (TEST_largestColumnFirst) {
      System.out.println("\nTesting largestColumnFirst(): ");
      System.out.println("------------------------------");
      int[][] M = genRandomMatrix(7, 0, 9, MATRIX_TYPE_RECT);
      System.out.println("  Random Matrix: ");
      printMatrix(M);
      largestColumnFirst(M);
      System.out.println("  After swapping the first and largest-sum columns: ");
      printMatrix(M);
    }
    
    // Test the transpose() method, if desired
    if (TEST_transpose) {
      System.out.println("\nTesting transpose(): ");
      System.out.println("------------------------------");
      int[][] M = genRandomMatrix(5, 0, 9, MATRIX_TYPE_SQUARE);
      System.out.println("  Random Matrix: ");
      printMatrix(M);
      transpose(M);
      System.out.println("  After transpose: ");
      printMatrix(M);
    }
    
    // Test the triToSym method, if desired
    if (TEST_triToSym) {
      System.out.println("\nTesting triToSym(): ");
      System.out.println("------------------------------");
      int matrixType = MATRIX_TYPE_TRIL;
      // About a quarter of the time, make matrix rugged, to see if triToSym() correctly returns null
      if (Math.random() < 0.25)   
        matrixType = MATRIX_TYPE_RAGGED;
      int[][] T = genRandomMatrix(7, 0, 9, matrixType);
      System.out.println("  Random Matrix: ");
      printMatrix(T);
      int[][] M = triToSym(T);
      System.out.println("  Returned matrix: ");
      printMatrix(M);
    }

    // Test ruggedToSquare() method, if desired
    if (TEST_raggedToSquare) {
      System.out.println("\nTesting raggedToSquare(): ");
      System.out.println("------------------------------");
      int[][] T = genRandomMatrix(7, -9, 9, MATRIX_TYPE_RAGGED);
      System.err.println("  Random Matrix: ");
      printMatrix(T);
      int[][] M = raggedToSquare(T);
      System.out.println("  Returned matrix: ");
      printMatrix(M);
    }

    // All done!
    System.out.println("\nAll tests completed!  Exiting...");
  }
}