1
(**************************************************************************)
5
(* Fran�ois Pottier and Yann R�gis-Gianas, INRIA Rocquencourt *)
7
(* Copyright 2005 Institut National de Recherche en Informatique et *)
8
(* en Automatique. All rights reserved. This file is distributed *)
9
(* under the terms of the Q Public License version 1.0, with the *)
10
(* change described in file LICENSE. *)
12
(**************************************************************************)
33
let rec mapd f = function
41
let a = Array.init n f in
43
Array.fold_left (fun count element ->
44
if element then count + 1 else count
47
let tabulateo number fold n f =
48
let a = Array.create n None in
50
let () = fold (fun () element ->
51
let image = f element in
52
a.(number element) <- image;
64
let rec truncate k xs =
71
x :: truncate (k-1) xs
74
if List.length xs <= k then xs else truncate k xs
76
module IntSet = Set.Make (struct
81
let separated_list_to_string printer separator list =
83
let rec loop x = function
99
let index_map string_map =
100
let n = StringMap.cardinal string_map in
101
let a = Array.create n None in
102
let conv, _ = StringMap.fold
103
(fun k v (conv, idx) ->
104
a.(idx) <- Some (k, v);
105
StringMap.add k idx conv, idx + 1)
106
string_map (StringMap.empty, 0)
108
((fun n -> snd (unSome a.(n))),
109
(fun k -> StringMap.find k conv),
110
(fun n -> fst (unSome a.(n))))
112
let support_assoc l x =
117
let index (strings : string list) : int * string array * int StringMap.t =
118
let name = Array.of_list strings
119
and n, map = List.fold_left (fun (n, map) s ->
120
n+1, StringMap.add s n map
121
) (0, StringMap.empty) strings in
124
(* Turning an implicit list, stored using pointers through a hash
125
table, into an explicit list. The head of the implicit list is
126
not included in the explicit list. *)
128
let materialize (table : ('a, 'a option) Hashtbl.t) (x : 'a) : 'a list =
130
match Hashtbl.find table x with
138
(* [iteri] implements a [for] loop over integers, from 0 to
142
for i = 0 to n - 1 do
146
(* [foldi] implements a [for] loop over integers, from 0 to [n-1],
147
with an accumulator. [foldij] implements a [for] loop over
148
integers, from [start] to [n-1], with an accumulator. *)
150
let foldij start n f accu =
151
let rec loop i accu =
155
loop (i+1) (f i accu)
162
(* [qfold f accu q] repeatedly takes an element [x] off the queue [q]
163
and applies [f] to the accumulator and to [x], until [q] becomes
164
empty. Of course, [f] can add elements to [q] as a side-effect.
166
We allocate an option to ensure that [qfold] is tail-recursive. *)
168
let rec qfold f accu q =
180
(* [qiter f q] repeatedly takes an element [x] off the queue [q] and
181
applies [f] to [x], until [q] becomes empty. Of course, [f] can add
182
elements to [q] as a side-effect. *)
192
let rec smap f = function
197
and xs' = smap f xs in
198
if x == x' && xs == xs' then
204
let s = String.copy s in
205
let n = String.length s in
206
for i = 0 to n - 1 do