#include "scpview.h"
#include "siman_solver.h"

SimanSolver* siman_solver_new(SCPView* pv,SCPView* spv) {

    SimanSolver* s=NULL;

    /*Check parameter*/
    assert(pv!=NULL);

    /*Allocate memory*/
    s = (SimanSolver*)malloc(sizeof(SimanSolver));
    assert(s!=NULL);

    /*Initialize*/
    s->problemView=pv;
    

    /*Allocate members*/
    s->bestSolutionFound=(unsigned char*)malloc(pv->columns);
    assert(s->bestSolutionFound!=NULL);

    s->currentSolution=(unsigned char*)malloc(pv->columns);
    assert(s->currentSolution!=NULL);

    s->neighborSolution=(unsigned char*)malloc(pv->columns);
    assert(s->neighborSolution!=NULL);

    if (spv!=NULL) s->sortedView=spv;
    else {
        s->sortedView=scp_view_get_copy(s->problemView);
        quick_sort_columns(s->sortedView,siman_solver_compare,NULL);
    }

    /*Allocate and prepare space for collection of morphs*/
    s->morphCollection=malloc(sizeof(int*)*pv->columns);
    assert(s->morphCollection!=NULL);
    memset(s->morphCollection,0,sizeof(int*)*pv->columns);

    s->stIterationCounter=0;

    return s;
}

void siman_solver_solve(SimanSolver* s, float temp, float frozenTemp, int iterations, int morphFlag,float constant,unsigned char* baseSolution,int lowerBound) {

    int cost=0;
    int cols=0;
    int i=0;
    int nbcost=0;
    int delta=0;
    double omega=0;

    /*Check parameters and conditions*/
    assert(s!=NULL && baseSolution!=NULL);
    assert(temp>0.0 && iterations>0 && constant!=0.0f);

    cols = s->problemView->columns;

    /*Create copies of base solution*/
    memcpy(s->currentSolution,baseSolution,cols);
    memcpy(s->bestSolutionFound,baseSolution,cols);


    assert(scp_view_is_solution(s->problemView,baseSolution)==1);

    s->morphFlag=morphFlag;

    cost=scp_view_get_cost_mask(s->problemView,s->currentSolution,cols);
    s->bestSolutionCost=cost;

    /*Initialize variables*/
    s->temp=temp;
    s->constant=constant;
    s->perturbCounter=0;
    s->constructCounter=0;
    s->morphFlag=morphFlag;


    while(s->temp>=frozenTemp) {

        for(i=0;i<iterations;i++) {

            /*Search for neighbor*/
            siman_solver_search(s);
           
            /*Determine whether the neighbor found is to be accepted*/
            nbcost=scp_view_get_cost_mask(s->problemView,s->neighborSolution,cols);
            delta=nbcost-cost;
            omega=rand()%131072/131072.0;

            /*Neighbor is accepted*/
            if (delta<=0 || omega<=exp(-delta/s->temp)) {
                cost=nbcost;

                memcpy(s->currentSolution,s->neighborSolution,cols);
                if (cost<s->bestSolutionCost) {
                    s->bestSolutionCost=cost;
                    memcpy(s->bestSolutionFound,s->currentSolution,cols);
                    /*Lower bound reached, immediate exit*/
                    if (cost<=lowerBound) return;
                }
            }

            
            s->stIterationCounter++;
        }

        /*Cool*/
        s->temp*=s->constant;
    }

}

void siman_solver_search(SimanSolver* s) {

    assert(s!=NULL);

    /*Create copy of current solution*/
    memcpy(s->neighborSolution,s->currentSolution,s->problemView->columns);

    /*Perturbation*/
    siman_solver_deflect(s);
    
    /*Morph*/
    if (s->morphFlag==1) siman_solver_morph(s,s->neighborSolution);

    /*Reconstruction*/
    siman_solver_construct(s);

    /*Redundant columns elimination*/
    siman_solver_redund(s);

}

void siman_solver_deflect(SimanSolver* s) {

    int ri=-1;

    /*Check parameter*/
    assert(s!=NULL);


    /*Drop column with least unique cover (1/3)*/
    if (s->perturbCounter==0) {
        ri=siman_solver_get_least_unique(s);
        if (ri!=-1) s->neighborSolution[ri]=0;
    }
    
    /*Drop random column (2/3)*/
    else {
        ri=siman_solver_get_random_index(s->neighborSolution,s->problemView->columns);
        if (ri!=-1) s->neighborSolution[ri]=0;
    }

    /*Iterate perturbation counter*/
    s->perturbCounter++;
    s->perturbCounter%=3;

    
}

void siman_solver_redund(SimanSolver* s) {

    int i=0;
    int c=s->problemView->columns;
    int pci=0;

    /*Check parameter*/
    assert(s!=NULL);

    for(i=c-1;i>=0;i--) {
        pci=s->sortedView->parentColumnMap[i];
        
        if (s->neighborSolution[pci]==1) {
            s->neighborSolution[pci]=0;
            if (!scp_view_is_solution(s->problemView,s->neighborSolution)==1) s->neighborSolution[pci]=1;
        }
    }
}

void siman_solver_construct(SimanSolver* s) {

    int i=0;
    SCPView* gdView=NULL;
    GreedySolver* gds=NULL;
    SimanSolver* gsa=NULL;
    unsigned char* nbCopy=NULL;


    assert(s!=NULL);
 

    /*Create copy of view*/
    gdView=scp_view_get_copy(s->problemView);

    /*Create copy of neighbor solution*/
    nbCopy=(unsigned char*)malloc(s->problemView->columns);
    memcpy(nbCopy,s->neighborSolution,s->problemView->columns);


    /*Initialize Greedy solver*/
    gds=greedy_solver_new(gdView);
    greedy_solver_initialize(gds,nbCopy);

    if (s->morphFlag==1) gsa=s;

    /*Solve using Balas-Ho greedy*/
    if (s->constructCounter==0) {
        greedy_solver_solve_chvatal(gds,gsa);
    }
    else {
        greedy_solver_solve_balasho(gds,gsa);
    }
    
    /*Obtain the solution*/
    for(i=0;i<gdView->columns;i++) {
        s->neighborSolution[gdView->parentColumnMap[i]]=gds->columnMask[i];
    }
   
    /*Delete greedy solver*/
    greedy_solver_delete(gds);
    scp_view_delete(gdView);

    if (nbCopy!=NULL) free(nbCopy);

    /*Iterate construction counter*/
    s->constructCounter++;
    s->constructCounter%=2;
}



int siman_solver_get_random_index(unsigned char* mask,int range) {

     int baseIndex=rand()%range;
     int direction=rand()%2;
     int i=0;
     int cntr=0;

    assert(mask!=NULL);

       

        one_search:

            /*Small verification*/
            cntr++;
            

            if (direction==0) {

                for(i=baseIndex;i<range;i++) {
                    if (mask[i]==1) {
                        return i;
                    }
                    
                }
            }

            else {
                for(i=baseIndex;i>=0;i--) {
                    if (mask[i]==1) {
                        return i;
                        break;
                    }
                    
                }
            }
            
            direction=!direction;
            if (cntr<2) goto one_search;

            return -1;
        
}

int siman_solver_compare(SCPView* v,int c1,int c2,void* miscData) {
    
    int v1;
    int v2;
    v1=scp_view_get_cost(v,c1);
    v2=scp_view_get_cost(v,c2);

    if (v1<v2) return -1; else if (v1>v2) return +1;
    return 0;
    
}

void siman_solver_add_morph(SimanSolver* s,int columnIndex) {

    int counter=0;
    int upper;
    int lower;
    int i=0;
    int j=0;
    int rows=0;
    int cols=0;
    double ratio=0.0;

    unsigned char v1;
    unsigned char v2;

    /*Check parameters*/
    assert(s!=NULL && columnIndex>=0 && columnIndex<s->problemView->columns);

    rows=s->problemView->rows;
    cols=s->problemView->columns;

    /*Allocate space for 30 morphs + one counter*/
    s->morphCollection[columnIndex]=malloc(31*sizeof(int));
    assert(s->morphCollection[columnIndex]!=NULL);

    /*Get morphs*/
    for(i=0;i<cols;i++) {
        
        if (i==columnIndex) continue;
        
        upper=0;
        lower=0;
        for(j=0;j<rows;j++) {
            v1=scp_view_get(s->problemView,j,columnIndex);
            v2=scp_view_get(s->problemView,j,i);
            upper+=(v1 & v2);
            lower+=(1 & v2);
            
        }
        /*Evaluate ratio*/
        ratio=(double)upper/(double)lower;
        if (ratio>0.6) {
            s->morphCollection[columnIndex][counter+1]=i;
            counter++;
            if (counter==30) break;
        }
        
    }

    /*Set number of morphs*/
    s->morphCollection[columnIndex][0]=counter;

    /*Morph for column constructed OK*/
    
}

void siman_solver_morph(SimanSolver* s,unsigned char* solution) {

    int i=0;
    int j=0;
    int mc=0;
    int mi=0;
    double ratio=0.0;
    double minratio=0.0;
    int mose=-1;

    /*Check parameters and conditions*/
    assert(s!=NULL);
    assert(solution!=NULL);


    /*Each column that is part of solution can be replaced with one of its
     *morphs in order to improve cost of partial solution over number of
     *rows covered by that solution
     */
    for(i=0;i<s->problemView->columns;i++) {

        /*Ignore columns not being part of solution*/
        if (solution[i]==0) continue;
        
        /*Has i-th column morphs ? If not - calculate them !*/
        if (s->morphCollection[i]==NULL) {
            siman_solver_add_morph(s,i);
        }

        mose=-1;

        minratio=scp_view_get_cost_mask(s->problemView,solution,s->problemView->columns);
        minratio/=scp_view_get_mask_coverage(s->problemView,solution);

        /*Browse morphs*/
        mc=s->morphCollection[i][0];
        for(j=1;j<mc+1;j++) {

            /*mi-th column is morph of i-th column*/
            mi=s->morphCollection[i][j];

            /*We care only about morphs that are not present in the solution*/
            if (solution[mi]==1) continue;

            /*Else we remove i-th column from solution and place mi-th column there*/
            solution[i]=0;solution[mi]=1;
            
            /*We calculate the ratio*/
            ratio=scp_view_get_cost_mask(s->problemView,solution,s->problemView->columns);
            ratio/=scp_view_get_mask_coverage(s->problemView,solution);

            /*If that ratio is better we improve minratio*/
            if (ratio<minratio) {
                minratio=ratio;
                mose=mi;    /*mose-th morph is a candidate*/
            }
            /*Rollback changes*/
            solution[i]=1;solution[mi]=0;
            
        }

        /*Any candidate ?*/
        if (mose!=-1) {
            solution[i]=0;solution[mose]=1;
        }

    }

}

int siman_solver_get_least_unique(SimanSolver* s) {

    int cols=s->problemView->columns;
    int rows=s->problemView->rows;
    int i=0,j=0;
    unsigned char v;
    int tag;
    int sc;
    int* hitpoints=NULL;

    hitpoints=malloc(sizeof(int)*cols);
    assert(hitpoints!=NULL);
    
    /*Each column has its own hitpoints*/
    memset(hitpoints,0,cols*sizeof(int));

    for(i=0;i<rows;i++) {
        
        tag=-1;
        
        for(j=0;j<cols;j++) {

            /*Columns not in solution are ignored*/
            if (s->neighborSolution[j]==0) continue;
            
            v=scp_view_get(s->problemView,i,j);
            
            if (v==1) {
                /*First column that cover i-th row*/
                if (tag==-1) {
                    tag=j;
                }
                /*At least two columns cover i-th row*/
                else {
                    tag=-1;break;
                }
            }
        }

        if (tag!=-1) hitpoints[tag]++;
    }

    j=PS_INFINITY;
    sc=-1;
    for (i=0;i<cols;i++) {
        if (s->neighborSolution[i]==0) continue;
        if (hitpoints[i]<j) {
            j=hitpoints[i];
            sc=i;
        }
    }

    /*It is possible that there is no column available*/
    free(hitpoints);
    
    /*Return*/
    return sc;

}

void siman_solver_get_solution(SimanSolver* s,unsigned char* retMask) {

    /*Check parameters*/
    assert(s!=NULL && retMask!=NULL);
    /*Copy best solution found*/
    memcpy(retMask,s->bestSolutionFound,s->problemView->columns);
    /*Done*/
}


void siman_solver_delete(SimanSolver* s) {

    int i=0;

    if (s==NULL) return;
    if (s->bestSolutionFound!=NULL) free(s->bestSolutionFound);
    if (s->currentSolution!=NULL) free(s->currentSolution);
    if (s->neighborSolution!=NULL) free(s->neighborSolution);
    
    /*Morph collection*/
    if (s->morphCollection!=NULL) {
        for(i=0;i<s->sortedView->columns;i++) {
            if (s->morphCollection[i]!=NULL) free(s->morphCollection[i]);
        }
        free(s->morphCollection);
    }

    if (s->sortedView!=NULL) scp_view_delete(s->sortedView);


    free(s);

}



void siman_solver_print(SimanSolver* s) {
    
    int i=0;
    int j=0;
    int k=0;

    if (s==NULL) {
        printf("SIMANSOLVER: NULL\n");
    }
    else printf("SIMANSOLVER: {\n");


    /*Solutions*/
    printf("C:");
    for(i=0;i<s->problemView->columns;i++) {
        printf("%d",s->currentSolution[i]);
    }
    printf("\nN:");
    for(i=0;i<s->problemView->columns;i++) {
        printf("%d",s->neighborSolution[i]);
    }
    printf("\nB:");
    for(i=0;i<s->problemView->columns;i++) {
        printf("%d",s->bestSolutionFound[i]);
    }

    printf("\nMorphs:\n");
    for(i=0;i<s->problemView->columns;i++) {
        if (s->morphCollection[i]==NULL) {printf("%d:NO_MORPHS\n",i);continue;}
        j=s->morphCollection[i][0];
        printf("%d:MC:%d |",i,j);
        for(k=1;k<j+1;k++) {
            printf("%d,",s->morphCollection[i][k]);
        }
        printf("\n");
    }

    printf("TEMP: %f\n",s->temp);

    printf("}\n");
}


