#include "ilist.h"
#include "greedy.h"


GreedySolver* greedy_solver_new(SCPView* pv) {


    GreedySolver* s=NULL;
    unsigned char* ptr=NULL;
    unsigned char* msk=NULL;

    /*Check parameters and conditions*/
    assert(pv!=NULL);
    
    /*Allocate new GreedySolver*/
    s = (GreedySolver*)malloc(sizeof(GreedySolver));
    assert(s!=NULL);
    
    /*Allocate space for indices of columns*/
    ptr = (unsigned char*)malloc(sizeof(unsigned char)*pv->columns);
    assert(ptr!=NULL);

    s->columnMask=ptr;
    
    /*Allocate space for mask of rows*/
    msk = (unsigned char*)malloc(sizeof(unsigned char)*pv->rows);
    assert(msk!=NULL);
    
    s->rowMask=msk;
    s->problemView=pv;

    /*Return pointer*/
    return s;
}


void greedy_solver_initialize(GreedySolver* s,unsigned char* columnMask) {

    int i=0;
    int j=0;

    unsigned char val;

    /*Check parameters and conditions*/
    assert (s!=NULL);
    
    memset(s->rowMask,0,s->problemView->rows);

    /*Clear indices and masks*/
    if (columnMask==NULL) {
        memset(s->columnMask,0,s->problemView->columns);
    }
    
    /*There is partial solution. We have some columns being part
     *of solution and we also have to update rowMask and coverCoverage
     */
    else {

        memcpy(s->columnMask,columnMask,s->problemView->columns);
        
        /*Update rowMask*/
        for(i=0;i<s->problemView->columns;i++) {

            if (s->columnMask[i]==1) {
                for(j=0;j<s->problemView->rows;j++) {
                    val=scp_view_get(s->problemView,j,i);
                    if (val==1 && s->rowMask[j]==0) {
                        s->rowMask[j]=1;
                    }
                }
            }
            
        }

        
    }

   
}


void greedy_solver_solve_chvatal(GreedySolver* s,SimanSolver* saSolver) {
    
    int rows=s->problemView->rows;
    int cols=s->problemView->columns;
    


    int ar;

    int columnIndex=0;
    int selectedColumnListIndex=0;
    int selectedColumnIndex=0;

    int morphCounter=0;

    double ratio;
    double minratio;

    IList* freeColumns=NULL;
    IList* freeRows=NULL;

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

    /*Create linked list of available columns and not covered rows*/
    freeColumns=ilist_new_from_mask(s->columnMask,cols,0);
    freeRows=ilist_new_from_mask(s->rowMask,rows,0);

    
  
    /*Repeat until the cover is completed. Ending condition is inside loop*/
    while(freeRows->length>0) {

        /*Calculate (cost/rows) covered ratio*/
        minratio=POS_INFINITY;
        
        selectedColumnIndex=-1;
        selectedColumnListIndex=-1;

        ilist_start_iteration(freeColumns);
        while(ilist_iterate(freeColumns,&columnIndex)) {

            /*How many additional rows will be covered*/
            ar=scp_view_get_negative_list_diference_size(s->problemView,freeRows,columnIndex);

            /*No additional rows covered, continuing*/
            if(ar==0) continue;

            /*Ratio calculation*/
            ratio = (scp_view_get_cost(s->problemView,columnIndex) ) / (float)(ar);
            /*Checking for minimum*/
            if (ratio<minratio) {
                minratio=ratio;
                selectedColumnListIndex=freeColumns->lastIterIndex;
                selectedColumnIndex=columnIndex;
            }
        }

       /*What should never happen*/
        assert(selectedColumnIndex!=-1);

        /*Selected column is removed from list of free columns*/
        ilist_remove(freeColumns,selectedColumnListIndex);

        /*List of free rows is updated*/
        greedy_solver_remove_covered_rows(s,freeRows,selectedColumnIndex);

        /*All rows covered, we are done here*/
        if (freeRows->length<1) goto f_end;

        /*Morphing*/
        if (saSolver!=NULL && morphCounter==3 ) {
            ilist_make_mask(freeColumns,s->columnMask,cols,0);
            siman_solver_morph(saSolver,s->columnMask);

            /*We have to reinitialize*/
            free(freeRows);
            free(freeColumns);

            greedy_solver_reinitialize(s);

            freeColumns=ilist_new_from_mask(s->columnMask,cols,0);
            freeRows=ilist_new_from_mask(s->rowMask,rows,0);
        }

        morphCounter++;
        morphCounter%=4;
        
    }

    f_end:

    ilist_make_mask(freeColumns,s->columnMask,cols,0);

    ilist_delete(freeColumns);
    ilist_delete(freeRows);
    
}

void greedy_solver_solve_balasho(GreedySolver* s,SimanSolver* saSolver) {

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

    int morphCounter=0;
    
    int ar;

    int columnIndex=0;
    int selectedColumnListIndex=0;
    int selectedColumnIndex=0;

    int rowIndex=0;
    int rowListIndex=0;
    
    double ratio;
    double maxratio;

    IList* freeColumns=NULL;
    IList* freeRows=NULL;

    freeColumns=ilist_new_from_mask(s->columnMask,cols,0);
    freeRows=ilist_new_from_mask(s->rowMask,rows,0);


    /*While there are some uncovered rows, perform the following.*/
    while(freeRows->length>0) {

        /*Choose randomly index in uncovered row*/
        rowListIndex=rand()%freeRows->length;
        rowIndex=ilist_get(freeRows,rowListIndex);
        
        /*Row k will be covered by some column. For each column there
         *is calculated how much uncovered rows it covers*/
        selectedColumnIndex=-1;
        selectedColumnListIndex=-1;

        maxratio=NEG_INFINITY;
        ilist_start_iteration(freeColumns);
        while(ilist_iterate(freeColumns,&columnIndex)) {

            
             /*We do not care about columns that do not cover the row*/
            if(scp_view_get(s->problemView,rowIndex,columnIndex)==0) continue;
            
            /*We calculate how many additional rows will be covered*/
            ar=scp_view_get_negative_list_diference_size(s->problemView,freeRows,columnIndex);

            ratio=(double)ar/(double)scp_view_get_cost(s->problemView,columnIndex);
            if (ratio>maxratio) {
                maxratio=ratio;
                selectedColumnIndex=columnIndex;
                selectedColumnListIndex=freeColumns->lastIterIndex;
            }

        }

        /*Thus, the row will be covered by some column*/
        assert(selectedColumnIndex!=-1);
        /*That column will be removed from the list of free columns*/
        ilist_remove(freeColumns,selectedColumnListIndex);

        /*List of free rows is updated*/
        greedy_solver_remove_covered_rows(s,freeRows,selectedColumnIndex);

        /*All rows covered, we are done here*/
        if (freeRows->length<1) goto f_end;

        /*Morphing*/
        if (saSolver!=NULL && morphCounter==3 ) {
            ilist_make_mask(freeColumns,s->columnMask,cols,0);
            siman_solver_morph(saSolver,s->columnMask);

            /*We have to reinitialize*/
            free(freeRows);
            free(freeColumns);

            greedy_solver_reinitialize(s);

            freeColumns=ilist_new_from_mask(s->columnMask,cols,0);
            freeRows=ilist_new_from_mask(s->rowMask,rows,0);
        }

        morphCounter++;
        morphCounter%=4;

    }

    f_end:

    ilist_make_mask(freeColumns,s->columnMask,cols,0);

    ilist_delete(freeColumns);
    ilist_delete(freeRows);
    
}


void greedy_solver_remove_covered_rows(GreedySolver* gs,IList* rowList,int column) {

    int i=0;
    int r=0;
   
    
    assert(gs!=NULL);
    assert(rowList!=NULL);

    while(i<rowList->length) {

        r=ilist_get(rowList,i);
        if (scp_view_get(gs->problemView,r,column)==1) {
            ilist_remove(rowList,i);
        }
        else {
            i++;
        }
    }

}


/*Update rowMask*/
void greedy_solver_reinitialize(GreedySolver* s) {

    int i=0;
    int j=0;
    unsigned char val=0;


    for(i=0;i<s->problemView->columns;i++) {

        if (s->columnMask[i]==1) {
            for(j=0;j<s->problemView->rows;j++) {
                val=scp_view_get(s->problemView,j,i);
                if (val==1 && s->rowMask[j]==0) {
                    s->rowMask[j]=1;
                }
            }
        }

    }
}


void greedy_solver_delete(GreedySolver* s) {

    /*Check parameter*/
    if (s==NULL) return;

    /*Free*/
    if (s->columnMask!=NULL) free(s->columnMask);
    if (s->rowMask!=NULL) free(s->rowMask);
    
    free(s);

    /*Done*/
}

void greedy_solver_print(GreedySolver* s) {
    int i=0;

    printf("[GREEDY] {\n");

    if (s==NULL) {
        printf("!!! NULL !!!\n}\n");
        return;
    }
    printf("columnMask:");

    for(i=0;i<s->problemView->columns;i++) {
        printf("%02d ",s->columnMask[i]);
    }
    printf("\n");
    
    printf("}\n");


}
