/*
Research Project:   Graphical Database for Category Theory
                    J. Bradbury, Dr. R. Rosebrugh, I. Rutherford
                    M. Graves, J. Tweedle
                    Mount Allison University 2001
                    Updated: May 8th, 2003
File:               Epi.java
Description:        This class contains the algorithms to check categories for
					epimorphisms.  It is used only by the EpiFrame class.
*/

public class Epi
{
	private Category cat;
	private int numepis;
	private String output;
	private boolean supress_output;
	private boolean endopassed;


	public Epi(Category newCat)
	{
		numepis = 0;
		supress_output = false;
		endopassed = false;
		output = "";
		cat = newCat;
	}

	public void generate_epis(int path[], int domain, HomTree pathtree, int maxloop)
	/*
	Parameters:
         path:   the current path
         domain: the current object of the path
         codomain:       the object we are trying to find all arrows to
         objects:        an array of integers which keeps the function from exceeding
                                 the maximum number of loops
         yestree:  tree of verified epimorphisms
         notree:   tree of verified non-epimorphisms
	Purpose:
         To find all epimorphisms from domain to codomain
	*/
	{
		int i, j, len, number, endo = 0;
		int arrow_array[] = new int [cat.num_arrows];
		String returning = "";
		path = cat.reduce(path);
		len = cat.path_len(path);
		if (path[0] == -2)
			path[0] = -1;

		for (i=0; i<len; i++)
			if (cat.arr[path[i]][1] == cat.arr[path[len-1]][0])
				endo++;

		if (endo < maxloop && len < cat.ini.getMAXWORD()-1)
		{
			if (!pathtree.containsPath(path))
			{
				pathtree.addPath(path);
				if (len > 0)
				{
					if (isepi(path))
					{
						output+=cat.path_to_string(cat.reverse_path(path)) + " is an epimorphism!\n";
						numepis++;
					}
				}
	
				number = cat.all_arr(domain, arrow_array);
				if (number > 0)
					for (i=0; i<number; i++)
					{
						for (j=cat.path_len(path); j>=0; j--)
						path[j+1] = path[j];
						path[0] = arrow_array[i];
						generate_epis(path, cat.arr[arrow_array[i]][1], pathtree, maxloop);
						for (j=0; j<=len; j++)
						path[j] = path[j+1];
					}
			}
		}
		else
			endopassed = true;
	}

	public boolean isepi(int[] epiP)
	{
		int path[] = new int[cat.ini.getMAXWORD()];
		HomTree alphatree, aepitree, pathtree;
		int obj, codomain;

		codomain = cat.arr[epiP[cat.path_len(epiP)-1]][0];

		for (obj=0; obj<cat.num_objects; obj++)
		{
			if (obj != codomain)
			{
				alphatree = new HomTree();
				aepitree = new HomTree();
				pathtree = new HomTree();
				path[0] = -1;

				if (!check_epi(alphatree, aepitree, epiP, path, obj, codomain, pathtree))
				{
					if (!supress_output)
						output += "Problem at object " + cat.obj[obj] + ".\n" + cat.path_to_string(epiP) + " is not an epimorphism.\n";
					return false;
				}
			}
		}
		return true;
	}


	public boolean check_epi(HomTree alphatree, HomTree aepitree, int[] epi, int[] path, int domain, int codomain, HomTree pathtree)
	/*
	Parameters:
      alphatree     - the tree to contain the paths
      aepitree     - the tree to contain the paths composed with the epi path
      epi[]        - the path to check as a epimorphism
      path[]        - integer array containing the path followed so far
      domain        - domain of paths to check
      codomain      - codomain of paths to check
	Purpose:
      Check if the epi path is a epimorphism
	*/
	{
		int i, j;
		int pathlen;
		int endo = 0;
		int numarrs;

		path = cat.reduce(path);
		pathlen = cat.path_len(path);
		if (path[0] == -2)
			path[0] = -1;

		for (i=0; i<pathlen; i++)
		{
			if (cat.arr[path[i]][1] == cat.arr[path[pathlen-1]][0])
				endo++;
		}

		if (endo < cat.ini.getMaxLoop() && pathlen < cat.ini.getMAXWORD()-1)
		{
			int[] newpath = cat.reduce(path);
			if (!pathtree.containsPath(newpath))
			{
				pathtree.addPath(newpath);
				// now check all paths from here, recursively
				int arrows[] = new int[cat.num_arrows];
				numarrs = cat.all_arr(domain, arrows);

				if (pathlen < cat.ini.getMAXWORD()-1)
					for (i = 0; i < numarrs; i++)
					{
						// add the new arrow to the path
						for (j=pathlen; j>=0; j--)
							path[j+1] = path[j];
						path[0] = arrows[i];

						// check recursively
						if (!check_epi(alphatree, aepitree, epi, path, cat.arr[path[0]][1], codomain, pathtree))
							return false;

						// now remove the arrow and object from the path
						for (j=0; j<=pathlen; j++)
							path[j] = path[j+1];
					}

				// if we're at the second object, then add the path to the tree
				if (path[0] != -1 && cat.arr[path[0]][1] == codomain)
				{
					int alpha[] = cat.reduce(path);
					if (alphatree.addPath(alpha))
					{
						alpha = cat.reduce(cat.append_path(path, epi));
						if (!aepitree.addPath(alpha))
							return false;
					}
				}
			}
		}
		else
			endopassed = true;
		return true;
	}

// get/set methods
	public int getNumEpis()
	{
		return numepis;
	}
	
	public void setNumEpis(int newNumEpis)
	{
		numepis = newNumEpis;
	}
	
	public String getOutput()
	{
		return output;
	}
	
	public void setOutput(String newOutput)
	{
		output = newOutput;
	}

	public boolean getSupressOutput()
	{
		return supress_output;
	}
	
	public void setSupressOutput(boolean newSupressOutput)
	{
		supress_output = newSupressOutput;
	}
	
	public boolean getEndoPassed()
	{
		return endopassed;
	}
	
	public void setEndoPassed(boolean newEndoPassed)
	{
		endopassed = newEndoPassed;
	}
	
}