/*
PROGRAM NAME:   Program #2 - Recursion
PROGRAMMER:     Daniel Yim
CLASS:          CSC 202.002
INSTRUCTOR:     Dr. Robert G. Strader
DATE DEVELOPED: January 30, 2008
DATE COMPLETED: January 30, 2008
REFERENCES:     Computer Science - 
                    Introduction to Java Programming
                    Y. Daniel Liang

STATEMENT:
    This program will recursively map out paths in a given square grid that is no larger than
    10 units and will follow a north-east pattern, which means traveling only north or east
    every move.

    The data pro vided will be:

                5
                3 0
                1 3

    From the data provided, the program reads that a square grid of 5 should be prepared
    and the starting coordinate is (3,0) and the end coordinate is (1,3). The program will
    then compute recursively every path that is possible from point A to point B. If no
    path is found, then an error message will be computed.

SAMPLE OUTPUT:


	5
	3 0
	1 3
	
	
	             0,0  0,1  0,2  0,3  0,4
	             1,0  1,1  1,2 [1,3] 1,4
	             2,0  2,1  2,2  2,3  2,4
	            [3,0] 3,1  3,2  3,3  3,4
	             4,0  4,1  4,2  4,3  4,4
	
	
	    Paths:  (3,0)(2,0)(1,0)(1,1)(1,2)(1,3)
	            (3,0)(2,0)(2,1)(1,1)(1,2)(1,3)
	            (3,0)(2,0)(2,1)(2,2)(1,2)(1,3)
	            (3,0)(2,0)(2,1)(2,2)(2,3)(1,3)
	            (3,0)(3,1)(2,1)(1,1)(1,2)(1,3)
	            (3,0)(3,1)(2,1)(2,2)(1,2)(1,3)
	            (3,0)(3,1)(2,1)(2,2)(2,3)(1,3)
	            (3,0)(3,1)(3,2)(2,2)(1,2)(1,3)
	            (3,0)(3,1)(3,2)(2,2)(2,3)(1,3)
	            (3,0)(3,1)(3,2)(3,3)(2,3)(1,3)
	
	            10 paths found!


SAMPLE OUTPUT WITH ERRONEOUS DATA:

	5
	3 4
	1 3
	
	
	            0,0  0,1  0,2  0,3  0,4
	            1,0  1,1  1,2 [1,3] 1,4
	            2,0  2,1  2,2  2,3  2,4
	            3,0  3,1  3,2  3,3 [3,4]
	            4,0  4,1  4,2  4,3  4,4
	
	
	    Paths:  NONE
	
	            ERROR: No valid paths were found!


METHODS USED: 
    enumPaths(int[] startCoords, int endCoords[], ArrayList pathsFound, ArrayList 
        pathCoordinatesFound, int sizeMax)
                This method assists the first call of the recursive method findPath,
                organizes the ArrayList used to store paths and, if available, outputs
                the paths found or outputs an error message.
    findPaths(int currentXPosition, int currentYPosition, int stopX, int stopY, ArrayList
        pathFound, ArrayList pathCoordinatesFOund, int sizeMax)
                findPaths evaluates and stores coordinates to the right or above a given
                coordinate, ultimately printing a path if one is found moving only north
                and east between a given point A to point B.
    printArray(int[] startCoords, int[] endCoords, int sizeMax)
                The method outputs the data provided by the file and also a two dimensional
                array to represent the coordinates in question.

DICTIONARY OF VARIABLES:
    public class Program1
        boolean debug
            A switch to output every action to aid the development process
        ArrayList debugList
            A list of paths that have been successful used for development
    public static main void
        final int SIZE
            A constant that reflects the header value read from the data file
        ArrayList<String> path
            A running list of coordinates used to store paths by the method findPaths
    public static void enumPaths
        int currentX
            Retrieves an array value and places it into a passable integer
        int currentY
            Retrieves an array value and places it into a passable integer
        int numPaths
            Number of paths found
        ArrayList<String> tempAL
            A temporary ArrayList to clone ArrayList paths and organize the entries of
            coordinates into entries of paths (a set of coordinates)
        String tempPath
            A temporary String used to store values read from ArrayList tempAL
    public static void printArray
        String[][] arr
           2D array used to draw a list of coordinates to a specified size
--------------------------------------------------------------------------------
*/

import java.util.*;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
    
public class Program2
{
            // Switch to activate the many debug statements in this program
    private static boolean debug = false;

// ============================= method main ===================================
    public static void main (String[] args)
    {
        try
        {
            FileInputStream dataFile 
                = new FileInputStream("prog2.dat");     // Initialize the file
            Scanner in = new Scanner(dataFile);         // Initialize the scanner
            final int SIZE = in.nextInt();              // Read in the header value & set constant
            int[] start = new int[2];                   // Initializes the starting coordinate
            int[] end = new int[2];                     // Initializes the ending coordinate
            ArrayList<String> pathCoords = new ArrayList<String>();   // Initialize the array to store
                                                                      // path coodinates
            ArrayList<String> paths = new ArrayList<String>();   // Initialize the array to store
                                                                 // paths
            start[0] = in.nextInt();        // Reads the X coordinate of the starting point
            start[1] = in.nextInt();        // Reads the Y coordinate of the starting point
            end[0] = in.nextInt();          // Reads the X coordinate of the ending point
            end[1] = in.nextInt();          // Reads the Y coordinate of the ending point
            
            printArray(start, end, SIZE);       // Print the original array/data
            enumPaths(start, end, pathCoords, paths, SIZE);  // Calls the helper method
            
            in.close();                         // Close the file
        }
        catch(FileNotFoundException e)
        {
                    // Display an error if the data file cannot be found
            System.out.println("/////////// ERROR! ///////////");
            System.out.println("The data file cannot be found!");
        }

                // Add lines to the end of the program.
        System.out.println ("\n");
                // Returns to the OS
        return;
    }   // End of public static void main
    
    
// ========================== method enumPaths ================================
/*
METHOD DESCRIPTION:
    This method assists the first call of the recursive method findPath, organizes
    the ArrayList used to store paths and, if available, outputs the paths found
    or outputs an error message.
*/
    public static void enumPaths(int[] start, int end[], ArrayList pathCoords, ArrayList paths, int size)
    {
        int currentX = start[0];
        int currentY = start[1];
                // Number of paths available
        int numPaths = 0;
                // A temporary ArrayList to store coordinates
        ArrayList<String> tempAL = new ArrayList<String>();
                // A temporary String used to couple coordinates into complete paths
        String tempPath = "";

                // Outputs a header
        System.out.print("    Paths:  ");
                // Starts the recursive call
        findPaths(currentX, currentY, end[0], end[1], pathCoords, paths, size);

                // Copies the set of coordinates into the temporary ArrayList
        tempAL.addAll(paths);
                // Clears the paths ArrayList prior to adding items
        paths.clear();

                // Iterator reads from the temporary ArrayList
        Iterator itTemp = tempAL.iterator();
        while (itTemp.hasNext())
        {
                    // Read value is stored in a temporary variable
            Object temp = itTemp.next();
                    // If the value read is the special symbol for a separate path...
            if(temp == "/")
            {
                        // Add what was logged in temporary String path
                paths.add(tempPath);
                        // Clear the String for a new path
                tempPath = "";
            }
            else
                        // Add to the end of the String
                tempPath = tempPath + temp;
        }

        if(debug) System.out.println("\nCONTENTS OF ARRAYLIST PATHS: ");

        Iterator itPaths = paths.iterator();
        while (itPaths.hasNext())
        {
                    // Output a blankspace (tab) if not the first line
            if(numPaths != 0) System.out.print("            ");
                    // Output the next line in the ArrayList
            System.out.println(itPaths.next());
                    // Increment the number of paths
            numPaths++;
        }
                // Check if no possible path was found and print an error if so
        if(numPaths == 0)
            System.out.println("NONE\n\n            ERROR: No valid paths were found!");
        else
                    // Output the number of paths found
            System.out.printf("\n           %d paths found!", numPaths);
    }           // End of public static void enumPaths

    
// ========================== method findPaths ================================
/*
METHOD DESCRIPTION:
    findPaths evaluates and stores coordinates to the right or above a given
    coordinate, ultimately printing a path if one is found moving only north
    and east between a given point A to point B.
*/
    public static void findPaths(int currentX, int currentY, int stopX, int stopY, ArrayList pathCoords,
        ArrayList paths, int size)
    {
        if(debug) System.out.println("EVALUATING POINT: (" + currentX + "," + currentY + ")");
                
                // Base case: should the current coordinate be the same as the
                // specified stopping coordinate, recursion should be finished
                // the method should print the path used.
        if(currentX == stopX && currentY == stopY)
        {
            if(debug) System.out.println("FINISHED PATHING\n");
                    // Copy the array before it is erased
            paths.addAll(pathCoords);
                    // Manually add the last coordinate
            paths.add("(" + stopX + "," + stopY + ")");
                    // Add a symbol to denote a new path
            paths.add("/");
            return;
        }
        else 
        {           // Adds the point to the ArrayList 
            if(debug) System.out.println("POINT ADDED: (" + currentX + "," + currentY + ")");
            pathCoords.add("(" + currentX + "," + currentY + ")");
        }
            
        if(currentX > stopX)       // North recursive movement
            findPaths(currentX-1, currentY, stopX, stopY, pathCoords, paths, size);
        if(currentY < stopY)       // East recursive movement
            findPaths(currentX, currentY+1, stopX, stopY, pathCoords, paths, size);
        
        if (debug) System.out.println("REMOVED: " + pathCoords.get(pathCoords.size()-1));
                // As the recursive pattern finishes, the coordinate that is no longer
                // used removes itself from the list.
        pathCoords.remove(pathCoords.size()-1);
        return;
                
    }           // End of public static void findPaths


// ============================= method printArray =============================
/*
METHOD DESCRIPTION:
    The method outputs the data provided by the file and also a two dimensional
                array to represent the coordinates in question.
*/     
    public static void printArray(int[] start, int[] end, int s)
    {
        String[][] arr = new String[s][s];    // Initialize the 2D Array
                // Populates the array
        for(int r = 0; r < s; r++)
            for(int c = 0; c < s; c++)
                arr[r][c] = r + "," + c;
        
                // Output the data given from file
        System.out.println("\f\n\n" + s);
        System.out.println(start[0] + " " + start[1]);
        System.out.println(end[0] + " " + end[1]);
        System.out.println("\n");

                // Reads from the array and prints according to the size given
        for(int r = 0; r < s; r++)
        {
            System.out.print("           ");
            for(int c = 0; c < s; c++)
                            // Checks to see if the coordinate about to be printed
                            // is a starting or ending coordinate
                    if((r == start[0] && c == start[1]) || (r == end[0] && c == end[1]))
                            // If true, printArray places indicators on the coords
                        System.out.print("[" + arr[r][c] + "]");
                    else System.out.print(" "+ arr[r][c] + " ");
            System.out.println();
        }
        System.out.println("\n");
    }       // End of public static void printArray

}   // End of public class Program2