/*********************************************************************
 * Author: B. Alex Bridges                                           *
 * Login ID: brid0129                                                *
 * Class: CPSC-102, Summer 1998                                      *
 * Project: Programming Assignment 2                                 *
 * Description: This program attempts to find an Euler tour in a     *
 *              given input graph.                                   *
 * Contents: main method which drives program.                       *
 *********************************************************************/

/* IMPORTS */
import java.io.*;
import java.util.Vector;
import java.util.StringTokenizer;


class Prog2
{
	/* CONSTANTS */
	final static boolean c_b_debug = true;		// CONTROLS EXTRA DEBUG OUTPUT
	final static int c_int_max_tree = 100;		// MAX. SIZE OF GRAPH'S TREE

	/* GLOBAL VARIABLES */
	static int int_edges = 0;					// FILE INPUT => NUMBER OF EDGES IN GRAPH

	/*************************************************************************
	 * Method: check_tour                                                    *
	 * Purpose: Checks if the tour is an Euler tour.                         *
	 * Input: --PARAMETERS--                                                 *
	 *        => Point_tour = Graph's current Tour as Series of Points       *
	 *        => int_edge_cnt = Current number of edges used                 *
	 * Output: --RETURN VALUES--                                             *
	 *         => YES = true                                                 *
	 *         => NO = false                                                 *
	 *************************************************************************/
	public static boolean check_tour(Point Point_c_tour, int int_edge_cnt)
	{
		/* LOCAL VARIABLES */
		int int_start = -1;	// TOUR'S START VALUE
		int int_stop = -1;	// TOUR'S STOP VALUE

		/* CRITERA #1: EACH EDGE HAS BEEN USED ONCE */
		if(int_edge_cnt == 2 * int_edges)
		{
			int_start = Point_c_tour.int_value;
			while(Point_c_tour.Point_next != null)
				Point_c_tour = Point_c_tour.Point_next;
			int_stop = Point_c_tour.int_value;
			/* CRITERIA #2: START POSITION = STOP POSITION */
			if(int_start == int_stop)
				return true;
			else
				return false;
		} // if
		else
			return false;
	} // method check_tour

	/*************************************************************************
	 * Method: extend_tour                                                  *
	 * Purpose: Adds new Point onto _beginning_ of tour.                     *
	 * Input: --PARAMETERS--                                                 *
	 *        => Point_tour = Graph's Current Tour as Series of Points       *
	 *        => Point_new = New Point for Tour                              *
	 * Output: --RETURN VALUES--                                             *
	 *         => COMPLETED SUCCESSFULLY = Point_tour                        *
	 *************************************************************************/
	public static Point extend_tour(Point Point_c_tour, Point Point_new)
	{
		Point_new.Point_next = Point_c_tour;
		return Point_new;
	} // method extend_tour

	/*************************************************************************
	 * Method: check_point                                                   *
	 * Purpose: Utilizes recursive-backtracking methodology to find tour.    *
	 * Input: --PARAMETERS--                                                 *
     *	      => arrPoint_tree = Graph's current Tree as Array of Points     *
	 *        => Point_tour = Graph's current Tour as Series of Points       *
	 *        => int_edge_cnt = Current number of edges used                 *
	 * Output: --RETURN VALUES--                                             *
	 *         => COMPLETED SUCCESSFULLY = Point_t_tour                      *
	 *         => DID NOT EXIST = null                                       *
	 *************************************************************************/
	public static Point check_point(Point[] arrPoint_c_tree, Point Point_c_tour, int int_edge_cnt)
	{
		/* LOCAL VARIABLES */
		boolean b_found_tour = false;		// GRAPH'S FOUND TOUR STATUS
		Point Point_t_tour = new Point();	// TEMPORARY TOUR
		Point Point_tmp;					// TEMPORARY POINT
		int int_p_point = -1;				// VALUE OF PREVIOUS POINT
		int int_c_point = -1;				// VALUE OF CURRENT POINT
		boolean b_fnd_pnt = false;			// STATUS OF FINDING POINT

		if(c_b_debug)
			System.out.println("DEBUG: Entered check_point");

		/* ASSIGN PROPER POINT VALUES */
		int_c_point = Point_c_tour.int_value;

		try
		{
			if(Point_c_tour.Point_next != null)
			{
				int_p_point = Point_c_tour.Point_next.int_value;

				if(c_b_debug)
					System.out.println("DEBUG: About to mark edges");

				/* MARK FORWARD AND BACKWARD EDGE AS USED */
				// => FORWARD EDGE = CURRENT POINT
				Point_tmp = arrPoint_c_tree[int_c_point];
				while(!b_fnd_pnt)
				{
					// ADVANCE THE REFERENCE TO THE NEXT POINT
					if(Point_tmp.int_value != int_p_point || Point_tmp.b_used)
						Point_tmp = Point_tmp.Point_next;
					else
						b_fnd_pnt = true;
				} // while
				Point_tmp.b_used = true;
				int_edge_cnt++;

				if(c_b_debug)
					System.out.println("DEBUG: Marked Current Point = "+int_c_point);

				// => BACKWARD EDGE = PREVIOUS POINT
				Point_tmp = arrPoint_c_tree[int_p_point];
				while(!b_fnd_pnt)
				{
					// ADVANCE THE REFERENCE TO THE NEXT POINT
					if(Point_tmp.int_value != int_c_point || Point_tmp.b_used)
						Point_tmp = Point_tmp.Point_next;
					else
						b_fnd_pnt = true;
				} // while
				Point_tmp.b_used = true;
				int_edge_cnt++;
				b_found_tour = check_tour(Point_c_tour, int_edge_cnt);

				if(c_b_debug)
					System.out.println("DEBUG: Marked Previous Point = "+int_p_point);
			} // if
		} // try
		catch(NullPointerException exception)
		{
			System.out.println(" FATAL EXCEPTION: Referenced NULL Pointer.");
			Point_tmp = new Point(-1);
			return Point_tmp;
		} // catch

		/* RESET CURRENT POSITION */
		Point_tmp = arrPoint_c_tree[int_c_point];
		if(c_b_debug)
			System.out.println("DEBUG: Looking at "+int_c_point+"'s Points . . . ");

		/* SET CURRENT POSITION AS NEXT UNUSED POINT */
		while(!b_found_tour && Point_tmp != null)
		{
			/* CONDITION #1: NEXT POINT */
			if(c_b_debug)
				System.out.println("DEBUG: --> Point "+Point_tmp.int_value);
			if(Point_tmp.b_used)
			{
				Point_tmp = Point_tmp.Point_next;
				if(c_b_debug)
					System.out.println("            which is used.");
			} // if
			else
			{
				if(c_b_debug)
					System.out.println("DEBUG: Began recurssion");
				Point_t_tour = check_point(arrPoint_c_tree, extend_tour(Point_c_tour, Point_tmp), int_edge_cnt);
				if(Point_t_tour.int_value == -1)
					Point_tmp = Point_tmp.Point_next;
				else
					b_found_tour = true;
				if(c_b_debug)
					System.out.println("DEBUG: Finished recurssion");
			} // else
		} // while

		/* CONDITION #2: RETURN TOUR --> PRINT*/
		if(b_found_tour && Point_tmp != null)
			return Point_t_tour;
		/* CONDITION #3: RETURN NULL --> ADVANCE STARTING POSITION */
		if(!b_found_tour && Point_tmp == null)
		{
			Point_tmp = new Point(-1);
			return Point_tmp;
		} // if

		/* IF FOR SOME REASON NONE OF THE ABOVE CONDITIONS ARE MET */
		Point_tmp = new Point(-1);
		return Point_tmp;
	} // method check_point

	/*************************************************************************
	 * Method: print_tour                                                    *
	 * Purpose: Prints the tour.                                             *
	 * Input: --PARAMETERS--                                                 *
	 *        => Point_tour = The tour.                                      *
	 * Output: N/A                                                           *
	 *************************************************************************/
	public static void print_tour(Point Point_tour)
	{
		while(Point_tour.Point_next != null)
		{
			System.out.print(Point_tour.int_value+", ");
			Point_tour = Point_tour.Point_next;
		} // while
	} // method print_tour

	/*************************************************************************
	 * Method: main                                                          *
	 * Purpose: Drives program.                                              *
	 * Input: --COMMAND-LINE ARGUMENTS--                                     *
	 *        1. 'GRAPH' = The filename of the graph's description.          *
	 * Output: --EXIT VALUES--                                               *
	 *         => COMPLETED SUCCESSFULLY = 1                                 *
	 *         => FATAL ERROR/EXCEPTION = -1                                 *
	 *************************************************************************/
	public static void main(String[] args)
	{
		/* LOCAL VARIABLES */
		int int_points = -1;								// FILE INPUT = NUMBER OF POINTS IN GRAPH
		String str_edges = "";								// FILE INPUT = CONCATENTAION OF EDGES IN GRAPH
		StringTokenizer strT_parser;						// STRING TOKENIZER
		Point Point_tour;									// GRAPH'S TOUR AS SERIES OF POINTS
		Point[] arrPoint_tree = new Point[c_int_max_tree];	// GRAPH'S TREE AS ARRAY OF POINTS
		int int_i;											// LOOP COUNTER
		int int_value1 = 0;									// VALUE1 OF CURRENT EDGE
		int int_value2 = 0;									// VALUE2 OF CURRENT EDGE
		Point Point_tmp;									// TEMPORARY POINT
		boolean b_result = false;							// RESULT FROM RECURSIVE METHOD

		/* HEADER */
		System.out.println("***********************************\n"+
						   "* BAB's Euler Tour Program v1.0.1 *\n"+
						   "***********************************\n");

		/* CHECKING FOR REQUIRED ARGUMENT */
		if(args.length != 1)
		{
			System.out.println(" FATAL ERROR: The following command-line argument must be included:\n"+
							   "  => 1. 'GRAPH' = The filename of the graph's description.");
			System.exit(-1);
		} // if

		try
		{
			/* FILE INPUT STREAM SETUP FOR GRAPH */
			BufferedReader br_file_in = new BufferedReader( new FileReader(args[0]) );

			System.out.println(" Reading '"+args[0]+"' . . . IN PROGRESS!\n");

			/* READING GRAPH'S POINTS */
			int_points = Integer.parseInt( br_file_in.readLine() );

			/* READING GRAPH'S EDGES */
			while( br_file_in.ready() )
			{
				str_edges = str_edges + br_file_in.readLine() +",";
				int_edges++;
			} // while

			System.out.println(" Reading '"+args[0]+"' . . . COMPLETED!\n");

			if(c_b_debug)
			{
			System.out.println("DEBUG: **Graph**\n"+
			                   "        --> '"+int_points+"' Points\n"+
			                   "        --> '"+int_edges+"' Edges = '"+str_edges+"'\n");
			} // if

			/* GRAPH'S EDGES => TOKENS => VALUES OF CURRENT EDGE => TREE */
			// GRAPH'S EDGES => TOKENS
			strT_parser = new StringTokenizer( str_edges, " ,", false );

			// FOR EACH EDGE . . .
			for(int_i = 1; int_i <= int_edges; int_i++)
			{
			//  TOKENS => VALUES OF CURRENT EDGE
			int_value1 = Integer.parseInt( strT_parser.nextToken() );
			int_value2 = Integer.parseInt( strT_parser.nextToken() );
				System.out.println("Value 1/2 = "+int_value1+"/"+int_value2);
			//  VALUES OF CURRENT EDGE => BEGINNING OF TREE . . .
			//   AS FORWARD EDGE
			Point_tmp = new Point(int_value2);
			Point_tmp.Point_next = arrPoint_tree[int_value1];
			arrPoint_tree[int_value1] = Point_tmp;
			//   AS BACKWARD EDGE
			Point_tmp = new Point(int_value1);
			Point_tmp.Point_next = arrPoint_tree[int_value2];
			arrPoint_tree[int_value2] = Point_tmp;
			} // for

			if(c_b_debug)
			{
				for(int_i = 0; int_i <= int_points - 1; int_i++)
				{
					System.out.print("["+int_i+"] --> ");
					Point_tmp = arrPoint_tree[int_i];
					while(Point_tmp != null)
					{
						System.out.print(Point_tmp.int_value+", ");
						Point_tmp = Point_tmp.Point_next;
					} // while
					System.out.println("");
				} // for
			} // if

			/* RECURSIVE METHOD TO FIND EULER TOUR */
			int_i = 0;
			System.out.println(" Searching for Euler Tour . . . IN PROGRESS!\n");
			do
			{
				Point_tour = new Point(int_i);
				Point_tour = check_point(arrPoint_tree, Point_tour, 0);
				int_i++;
			} while(Point_tour != null && int_i < int_points);

			System.out.println(" Searching for Euler Tour . . . COMPLETED!\n");

			/* OUTPUT */
			if(b_result)
			{
				System.out.print(" An Euler Tour _DOES_ exist for this graph!\n"+
				                 "  It is . . . ");
				print_tour(Point_tour);
			} // if
			else
				System.out.println(" An Euler Tour _DOESN'T_ exist for this graph!");
		} // try
		/* EXCEPTION HANDLING */
		catch(FileNotFoundException exception)
		{
			System.out.println(" FATAL EXCEPTION: Graph input file '"+args[0]+"' not found.");
			System.exit(-1);
		} // catch
		catch(IOException exception)
		{
			System.out.println(" FATAL EXCEPTION: File input problem.");
			System.exit(-1);
		} // catch
		catch(NumberFormatException exception)
		{
			System.out.println(" EXCEPTION: Invalid menu option. Please try again.");
		} // catch
	} // method main
} // class Prog2