package MyPackage;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Ali Shahbazi
 */


public class SpacialSearch2 {//SpacialSearch2 consider input range other than 0 and 1
    
    private int PointNumCell=20;//number of points in each cell
    
    //Data array info
    private ArrayDouble2D Data;
    private int DataSize;
    //spacial info
    private int[][] SData;//
    //789
    //456
    //123
    private int[] SDataFill;
    private int StepNum;
    private double StepSize;
    private int BufInc=50;
    
    private int[][] CellsLayerN;//just used to store layar n cells

    public StatOnline statusL=new StatOnline();
    public StatOnline statusC=new StatOnline();
    public StatOnline statusP=new StatOnline();
    
    private double[] dataLowerBound;
    private double[] dataHigherBound;
    
    public SpacialSearch2(){
        super();
    }
    
    public void Preprocess(ArrayDouble2D data, int StepNumber){//StepNum is in each dimension
        this.StepNum=StepNumber;

        this.dataHigherBound=data.dataHigherBound;
        this.dataLowerBound=data.dataLowerBound;
        
        this.StepSize=(dataHigherBound[0]-dataLowerBound[0])/StepNumber;
        
        this.Data=data;
        this.DataSize=data.GetSize();
        this.BufInc=(int)(PointNumCell*5);
        
        int cellNum=(int)Math.round(Math.pow(StepNumber, data.GetDimension()));
        this.SDataFill=new int [cellNum];
        this.SData=new int[cellNum][BufInc];
        this.CellsLayerN=new int[cellNum][data.GetDimension()];
        //preprocess

        this.AddPointsToSS(data.GetStartIndex(), data.GetEndIndex());
        
        
    }
    public void Preprocess(ArrayDouble2D data){//StepNum is in each dimension
        int StepNumber=this.CalcStepNum(data.GetSize(),data.GetDimension());
        this.Preprocess(data, StepNumber);
    }
    public int CalcStepNum(int data_size, int dimension){
        int StepNumber=(int) Math.round(  Math.pow((double)data_size/PointNumCell, (double)1.0/dimension)  );
        return StepNumber;
    }

    public void Add(){
        this.AddPointsToSS(this.Data.GetStartIndex()+this.DataSize, this.Data.GetEndIndex());
        this.DataSize=this.Data.GetSize();
    }

    
    
    private void AddPointsToSS(int StartIndex, int EndIndex){

        int index=0;

        for(int i=StartIndex;i<EndIndex;i++){

            index=this.CellAdrArrayToInt(this.FindCell(this.Data.Arr[i]));
            //increse array size

            if(this.SData[index].length==this.SDataFill[index]){
                int[] temp=new int[this.SDataFill[index]+BufInc];
                System.arraycopy(this.SData[index], 0, temp, 0, this.SDataFill[index]);
                this.SData[index]=temp;
            }

            //
            this.SData[index][this.SDataFill[index]]=i;
            this.SDataFill[index]++;
        }
    }

    public double Find1NNDist(double[] input){
        int index;
        index=this.Find1NN(input);
        return this.Distance(input, this.Data.Arr[index]);
    }
    
    
    
    public int Find1NN(double[] input){ //returns the index of nearest neighbor, return -1 if no point found
        double NearestDist=9999999999.9;
        int NearestIndex=-1;
        double temp=0;
        double cellCounter=0;
        double pointCounter=0;

        //find input cell
        int[] inputCell=FindCell(input);
        

        //
        for(int lay=0;lay<this.StepNum;lay++){//for layers
            //check for break
            if(NearestIndex>=0){
                if(FindLayerDistance(input,lay)>NearestDist){
                    statusL.Update(lay-1);
                    statusC.Update(cellCounter);
                    statusP.Update(pointCounter);
                    return NearestIndex;
                }
            }


            int cell_num=UpdateCellsLayerN(inputCell,lay);
            if(cell_num==0)
                break;
            
            for(int j=0; j<cell_num;j++){//for cells in a layer
                
                
                if(FindCellDistance(input, CellsLayerN[j])<NearestDist){
                    
                    int index=CellAdrArrayToInt(CellsLayerN[j]);                    
                    int indexArrayLen=this.SDataFill[index];
                    pointCounter=pointCounter+indexArrayLen;
                    cellCounter++;
                    
        
                    index=Find1NNInCell(input, CellsLayerN[j]);
                    
                    if(index>=0){
                        temp=Distance(input, this.Data.Arr[index]);
                        if(temp<NearestDist){
                            NearestIndex=index;
                            NearestDist=temp;
                        }
                    }
                }
            }
        }

        if(NearestIndex==-1)
            System.err.println("Error: SpacialSearch.Find returns -1");

        return NearestIndex;
    }
    

    private double Distance(double[] x, double[] y){//distance in n dimension
        int dim=x.length;
        double dist=0;
        for(int i=0;i<dim;i++){
            dist+=((x[i]-y[i])*(x[i]-y[i]));
        }

        return (Math.sqrt(dist));
    }

    private double DistanceP2(double[] x, double[] y){//distance in n dimension
        int dim=x.length;
        double dist=0;
        for(int i=0;i<dim;i++){
            dist+=((x[i]-y[i])*(x[i]-y[i]));
        }

        return dist;
    }

    
    private int CellAdrArrayToInt(int[] cell){
        int index=cell[0];
        for(int i=1;i<cell.length;i++){
            index+=cell[i]*(i*this.StepNum);
        }
        return index;
    }
    
    
    private int[] FindCell(double[] input){
        double[] scaledInput=scaleDataToUnit(input);
        int[] res=new int[input.length];
        for(int i=0;i<input.length;i++){
            res[i]=(int)(scaledInput[i]/this.StepSize);
            if(res[i]>=this.StepNum)   res[i]= this.StepNum-1;
        }
        return res;
    }
    private double[] scaleDataToUnit(double data[]){
        double[] dataScaled=new double[data.length];
        for(int d=0;d<data.length;d++){
            dataScaled[d]=(data[d]-dataLowerBound[d])/(dataHigherBound[d]-dataLowerBound[d]);
        }
        return dataScaled;
    }
    
    
    private double FindLayerDistance(double[] input, int layer){
        double d=FindCellDistance(input,FindCell(input));
        if(layer<=1)
            return d;
        else
            return d+(layer-1)*this.StepSize;
    }
    
    private double FindCellDistance(double[] input, int[] cell){
        
        int dim=Data.GetDimension();
        double dist=0;
        double temp;
        
        int[] inputCell=FindCell(input);
        //1. if cell of the input point
        if(this.CellAdrArrayToInt(cell)==this.CellAdrArrayToInt(inputCell)){
            ArrayDouble1D temp2=new ArrayDouble1D(dim*2);
            for(int i=0;i<dim;i++){
                temp2.Arr[2*i]=(cell[i]+1)*this.StepSize - input[i];
                temp2.Arr[2*i+1]=input[i] - (cell[i]+0)*this.StepSize;
            }

            return temp2.GetMin();
        }
        
        //2. otherwise
        for(int i=0;i<dim;i++){
            if(input[i]<(cell[i]+0)*this.StepSize)
                temp=(cell[i]+0)*this.StepSize - input[i];
            else if(input[i]>(cell[i]+1)*this.StepSize)
                temp=input[i] - (cell[i]+1)*this.StepSize;
            else
                temp=0;
            
            dist+=(temp*temp);
            
        }
        
        return Math.sqrt(dist);
        
        
    }
    
    
    
    private int Find1NNInCell(double[] input, int[] cell){//return -1 if nothing found
        int index=CellAdrArrayToInt(cell);
        int[] indexArray=this.SData[index];
        int indexArrayLen=this.SDataFill[index];
        double min=999999999,d;
        int min_index=-1;

        for(int i=0;i<indexArrayLen;i++){
            d=DistanceP2(input,this.Data.Arr[indexArray[i]]);
            if(d<min){
                min=d;
                min_index=indexArray[i];
            }
        }

        return min_index;
    }
    

    private boolean IsBorderCell(int layer, int[] array){
        for(int i=0;i<array.length;i++){
            if(array[i]==layer || array[i]==-layer)
                return true;
        }
        return false;
        
    }
    
    private int UpdateCellsLayerN(int[] cell, int layer){//return the number of found cells
        //22222
        //21112
        //21012  //num od cells in layer n and dimension d: (2n+1)^d - (2n-1)^d
        //21112
        //22222
        int dim=Data.GetDimension();
        int[] acounter=new int[dim];
        int[] acounter2=new int[dim];
        boolean IsInHypercube=true;
        int size=0;
        
        //layer=0
        if(layer==0){
            for(int i=0;i<dim;i++){
                CellsLayerN[0][i]=cell[i];
            }
            size=1;
            return size;
        }
        //other layers
        for(int i=0;i<dim;i++){//init
            acounter[i]=-layer;
        }
        int M=(int)Math.pow(2*layer+1, dim);
        for(int k=0;k<M;k++){
            //check the cell
            if(IsBorderCell(layer, acounter)==true){
                //copy acounter to acounter2
                IsInHypercube=true;
                for(int i=0;i<dim;i++){
                    acounter2[i]=cell[i]+acounter[i];
                    if(acounter2[i]<0 || acounter2[i]>=this.StepNum){
                        IsInHypercube=false;
                        break;
                    }                       
                }
                //copy acounter2 to CellsLayerN
                if(IsInHypercube==true){
                    for(int i=0;i<dim;i++)
                        CellsLayerN[size][i]=acounter2[i];
                    size++;
                }
            }
            
            //change the cell
            for(int i=0;i<dim;i++){
                acounter[i]++;
                if(acounter[i]>layer)
                    acounter[i]=-layer;
                else
                    break;
            }
            
        }//end of while
        return size;
    }
    
    /*
    private int[][] GetCellsLayerN(int[] cell, int layer){//only 2-d
        //22222
        //21112
        //21012
        //21112
        //22222
        int dim=2;
        //layer 0
        if(layer==0){
            int[][] cells=new int[1][dim];
            cells[0]=cell;
            return cells;
        }
        //other layers

        

        //find cells
        

        int cellNum=0;
        int x,y;
        //down
        for(int i=-layer;i<layer;i++){
            x=cell[0]+i;
            y=cell[1]-layer;
            if(x>=0 && x<this.StepNum && y>=0 && y<this.StepNum){
                this.CellsLayerN[cellNum][0]=x;
                this.CellsLayerN[cellNum][1]=y;
                cellNum++;
            }
        }

        //right
        for(int i=-layer;i<layer;i++){
            x=cell[0]+layer;
            y=cell[1]+i;
            if(x>=0 && x<this.StepNum && y>=0 && y<this.StepNum){
                this.CellsLayerN[cellNum][0]=x;
                this.CellsLayerN[cellNum][1]=y;
                cellNum++;
            }
        }
        //up
        for(int i=layer;i>-layer;i--){
            x=cell[0]+i;
            y=cell[1]+layer;
            if(x>=0 && x<this.StepNum && y>=0 && y<this.StepNum){
                this.CellsLayerN[cellNum][0]=x;
                this.CellsLayerN[cellNum][1]=y;
                cellNum++;
            }
        }
        
        //left
        for(int i=layer;i>-layer;i--){
            x=cell[0]-layer;
            y=cell[1]+i;
            if(x>=0 && x<this.StepNum && y>=0 && y<this.StepNum){
                this.CellsLayerN[cellNum][0]=x;
                this.CellsLayerN[cellNum][1]=y;
                cellNum++;
            }
        }

        int[][] cells=new int[cellNum][dim];
        for(int i=0;i<cellNum;i++){
            cells[i][0]=this.CellsLayerN[i][0];
            cells[i][1]=this.CellsLayerN[i][1];
        }
        return cells;
    }
    */
    
    
    //---------------------------------------
    // Not optimized search, search all the points
    //---------------------------------------
    public int Find1NNold(ArrayDouble2D data, double[] input){
        double dist_sq;
        double dist_sq_min=9999999999999999999999999999999.9;
        int i,j;
        int nearest=0;
        int dimension=data.GetDimension();

        for ( j = data.GetStartIndex(); j < data.GetEndIndex(); j++ ){
            dist_sq = 0.0;
            for ( i = 0; i < dimension; i++ )
                dist_sq = dist_sq + (input[i]-data.Arr[j][i]) * (input[i]-data.Arr[j][i]);

            if (dist_sq < dist_sq_min ){
                dist_sq_min = dist_sq;
                nearest = j;
            }
        }
        return nearest;
    }
}