#include "stdafx.h"

#ifdef _MSC_VER
#pragma hdrstop
#endif

using namespace std;

#include "../../Kernel/kernelincludes.h"

#include "CovMatrix.h"
#include "AuraCover.h"

void AuraCover::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 AuraCover::Release ( struct header_of_solution_UCP *SolUCP )
{ //structure to release allocated memory for solution
  CLink *Aux;
  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 *AuraCover::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) throw RuntimeException( "Aura: Not enough memory" );
   //and set all antries to zero
   Solution->Cost=0;
   Solution->SetC=0;

  return Solution;
}

void AuraCover::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 AuraCover::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 AuraCover::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) throw RuntimeException( "Aura: Not enough memory" );
     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 AuraCover::remove_Col_From_Matrix ( struct CoveringMatrix *CM, struct CLink *colToRemove )
{//remove column from covering matrix
  struct CLink *Entry;
  
  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 AuraCover::remove_Col_From_Matrix ( struct CoveringMatrix *CM, int ID )
{//remove column from covering matrix
  struct CLink *Entry;
  
  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 AuraCover::remove_Row_From_Matrix ( struct CoveringMatrix *CM, struct CLink *rowToRemove )
{
  struct CLink *Entry;
  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 AuraCover::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* AuraCover::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) throw RuntimeException( "Aura: Not enough memory" );
  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) throw RuntimeException( "Aura: Not enough memory" );
      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 ) throw RuntimeException( "Aura: Not enough memory" );

     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) throw RuntimeException( "Aura: Not enough memory" );

       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 ) throw RuntimeException( "Aura: Not enough memory" );

     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 AuraCover::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;
  struct CLink *Columns;
  struct CLink *Rows;
  //Create row links
  if (Cm->countOfCols!=0||Cm->countOfRows!=0)
  {
  Cm->RowLink = new CLink;
  if ( Cm->RowLink==NULL ) throw RuntimeException( "Aura: Not enough memory" );
  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) throw RuntimeException( "Aura: Not enough memory" );
     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) throw RuntimeException( "Aura: Not enough memory" );
  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) throw RuntimeException( "Aura: Not enough memory" );
     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
     uBound+=Columns->Cost;//increase upper bound
     Columns->Next=0;
   }
  else  Columns->Next=0;
   uBound++;
   MaxCost=uBound;
   }
   else {Cm->RowLink=0;Cm->ColLink=0;}
}

void AuraCover::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 AuraCover::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 AuraCover::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
	  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;
}

int AuraCover::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 * AuraCover::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) throw RuntimeException( "Aura: Not enough memory" );
   //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 * AuraCover::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) throw RuntimeException( "Aura: Not enough memory" );
   //and set all antries to zero
    header->link_To_Cube=0;
  header->countOfCubes=0;
  return header;
}

struct Domain * AuraCover::InitDomain (  int numberOfRow )
{//Structure to create empty Domain
   struct Domain *domain=0;
   //first allocate memory
   domain = new struct Domain;
     if ( domain==0) throw RuntimeException( "Aura: Not enough memory" );
   //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 AuraCover::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 AuraCover::add_Col_To_Domain ( struct Domain *domain, struct CLink *Column ) 
{

	struct CLink *Auxiliary;
	struct CLink *Auxiliary2;


	Auxiliary = new CLink;
	if ( Auxiliary == NULL ) throw RuntimeException( "Aura: Not enough memory" );
	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 AuraCover::find_Cols_Covering_Row (  struct CoveringMatrix *CM, struct CLink *SelectedRow, struct Domain *SelectedRowDomain ) {

	struct CLink *ColLink;

	ColLink = CM->ColLink;
	while ( ColLink != 0 ) {
		if ( CM->Array[ColLink->ID][SelectedRow->ID] == 1 )  add_Col_To_Domain (SelectedRowDomain, ColLink );
		ColLink = ColLink->Next;
	}
}
void AuraCover::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 AuraCover::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 AuraCover::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 AuraCover::Release ( struct CLink* Pomocny_SetC)
{
	struct CLink *AuxSetC,*Aux2SetC;
		AuxSetC=Pomocny_SetC;
		while (AuxSetC != 0 )
		{
			Aux2SetC=AuxSetC;
			AuxSetC=AuxSetC->Next;
			delete (Aux2SetC);
		}
}

void AuraCover::add_Row_To_Matrix (struct CoveringMatrix *CM, struct CLink *RowLink)
{
	struct CLink *AuxRow,*Aux1;
	
	AuxRow = new CLink;
	if ( AuxRow == NULL) throw RuntimeException( "Aura: Not enough memory" );
	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 * AuraCover::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 AuraCover::add_Domain_To_Cube ( struct cube *cube_of_Matrix,struct Domain* source_Domain)

{
	struct Domain *Auxi;
	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 AuraCover::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 AuraCover::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 * AuraCover::make_Domain_Intersection ( struct CLink *Domain_Row1, struct CLink *Domain_Row2)

{
	struct CLink *Auxiliary1;
	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  * AuraCover::make_Difference_Domain ( struct CLink *Domain_Row2, struct CLink *Domain_Row1)
// 
{
	struct CLink *Auxiliary1;
	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 AuraCover::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 * AuraCover::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 *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) throw RuntimeException( "Aura: Not enough memory" );

  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) throw RuntimeException( "Aura: Not enough memory" );

       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 ) throw RuntimeException( "Aura: Not enough memory" );

      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
}

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

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

int AuraCover::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
}
void AuraCover::check_essentiality ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolutionUCP ){ 
	
	struct CLink *RowLink;
	struct CLink *ColLink;
	struct CLink *EssentialColumn;	

	//cout << " finding number of 1s" << endl;
	FindNumberOf1(CM);

	RowLink=CM->RowLink;
	// Row to compare

	//cout << "checking rows" << endl;
	while ( RowLink != 0 ) { 

		if ( RowLink->NumberOf1==1) {	
			
			ColLink = CM->ColLink;

			while(ColLink!=0) {
				if ( CM->Array[ColLink->ID][RowLink->ID]==1 ) {
					EssentialColumn = ColLink;
					cout << "essential column " << EssentialColumn->ID << " with cost " << EssentialColumn->Cost<< endl;
					break;
				}
				ColLink=ColLink->Next;
			}

			
			/* If row is covered by only one column,that column is essential.
			* It will be added to solution and removed from matrix with
			* all rows it covers */
			AddToSolution ( SolutionUCP,EssentialColumn);
			RemoveColWithRows(EssentialColumn,CM);
			RowLink=CM->RowLink;
		} else 
			RowLink=RowLink->Next;
	}


}


float AuraCover::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* AuraCover::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;

}

int AuraCover::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 AuraCover::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 * AuraCover::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 AuraCover::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;
   
  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 * AuraCover::Split_Domain ( struct CoveringMatrix *Matice_MSIR,struct CoveringMatrix *matrix_Without_MSIR,struct cube *cube_Of_Matrix_MSIR,struct Domain *domain_Of_Selected_Row)
{
	struct CLink *cols_Covering_Row_MSIR;
	struct CLink *cols_Covering_Row_Without_MSIR,*Auxiliary2;
	struct Domain *domain_MSIR_Second_Cycle,*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];
  if ( nonzeroIntersection==NULL) throw RuntimeException( "Aura: Not enough memory" );
  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; //odkaz na mnozinu sloupcu pokryvajici 1 radek matice 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;//napojuje se do domeny,netreba mazat
              nonzeroIntersection[domain_ID]=1;//musim si zapamatovat,jestli byl prunik nenulovy
              while (Auxiliary2!=0 )
	            {//a zaroven odebereme sloupce z domeny vybraneho radku, budeme to potrebovat pro Part2
                remove_Col_From_Domain ( domain_Selected_Row_Removed_Intersection,Auxiliary2->ID );//domain_Of_Selected_Row se tady zmeni,
		            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;//vysledek ulozime
      if (Auxiliary1->SetC!=0 )  
      {
        add_Domain_To_Cube (created_Cube,found_Domain);//napijime do krychle a hledame dalsi,to musim zejtra dodelat
      }    
      else {
      Release (found_Domain);
      }
	    domain_MSIR_Second_Cycle=domain_MSIR_Second_Cycle->Next;
	    domain_ID++;
	  }
	  if (appendDomain) 
    {  //Pokud je to jiz posledni nalezene reseni, ktere nepokryva vybrany radek, tak musime napojit "reseni radku bez sloupcu vsech domen"
       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 AuraCover::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 Omezit_Cas)
{
	struct Domain *Auxiliary_Copy;
    struct CoveringMatrix *Matice_Bez_MSIR_Kopie;
	struct CLink *RowLink_Vybraneho_Radku;
	struct Domain *domain_Of_Selected_Row;
    struct cube *AuxCube;
    struct header_Of_Cubes *header_Of_Cubes=0;
	int Cube_ID=0,domain_ID=0;
	int cena_Domen;
	int stillToRaise,return_Value,best_Row;
	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 (Omezit_Cas) 
  if (NumCalls++>callUpperBound)
  {
    
//    StopTime=GetMyCPUTime();
    if (int(StopTime-StartTime)>=MaxRunTime ) {stopCover=true;return 1;}
    else NumCalls=0;
    
  } 

 Auxiliary_Copy=cube_Of_Matrix_MSIR->link_To_Domain;
 cena_Domen=1;
 while(Auxiliary_Copy!=0)
 {
  if(Auxiliary_Copy->cheapestColumn>cena_Domen)
      cena_Domen=Auxiliary_Copy->cheapestColumn;
  Auxiliary_Copy=Auxiliary_Copy->Next;
 }
 if (stillToRaise <= cena_Domen)
 {
    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);
     } 
 }
  
  best_Row=select_Best_Uncovered_Row ( matrix_Without_MSIR,cube_Of_Matrix_MSIR );
	RowLink_Vybraneho_Radku=matrix_Without_MSIR->RowLink;
	while (RowLink_Vybraneho_Radku->ID!=best_Row) RowLink_Vybraneho_Radku=RowLink_Vybraneho_Radku->Next; 
  header_Of_Cubes=create_Empty_Header_Cube();

	if (RowLink_Vybraneho_Radku!=0)
	{
    domain_Of_Selected_Row = InitDomain(RowLink_Vybraneho_Radku->ID);
    find_Cols_Covering_Row ( matrix_Without_MSIR,RowLink_Vybraneho_Radku,domain_Of_Selected_Row );
    remove_Row_From_Matrix (matrix_Without_MSIR,RowLink_Vybraneho_Radku);  
    header_Of_Cubes->link_To_Cube=Split_Domain (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,false)==0) return_Value=0;
    Release (Matice_Bez_MSIR_Kopie);
    if (stopCover) break;
    AuxCube=AuxCube->Next;
  
  }
  Release (header_Of_Cubes);
 return return_Value;
}
  
int AuraCover::BABAURA2 ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolUCP,long double instance  )
{//Branch and Bound with Limit Lower Bound computation
   struct CLink *SelectedColumn;
   struct CoveringMatrix *CopyCM2;
   struct CoveringMatrix *CopyCMForMSIR;
   struct header_of_solution_UCP *SolUCP2;
   struct header_of_solution_UCP *SolUCP1;
   struct header_of_solution_UCP *Reseni_Ziskane_Z_Dominanci;
   int MSIR=0;
   int lbound_New,difference;
   //doplnene promenne pro raiser
   struct cube *cube_Of_Matrix_MSIR;
   struct CoveringMatrix *matrix_Without_MSIR;
   int lBound=0,raiserLowerBound=0,raiserAnswer=0,volani_Raiser=0,ID_Sloupce_K_Vyjmuti;
   struct header_of_solution_UCP *SolRaiser;
   struct CoveringMatrix *MaticeMSIR;
   
   if (stopCover) {uBound=MaxCost;return 1;}

   
   cout << "B&B " << setw(8) << instance << ", Upper Bound: " << setw(6) << uBound;
   cout << " ; Overall state cost: " << setw(6) << CM->Cost ;
   cout << " ;  Solution cost (without domination): " << setw(6) << SolUCP->Cost << endl;

   NumCalls+=10;
   Reseni_Ziskane_Z_Dominanci=create_New_Empty_Solution();//Solution given by essential columns

   check_essentiality(CM,Reseni_Ziskane_Z_Dominanci);
   //SolveDominance(CM,Reseni_Ziskane_Z_Dominanci);
   CM->Cost+=Reseni_Ziskane_Z_Dominanci->Cost;
	 AppendSolution (Reseni_Ziskane_Z_Dominanci,SolUCP );
     
	 NumCalls2++;

   if ( CM->ColLink!=0&&CM->RowLink!=0)
   {
   /************najdeme MSIR***********/
    
     FindNumberOf1(CM);//tohle je potreba pro FindMSIR a zaroven odstranuje z matice sloupce se samymi nulami 
     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); //nejprve si zkopiruju celou puvodni matici
          CopyCMForMSIR=Duplicate(CM);
          MaticeMSIR=create_Matrix_Of_Rows_MSIR ( CopyCMForMSIR,matrix_Without_MSIR);//tato procedura z matrix_Without_MSIR odebere radky MSIR
          SolRaiser=create_New_Empty_Solution();
          cube_Of_Matrix_MSIR = create_Empty_Cube ();
          find_Cube_Of_Matrix ( MaticeMSIR, cube_Of_Matrix_MSIR);
          raiserLowerBound=cube_Of_Matrix_MSIR->countOfCheapestCols;
          parameterN=difference;
          
          raiserAnswer = Raiser (CM,MaticeMSIR,matrix_Without_MSIR,cube_Of_Matrix_MSIR,raiserLowerBound,SolRaiser,false);
          
          Release (CopyCMForMSIR);
          Release (matrix_Without_MSIR);
          Release (MaticeMSIR);
          Release (cube_Of_Matrix_MSIR); 
          if (raiserAnswer == 1) 
            {
              SolUCP->Cost=MaxCost;
              Release(SolRaiser);
              return 1;
            } 
          else 
            {
              AppendSolution(SolRaiser,SolUCP); //tady musim udelat prunik path+reseni ziskane raiserem
              return 0;
            }      
      }  
    }  
   /****************pokud je CM prazdna****************/
   if ( CM->ColLink==0||CM->RowLink==0 )
    {
      
	    if ( CM->Cost<uBound )
    	{
		
			cout << "B&B " << setw(8) << instance << ", Upper Bound: " << setw(6) << uBound << " - found new best solution with cost " << CM->Cost << endl;
	      uBound=CM->Cost;
	      return 0;
	    }
      else
      
	    {
			cout << "B&B " << setw(8) << instance << ", Upper Bound: " << setw(6) << uBound << " - found solution with cost " << CM->Cost << endl;
       return 1;
      }
    }   
   else 
    {//matice neni prazdna
     SelectedColumn=select_Col_Contrib (CM);
     ID_Sloupce_K_Vyjmuti=SelectedColumn->ID;
	 cout << "pridavam sloupec " << ID_Sloupce_K_Vyjmuti << endl;
     CopyCM2=Duplicate (CM);
     SolUCP1=create_New_Empty_Solution();//Solution given by first call B&B
/*************************************prvni vetev***************************************/
     AddToSolution ( SolUCP1,SelectedColumn);
     CM->Cost+=SolUCP1->Cost; //Remove it from matrix
     CM->lbound=lbound_New;
     RemoveColWithRows ( SelectedColumn,CM );
 
     if ( BABAURA2(CM,SolUCP1,2*instance+1)==1 ) SolUCP1->Cost=MaxCost;
/*********************************************druha vetev***********************************************/

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

/*********************************************reseni***********************************************/     
     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;
}

/************************KONEC AURA SOLVER*********************************************/


void AuraCover::Set_Max_Raiser (struct CoveringMatrix *Cm)
{//spocita prumernou cenu vsech sloupcu v matici, hodnota maxraiser bude na tuto hodnotu nastavena
  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 *AuraCover::RebuildMatrix (CovMatrix *CVM)
{
  int I,J;
  int * Costs;
    
  struct CoveringMatrix *Cm;
  
   Cm=new CoveringMatrix;
   if ( Cm==NULL ) throw RuntimeException( "Aura: Not enough memory" );
   Cm->Cost=0;
   Cm->countOfCols=0;
   Cm->countOfRows=0;
    Cm->countOfOnes=0;
  
  //first load dimensions of array to allocate memory
  Cm->countOfCols=CVM->GetColNum();
  Cm->countOfRows=CVM->GetRowNum();            
  Costs=new int [Cm->countOfCols];
  if ( Costs==NULL) throw RuntimeException( "Aura: Not enough memory" );
   
  Cm->Array=new char * [Cm->countOfCols];
  if ( Cm->Array==0 ) throw RuntimeException( "Aura: Not enough memory" );
    
  for (I=0;I<Cm->countOfCols;I++)
      {
        Cm->Array[I]=new char [Cm->countOfRows]; 
        if ( Cm->Array[I]==0 ) throw RuntimeException( "Aura: Not enough memory" );
      }
      
  for (I=0;I<Cm->countOfCols;I++)
  {
      Costs[I]=CVM->GetCost(I);
      
  }
    
  for (J=0;J<Cm->countOfRows;J++)
   
     for (I=0;I<Cm->countOfCols;I++)
       Cm->Array[I][J]=CVM->GetValue(J,I);
 
  create_Matrix ( Cm,Costs);
  
  delete [] Costs;
  
  return Cm;

}
list<unsigned int> AuraCover::Rebuild_Solution (struct header_of_solution_UCP *SolutionUCP)
{
 struct CLink *Aux;
 list<unsigned int> Solution;
  //struct CovLink *FirstCol=0,*AuxCol=0,*AuxSol=0;
  Aux=SolutionUCP->SetC;
  
  while (Aux!=0)
  {
    Solution.push_back(Aux->ID);
    Aux=Aux->Next;
  }
  return Solution;
}
AuraCover::AuraCover (CovMatrix *_matrix )
{
  uBound=0;
  stopCover=false;
  CM=RebuildMatrix( _matrix );//vytvori a prekopiruje puvodni matici do struktury pro auru
  SolutionUCP=create_New_Empty_Solution();//vytvori prazdnou hlavicku reseni
  isAllCovered = false;
  
}
AuraCover::~AuraCover ()
{
  Release (CM);//odstrani matici a 
  Release (SolutionUCP);//seznam reseni
}

list<unsigned int> AuraCover::Run()
{
	NumCalls2=0;
  MaxRunTime=100;//toto nastavuje priblizny maximalni cas behu algoritmu.testuje se ve funkci Raiser, po jeho dokonceni, takze muze trvat i podstatne dele.
                //pote se ukonci aura a vrati nejlepsi nalezene reseni
  BABAURA2 ( CM,SolutionUCP,0);//spusti se aura//ten posledni parametr znaci, zda chceme omezit cas si nikoliv.0=neomezovat, 1=omezit na MaxRunTime [s]
  Solution=Rebuild_Solution (SolutionUCP);
  isAllCovered = checkCoverage(CM,SolutionUCP);
  return Solution;
}

bool AuraCover::checkCoverage(struct CoveringMatrix *CM,struct header_of_solution_UCP *SolUCP){

	bool* rowIsCovered = new bool[CM->countOfRows];
	int i;
	int solutionColumnID;

	struct CLink *SolutionColumn;

	SolutionColumn = SolUCP->SetC;

	for(i=0;i<CM->countOfRows;i++)
			rowIsCovered[i] = false;

	while(SolutionColumn->Next!=0) {
		
		solutionColumnID = SolutionColumn->ID;

		for(i=0;i<CM->countOfRows;i++)
		if(CM->Array[solutionColumnID][i]==1)
			rowIsCovered[i] = true;
		
		SolutionColumn = SolutionColumn->Next;
	}

	for(i=0;i<CM->countOfRows;i++)
			if(rowIsCovered[i] == false)
				return false;
	return true;

}
