anil.recoil.org
My working unpac repository
1(**************************************************************************)
2(* *)
3(* OCaml *)
4(* *)
5(* Xavier Leroy, projet Cristal, INRIA Rocquencourt *)
6(* *)
7(* Copyright 1996 Institut National de Recherche en Informatique et *)
8(* en Automatique. *)
9(* *)
10(* All rights reserved. This file is distributed under the terms of *)
11(* the GNU Lesser General Public License version 2.1, with the *)
12(* special exception on linking described in the file LICENSE. *)
13(* *)
14(**************************************************************************)
15
16(* NOTE:
17 If this file is arrayLabels.mli, run tools/sync_stdlib_docs after editing it
18 to generate array.mli.
19
20 If this file is array.mli, do not edit it directly -- edit
21 arrayLabels.mli instead.
22 *)
23
24(** Array operations.
25
26 The labeled version of this module can be used as described in the
27 {!StdLabels} module.
28*)
29
30type 'a t = 'a array
31(** An alias for the type of arrays. *)
32
33external length : 'a array -> int = "%array_length"
34(** Return the length (number of elements) of the given array. *)
35
36external get : 'a array -> int -> 'a = "%array_safe_get"
37(** [get a n] returns the element number [n] of array [a].
38 The first element has number 0.
39 The last element has number [length a - 1].
40 You can also write [a.(n)] instead of [get a n].
41
42 @raise Invalid_argument
43 if [n] is outside the range 0 to [(length a - 1)]. *)
44
45external set : 'a array -> int -> 'a -> unit = "%array_safe_set"
46(** [set a n x] modifies array [a] in place, replacing
47 element number [n] with [x].
48 You can also write [a.(n) <- x] instead of [set a n x].
49
50 @raise Invalid_argument
51 if [n] is outside the range 0 to [length a - 1]. *)
52
53external make : int -> 'a -> 'a array = "caml_array_make"
54(** [make n x] returns a fresh array of length [n],
55 initialized with [x].
56 All the elements of this new array are initially
57 physically equal to [x] (in the sense of the [==] predicate).
58 Consequently, if [x] is mutable, it is shared among all elements
59 of the array, and modifying [x] through one of the array entries
60 will modify all other entries at the same time.
61
62 @raise Invalid_argument if [n < 0] or [n > Sys.max_array_length].
63 If the value of [x] is a floating-point number, then the maximum
64 size is only [Sys.max_array_length / 2].*)
65
66external create_float: int -> float array = "caml_array_create_float"
67(** [create_float n] returns a fresh float array of length [n],
68 with uninitialized data.
69 @since 4.03 *)
70
71val init : int -> (int -> 'a) -> 'a array
72(** [init n f] returns a fresh array of length [n],
73 with element number [i] initialized to the result of [f i].
74 In other terms, [init n f] tabulates the results of [f]
75 applied in order to the integers [0] to [n-1].
76
77 @raise Invalid_argument if [n < 0] or [n > Sys.max_array_length].
78 If the return type of [f] is [float], then the maximum
79 size is only [Sys.max_array_length / 2].*)
80
81val make_matrix : int -> int -> 'a -> 'a array array
82(** [make_matrix dimx dimy e] returns a two-dimensional array
83 (an array of arrays) with first dimension [dimx] and
84 second dimension [dimy]. All the elements of this new matrix
85 are initially physically equal to [e].
86 The element ([x,y]) of a matrix [m] is accessed
87 with the notation [m.(x).(y)].
88
89 @raise Invalid_argument if [dimx] or [dimy] is negative or
90 greater than {!Sys.max_array_length}.
91 If the value of [e] is a floating-point number, then the maximum
92 size is only [Sys.max_array_length / 2]. *)
93
94val init_matrix : int -> int -> (int -> int -> 'a) -> 'a array array
95(** [init_matrix dimx dimy f] returns a two-dimensional array
96 (an array of arrays)
97 with first dimension [dimx] and second dimension [dimy],
98 where the element at index ([x,y]) is initialized with [f x y].
99 The element ([x,y]) of a matrix [m] is accessed
100 with the notation [m.(x).(y)].
101
102 @raise Invalid_argument if [dimx] or [dimy] is negative or
103 greater than {!Sys.max_array_length}.
104 If the return type of [f] is [float],
105 then the maximum size is only [Sys.max_array_length / 2].
106
107 @since 5.2 *)
108
109val append : 'a array -> 'a array -> 'a array
110(** [append v1 v2] returns a fresh array containing the
111 concatenation of the arrays [v1] and [v2].
112 @raise Invalid_argument if
113 [length v1 + length v2 > Sys.max_array_length]. *)
114
115val concat : 'a array list -> 'a array
116(** Same as {!append}, but concatenates a list of arrays. *)
117
118val sub : 'a array -> int -> int -> 'a array
119(** [sub a pos len] returns a fresh array of length [len],
120 containing the elements number [pos] to [pos + len - 1]
121 of array [a].
122
123 @raise Invalid_argument if [pos] and [len] do not
124 designate a valid subarray of [a]; that is, if
125 [pos < 0], or [len < 0], or [pos + len > length a]. *)
126
127val copy : 'a array -> 'a array
128(** [copy a] returns a copy of [a], that is, a fresh array
129 containing the same elements as [a]. *)
130
131val fill : 'a array -> int -> int -> 'a -> unit
132(** [fill a pos len x] modifies the array [a] in place,
133 storing [x] in elements number [pos] to [pos + len - 1].
134
135 @raise Invalid_argument if [pos] and [len] do not
136 designate a valid subarray of [a]. *)
137
138val blit :
139 'a array -> int -> 'a array -> int -> int ->
140 unit
141(** [blit src src_pos dst dst_pos len] copies [len] elements
142 from array [src], starting at element number [src_pos], to array [dst],
143 starting at element number [dst_pos]. It works correctly even if
144 [src] and [dst] are the same array, and the source and
145 destination chunks overlap.
146
147 @raise Invalid_argument if [src_pos] and [len] do not
148 designate a valid subarray of [src], or if [dst_pos] and [len] do not
149 designate a valid subarray of [dst]. *)
150
151val to_list : 'a array -> 'a list
152(** [to_list a] returns the list of all the elements of [a]. *)
153
154val of_list : 'a list -> 'a array
155(** [of_list l] returns a fresh array containing the elements
156 of [l].
157
158 @raise Invalid_argument if the length of [l] is greater than
159 [Sys.max_array_length]. *)
160
161(** {1:comparison Comparison} *)
162
163val equal : ('a -> 'a -> bool) -> 'a array -> 'a array -> bool
164(** [equal eq a b] is [true] if and only if [a] and [b] have the
165 same length [n] and for all [i] in \[[0];[n-1]\], [eq a.(i) b.(i)]
166 is [true].
167
168 @since 5.4 *)
169
170val compare : ('a -> 'a -> int) -> 'a array -> 'a array -> int
171(** [compare cmp a b] compares [a] and [b] according to the shortlex order,
172 that is, shorter arrays are smaller and equal-sized arrays are compared
173 in lexicographic order using [cmp] to compare elements.
174
175 @since 5.4 *)
176
177(** {1 Iterators} *)
178
179val iter : ('a -> unit) -> 'a array -> unit
180(** [iter f a] applies function [f] in turn to all
181 the elements of [a]. It is equivalent to
182 [f a.(0); f a.(1); ...; f a.(length a - 1); ()]. *)
183
184val iteri : (int -> 'a -> unit) -> 'a array -> unit
185(** Same as {!iter}, but the
186 function is applied to the index of the element as first argument,
187 and the element itself as second argument. *)
188
189val map : ('a -> 'b) -> 'a array -> 'b array
190(** [map f a] applies function [f] to all the elements of [a],
191 and builds an array with the results returned by [f]:
192 [[| f a.(0); f a.(1); ...; f a.(length a - 1) |]]. *)
193
194val map_inplace : ('a -> 'a) -> 'a array -> unit
195(** [map_inplace f a] applies function [f] to all elements of [a],
196 and updates their values in place.
197 @since 5.1 *)
198
199val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
200(** Same as {!map}, but the
201 function is applied to the index of the element as first argument,
202 and the element itself as second argument. *)
203
204val mapi_inplace : (int -> 'a -> 'a) -> 'a array -> unit
205(** Same as {!map_inplace}, but the function is applied to the index of the
206 element as first argument, and the element itself as second argument.
207 @since 5.1 *)
208
209val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a array -> 'acc
210(** [fold_left f init a] computes
211 [f (... (f (f init a.(0)) a.(1)) ...) a.(n-1)],
212 where [n] is the length of the array [a]. *)
213
214val fold_left_map :
215 ('acc -> 'a -> 'acc * 'b) -> 'acc -> 'a array -> 'acc * 'b array
216(** [fold_left_map] is a combination of {!fold_left} and {!map} that threads an
217 accumulator through calls to [f].
218 @since 4.13 *)
219
220val fold_right : ('a -> 'acc -> 'acc) -> 'a array -> 'acc -> 'acc
221(** [fold_right f a init] computes
222 [f a.(0) (f a.(1) ( ... (f a.(n-1) init) ...))],
223 where [n] is the length of the array [a]. *)
224
225
226(** {1 Iterators on two arrays} *)
227
228
229val iter2 : ('a -> 'b -> unit) -> 'a array -> 'b array -> unit
230(** [iter2 f a b] applies function [f] to all the elements of [a]
231 and [b].
232 @raise Invalid_argument if the arrays are not the same size.
233 @since 4.03 (4.05 in ArrayLabels)
234 *)
235
236val map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
237(** [map2 f a b] applies function [f] to all the elements of [a]
238 and [b], and builds an array with the results returned by [f]:
239 [[| f a.(0) b.(0); ...; f a.(length a - 1) b.(length b - 1)|]].
240 @raise Invalid_argument if the arrays are not the same size.
241 @since 4.03 (4.05 in ArrayLabels) *)
242
243
244(** {1 Array scanning} *)
245
246val for_all : ('a -> bool) -> 'a array -> bool
247(** [for_all f [|a1; ...; an|]] checks if all elements
248 of the array satisfy the predicate [f]. That is, it returns
249 [(f a1) && (f a2) && ... && (f an)].
250 @since 4.03 *)
251
252val exists : ('a -> bool) -> 'a array -> bool
253(** [exists f [|a1; ...; an|]] checks if at least one element of
254 the array satisfies the predicate [f]. That is, it returns
255 [(f a1) || (f a2) || ... || (f an)].
256 @since 4.03 *)
257
258val for_all2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
259(** Same as {!for_all}, but for a two-argument predicate.
260 @raise Invalid_argument if the two arrays have different lengths.
261 @since 4.11 *)
262
263val exists2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
264(** Same as {!exists}, but for a two-argument predicate.
265 @raise Invalid_argument if the two arrays have different lengths.
266 @since 4.11 *)
267
268val mem : 'a -> 'a array -> bool
269(** [mem a set] is true if and only if [a] is structurally equal
270 to an element of [set] (i.e. there is an [x] in [set] such that
271 [compare a x = 0]).
272 @since 4.03 *)
273
274val memq : 'a -> 'a array -> bool
275(** Same as {!mem}, but uses physical equality
276 instead of structural equality to compare array elements.
277 @since 4.03 *)
278
279val find_opt : ('a -> bool) -> 'a array -> 'a option
280(** [find_opt f a] returns the first element of the array [a] that satisfies
281 the predicate [f], or [None] if there is no value that satisfies [f] in the
282 array [a].
283
284 @since 4.13 *)
285
286val find_index : ('a -> bool) -> 'a array -> int option
287(** [find_index f a] returns [Some i], where [i] is the index of the first
288 element of the array [a] that satisfies [f x], if there is such an
289 element.
290
291 It returns [None] if there is no such element.
292
293 @since 5.1 *)
294
295val find_map : ('a -> 'b option) -> 'a array -> 'b option
296(** [find_map f a] applies [f] to the elements of [a] in order, and returns the
297 first result of the form [Some v], or [None] if none exist.
298
299 @since 4.13 *)
300
301val find_mapi : (int -> 'a -> 'b option) -> 'a array -> 'b option
302(** Same as [find_map], but the predicate is applied to the index of
303 the element as first argument (counting from 0), and the element
304 itself as second argument.
305
306 @since 5.1 *)
307
308(** {1 Arrays of pairs} *)
309
310val split : ('a * 'b) array -> 'a array * 'b array
311(** [split [|(a1,b1); ...; (an,bn)|]] is [([|a1; ...; an|], [|b1; ...; bn|])].
312
313 @since 4.13 *)
314
315val combine : 'a array -> 'b array -> ('a * 'b) array
316(** [combine [|a1; ...; an|] [|b1; ...; bn|]] is [[|(a1,b1); ...; (an,bn)|]].
317 Raise [Invalid_argument] if the two arrays have different lengths.
318
319 @since 4.13 *)
320
321(** {1:sorting_and_shuffling Sorting and shuffling} *)
322
323val sort : ('a -> 'a -> int) -> 'a array -> unit
324(** Sort an array in increasing order according to a comparison
325 function. The comparison function must return 0 if its arguments
326 compare as equal, a positive integer if the first is greater,
327 and a negative integer if the first is smaller (see below for a
328 complete specification). For example, {!Stdlib.compare} is
329 a suitable comparison function. After calling [sort], the
330 array is sorted in place in increasing order.
331 [sort] is guaranteed to run in constant heap space
332 and (at most) logarithmic stack space.
333
334 The current implementation uses Heap Sort. It runs in constant
335 stack space.
336
337 Specification of the comparison function:
338 Let [a] be the array and [cmp] the comparison function. The following
339 must be true for all [x], [y], [z] in [a] :
340- [cmp x y] > 0 if and only if [cmp y x] < 0
341- if [cmp x y] >= 0 and [cmp y z] >= 0 then [cmp x z] >= 0
342
343 When [sort] returns, [a] contains the same elements as before,
344 reordered in such a way that for all i and j valid indices of [a] :
345- [cmp a.(i) a.(j)] >= 0 if i >= j
346*)
347
348val stable_sort : ('a -> 'a -> int) -> 'a array -> unit
349(** Same as {!sort}, but the sorting algorithm is stable (i.e.
350 elements that compare equal are kept in their original order) and
351 not guaranteed to run in constant heap space.
352
353 The current implementation uses Merge Sort. It uses a temporary array of
354 length [n/2], where [n] is the length of the array. It is usually faster
355 than the current implementation of {!sort}.
356*)
357
358val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
359(** Same as {!sort} or {!stable_sort}, whichever is
360 faster on typical input. *)
361
362val shuffle :
363 rand: (* thwart tools/sync_stdlib_docs *) (int -> int) -> 'a array -> unit
364(** [shuffle rand a] randomly permutes [a]'s element using [rand] for
365 randomness. The distribution of permutations is uniform.
366
367 [rand] must be such that a call to [rand n] returns a uniformly
368 distributed random number in the range \[[0];[n-1]\].
369 {!Random.int} can be used for this (do not forget to
370 {{!Random.self_init}initialize} the generator).
371
372 @since 5.2 *)
373
374(** {1 Arrays and Sequences} *)
375
376val to_seq : 'a array -> 'a Seq.t
377(** Iterate on the array, in increasing order. Modifications of the
378 array during iteration will be reflected in the sequence.
379 @since 4.07 *)
380
381val to_seqi : 'a array -> (int * 'a) Seq.t
382(** Iterate on the array, in increasing order, yielding indices along elements.
383 Modifications of the array during iteration will be reflected in the
384 sequence.
385 @since 4.07 *)
386
387val of_seq : 'a Seq.t -> 'a array
388(** Create an array from the generator
389 @since 4.07 *)
390
391(** {1:array_concurrency Arrays and concurrency safety}
392
393 Care must be taken when concurrently accessing arrays from multiple
394 domains: accessing an array will never crash a program, but unsynchronized
395 accesses might yield surprising (non-sequentially-consistent) results.
396
397 {2:array_atomicity Atomicity}
398
399 Every array operation that accesses more than one array element is not
400 atomic. This includes iteration, scanning, sorting, splitting and
401 combining arrays.
402
403 For example, consider the following program:
404{[let size = 100_000_000
405let a = Array.make size 1
406let d1 = Domain.spawn (fun () ->
407 Array.iteri (fun i x -> a.(i) <- x + 1) a
408)
409let d2 = Domain.spawn (fun () ->
410 Array.iteri (fun i x -> a.(i) <- 2 * x + 1) a
411)
412let () = Domain.join d1; Domain.join d2
413]}
414
415 After executing this code, each field of the array [a] is either [2], [3],
416 [4] or [5]. If atomicity is required, then the user must implement their own
417 synchronization (for example, using {!Mutex.t}).
418
419 {2:array_data_race Data races}
420
421 If two domains only access disjoint parts of the array, then the
422 observed behaviour is the equivalent to some sequential interleaving of the
423 operations from the two domains.
424
425 A data race is said to occur when two domains access the same array element
426 without synchronization and at least one of the accesses is a write.
427 In the absence of data races, the observed behaviour is equivalent to some
428 sequential interleaving of the operations from different domains.
429
430 Whenever possible, data races should be avoided by using synchronization to
431 mediate the accesses to the array elements.
432
433 Indeed, in the presence of data races, programs will not crash but the
434 observed behaviour may not be equivalent to any sequential interleaving of
435 operations from different domains. Nevertheless, even in the presence of
436 data races, a read operation will return the value of some prior write to
437 that location (with a few exceptions for float arrays).
438
439 {2:array_data_race_exceptions Float arrays}
440
441 Float arrays have two supplementary caveats in the presence of data races.
442
443 First, the blit operation might copy an array byte-by-byte. Data races
444 between such a blit operation and another operation might produce surprising
445 values due to tearing: partial writes interleaved with other operations can
446 create float values that would not exist with a sequential execution.
447
448 For instance, at the end of
449 {[let zeros = Array.make size 0.
450let max_floats = Array.make size Float.max_float
451let res = Array.copy zeros
452let d1 = Domain.spawn (fun () -> Array.blit zeros 0 res 0 size)
453let d2 = Domain.spawn (fun () -> Array.blit max_floats 0 res 0 size)
454let () = Domain.join d1; Domain.join d2
455]}
456 the [res] array might contain values that are neither [0.] nor [max_float].
457
458 Second, on 32-bit architectures, getting or setting a field involves two
459 separate memory accesses. In the presence of data races, the user may
460 observe tearing on any operation.
461*)
462
463(**/**)
464
465(** {1 Undocumented functions} *)
466
467(* The following is for system use only. Do not call directly. *)
468
469external unsafe_get : 'a array -> int -> 'a = "%array_unsafe_get"
470external unsafe_set : 'a array -> int -> 'a -> unit = "%array_unsafe_set"
471
472module Floatarray : sig
473 external create : int -> floatarray = "caml_floatarray_create"
474 external length : floatarray -> int = "%floatarray_length"
475 external get : floatarray -> int -> float = "%floatarray_safe_get"
476 external set : floatarray -> int -> float -> unit = "%floatarray_safe_set"
477 external unsafe_get : floatarray -> int -> float = "%floatarray_unsafe_get"
478 external unsafe_set : floatarray -> int -> float -> unit
479 = "%floatarray_unsafe_set"
480end