package algorithmrepository.contouring;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import algorithmrepository.Algorithms;

/** Functions for loading and handling the first wall 
 *
 * Boundary Intersection search
 *  The specified grid is created and the list of boundary segments
 *  in (even partly) each cell are stored in a list associated with 
 *  that cell. The routine isCrossingBoundary() will use this to quickly 
 *  test for  intersections of only near by boundary segments. It
 *  is intended that most called to isCrossingWall() will return immediately
 *  as no boundary segments are in or cross that cell.
 * 
 * @author oliford <codes(at)oliford.co.uk>
 *
 */
public class OptimisedBoundaryHandler {

    double boundX[], boundY[]; //coordinates of boundary segments
    int nBound;

    int nx,ny; /* grid over which we store which segments are in a grid square */
    double x0, x1, y0, y1;
    double dx,dy;
    int indecies[][];

    int segmentFlags[]; // grid of flags giving info about segments contact with first wall...    
    private final int FLAG_CONTACT =    1; /* Segment is crosses boundary at least once */
    private final int FLAG_INSIDE =     2; /* Segment is entirely inside boundary */
    private final int FLAG_MASK =       3;
    /** Vertical segment bits location (i,j)->(i+1,j) */
    private final int FLAG_VERT =    0;
    /** Horizontal segment bits location (i,j)->(i,j+1) */
    private final int FLAG_HORZ =    8;

    /** Load boundary definition from file. Format is: <BR>
     * n<BR>
     * x0, y0<BR>
     * x1, y1<BR>
     * ...<BR>
     * xn, yn<BR>
     */
    private void loadBoundaryTestFile(String fileName){
        try {
            BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(fileName)));
            String line;

            do line = reader.readLine(); while(line.matches("\\s*//.*")); //next non-comment line
            /* '\\' is escaped '\';  '\s' means "space or tab etc"; "*" means "0 or more of previous"; "." means "anything" */

            nBound = Integer.parseInt(line);	    	    
            boundX = new double[nBound];
            boundY = new double[nBound];

            for(int i=0; i<nBound; i++){
                do line = reader.readLine(); while(line.matches("\\s*//.*")); //next non-comment line

                String parts[] = line.split("[\\s,]+"); // [] means "any of these"; '+' means "1 or more of previous"
                boundX[i] = Double.parseDouble(parts[0]);
                boundY[i] = Double.parseDouble(parts[1]);
            }


        }catch (IOException e) {
            throw new RuntimeException("Error interpreting flush style first wall:" + e.getMessage());
        }

    }

    /** If first and last point of the boundary arn't the same, add the first pointto the end */ 
    private void assureBoundaryConnects(){
        /* if the last point isn't the same as the first, make is so */
        if(boundX[nBound-1] != boundX[0] || boundY[nBound-1] != boundY[0]){
            double boundX2[] = new double[nBound+1]; System.arraycopy(boundX, 0, boundX2, 0, nBound);
            double boundY2[] = new double[nBound+1]; System.arraycopy(boundY, 0, boundY2, 0, nBound);           
            boundX2[nBound] = boundX2[0]; 
            boundY2[nBound] = boundY2[0];
            nBound++;
            boundX = boundX2;
            boundY = boundY2;
            //System.out.println("Closed boundary with ("+
            //boundX[nBound-1]+", "+boundY[nBound-1]+")-("+boundX[0]+", "+boundY[0]+")");
        }
    }

    /** Create an optimised boundary handler with the given grid and boundary
     * loaded from a text file containing: <BR>
     * n<BR>
     * x0, y0<BR>
     * x1, y1<BR>
     * ...<BR>
     * xn, yn<BR>
     */
    public OptimisedBoundaryHandler(String fileName,
                                    double x0, double x1, int nx,
                                    double y0, double y1, int ny){
        loadBoundaryTestFile(fileName);
        assureBoundaryConnects();
        initGrid(x0, x1, nx, y0, y1, ny);
    }

    /** Create an optimised boundary handler with the given boundary and grid */
    public OptimisedBoundaryHandler(double boundX[], double boundY[],
                                    double x0, double x1, int nx,
                                    double y0, double y1, int ny){
        this.boundX = boundX;
        this.boundY = boundY;
        this.nBound = boundX.length;	    
        assureBoundaryConnects();	    
        initGrid(x0, x1, nx, y0, y1, ny);
    }

    /** Create given grid and setup boundary element indicies array */
    private void initGrid(double x0, double x1, int nx,
        double y0, double y1, int ny) {


        int nIdx;
        int tmp[] = new int[nBound]; /* maximum number of indicies we might store in one entry is all of them */

        this.x0 = x0; this.x1 = x1; this.nx = nx;
        this.y0 = y0; this.y1 = y1; this.ny = ny;
        this.dx = (x1 - x0) / ((double)nx - 1.0);
        this.dy = (y1 - y0) / ((double)ny - 1.0);

        indecies = new int[nx * ny][];
        segmentFlags = new int[(nx+1) * (ny+1)]; //there are n+1 segements in each direction

        /* for each grid square ... */
        for(int i=0; i < ny; i++){
            double gridY0, gridY1;
            gridY0 = y0 + i * dy;
            gridY1 = gridY0 + dy;

            for(int j=0; j < nx; j++){
                double gridX0, gridX1;
                gridX0 = x0 + j * dx;
                gridX1 = gridX0 + dx;

                nIdx = 0;

                for(int k=0; k < (nBound-1); k++){ /* for each first wall segment */
                    //find out what segments of this grid square it hits
                    boolean hitTop = Algorithms.intersectionTwoLineSegments2D( gridX0, gridY0,  gridX1, gridY0,  
                                        boundX[k], boundY[k],  boundX[k+1], boundY[k+1], null);
                    boolean hitLeft = Algorithms.intersectionTwoLineSegments2D( gridX0, gridY0,  gridX0, gridY1,
                                        boundX[k], boundY[k],  boundX[k+1], boundY[k+1], null);
                    boolean hitRight = Algorithms.intersectionTwoLineSegments2D( gridX1, gridY0,  gridX1, gridY1,
                                        boundX[k], boundY[k],  boundX[k+1], boundY[k+1], null);
                    boolean hitBottom = Algorithms.intersectionTwoLineSegments2D( gridX0, gridY1,  gridX1, gridY1,
                                        boundX[k], boundY[k],  boundX[k+1], boundY[k+1], null);

                    /* For the 'contour from boundary' support in BoundedContouring which is not yet implemented.
                    if(hitTop) segmentFlags[i*(nx+1)+j] |= (FLAG_CONTACT << FLAG_HORZ); 
                    if(hitLeft) segmentFlags[i*(nx+1)+j] |= (FLAG_CONTACT << FLAG_VERT);
                    //catch bottom and right on last grid iteration (there are n+1 segments)
                    if(i == (ny-1) && hitBottom)  segmentFlags[(i+1)*(nx+1)+j] |= (FLAG_CONTACT << FLAG_VERT);
                    if(j == (nx-1) && hitRight)  segmentFlags[i*nx+(j+1)] |= (FLAG_CONTACT << FLAG_VERT);
                    */

                    /* if this element intersects any of the edges of this square, 
                     * (or if it is entirely inside the square), we need to add it to the square's cache */
                    if( (boundX[k] > gridX0 && boundX[k] < gridX1 && boundY[k] > gridY0 && boundY[k] < gridY1) ||
                        hitTop || hitLeft || hitRight || hitBottom){
                        tmp[nIdx++] = k; /* if so, add this index to this square's intersecting segments array */
                    }
                }

                /* If there were any contacts, alloc the array for this grid square and copy the indecies in */
                if(nIdx > 0){
                    indecies[i*nx+j] = new int[nIdx];
                    System.arraycopy(tmp, 0, indecies[i*nx+j], 0, nIdx);
                }else
                    indecies[i*nx+j] = null; /* otherwise mark it empty */

            }
        }
        
        // For the 'contour from boundary' support in BoundedContouring which is not yet implemented.
        //findIfSegementsAreEnclosed();
        //calcGridBoundaryApprox();

    }

    /** initGrid will have marked if the segements are in contact with the first wall. For all those
     * that arn't, find out whether they are completely inside of completely outside.
     * For the 'contour from boundary' support in BoundedContouring which is not yet implemented.
     */
    private void findIfSegementsAreEnclosed(){

        //define a point that is definately off the grid
        double outsideX = x0 - dx;
        double outsideY = y0 - dy;

        for(int i=0; i <= ny; i++){
            double gridY0, gridY1;
            gridY0 = y0 + i * dy;
            gridY1 = gridY0 + dy;

            for(int j=0; j <= nx; j++){
                double gridX0, gridX1;
                gridX0 = x0 + j * dx;
                gridX1 = gridX0 + dx;

                /* count how many times a line from the common vertex to the outside 
                 * point crosses the boundary. We can use the optimised search since 
                 * initGrid has to ben done by here. 
                 */
                int intersectCount = countCrossings(gridX0, gridY0, outsideX, outsideY, null, Integer.MAX_VALUE);
                boolean inside = (intersectCount % 2) > 0;

                /* vertical segment first */
                if( ((segmentFlags[i*(nx+1)+j] >> FLAG_VERT) & FLAG_MASK) != FLAG_CONTACT ){
                    //if it isn't in contact
                    if(inside) //and is inside, mark it so
                        segmentFlags[i*(nx+1)+j] |= (FLAG_INSIDE << FLAG_VERT); 
                }

                /* horizontal segment */
                if( ((segmentFlags[i*(nx+1)+j] >> FLAG_HORZ) & FLAG_MASK) != FLAG_CONTACT ){
                    //if it isn't in contact
                    if(inside) //and is inside, mark it so
                        segmentFlags[i*(nx+1)+j] |= (FLAG_INSIDE << FLAG_HORZ); 
                }

            }
        }
    }
    
    /** Finds the series of grid points which make up a boundary just outside the real boundary 
     *  For the 'contour from boundary' support in BoundedContouring which is not yet implemented.
     *  */  
    private void calcGridBoundaryApprox(){
        //First, make a list of verticies which have at least two seg outside
    }

    /** Find if the line (r0,z0)-(r1,z1) crosses any boundary element and return the contact point.
     * Only grid squares that either(r0,z0) or (r1,z1) lie inside or on the edge of will be tested.
     */
    public final boolean isCrossing(double lineX0, double lineY0, double lineX1, double lineY1, double hitCoord[]){
        return (countCrossings(lineX0, lineY0, lineX1, lineY1, hitCoord, 1) > 0);
    }
    
    
    public final int countCrossingsBruteForce(double x, double y){
        
        double x2 = x0 - 5 * (x1 - x0);
        double y2 = y0 - 5 * (y1 - y0);
        int crossings = 0;
        for(int i=0;i<(nBound-1);i++){
            if( Algorithms.intersectionTwoLineSegments2D(x, y, x2, y2, boundX[i], boundY[i], boundX[i+1], boundY[i+1], null))
                crossings++;
        }
        
        return crossings;
    }
    
    /** Find how many times the line (r0,z0)-(r1,z1) crosses any boundary element and return the last contact point.
     * Only grid squares that either(r0,z0) or (r1,z1) lie inside or on the edge of will be tested.
     */
    public final int countCrossings(double x, double y){
        return countCrossings(x0 - 5 * (x1 - x0), y0 - 5 * (y1 - y0), x, y, null, Integer.MAX_VALUE);
    }
    
    /** Finds if the point (x,y) is inside the boundary. */
    public final boolean isInside(double x, double y){ 
        //check number of times the boundary crosses a line from this point to well outside the grid.
        //This assumes the boundary doesn't leave the grid boundary
        return ( (countCrossings(x0 - 5 * (x1 - x0), y0 - 5 * (y1 - y0), x, y,
                                    null, Integer.MAX_VALUE) % 2) > 0);
    }
 
    /** Find how many times the line (r0,z0)-(r1,z1) crosses any boundary element and return the last contact point.
     * Only grid squares that either(r0,z0) or (r1,z1) lie inside or on the edge of will be tested.
     */
    public final int countCrossings(double lineX0, double lineY0, double lineX1, double lineY1, double hitCoord[], int maxCount){
        int i,j;
        int k, idx;
        int count = 0;

        if(false){
            /*The slow way of doing it, for speed comparison */
            for(k=0;k<(nBound-1);k++)
                if( Algorithms.intersectionTwoLineSegments2D( boundX[k], boundY[k], boundX[k+1], boundY[k+1], lineX0, lineY0, lineX1, lineY1, hitCoord) ){
                    count++;
                    if(count >= maxCount)
                        return count;
                }

            return count;
        }

        int box[] = getBoxEnclosing(lineX0, lineY0, lineX1, lineY1);
        if(box == null)
            return 0;
        
        
        boolean checked[] = new boolean[nBound];

        /* for any cell in the box, check against first wall segments near that cell. */
        for(i = box[0]; i <= box[1]; i++)
            for(j = box[2]; j <= box[3]; j++)
                if( indecies[i*nx+j] != null)
                    for(k = 0; k < indecies[i*nx+j].length; k++){
                        idx = indecies[i*nx+j][k];
                        
                        if(checked[idx])continue; //already done from another grid sqaure
                        
                        if(hitCoord == null) hitCoord = new double[2];
                        if( Algorithms.intersectionTwoLineSegments2D( boundX[idx], boundY[idx], boundX[idx+1], boundY[idx+1], lineX0, lineY0, lineX1, lineY1, hitCoord) ){
                            count++;
                              if(count >= maxCount)
                                return count;
                        }
                        checked[idx] = true;
                    }

        return count;
    }

    /** Returns { i0, i1, j0, j1 } indecies of the rectangle of grid points totally enclosing
     * the given line 
     *  
     * @return
     */
    public final int[] getBoxEnclosing(double lineX0, double lineY0, double lineX1, double lineY1){
        int i,j,k,i0,i1,j0,j1;
        /* calc the box of cells that definitely includes the whole line (probably sub-optimal)*/
        i = (int)((lineY0 - y0) / dy);
        k = (int)((lineY1 - y0) / dy);
        if(i < k){ i0 = i; i1 = k; } else { i0 = k; i1 = i; }

        j = (int)((lineX0 - x0) / dx);
        k = (int)((lineX1 - x0) / dx);
        if(j < k){ j0 = j; j1 = k; } else { j0 = k; j1 = j; }

        if(i0 >= ny || i1 < 0 || j0 >= nx || j1 < 0)    /* the box is entirely off the grid, */ 
            return null;

        if(i0 < 0) i0 = 0; /* make sure we don't overrun the edges */
        if(i1 >= ny) i1 = ny-1;
        if(j0 < 0) j0 = 0;
        if(j1 >= nx) j1 = nx-1;

        return new int[]{ i0, i1, j0, j1 };
    }
    
    public final double[] getBoundX(){ return boundX; }
    public final double[] getBoundY(){ return boundY; }
}