import java.util.*;

/**
 * Class Springer
 *
 * @author Philipp Bolliger <br>
 * Informatik II - FS2009 <br>
 * Uebungsserie 11 <br>
 */
public class Springer {


	/* ---------------------------------------
     Uebungsserie 11 - Aufgabe 4a
     --------------------------------------- */
	/**
	 * The method positions() computes all positions that can be reached on the board
	 * in n moves starting from positions "start". The set "visited" stores all positions
	 * that have already been visited. <br>
	 *
	 * More information about the interface "Set" is available at:<br>
	 * http://java.sun.com/j2se/1.4.2/docs/api/index.html.<br>
	 *
	 * @param start Start position
	 * @param n Number of moves
	 * @param visited All positions visited sofar
	 **/
	static void positions( Pos start, int n, Set visited ) {
		//break condition?
		//if( .... ) return;

		//recursive call
		//positions( ...., n-1, visited );
	}


	// ---------------------------------------
	// Uebungsserie 11 - Aufgabe 4c
	// ---------------------------------------
	/**
	 * The method path() checks if there exists a completion for the path
	 * stored in "sofar" that allows the knight to visit every single field
	 * of the board exactly once.
	 * All visited positions are stored in the Vector "sofar".
	 * The last visited position can be retrieved through a call to the
	 * Vector Class method lastElement(): <br>
	 *
	 * "(Pos)sofar.lastElement();" <br>
	 *
	 * More information about the class "Vector" is available at:<br>
	 * http://java.sun.com/j2se/1.4.2/docs/api/index.html.
	 *
	 * @param sofar All positions visited sofar
	 * @param next Next position to visit
	 * @return True f a valid path including "sofar" is found, false otherwise
	 **/
	static boolean path( Vector sofar, Pos next ) {
		//example:
		//
		//sofar.add(...)
		//....
		//sofar.remove(...)
		//
		//path(.....)

		return false;
	}



	// ---------------------------------------
	// Uebungsserie 11 - Aufgabe 4b und 4d
	// ---------------------------------------
	public static void main( String[] args ) {
		/* The instruction Pos.setMax(8) forces
		 * the width and height of the board to be 8.
		 * Valid positions have therefore x and y between 1 and 8
		 */
		Pos.setMax( 8 );

		/* Creates an empty set. The interface Set and the class TreeSet
		 * part of the java.util packcage
		 * (see http://java.sun.com/j2se/1.4.2/docs/api/index.html)
		 */
		Set visited = new TreeSet();

		/* ---------------------------------------
         Uebungsserie 11 - Aufgabe 4b [Pos(1,4)]
         --------------------------------------- */

		/* Startposition (4,1) bereits besucht: */
		Pos initial = new Pos(4,1);
		visited.add( initial );
		int hops = 2;

		/* Add all reachable positions to the positions set */
		//positions( ..... );

		System.out.println( "Within " + hops + " hops starting from position " + initial.toString() + " "
				+ visited.size() + " positions (out of "
				+ Pos.boardPositions() + ") have been found");
		System.out.println( visited );
		System.out.println( "----------------------------------------- " );


		/* ---------------------------------------
         Uebungsserie 11 - Aufgabe 4b [Pos(2,1)]
         --------------------------------------- */

		/*re-initialize the set of visited positions */
		visited = new TreeSet();
		initial = new Pos(2,1);
		visited.add( initial );

		/* Add all reachable positions to the positions set */
		//positions( ..... );

		System.out.println( "Within " + hops + " hops starting from position " + initial.toString() + " "
				+ visited.size() + " positions (out of "
				+ Pos.boardPositions() + ") have been found");
		System.out.println( visited );
		System.out.println( "----------------------------------------- " );


		/* ---------------------------------------
         Uebungsserie 11 - Aufgabe 4d
         --------------------------------------- */

		/* Force width and eight of the board to be 5 */
		Pos.setMax( 5 );

		/* Create a Vector (Class Vector is part of the java.util package) */
		Vector myPath = new Vector();
		initial = new Pos(1,3);
		if(path( myPath, initial )) {
			// if there exists a valid path
			System.out.println("Starting from position " + initial.toString()
					+ ", the following path has been found: ");
			System.out.println(  myPath );
			System.out.println( "----------------------------------------- " );
		}
		else {
			System.out.println("No path found (starting from position " + initial.toString() + ")");

		}
	} // end main()




} // end class Springer