package rebelsky.util;		// If you make your own copy of this class,
				// replace this line with 
				//   import rebelsky.util.*;

import java.util.Vector;	// We're building matrices from
				// vectors

/**
 * A simple implementation of variable-size matrices.  These matrices are
 * allowed to shrink and grow.  While Java numbers most things starting at
 * 0, the indices for rows and columns in these matrices begin at 1.
 * <p>
 * Copyright (c) 1998 Samuel A. Rebelsky.  All rights reserved.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of February 1998
 */
public class Matrix
{
  /*
   * Primary design: We'll represent the matrix as a vector of vectors,
   * using appropriate techniques to ensure that each of the "subvectors"
   * has the same size.  Each subvector will represent one row of the
   * matrix. 
   *
   * For the standard methods, we'll take advantage of java.util.Vector
   * providing equivalent methods and just use those methods.
   */
    
  // +------------+--------------------------------------------------------
  // | Attributes |
  // +------------+
  
  /**
   * The set of rows.
   */
  protected Vector contents;
  
  /**
   * The number of rows.  Not strictly necessary, but useful for error
   * checking.  We could also use contents.size(), but that's slightly
   * more costly and potentially inaccurate.
   */
  protected int rows;
  
  /**
   * The number of columns.  Again, not strictly necessary, but useful for
   * error checking.  We could also use ((Vector) contents.elementAt(0)).size(),
   * but that's also more costly, potentially inaccurate, and may throw
   * a number of exceptions.
   */
  protected int cols;
  
  /**
   * Are we testing something?
   */
  protected static boolean TESTING = false;


  // +--------------+------------------------------------------------------
  // | Constructors |
  // +--------------+
  
  /**
   * Build a matrix with n rows and m columns and empty (null) cells.
   */
  public Matrix(int rows, int cols)
  {
    this(null, rows, cols);
  } // Matrix(int, int)
  
  /**
   * Build a matrix with n rows, m columns, and all cells set to some
   * default object.  Does not currently make copies of the object
   * but maydo so eventually.
   */
  public Matrix(Object obj, int rows, int cols)
  {
    // One row in the vector
    Vector oneRow;
    
    // Record the number of rows and columns
    this.rows = rows;
    this.cols = cols;
    // Create the list of rows
    this.contents = new Vector(rows);
    // Create each row and add it to the list of rows
    for (int row = 0; row < rows; ++row) {
      // Create the current row.
      oneRow = new Vector(cols);
      // Fill in the row, a column at a time.
      for (int col = 0; col < cols; ++col) {
/*
        if ((obj != null) && (obj instanceof Cloneable)) {
          // For some reason, the next two lines don't work.  We'll
          // use hack and just use the original object.
          Cloneable copyme = (java.lang.Cloneable) obj;
          oneRow.addElement(copyme.clone());
        }
        else {
          oneRow.addElement(obj);
        }
 */
        oneRow.addElement(obj);
      } // for each column
      // Add the row to the list
      contents.addElement(oneRow);
    } // for each row
  } // Matrix(Object, int, int)
  
  
  // +---------+-----------------------------------------------------------
  // | Methods |
  // +---------+
  
  /**
   * Clear the matrix.
   * <br>pre: (none)
   * <br>post: # of rows is 0.
   * <br>post: # of columns is 0.
   */
  public void clear()
  {
    // Just replace the contents with an empty vector.
    contents = new Vector();
    rows = 0;
    cols = 0;
  } // clear()
 
  /**
   * Get the number of columns.
   * <br>pre: (none)
   * <br>post: the number of columns is returned
   *
   * @return the number of columns.
   */
  public int columns()
  { 
    return cols;
  } // columns()
 
  /**
   * Delete one column of the matrix.
   * <br>pre: 1 <= col <= columns.
   * <br>post: the matrix has one fewer column.  In particular, the specified
   *           column is deleted.
   *
   * @exception BoundsException
   *   when the column is invalid.  In this case, the matrix is not affected.
   * @exception Exception
   *   when an unknown error occured.  In this case, the matrix may be
   *   seriously damaged.
   */
  public void deleteColumn(int col)
    throws BoundsException, Exception
  {
    // Verify the column.  If this fails, an exception is thrown.
    verifyColumn(col);
    // Step through the rows, deleting the appropriate element from each row.
    // If one of these fails, the matrix will most likely be of uneven size,
    // so we throw a different kind of exception.
    try {
      // Grab each row from the vector of rows and delete the
      // appropriate element.
      for(int row = 0; row < rows; ++row) {
        ((Vector) contents.elementAt(row)).removeElementAt(col-1);
      } // for
      // Update the number of columns.
      cols = cols - 1;
    }
    catch (Exception problem) {
      throw new Exception("Matrix is severely damaged.");
    }
  } // deleteColumn(int)
  
  /**
   * Delete one row of the matrix.
   * <br>pre: 1 <= row <= rows.
   * <br>post: the matrix has one fewer row (in particular, the specified
   *     row is deleted).
   *
   * @exception BoundsException
   *   when the row is invalid.  In such cases, the matrix isn't affected.
   */
  public void deleteRow(int row)
    throws BoundsException
  {
    // Make sure that the row is correct.  This throws an exception if it
    // fails.
    verifyRow(row);
    // Delete the row from the list of rows and update the number of rows.
    try {
      contents.removeElementAt(row-1);
      rows = rows - 1;
    } // try
    catch (Exception problem) {
      throw new BoundsException();
    } // catch(Exception)
  } // deleteRow
 
  /**
   * Convert the matrix to a two-dimensional string (including
   * carriage returns).
   * <br>pre: The matrix is nonempty.
   * <br>post: A two-dimensional version is returned.
   */
  public String draw()
  {
    // The element at one position in the matrix.
    Object elem;
    // The string value of that element.
    String str;
    // In order to draw, we'll need to figure out a standard cell width
    // value.
    int cell_width = 0;
    // The string value of the matrix
    String picture = "";
    // A horizontal line (used for delimiting rows)
    String horiz = "";
    // A few dashes in that horizontal line
    String dashes = "";

    // Special case: empty matrix
    if ((rows == 0) && (cols == 0)) {
      return "*";
    }

    // Find the maximum width of any value.
    if ((""+rows).length() > cell_width) {
      cell_width = (""+rows).length();
    }
    if ((""+cols).length ()> cell_width) {
      cell_width = (""+cols).length();
    }
    for (int row = 1; row <= rows; ++row) {
      for (int col = 1; col <= cols; ++col) {
        try {
          elem = get(row, col);
        }
        catch (Exception e) {
          elem = "*";
        }
        if (elem != null) {
          str = elem.toString();
          if (str.length() > cell_width) {
            cell_width = str.length();
          }
        } // if the element is non-null
      } // for each column
    } // for each row

    // The number of spaces on the screen will be two more, so that we
    // can put a single space on each side of every data value.
    cell_width = cell_width + 2;

    // Determine the horizontal line.  This could probably be done
    // more efficiently, but ...
    for (int i = 0; i < cell_width; ++i) {
      dashes = dashes + "-";
    }
    dashes = dashes;
    horiz = StringUtils.spaces(cell_width) + "+";
    for (int col = 0; col < cols; ++col) {
      horiz = horiz + dashes + "+";
    } // for
    horiz = horiz + "\n";  // That's a carriage return

    // Print the column headers.  
    picture = picture + StringUtils.spaces(cell_width + 1);
    for (int col = 1; col <= cols; ++col) {
      picture = picture + StringUtils.center(""+col, cell_width) + " ";
    }
    picture = picture + "\n" + horiz;		// "\n" is carriage return
   
    // Print the rows
    for (int row = 1; row <= rows; ++row) {
      // Print the header
      picture = picture + StringUtils.right(""+row, cell_width - 1) + " |";
      // Print the cells
      for (int col = 1; col <= cols; ++col) {
        try {
          elem = get(row, col);
        }
        catch (Exception e) {
          elem = "*";
        }
        if (elem == null) {
          picture = picture + StringUtils.spaces(cell_width);
        }
        else {
          picture = picture + StringUtils.center(elem.toString(), cell_width);
        }
        picture = picture + "|";
      } // for each column
      picture = picture + "\n" + horiz; // carriage return
    } // for each row

    // That's it
    return picture;
  } // draw()
 
  /**
   * Fill along a "line" in the matrix.
   * <br>pre: 1 <= start_row <= number of rows
   * <br>pre: 1 <= end_row <= number of rows
   * <br>pre: 1 <= start_col < number of columns
   * <br>pre: 1 <= end_col <= number of columns
   * <br>pre: delta_row >= 0
   * <br>pre: delta_col >= 0
   * <br>pre: at least one of delta_row and delta_col is positive
   * <br>pre: (end_row,end_col) is a whole number of "steps" from
   *          (start_row,start_col), where a step is defined by
              (delta_row,delta_col).
   * <br>post: every position between (start_row,start_col) and
   *     (end_row,end_col) using an offset of (delta_row,delta_col)
   *     is set to val.
   * @throw BoundsException 
   *   when one of these conditions is not met.
   */
  public void fillLine(Object val,
                       int start_row, int start_col,
                       int delta_row, int delta_col,
                       int end_row, int end_col)
    throws BoundsException
  {
    // The current row and column (which we'll step through)
    int row = start_row;
    int col = start_col;

    // Test the many preconditions.  All the verifyXXX
    // methods throw exceptions.
    verifyRow(start_row);
    verifyRow(end_row);
    verifyColumn(start_col);
    verifyColumn(end_col);
    try {
      Assert.pre(delta_row + delta_col > 0, 
                 "At least one of the increments must be positive");
      Assert.pre(delta_row >= 0,
                 "The row increment must be nonnegative");
      Assert.pre(delta_col >= 0,
                 "The column increment must be nonnegative");
      Assert.pre(( (delta_row == 0) ||
                   (((end_row-start_row) % delta_row) == 0) ),
                 "The row increment must evenly divide the row distance");
      Assert.pre(( (delta_col == 0) || 
                   (((end_col - start_col) % delta_col) == 0) ),
                 "The column increment must evenly divide the column distance");
      Assert.pre(((delta_row > 0) || (end_row == start_row)),
                 "When the row increment is 0, " +
                 "the start and end row must be the same");
      Assert.pre(((delta_col > 0) || (end_col == start_col)),
                 "When the column increment is 0, " +
                 "the start and end column must be the same");
      Assert.pre(( (delta_row == 0) || (delta_col == 0) ||
                   ( ((end_row - start_row) / delta_row) ==
                     ((end_col - start_col) / delta_col) ) ),
                 "You must be able to end at the end point.");
    } // try
    catch (FailedPrecondition reason) {
      throw new BoundsException(reason.toString());
    } // catch(FailedPrecondition)

    // Step through the rows and the columns until we reach the end.
    while ((row <= end_row) && (col <= end_col)) {
      set(val, row, col);
      row = row + delta_row;
      col = col + delta_col;
    } // while
  } // fill(Object, int,int, int,int, int,int)
  
  /**
   * Get the value stored at (row,col).
   * <br>pre: 1 <= row <= rows.
   * <br>pre: 1 <= col <= cols.
   * <br>post: (none)
   *
   * @return the object stored at (row,col)
   * @exception BoundsException
   *   if the preconditions are not met
   */
  public Object get(int row, int col)
    throws BoundsException
  {
    // Make sure that the bounds are reasonable.  This throws an
    // exception if the bounds are not reasonable.
    verifyBounds(row,col);
    // Extract the appropriate element
    try {
      return ((Vector) contents.elementAt(row-1)).elementAt(col-1);
    }
    catch (Exception e) { // Probably ArrayIndexOutOfBoundsException, but ...
      throw new BoundsException();
    }
  } // get(int,int)
  
  /**
   * Get the value stored at a particular point.
   * <br>pre: 1 <= row <= rows.
   * <br>pre: 1 <= col <= cols.
   * <br>post: (none)
   *
   * @return the object stored at (row,col)
   * @exception BoundsException
   @   if the preconditions are not met
   */
  public Object get(MatrixIndex index)
    throws BoundsException
  {
    return get(index.row(), index.column());
  } // get(MatrixIndex)

  /**
   * Insert a new column into the matrix before a particular column.  If the
   * specified column is immediately after the last column in the matrix, inserts 
   * the new column as the last column in the matrix.  If the matrix is empty and 
   * the column is 1, makes a linear matrix corresponding to the column.
   * <br>pre: 1 <= col <= columns+1.
   * <br>pre: the length of the new column is the same as the number
   *     of rows in the matrix (or the matrix is empty).
   *
   * @exception BoundsException
   *   when the preconditions are not met.
   * @exception Exception
   *   when something goes wrong and it's possible we now have a non-square
   *   matrix.
   */
  public void insertColumn(Vector new_col, int col)
     throws BoundsException, Exception
  {
    // Make sure the column is reasonable.
    if (col != cols+1) {
      verifyColumn(col);
    }
    // Make sure that the new column is of the correct size
    if ((rows != 0) && (new_col.size() != rows)) {
      throw new BoundsException("invalid size column");
    } // if
    
    // Insert it 
    try {
      // Special case: empty matrix.  Create appropriately many rows
      if (rows == 0) {
        rows = new_col.size();
        for (int i = 0; i < rows; ++i) {
          contents.addElement(new Vector());
        }
      } // special case
      // Insert elements, one by one
      for (int i = 0; i < rows; ++i) {
        ((Vector) contents.elementAt(i)).insertElementAt(new_col.elementAt(i), 
                                                         col-1);
      } // for
    } // try
    catch (Exception problem) {
      throw problem;
    } // catch(Exception)
    // Increment the number of columns
    ++cols;
  } // insertColumn(Vector,int)
  
  /**
   * Insert a new row into the matrix before a particular row.  If that
   * particular row is immediately after the last row in the matrix,
   * inserts the new row as the last row in the matrix.  If the matrix is
   * empty and the row is 1, makes a linear matrix corresponding to the
   * row.
   * <br>pre: 1 <= row <= rows+1.
   * <br>pre: the length of the new row is the same as the number
   *     of columns in the matrix (or the matrix is empty).
   *
   * @exception BoundsException
   *   when the preconditions are not met.
   */
  public void insertRow(Vector new_row, int row)
    throws BoundsException
  {
    // Make sure the row is reasonable.
    if (row != rows+1) {
      verifyRow(row);
    }
    // Make sure that the new row is of the correct size
    if ((cols != 0) && (new_row.size() != cols)) {
      throw new BoundsException("invalid size row");
    } // if
    // Insert it
    try {
      contents.insertElementAt(new_row, row-1);
    }
    catch (Exception problem) {
      throw new BoundsException();
    }
    // Increment the number of rows
    ++rows;
    // Special case: previously empty matrix
    if (rows == 1) {
      cols = new_row.size();
    }
  } // insertRow(new_row)
  
  /**
   * Get the number of rows.
   * <br>pre: (none)
   * <br>post: the number of rows is returned.
   *
   * @return the number of rows.
   */
  public int rows()
  { 
    return rows;
  } // rows()
 
  /**
   * Set the value at (row,col) to obj.
   * <br>pre: 1 <= row <= rows.
   * <br>pre: 1 <= col <= cols.
   * <br>post: this[row,col] is obj
   *
   * @return the object previously stored at (row,col)
   * @exception BoundsException
   *   if the preconditions are not met
   */
  public Object set(Object obj, int row, int col)
    throws BoundsException
  {
    // Make sure that the bounds are reasonable.  This throws an
    // exception if the bounds are not reasonable.
    verifyBounds(row,col);
    // Do the real work.
    try {
      // Grab the appropriate row
      Vector theRow = (Vector) contents.elementAt(row-1);
      // Grab the old value.  We could probably use the return value of
      // the "set" command, but hey, I feel like doing it this way.
      Object old = theRow.elementAt(col-1);
      // Set the new value
      theRow.setElementAt(obj, col-1);
      // Return the old value
      return old;
     }
    catch (Exception e) { // Probably ArrayIndexOutOfBoundsException, but ...
      throw new BoundsException();
    }
  } // set(int,int)
  
  /**
   * Set the value at a point to obj.
   * <br>pre: 1 <= row <= rows.
   * <br>pre: 1 <= col <= cols.
   * <br>post: this[row,col] is obj
   *
   * @return the object previously stored at (row,col)
   * @exception BoundsException
   *   if the preconditions are not met
   */
  public Object set(Object obj, MatrixIndex index)
    throws BoundsException
  {
    return set(obj, index.row(), index.column());
  } // set(Object,MatrixIndex)


  // +------------------+--------------------------------------------------
  // | Standard Methods |
  // +------------------+
  
  /**
   * Make a copy of the current vector.
   * <br>pre: (none)
   * <br>post: (none)
   *
   * @return a copy of the current vector.
   */
  public Object clone()
  {
    // Build an empty matrix
    Matrix copy = new Matrix(0,0);
    // Update its attributes directly
    copy.contents = (Vector) contents.clone();
    copy.rows = rows;
    copy.cols = cols;
    // Return this new copy
    return copy;
  } // clone()
  
  /**
   * Determine if another object is equal to this matrix.
   * <br>pre: (none)
   * <br>post: (none)
   *
   * @return true if the other object is a matrix and that matrix is
   *         equal to this one (according to the rules of vectors); 
   *         false otherwise
   */
  public boolean equals(Object other)
  { 
    return ((other instanceof Matrix) && 
            contents.equals(((Matrix) other).contents));
  } // equals(Object)
  
  /**
   * Compute a hash value for this matrix.
   * <br>pre: (none)
   * <br>post: (none)
   *
   * @return an appropriate value
   */
  public int hashCode()
  {
    return contents.hashCode();
  } // hashCode()
  
  /**
   * Convert this matrix to a string.
   * <br>pre: (none)
   * <br>post: (none)
   *
   * @return a string of the form [[row1], [row2], ..., [rown]]
   */
  public String toString()
  {
    return contents.toString();
  } // toString


  // +---------------+-----------------------------------------------------
  // | Local Methods |
  // +---------------+
  
  /**
   * Verify that the bounds (row and column) are reasonable (row is
   * between 1 and rows, col is between 1 and cols).
   * <br>pre: 1 <= row <= rows.
   * <br>pre: 1 <= col <= cols.
   * <br>post: (none)
   *
   * @exception BoundsException
   *   when the preconditions are not met
   */
  protected void verifyBounds(int row, int col)
    throws BoundsException
  {
    verifyRow(row);
    verifyColumn(col);
  } // verifyBounds(int,int)
  
  /**
   * Verify that the column is between 1 and cols.
   * <br>pre: 1 <= col <= cols.
   * <br>post: (none)
   *
   * @exception BoundsException
   *   when the column is not between 1 and cols
   */
  public void verifyColumn(int col)
    throws BoundsException
  {
    try {
      Assert.pre((1 <= col) && (col <= cols), 
                 "column must be between 1 and " + cols);
    }
    catch (FailedPrecondition reason) {
      throw new BoundsException(reason.toString());
    } // catch(FailedPrecondition)
  } // verifyColumn(int)

  /**
   * Verify that the row is between 1 and rows.
   * <br>pre: 1 <= row <= rows.
   * <br>post: (none)
   *
   * @exception BoundsException
   *   when the row is not between 1 and rows
   */
  public void verifyRow(int row)
    throws BoundsException
  {
    try {
      Assert.pre((1 <= row) && (row <= rows), 
                 "row must be between 1 and " + rows);
    }
    catch (FailedPrecondition reason) {
      throw new BoundsException(reason.toString());
    } // FailedPrecondition
  } // verifyRow(int)

} // Matrix