#include <windows.h>
#include <process.h>
#include <memory.h>
#include <io.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <alloc.h>
#include <dos.h>
#include <math.h>
#include "aura.h"
#include "cover.h"
#include "tpfnct.h"
//structure to keep number of columns,used for solution


float GetMyCPUTime()
{
    HANDLE hProcess; // specifies the process of interest
    FILETIME lpCreationTime; // when the process was created
    FILETIME lpExitTime; // when the process exited
    FILETIME lpKernelTime; // time the process has spent in kernel mode
    FILETIME lpUserTime;
    LARGE_INTEGER t1, t2;


    hProcess = GetCurrentProcess();
    GetProcessTimes(hProcess, &lpCreationTime, &lpExitTime, &lpKernelTime,&lpUserTime);
    memcpy(&t1, &lpUserTime, sizeof(FILETIME));
    memcpy(&t2, &lpKernelTime, sizeof(FILETIME));
    return ((float)(t1.QuadPart+t2.QuadPart)/10000000);
}
void Release (struct CoveringMatrix * CM)
{ //Function to release allocated memory for structure keeping matrix
  struct CLink *Aux;
  struct CLink *Aux2;
  if ( CM->ColLink !=0 )
    {//First,delete all rows
     Aux=CM->ColLink->Next;
    delete (CM->ColLink);
     while ( Aux!=0 )
      {
	Aux2=Aux->Next;
	delete (Aux);
	Aux=Aux2;
      }
    }
  if ( CM->RowLink !=0 )
    {//then delete all columns
     Aux=CM->RowLink->Next;
     delete (CM->RowLink);
     while ( Aux!=0 )
      {
	Aux2=Aux->Next;
	delete (Aux);
	Aux=Aux2;
      }
    }
  delete (CM);//fillany delete header of structure
}





void Release ( struct header_of_solution_UCP *SolUCP )
{ //structure to release allocated memory for solution
  struct CLink *Aux;
  struct CLink *Aux2;

  if ( SolUCP->SetC !=0 )
   {//delete all column links
      Aux=SolUCP->SetC->Next;
      delete ( SolUCP->SetC );
      while ( Aux!=0 )
	 {
	    Aux2=Aux->Next;
	    delete (Aux);
	    Aux=Aux2;
	 }
   }
   delete ( SolUCP );//delete header
}

struct header_of_solution_UCP *create_New_Empty_Solution ( void )
{//Structure to create empty header structure to keep solution

   struct header_of_solution_UCP *Solution;

   //first allocate memory
   Solution=new header_of_solution_UCP;
     if ( Solution==NULL)
       {
	     printf ("Insufficient memory \n");
	     exit(0);
       }
   //and set all antries to zero
   Solution->Cost=0;
   Solution->SetC=0;

  return Solution;
}


void AppendSolution (struct header_of_solution_UCP *Source,struct header_of_solution_UCP *Target )
{//function to apend partial solution to solution of UCP
  struct CLink *Aux;

  //if there are no cols in solution of UCP
  if ( Target->SetC==0 ) Target->SetC=Source->SetC;
   else
     { //else connect to the end of link
       Aux=Target->SetC;
       while ( Aux->Next!=0 )
	       Aux=Aux->Next;
       Aux->Next=Source->SetC;
     }
  Target->Cost+=Source->Cost;
  delete (Source);//delete header of partial solution,it is no inter needed
}

void Replace_Solution (struct header_of_solution_UCP *Source,struct header_of_solution_UCP *Target )
{//function to apend partial solution to solution of UCP
  struct CLink *Aux,*Aux2;

  //if there are no cols in solution of UCP
  if ( Target->SetC!=0 )
     { //first delete all cols
       Aux=Target->SetC;
       while ( Aux!=0 )
       {
	       Aux2=Aux;
         Aux=Aux->Next;
	       delete (Aux2);
       }
     }
     
  Target->SetC=Source->SetC;     
  Target->Cost=Source->Cost;
  delete (Source);//delete header of partial solution,it is no inter needed
}


void AddToSolution ( struct header_of_solution_UCP *SolutionUCP,struct CLink *Column )
{//Function to add column number to solution
     struct CLink *Solution;
     struct CLink *Aux;

     Solution=new CLink;
     if ( Solution==NULL)
       {
	        printf ("Insufficient memory \n");
	        exit(0);
       }
     Solution->ID=Column->ID;
     Solution->Cost=Column->Cost;
     Solution->Offset=Column->Offset;
     Solution->NumberOf1=Column->NumberOf1;
     Solution->Next=0;

     if ( SolutionUCP->SetC==0 )
	{//if there are no entries in solution
	  SolutionUCP->SetC=Solution;
	  SolutionUCP->Cost=Column->Cost;
	}
      else
       {//else append it to the end od links
	 SolutionUCP->Cost+=Column->Cost;
	 Aux=SolutionUCP->SetC;
	 while ( Aux->Next!=0 )
	 Aux=Aux->Next;
	 Aux->Next=Solution;
       }
}




void PrintSolution ( struct header_of_solution_UCP *SolutionUCP )
{
   struct CLink *Aux;

   Aux=SolutionUCP->SetC;

   while (Aux!=0 )
     {

      	printf("%d ",Aux->ID );
      	Aux=Aux->Next;
     }
  printf("\nCost: %lu\n\n----------------------------\n",SolutionUCP->Cost);
}

void remove_Col_From_Matrix ( struct CoveringMatrix *CM, struct CLink *colToRemove )
{//remove column from covering matrix
  struct CLink *Entry,*Aux;
  
  Entry=CM->ColLink;

  if ( Entry !=0 )
    {
    while ( Entry->ID!=colToRemove->ID )
    	Entry=Entry->Next;

	if ( Entry->Next != 0&&Entry->Previous!=0 )
	  {
	   Entry->Next->Previous=Entry->Previous;
	   Entry->Previous->Next=Entry->Next;
	  }
       else
	if ( Entry->Next!=0&&Entry->Previous==0	)
	  {
	   Entry->Next->Previous=0;
	   CM->ColLink=Entry->Next;
	  }
	else
	if ( Entry->Next == 0&&Entry->Previous!=0 )
	  {
	   Entry->Previous->Next=0;
	  }
	else
	if ( Entry->Next == 0&&Entry->Previous==0 )
	  {//if it is the only column in the matrix,all rows must be deleted
	   //to set the matrix empty
	   CM->ColLink=0;
	  }
	CM->countOfCols--;//decrease dimension of matrix
	delete (Entry);//delete column
    
    

    }
}

void remove_Col_From_Matrix ( struct CoveringMatrix *CM, int ID )
{//remove column from covering matrix
  struct CLink *Entry,*Aux;
  
  Entry=CM->ColLink;

  if ( Entry !=0 )
    {
    while ( Entry->ID!=ID )//pokud se cislo sloupce shoduje se sloupcem k vymazani
    	Entry=Entry->Next;

	if ( Entry->Next != 0&&Entry->Previous!=0 )
	  {
	   Entry->Next->Previous=Entry->Previous;
	   Entry->Previous->Next=Entry->Next;
	  }
       else
	if ( Entry->Next!=0&&Entry->Previous==0	)
	  {
	   Entry->Next->Previous=0;
	   CM->ColLink=Entry->Next;
	  }
	else
	if ( Entry->Next == 0&&Entry->Previous!=0 )
	  {
	   Entry->Previous->Next=0;
	  }
	else
	if ( Entry->Next == 0&&Entry->Previous==0 )
	  {//if it is the only column in the matrix,all rows must be deleted
	   //to set the matrix empty
	   CM->ColLink=0;
	  }
	CM->countOfCols--;//decrease dimension of matrix
	delete (Entry);//delete column
    
    

    }
}

void remove_Row_From_Matrix ( struct CoveringMatrix *CM, struct CLink *rowToRemove )
{
  struct CLink *Entry,*Aux;
  Entry=CM->RowLink;
  if ( Entry !=0 )
  {
	
    while ( Entry->ID!=rowToRemove->ID )
	Entry=Entry->Next;
    
	if ( Entry->Next != 0 &&Entry->Previous!=0 )
	  {
	   Entry->Next->Previous=Entry->Previous;
	   Entry->Previous->Next=Entry->Next;
	  }
       else
	if ( Entry->Next!=0 &&Entry->Previous==0	)
	  {
	   Entry->Next->Previous=0;
	   CM->RowLink=Entry->Next;
	  }
	else
	if ( Entry->Next == 0 &&Entry->Previous!=0 )
	  {
	   Entry->Previous->Next=0;
	  }
	else
	if ( Entry->Next == 0&&Entry->Previous==0 )
	  {
	   CM->RowLink=0;

	  }
	 delete (Entry);//delete row
	 CM->countOfRows--;//decrease dimension of matrix

  }

}

void RemoveColWithRows ( struct CLink * Column, struct CoveringMatrix *CM )
{//Function to remove column and all rows it covers
  struct CLink *RowLink;
  struct CLink *Aux;

  RowLink = CM->RowLink;
  while ( RowLink!=0)
   {
    if ( CM->Array[Column->ID][RowLink->ID]==1 )
       {//if column intersect row,it will be deleted
	       Aux=RowLink->Next;
	       remove_Row_From_Matrix(CM,RowLink );
	  
       }
     else Aux=RowLink->Next;
      RowLink=Aux;
   }//by deleting all rows int the matrix,all cols should be deleted too
   //if there is a column in the matrix,delete current column

   if ( CM->ColLink!=0 ) remove_Col_From_Matrix ( CM,Column );
}




struct CoveringMatrix *Duplicate ( struct CoveringMatrix *CM)
{//Function to duplicate links to rows and cols of covering matrix
  struct CoveringMatrix *Copy;
  struct CLink *Rows;
  struct CLink *Columns;
  struct CLink *CMRowLink;
  struct CLink *CMColLink;

  CMRowLink=CM->RowLink;
  CMColLink=CM->ColLink;
  Copy=new CoveringMatrix;
  if ( Copy==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

  Copy->Cost=CM->Cost;
  Copy->countOfOnes=CM->countOfOnes;
  Copy->countOfCols=CM->countOfCols;
  Copy->countOfRows=CM->countOfRows;
  Copy->MSIR=CM->MSIR;
  Copy->lbound=CM->lbound;
  Copy->Array=CM->Array;//Sel all antries of created link to
  //values of link of original matrix
  Copy->Dirty=CM->Dirty;
  Copy->ColLink=NULL;
  Copy->RowLink=NULL;

  if ( CM->RowLink!=NULL )
    {//if there are another entries,add it to duplicated matrix
      Copy->RowLink=new CLink;
      if ( Copy->RowLink==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }
      Copy->RowLink->Previous=NULL;
      Copy->RowLink->Next=NULL;
      Copy->RowLink->Offset=CM->RowLink->Offset;
      Copy->RowLink->ID=CM->RowLink->ID;
      Copy->RowLink->NumberOf1=CM->RowLink->NumberOf1;
      Copy->RowLink->Cost=CM->RowLink->Cost;
      Rows=Copy->RowLink;
      CMRowLink=CM->RowLink->Next;


  while ( CMRowLink!=NULL )
   {
     Rows->Next=new CLink;
     if ( Rows->Next==NULL )
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

     Rows->Next->Previous=Rows;
     Rows=Rows->Next;
     Rows->Offset=CMRowLink->Offset;
     Rows->ID=CMRowLink->ID;
     Rows->NumberOf1=CMRowLink->NumberOf1;
     Rows->Cost=CMRowLink->Cost;
//Sel all antries of created link to
  //values of link of original matrix
     Rows->Next=NULL;
     CMRowLink=CMRowLink->Next;
   }
  }

  if ( CM->ColLink!=NULL )
     {

       Copy->ColLink = new CLink;
       if ( Copy->ColLink==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

       Copy->ColLink->Previous=NULL;
       Copy->ColLink->Next=NULL;
       Copy->ColLink->Offset=CM->ColLink->Offset;
       Copy->ColLink->NumberOf1=CM->ColLink->NumberOf1;
       Copy->ColLink->Cost=CM->ColLink->Cost;
       Copy->ColLink->ID=CM->ColLink->ID;
       Columns=Copy->ColLink;
       CMColLink=CM->ColLink->Next;
//Sel all antries of created link to
  //values of link of original matrix

 while ( CMColLink!=NULL )
   {
     Columns->Next=new CLink;
     if ( Columns->Next==NULL )
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

      Columns->Next->Previous=Columns;
     Columns=Columns->Next;

     Columns->Offset=CMColLink->Offset;
     Columns->ID=CMColLink->ID;
     Columns->NumberOf1=CMColLink->NumberOf1;
     Columns->Cost=CMColLink->Cost;

     Columns->Next=NULL;
     CMColLink=CMColLink->Next;
//Sel all antries of created link to
  //values of link of original matrix
    }
   }
  return Copy;
}


void print_Matrix ( struct CoveringMatrix *CM )
{//print_Matrix 
  struct CLink *Columns;
  struct CLink *Rows;

  printf("\n    ");
    Columns=CM->ColLink;
    while ( Columns!=0)
    {
      printf ("%d ",Columns->ID);
      Columns=Columns->Next;
    }
  printf("\n");
  Rows=CM->RowLink;
  while ( Rows!=0)
   {
    printf ( "%2d- ",Rows->ID);
    Columns=CM->ColLink;
    while ( Columns!=0)
    {
      printf ("%d ",CM->Array[Columns->ID][Rows->ID]);
      Columns=Columns->Next;
    }
    printf ("\n");
    Rows=Rows->Next;
   }
}


void create_Matrix ( struct CoveringMatrix *Cm,int *Costs )
{//Function to create row and column links of covering matrix
	//CM->Array ukazuje na pole, musim vytvorit ukazatele na jednotlive radky a sloupce.
  int I,J;
  struct CLink *Columns;
  struct CLink *Rows;
  //Create row links
  if (Cm->countOfCols!=0||Cm->countOfRows!=0)
  {
  Cm->RowLink = new CLink;
  if ( Cm->RowLink==NULL )
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

  Cm->RowLink->Previous=0;
  Cm->RowLink->Offset=Cm->countOfCols;
  Cm->RowLink->ID=0;
  Cm->RowLink->NumberOf1=0;
  Rows=Cm->RowLink;
  if (Cm->countOfRows>1)
  for ( I=2;I<=Cm->countOfRows;I++)
   {
     Rows->Next=new CLink;
     if ( Rows->Next==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

     Rows->Next->Previous=Rows;
     Rows=Rows->Next;
     Rows->Offset=I*Cm->countOfCols*sizeof(char);
     Rows->ID=I-1;
     Rows->NumberOf1=0;
     Rows->Next=0;
   }
  else  Rows->Next=0;
  //Create column links
  Cm->ColLink = new CLink;
  if ( Cm->ColLink==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

  Cm->ColLink->Previous=0;
  Cm->ColLink->Offset=0;
  Cm->ColLink->NumberOf1=0;
  Cm->ColLink->ID=Cm->countOfCols-1;
  
  Cm->ColLink->Cost=Costs[Cm->countOfCols-1];//cost of the column is kept at the beginning
				//of array
  uBound+=Cm->ColLink->Cost;//upper bound is computed here
  Columns=Cm->ColLink;
  if (Cm->countOfCols>1)
  for ( I=Cm->countOfCols-2;I>=0;I--)
   {
     Columns->Next=new CLink;

     if ( Columns->Next==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

     Columns->Next->Previous=Columns;
     Columns=Columns->Next;
     Columns->Offset=I*sizeof(char);
     Columns->ID=I;
     Columns->NumberOf1=0;
     Columns->Cost=Costs[I];//cost of column
     if (Costs[I]<0)printf("c %d",Costs[I] );
     uBound+=Columns->Cost;//increase upper bound
     Columns->Next=0;
   }
  else  Columns->Next=0;
   uBound++;
   MaxCost=uBound;
   }
   else {Cm->RowLink=0;Cm->ColLink=0;}
}


void FindNumberOf1 ( struct CoveringMatrix *CM )
{//function to find number of ones in rows and columns
 int One;//tahle funkce najde pocty jednicek v radcich a sloupcich a zaroven odstrani vsechny sloupce,ktere nemaji zadne jednicky
 struct CLink *Columns,*colWithoutOnes;
 struct CLink *Rows;
 CM->countOfOnes=0;
  Rows=CM->RowLink;
  while ( Rows!=0)
   {
     Rows->NumberOf1=0;
     Rows=Rows->Next;
   }
 Columns=CM->ColLink;
 while ( Columns!=0)
  {
    Columns->NumberOf1=0;  
    One=0;
    Rows=CM->RowLink;
  while ( Rows!=0)
   {
    One = CM->Array[Columns->ID][Rows->ID];
    if (One )
     {
       Rows->NumberOf1+=One;
       Columns->NumberOf1+=One;
       CM->countOfOnes++;
     }
    Rows=Rows->Next;
   }
   if (Columns->NumberOf1==0)
   {
    colWithoutOnes=Columns;
   
    Columns=Columns->Next;
    remove_Col_From_Matrix(CM,colWithoutOnes);
   
   }
   else Columns=Columns->Next;
  }
   Rows=CM->RowLink;
  while ( Rows!=0)
   {
   
     Rows=Rows->Next;
   }
}


void R_Dominance ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolutionUCP )
{//reduce the matrix by row dominance
  int Dominance;
  struct CLink *RowLink;
  struct CLink *Aux;
  struct CLink *ColLink;
  struct CLink *EssentialColumn;
  struct CLink *ComparedRow;
  int Dirty=0;
   int NumberOf1;

  
 FindNumberOf1(CM);
 ComparedRow=CM->RowLink;
  while ( ComparedRow != 0 )  //Row to compare
   {
      RowLink=CM->RowLink;  //
		//Other rows are compared,looking for dominance
      while ( RowLink!=0 )
	{
	  Dominance=0;
	  if (ComparedRow->NumberOf1>RowLink->NumberOf1)
	  {//there is no chance dominance
      RowLink=RowLink->Next;
    }
    else
    {
	  ColLink=CM->ColLink;
	  NumberOf1=0;
	  EssentialColumn=NULL;
	  while ( ColLink!=0 )
	   {

	     if ( CM->Array[ColLink->ID][ComparedRow->ID]==1 )
	      {
	      if ( CM->Array[ColLink->ID][RowLink->ID] ==1 )
	      {   //if ComparedRow has ones at the same position as the second,domitates
		if ( Dominance!=-1 ) Dominance=1;
	      }
	      else  { Dominance=-1; }//dominance failed
	      EssentialColumn=ColLink;
	      NumberOf1++;
	     }
	    ColLink=ColLink->Next;
	   }
	  if (Dominance==1&&RowLink->ID!=ComparedRow->ID)
	    {//if copare row with itself,it cannot be removed
		Aux=RowLink->Next;
		remove_Row_From_Matrix (CM,RowLink );
		Dirty = 1;
	    }
	  else Aux=RowLink->Next;
	 RowLink=Aux;
      }
      }
     if ( NumberOf1==1)
     {//if row is covered by only one column,it is esential column,
      //will be added to solution and removed from matrix with
      //rows it covers
	AddToSolution ( SolutionUCP,EssentialColumn);
	Aux=ComparedRow->Next;
	RemoveColWithRows(EssentialColumn,CM);
	Dirty = 1;
	ComparedRow=Aux;
     }
   else ComparedRow=ComparedRow->Next;
  }
CM->Dirty=Dirty;
}

void S_Dominance ( struct CoveringMatrix *CM)
{//reduce the matrix by column dominance
  int Dominance;
  int Dirty=0;
  struct CLink *RowLink;
  struct CLink *Aux;
  struct CLink *ColLink;
  struct CLink *ComparedCol;
  
  FindNumberOf1(CM);

  ComparedCol=CM->ColLink;
  while ( ComparedCol != 0 )  //Column to compare
   {
  ColLink=CM->ColLink;
  while ( ColLink!=0 )
	{
	if (ComparedCol->NumberOf1<ColLink->NumberOf1)
	{//there is no chance dominance
    ColLink=ColLink->Next;
  }
	else {
	  
	  Aux=ColLink->Next;
	  if ( ColLink->ID!=ComparedCol->ID )
	  {//To disable compare column with itself
	   if (CM->ColLink==0) printf("Nula3");
	  Dominance=0;
	  
	  RowLink=CM->RowLink;
	  while ( RowLink!=0 )
	   {
	    if (CM->Array[ColLink->ID][RowLink->ID] ==1 )
	      if ( CM->Array[ComparedCol->ID][RowLink->ID] ==1 )
	      {   //if ComparedCol has ones at the same position as second col
		  //it has less ones than second column,will be removed
		      Dominance=1;
	      }
	      else  { Dominance=0; break; }//dominance failed
	    RowLink=RowLink->Next;
	   }
	  if (Dominance==1)  //column will be renoved here
	    {
		if ( ColLink->Cost >= ComparedCol->Cost ) //remove/add comment to keep
							  //column with less cost than copared col
							  //in matrix
		  {
		    remove_Col_From_Matrix (CM,ColLink );
		    Dirty = 1;
		  }
	    }
	  }
	 ColLink=Aux;
	}
	}

   ComparedCol=ComparedCol->Next;
  }
   CM->Dirty=Dirty;

//  return CM;
}




int SolveDominance ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolutionUCP )
{ //Reduce matrix with dominance relations
int ColDom=0,return_Value=0;
 if ( CM->ColLink !=0 )
  {

   CM->Dirty=1;
//Dominance will be solved as long as any change has been made
   while (CM->Dirty)
    {
      R_Dominance(CM,SolutionUCP);
      if (CM->Dirty) return_Value=1;
    	if ( CM->Dirty==1||ColDom==0 )
    	 {
    	  CM->Dirty=0;
    	  S_Dominance(CM);
    	  if (CM->Dirty) return_Value =1;
    	  ColDom=1;
    	 }
    }
 }
 return return_Value;
}





/*****************************************************AURA functions************************/

struct cube *create_Empty_Cube ( void )
{//Structure to create empty header structure to keep domain

   struct cube *domain=0;

   //first allocate memory
   domain=new cube;
     if ( domain==NULL)
       {
       	printf ("Insufficient memory \n");
      	exit(0);
       }
   //and set all antries to zero
    domain->link_To_Domain=0;
  domain->counfOfDomain=0;
  domain->countOfCheapestCols=0;
  domain->Next=0;
  return domain;
}
struct header_Of_Cubes *create_Empty_Header_Cube ( void )
{//Structure to create empty header structure to keep domain

   struct header_Of_Cubes *header=0;

   //first allocate memory
   header=new header_Of_Cubes;
     if ( header==NULL)
       {
	       printf ("Insufficient memory \n");
	       exit(0);
       }
   //and set all antries to zero
    header->link_To_Cube=0;
  header->countOfCubes=0;
  return header;
}


//tohle by melo fungovat
void print_Cube ( cube *cube_of_Matrix)
{
	struct Domain	*domain;
	struct CLink *cols_Covering_Row;
	domain = cube_of_Matrix->link_To_Domain;

	while (domain != 0 )
	{
		cols_Covering_Row=domain->SetC;
		printf("(");
		while (cols_Covering_Row !=0 )
		{
			printf(" %d",cols_Covering_Row->ID);
			cols_Covering_Row=cols_Covering_Row->Next;
		}
		printf(")");
		domain=domain->Next;
		if (domain!=0) printf(" x ");
	}


}


//tohle by melo fungovat
struct Domain *InitDomain (  int numberOfRow )
{//Structure to create empty Domain
   struct Domain *domain=0;
   //first allocate memory
   domain = new struct Domain;
     if ( domain==0)
       {
        	printf ("Insufficient memory \n");
          exit(0);
       }
   //and set all antries to zero
   domain->cheapestColumn=0;
   domain->numberOfRow=numberOfRow;
   domain->countOfCols=0;
   domain->SetC=0;
   domain->Next=0;
   domain->Previous=0;

   return domain;
}

void remove_Col_From_Domain (struct Domain *domain, int required_Col_ID )
{
	struct CLink *Auxiliary,*Auxiliary2;

	Auxiliary = domain->SetC;

	if (Auxiliary!=0)
	{	//if it is firs row in set
		if (Auxiliary->ID == required_Col_ID )
		{
			domain->SetC=Auxiliary->Next;
			delete (Auxiliary);
		}
		else 
		{
			while (Auxiliary->Next->ID!=required_Col_ID &&Auxiliary->Next!=0)//jinak ho musime nalezt
			{
				Auxiliary=Auxiliary->Next;
			}
		if (Auxiliary->Next!=0&& Auxiliary->Next->ID==required_Col_ID)
		{
		Auxiliary2=Auxiliary->Next;//
		Auxiliary->Next=Auxiliary->Next->Next;
		delete (Auxiliary2);
		}
		}
	}
	

}



void add_Col_To_Domain ( struct Domain *domain, struct CLink *Column ) 
{

	struct CLink *Auxiliary;
	struct CLink *Auxiliary2;


	Auxiliary = new CLink;
	if ( Auxiliary == NULL ) {
		printf ("Insufficient memory \n");
	  	exit(0);
      }

	Auxiliary->ID = Column->ID;
	Auxiliary->Cost = Column->Cost;
	Auxiliary->Offset=Column->Offset;
	Auxiliary->Next = 0;
  domain->countOfCols++;

	if ( domain->SetC == 0) {
		domain->SetC = Auxiliary;
		domain->cheapestColumn=Column->Cost;

	}
	else {
		Auxiliary2 = domain->SetC;
		while ( Auxiliary2->Next != 0 ) Auxiliary2 = Auxiliary2->Next;
		Auxiliary2->Next = Auxiliary;
		if (domain->cheapestColumn>Column->Cost)//if col is cheapest, set it to cheapestColumn 
		  domain->cheapestColumn=Column->Cost;
	}
  
}




void find_Cols_Covering_Row (  struct CoveringMatrix *CM, struct CLink *SelectedRow, struct Domain *SelectedRowDomain ) {

	struct CLink *ColLink;
	struct CLink *RowLink;
	//unsigned char *RowOffset;

	ColLink = CM->ColLink;


	while ( ColLink != 0 ) {
		if ( CM->Array[ColLink->ID][SelectedRow->ID] == 1 )  add_Col_To_Domain (SelectedRowDomain, ColLink );
		ColLink = ColLink->Next;
	}

}
void Release ( struct cube *cube_of_Matrix )
{
	struct Domain *Aux_Domain,*Aux2_Domain;
	struct CLink *AuxSetC,*Aux2SetC;
	Aux_Domain=cube_of_Matrix->link_To_Domain;
	if (cube_of_Matrix!=0)
	{
	while ( Aux_Domain !=0 )
	{

		AuxSetC=Aux_Domain->SetC;
		while (AuxSetC != 0 )
		{
			Aux2SetC=AuxSetC;
			AuxSetC=AuxSetC->Next;
			delete (Aux2SetC);
		}
		Aux2_Domain=Aux_Domain;
		Aux_Domain=Aux_Domain->Next;
		delete (Aux2_Domain);
	}
	delete (cube_of_Matrix);
  }

}
void Release (struct header_Of_Cubes *header)
{
  struct cube *cube_of_Matrix,*Auxiliary ;
  struct Domain *Aux_Domain,*Aux2_Domain;
  struct CLink *AuxSetC,*Aux2SetC;
  
  cube_of_Matrix=header->link_To_Cube;
  while(cube_of_Matrix!=0)
  {
  
 
    Aux_Domain=cube_of_Matrix->link_To_Domain;
  	while ( Aux_Domain !=0 )
	  {

	 	  AuxSetC=Aux_Domain->SetC;
		  while (AuxSetC != 0 )
		  {

		  	 Aux2SetC=AuxSetC;
		   	AuxSetC=AuxSetC->Next;
		  	delete (Aux2SetC);
		  }
		  Aux2_Domain=Aux_Domain;
		  Aux_Domain=Aux_Domain->Next;
		  delete (Aux2_Domain);
	  }
    Auxiliary=cube_of_Matrix;
    cube_of_Matrix=cube_of_Matrix->Next;

    delete(Auxiliary);

  }
  delete(header);
}

void Release ( struct Domain* Aux_Domain)
{
	struct CLink *AuxSetC,*Aux2SetC;
		AuxSetC=Aux_Domain->SetC;
		while (AuxSetC != 0 )
		{
			Aux2SetC=AuxSetC;
			AuxSetC=AuxSetC->Next;
			delete (Aux2SetC);
		}
		delete (Aux_Domain);


}
void Release ( struct CLink* Pomocny_SetC)
{
	struct CLink *AuxSetC,*Aux2SetC;
		AuxSetC=Pomocny_SetC;
		while (AuxSetC != 0 )
		{
			Aux2SetC=AuxSetC;
			AuxSetC=AuxSetC->Next;
			delete (Aux2SetC);
		}
	

}
void add_Row_To_Matrix (struct CoveringMatrix *CM, struct CLink *RowLink)
{
	struct CLink *AuxRow,*Aux1;
	
	AuxRow = new CLink;
	if ( AuxRow == NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }
	AuxRow->Previous=0;
	AuxRow->Next=0;
	AuxRow->Offset=RowLink->Offset;
	AuxRow->ID=RowLink->ID;
	AuxRow->NumberOf1=RowLink->NumberOf1;//copy data
	CM->countOfRows++;
		

	if ( CM->RowLink == 0 )
	  CM->RowLink = AuxRow;//if matrix is empty, set it firs row
	else 
	{
		Aux1=CM->RowLink;
		while (Aux1->Next != 0 )
		{
			Aux1=Aux1->Next;
		}
		Aux1->Next=AuxRow;
		AuxRow->Previous=Aux1;
	}


}


struct Domain *copy_Domain (struct Domain *source_Domain)
{
  struct Domain *Auxi;
  struct CLink *Auxiliary1;
  Auxi=InitDomain(source_Domain->numberOfRow);
 
  Auxiliary1=source_Domain->SetC;
  
  Auxi->numberOfRow=source_Domain->numberOfRow;
  Auxi->cheapestColumn=source_Domain->cheapestColumn;
  Auxi->countOfCols=source_Domain->countOfCols;
  while (Auxiliary1!=0)
  {
    add_Col_To_Domain (Auxi,Auxiliary1);
    Auxiliary1=Auxiliary1->Next;
  }
  return Auxi;
}
void add_Domain_To_Cube ( struct cube *cube_of_Matrix,struct Domain* source_Domain)

{
	struct Domain *Auxi,*Kopirovana;
	if (cube_of_Matrix->link_To_Domain==0)
	{
    cube_of_Matrix->link_To_Domain=source_Domain;
  }
  else
  {
    Auxi=cube_of_Matrix->link_To_Domain;
    while (Auxi->Next!=0)
    Auxi=Auxi->Next;
    Auxi->Next=source_Domain;
  }
  cube_of_Matrix->counfOfDomain++;
  cube_of_Matrix->countOfCheapestCols+=source_Domain->cheapestColumn;
  
}
void add_Cube_To_Header ( struct header_Of_Cubes *header, struct cube *cube_of_Matrix)

{
	struct cube *Auxi;
	if (header->link_To_Cube==0)
	{
    header->link_To_Cube=cube_of_Matrix;
  }
  else
  {
    Auxi=header->link_To_Cube;
    while (Auxi->Next!=0)
    Auxi=Auxi->Next;
    Auxi->Next=cube_of_Matrix;
  }
  header->countOfCubes++;
  
}
void find_Cube_Of_Matrix ( struct CoveringMatrix *CM, struct cube *cube_of_Matrix)

{
	struct CLink *Auxiliary_RowLink;
	struct Domain *Aux_Domain;
	struct Domain *Aux2_Domain;

	Auxiliary_RowLink = CM->RowLink;

	while ( Auxiliary_RowLink != 0 )
	   {
	
		Aux_Domain = InitDomain(Auxiliary_RowLink->ID);
		
		find_Cols_Covering_Row ( CM,Auxiliary_RowLink,Aux_Domain );

		if ( cube_of_Matrix->link_To_Domain == 0 )	{
			cube_of_Matrix->link_To_Domain = Aux_Domain;
		}
		else {
			Aux2_Domain=cube_of_Matrix->link_To_Domain;
			while ( Aux2_Domain->Next != 0 ) Aux2_Domain = Aux2_Domain->Next;
			Aux2_Domain->Next = Aux_Domain;

		}
		cube_of_Matrix->counfOfDomain++;
    cube_of_Matrix->countOfCheapestCols+=Aux_Domain->cheapestColumn;
		Auxiliary_RowLink=Auxiliary_RowLink->Next;
	   }
}

struct Domain *make_Domain_Intersection ( struct CLink *Domain_Row1, struct CLink *Domain_Row2)

{
	struct CLink *Auxiliary1,*Auxiliary2;
	Auxiliary1=Domain_Row2;
	struct Domain *intersection;

	intersection = InitDomain (0);

	while ( Domain_Row1!=0 )
	{
		Auxiliary1=Domain_Row2;
		while (Auxiliary1!=0)
		{
			if ( Domain_Row1->ID == Auxiliary1->ID )
			add_Col_To_Domain (intersection,Auxiliary1);		
			Auxiliary1=Auxiliary1->Next;
		}
		Domain_Row1=Domain_Row1->Next;
	}
	return intersection;
}
struct Domain  *make_Difference_Domain ( struct CLink *Domain_Row2, struct CLink *Domain_Row1)
// 
{
	struct CLink *Auxiliary1,*Auxiliary2;
	Auxiliary1=Domain_Row2;
	struct Domain *difference;
  int contain;
	difference = InitDomain (0);

	while ( Domain_Row1!=0 )
	{
		Auxiliary1=Domain_Row2;
		contain=0;
		while (Auxiliary1!=0)
		{//if row is contained in first domain
			if ( Domain_Row1->ID == Auxiliary1->ID ) contain=1;
			Auxiliary1=Auxiliary1->Next;
		}
		if (!contain) add_Col_To_Domain (difference,Domain_Row1);
		Domain_Row1=Domain_Row1->Next;
	}
	return difference;
}


int evaluate_Row (struct CoveringMatrix *CM,struct CLink *PomocnyRadek)
{
  struct CLink *AuxiliaryCol;
  AuxiliaryCol=CM->ColLink;
   int SP=0;
  if (PomocnyRadek==0) return -1;
  while (AuxiliaryCol!=0)
  {
    if ( CM->Array[AuxiliaryCol->ID][PomocnyRadek->ID] )
    {
      SP+=AuxiliaryCol->NumberOf1;
      
      
    }
    AuxiliaryCol=AuxiliaryCol->Next;
  }
  return SP;

}




struct CoveringMatrix * create_Matrix_Of_Rows_MSIR ( struct CoveringMatrix *original_Matrix,struct CoveringMatrix *original_Matrix_Without_MSIR)
//creaate matrix with rows MSIR, set colls is the same as in the original matrix
{//
  struct CLink *Aux1;
  struct CLink *Aux2;
  struct CLink *RowWithMin1;
  struct CLink *Column;

  struct CLink *Columns;
  struct CLink *Rows;
  struct CLink *original_Matrix_RowLink;
  struct CLink *original_Matrix_ColLink;

  int MinCost=0;
  int Independent,RP1,RP2;
  struct CoveringMatrix *matrix_MSIR=0;

  matrix_MSIR=new CoveringMatrix; // nejprve vytvorime novou matici
  if ( matrix_MSIR==NULL)
       {
	        printf ("Insufficient memory \n");
	        exit(0);
       }

  matrix_MSIR->countOfCols=original_Matrix->countOfCols;
  matrix_MSIR->countOfRows=0;
  matrix_MSIR->Cost=original_Matrix->Cost;
  matrix_MSIR->Array=original_Matrix->Array;
  matrix_MSIR->ColLink=0;
  matrix_MSIR->RowLink=0;
  
  original_Matrix_RowLink=original_Matrix->RowLink;
  original_Matrix_ColLink=original_Matrix->ColLink;



 if ( original_Matrix->ColLink!=NULL )
     {//copy all cols to MSIR matrix
       matrix_MSIR->ColLink = new CLink;
       if ( matrix_MSIR->ColLink==NULL)
       {
	       printf ("Insufficient memory \n");
	       exit(0);
       }

       matrix_MSIR->ColLink->Previous=NULL;
       matrix_MSIR->ColLink->Next=NULL;
       matrix_MSIR->ColLink->Offset=original_Matrix->ColLink->Offset;
       matrix_MSIR->ColLink->NumberOf1=original_Matrix->ColLink->NumberOf1;
       matrix_MSIR->ColLink->Cost=original_Matrix->ColLink->Cost;
       matrix_MSIR->ColLink->ID=original_Matrix->ColLink->ID;
       Columns=matrix_MSIR->ColLink;
       original_Matrix_ColLink=original_Matrix->ColLink->Next;
	//Sel all antries of created link to
	//values of link of original matrix

	while ( original_Matrix_ColLink!=NULL )
	{
      Columns->Next=new CLink;
      if ( Columns->Next==NULL )
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

      Columns->Next->Previous=Columns;
      Columns=Columns->Next;
      Columns->Offset=original_Matrix_ColLink->Offset;
      Columns->ID=original_Matrix_ColLink->ID;
      Columns->NumberOf1=original_Matrix_ColLink->NumberOf1;
      Columns->Cost=original_Matrix_ColLink->Cost;
      Columns->Next=NULL;
      original_Matrix_ColLink=original_Matrix_ColLink->Next;
	//Sel all antries of created link to
	//values of link of original matrix
      }
    }





while ( original_Matrix->RowLink!=0 )
  {
  Aux1=original_Matrix->RowLink;
  Aux2=original_Matrix->RowLink->Next;
  FindNumberOf1 (original_Matrix);
  RowWithMin1=original_Matrix->RowLink;
  while (Aux2!=0 )//zde se nalezne radek s nejmene jednickami
    {  //The less ones row has,the greater chance to be independent
      //select row with minimum ones
        RP1=evaluate_Row(original_Matrix,Aux2);
        RP2=evaluate_Row(original_Matrix,RowWithMin1);
        if (RP1<RP2) RowWithMin1=Aux2;
      Aux2=Aux2->Next;
    }

  while (Aux1!=0 )
   {
    if ( Aux1!=RowWithMin1 )
    {
     Column=original_Matrix->ColLink;
     Independent=0;
     while ( Column!=0 )
      {
       if ( original_Matrix->Array[Column->ID][Aux1->ID] ==1 )//pokud radek a matice ma jednicku,nesmi to byt ten s nejmene jednickami
	 if ( original_Matrix->Array[Column->ID][RowWithMin1->ID] ==0 )//a radek s nejmene jednickami jednicku nema,je sance ze nejsou pokryty jednim sloupcem
	   {
	     Independent=1;
	   }
	 else { Independent=0;break; }
       Column=Column->Next;
      }
     if ( Independent )//if independent,continue with next row
      {
	 Aux1=Aux1->Next;
       }
     else
	{
	  Aux2=Aux1->Next;
	  remove_Row_From_Matrix ( original_Matrix,Aux1 );//else remove from matrix
	  Aux1=Aux2;
	}
    }
    else 
    {
	Aux1=Aux1->Next;  //To disable compare row with itself
    }
   }


  add_Row_To_Matrix( matrix_MSIR , RowWithMin1 );//add to MSIR matrix
  remove_Row_From_Matrix ( original_Matrix,RowWithMin1 );
  remove_Row_From_Matrix ( original_Matrix_Without_MSIR, RowWithMin1 );

 }
 return matrix_MSIR; //else independent row is found,increase MSIR
}



void print_Cube_Header (struct header_Of_Cubes *header)
{
  struct cube *AuxCube;
  struct Domain *AuxDomain;
  struct CLink *link_To_Cols;
  
  AuxCube=header->link_To_Cube;
  while (AuxCube!=0)
  {
    AuxDomain=AuxCube->link_To_Domain;
    while (AuxDomain!=0)
    {
      link_To_Cols=AuxDomain->SetC;
      printf("(");
      while (link_To_Cols!=0)
      {
        printf(" %d",link_To_Cols->ID);
        link_To_Cols=link_To_Cols->Next;
      }
      printf(")");
      if(AuxDomain->Next!=0) printf(" x ");
      AuxDomain=AuxDomain->Next;
    }
    printf("\n");
    AuxCube=AuxCube->Next;
  }
}




/*****************************************************end AURA functions***********************/





/****************************************************************************************************/
/****************************************************************************************************/
/******************covering algorithm****************************************************************/
/****************************************************************************************************/
/****************************************************************************************************/
/****************************************************************************************************/


int FindMSIR ( struct CoveringMatrix *CM,int MSIR )

{//Function to find Number of MSIR
  struct CLink *Aux1;
  struct CLink *Aux2;
  struct CLink *RowWithMin1;


  struct CLink *Column;
  int Independent,RP1,RP2;
  int MinCost=0;
  if ( CM->RowLink!=0 )
  {
  Aux1=CM->RowLink;
  Aux2=CM->RowLink->Next;
  FindNumberOf1 (CM);
  RowWithMin1=CM->RowLink;
  while (Aux2!=0 )
    { //The less ones row has,the greater chance to be independent
      //select row with minimum ones
       RP1=evaluate_Row(CM,Aux2);
       RP2=evaluate_Row(CM,RowWithMin1);
        if (RP1<RP2) RowWithMin1=Aux2;
      Aux2=Aux2->Next;
      
    }

  Independent=0;
  while (Aux1!=0 )
    {
    if ( Aux1!=RowWithMin1 )
    {
     Column=CM->ColLink;
     while ( Column!=0 )
      {//Find all dependent rows and remove them from matrix
        if ( CM->Array[Column->ID][Aux1->ID]==1 )
	         if ( CM->Array[Column->ID][RowWithMin1->ID]==0 )
	         {
	           Independent=1;
	         }
	         else { Independent=0;break; }
       Column=Column->Next;
      }
      if ( Independent )
       {
	       Aux1=Aux1->Next;
       }
      else
	{
	  Aux2=Aux1->Next;
	  remove_Row_From_Matrix ( CM,Aux1 );
	  Aux1=Aux2;
	}
     }
     else Aux1=Aux1->Next;  //To disable compare row with itself
    }
  Aux1=CM->ColLink;
  while ( Aux1!=NULL)
   {
     if ( CM->Array[Aux1->ID][RowWithMin1->ID]  )
       {
	 if ( !MinCost ) MinCost=Aux1->Cost;
	   else if ( Aux1->Cost<MinCost ) MinCost=Aux1->Cost;
       }
     Aux1=Aux1->Next;
   }
  MSIR+=MinCost;

  remove_Row_From_Matrix ( CM,RowWithMin1 );
  MSIR=FindMSIR ( CM,MSIR );
 }
 return MSIR; //else independent row is found,increase MSIR
}



float evaluate_Column (struct CoveringMatrix *CM,struct CLink *AuxiliaryCol)
{
  struct CLink *PomocnyRadek;
  PomocnyRadek=CM->RowLink;

  float SP=0;
  
  while (PomocnyRadek!=0)
  {
    if ( CM->Array[AuxiliaryCol->ID][PomocnyRadek->ID]  )
      SP+=(float)1/PomocnyRadek->NumberOf1;
      
    PomocnyRadek=PomocnyRadek->Next;
  }
  return SP;

}

struct CLink* select_Col_Contrib (struct CoveringMatrix *CM)
{
  struct CLink *ColLink;
 struct CLink *SelectedColumn;
 float SP1,SP2;
 
 FindNumberOf1(CM);
 if ( CM->ColLink !=0 )
    {
    ColLink=CM->ColLink;
    SelectedColumn=CM->ColLink;
    while ( ColLink!=0 )
      {
        SP1=evaluate_Column (CM,ColLink);
        SP1/=(float)ColLink->Cost;
        SP2=evaluate_Column (CM,SelectedColumn);
        SP2/=SelectedColumn->Cost;
        if (SP1>SP2) SelectedColumn=ColLink;
        ColLink=ColLink->Next;
      }	     
	    
     }
 return SelectedColumn;

}


/**************************************************heuristics********************************************************/

int FindEssential ( struct CoveringMatrix *CM, struct header_of_solution_UCP *SolUCP ) {

 struct CLink *ColLink;
 struct CLink *RowLink;
 struct CLink *EssentialColumn;
 struct CLink *Aux;


EssentialColumn = new CLink;
Aux = new CLink;

 int ColID;
 int essential; 	// essential = 0 - pocatecni nastaveni
			            // essential = 1 - radek contain jedino jednicku
			            // essential = 2 - radek contain vice jednicek 

 RowLink = CM->RowLink;
 

 while ( RowLink!=0 ) {

	ColLink = CM->ColLink;
	essential = 0;
	ColID = 0;

	while ( ColLink!=0 ) {
	  if ( CM->Array[ColLink->ID][RowLink->ID]==1  ) {  // jestlize radek contain jen jednu 1, essential se nastavi na hodnotu 1
		if ( essential == 0 ) {


			essential = 1;
			EssentialColumn = ColLink;
			ColID = ColLink->ID;
		}
		else if ((essential == 1 || essential == 2) && (ColID != ColLink->ID)){


			essential = 2;
			EssentialColumn = 0;
		}		
	  }
	  ColLink=ColLink->Next;
   	}
	
	if ( essential == 1) {

		AddToSolution ( SolUCP,EssentialColumn);
	    RemoveColWithRows( EssentialColumn, CM);
		FindEssential ( CM, SolUCP ); 
		return 0;
	}else RowLink = RowLink->Next;
 }

 return 0;
}

int RothHeuristicPositiv ( struct CoveringMatrix *CM, struct header_of_solution_UCP *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *BestColumn;   // sloupec s nejhorsi cenou, jenz bude odebran

int val,random2 ;


 int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float bestvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 

ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

BestColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 bestvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		//RowOffset = CM->Array + RowLink->Offset;
		if ( CM->Array[ColLink->ID][RowLink->ID]==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			
			columnvalue = ( 1 / (float) columncost ) ; // spoctena hodnota sloupce
			break;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota sloupce %d je %f  ",ColLink->ID, columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue > bestvalue || bestvalue == -1 ) {  // jestlize jsme nalezli sloupec s horsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		BestColumn = ColLink;
		bestvalue = columnvalue;
	} 

	if ( columnvalue == bestvalue ) { 
	random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//	   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			BestColumn = ColLink;
//			bestvalue = columnvalue;
		}
	}

	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejhorsi (nejnizsi) hodnotou mame ulozen v promene WorstColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
  AddToSolution ( SolUCP,BestColumn );   //... pridame ho tedy do reseni 
  RemoveColWithRows ( BestColumn,CM );  // ... a odebereme ho z matice

 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}

 int ServitHeuristic ( struct CoveringMatrix *CM, struct header_of_solution_UCP *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *WorstColumn;   // sloupec s nejhorsi cenou, jenz bude odebran

int val,random2 ;
float one = 1;

 int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float worstvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 float fractionalvalue=0; // pomocna promenna pro vypocet hodnoty sloupce ( uchovava se v ni castecna cena sloupce, 
				     // ktera musi byt invertovana, nez bude vynasobena se zbytkem )


ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

WorstColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 worstvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		//RowOffset = CM->Array + RowLink->Offset;
		if ( CM->Array[ColLink->ID][RowLink->ID]==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			Aux = CM->ColLink;
			while ( Aux != 0 ) {                  //... projdeme vsechny sloupce radku v nemz ta jednicka byla

				if ( CM->Array[Aux->ID][RowLink->ID]==1 ) { 
					fractionalvalue = fractionalvalue + ( one/(float)Aux->Cost );
	//				printf ("Fraction hodnota je je %f  ", fractionalvalue);
				}
				Aux = Aux->Next;
			}
			columnvalue += ( 1 / (float) columncost ) * ( 1 / fractionalvalue ); // spoctena hodnota sloupce
			fractionalvalue = 0;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota je %f  ", columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue < worstvalue || worstvalue == -1 ) {  // jestlize jsme nalezli sloupec s horsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		WorstColumn = ColLink;
		worstvalue = columnvalue;
	} 
	if ( columnvalue == worstvalue ) { 
		random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			WorstColumn = ColLink;
//			worstvalue = columnvalue;
		}
	}

	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejhorsi (nejnizsi) hodnotou mame ulozen v promene WorstColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
 remove_Col_From_Matrix ( CM, WorstColumn );   //... odebereme ho tedy, protoze vsechny radky ktere pokryva, obsahuji 
                                     //minimalne jeste jednu jednicku a lze je tak pokryt 'lepsim' sloupcem
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}

struct CLink* Vyber_Sloupec_ContribAdd (struct CoveringMatrix *CM)
{
  struct CLink *ColLink;
 struct CLink *SelectedColumn;
 float SP1,SP2;
 int random2;
 FindNumberOf1(CM);
 if ( CM->ColLink !=0 )
    {

 //   Choose(CM);

    ColLink=CM->ColLink;
    SelectedColumn=CM->ColLink;
    while ( ColLink!=0 )
      {
               
        SP1=evaluate_Column (CM,ColLink);
        SP1/=(float)ColLink->Cost;
        SP2=evaluate_Column (CM,SelectedColumn);
        SP2/=SelectedColumn->Cost;
         if (SP1>SP2) SelectedColumn=ColLink;
         else if (SP1==SP2)
         {
    		   random2 = (((double) rand() / 
                       (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
	           if ( random2-1 ) SelectedColumn=ColLink;      
         }
	    ColLink=ColLink->Next;
     }

  }
return SelectedColumn;

}

void ContribAddHeuristic ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolUCP )
{ //Select column with most ones in rows with few ones
 struct CLink *ColLink;
 struct CLink *SelectedColumn;
 while ( CM->RowLink !=0 )
  {
   if ( CM->ColLink!=0)
    {

    SelectedColumn=Vyber_Sloupec_ContribAdd(CM);
    AddToSolution(SolUCP,SelectedColumn);
    
    RemoveColWithRows(SelectedColumn,CM);
    }
   }

}


void NaturalHeuristic ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolUCP )
{ //This heuristic consist in choosing columns which covers the largest
  //number of rows
 struct CLink *ColLink;
 struct CLink *SelectedColumn;
int random2;
 while ( CM->RowLink !=0 )
  {
   
    if ( CM->ColLink !=0 )
    {
    FindNumberOf1(CM);
    ColLink=CM->ColLink;
    SelectedColumn=CM->ColLink;
    while ( ColLink!=0 )
      {//find column with largest number of ones
	  if ( ColLink->NumberOf1==SelectedColumn->NumberOf1 )
	    {
 		if ( ColLink->Cost<SelectedColumn->Cost ) SelectedColumn=ColLink;
		 else if ( ColLink->Cost == SelectedColumn->Cost ) {
		   random2 = (((double) rand() / 
                       (double) RAND_MAX) * 2 + 1);

	           if ( random2-1 ) SelectedColumn=ColLink;
		}
	    }
	  if ( ColLink->NumberOf1>SelectedColumn->NumberOf1 )
	  SelectedColumn=ColLink;
	  ColLink=ColLink->Next;
      }
    if ( SelectedColumn->NumberOf1 !=0 )
     {
      AddToSolution ( SolUCP,SelectedColumn );
     }
      RemoveColWithRows ( SelectedColumn,CM );
    }
   }


 }



/**************************************************heuristika********************************************************/


int select_Best_Uncovered_Row ( struct CoveringMatrix *matrix_Without_MSIR ,struct cube *cube_Of_Matrix_MSIR)
{
  int best_Intersected_Row_Number,intersected_Row_Number,best_Row;
  struct Domain *AuxDomain,*domain_Of_Selected_Row=0,*Auxiliary1;
  float best_Weight=0,weight,count_Cols_Of_Intersection,count_Cols_Of_Domain,count_Cols_Of_Domain_Without_Intersection,w;
  struct CLink *AuxRow;
  struct CLink *Auxiliary2;
  best_Intersected_Row_Number=-1;
  
  AuxRow=matrix_Without_MSIR->RowLink;
  while (AuxRow!=0)
  {
    intersected_Row_Number=0;
    weight=1;
    
    AuxDomain=cube_Of_Matrix_MSIR->link_To_Domain;
    domain_Of_Selected_Row = InitDomain(AuxRow->ID);
    find_Cols_Covering_Row ( matrix_Without_MSIR,AuxRow,domain_Of_Selected_Row );
    while (AuxDomain!=0)
    {
      Auxiliary1=0;
      Auxiliary1=make_Domain_Intersection (AuxDomain->SetC,domain_Of_Selected_Row->SetC);
      count_Cols_Of_Intersection=0;
      if (Auxiliary1->SetC!=0) 
      {
        Auxiliary2=Auxiliary1->SetC;
        intersected_Row_Number++;//count of domains intersecting row
        count_Cols_Of_Intersection=0;
        while (Auxiliary2!=0 ) //size of domain
	      {
          count_Cols_Of_Intersection++; 
		      Auxiliary2=Auxiliary2->Next;
	      }
        Auxiliary2=AuxDomain->SetC;
        count_Cols_Of_Domain=0;
        while (Auxiliary2!=0 )//size of original domain
	      {
          count_Cols_Of_Domain++; 
		      Auxiliary2=Auxiliary2->Next;
	      }
	      count_Cols_Of_Domain_Without_Intersection=count_Cols_Of_Domain-count_Cols_Of_Intersection;
	      w=(float)count_Cols_Of_Domain_Without_Intersection/(float)count_Cols_Of_Domain;
	      weight=weight*w;
	      Release (Auxiliary1);
      }
      else delete (Auxiliary1);
      AuxDomain=AuxDomain->Next;
    }
    Release (domain_Of_Selected_Row);
    if (best_Intersected_Row_Number == -1 || intersected_Row_Number<best_Intersected_Row_Number)
    {
      best_Intersected_Row_Number=intersected_Row_Number;
      best_Weight=weight;
      best_Row=AuxRow->ID;
      
    }
    else 
      if (intersected_Row_Number=best_Intersected_Row_Number)
        {
          if (weight>best_Weight)
          {
              best_Intersected_Row_Number=intersected_Row_Number;
              best_Weight=weight;
              best_Row=AuxRow->ID;
            
          }  
        }
    AuxRow=AuxRow->Next;
  }
  return best_Row;
}

int Add_Set_Of_1intersecting_Rows (struct CoveringMatrix *matrix_Without_MSIR,struct cube *cube_Of_Matrix_MSIR,int Still_To_Raise)
{
    struct CLink *row_Of_Matrix_Without_MSIR,*row_To_Delete;
    struct Domain *AuxDomain,*intersecting_Domain,*intersection,*domain_Of_Row;
    struct CLink *Auxiliary2;   
    int nubmer_Of_Intersected_Domains,intersected_Domain,domain_Reducing;
    
    
    row_Of_Matrix_Without_MSIR=matrix_Without_MSIR->RowLink;
    domain_Reducing=1;
    
    
 while (domain_Reducing) 
 {
    domain_Reducing=0;
    while (row_Of_Matrix_Without_MSIR!=0)
    {//test all rows
      nubmer_Of_Intersected_Domains=0;
      AuxDomain=cube_Of_Matrix_MSIR->link_To_Domain;
      
      while (AuxDomain!=0)
      {//all domains
        if (AuxDomain->cheapestColumn>=Still_To_Raise)
        { 
          Auxiliary2=AuxDomain->SetC;
          intersected_Domain=0;
          while(Auxiliary2!=0)
          {//test intersection row with domain
            
            if ( matrix_Without_MSIR->Array[Auxiliary2->ID][row_Of_Matrix_Without_MSIR->ID] )
            {
                intersected_Domain=1;
                intersecting_Domain=AuxDomain;
            }
            
            Auxiliary2=Auxiliary2->Next;
          }
          if (intersected_Domain) nubmer_Of_Intersected_Domains++;
         } 
          AuxDomain=AuxDomain->Next;
      }
      if (nubmer_Of_Intersected_Domains==1)
      {
        domain_Reducing=1;
        domain_Of_Row=InitDomain(row_Of_Matrix_Without_MSIR->ID);
        find_Cols_Covering_Row(matrix_Without_MSIR,row_Of_Matrix_Without_MSIR,domain_Of_Row);
        intersection=make_Domain_Intersection (domain_Of_Row->SetC,intersecting_Domain->SetC);        
        Release(intersecting_Domain->SetC);
        intersecting_Domain->SetC=intersection->SetC;
        cube_Of_Matrix_MSIR->countOfCheapestCols-=intersecting_Domain->cheapestColumn;
        cube_Of_Matrix_MSIR->countOfCheapestCols+=intersection->cheapestColumn;
        intersecting_Domain->cheapestColumn=intersection->cheapestColumn;
        delete (intersection);
        Release(domain_Of_Row);

        row_To_Delete=row_Of_Matrix_Without_MSIR;
        row_Of_Matrix_Without_MSIR=row_Of_Matrix_Without_MSIR->Next;
        remove_Row_From_Matrix (matrix_Without_MSIR,row_To_Delete);
        
      }

      else if (nubmer_Of_Intersected_Domains==0)
      {
        return 1;
      }
      
      else row_Of_Matrix_Without_MSIR=row_Of_Matrix_Without_MSIR->Next;
     }
  } 
  return 0;
}



struct CoveringMatrix * find_Best_Set_Of_Non_Intersecting_Rows (struct CoveringMatrix *matrix_Without_MSIR,struct cube *cube_Of_Matrix_MSIR)
{
  struct CLink *row_Of_Matrix_Without_MSIR,*row_To_Delete;
  struct Domain *AuxDomain;
  struct CLink *Auxiliary2;
  
  struct CoveringMatrix * BSONIR,*CopyCMForMSIR;

  AuxDomain=cube_Of_Matrix_MSIR->link_To_Domain;
  while (AuxDomain!=0)
     {
          Auxiliary2=AuxDomain->SetC;
          while(Auxiliary2!=0)
          {
            row_Of_Matrix_Without_MSIR=matrix_Without_MSIR->RowLink;
            while (row_Of_Matrix_Without_MSIR!=0)
            {
              if ( matrix_Without_MSIR->Array[Auxiliary2->ID][row_Of_Matrix_Without_MSIR->ID] )
              {
                row_To_Delete=row_Of_Matrix_Without_MSIR;
                row_Of_Matrix_Without_MSIR=row_Of_Matrix_Without_MSIR->Next;
                remove_Row_From_Matrix (matrix_Without_MSIR,row_To_Delete);
              }
              else row_Of_Matrix_Without_MSIR=row_Of_Matrix_Without_MSIR->Next;
            }
            
            Auxiliary2=Auxiliary2->Next;
          }
          AuxDomain=AuxDomain->Next;
     }
  CopyCMForMSIR=Duplicate(matrix_Without_MSIR);
  BSONIR=create_Matrix_Of_Rows_MSIR ( CopyCMForMSIR,matrix_Without_MSIR);//tato procedura z matrix_Without_MSIR odebere radky MSIR
  Release(CopyCMForMSIR);
  return BSONIR;
}

int found_Solution (struct CoveringMatrix *CM,struct cube *cube_of_Matrix,struct header_of_solution_UCP *SolUCP,int Path)
{//select cheapest solution
  struct Domain *AuxDomain;
  struct header_of_solution_UCP *wanted_Solution;
  struct CLink *Auxiliary,*col_Added_To_Solution;
  int lower_Cost,new_Ubound,new_N,return_Value;
   
  struct CLink *Auxiliary2;
  
  wanted_Solution=create_New_Empty_Solution();
  
  AuxDomain=cube_of_Matrix->link_To_Domain;
  while (AuxDomain!=0)
  {
    //all domains
    Auxiliary=AuxDomain->SetC;
    lower_Cost=Auxiliary->Cost;
    col_Added_To_Solution=Auxiliary;
    while(Auxiliary!=0)
    {//aand select cheapest column from them
      if (Auxiliary->Cost<lower_Cost)
      {
        lower_Cost=Auxiliary->Cost;
        col_Added_To_Solution=Auxiliary;
      }
      Auxiliary=Auxiliary->Next;
    }
    AddToSolution (wanted_Solution,col_Added_To_Solution);
    AuxDomain=AuxDomain->Next;
  }
  new_Ubound=wanted_Solution->Cost+Path;
  new_N=parameterN-(uBound-new_Ubound);
  parameterN=new_N;

  uBound=new_Ubound;
  Replace_Solution(wanted_Solution,SolUCP);


  return 0;
}

struct cube *split_Cube ( struct CoveringMatrix *Matice_MSIR,struct CoveringMatrix *matrix_Without_MSIR,struct cube *cube_Of_Matrix_MSIR,struct Domain *domain_Of_Selected_Row)
{//function to split cube into part1 and part2
	struct CLink *cols_Covering_Row_MSIR;
	struct CLink *cols_Covering_Row_Without_MSIR,*Auxiliary2;
	struct Domain *domain_MSIR_Second_Cycle,*domain_1row_Without_MSIR,*found_Domain,*Auxiliary_Copy,*domain_MSIR_First_Cycle,*Auxiliary1;
	struct Domain *domain_Selected_Row_Removed_Intersection;
  struct cube *created_Cube;
  struct header_Of_Cubes *header_Of_Cubes=0;
	 int Cube_ID=0,domain_ID=0,appendDomain;
	 int *nonzeroIntersection;
	
	domain_Selected_Row_Removed_Intersection = copy_Domain(domain_Of_Selected_Row);
  nonzeroIntersection = new int [cube_Of_Matrix_MSIR->counfOfDomain+1];
  for (int i=0;i<=cube_Of_Matrix_MSIR->counfOfDomain;i++)
  nonzeroIntersection[i]=0;
  header_Of_Cubes=create_Empty_Header_Cube();
/********************************************Part1 soldomain****************************************************************************/

  domain_MSIR_First_Cycle=cube_Of_Matrix_MSIR->link_To_Domain;
	Cube_ID=0;
  while (domain_MSIR_First_Cycle!=0)
  {
    created_Cube=create_Empty_Cube();
    appendDomain=1;
    domain_MSIR_Second_Cycle=cube_Of_Matrix_MSIR->link_To_Domain;
    domain_ID=0;
	  while (domain_MSIR_Second_Cycle != 0 )
	  {
	     cols_Covering_Row_Without_MSIR=domain_Of_Selected_Row->SetC;
	     cols_Covering_Row_MSIR=domain_MSIR_Second_Cycle->SetC; //link to sec cols covering 1 row MSIR
  	   if (Cube_ID == domain_ID) 
       {
          Auxiliary1=make_Domain_Intersection (cols_Covering_Row_MSIR,cols_Covering_Row_Without_MSIR);
          if (Auxiliary1->SetC!=0) 
           {
              Auxiliary2=Auxiliary1->SetC;//add to domain
              nonzeroIntersection[domain_ID]=1;//to remember if intersection is non-zero
              while (Auxiliary2!=0 )
	            {//and remove cols from domain 2 row, needed for patr2
                remove_Col_From_Domain ( domain_Selected_Row_Removed_Intersection,Auxiliary2->ID );//domain_Of_Selected_Row will change here,
		            Auxiliary2=Auxiliary2->Next;
	            }
            }  
          else 
          {
            nonzeroIntersection[domain_ID]=0;
            appendDomain=0;
          }
       }
  
       else 
       {       
          if (Cube_ID > domain_ID) 
          {
            if (nonzeroIntersection[domain_ID]) Auxiliary1=make_Difference_Domain (cols_Covering_Row_Without_MSIR,cols_Covering_Row_MSIR);
            else 
            {
                  Auxiliary_Copy=copy_Domain(domain_MSIR_Second_Cycle);                  
                  Auxiliary1=Auxiliary_Copy;
            }
          }  
          else 
           if (Cube_ID < domain_ID) 
              {
                  
                  Auxiliary_Copy=copy_Domain(domain_MSIR_Second_Cycle); 
                  Auxiliary1=Auxiliary_Copy;
              }
        if (Auxiliary1->SetC==0) appendDomain=0;
    
      }
  
      found_Domain=Auxiliary1;//save result
      if (Auxiliary1->SetC!=0 )  
      {
        add_Domain_To_Cube (created_Cube,found_Domain);//add to domain and find next
      }    
      else {
      Release (found_Domain);
      }
	    domain_MSIR_Second_Cycle=domain_MSIR_Second_Cycle->Next;
	    domain_ID++;
	  }
	  if (appendDomain) 
    {  
      //if it is last found cobe of part1, add domain covering row without cols all domains
       add_Cube_To_Header (header_Of_Cubes,created_Cube);
    }
	  else {
     Release (created_Cube);
     }
	  
	  domain_MSIR_First_Cycle=domain_MSIR_First_Cycle->Next;
	  Cube_ID++;
  }

/*************************************************************part 2 soldomain***********************************************************/

  if(domain_Selected_Row_Removed_Intersection->SetC!=0) 
  {
     domain_MSIR_Second_Cycle=cube_Of_Matrix_MSIR->link_To_Domain;
     created_Cube=create_Empty_Cube();
     appendDomain=1;
 	   while (domain_MSIR_Second_Cycle != 0 )
 	   {
        Auxiliary1=make_Difference_Domain (domain_Of_Selected_Row->SetC,domain_MSIR_Second_Cycle->SetC);
        if (Auxiliary1->SetC!=0)
        {
          found_Domain=Auxiliary1;
          add_Domain_To_Cube (created_Cube,found_Domain);
        }
        else 
        {
          appendDomain=0;
          Release (Auxiliary1);
          break;
        }
        domain_MSIR_Second_Cycle=domain_MSIR_Second_Cycle->Next;
        
     }
    if (appendDomain) 
    {
      add_Domain_To_Cube (created_Cube,domain_Selected_Row_Removed_Intersection);
      add_Cube_To_Header (header_Of_Cubes,created_Cube);
    }
    else
      {
          Release ( created_Cube);
      }
  }    
  else 
  {
     delete (domain_Selected_Row_Removed_Intersection);
  }
  created_Cube=header_Of_Cubes->link_To_Cube;
  delete header_Of_Cubes;
  return (created_Cube);
}

/****************************************************AURA*************************************/

int Raiser (  struct CoveringMatrix *CM,struct CoveringMatrix *Matice_MSIR,struct CoveringMatrix *matrix_Without_MSIR,struct cube *cube_Of_Matrix_MSIR,int lbound,struct header_of_solution_UCP *SolUCP,int reduce_Time)
{
	struct CLink *cols_Covering_Row_MSIR;
	struct CLink *cols_Covering_Row_Without_MSIR,*Auxiliary1,*Auxiliary2;
	struct Domain *Domain_1Radku_MSIR,*domain_1row_Without_MSIR,*found_Domain,*Auxiliary_Copy,*domain_MSIR_First_Cycle;
  struct CoveringMatrix *Matice_Bez_MSIR_Kopie;
	struct CLink *rowLink_Selected_Row,*rowsBSONIR;
	struct Domain *domain_Of_Selected_Row,*domain_Selected_Row_Removed_Intersection,*domain_Row_BSONIR;
  struct cube *created_Cube,*AuxCube;
  struct header_Of_Cubes *header_Of_Cubes=0;
	 int Cube_ID=0,domain_ID=0,appendDomain;
	 int *nonzeroIntersection,cost_Domains;
	
  
	int stillToRaise,return_Value,best_Row;
	struct CoveringMatrix *BSONIR,*CopyCMForBSONIR;
	if (stopCover) return 1;

  stillToRaise=lbound + parameterN - cube_Of_Matrix_MSIR->countOfCheapestCols;
	if (stillToRaise <=0 ) {return 1;}
  if (matrix_Without_MSIR->RowLink == 0) 
  {
   return found_Solution (CM,cube_Of_Matrix_MSIR,SolUCP,matrix_Without_MSIR->Cost);
  }
  if (reduce_Time) 
  if (NumCalls++>callUpperBound)
  {
    
    StopTime=GetMyCPUTime();
    if (floor(StopTime-StartTime)>=MaxRunTime ) {stopCover=1;return 1;}
    else NumCalls=0;
    
  } 
  

 /*find BSONIR*/
 CopyCMForBSONIR=Duplicate(matrix_Without_MSIR);
 BSONIR=find_Best_Set_Of_Non_Intersecting_Rows(CopyCMForBSONIR,cube_Of_Matrix_MSIR);
 Release(CopyCMForBSONIR);
 if (BSONIR->RowLink!=0)
 {
  rowsBSONIR=BSONIR->RowLink;
  while (rowsBSONIR!=0)
  {
    domain_Row_BSONIR=InitDomain(rowsBSONIR->ID);
    find_Cols_Covering_Row ( matrix_Without_MSIR,rowsBSONIR,domain_Row_BSONIR );
    add_Domain_To_Cube (cube_Of_Matrix_MSIR,domain_Row_BSONIR );
    stillToRaise-=domain_Row_BSONIR->cheapestColumn;
    remove_Row_From_Matrix(matrix_Without_MSIR,rowsBSONIR);
    if(stillToRaise<=0) return 1;
    rowsBSONIR=rowsBSONIR->Next;
  }
 } 
 Release (BSONIR);
  if (matrix_Without_MSIR->RowLink == 0) 
  {
   return found_Solution (CM,cube_Of_Matrix_MSIR,SolUCP,matrix_Without_MSIR->Cost);
  } 
 Auxiliary_Copy=cube_Of_Matrix_MSIR->link_To_Domain;
 cost_Domains=1;
 while(Auxiliary_Copy!=0)
 {
  if(Auxiliary_Copy->cheapestColumn>cost_Domains)
      cost_Domains=Auxiliary_Copy->cheapestColumn;
  Auxiliary_Copy=Auxiliary_Copy->Next;
 }
 
 //condition to call Add_Set_Of_1intersecting_Rows
 if (stillToRaise <= cost_Domains)
 {
    if (Add_Set_Of_1intersecting_Rows(matrix_Without_MSIR,cube_Of_Matrix_MSIR,stillToRaise))return 1;
        stillToRaise=lbound + parameterN - cube_Of_Matrix_MSIR->countOfCheapestCols;
        if (stillToRaise <=0 ) return 1;
    
     if (matrix_Without_MSIR->RowLink == 0) 
     {
        return found_Solution (CM,cube_Of_Matrix_MSIR,SolUCP,matrix_Without_MSIR->Cost);
     } 
 }
  //select best row
  best_Row=select_Best_Uncovered_Row ( matrix_Without_MSIR,cube_Of_Matrix_MSIR );
	rowLink_Selected_Row=matrix_Without_MSIR->RowLink;
	while (rowLink_Selected_Row->ID!=best_Row) rowLink_Selected_Row=rowLink_Selected_Row->Next; 
  header_Of_Cubes=create_Empty_Header_Cube();

	if (rowLink_Selected_Row!=0)
	{
    domain_Of_Selected_Row = InitDomain(rowLink_Selected_Row->ID);
    find_Cols_Covering_Row ( matrix_Without_MSIR,rowLink_Selected_Row,domain_Of_Selected_Row );
    remove_Row_From_Matrix (matrix_Without_MSIR,rowLink_Selected_Row);  
    header_Of_Cubes->link_To_Cube=split_Cube (Matice_MSIR,matrix_Without_MSIR,cube_Of_Matrix_MSIR,domain_Of_Selected_Row);
    Release (domain_Of_Selected_Row);
  }  
  AuxCube=header_Of_Cubes->link_To_Cube;
  return_Value=1;
  while (AuxCube!=0)
  {
    Matice_Bez_MSIR_Kopie=Duplicate(matrix_Without_MSIR);
    if (Raiser (CM,Matice_MSIR,Matice_Bez_MSIR_Kopie,AuxCube,lbound,SolUCP,reduce_Time)==0) return_Value=0;
    Release (Matice_Bez_MSIR_Kopie);
    if (stopCover) break;
    AuxCube=AuxCube->Next;
  
  }
  Release (header_Of_Cubes);
 return return_Value;
}
  

 int BABAURA2 ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolUCP,int reduce_Time )
{//Aura Solver
   struct CLink *SelectedColumn,*SelectedColumn2;
   struct CoveringMatrix *CopyCM2;
   struct CoveringMatrix *CopyCMForMSIR;
   struct header_of_solution_UCP *SolUCP2;
   struct header_of_solution_UCP *SolUCP1;
   struct header_of_solution_UCP *solution_From_Dominance;
   struct header_Of_Set_MSIR *SetMSIR;
    int MSIR=0;
   int lbound_New,difference;
   
   struct cube *cube_Of_Matrix_MSIR;
   struct CoveringMatrix *matrix_Without_MSIR;
   int lBound=0,raiserLowerBound=0,raiserAnswer=0,volani_Raiser=0,ID_Col_To_Remove;
   struct header_of_solution_UCP *SolRaiser;
   struct CoveringMatrix *matrixMSIR;
   
   if (stopCover) {uBound=MaxCost;return 1;}
   NumCalls+=10;
   solution_From_Dominance=create_New_Empty_Solution();//Solution given by essential columns

   SolveDominance(CM,solution_From_Dominance);
   CM->Cost+=solution_From_Dominance->Cost;
	 AppendSolution (solution_From_Dominance,SolUCP );
     

   if ( CM->ColLink!=0&&CM->RowLink!=0)
   {
   /************find MSIR***********/
    
     FindNumberOf1(CM);//needed for MSIR and will remove all zero columns from matrix 
     CopyCMForMSIR=Duplicate(CM);//Duplicate matrix for MSIR computation
     MSIR=FindMSIR(CopyCMForMSIR,MSIR);
     Release(CopyCMForMSIR);
     lbound_New=CM->Cost+MSIR;
     difference = uBound-lbound_New ;
     if (difference <= 0 ) 
      {
        SolUCP->Cost=MaxCost;
        return 1;
      }
     else if (difference<=maxRaiser)
      {
          
          matrix_Without_MSIR=Duplicate(CM); //save oroginal matrix
          CopyCMForMSIR=Duplicate(CM);
          matrixMSIR=create_Matrix_Of_Rows_MSIR ( CopyCMForMSIR,matrix_Without_MSIR);//and remove MSIR rows from matrix
          SolRaiser=create_New_Empty_Solution();
          cube_Of_Matrix_MSIR = create_Empty_Cube ();
          find_Cube_Of_Matrix ( matrixMSIR, cube_Of_Matrix_MSIR);
          raiserLowerBound=cube_Of_Matrix_MSIR->countOfCheapestCols;
          parameterN=difference;
          
          raiserAnswer = Raiser (CM,matrixMSIR,matrix_Without_MSIR,cube_Of_Matrix_MSIR,raiserLowerBound,SolRaiser,reduce_Time);
          
          Release (CopyCMForMSIR);
          Release (matrix_Without_MSIR);
          Release (matrixMSIR);
          Release (cube_Of_Matrix_MSIR); 
          if (raiserAnswer == 1) 
            {
              SolUCP->Cost=MaxCost;
              Release(SolRaiser);
              return 1;
            } 
          else 
            {
              AppendSolution(SolRaiser,SolUCP); 
              return 0;
            }      
      }  
    }  
   /****************if CM is empty****************/
   if ( CM->ColLink==0||CM->RowLink==0 )
    {
      
	    if ( CM->Cost<uBound )
    	{
        uBound=CM->Cost;
	      return 0;
	    }
      else
      
	    {
       return 1;
      }
    }   
   else 
    {//matrix is not empty
     SelectedColumn=select_Col_Contrib (CM);
     ID_Col_To_Remove=SelectedColumn->ID;
     CopyCM2=Duplicate (CM);
     SolUCP1=create_New_Empty_Solution();//Solution given by first call B&B
/*************************************first branch***************************************/
     AddToSolution ( SolUCP1,SelectedColumn);
     CM->Cost+=SolUCP1->Cost; //Remove it from matrix
     CM->lbound=lbound_New;
     RemoveColWithRows ( SelectedColumn,CM );
 
     if ( BABAURA2(CM,SolUCP1,reduce_Time)==1 ) SolUCP1->Cost=MaxCost;
/*********************************************second branch***********************************************/

     if ( (SolUCP1->Cost!=MaxCost && SolUCP1->Cost == lbound_New ))
     {
	      AppendSolution ( SolUCP1,SolUCP);
	      return 0;
     }  
     else
     { 
        remove_Col_From_Matrix ( CopyCM2,ID_Col_To_Remove);
        SolUCP2=create_New_Empty_Solution();
        CopyCM2->lbound=lbound_New;
        if ( BABAURA2(CopyCM2,SolUCP2,reduce_Time)==1 )SolUCP2->Cost=MaxCost;
        Release (CopyCM2);   
    } 

/*********************************************select solution***********************************************/     
     if ( SolUCP1->Cost < SolUCP2->Cost )//Solution 1 was succesfull
	   {
	      Release (SolUCP2);
	      AppendSolution ( SolUCP1,SolUCP );
	      return 0;
	   }
	   else
	     {
	       if ( SolUCP2->Cost!=MaxCost )//Solution 2 was succesfull
 		       {
		        Release (SolUCP1);
		        AppendSolution ( SolUCP2,SolUCP );
		        return 0;
	         }
	       else
	         {//No solution was succesfull
		        Release (SolUCP1);
		        Release (SolUCP2);
		        return 1;
	         }
	    }
    }
  return 0;
}

/***********************end Aura*********************************************/



struct time RunTime (float Time2, float Time1 )
{
  struct time Result;
  Time1-=Time2;
  Result.ti_hour=Time1/360000;
  Time1-=Result.ti_hour*360000;
  Result.ti_min=Time1/6000;
  Time1-=Result.ti_min*6000;
  Result.ti_sec=Time1/100;
  Time1-=Result.ti_sec*100;
  Result.ti_hund=Time1;
  return Result;
}


float MatrixDensity ( struct CoveringMatrix *CM )
{
  float NumberOf1=0;
  struct CLink *Column;
  struct CLink *Row;
  Column=CM->ColLink;
  while ( Column !=NULL)
   {
     Row=CM->RowLink;
     while ( Row!=NULL )
       {
	  NumberOf1+=CM->Array[Column->ID][Row->ID];
	  Row=Row->Next;
       }
     Column=Column->Next;
   }
 return 1/((CM->countOfCols*CM->countOfRows)/NumberOf1);
}





int vefiry_Solution (struct CoveringMatrix *Cm,struct header_of_solution_UCP *SolutionUCP )
{//verify if solution is valid
  struct CLink *colLinkSolution;
  struct CoveringMatrix *CM3;
  
  CM3=Duplicate(Cm);
  colLinkSolution=SolutionUCP->SetC;

  while(colLinkSolution!=0)
  {
  
    RemoveColWithRows(colLinkSolution,CM3);
  
    colLinkSolution=colLinkSolution->Next;
  }

  if (CM3->RowLink!=0) {Release (CM3); return 1;}
  else {Release(CM3);return 0;}
  
  
}

void Set_Max_Raiser (struct CoveringMatrix *Cm)
{//max raiser = average cost cols * 4
  int Prumerna_Cena_Sloupcu=0;
  int Cena_Sloupcu=0;
   struct CLink *Sloupec;
   
   Sloupec=Cm->ColLink;
   if (Sloupec!=0)
   {
   while (Sloupec!=0)
    { 
      Cena_Sloupcu+=Sloupec->Cost;
  
      Sloupec=Sloupec->Next;
    }
  
  Cena_Sloupcu/=Cm->countOfCols;
  
  maxRaiser=4*Cena_Sloupcu;
  }

}

struct CoveringMatrix *RebuildMatrix (struct CovMatrix *CVM)
{
 struct CovLink *AuxCol,*AuxRow;
  int I,J;
  int * Costs;

  
  struct CoveringMatrix *Cm;
  
  
   Cm=new CoveringMatrix;
   if ( Cm==NULL )
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }
   Cm->Cost=0;
   Cm->countOfCols=0;
   Cm->countOfRows=0;
 
   Cm->countOfOnes=0;
  
  //first load dimensions of array to allocate memory
       Cm->countOfCols=CVM->rows; 
    
  AuxCol=CVM->col;
  I=0;
  while (AuxCol!=0)
  {
      I++;
      AuxCol=AuxCol->next;
  }
 Cm->countOfRows=I;            
  
   Costs=new int [Cm->countOfCols];
  Cm->Array=new char * [Cm->countOfCols];
    if ( Cm->Array==0 )
    {
	    printf("Insufficient memory");
	    exit(0);
    }
  for (I=0;I<Cm->countOfCols;I++)
      {
        Cm->Array[I]=new char [Cm->countOfRows]; 
        if ( Cm->Array[I]==0 )
        {
	       printf("Insufficient memory");
	       exit(0);
        }
      }
      
//load costs

  AuxCol=CVM->row;
  I=Cm->countOfCols-1;//numbers of cols in Boom matrix are from max to zero 
  while (AuxCol!=0)
  {
      Costs[I--]=AuxCol->term->dim+1;
      AuxCol=AuxCol->next;
  }
    
 //Load array
 AuxRow=CVM->col;
 J=0;
 while ( AuxRow!=0)
  {
  AuxCol=CVM->row;
  I=Cm->countOfCols-1;
  while ( AuxCol!=0 )
   {//numbers of cols in Boom matrix are from max to zero
      Cm->Array[I--][J]=CVM->matrix[AuxCol->index][AuxRow->index]-48;
      AuxCol=AuxCol->next;
   }
   J++;
   AuxRow=AuxRow->next;
  }
  
  create_Matrix ( Cm,Costs);
  delete [] Costs;
  return Cm;

}
struct CovLink *Rebuild_Solution (struct header_of_solution_UCP *SolutionUCP,struct CovMatrix *CVM)
{
  struct CLink *Aux;
  struct CovLink *FirstCol=0,*AuxCol=0,*AuxSol=0;
  Aux=SolutionUCP->SetC;
  
  while (Aux!=0)
  {
    AuxCol=CVM->row;
    while (AuxCol!=0)
    {
   
      if (AuxCol->index==Aux->ID)
      {

      if (FirstCol==0)
      {
     
        FirstCol=new CovLink;
        FirstCol->term=AuxCol->term;
        FirstCol->index=AuxCol->index;
        FirstCol->contrib=AuxCol->contrib;
        FirstCol->vct=AuxCol->vct;
        FirstCol->count=AuxCol->count;
        
        FirstCol->next=0;
        FirstCol->prev=0;
      }
      else
      {
        
        AuxSol=FirstCol;
        while (AuxSol->next!=0)
        {
          AuxSol=AuxSol->next;
         }
   
        AuxSol->next=new CovLink;
        AuxSol->next->term=AuxCol->term;
        AuxSol->next->index=AuxCol->index;
        AuxSol->next->contrib=AuxCol->contrib;
        AuxSol->next->vct=AuxCol->vct;
        AuxSol->next->count=AuxCol->count;
        
        AuxSol->next->next=0;
          AuxSol->next->prev=AuxSol;
        
        
      }
       
      }
     
      AuxCol=AuxCol->next;
    }
    Aux=Aux->Next;
  }
  
  AuxCol=FirstCol;
  return FirstCol;
}
struct CovMatrix *SelectSolver (struct CovMatrix *CVM,struct CovSol * best,int Solver,int MaxTime)
{
    struct CoveringMatrix *Cm,*CM2;
    struct header_of_solution_UCP *SolutionUCP;
    
    
    
    Cm=RebuildMatrix(CVM);
    
    MaxRunTime=MaxTime;
    
    if (Cm->RowLink!=0||Cm->ColLink!=0)
    {
    SolutionUCP=create_New_Empty_Solution();
    
    if (Solver==3)
    {
      MaxCost++;
      uBound=MaxCost;
      NumCalls=0;
      
      
      Set_Max_Raiser (Cm);
      if (MaxRunTime)  
       {
        callUpperBound=MaxRunTime*(100-Cm->countOfCols/5);
        
        if (callUpperBound<1)callUpperBound=1;
         CM2=Duplicate(Cm); 
           
         BABAURA2 ( CM2,SolutionUCP,1 );
         Release (CM2);
         if (vefiry_Solution(Cm,SolutionUCP))
         {
           Release (SolutionUCP);
           SolutionUCP=create_New_Empty_Solution();
           ContribAddHeuristic(Cm,SolutionUCP);
         }
       }
      else BABAURA2 ( Cm,SolutionUCP,0 );//if MaxRunTime==0, there is no timeover break 
    } else 
    if (Solver==5)
    {
      NaturalHeuristic(Cm,SolutionUCP);    
    }else 
    if (Solver==6)
    {
      ContribAddHeuristic(Cm,SolutionUCP);
    } else 
    if (Solver==7)
    {
      RothHeuristicPositiv(Cm,SolutionUCP);
    } else 
    if (Solver==8)
    {
      ServitHeuristic(Cm,SolutionUCP);
    }
    
    CVM->sol=Rebuild_Solution (SolutionUCP,CVM);
    CVM->solcost=SolutionUCP->Cost;
    best->solcost=SolutionUCP->Cost;
    best->sol=CVM->sol;
    for  (int I=0;I<Cm->countOfCols;I++)
      delete  Cm->Array[I];
    delete  Cm->Array;
    
    Release (Cm);
    
    Release (SolutionUCP);
    }
    else {
    CVM->sol=0;
    CVM->solcost=0;
    best->sol=0;
    }
    return CVM;
}
float DensityMatrix(struct CoveringMatrix *Cm)
{
  FindNumberOf1 (Cm);
  return (float)Cm->countOfOnes/(Cm->countOfCols*Cm->countOfRows)*100;
}
struct CovMatrix *AutoSelectSolver (struct CovMatrix *CVM,struct CovSol * best,int MaxAuraRunTime,int effort,int endcov)
{//endcov is not used , MaxTime us default t=2
    struct CoveringMatrix *Cm,*CMAura;
    struct header_of_solution_UCP *SolutionUCP,*SolutionUCPDominance;
    int UnifiedCosts;
    float Density;
    
    if (!MaxAuraRunTime) MaxRunTime=2;
    else MaxRunTime=MaxAuraRunTime;
    Cm=RebuildMatrix(CVM);
    
    SolutionUCP=create_New_Empty_Solution();
    SolutionUCPDominance=create_New_Empty_Solution();
    
    if (MaxCost > Cm->countOfCols) UnifiedCosts=0; //maxRaiser=4*average cost of all cols, if maxRaiser=4, all col cost=1 
      else UnifiedCosts=1;
    
    if (Cm->countOfRows<100*effort && Cm->countOfCols<100*effort) 
      SolveDominance (Cm,SolutionUCPDominance); //if matrix is small, but not enough to use AURA, try to solve dominance and look how the matrix has been reuced
     
    CMAura=Duplicate(Cm);
    
    if (Cm->ColLink !=0)  
    {//if sol UCP has not been found by dominance process
    Density=MatrixDensity (Cm);
    
    if (UnifiedCosts) //case unified costs
    { 
      if (Density<6)
      {
        if (Cm->countOfRows<22*effort && Cm->countOfCols<22*effort) //if matrix is small enough, try to solve using AURA 
        {
          uBound=MaxCost;
          NumCalls=0;
          callUpperBound=200;
          Set_Max_Raiser (Cm);
          
          BABAURA2 ( CMAura,SolutionUCP,1 );
         
         if (vefiry_Solution(Cm,SolutionUCP))
         {
           Release (SolutionUCP);
           SolutionUCP=create_New_Empty_Solution();
           ContribAddHeuristic(Cm,SolutionUCP);
         }
        }
        else 
        {
          
            if (Cm->countOfCols<300*effort && Cm->countOfRows<300*effort)
              {
                ContribAddHeuristic(Cm,SolutionUCP);
              }
            else
            {
              NaturalHeuristic(Cm,SolutionUCP);
            }
          
        }
      }
      else //density is greater than 6%
      {
        if (Cm->countOfRows<20*effort && Cm->countOfCols<20*effort) //if matrix is small enough, try to solve using AURA 
        {
          uBound=MaxCost;
          NumCalls=0;
          callUpperBound=200;
          Set_Max_Raiser (Cm);
           
          BABAURA2 ( CMAura,SolutionUCP,1 );
        
         if (vefiry_Solution(Cm,SolutionUCP))
         {
           Release (SolutionUCP);
           SolutionUCP=create_New_Empty_Solution();
           ContribAddHeuristic(Cm,SolutionUCP);
         }
          
        }
        else 
        {//ContribAdd heuristic is fastest for this density
          printf("Solving UCP by ContribAdd Heuristic\n");
          ContribAddHeuristic(Cm,SolutionUCP);
        }
      }
    }
    else //case non-unified costs
    {
      if (Density<6)
      {

        if (Cm->countOfRows<18*effort && Cm->countOfCols<18*effort) //if matrix is small enough, try to solve using AURA 
        {
          uBound=MaxCost;
          NumCalls=0;
          callUpperBound=200;
          Set_Max_Raiser (Cm);
          BABAURA2 ( CMAura,SolutionUCP,1 );
         if (vefiry_Solution(Cm,SolutionUCP))
         {
           Release (SolutionUCP);
           SolutionUCP=create_New_Empty_Solution();
           ContribAddHeuristic(Cm,SolutionUCP);
         }
          
        }
        else 
        {
          if (Cm->countOfRows<80*effort && Cm->countOfCols<80*effort)
          {
            ServitHeuristic(Cm,SolutionUCP);
          }
          else if (Cm->countOfRows<400*effort && Cm->countOfCols<400*effort)
          {
            ContribAddHeuristic(Cm,SolutionUCP);
          }
          else
          {
            RothHeuristicPositiv(Cm,SolutionUCP);
          }
        }
      }
      else //density is greater than 6%
      {
        if (Cm->countOfRows<15*effort && Cm->countOfCols<15*effort) //if matrix is small enough, try to solve using AURA 
        {
          uBound=MaxCost;
          NumCalls=0;
          callUpperBound=200;
          Set_Max_Raiser (Cm);
          BABAURA2 ( CMAura,SolutionUCP,1 );
        
         if (vefiry_Solution(Cm,SolutionUCP))
         {
           Release (SolutionUCP);
           SolutionUCP=create_New_Empty_Solution();
           ContribAddHeuristic(Cm,SolutionUCP);
         }
          
        }
        else 
          if (Cm->countOfCols<400*effort && Cm->countOfRows<400*effort)
          {
            ContribAddHeuristic(Cm,SolutionUCP);
          }
          else
          {
            RothHeuristicPositiv(Cm,SolutionUCP);
          }
      }

    }
    }

    AppendSolution(SolutionUCPDominance,SolutionUCP);
    CVM->sol=Rebuild_Solution (SolutionUCP,CVM);
    CVM->solcost=SolutionUCP->Cost;
    best->solcost=SolutionUCP->Cost;
    best->sol=CVM->sol;

    for  (int I=0;I<Cm->countOfCols;I++)
     delete  Cm->Array[I];
    delete  Cm->Array;
    Release (Cm);
    Release (CMAura);
    Release (SolutionUCP);
    return CVM;
}


