1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
(***********************************************************************)
(* *)
(* Objective Caml *)
(* *)
(* Pierre Weis, projet Cristal, INRIA Rocquencourt *)
(* *)
(* Copyright 2001 Institut National de Recherche en Informatique et *)
(* en Automatique. All rights reserved. This file is distributed *)
(* only by permission. *)
(* *)
(***********************************************************************)
exception File_vide;;
type 'a t =
| Vide | File of int * 'a * 'a t * 'a t;;
let vide = Vide;;
let rec enlve_sommet = function
| Vide -> raise File_vide
| File(prio, elt, Vide, Vide) -> Vide
| File(prio, elt, gauche, Vide) -> gauche
| File(prio, elt, Vide, droite) -> droite
| File(prio, elt, (File(prio_g, elt_g, _, _) as gauche),
(File(prio_d, elt_d, _, _) as droite)) ->
if prio_g < prio_d
then File(prio_g, elt_g, enlve_sommet gauche, droite)
else File(prio_d, elt_d, gauche, enlve_sommet droite);;
let extraire = function
| Vide -> raise File_vide
| File(prio, elt, _, _) as file -> (prio, elt, enlve_sommet file);;
let rec ajoute file prio elt =
match file with
| Vide ->
File(prio, elt, Vide, Vide)
| File(prio1, elt1, gauche, droite) ->
if prio <= prio1
then File(prio, elt, ajoute droite prio1 elt1, gauche)
else File(prio1, elt1, ajoute droite prio elt, gauche);;
|
