// StudentMazeGenerator.java
//
// ICS 23 Project #1: Dark at the End of the Tunnel
// Coded by Alex Thornton Fall 2002


// The StudentMazeGenerator class is where you should implement your maze
// generation algorithm. Presently, it returns a newly-created maze in which
// every wall exists.

import java.util.Random;
import java.util.Set;
import java.util.HashSet;


public class StudentMazeGenerator implements MazeGenerator
{
    private Random random = new Random();
    
    private Set visited;
    
    protected Maze maze;
    protected MazeGeneratorListener lis;
    
    public Maze generateMaze(int width, int height, MazeGeneratorListener lis)
    {
        maze = MazeFactory.createMaze(width, height);
        (this.lis = lis).startingMazeGeneration(maze);
        visited = new HashSet();

        // generateMaze(new NNode(0, 0));

        initP();
	generateMaze( 0, 0 );

        return maze;
    }
    
    private int[][] perms;

    public void generateMaze(int x, int y) {
        // Aufbabencode hier einfuegen.

	visited.add( new NNode( x, y) );
        lis.mazeModified(maze);

	int actual = random.nextInt(24);
	// showPerm( actual );
	
	for(int i=0; i < 4; i++) {
  	    // System.out.println( "foo:" + i +
	    //			" perm: " + perms[actual][i] );
	    switch ( perms[actual][i] ) {
	    case 0:
	        if ( y != 0 &&
		     ! maze.canMoveNorthFrom( x, y ) &&
		     ! visited.contains( new NNode( x, y-1 ) ) ) {
		    maze.removeWallNorthOf( x, y );
		    generateMaze( x, y-1);
		}
	        break;
	    case 1:
	        if ( x != maze.getWidth()-1 &&
		     ! maze.canMoveEastFrom( x, y ) &&
		     ! visited.contains( new NNode( x+1, y ) ) ) {
		    maze.removeWallEastOf( x, y );
		    generateMaze( x+1, y);
		}
		break;
	    case 2:
		if ( y != maze.getHeight()-1 &&
		     ! maze.canMoveSouthFrom( x, y )  &&
		     ! visited.contains( new NNode( x, y+1 ) ) ) {
		    maze.removeWallSouthOf( x, y );
		    generateMaze( x, y+1);
		}
		break;
	    case 3:
		if ( x != 0 &&
		     ! maze.canMoveWestFrom( x, y ) &&
		     ! visited.contains( new NNode( x-1, y ) ) ) {
		    maze.removeWallWestOf( x, y );
		    generateMaze( x-1, y);
		}
		break;
	    }
	    
	}

    }
    

    private void printMaze(Maze maze, java.io.PrintStream output)
    {
        for (int x = 0; x < maze.getWidth(); x++) {
            output.print(" _");
        }
        output.println();
        
        for (int y = 0; y < maze.getHeight(); y++) {
            if (!maze.canMoveWestFrom(0, y)) {
                output.print('|');
            }
            for (int x = 0; x < maze.getWidth(); x++) {
                if (!maze.canMoveSouthFrom(x, y)) {
                    output.print('_');
                }
                else {
                    output.print(' ');
                }
                
                if (!maze.canMoveEastFrom(x, y)) {
                    output.print('|');
                }
                else {
                    output.print(' ');
                }
            }
            output.println();
        }
    }

    private int[][] permutation(int[] input){

	// The first permutation is the input itself.
	int[][] result = new int[1][input.length];
	result[0] = input;

	// The others are constructed by interchanging. Every element
	// of the array is interchanged with every element that is
	// "more right".

	for (int left = 0; left < input.length - 1; left++){
	    // How many permutation are yet constructed
	    // that are to be permuted to create new permutations.
	    int anz = result.length;

	    // Interchange the element "left" with every element
	    // on its right in the existing permutations, and append
	    // he new permutations to the array.
	    for (int right = left + 1; right < input.length; right++){
		for (int line = 0; line < anz; line++){
		    int[] nxt = new int[input.length];

		    // copy old permutation
		    for (int h = 0; h < nxt.length; h++)
			nxt[h] = result[line][h];

		    // interchange the elements "left" and "right"
		    nxt[left] = result[line][right];
		    nxt[right] = result[line][left];

		    // append new permutation
		    result = append(result, nxt);
		}
	    }
	}
	return result;
    }
    private int[][] append(int[][] r, int[] a){
	int[][] res = new int[r.length + 1][];
	for (int i = 0; i < res.length - 1; i++)
	    res[i] = r[i];
	res[res.length - 1] = a;
	return res;
    }
    
    private void initP() {
	int[] perm = new int[4];
	perm[0]=0;
	perm[1]=1;
	perm[2]=2;
	perm[3]=3;
	perms = permutation( perm );
	/*
	  for ( int x = 0; x < perms.length; x++ ) {
	  for ( int y = 0; y < perms[x].length; y++ )
	  System.out.print( perms[x][y] + " " );
	  System.out.println();
	  }
	*/
    }

    private void showPerm( int permno ) {
	// int permno = ((int) (java.lang.Math.random() * 24));
	System.out.print( "perm no " + permno + " " );
	for ( int y = 0; y < perms[permno].length; y++ )
	    System.out.print( perms[permno][y] + " " );
	System.out.println();
    }
    

}


class NNode {
    private int x;
    private int y;
    
    public NNode(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() { return x; }
    
    public int getY() { return y; }
    
    public boolean equals(Object o) {
        if (o == null || !(o instanceof NNode)) return false;
        
        NNode node = (NNode) o;
        
        return node.getX() == getX() && node.getY() == getY();
    }
    
    
    public int hashCode() {
        return x + 100 * y;
    }
    
    
    public String toString() {
        return "Node: (" + x + ", " + y + ")";
    }
}