Skip to content
This repository
Newer
Older
100644 504 lines (419 sloc) 16.251 kb
fccc6851 » MLstate
2011-06-21 Initial open-source release
1 (*
2 Copyright © 2011 MLstate
3
4 This file is part of OPA.
5
6 OPA is free software: you can redistribute it and/or modify it under the
7 terms of the GNU Affero General Public License, version 3, as published by
8 the Free Software Foundation.
9
10 OPA is distributed in the hope that it will be useful, but WITHOUT ANY
11 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for
13 more details.
14
15 You should have received a copy of the GNU Affero General Public License
16 along with OPA. If not, see <http://www.gnu.org/licenses/>.
17 *)
18 exception IteratorEnd
19
20 (** Big-Endian Particia tree maps, from "Fast Mergeable Integer Maps", Chris Okasaki, Andrew Gill
21 @author Louis Gesbert *)
22
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
23 (*In the comments, low means on the right, hence the bits whose value is
24 smaller. If a number is b_4b_3b_2b_1, then b_1 is the lowest bit and b_4 the highest
25 When we speak of "bit m" we will mean the bit k=log(m), and we assume
26 that m=2^k - hence m has only one 1 in his binary representation*)
27
28 (*Big-endian means that branches are shared for paths whose higher bits are
29 equal*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
30 type key = int
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
31
fccc6851 » MLstate
2011-06-21 Initial open-source release
32 type 'a t =
33 | Empty
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
34 (*A tree with one element whose index is the int*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
35 | Lf of int * 'a
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
36 (*A tree with two subtree, we assume that the index of both subtree are
37 equal on bit higher than mask, and the bit at position mask is 0 on the
38 left subtree, and 1 on the right subtree.
39 We require that the m lower bits are 01111...11*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
40 | Br of int (* prefix *) * int (* branching bit (mask) *) * 'a t * 'a t
41
42 let empty = Empty
43
44 let is_empty t = Empty = t
45
46 let singleton k v = Lf (k,v)
47
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
48 (** Sets bit m to 0, and all lower bit to 1*)
49 let mask i m = if m > 0 then (i lor (m-1)(*one-ing the bit at post lower than m*)) land (lnot m) (*zeroing bit m*)else 0
fccc6851 » MLstate
2011-06-21 Initial open-source release
50
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
51 (**is bit mth equal to 0*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
52 let zerobit i m = (0 = i land m)
53
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
54 (* Put all bits to 0 from bit m leftwards until we found the highest bit*)
55 (**The highest bit, assuming there is one at least at bit m, else 0*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
56 let highestbit i m =
57 let rec aux i =
58 let m = i land (-i) in (* lowest bit of i *)
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
59 if i = m (* If i has only one bit, which is the lowest one, or i=0*)
60 then i else aux (i - m (*i without its lowest bit*))
61 in aux (i land (lnot (m - 1))
62 (*bits at position strictly lower than m are zeroed*))
fccc6851 » MLstate
2011-06-21 Initial open-source release
63
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
64 (** Highest bit where p1 and p2 differ at bit m or higher, else 0*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
65 let branchingbit p1 p2 m = highestbit (p1 lxor p2) m
66
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
67 (** A tree whith two subtrees, t1 and t2, whose indexes, p1 and p2.
68 We assume that they differ only at position m or higher*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
69 let join p1 t1 p2 t2 m =
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
70 (*the position of the highest difference at bit m or higher*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
71 let m = branchingbit p1 p2 m in
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
72 (*if the first different bit is 0 in p1*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
73 if zerobit p1 m
74 then Br (mask p1 m, m, t1, t2)
75 else Br (mask p1 m, m, t2, t1)
76
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
77
fccc6851 » MLstate
2011-06-21 Initial open-source release
78 let rec add k v t = match t with
79 | Lf (k',_v') ->
80 if k = k' then Lf (k, v)
81 else join k (Lf (k, v)) k' t 1
82 | Br (p,m,t1,t2) when mask k m = p ->
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
83 (*if k and m are equal on bit strictly higher than m*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
84 if zerobit k m
85 then Br (p, m, add k v t1, t2)
86 else Br (p, m, t1, add k v t2)
87 | Br (p,m,_t1,_t2) ->
5b18026a » Arthur Milchior
2011-06-28 [enhance] Stdlib: Comments in Standard Library
88 (*There is a difference on bit m or an higher bit*)
fccc6851 » MLstate
2011-06-21 Initial open-source release
89 join k (Lf (k, v)) p t (m lsl 1)
90 | Empty -> Lf (k, v)
91
92 let replace k rep t =
93 let rec aux = function
94 | Lf (k', v') ->
95 if k = k' then Lf (k, rep (Some v'))
96 else join k (Lf (k, rep None)) k' t 1
97 | Br (p, m, t1, t2) when mask k m = p ->
98 if zerobit k m
99 then Br (p, m, aux t1, t2)
100 else Br (p, m, t1, aux t2)
101 | Br (p, m, _t1, _t2) ->
102 join k (Lf (k, rep None)) p t (m lsl 1)
103 | Empty -> Lf (k, rep None)
104 in
105 aux t
106
107 let rec add_fi f k v t = match t with
108 | Lf (k',v') ->
109 if k = k' then Lf (k, f k v v')
110 else join k (Lf (k,v)) k' t 1
111 | Br (p,m,t1,t2) when mask k m = p ->
112 if zerobit k m
113 then Br (p, m, add_fi f k v t1, t2)
114 else Br (p, m, t1, add_fi f k v t2)
115 | Br (p,m,_t1,_t2) ->
116 join k (Lf (k, v)) p t (m lsl 1)
117 | Empty -> Lf (k,v)
118
119 let rec safe_add k v t =
120 add_fi (fun _ _ -> raise (Invalid_argument "Base.Map.safe_add")) k v t
121
122 let rec find_opt k t = match t with
123 | Br (_,m,tl,tr) -> if zerobit k m then find_opt k tl else find_opt k tr
124 | Lf (k',v) -> if k = k' then Some v else None
125 | Empty -> None
126
127 let rec findi_opt k t = match find_opt k t with
128 | Some v -> Some (k, v)
129 | None -> None
130
131 let find k t = match find_opt k t with Some v -> v | None -> raise Not_found
132 let findi k t = match find_opt k t with Some v -> k,v | None -> raise Not_found
133
134 let rec remove k t = match t with
135 | Br (_,_,Lf(k',_v),t') when k' = k -> t'
136 | Br (_,_,t',Lf(k',_v)) when k' = k -> t'
137 | Br (p,m,t1,t2) ->
138 if zerobit k m
139 then Br(p,m,remove k t1,t2)
140 else Br(p,m,t1,remove k t2)
141 | Lf (k',_v) when k = k' -> Empty
142 | n -> n
143
95c5f506 » OpaOnWindowsNow
2011-07-29 [fix] IntMap: update and update_default were no ops on new key
144 (* on_miss specify what to do when the key is not found
145 take the part of intmap that should contains the key *)
146 let rec update_gen k f t ~on_miss = match t with
fccc6851 » MLstate
2011-06-21 Initial open-source release
147 | Br (p,m,tl,tr) ->
148 if zerobit k m
95c5f506 » OpaOnWindowsNow
2011-07-29 [fix] IntMap: update and update_default were no ops on new key
149 then Br (p,m,update_gen k f tl ~on_miss,tr)
150 else Br (p,m,tl,update_gen k f tr ~on_miss)
fccc6851 » MLstate
2011-06-21 Initial open-source release
151 | Lf (k',v) when k=k' -> Lf (k,f v)
95c5f506 » OpaOnWindowsNow
2011-07-29 [fix] IntMap: update and update_default were no ops on new key
152 | n -> on_miss n
fccc6851 » MLstate
2011-06-21 Initial open-source release
153
95c5f506 » OpaOnWindowsNow
2011-07-29 [fix] IntMap: update and update_default were no ops on new key
154 let raise_Not_found _ = raise Not_found
155 let update k f t = update_gen k f t ~on_miss:raise_Not_found
156 let update_default k f default t = update_gen k f t ~on_miss:(fun m -> add k default m)
fccc6851 » MLstate
2011-06-21 Initial open-source release
157
158 let rec mem k t = match t with
159 | Br (_,m,tl,tr) -> if zerobit k m then mem k tl else mem k tr
160 | Lf (k',_v) when k=k' -> true
161 | _ -> false
162
163 (* We want some functions to be ordered. The patricia tree is ordered by
164 lexicographical order of bits, that is 0 < 1 < max_int < min_int < -1.
165 The only problem may be the first node when m = 0b1000..., ie m = min_int
166 (<=> m < 0).
167 So we embed the functions with the following hack, only modifying the
168 top-level call (so that the cost is negligible) ; it breaks the tree, but
169 returns a prefix suitable for integer comparison. *)
170 let ordertop f t = match t with
171 | Br (_p,m,tl,tr) -> if m < 0 then f (Br (-1, m, tr, tl)) else f t
172 | t -> f t
173
174 (* "repairs" the root of t' according to t, to call after ordertop for map-like functions *)
175 let ordertop_ret t t' = match t, t' with
176 | Br (p,m,_,_), Br (_,_,tl,tr) ->
177 if m < 0 then Br (p, m, tr, tl) else t'
178 | _, _ -> t'
179
180 let ordertop_and_ret f t = ordertop_ret t (ordertop f t)
181
182 let rec iter f t = match t with
183 | Br (_,_,tl,tr) -> iter f tl; iter f tr
184 | Lf (k,v) -> f k v
185 | Empty -> ()
186 let iter f = ordertop (iter f)
187
188 let rec rev_iter f t = match t with
189 | Br (_,_,tl,tr) -> rev_iter f tr; rev_iter f tl
190 | Lf (k,v) -> f k v
191 | Empty -> ()
192 let rev_iter f = ordertop (rev_iter f)
193
194 let rec map f t = match t with
195 | Br (p,m,tl,tr) -> Br (p, m, map f tl, map f tr)
196 | Lf (k,v) -> Lf (k, f v)
197 | Empty -> Empty
198 let map f = ordertop_and_ret (map f)
199
200 let rec mapi f t = match t with
201 | Br (p,m,tl,tr) -> Br (p, m, mapi f tl, mapi f tr)
202 | Lf (k,v) -> Lf (k, f k v)
203 | Empty -> Empty
204 let mapi f = ordertop_and_ret (mapi f)
205
206 let rec fold f t acc = match t with
207 | Br (_,_,tl,tr) -> fold f tr (fold f tl acc)
208 | Lf (k,v) -> f k v acc
209 | Empty -> acc
210 let fold f t acc = ordertop (fun t -> fold f t acc) t
211
212 let fold_range_compare _ = assert false
213
214 let rec fold_range f t k1 k2 acc = match t with
215 | Br (p,_,tl,tr) ->
216 let acc = if k1 <= p then fold_range f tl k1 k2 acc else acc in
217 if p < k2 then fold_range f tr k1 k2 acc else acc
218 | Lf (k,v) -> if k1 <= k && k <= k2 then f k v acc else acc
219 | Empty -> acc
220 let fold_range f t k1 k2 acc = ordertop (fun t -> fold_range f t k1 k2 acc) t
221
222 let fold_length ~start:_ ~length:_ = assert false (* TODO as soon as needed *)
223
224 let rec fold_rev f t acc = match t with
225 | Br (_,_,tl,tr) -> fold_rev f tl (fold_rev f tr acc)
226 | Lf (k,v) -> f k v acc
227 | Empty -> acc
228 let fold_rev f t acc = ordertop (fun t -> fold_rev f t acc) t
229
230 let rec fold_map f t acc = match t with
231 | Br (p,m,tl,tr) ->
232 let acc, tl = fold_map f tl acc in
233 let acc, tr = fold_map f tr acc in
234 acc, Br (p, m, tl, tr)
235 | Lf (k,v) ->
236 let acc, v = f k v acc in acc, Lf (k, v)
237 | Empty -> acc, Empty
238 let fold_map f t acc =
239 let acc, t' = ordertop (fun t -> fold_map f t acc) t in
240 acc, ordertop_ret t t'
241
242
243 let filter_val f t =
244 fold (fun k v acc -> if f v then add k v acc else acc) t empty
245
246 let filter_keys f t =
247 fold (fun k v acc -> if f k then add k v acc else acc) t empty
248
249 let rec compare f t1 t2 = match t1, t2 with
250 | Br (p1,m1,tl1,tr1), Br (p2,m2,tl2,tr2) ->
251 let k = Pervasives.compare (p1,m1) (p2,m2) in
252 if k <> 0 then k else
253 let k = compare f tl1 tl2 in
254 if k <> 0 then k
255 else compare f tr1 tr2
256 | Lf (k1,v1), Lf (k2, v2) ->
257 let k = Pervasives.compare k1 k2 in
258 if k <> 0 then k
259 else f v1 v2
260 | Empty, Empty -> 0
261 | Br _, Lf _ | Br _, Empty | Lf _, Empty -> -1
262 | Lf _, Br _ | Empty, Br _ | Empty, Lf _ -> 1
263
264 let rec equal f t1 t2 = match (t1, t2) with
265 | Br (p1,m1,tl1,tr1), Br (p2,m2,tl2,tr2) ->
266 p1 = p2 && m1 = m2 && equal f tl1 tl2 && equal f tr1 tr2
267 | Lf (k1,v1), Lf (k2, v2) ->
268 k1 = k2 && f v1 v2
269 | Empty, Empty -> true
270 | _, _ -> false
271
272 module Iter : (IterSig.S with type +'a element = int * 'a and type +'a structure = 'a t) = struct
273 type 'a structure = 'a t
274 type 'a element = int * 'a
275 type 'a t = ('a structure) list
276
277 let rec make_aux acc = function
278 | Empty -> acc
279 | Br (_,_,tl,tr) -> make_aux (tr :: acc) tl
280 | Lf (k,v) -> Lf (k,v) :: acc
281
282 let make m = make_aux [] m
283
284 let get = function
285 | Lf (k,v) :: _l -> k, v
286 | [] -> raise IteratorEnd
287 | _ -> assert false
288
289 let next = function
290 | Lf (_k, _v) :: Br (_,_,tl,tr) :: l -> make_aux (tr :: l) tl
291 | Lf (_k, _v) :: l -> l
292 | [] -> raise IteratorEnd
293 | _ -> assert false
294
295 let at_end i = i = []
296
297 (* TODO raise notimplemented, not just failwith *)
298 let remaining _i = failwith "NotImplemented: IntMap.Iter.remaining"
299 end
300
22584156 » Arthur Milchior
2011-06-28 [feature] Map: adding fold_map_2
301 (*this is not efficient, but at this time, this function is not called and is
302 here only to confom to the signature*)
303 (*todo: look if ordertop is needed, and can be applied to both tree*)
304 let fold_map2 f t t' acc =
305 (* the result of the map, the accumulator and the iterator*)
306 let rec aux iter acc = function
307 | Br (p,m,tl,tr) ->
308 let acc, tl, iter = aux iter acc tl in
309 let acc, tr, iter = aux iter acc tr in
310 acc, Br (p, m, tl, tr), iter
311 | Lf (k,v) ->
312 let ()=if Iter.at_end iter
313 then invalid_arg "intMap.fold_map2" in
314 let k',v' = Iter.get iter in
315 let () = assert (k=k')
316 and iter = Iter.next iter in
317 let acc, v = f k v v' acc in
318 acc, Lf (k, v), iter
319 | Empty ->
320 acc, Empty, iter
321 in
322 let iter' = Iter.make t' in
323 let acc, t, iter' = aux iter' acc t in
324 if Iter.at_end iter' then acc, t
325 else invalid_arg "intMap.fold_map2"
326
327
fccc6851 » MLstate
2011-06-21 Initial open-source release
328 module RevIter : (IterSig.S with type +'a element = int * 'a and type +'a structure = 'a t) = struct
329 type 'a structure = 'a t
330 type 'a element = int * 'a
331 type 'a t = ('a structure) list
332
333 let rec make_aux acc = function
334 | Empty -> acc
335 | Br (_,_,tl,tr) -> make_aux (tl :: acc) tr
336 | Lf (k,v) -> Lf (k,v) :: acc
337
338 let make m = make_aux [] m
339
340 let get = function
341 | Lf (k,v) :: _l -> k, v
342 | [] -> raise IteratorEnd
343 | _ -> assert false
344
345 let next = function
346 | Lf (_k, _v) :: Br (_,_,tl,tr) :: l -> make_aux (tl :: l) tr
347 | Lf (_k, _v) :: l -> l
348 | [] -> raise IteratorEnd
349 | _ -> assert false
350
351 let at_end i = i = []
352
353 let remaining _i = failwith "NotImplemented: IntMap.Iter.remaining"
354 end
355
356 let rec min t = match t with
357 | Br (_,_,tl,_tr) -> min tl
358 | Lf (k,v) -> k,v
359 | Empty -> raise Not_found
360 let min t = ordertop min t
361
708e8656 » Arthur Milchior
2011-06-28 [feature] Map: Adding the function choose
362 (*
363 Choose is min, because they are no value except on leaf
364 hence I must go to a leaf to find something. And min already
365 find a leaf
366 *)
367 let choose = min
368
e74f6b52 » Arthur Milchior
2011-06-28 [feature] libbase: choose_opt in Maps and Sets
369 let choose_opt t =
370 try Some (choose t) with | Not_found -> None
371
fccc6851 » MLstate
2011-06-21 Initial open-source release
372 let rec max t = match t with
373 | Br (_,_m,_tl,tr) -> max tr
374 | Lf (k,v) -> k,v
375 | Empty -> raise Not_found
376 let max t = ordertop max t
377
378 let rec find_inf k t = match t with
379 | Br (p,_,tl,tr) ->
380 if k <= p then find_inf k tl
381 else (try find_inf k tr with Not_found -> max tl)
382 | Lf (k',v) -> if k' <= k then k',v else raise Not_found
383 | Empty -> raise Not_found
384 let find_inf k t = ordertop (find_inf k) t
385
386 let rec find_sup k t = match t with
387 | Br (p,_,tl,tr) ->
388 if k <= p
389 then (try find_sup k tl with Not_found -> min tr)
390 else find_sup k tr
391 | Lf (k',v) -> if k' >= k then k',v else raise Not_found
392 | Empty -> raise Not_found
393 let find_sup k t = ordertop (find_sup k) t
394
395 let nearest k t =
396 let b = try Some (find_inf k t) with Not_found -> None in
397 let a = try Some (find_sup k t) with Not_found -> None in
398 match b,a with
399 | None, Some x | Some x, None -> x
400 | None, None -> raise Not_found
401 | Some (kb,vb), Some (ka,va) ->
402 if k - kb <= ka - k then kb, vb
403 else ka, va
404
405 let from_list l = List.fold_left (fun t (k,v) -> add k v t) empty l
406
407
408 let fold_assoc k v acc = (k, v) :: acc
409 let to_list t = fold_rev fold_assoc t []
410 let ordered_list t = fold_rev fold_assoc t []
411 let rev_ordered_list t = fold fold_assoc t []
412
413 let keys t = fold_rev (fun k _ acc -> k::acc) t []
414 let elts t = fold_rev (fun _ v acc -> v::acc) t []
415
416 (* FIXME: Random according to the distribution of bits, not the actual map *)
417 let rec random t = match t with
418 | Br (_p,_m,tl,tr) -> if Random.int 2 = 0 then random tl else random tr
419 | Lf (k,v) -> k, v
420 | Empty -> raise Not_found
421
422 let size t = fold (fun _ _ i -> i+1) t 0
423
424 let rec height t = match t with
425 | Br (_p,_m,tl,tr) -> Pervasives.max (height tl) (height tr) + 1
426 | Lf _ -> 1
427 | Empty -> 0
428
429 let rec merge_i f t1 t2 = match t1, t2 with
430 | Br (p1,m1,tl1,tr1), Br (p2,m2,tl2,tr2) ->
431 if p1 = p2 && m1 = m2 then (* same node *)
432 Br (p1, m1, merge_i f tl1 tl2, merge_i f tr1 tr2)
433 else if m2 lsr 1 > m1 lsr 1 && mask p1 m2 = p2 then (* p1 is a sub-node of p2 *)
434 if zerobit p1 m2
435 then Br (p2, m2, merge_i f t1 tl2, tr2)
436 else Br (p2, m2, tl2, merge_i f t1 tr2)
437 else if m1 lsr 1 > m2 lsr 1 && mask p2 m1 = p1 then (* p2 is a sub-node of p1 *)
438 if zerobit p2 m1
439 then Br (p1,m1,merge_i f tl1 t2 ,tr1)
440 else Br (p1,m1,tl1,merge_i f tr1 t2)
441 else (* disjoint nodes *)
442 join p1 t1 p2 t2 m1
443 | Lf (k1,v1), Lf (k2,v2) when k1 = k2 -> Lf (k1, f k1 v1 v2)
444 | Lf (k1,v1), t2 -> add_fi f k1 v1 t2
445 | t1, Lf (k2,v2) -> add_fi (fun k v2 v1 -> f k v1 v2) k2 v2 t1
446 | Empty, t | t, Empty -> t
447
448 let merge f t1 t2 = merge_i (fun _ -> f) t1 t2
449 let safe_merge t1 t2 =
450 merge (fun _ _ -> raise (Invalid_argument "Base.Map.safe_merge")) t1 t2
451
452 let rec decons = function
453 | Empty -> invalid_arg "IntMap.decons"
454 | Lf (key, val_) -> Empty, key, val_, Empty
455 | Br (_prefix, _mask, left, right) -> (
456 match left, right with
457 | Empty, Empty -> invalid_arg "IntMap.decons"
458 | left, Lf (key, val_)
459 | Lf (key, val_), left
460 -> left, key, val_, Empty
461 | br_left, br_right ->
462 let l_left, key, val_, l_right = decons br_left in
463 l_left, key, val_, (merge (fun _ a -> a) l_right br_right)
464 )
465
466 let rename f t =
467 fold (fun k v t -> add (f k) v t) t empty
468
469 (* cf doc *)
470 let pp sep ppe fmt t =
471 let fiter elt val_ =
472 ppe fmt elt val_ ;
473 Format.fprintf fmt sep
474 in
475 iter fiter t
476
477 let compare_key : int -> int -> int = Pervasives.compare
478
479 let diff map1 map2 =
480 fold (fun k v acc ->
481 if mem k map2 then
482 acc
483 else
484 add k v acc
485 ) map1 empty
486 let diff2 map1 map2 map3 =
487 fold (fun k v acc ->
488 if mem k map2 && not (mem k map3) then
489 acc
490 else
491 add k v acc
492 ) map1 empty
493
645f07a7 » Arthur Milchior
2011-07-11 [feature] libbase: Taking an element to show the difference between …
494 let example_diff s1 s2 =
495 let diff_ = diff s1 s2 in
496 match choose_opt diff_ with
497 | Some elt -> Some elt
498 | None ->
499 let diff = diff s2 s1 in
500 match choose_opt diff with
501 | Some elt -> Some elt
502 | None -> None
503
fccc6851 » MLstate
2011-06-21 Initial open-source release
504 let from_sorted_array _ = assert false
Something went wrong with that request. Please try again.