/*
Research Project:   Graphical Database for Category Theory
                    J. Bradbury, Dr. R. Rosebrugh, I. Rutherford
                    Mount Allison University 2001
File:               InitialObject.java
Description:	      This file contains the algorithms to test a given category
                      for initial and terminal objects; 
                        -- when an initial object is to be tested for, the
                      category is passed in regularly, and the calling method
                      uses the setObjectType() method to set it as an
                      INITIAL_OBJECT (the default).  Then the algorithm is
                      performed, and the calling method gets the output via the
                      getOutput() method.
                        -- when a terminal object is to be tested for, the
                      category must first be dualled (i.e. call the makeDual()
                      method), then passed to the InitialObject constructor.
                      Then the calling method uses the setObjectType() method
                      to set it as a TERMINAL_OBJECT.  Then the algorithm (the
                      exact same algorithm as performed on an INITIAL_OBJECT) is
                      perforemd, and the calling method gets the output via the
                      getOutput() method.
*/

public class InitialObject
{

	private Category cat = new Category();	
	private String output;
	private String objectType;

	public InitialObject(Category newCat, String newObjectType)
	{
		cat = newCat;
		output = "";
		objectType = newObjectType;
	}


	//INITIAL/TERMINAL OBJECT FUNCTIONS
	
	public boolean check_initial(int path[], int domain, int objects[], int object_array[][], String orig)
	/*
	Parameters:
	        path:   array of integers containing the path of arrows followed
	                                        so far
	        domain: integer representing the domain of the current arrow in
	                                        the path
	        objects:array of integers containing the objects visited along
	                                        the current path
	        object_array:   uses the integers representing the objects as subscripts
	                                        and stores paths to each object as the elements of the
	                                        array
	        orig:  string containing the name of the object being tested for an initial object
	
	Purpose:
	        A recursive function to determine if object domain is initial.
	
	Design:
	        Traces all paths from object domain.  If a path is the first path
	        with its codomain, the path is stored in object_array.  Otherwise,
	        the path is compared to the path stored for the object which is the
	        codomain; if it is not equal to the stored path, the object is not
	        initial, a message is displayed, and the function returns false.
	        Otherwise, the function returns true.
	*/
	{
		int i, j, number, current_arrow, codomain;
		boolean done;
		int arrow_array[] = new int [cat.ini.getMAXARR()];
		int first[] = new int [cat.ini.getMAXWORD()];
		int second[] = new int [cat.ini.getMAXWORD()];
	
		// check for a looped path
		done = false;
		// for every object in the current path
		for (i=0; i<cat.path_len(objects)-1; i++)
		{
			// if the object we're at has already been visited along this path
			if (objects[i] == domain)
			{
				// first is the current path
				first = cat.copy_path(path);
				// second is the current path, but only up until the first occurence of this object
				second = cat.copy_path(path);
				for (j=cat.path_len(second)-i; j<=cat.path_len(second); j++)
				{
					second[j+i-cat.path_len(second)] = second[j];
				}
				// reduce both paths and see if they are equal
				first = cat.reduce(first);
				second = cat.reduce(second);

				// if they aren't equal then we can't have an initial object
				if (!cat.equals(first, second))
				{
					output += "\n" + orig + " NOT " + objectType.toUpperCase() + ": " + cat.path_to_string(first) + " and " + cat.path_to_string(second) + " are both paths to object " + cat.obj[domain];
					return false;
				}

				// presuming we're not at the first object, then we can stop here
				// if we are at the first object however, a path is already stored for it (-2 = identity)
				// so we can't finish here, or we won't have checked all the paths out of the first object
				if (cat.path_len(path) > 1)
					done = true;
			}
		}

		if (!done)
		{
			// make sure the current path is ok
			if (object_array[domain][0] == -1)
			{
				// this object has not been reached yet
				first = cat.copy_path(path);
				first = cat.reduce(first);
				object_array[domain] = cat.copy_path(first);
			}
			else
			{
				// make sure the current path equals the already-stored path
				first = cat.copy_path(path);
				second = cat.copy_path(object_array[domain]);
				first = cat.reduce(first);
				second = cat.reduce(second);
				if (!cat.equals(first, second))
				{
								output += "\n" + orig + " NOT " + objectType.toUpperCase() + ": " + cat.path_to_string(first) + " and " + cat.path_to_string(second) + " are both paths to object " + cat.obj[domain];
							return false;
					}
				}
		
			// check all arrows from this object
			number = cat.all_arr(domain, arrow_array);
			for (i=0; i<number; i++)
			{
				current_arrow = arrow_array[i];
				codomain = cat.arr[current_arrow][1];
	
				// add the current arrow to the path, and the current object to the objects list
				// NOTE: the path is stored in BACKWARDS order compared to the order in which the arrows
				// are follower. ie. it is stored in the same order as it would be written
				// the objects array is stored in normal forwards order - the order in which the objects
				// are visited along the path
				for (j=cat.path_len(path); j>=0; j--)
				{
					path[j+1] = path[j];
				}
				path[0] = current_arrow;
				objects[cat.path_len(objects)+1] = -1;
				objects[cat.path_len(objects)] = codomain;
	
				// now recurse by checking from the next object
				if (!check_initial(path, codomain, objects, object_array, orig))
					return false;
	
				// presuming the last call returned true, then we remove the last object from the path
				// and the last arrow
				for (j=0; j<cat.path_len(path); j++)
				{
					path[j] = path[j+1];
				}
				objects[cat.path_len(objects)-1] = -1;
			}
		}

		// if nothing failed, then return true
		return true;
	}

	public void initial_object(int objt)
	/*
	Parameter:
				objt:	 the object to be checked for initiality
	Purpose:
				To display a message indicating whether or not the object is initial.
	Design:
				Calls function check_initial
				to determine if the object has more than one path to any other object;
				if so, the object is not initial.	If there is no path to any object
				in the category, the object is not initial and a message is displayed.
				If there is exactly one path to ALL objects, it is displayed that the
				object is initial.
	*/
	{
		int path[] = new int [cat.ini.getMAXWORD()];
		int objectOnPath[] = new int [cat.ini.getMAXWORD()];
		int i;
		int pathsToObjects[][] = new int [cat.ini.getMAXWORD()][cat.ini.getMAXARR()];
		char name;
		char ob;

		// initialize the path and objects array
		path[0] = -1;
		objectOnPath[0] = objt;
		objectOnPath[1] = -1;

		//Initialize every object in pathsToObjects to
		//be -1, if a path from cat.obj[objt] to
		//an object exists, this value will change
		for(i=0; i < cat.num_objects; i++)
		{
			pathsToObjects[i][0] = -1;
		}

		//Set current object, cat.obj[objt], to a value
		//of -2 in pathsToObjects - it now has the identity path pointing to it
		pathsToObjects[objt][0] = -2;
		pathsToObjects[objt][1] = -1;

		//Determine if current object cat.obj[objt] has more than one path to
		//any other object
		if (check_initial(path,objt,objectOnPath,pathsToObjects,cat.obj[objt]))
		{
			//For all objects in category
			for(i=0; i < cat.num_objects; i++)
			{
				//If an index in the pathsToObjects is -1, this means
				//that there is no path from cat.obj[objt] to cat.obj[i]
				if(pathsToObjects[i][0] == -1)
				{
					if (objectType.toLowerCase().equals("initial"))
					{
						output += "\n" + cat.obj[objt] + " NOT " + objectType.toUpperCase() + ": no path to object " + cat.obj[i];
					}
					else
					{
						output += "\n" + cat.obj[objt] + " NOT " + objectType.toUpperCase() + ": no path from object " + cat.obj[i];
					}
					i = cat.num_objects + 1;
				}
			}

			//If there is a unique path to all objects then display message
			//that object cat.obj[objt] is an initial object
			if(i == cat.num_objects)
			{
				if (objectType.toLowerCase().equals("initial"))
				{
					output += "\n" + cat.obj[objt] + " is an " + objectType + " object!";
				}
				else
				{
					output += "\n" + cat.obj[objt] + " is a " + objectType + " object!";
				}
			}
		}
	}

	public String getOutput()
	{
		return output;
	}

	public void setOutput(String newOutput)
	{
		output = newOutput;
	}
}