import java.io.Serializable;

/*
 * File: ABMatrix.java
 * Author: Dillon Sadofsky (adapted from the materials at cse.unl.edu/~scot)
 *
 * Description:	this class represents a smart ADT.  The object represents a matrix of
 * 	constraints.  I implemented some more in depth constructors, accessors, mutators,
 * 	and a couple matrix functions that are helpful.
 */

public class ABMatrix implements Serializable
{
	/**
	 * for Serializable interface
	 */
	private static final long serialVersionUID = 5334532903567570727L;

	/**
	 * M is the number of rows and columns since we always have a square matrix
	 * I made these members private because they should be.
	 */
	public int M;

	/**
	 * This is the actual matrix that you must use
	 */
	public double[][] matrix;

	// Basic constructor
	public ABMatrix()
	{
		matrix = null;
		M = 0;
	}

	// Constructor that specifies matrix size (initialize to -infinity)
	public ABMatrix(int m) throws Exception
	{
		if (m < 0)
			throw new Exception("The size of the ABMatrix is invalid!");

		M = m;
		matrix = new double[m][m];

		EmptyMatrix();
	}

	// Constructor with initial data
	public ABMatrix(int m, double[][] aryNew) throws Exception
	{
		if (m < 0 || m != aryNew.length)
			throw new Exception("The size of the ABMatrix is invalid!");

		M = m;
		matrix = aryNew;
	}

	// Copy constructor
	public ABMatrix(ABMatrix abmNew)
	{
		M = abmNew.M;
		matrix = abmNew.matrix;
	}

	/**
	 * This loads a previously saved matrix
	 * @param filename
	 */
	public ABMatrix(double[][] input, int m, String[] variables) throws Exception
	{
		M = m;
		matrix = input;

		if (m != variables.length)
		{
			throw new Exception("The number of variables must match the size of the programs.");
		}
	}

	/*
	 * Function:	EmptyMatrix()
	 * Input:		None
	 * output:		None
	 * 		This function sets the value of all elements in the array to negative infinity.
	 * This is my simple way of clearing out the elements (good on construction).
	 */
	public void EmptyMatrix()
	{
		for (int i = M - 1; i >= 0; --i)
		{
			for (int j = M - 1; j >= 0; --j)
			{
				matrix[i][j] = Double.NEGATIVE_INFINITY;
			}
		}
	}

	// Dimension accessor
	public int GetDimension()
	{
		return M;
	}

	// Array item accessor
	public double GetItem(int m, int n)
	{
		return matrix[m][n];
	}

	// Sort of an overwrite of the = operator
	public void Copy(ABMatrix old)
	{
		M = old.M;
		matrix = old.matrix;
	}

	// Copies and returns the current matrix
	public ABMatrix Clone()
	{
		ABMatrix abmNew = new ABMatrix(this);
		return abmNew;
	}

	// Mutator for matrix items
	public void SetItem(int m, int n, double val)
	{
		matrix[m][n] = val;
	}

	/*
	 * The next two functions compute transitive closure.  One stores the result in this.
	 */
	public ABMatrix GetTransitiveClosure()
	{
		ABMatrix abmNew = this;
		int nMaxDepth = M; //Math.log(M); // I think we need log base 2, because we're talking about paths in a tree, right?

		// This is the maximum path depth that we need account for
		for (int cnt = 0; cnt < nMaxDepth; ++cnt)
		{
			for (int i = 0; i < M; ++i)
			{
				for (int j = 0; j < M; ++j)
				{
					for (int k = 0; k < M; ++k)
						matrix[i][j] = TransitiveMax(matrix[i][j], TransitiveAdd(matrix[i][k], matrix[k][j]));
				}
			}
		}

		return abmNew;
	}

	/* Like above, but it stores the transitive closure version of the matrix in 'this'
	 */
	public void DoTransitiveClosure()
	{
		Copy(GetTransitiveClosure());
	}

	/*
	 * This is a regular adding function that accounts for negative infinity
	 */
	static private double TransitiveAdd(double a, double b)
	{
		// Just make sure that we don't make things greater than -Infinity by adding to it
		if (a == Double.NEGATIVE_INFINITY || b == Double.NEGATIVE_INFINITY)
			return Double.NEGATIVE_INFINITY;
		else
			return a + b;
	}

	/*
	 * I was suspicious of the way the math library would treat -inifinity so I wrote this to make sure
	 */
	static private double TransitiveMax(double a, double b)
	{
		// We want to know which is larger, a, or b + c, but we must account for negative infinity
		if (a == Double.NEGATIVE_INFINITY)
		{
			// If a is negative infinity, return b no matter what it is
			return b;
		}
		else if (b == Double.NEGATIVE_INFINITY)
			return a;
		else
			return Math.max(a, b);
	}

	/*
	 * A trace function for simpler debugging
	 */
	public void Trace()
	{
		for (int i = 0; i < M; ++i)
		{
			for (int j = 0; j < M; ++j)
			{
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	/*
	 * This function is a logical replacement for the == operator
	 */
	public boolean Equals(ABMatrix b)
	{
		if (M != b.M)
			return false;

		for (int i = M - 1; i >= 0; --i)
		{
			for (int j = M - 1; j>= 0; --j)
			{
				if (matrix[i][j] != b.matrix[i][j])
					return false;
			}
		}

		return true;
	}
}
