/*
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:               Equalizer.java
Description:        This class contains the algorithms to check a given
                    category for equalizers.  It is used only by the
                    EqualizerFrame class.
*/


public class Equalizer
{
	private Category cat;
	private int numequalizers;
	private String output;
	private String type;
	private boolean supress_output;
	private boolean endopassed;

	public Equalizer(Category newCat, String newType)
	{
		cat = newCat;
		numequalizers = 0;
		supress_output = false;
		endopassed = false;
		output = "";
		type = newType;
	}

	public void checkEqualizer(int i, int[] alpha, int[] beta)
	{
		int path[] = new int[cat.ini.getMAXARR()];
		int objects[] = new int[cat.num_objects];
		HomTree yestree, notree;
		supress_output = true;
		numequalizers = 0;
		int codomain = cat.arr[alpha[cat.path_len(alpha)-1]][0];

		for (int j=0; j<cat.num_objects; j++)
			objects[j] = 0;

		path[0] = -1;
		yestree = new HomTree();
		notree = new HomTree();
		
/*		if (cat.equals(cat.reduce(alpha), cat.reduce(beta)))
		{
			if (type.equals("equalizer"))
				output = "1 is an equalizer!\n";
			else if (type.equals("coequalizer"))
				output = "1 is a coequalizer!\n";
			numequalizers++;
			return;
		}*/
		
		generate_equalizers(path, i, codomain, objects, yestree, notree, alpha, beta, cat.ini.getMaxLoop());
	}

	public boolean equalizer(int[] equalizer, int[] alpha, int[] beta)
	{
		int arrows[] = new int[cat.num_arrows];
		int path[] = new int[cat.ini.getMAXWORD()];
		HomTree tree1, tree2, pathtree;
		int i, obj, number, domain, codomain;

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

		for (obj=0; obj<cat.num_objects; obj++)
		{
			tree1 = new HomTree();
			tree2 = new HomTree();

			pathtree = new HomTree();
			path[0] = -1;
			if (!makeEGammaTree(path, tree1, tree2, obj, domain, cat.ini.getMaxLoop(), equalizer, pathtree))
				return false;

			tree2 = new HomTree();
			pathtree = new HomTree();
			path[0] = -1;
			makeEPrimeTree(path, tree2, obj, codomain, cat.ini.getMaxLoop(), alpha, beta, pathtree);

			if (!tree1.isEqual(tree2)) // && obj != codomain && obj != cat.arr[alpha[path_len(alpha)-1]][1])
			{
				if (!supress_output)
				{
					if (type.equals("equalizer"))
						output = "Problem at object " + cat.obj[obj] + ".\n" + cat.path_to_string(equalizer) + " is not an equalizer.\n";
					else if (type.equals("coequalizer"))
						output = "Problem at object " + cat.obj[obj] + ".\n" + cat.path_to_string(cat.reverse_path(equalizer)) + " is not a coequalizer.\n";
				}
				return false;
			}
		}
		if (type.equals("equalizer"))
			output = cat.path_to_string(equalizer) + " is an equalizer!\n";
		else if (type.equals("coequalizer"))
			output = cat.path_to_string(cat.reverse_path(equalizer)) + " is a coequalizer!\n";
		return true;
	}

	public void generate_equalizers(int path[], int domain, int codomain, int objects[], HomTree yestree, HomTree notree, int[] alpha, int[] beta, 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;
		int arrow_array[] = new int [cat.num_arrows];
		path = cat.reduce(path);

		len = cat.path_len(path);
		if (!yestree.containsPath(path) && !notree.containsPath(path) && objects[domain] < maxloop)
		{
			if (len > 0 && cat.arr[path[0]][1] == codomain)
			{
				if (equalizer(path, alpha, beta))
				{
					numequalizers++;
					yestree.addPath(path);
				}
				else
				{
					notree.addPath(path);
				}
			}

			number = cat.all_arr(domain, arrow_array);
			if (number > 0)
				for (i=0; i<number; i++)
				{
					domain = cat.arr[arrow_array[i]][1];
					objects[domain]++;
					if (path[0] == -2)
						path[0] = -1;
					for (j=cat.path_len(path); j>=0; j--)
						path[j+1] = path[j];
					path[0] = arrow_array[i];
	
					generate_equalizers(path, domain, codomain, objects, yestree, notree, alpha, beta, maxloop);
	
					for (j=0; j<=len; j++)
						path[j] = path[j+1];
					objects[domain]--;
				}
		}
		else
		{
			notree.addPath(path);
		}
	}

	public void makeEPrimeTree(int path[], HomTree homtree, int obj1, int obj2, int maxloop, int alphapath[], int betapath[], HomTree pathtree)
	/*
		Parameters:
			path[] - integer array containing the path followed so far
			objects[] - integer array containing a list of all the objects visited along the path
			homtree - the tree to contain the paths
			obj1 and obj2 - check for paths from obj1 to obj2
			maxloop - max endomorphism limit
		Purpose:
			To generate the reduced hom set from one object to another as a tree
		Design:
			Creates a tree homtree of all the reduced paths from one object to another.
	*/
	{
		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 < maxloop && pathlen < cat.ini.getMAXWORD()-1)
		{
			if (!pathtree.containsPath(path) || pathlen == 0)
			{
				pathtree.addPath(path);
				// now check all paths from here, recursively
				int arrows[] = new int[cat.num_arrows];
				numarrs = cat.all_arr(obj1, arrows);

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

						makeEPrimeTree(path, homtree, cat.arr[arrows[i]][1], obj2, maxloop, alphapath, betapath, pathtree);

						// now remove the arrow and object from the path and object list
						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 ((pathlen == 0 && obj1 == obj2) || (pathlen != 0 && cat.arr[path[0]][1] == obj2))
				{
					int f[] = cat.reduce(cat.append_path(path, alphapath));
					int g[] = cat.reduce(cat.append_path(path, betapath));
					if (cat.equals(f, g))
						homtree.addPath(path);
				}
			}
		}
		else
			endopassed = true;
	}

	public boolean makeEGammaTree(int path[], HomTree homtree, HomTree gammatree, int obj1, int obj2, int maxloop, int equalizer[], HomTree pathtree)
	/*
		Parameters:
			path[]				- integer array containing the path followed so far
			objects[]		 - integer array containing a list of all the objects visited along the path
			homtree			 - the tree to contain the paths
			obj1 and obj2 - check for paths from obj1 to obj2
			maxloop			 - max endomorphism limit
		Purpose:
			To generate the reduced hom set from one object to another as a tree
		Design:
			Creates a tree homtree of all the reduced paths from one object to another.
	*/
	{
		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 < maxloop && pathlen < cat.ini.getMAXWORD()-1)
		{
			int newpath[] = cat.reduce(path);
			if (!pathtree.containsPath(newpath) || pathlen == 0)
			{
				pathtree.addPath(newpath);
				// now check all paths from here, recursively
				int arrows[] = new int[cat.num_arrows];
				numarrs = cat.all_arr(obj1, arrows);

				for (i=0; i<numarrs; i++)
				{
					// add the new arrow to the path, and the new object to the object list
					for (j=pathlen; j>=0; j--)
						path[j+1] = path[j];
					path[0] = arrows[i];

					if (!makeEGammaTree(path, homtree, gammatree, cat.arr[arrows[i]][1], obj2, maxloop, equalizer, pathtree))
						return false;

					// now remove the arrow and object from the path and object list
					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 ((pathlen == 0 && obj1 == obj2) || (pathlen != 0 && cat.arr[path[0]][1] == obj2))
				{
					if (!gammatree.containsPath(path))
					{
						gammatree.addPath(path);
						int reducedpath[] = cat.reduce(cat.append_path(path, equalizer));
						if (homtree.containsPath(reducedpath))
							return false;
						homtree.addPath(reducedpath);
					}
				}
			}
		}
		else
			endopassed = true;
		return true;
	}

// get/set methods
	public int getNumEqualizers()
	{
		return numequalizers;
	}

	public void setNumEqualizers(int newNumEqualizers)
	{
		numequalizers = newNumEqualizers;
	}
		
	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;
	}
}