type 'a cycle_bien_cha”nˇ = Nil | Cellule of 'a cellule_de_cycle and 'a cellule_de_cycle = { valeur : 'a ; mutable lien_avant : 'a cycle_bien_cha”nˇ ; mutable lien_arri¸re : 'a cycle_bien_cha”nˇ } ;; let avance_cycle = function Nil -> Nil | Cellule c -> c.lien_avant ;; let recule_cycle = function Nil -> Nil | Cellule c -> c.lien_arri¸re ;; let valeur_cycle = function Nil -> raise Cycle_Vide | Cellule c -> c.valeur ;; let lien_avant_sur but = function Nil -> raise Cycle_Vide | Cellule c -> c.lien_avant <- but ;; let lien_arri¸re_sur but = function Nil -> raise Cycle_Vide | Cellule c -> c.lien_arri¸re <- but ;; let taille_cycle = function Nil -> 0 | cycle -> let rec compte n c = if c = cycle then n else compte (n+1) (avance_cycle c) in compte 1 (avance_cycle cycle) ;; let est_singleton = function Nil -> false | c -> c = (avance_cycle c) ;; let supprime_valeur_cycle = function Nil -> raise Cycle_Vide | c -> if (est_singleton c) then Nil else begin lien_avant_sur (avance_cycle c) (recule_cycle c) ; lien_arri¸re_sur (recule_cycle c) (avance_cycle c) ; avance_cycle c end ;; let ins¸re_devant x cycle = let c = Cellule { valeur = x ; lien_avant = (avance_cycle cycle) ; lien_arri¸re = cycle } in if cycle = Nil then begin lien_avant_sur c c ; lien_arri¸re_sur c c ; c end else begin lien_avant_sur c cycle ; lien_arri¸re_sur c (avance_cycle c) ; c end ;; let ins¸re_derri¸re x cycle = let c = Cellule { valeur = x ; lien_avant = cycle ; lien_arri¸re = (recule_cycle cycle) } in if cycle = Nil then begin lien_avant_sur c c ; lien_arri¸re_sur c c ; c end else begin lien_avant_sur c (recule_cycle c) ; lien_arri¸re_sur c cycle ; c end ;; let cycle_en_liste = function Nil -> [] | c -> let rec scan cycle accu = if cycle = c then (valeur_cycle c) :: accu else scan (recule_cycle cycle) ((valeur_cycle cycle) :: accu) in scan (recule_cycle c) [] ;; let rec liste_en_cycle = function [] -> Nil | a :: q -> ins¸re_devant a (recule_cycle (liste_en_cycle q)) ;;