module Array: BatArray
type'a
t ='a array
The type of arrays.
include BatEnum.Enumerable
include BatInterfaces.Mappable
val length : 'a array -> int
Return the length (number of elements) of the given array.
val get : 'a array -> int -> 'a
Array.get a n
returns the element number n
of array a
.
The first element has number 0.
The last element has number Array.length a - 1
.
You can also write a.(n)
instead of Array.get a n
.
Invalid_argument
if n
is outside the range 0 to (Array.length a - 1)
.val set : 'a array -> int -> 'a -> unit
Array.set a n x
modifies array a
in place, replacing
element number n
with x
.
You can also write a.(n) <- x
instead of Array.set a n x
.
Invalid_argument
if n
is outside the range 0 to Array.length a - 1
.val make : int -> 'a -> 'a array
Array.make n x
returns a fresh array of length n
,
initialized with x
.
All the elements of this new array are initially
physically equal to x
(in the sense of the ==
predicate).
Consequently, if x
is mutable, it is shared among all elements
of the array, and modifying x
through one of the array entries
will modify all other entries at the same time.
Invalid_argument
if n < 0
or n > Sys.max_array_length
.
If the value of x
is a floating-point number, then the maximum
size is only Sys.max_array_length / 2
.val create_float : int -> float array
val make_float : int -> float array
Array.make_float n
returns a fresh float array of length n
,
with uninitialized data.
val of_seq : 'a Stdlib.Seq.t -> 'a array
val to_seq : 'a array -> 'a Stdlib.Seq.t
val to_seqi : 'a array -> (int * 'a) Stdlib.Seq.t
val create : int -> 'a -> 'a array
Array.create
is an alias for Array.make
.val init : int -> (int -> 'a) -> 'a array
Array.init n f
returns a fresh array of length n
,
with element number i
initialized to the result of f i
.
In other terms, Array.init n f
tabulates the results of f
applied to the integers 0
to n-1
.
Invalid_argument
if n < 0
or n > Sys.max_array_length
.
If the return type of f
is float
, then the maximum
size is only Sys.max_array_length / 2
.val make_matrix : int -> int -> 'a -> 'a array array
Array.make_matrix dimx dimy e
returns a two-dimensional array
(an array of arrays) with first dimension dimx
and
second dimension dimy
. All the elements of this new matrix
are initially physically equal to e
.
The element (x,y
) of a matrix m
is accessed
with the notation m.(x).(y)
.
Invalid_argument
if dimx
or dimy
is negative or
greater than Sys.max_array_length
.
If the value of e
is a floating-point number, then the maximum
size is only Sys.max_array_length / 2
.val create_matrix : int -> int -> 'a -> 'a array array
Array.create_matrix
is an alias for Array.make_matrix
.val append : 'a array -> 'a array -> 'a array
Array.append v1 v2
returns a fresh array containing the
concatenation of the arrays v1
and v2
.
val concat : 'a array list -> 'a array
Same as Array.append
, but concatenates a list of arrays.
val sub : 'a array -> int -> int -> 'a array
Array.sub a start len
returns a fresh array of length len
,
containing the elements number start
to start + len - 1
of array a
.
Invalid_argument
if start
and len
do not
designate a valid subarray of a
; that is, if
start < 0
, or len < 0
, or start + len > Array.length a
.val copy : 'a array -> 'a array
Array.copy a
returns a copy of a
, that is, a fresh array
containing the same elements as a
.
val fill : 'a array -> int -> int -> 'a -> unit
Array.fill a ofs len x
modifies the array a
in place,
storing x
in elements number ofs
to ofs + len - 1
.
Invalid_argument
if ofs
and len
do not
designate a valid subarray of a
.val blit : 'a array -> int -> 'a array -> int -> int -> unit
Array.blit v1 o1 v2 o2 len
copies len
elements
from array v1
, starting at element number o1
, to array v2
,
starting at element number o2
. It works correctly even if
v1
and v2
are the same array, and the source and
destination chunks overlap.
Invalid_argument
if o1
and len
do not
designate a valid subarray of v1
, or if o2
and len
do not
designate a valid subarray of v2
.val to_list : 'a array -> 'a list
Array.to_list a
returns the list of all the elements of a
.
val split : ('a * 'b) array -> 'a array * 'b array
Array.split a
converts the array of pairs a
into a pair of arrays.
val of_list : 'a list -> 'a array
Array.of_list l
returns a fresh array containing the elements
of l
.
val max : 'a array -> 'a
max a
returns the largest value in a
as judged by
Pervasives.compare
Invalid_argument
on empty inputval min : 'a array -> 'a
min a
returns the smallest value in a
as judged by
Pervasives.compare
Invalid_argument
on empty inputval min_max : 'a array -> 'a * 'a
min_max a
returns the (smallest, largest) pair of values from a
as judged by Pervasives.compare
Invalid_argument
on empty inputval sum : int array -> int
sum l
returns the sum of the integers of l
val fsum : float array -> float
fsum l
returns the sum of the floats of l
val kahan_sum : float array -> float
kahan_sum l
returns a numerically-accurate
sum of the floats of l
.
You should consider using Kahan summation when you really care about very small differences in the result, while the result or one of the intermediate sums can be very large (which usually results in loss of precision of floating-point addition).
The worst-case rounding error is constant, instead of growing with
(the square root of) the length of the input array as with BatArray.fsum
. On the other hand, processing each element requires four
floating-point operations instead of one. See
the wikipedia article on Kahan summation for more details.
val avg : int array -> float
avg l
returns the average of l
val favg : float array -> float
favg l
returns the average of l
val left : 'a array -> int -> 'a array
left r len
returns the array containing the len
first
characters of r
. If r
contains less than len
characters, it
returns r
.
Examples:
Array.left [|0;1;2;3;4;5;6|] 4 = [|0;1;2;3|]
Array.left [|1;2;3|] 0 = [||]
Array.left [|1;2;3|] 10 = [|1;2;3|]
val right : 'a array -> int -> 'a array
left r len
returns the array containing the len
last characters of r
.
If r
contains less than len
characters, it returns r
.
Example: Array.right [|1;2;3;4;5;6|] 4 = [|3;4;5;6|]
val head : 'a array -> int -> 'a array
val tail : 'a array -> int -> 'a array
tail r pos
returns the array containing all but the pos
first characters of r
Example: Array.tail [|1;2;3;4;5;6|] 4 = [|5;6|]
val iter : ('a -> unit) -> 'a array -> unit
Array.iter f a
applies function f
in turn to all
the elements of a
. It is equivalent to
f a.(0); f a.(1); ...; f a.(Array.length a - 1); ()
.
val map : ('a -> 'b) -> 'a array -> 'b array
Array.map f a
applies function f
to all the elements of a
,
and builds an array with the results returned by f
:
[| f a.(0); f a.(1); ...; f a.(Array.length a - 1) |]
.
val iteri : (int -> 'a -> unit) -> 'a array -> unit
Same as Array.iter
, but the
function is applied to the index of the element as first argument,
and the element itself as second argument.
val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
Same as Array.map
, but the
function is applied to the index of the element as first argument,
and the element itself as second argument.
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
Array.fold_left f x a
computes
f (... (f (f x a.(0)) a.(1)) ...) a.(n-1)
,
where n
is the length of the array a
.
val fold_while : ('acc -> 'a -> bool) ->
('acc -> 'a -> 'acc) -> 'acc -> 'a array -> 'acc * int
fold_while p f init a
, accumulates elements x
of array a
using
function f
, as long as the predicate p acc x
holds.
At the end, the accumulated value along with the first index i
where p acc a.(i)
does not hold is returned.
If the returned index is equal to length a
, the whole array
was folded.
val fold : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
Alias for fold_left
.
val fold_right : ('b -> 'a -> 'a) -> 'b array -> 'a -> 'a
Array.fold_right f a x
computes
f a.(0) (f a.(1) ( ... (f a.(n-1) x) ...))
,
where n
is the length of the array a
.
val modify : ('a -> 'a) -> 'a array -> unit
modify f a
replaces every element x
of a
with f x
.
val modifyi : (int -> 'a -> 'a) -> 'a array -> unit
Same as BatArray.modify
, but the function is applied to the index of
the element as the first argument, and the element itself as
the second argument.
val fold_lefti : ('a -> int -> 'b -> 'a) -> 'a -> 'b array -> 'a
As fold_left
, but with the index of the element as additional argument
val fold_righti : (int -> 'b -> 'a -> 'a) -> 'b array -> 'a -> 'a
As fold_right
, but with the index of the element as additional argument
val reduce : ('a -> 'a -> 'a) -> 'a array -> 'a
Array.reduce f a
is fold_left f a.(0) [|a.(1); ..; a.(n-1)|]
. This
is useful for merging a group of things that have no
reasonable default value to return if the group is empty.
Invalid_argument
on empty arrays.val singleton : 'a -> 'a array
Create an array consisting of exactly one element.
val sort : ('a -> 'a -> int) -> 'a array -> unit
Sort an array in increasing order according to a comparison
function. The comparison function must return 0 if its arguments
compare as equal, a positive integer if the first is greater,
and a negative integer if the first is smaller (see below for a
complete specification). For example, Pervasives.compare
is
a suitable comparison function, provided there are no floating-point
NaN values in the data. After calling Array.sort
, the
array is sorted in place in increasing order.
Array.sort
is guaranteed to run in constant heap space
and (at most) logarithmic stack space.
The current implementation uses Heap Sort. It runs in constant stack space.
Specification of the comparison function:
Let a
be the array and cmp
the comparison function. The following
must be true for all x, y, z in a :
cmp x y
> 0 if and only if cmp y x
< 0cmp x y
>= 0 and cmp y z
>= 0 then cmp x z
>= 0When Array.sort
returns, a
contains the same elements as before,
reordered in such a way that for all i and j valid indices of a
:
cmp a.(i) a.(j)
>= 0 if and only if i >= jval stable_sort : ('a -> 'a -> int) -> 'a array -> unit
Same as Array.sort
, but the sorting algorithm is stable (i.e.
elements that compare equal are kept in their original order) and
not guaranteed to run in constant heap space.
The current implementation uses Merge Sort. It uses n/2
words of heap space, where n
is the length of the array.
It is usually faster than the current implementation of Array.sort
.
val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
Same as Array.sort
or Array.stable_sort
, whichever is faster
on typical input.
val decorate_stable_sort : ('a -> 'b) -> 'a array -> 'a array
decorate_stable_sort f a
returns a sorted copy of a
such that if f
then
x < f yx
is earlier in the result than y
. This
function is useful when f
is expensive, as it only computes f
once for each element in the array. See
Schwartzian
Transform.
x
It is unnecessary to have an additional comparison function as
argument, as the builtin Pervasives.compare
is used to compare
the 'b
values. This is deemed sufficient.
val decorate_fast_sort : ('a -> 'b) -> 'a array -> 'a array
As Array.decorate_stable_sort
, but uses fast_sort internally.
val bsearch : 'a BatOrd.ord ->
'a array ->
'a -> [ `All_bigger | `All_lower | `At of int | `Empty | `Just_after of int ]
bsearch cmp arr x
finds the index of the object x
in the array arr
,
provided arr
is sorted using cmp
. If the array is not sorted,
the result is not specified (may raise Invalid_argument).
Complexity: O(log n) where n is the length of the array (dichotomic search).
Invalid_argument
if the array is found to be unsorted w.r.t cmp
`At i
if cmp arr.(i) x = 0
(for some i)`All_lower
if all elements of arr
are lower than x
`All_bigger
if all elements of arr
are bigger than x
`Just_after i
if arr.(i) < x < arr.(i+1)
`Empty
if the array is emptyval pivot_split : 'a BatOrd.ord -> 'a array -> 'a -> int * int
pivot_split cmp arr x
assumes that arr
is sorted w.r.t
cmp
. It splits an array arr
of length len
into three parts,
by returning a couple (i,j) such as:
sub arr 0 i
) are lower than x
sub arr i (j-i)
) are equal to x
sub arr j (len-j)
) are bigger than x
In particular, it returns:
arr
are bigger than x
x
x
Complexity: logarithmic in the size of the array
Invalid_argument
if the array is found not to be sortedval iter2 : ('a -> 'b -> unit) -> 'a array -> 'b array -> unit
Array.iter2 f [|a0; a1; ...; an|] [|b0; b1; ...; bn|]
performs calls f a0 b0; f a1 b1; ...; f an bn
in that order.
Invalid_argument
if the two arrays have different lengths.val iter2i : (int -> 'a -> 'b -> unit) -> 'a array -> 'b array -> unit
Array.iter2i f [|a0; a1; ...; an|] [|b0; b1; ...; bn|]
performs calls f 0 a0 b0; f 1 a1 b1; ...; f n an bn
in that
order.
Invalid_argument
if the two arrays have different
lengths.val for_all2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
As Array.for_all
but on two arrays.
Invalid_argument
if the two arrays have different lengths.val exists2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
As Array.exists
but on two arrays.
Invalid_argument
if the two arrays have different lengths.val map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
As Array.map
but on two arrays.
Invalid_argument
if the two arrays have different lengths.val cartesian_product : 'a array -> 'b array -> ('a * 'b) array
Cartesian product of the two arrays.
val for_all : ('a -> bool) -> 'a array -> bool
for_all p [|a0; a1; ...; an|]
checks if all elements of the
array satisfy the predicate p
. That is, it returns (p a0)
.
&& (p a1) && ... && (p an)
val exists : ('a -> bool) -> 'a array -> bool
exists p [|a0; a1; ...; an|]
checks if at least one element of
the array satisfies the predicate p
. That is, it returns (p
.
a0) || (p a1) || ... || (p an)
val find : ('a -> bool) -> 'a array -> 'a
find p a
returns the first element of array a
that
satisfies the predicate p
.
Not_found
if there is no value that satisfies p
in
the array a
.val mem : 'a -> 'a array -> bool
mem m a
is true if and only if m
is equal to an element of a
.
val memq : 'a -> 'a array -> bool
Same as Array.mem
but uses physical equality instead of
structural equality to compare array elements.
val findi : ('a -> bool) -> 'a array -> int
findi p a
returns the index of the first element of array a
that satisfies the predicate p
.
Not_found
if there is no value that satisfies p
in the
array a
.val filter : ('a -> bool) -> 'a array -> 'a array
filter p a
returns all the elements of the array a
that satisfy the predicate p
. The order of the elements
in the input array is preserved.
val filteri : (int -> 'a -> bool) -> 'a array -> 'a array
As filter
but with the index passed to the predicate.
val filter_map : ('a -> 'b option) -> 'a array -> 'b array
filter_map f e
returns an array consisting of all elements
x
such that f y
returns Some x
, where y
is an element
of e
.
val count_matching : ('a -> bool) -> 'a array -> int
count_matching p a
returns the number of elements of a
satisfying predicate p
.
val find_all : ('a -> bool) -> 'a array -> 'a array
find_all
is another name for Array.filter
.
val partition : ('a -> bool) -> 'a array -> 'a array * 'a array
partition p a
returns a pair of arrays (a1, a2)
, where
a1
is the array of all the elements of a
that
satisfy the predicate p
, and a2
is the array of all the
elements of a
that do not satisfy p
.
The order of the elements in the input array is preserved.
val rev : 'a array -> 'a array
Array reversal.
val rev_in_place : 'a array -> unit
In-place array reversal. The array argument is updated.
val enum : 'a array -> 'a BatEnum.t
Returns an enumeration of the elements of an array. Behavior of the enumeration is undefined if the contents of the array changes afterwards.
val of_enum : 'a BatEnum.t -> 'a array
Build an array from an enumeration.
val backwards : 'a array -> 'a BatEnum.t
Returns an enumeration of the elements of an array, from last to first.
val of_backwards : 'a BatEnum.t -> 'a array
Build an array from an enumeration, with the first element of the enumeration as the last element of the array and vice versa.
val range : 'a array -> int BatEnum.t
range a
returns an enumeration of all valid indexes into the given
array. For example, range [|2;4;6;8|] = 0--3
.
val insert : 'a array -> 'a -> int -> 'a array
insert xs x i
returns a copy of xs
except the value x
is
inserted in position i
(and all later indices are shifted to the
right).
Invalid_argument
if i < 0 || i > Array.length xs
.val remove_at : int -> 'a array -> 'a array
remove_at i a
returns the array a
without the element at index i
.
Invalid_argument
if i
is outside of a
bounds.val print : ?first:string ->
?last:string ->
?sep:string -> ('a, 'b) BatIO.printer -> ('a t, 'b) BatIO.printer
Print the contents of an array, with ~first
preceding the first
item (default: "[|"), ~last
following the last item (default:
"|]") and ~sep
separating items (default: "; "). A printing
function must be provided to print the items in the array.
Example: IO.to_string (Array.print Int.print) |2;4;66|
= "|2; 4; 66|
"
val compare : 'a BatOrd.comp -> 'a array BatOrd.comp
compare c
generates the lexicographical order on arrays induced
by c
. That is, given a comparison function for the elements of
an array, this will return a comparison function for arrays of
that type.
val ord : 'a BatOrd.ord -> 'a array BatOrd.ord
Hoist an element comparison function to compare arrays of those
elements, with shorter arrays less than longer ones, and
lexicographically for arrays of the same size. This is a
different ordering than compare
, but is often faster.
val shuffle : ?state:Stdlib.Random.State.t -> 'a array -> unit
shuffle ~state:rs a
randomly shuffles in place the elements of a
.
The optional random state rs
allows to control the random
numbers being used during shuffling (for reproducibility).
Shuffling is implemented using the Fisher-Yates
algorithm and works in O(n), where n is the number
of elements of a
.
val equal : 'a BatOrd.eq -> 'a array BatOrd.eq
Hoist a equality test for elements to arrays. Arrays are only equal if their lengths are the same and corresponding elements test equal.
The following modules replace functions defined in Array
with
functions behaving slightly differently but having the same
name. This is by design: the functions are meant to override the
corresponding functions of Array
.
module Exceptionless:sig
..end
Operations on Array
without exceptions.
module Labels:sig
..end
Operations on Array
with labels.
module Cap:sig
..end
Capabilities for arrays.
module Incubator:sig
..end