(*  Implémentation naïve 
à l'aide d'une liste triée *)


type f_p = ( int * string ) list ref ;;


let (file_1 : f_p ) = ref [ ( 15 , "tache_a" ) ; ( 7 , "tache_b" ) ;
 ( 3 , "tache_c" ) ];;


(*  creation de file vide  *)
let cree_file () =
	(ref [] : f_p) ;;
	
(*  File vide  *)
let file_vide (f : f_p ) =
	f = ref [] ;;   (* ou !f = []  *)
	
let file_2 = cree_file() ;;

file_vide file_1 ;;


(*  Fonction extraction  *)

let extraction (f : f_p ) =
	if file_vide f then failwith " erreur extraction file vide "
	else
		begin
			let tete = List.hd (!f ) in
			f := List.tl ( !f ) ;
			snd (tete) 		
		end;;
		
		
extraction file_1 ;;


(*  Ajout d'une tache  *)
let ajout (f : f_p ) ( poids , tache ) =
	let rec inserer liste (p , t ) =
			match liste with
				| [] -> [ (p,t)]
				| (poids_tete , tache_tete ) :: reste when poids_tete > p ->
			(poids_tete , tache_tete ) :: ( inserer reste (p,t) )	
				| (poids_tete , tache_tete ) :: reste -> 
			(p,t) :: liste 
	in
	f := inserer (!f)( poids , tache )  ;;


ajout file_1 ( 12 , "tache_d" ) ;;

file_1 ;;

ajout file_1 ( 2 , "tache_e" ) ;;

file_1 ;;

ajout file_1 ( 23 , "tache_f" ) ;;

file_1 ;;



(*  Implémentation à l'aide d'un arbre *)

type fp_arbre = V | N of fp_arbre *(int*string) * fp_arbre;;

let ex_1 = N(N(N(N(V,(12,"h"),V)
,(15,"e"),V),
(23,"c"), N(V,(7,"f"),V)),
(25,"a"),
N(N(V,(14,"g"),V),(19,"d"),V));;

let cree_file () =
	V;;

let file_vide f =
	f = V ;;

let tache_prioritaire f =
	if file_vide f then failwith " erreur file vide"
	else
	let N(a_g , (p,t) , a_d ) = f in t;;

let rec fusion file_1 file_2 =
	match (file_1 , file_2 ) with
		| file_1 , V -> file_1
		| V, file_2 -> file_2
		| N(ag_1 , (p_1 , t_1 ) , ad_1 ) , N(ag_2 , (p_2 , t_2 ) , ad_2 )
		->  if p_1 > p_2 then
					N(fusion ag_1 file_2 , (p_1 ,t_1 ) , ad_1 )
					else
					N( ag_2 , (p_2 ,t_2 ) , fusion file_1 ad_2 );;


let supprime f =
			if file_vide f then failwith " pb de file vide "
			else
				let N(ag,e , ad ) = f in fusion ag ad ;;
		
		
supprime ex_1 ;;


let ajout f ( poids , tache ) =
	fusion f (N(V , (poids , tache ) , V ));;
	
	

let rec construction_file liste_tache =
	match liste_tache with
		| [] -> V
		| e :: reste -> ajout  (construction_file reste ) e;;

construction_file [(15,"a")  ;  ( 7 , "c" ) ; ( 12 , "d") ;( 25 , "b" ) ];;



(*  Structure de tas  *)

type f_p_tab = int array ;;
let ex_1 : f_p_tab = [| 10 ; 34; 25; 23 ; 15 ; 12 ; 18 ; 11 ;
13 ; 9 ; 6 ; 0 ;0 ; 0 ;0 ; 0 ; 0 ; 0 ; 0 ; 0 |];;	
	
let cree_file () =
		Array.make 20 0 ;;

let file_vide f =
	f.(0) = 0 ;;

let echange tab i j =
	let temp = tab.(j) in
	tab.(j) <- tab.(i) ;
	tab.(i) <- temp ;;

let remonte tab i =
	let indice_courant = ref i in
	while !indice_courant > 1 && 
	tab.( !indice_courant /2 ) < tab.(!indice_courant ) do
		echange tab (!indice_courant /2 ) !indice_courant  ;
		indice_courant := !indice_courant /2  ;
	done ;;

let ajout (f : f_p_tab ) element =
		let new_taille = f.(0) +1 in
		f.(new_taille) <- element ;
		remonte f new_taille ;
		f.(0) <- new_taille ;;

ajout ex_1 39 ;;	

ex_1 ;;	
		

let rec percole (f : f_p_tab ) i =
	let n= f.(0) in
	(* cas terminaux  *)
	if (2*i > n) 
	 then ()
			(* le cas de feuille *)
	else
		if (2*i+1 > n) && f.(2*i) < f.(i) then ()
			(* cas d'un seul fils  bien range *)
		else 
			if f.(2*i+1) < f.(i) && f.(2*i) < f.(i) then ()
			(*  bien range  *)
	else
				begin
					if (2*i = n) then (*  un seul fils mal range *)
							begin
								echange f (2*i) i ;
							end
					else (*  deux fils mal range *)
						if f.(2*i) < f.(2*i +1 ) then
							begin
							echange f (2*i +1) i ;
							percole f (2*i+1) ;
							end
							else
							begin
							echange f (2*i) i ;
							percole f (2*i) ;
							end
				end ;;
	
	
percole ex_1 3 ;;

ex_1;;

let ex_2 = [|11; 14; 34; 23; 15; 25; 18; 11;
 13; 9; 6; 12; 0; 0; 0; 0; 0; 0; 0; 0|]		;;
 
percole ex_2 1 ;; 

ex_2 ;;
		
let supprime (f : f_p_tab ) =		
		if file_vide f then failwith "la file est vide"
		else
			begin
				let n = f.(0) in
				echange f 1 n ;
				f.(0) <- f.(0) -1 ;
				percole f 1 ;			
			end;;

ex_1 ;;

supprime ex_1	;;	

ex_1 ;;
		
	
let ex_tab =
		[| 8;5;4;1;3;6;9;12;2|];;
supprime ex_tab ;;

ex_tab ;;		
		
		
(*  Tri par tas  *)

let fil_of_tab tab =
		let n = tab.(0) in
		for i = (n+1)/2 downto 1 do
			(*  ou for i = 1 to (n+1)/2  *)
		percole tab i ;
		(*  ou percole tab ((n+1)/2-i+1 ) *)
		done ;
		tab ;;


let ex_tab =
		[| 8;5;4;1;3;6;9;12;2|];;
fil_of_tab ex_tab ;;	


let tri_tas tab =
		let f = fil_of_tab tab in
		while f.(0) <> 0 do
			supprime f
		done ;
		f ;;

tri_tas	[| 8;5;4;1;3;6;9;12;2|] ;;