#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
#include "vc.h"

/*
PROGRAMMA CHE RISOLVE L'IHITTING SET PROBLEM
INPUT: A = { a1... an}
    e m diversi sottinsiemi B1...Bm sotinsiemi di A
    e intero K>=0
OUTPUT:un insieme tale che HittingSet intersecato Bi per ogni i è diverso dal vuoto.

*/
/*
return a empty HS
*/
char *makeHS(int nov)
{

	char *vc;
	vc=(char *)malloc(nov+1); vc[nov]=0;
	memset(vc,'0',nov);
	return vc;
}
void stampaInsiemeA(int A[],int n)
{
     int i;
     printf("\n\n====INSIEME A===\n");
     for(i=0;i<n;i++)
     {
                     printf("%d\n",A[i]);
     }
}

void stampaInsiemiB(int B[][100],int m)
{
   int elem=0,i;
   printf("\n\n======INSIEMI B======\n\n");

   for(i=0;i<m;i++)
    {
     printf("====INSIEME B-%d====\n",i);
     while(B[i][elem]!=-1)
      {
        printf("%d ",B[i][elem]);
        elem++;
      }
      printf("\n");
      elem=0;
    }
}
int cardinalita(int B[][100],int i)
{
    int elem=0;
    int cardinalita=0;
    while(B[i][elem]!=-1)
    {
       cardinalita++;
       elem++;
    }
    return cardinalita;

}

void cancellaA(int A[],int i,int n)
{

    if(i<n)
    {
       A[i]=A[i+1];
    }


}


int cancellaB(int B[][100],int i,int m)
{

    int elem=0,ind=0;
    int j,t=0;
    int vet[100];
    int numB=m-1;
    int C[100][100];
    //cerco i Bi che hanno i e li salvo in vet[]
    for(j=0;j<m;j++)
    {
       while(B[j][elem]!=-1)
       {
        if(B[j][elem]==i)
        {
            vet[t]=j;
            t++;
            break;
        }
        elem++;
       }
      elem=0;
     }
     //copio la matrice B nella matrice C
     for(j=0;j<m;j++)
    {
       while(B[j][elem]!=-1)
       {
          C[j][elem]=B[j][elem];
          elem++;
       }
      C[j][elem]=-1;
      elem=0;
    }

      //dove ho trovato l'elemento i pongo tutto il Bi a -2


      for(j=0;j<t;j++)
     {ind =vet[j];
       while(B[ind][elem]!=-1)
       {
            B[ind][elem]=-2;
            elem++;

       }
       B[ind][elem]=-1;
       elem=0;

     }


     elem=0;
     ind=0;
     int controllo=0;
     //copio nella matrice di appoggio solo i Bi che non contengono i
     for(j=0;j<m;j++)
     {
        while (B[j][elem]!=-1)
        {
            if(B[j][elem]!=-2)
            {
              C[ind][elem]=B[j][elem];

              //printf("copio nella matrice d'appoggio C[%d][%d] : B[%d][%d]:%d\n",ind,elem,j,elem,C[ind][elem]);
              controllo++;
            }

           elem++;
        }
        if(controllo!=0)
        {
        ind++;
        }
        controllo=0;
        C[ind][elem]=-1;
         elem=0;

     }
     //ricopio tutto nella matrice B
     for(j=0;j<m-t;j++)
     {
        while (C[j][elem]!=-1)
        {
              B[j][elem]=C[j][elem];
              elem++;
        }
        B[j][elem]=-1;
        elem=0;
     }

     printf("numero elementi rimanenti:%d\n",m-t);
     //stampaInsiemiB(B,m-t);
     return m-t;



}
/*int coeffBinomiale(int n,int k)
{
 int i,j,numeratore=n,denominatore=k;
 int coeff=0;
 for(i=n-1;i>=(n-k);i--)
 {
                       numeratore=numeratore*i;
 }
 for(i=k;i>0;i--)
 {
                       denominatore=denominatore*i;
  }

  coeff=numeratore/denominatore;
  return coeff;

}
*/
char *HS(int A[],int B[][100],int n,int m,int ini,int k,int D[][100],int vm)
{
int i=0,j,t=0,elem=0,w=0;

         if((m==0)&&(k==0))
          {           printf("stampa11\n");

                      char *c=NULL;
                      return c;
          }
          if((m==0)&&(k!=0))
          {                 printf("stampa12\n");
                            return makeHS(ini);
          }
         if((k==0)&&(m!=0))
          {           printf("stampa2\n");
                      char *c=NULL;
                      return c;
          }



          int vet[100];

          while(B[i][elem]!=-1)
          {
             vet[t]=B[i][elem];
             printf("B[%d][%d]:%d\n",i,elem,vet[t]);
             elem++;
             t++;

          }


          elem=0;
          char *r;
          for(i=0;i<t;i++)
          {int num=vet[i];

            w=cancellaB(B,num,m);
           printf("cancella :%d\n",vet[i]);
           r=HS(A,B,n,w,ini,k-1,D,vm);
             if(r!=NULL)
             {           printf("stampa3 %d\n",num);
                         r[num]='1';


             }
             if(r==NULL)
             {
                     *r=NULL;
                      printf("stampa no HS\n");

             }
            elem=0;

         for(j=0;j<vm;j++)
           {
              while (D[j][elem]!=-1)
                { printf("lolo1 B[%d][%d]=D[%d][%d] :=%d  =  %d\n",j,elem,j,elem,B[j][elem],D[j][elem]);
                B[j][elem]=D[j][elem];
              printf("lolo2\n");
              elem++;
                }
           B[j][elem]=-1;
            elem=0;
          }


          }
           return r;



}


int main (void)
{

 int n,m,i,j,k;
 int elem=0;
 int A[100];
 int B[100][100];
 printf("======HITTING SET PROBLEM======\n\n");
 printf("inserisci il numero di elementi nell'insieme A\n");
 scanf("%d",&n);
 printf("inserisci il numero di sottoinsiemi di A\n");
 scanf("%d",&m);
  printf("inserisci k\n");
 scanf("%d",&k);

 for(i=0;i<n;i++)
 {
    printf("inserisci l'elemento %d-esimo dell'insieme A\n",i);
    scanf("%d",&A[i]);
 }
 printf("\n\n");
 for(i=0;i<m;i++)
 {
  printf("Quanti elementi contiene l'insieme B%d-esimo?\n",i);
  scanf("%d",&elem);

  for(j=0;j<elem;j++)
  {
     printf("inserisci l'elemento nell'insieme \n");
     scanf("%d",&B[i][j]);
  }
  B[i][elem]=-1;

 }
  int D[100][100];

  stampaInsiemeA(A,n);
  stampaInsiemiB(B,m);
  elem=0;
  for(j=0;j<m;j++)
           {
              while (B[j][elem]!=-1)
                {
                  D[j][elem]=B[j][elem];
                  elem++;
                }
                elem=0;
           }


  char *s=HS( A,B,n,m,n,k,D,m);
  if(s!=NULL)
  {
     printf("esiste HS di cardinalita %d ed e':%s\n",k,s);
  }
  else
  {
      printf("non esiste HS di cardinalita %d\n",k);
  }
 system("pause");
 return 0;
}