1 (***********************************************************************)
5 (* Kim Nguyen, LRI UMR8623 *)
6 (* Université Paris-Sud & CNRS *)
8 (* Copyright 2010-2013 Université Paris-Sud and Centre National de la *)
9 (* Recherche Scientifique. All rights reserved. This file is *)
10 (* distributed under the terms of the GNU Lesser General Public *)
11 (* License, with the special exception on linking described in file *)
14 (***********************************************************************)
17 type node = Naive_tree.node
18 type cell = { node : node;
23 type t = { mutable length : int;
25 mutable last : cell; }
27 let rec nil = { node = Naive_tree.nil;
30 let create () = { length = 0;
36 if c != nil then begin
46 let length l = l.length
47 let is_empty l = l.head == nil
50 if is_empty l then failwith "pop"
52 let v = l.head.node in
53 let nhead = l.head.next in
55 if nhead == nil then l.last <- nil;
61 let ncell = { node = n;
64 if l.head == nil then begin
71 l.length <- l.length + 1
74 let push_back n l = add n l
76 let ncell = { node = n;
79 if l.head == nil then begin
85 l.length <- l.length + 1;
89 let len2 = l2.length in
90 if len2 != 0 then begin
91 l1.length <- l1.length + len2;
92 l1.last.next <- l2.head;
101 let finished i = i == nil
105 if finished i then l2 else begin
110 loop (create ()) (head l)