import java.awt.geom.Point2D;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Stack;
/**
    implements the virtual representation of the physical world
    responsible for the 3 functions required by graph, and any other functions accessing data regarding the layout of the world
**/
public class Map
{
//    int map[][];
    float map[][];
    int w, h;
    float maxDanger;
    Stack stack;
    /**
        Constructor
        @param w width of the world grid
        @param h height of the world grid
    **/
    public Map( int w, int h )
    {
		stack = new Stack();
		this.w = w;
		this.h = h;
		//map = new int[w][h];
        map = new float[w][h];
    }
    
    public String toString(){
    String answer = new String();
	for( int i = 0; i < w; i ++ ){
		 for( int j = 0; j < h; j ++ ){
			  answer += map[i][j];
			  }
		 answer += "\n";
		 }
    return answer;
    }
    /**
        constructs a new radar 
        does NOT update the map
        @param x x position of the radar
        @param y position of the radar
        @param r radius of the radar
        @param s strength of the radar
    **/
    public void addRadar( Radar newRadar )
    {
        stack.push( newRadar );
    }

    
    /**
        constructs a radar randomly
        does NOT update the map
    **/
    public void genRandomRadar()
    {
		float x = (float)Math.random() * (float)w;
		float y = (float)Math.random() * (float)h;
		float r = (float)Math.random() * (float)w/5 + (float)w/20;
		float s = (float)Math.random() * (float)5 + (float)1;
   //     addRadar( x,y,r,s );
	}

    /**
        updates the map for new radar data
        runs in O( w*h*numRadar )
    **/
	public void update()
	{
		for ( int i =0 ; i < w; i ++ )
			for( int j = 0; j < h; j ++ ){
				map[i][j] = Const.ambientDanger();
				for( int k = 0; k < stack.size(); k ++ ){
					map[i][j] += ((Radar)stack.elementAt(k)).dangerTo(i,j);
                    if( map[i][j] > maxDanger )
                        maxDanger = map[i][j];
                }
			}
	}

    /**
        Estimates the danger from traveling between two locations
        this is the main function that controls search behavior
        the way it is estimated depends on Const.distanceEstimateType
        the final answer is multiplied by Const.creativity
        estimate types :
            0 = mearly the distance between the two points
            1 = an optomized estimated of 2
            2 = the actual danger from going straight from a to b
        @param a start location
        @param b goal location
        @return the danger estimated
    **/
    float pathCostEstimate( Location a, Location b )
    {
   //     return (float) Math.sqrt( Math.pow( a.x - b.x, 2 ) + Math.pow( a.y -b.y,2 ));
    
        //System.out.println( "regular : " + dangerLine( a,b ) );
        //System.out.println( "segmented : " + segmentedDangerLine( a,b, 8 ) );
        switch( Const.distanceEstimateType() ){
            case( 0 ):
                return a.distanceTo( b ) * Const.creativity();
            case( 1 ) :
                return segmentedDangerLine( a,b,Const.distanceLineSegments() ) * Const.creativity();
            case( 2 ) :
                return dangerLine( a, b ) * Const.creativity();
        }
        return 0f;
    }

    /**
        returns the cost of movnig from location a to location b
        currently the dangerLine between them
    **/
        
    float traverseCost( Location a, Location b )
    {
//        return (float) Math.sqrt( Math.pow( a.x - b.x, 2 ) + Math.pow( a.y -b.y,2 ));
        return dangerLine( a, b);
    //    return map[a.x][a.y] + map[b.x][b.y];
    }

    /**
        required for a*
        returns the neighbors to a location in space
        currently just the 8 points around it on the grid.
        A more complicated representation of space would require work here
    **/
    LinkedList findNeighbors( Location l )
    {
        LinkedList a = new LinkedList();
        for( int i = -1; i <= 1; i ++ )
            for( int j = -1; j <= 1; j ++ )
                if(( l.x + i >= 0) &&
                   ( l.y + j >= 0) &&
                   ( l.x + i < w) &&
                   ( l.y + j < h) &&
                   !(i == 0 && j == 0) )
                    {
                        Location b = new Location( l.x + i, l.y + j );
                        a.add( b );
                    }
        return a;
    }

    /**
        returns the danger at a set point, minus ambient danger
        currently used to do the display
    **/
    public float dangerAt( int x, int y ) {
        return map[x][y] - Const.ambientDanger();
    }

    /**
        estimates dangerLine, by segementing the line, checking danger at those points and averaging that danger over the whole of the line
        runs much faster then dangerLine, at abuot 90% accuracy
        @param a the start location
        @param b the goal location
        @param segments the number of segments the lins i broke into, ~ to accuracy / speed.
        @return an estimate of hte danger between the two points
    **/
    public float segmentedDangerLine( Location a, Location b, int segments )
    {
        if( a.equals(b)) return 0.0f;
        float stepx = ( b.x - a.x ) / (float) segments;
        float stepy = ( b.y - a.y ) / (float) segments;
        float length = (float) Point2D.distance( a.x, a.y, b.x, b.y );
        float danger = 0;
        for( int i = 0; i <= segments; i ++ )
            danger += dangerAt(         a.x + stepx * i,
                                        a.y + stepy * i );
        return ( danger / segments ) * length;
    }
        
    /**
        returns the dangersum along a line between locations.
        requires a lot of processing as it does anti aliased line math between the two points
        @param a start location
        @param b stop location
        @return the correct danger between the two points
    **/
        
    public float dangerLine( Location a, Location b)
    {
        if( a.equals( b ) ) return 0.0f;
        int startx = a.x;
        int starty = a.y;
        int ratiox = b.x - a.x;
        int ratioy = b.y - a.y;
        int length = (int) Math.ceil( Point2D.distance( a.x, a.y, b.x, b.y ) );  //ceiling discourages diagnoal moves
        float dangerSum = 0; 
        for( int i = 0; i <= length; i ++ ) {
            float ipol = ((float) i ) / ((float) length );
            dangerSum += dangerAt( startx + ipol*ratiox, starty + ipol*ratioy );
        }
        return dangerSum;
    }

    /**
        calculates the danger at a location 
        antialiases the discrete voxel danger space to determine what the danger would be in a continuous space at a location.
        @param x the x location
        @param y the y location
        @return the danger at a point
    **/
    public float dangerAt( float x, float y )
    {
        float x1 = x - (float) Math.floor( x );
        float y1 = y - (float) Math.floor( y );
        float x0 = 1 - x1;
        float y0 = 1 - y1;
        int xi = (int) Math.floor( x );
        int yi = (int) Math.floor( y );
        float answer = 0;
        answer += map[xi+0][yi+0] * x0*y0;
        if( y1 > 0.0f )
            answer += map[xi+0][yi+1] * x0*y1;
        if( x1 > 0.0f )
        answer += map[xi+1][yi+0] * x1*y0;
        if( x1 > 0.0f && y1 > 0.0f )
            answer += map[xi+1][yi+1] * x1*y1;
        //if( answer > 1000 )
          //  System.out.print( x + "\t" + y + "\t" + x0 + "\t" + y0 + "\t" + x1 + "\t" + y1 + "\t" + xi + "\t" + yi + "\t" + answer );
        return answer;
    }

    /**
        @return the danger at the most dangeruos spot
    **/
    public float maximumDanger() {
        return maxDanger;
    }

    /**
        smooths a route to be more effecient and occupy less wp's
        uses smootherBias to determine when to remove points from the route
    **/
        
    public LinkedList smoothRoute( LinkedList route )
    {
        ListIterator it = route.listIterator(0);
        LinkedList newRoute = new LinkedList();
        Location a = (Location) it.next();
        Location b = (Location) it.next();
        Location c = (Location) it.next();
        newRoute.add( a );
        while( it.hasNext() ) {
            float dangerFirst = dangerLine( a,b );
            float dangerSecond = dangerLine( b,c );
            float dangerBoth = dangerLine( a,c );
        //    System.out.println( a + " " + b + " " + c + " " + dangerFirst + " " + dangerSecond + " " + dangerBoth );
            if( dangerLine(a,b) + dangerLine(b,c) > dangerLine(a,c)*Const.smootherBias() ) //better to cut 
            {
                b = c;
                c = (Location) it.next();
            }
            else
            {
                a = b;
                b = c;
                c = (Location) it.next();
                newRoute.add( a );
            }
        }
        newRoute.add( c );
        return newRoute;
    }

    /**
        produces the sum danger from passing through all the wp's in a route
    **/
    public float dangerOnRoute( LinkedList route )
    {
        float answer = 0f;
        for( int i = 1; i < route.size(); i ++) {
            Location a = (Location) route.get( i );
            Location b = (Location) route.get( i-1 );
            answer += dangerLine( a,b );
        }
        return answer;
    }
}