// réseau de communication avec débordement politique 1

function [l]=deux_en_un (i,j,n)
	x=max(i,j)			
	y=min(i,j)			
	l=(x-y)+(2*n-y)*(y-1)/2
endfunction	

function [x,y]=un_en_deux (l,n)
	delta=(2*n-1)^2+8*(1-l)
	y=int(((2*n+1)-sqrt(delta))/2)
	x=l+y-(2*n-y)*(y-1)/2
endfunction	

function [l]=circuits(i,j,tab,n) 	//rend le tableau des C circuits joignant les villes i,j
	x=max(i,j)			//utile pour ne pas utiliser un tableau à 2 dimensions
	y=min(i,j)			//couteux en espace mémoire
	l=tab((x-y)+(2*n-y)*(y-1)/2,:,1)	// utile egalement pour le tableau d'occupation, rend alors le nombre de cicuits utilisés entre i et j
endfunction


function [l]=occupation(i,j,tab,n) 	//Idem pour un tableau à une dimansion (l'occupation)
	x=max(i,j)			//rend alors le nombre de cicuits utilisés entre i et j
	y=min(i,j)
	l=tab((x-y)+(2*n-y)*(y-1)/2)	
endfunction


function []=sauvecircuit (i,j,t,tab,n) // t est le nouveau tableau des cicuits joignant les villes i et j
	x=max(i,j)
	y=min(i,j)
	tab((x-y)+(2*n-y)*(y-1)/2,:,1)=t
endfunction


function []=sauveoccupation (i,j,t,tab,n) // t est la nouvelle valeur de l'occupation entre les villes i et j
	x=max(i,j)
	y=min(i,j)
	tab((x-y)+(2*n-y)*(y-1)/2)=t
endfunction


function [res]=CalculIntP2(a,b,n,C,DureeEtat,TabOccupation) 	// calcul de int(0,t,1(X=C)*...)
	if (TabOccupation(deux_en_un(a,b,n))<C) then		// DureeEtat:temps depuis lequel on est dans cet etat
		res=0
	else
		somme=0
		for i = 1:n
			if (i<>a & i<>b) then
				if ((TabOccupation(deux_en_un(a,i,n))<C) & (TabOccupation(deux_en_un(i,b,n))<C)) then somme=somme +1;end
			end
		end
		res = DureeEtat * (1- somme/(n-2))
	end
endfunction


function [TempsActuel,Tt,Tt2,Ttlast]=ChangementEtat(TempsActuel,NouveauTemps,TabOccupation,Tt,n,C,Tt2,Ttlast) //function à executer lorsque l'on change d'etat (ajout ou suppression d'un appel). Pour le calcul de Tt
							//avant de changer le tableau d'occupation
	if (Ttlast+1)*DeltaT<NouveauTemps then //on ne refait le calcul des Tt que si une sauvegarde de Tt2 va etre faite
		for i=1:(n^2-n)/2
			[a,b]=un_en_deux(i,n)
			Tt(i)=Tt(i)+CalculIntP2(a,b,n,C,NouveauTemps-TempsActuel,TabOccupation)
		end
	end
	
	while (Ttlast+1)*DeltaT<NouveauTemps		//calcul des Tt2
		Ttlast=Ttlast+1
		for i=1:(n^2-n)/2
			Tt2(i,Ttlast)=Tt(i)/(Ttlast*DeltaT)
		end
	end
		
	TempsActuel=NouveauTemps
endfunction //Pour l'appel: [TempsActuel,Tt,Tt2,Ttlast]=ChangementEtat(TempsActuel,???,TabOccupation,Tt,n,C,Tt2,Ttlast)


function [Tt,Tt2]=SimulTelP2 (rho,C,n,Tmax,DeltaT) // Politique 2 // C circuits par ligne n villes
					//DeltaT est le temps entre chaque mesure pour Tt2
	ligne=zeros((n^2-n)/2,C,2) 	//simule les lignes par un tableau à 2 dimensions s'il y a zero alors pas d'appel sinon l'appel fini a t
					// Pour le 3 eme indice: si 1 alors rend t, si 2 alors rend la troisième ville concerné par cet appel
					//si connexion directe entre a et b avec a<b alors rend b
	Tt=zeros(1,(n^2-n)/2) //en fait Tt*t //on utilise deux_en_un() pour connaitre Tt(ab,2,n)
	Tt2=zeros((n^2-n)/2,Tmax/DeltaT)	//effectue une mesure de Tt2 tous les DeltaT
	Ttlast=0				//dernière mesure effectuée pour les Tt2
	TabOccupation=zeros(1,(n^2-n)/2)
	ProchainDecrochage=zeros(1,(n^2-n)/2) //donne le prochain decrochage entre les villes a et b
	TempsActuel=0
	lambda=C*rho
	NbLiason=(n^2-n)/2

	for i=1:NbLiason 	//remplissage du tableau du prochain decrochage
		ProchainDecrochage(i)= grand(1,1,'exp', 1/lambda)
	end
	

	while (TempsActuel<Tmax)
		Mini=ProchainDecrochage(1)
		imin=1
		for i=2:NbLiason //recherche du prochain appel
			if ProchainDecrochage(i)<Mini then Mini=ProchainDecrochage(i);imin=i;end
		end 
		ProchainAppel=Mini

		for j=1:NbLiason
			tempt=ligne(j,:,1) //ceci permet d'accelerer les calculs: le temp d'accés à un tableau à 3 dimensions est très long
			for i=1:C
				if (tempt(i)>0) then 
					if tempt(i)<Mini then Mini=tempt(i);imin=i;jmin=j; end
				end
			end
		end
		

		if (Mini==ProchainAppel) then //le prochain evenement est un appel
			//Ajout d'un nouvel appel si possible
		
			if (TabOccupation(imin)==C) then //ligne a à b saturée
				// tentative par une autre ligne
				[a,b]=un_en_deux(imin,n)  //a>b
				rand('uniform')
				temp=int(rand()*(n-2))+1 //tirage aléatoire de la ville par où passer
				if (temp>=b) then
					temp=temp+1
					if (temp>=a) then temp=temp+1;end //pour que c<>b et c<>a
				end
				if (TabOccupation(deux_en_un(a,temp,n))==C |TabOccupation(deux_en_un(temp,b,n))==C) then
					[TempsActuel,Tt,Tt2,Ttlast]=ChangementEtat(TempsActuel,ProchainDecrochage(imin),TabOccupation,Tt,n,C,Tt2,Ttlast)	//annulation de l'appel
					ProchainDecrochage(imin)=ProchainDecrochage(imin)+grand(1,1,'exp', 1/lambda)						
				else
					//nouvel appel entre a et temp, et entre temp et b 
					
					//recherche d'une ligne entre a et temp
					lign=0
					for i =1:C
						if ligne(deux_en_un(a,temp,n),i,1)==0 then lign=i;break;end
					end
					
					lign2=0 //recherche entre temp et b
					for i =1:C
						if ligne(deux_en_un(b,temp,n),i,1)==0 then lign2=i;break;end
					end
					ligne(deux_en_un(a,temp,n),lign,1)=ProchainDecrochage(imin)+grand(1,1,'exp',1)
					ligne(deux_en_un(b,temp,n),lign2,1)=ligne(deux_en_un(a,temp),lign,1)
					ligne(deux_en_un(a,temp,n),lign,2)=b
					ligne(deux_en_un(b,temp,n),lign2,2)=a
					[TempsActuel,Tt,Tt2,Ttlast]=ChangementEtat(TempsActuel,ProchainDecrochage(imin),TabOccupation,Tt,n,C,Tt2,Ttlast)
					TabOccupation(deux_en_un(a,temp,n))=TabOccupation(deux_en_un(a,temp,n))+1
					TabOccupation(deux_en_un(b,temp,n))=TabOccupation(deux_en_un(b,temp,n))+1
					ProchainDecrochage(imin)=ProchainDecrochage(imin)+grand(1,1,'exp',1/lambda)
				end				
			else //ligne a à b non saturée
	 			//recherche d'une ligne libre
				for i=1:C
					if (ligne(imin,i,1)==0) then lign=i;break:end  //lign est une ligne libre
				end
				ligne(imin,lign,1)=ProchainDecrochage(imin)+grand(1,1,'exp',1)
				[a,b]=un_en_deux(imin,n) 	//a>b
				ligne(imin,lign,2)=a 	//dans ce cas, on met max(a,b) dans ligne(,,2)
				[TempsActuel,Tt,Tt2,Ttlast]=ChangementEtat(TempsActuel,ProchainDecrochage(imin),TabOccupation,Tt,n,C,Tt2,Ttlast)
				ProchainDecrochage(imin)=ProchainDecrochage(imin)+grand(1,1,'exp',1/lambda)
				TabOccupation(imin)=TabOccupation(imin)+1		
			end
		else	//sinon fin de l'appel imin,jmin
			// jmin est l'entier représentant la ligne entre la ville a et b
			// imin est l'entier représentant le circuit de cette ligne
			[a,b]=un_en_deux (jmin,n)
			[TempsActuel,Tt,Tt2,Ttlast]=ChangementEtat(TempsActuel,ligne(jmin,imin,1),TabOccupation,Tt,n,C,Tt2,Ttlast)
			if ligne(jmin,imin,2)<>a then //cas où la communication n'est établie directement entre a et b
				c=ligne(jmin,imin,2)
				//il existe deux possibilités: a <-> b <-> c ou c <-> a <-> b
				for i=1:C
					if ligne(deux_en_un(b,c,n),i,1)==ligne(jmin,imin,1) then cas=1;lign=i;end //cas b<->c
					if ligne(deux_en_un(a,c,n),i,1)==ligne(jmin,imin,1) then cas=2;lign=i;end //cas a<->c
				end
				if cas==0 then disp("Erreur");end
				if cas==1 then	//b<->c
					ligne(deux_en_un(b,c,n),lign,1)=0
					TabOccupation(deux_en_un(b,c,n))=TabOccupation(deux_en_un(b,c,n))-1
				else
					ligne(deux_en_un(a,c,n),lign,1)=0
					TabOccupation(deux_en_un(a,c,n))=TabOccupation(deux_en_un(a,c,n))-1				
				end
			end
			ligne(jmin,imin,1)=0
			TabOccupation(jmin)=TabOccupation(jmin)-1
		end
	end
endfunction