#include "tipos.h"       
#include <math.h> 

int coste_asaco()
{ 
	int i,coste=0;

    for(i=1;i<=num_color;i++)
    {       
    	coste -= v[i]*v[i];
    	coste += 2*v[i]*e[i];
    }                      
    
    return coste;
}

int sa_ilegal()
{       
	int best_color,legal=0;
	
	best_color = num_color=2*cota_sup; 
	
	do {
	    num_color--;
		color_inicial_aleat();
		if(num_color==1) return best_color;
		legal =	sa_2(7);   /* 30*/
		if(legal==0)
		{ 
			if(comprueba_color(num_color)!=1)
				 abortar("Error sa_ilegal");
			best_color = num_color;  
			/*printf("\n%d",num_color);*/
		} 
	}	
	while(legal==0);   
    
	return best_color;
}


int sa_2(int tope)
{  
	int freezecount,Sizefactor,Minpercent;
	float cutoff,tempfactor,t; 
	int r,changes,vert,new_color;
	long trials,tope_trials;
	int tope_change,proba;
	double prob;
	int *ilegales,f,f_change,best_f;
	
	Sizefactor =   4;        
	Minpercent =   30;        /* 30*/
	t		   =   2;
	cutoff     = (float) 0.1; /* 0.2*/
	tempfactor = (float) 0.95; /* 0.97*/ 
	
	freezecount=0;     
	ilegales=reserva_vector(num_color);
    best_f = f = ilegal(ilegales);  
    if(f==0) return 0;
    if(num_color<2) return f;
    
	while(freezecount < tope )
	{
		changes=0;
		trials=0; 
		tope_trials = (long) Sizefactor *num_color*n;
		tope_change = (int) (cutoff*num_color*n);
		while(trials   < tope_trials  &&
		      changes  < tope_change)
		{
			trials += 1;
			vert = random_vert_ilegal();
			new_color = getrandom(1,num_color); 
			while(new_color == uno[vert]->color)
				new_color = getrandom(1,num_color); 
				
		    f_change=c_ileg(vert,new_color);
		        
		    if(f_change <=0)
		    {
		     	changes +=1;
		     	f += f_change;
		     	actualiza_clases(ilegales,vert,new_color);
		    }
		    else
		    {
		       	prob = exp((double)(-f_change/t));
		       	proba = (int) 100*prob;
		       	r = getrandom(1,100);
		       	if(r <= proba )
		       	{
		        	changes += 1;
		        	f += f_change;
		     		actualiza_clases(ilegales,vert,new_color);
		        }
		    }   
		    if(f<best_f) {best_f=f; freezecount=0;}
		    if(f!=ilegales[0]) abortar("PProblemas");   
		    if(f==0) { free(ilegales); return 0; }
		}    
		t = tempfactor * t;
		if(changes/trials < Minpercent)
		    	freezecount++; 
	}
	free(ilegales);	
	return best_f;	
}	
   

int sa(int tope,int *posible)
{  
	int best_color,best_cost;
	int freezecount,Sizefactor,Minpercent;
	float cutoff,tempfactor,t; 
	int changes,vert,new_color;
	int coste_nuevo,delta,p,r;
	long trials,tope_trials;
	int tope_change,i,il_new,il_old;
	int *mejor_color,proba;
	double prob;
	
	Sizefactor =    2;        /* 2 */
	Minpercent =    2;
	t		   =   10;
	cutoff     = (float) 0.4;
	tempfactor = (float) 0.95;  /* 0.95*/
	num_color  =   50;
	
	mejor_color = reserva_vector(n);
	best_cost  = 30000;
	free(v);free(e);
		    
	color_inicial_aleat();
	cost = inicia_v_e_coste();
	best_color = num_color;
	freezecount=0;                     
	
	while(freezecount < tope )
	{
		changes=0;
		trials=0; 
		tope_trials = (long) Sizefactor *num_color*n;
		tope_change = (int) (cutoff*num_color*n);
		while(trials   < tope_trials  &&
		      changes  < tope_change)
		{
			trials += 1;
			vert = random_vert();
			new_color = getrandom(1,num_color+1);
		    if(new_color != uno[vert]->color)
		    {
		     	coste_nuevo=new_coste(vert,uno[vert]->color,
		     				new_color,&il_old,&il_new);
		     	delta = coste_nuevo - cost;
		     	if(delta <=0)
		     	{
		     		changes +=1;
		     		cost = coste_nuevo;
		            p = actualiza_solucion(vert,uno[vert]->color,
		            					new_color,il_old,il_new); 
		            /*cas=coste_asaco();
		            if(cost!=cas) abortar("Coste en sa");*/
		            if(p == 0 && cost<best_cost)
		            {         
		            	*posible=1;
		            	printf("\n %d",num_color); 
		            	best_color  = num_color;
		            	for(i=1;i<=n;i++) 
		            		mejor_color[i]=uno[i]->color;
		            	best_cost   = cost;
		            	freezecount = 0;
		            }
		        }
		        else
		        {
		        	prob = exp((double)(-delta/t));
		        	proba = (int) 100*prob;
		        	r = getrandom(1,100);
		        	if(r <= proba )
		        	{
		        		changes += 1;
		        		cost = coste_nuevo; 
		            	actualiza_solucion(vert,uno[vert]->color,
		            					new_color,il_old,il_new);
		            }
		         }
		    }
		}    
		t = tempfactor * t;
		if(changes/trials < Minpercent)
		    	freezecount++; 
	}
	for(i=1;i<=n;i++) 
		uno[i]->color=mejor_color[i];
	free(mejor_color);	
	return best_color;	
}	



int actualiza_solucion(int vert,int old_c,int new_c,
    int ilegales_old,int ilegales_new)
{
/* Devuelve un 0 si la nueva solucion es posible */
	int i,p;
	
	if(new_c==num_color+1) num_color++;
	
	v[old_c]--;
	v[new_c]++;
	e[old_c] -= ilegales_old;
	e[new_c] += ilegales_new;
	uno[vert]->color = new_c;
	
	
	if(v[old_c]==0) /* Hay un color menos */
	{               
		for(i=old_c;i<num_color;i++)
		{
			v[i]=v[i+1];	                  
	    	e[i]=e[i+1];
	    }                  
		for(i=1;i<=n;i++)
		{
			if(uno[i]->color > old_c)
				uno[i]->color--;
		}
		e[num_color]=0;
		v[num_color--]=0;
	}
	p=0;i=1;
	while(i<=n && p==0) if(e[i++]!=0) p=1;

    return p;             
}
	



int new_coste(int vert,int old_c,int new_c,
	int *ilegales_old,int *ilegales_new)
{                 
	int c,i;
	
	c  = cost;
	c += (v[old_c]*v[old_c]) -
		   	((v[old_c]-1)*(v[old_c]-1));
	c += (v[new_c]*v[new_c]) -
		   	((v[new_c]+1)*(v[new_c]+1));
	                              
	*ilegales_old=*ilegales_new=0;	                              
	for(i=1;i<=uno[vert]->adya[0];i++)
	{
		if(uno[ uno[vert]->adya[i]]->color==old_c)
			(*ilegales_old)++;
	    if(uno[ uno[vert]->adya[i]]->color==new_c)
			(*ilegales_new)++;
	}
	
	c -= (2*v[old_c]*e[old_c]) -
		   	(2*(v[old_c]-1)*(e[old_c]-(*ilegales_old)));
	c -= (2*v[new_c]*e[new_c]) -
		   	(2*(v[new_c]+1)*(e[new_c]+(*ilegales_new)));
		   	
	return c;
}
	
int inicia_v_e_coste()
{ 
	register i,j;
	int c,coste;
	
	v = reserva_vector(2 * num_color);
	e = reserva_vector(2 * num_color);	
	
	for(i=1;i<=n;i++)
	{   
		c = uno[i]->color;
		if(c==0 || c==-1) abortar("Error en coste");
		v[c]++;
		for(j=1;j<=uno[i]->adya[0];j++)	
        {
        	if(uno[ uno[i]->adya[j] ]->color == c)
        		e[c]++;
        }
    }
    
    for(i=1;i<=num_color;i++) e[i] /= 2;
    
    coste=0;
    for(i=1;i<=num_color;i++)
    {       
    	coste -=   v[i]*v[i];
    	coste += 2*v[i]*e[i];
    }                      
    
    return coste;
}

int random_vert()
{
	int clase,i,j,index;
	
	clase = getrandom(1,num_color);
	i 	  = getrandom(1,v[clase]);
   
    j=index=1;
    while(uno[index]->color !=clase)
   		index++;
   		
    while(j<i)
    {    
   		index++;
   		if(uno[index]->color==clase) j++;		
    }
    
    if(uno[index]->color != clase) abortar("random_vert");
    
    return index;
}