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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| (* vim:set ts=4 sw=4: *)
type
'a cellule = {id: int; head : 'a; mutable next : 'a liste; mutable prev : 'a liste}
and
'a liste = Nil | Liste of 'a cellule
;;
let compteur = ref 1;;
let cons a l =
let res = {id=(!compteur); head=a ; next=l; prev=Nil} in
let _ = compteur := !compteur + 1 in
let p =
match l with
Nil -> Liste(res)
|Liste(c) -> c.prev
in
let _ = res.prev <- p in
let _ = match l with
Nil -> ()
|Liste(c) -> c.prev <- Liste(res)
in
let _ = if res.next = Nil then res.next <- Liste(res) in
Liste(res)
;;
let concat l1 l2 =
match (l1,l2) with
(Nil,_) -> l2
|(_,Nil) -> l1
|(Liste(c1),Liste(c2)) ->
let Liste(c1_p) = c1.prev in
let Liste(c2_p) = c2.prev in
c1_p.next <- l2 ;
c2.prev <- Liste(c1_p) ;
c2_p.next <- l1 ;
c1.prev <- Liste(c2_p) ;
l1
;;
let rec iter f l =
let first =
match l with
Nil -> 0
|Liste(c) -> c.id
in
let rec aux l =
match l with
Nil -> ()
|Liste(c) -> if ((c.id) <> first) then begin f (c.head) ; aux (c.next) end
in
match l with
Nil -> aux l
|Liste(c) -> f (c.head) ; aux (c.next)
;;
let print print_elt l =
print_string " [ " ;
iter (fun x -> print_elt x ; print_string " ") l ;
print_string "] " ; print_newline ()
;;
let main () =
let l = Nil in
print print_int l ;
let l1 = (cons 2 l) in
let l2 = (cons 3 l) in
print print_int (concat l1 l2)
;;
main ();; |