Module CCArray
Array utils
type 'a sequence
= ('a -> unit) -> unit
type 'a klist
= unit -> [ `Nil | `Cons of 'a * 'a klist ]
type 'a gen
= unit -> 'a option
type 'a equal
= 'a -> 'a -> bool
type 'a ord
= 'a -> 'a -> int
type 'a random_gen
= Stdlib.Random.State.t -> 'a
type 'a printer
= Stdlib.Format.formatter -> 'a -> unit
Arrays
include module type of CCShimsArray_
include Stdlib.Array
val length : 'a array -> int
val get : 'a array -> int -> 'a
val set : 'a array -> int -> 'a -> unit
val make : int -> 'a -> 'a array
val create : int -> 'a -> 'a array
val create_float : int -> float array
val make_float : int -> float array
val init : int -> (int -> 'a) -> 'a array
val make_matrix : int -> int -> 'a -> 'a array array
val create_matrix : int -> int -> 'a -> 'a array array
val append : 'a array -> 'a array -> 'a array
val concat : 'a array list -> 'a array
val sub : 'a array -> int -> int -> 'a array
val copy : 'a array -> 'a array
val fill : 'a array -> int -> int -> 'a -> unit
val blit : 'a array -> int -> 'a array -> int -> int -> unit
val to_list : 'a array -> 'a list
val of_list : 'a list -> 'a array
val iter : ('a -> unit) -> 'a array -> unit
val iteri : (int -> 'a -> unit) -> 'a array -> unit
val map : ('a -> 'b) -> 'a array -> 'b array
val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
val fold_right : ('b -> 'a -> 'a) -> 'b array -> 'a -> 'a
val iter2 : ('a -> 'b -> unit) -> 'a array -> 'b array -> unit
val map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
val for_all : ('a -> bool) -> 'a array -> bool
val exists : ('a -> bool) -> 'a array -> bool
val mem : 'a -> 'a array -> bool
val memq : 'a -> 'a array -> bool
val sort : ('a -> 'a -> int) -> 'a array -> unit
val stable_sort : ('a -> 'a -> int) -> 'a array -> unit
val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
val to_seq : 'a array -> 'a Stdlib.Seq.t
val to_seqi : 'a array -> (int * 'a) Stdlib.Seq.t
val of_seq : 'a Stdlib.Seq.t -> 'a array
val empty : 'a t
empty
is the empty array, physically equal to||
.
val equal : 'a equal -> 'a t equal
equal eq a1 a2
istrue
if the lengths ofa1
anda2
are the same and if their corresponding elements test equal, usingeq
.
val compare : 'a ord -> 'a t ord
compare cmp a1 a2
compares arraysa1
anda2
using the function comparisoncmp
.
val swap : 'a t -> int -> int -> unit
swap a i j
swaps elements at indicesi
andj
.- since
- 1.4
val get : 'a t -> int -> 'a
get a n
returns the element numbern
of arraya
. The first element has number 0. The last element has numberlength a - 1
. You can also writea.(n)
instead ofget a n
.Raise
Invalid_argument "index out of bounds"
ifn
is outside the range 0 to(length a - 1)
.
val get_safe : 'a t -> int -> 'a option
get_safe a i
returnsSome a.(i)
ifi
is a valid index.- since
- 0.18
val set : 'a t -> int -> 'a -> unit
set a n x
modifies arraya
in place, replacing element numbern
withx
. You can also writea.(n) <- x
instead ofset a n x
.Raise
Invalid_argument "index out of bounds"
ifn
is outside the range 0 tolength a - 1
.
val length : _ t -> int
length a
returns the length (number of elements) of the given arraya
.
val fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
fold f init a
computesf (... (f (f init a.(0)) a.(1)) ...) a.(n-1)
, wheren
is the length of the arraya
.
val foldi : ('a -> int -> 'b -> 'a) -> 'a -> 'b t -> 'a
foldi f init a
is just likefold
, but it also passes in the index of each element as the second argument to the folded functionf
.
val fold_while : ('a -> 'b -> 'a * [ `Stop | `Continue ]) -> 'a -> 'b t -> 'a
fold_while f init a
folds left on arraya
until a stop condition via('a, `Stop)
is indicated by the accumulator.- since
- 0.8
val fold_map : ('acc -> 'a -> 'acc * 'b) -> 'acc -> 'a t -> 'acc * 'b t
fold_map f init a
is afold_left
-like function, but it also maps the array to another array.- since
- 1.2, but only
- since
- 2.1 with labels
val scan_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc t
scan_left f init a
returns the array[|init; f init x0; f (f init a.(0)) a.(1); …|]
.- since
- 1.2, but only
- since
- 2.1 with labels
val iter : ('a -> unit) -> 'a t -> unit
iter f a
applies functionf
in turn to all elements ofa
. It is equivalent tof a.(0); f a.(1); ...; f a.(length a - 1); ()
.
val iteri : (int -> 'a -> unit) -> 'a t -> unit
iteri f a
is likeiter
, but the functionf
is applied with the index of the element as first argument, and the element itself as second argument.
val blit : 'a t -> int -> 'a t -> int -> int -> unit
blit a1 o1 a2 o2 len
copieslen
elements from arraya1
, starting at element numbero1
, to arraya2
, starting at element numbero2
. It works correctly even ifa1
anda2
are the same array, and the source and destination chunks overlap.Raise
Invalid_argument "CCArray.blit"
ifo1
andlen
do not designate a valid subarray ofa1
, or ifo2
andlen
do not designate a valid subarray ofa2
.
val reverse_in_place : 'a t -> unit
reverse_in_place a
reverses the arraya
in place.
val sorted : ('a -> 'a -> int) -> 'a t -> 'a array
sorted f a
makes a copy ofa
and sorts it withf
.- since
- 1.0
val sort_indices : ('a -> 'a -> int) -> 'a t -> int array
sort_indices f a
returns a new arrayb
, with the same length asa
, such thatb.(i)
is the index at which thei
-th element ofsorted f a
appears ina
.a
is not modified.In other words,
map (fun i -> a.(i)) (sort_indices f a) = sorted f a
.sort_indices
yields the inverse permutation ofsort_ranking
.- since
- 1.0
val sort_ranking : ('a -> 'a -> int) -> 'a t -> int array
sort_ranking f a
returns a new arrayb
, with the same length asa
, such thatb.(i)
is the index at which thei
-th element ofa
appears insorted f a
.a
is not modified.In other words,
map (fun i -> (sorted f a).(i)) (sort_ranking f a) = a
.sort_ranking
yields the inverse permutation ofsort_indices
.In the absence of duplicate elements in
a
, we also havelookup_exn a.(i) (sorted a) = (sorted_ranking a).(i)
.- since
- 1.0
val find_map : ('a -> 'b option) -> 'a t -> 'b option
find_map f a
returnsSome y
if there is an elementx
such thatf x = Some y
. Otherwise returnsNone
.- since
- 1.3, but only
- since
- 2.1 with labels
val find : ('a -> 'b option) -> 'a t -> 'b option
find f a
is an alias tofind_map
.- deprecated
since 1.3, use
find_map
instead. The version with labels is
- deprecated
since 2.1, use
find_map
instead.
val find_map_i : (int -> 'a -> 'b option) -> 'a t -> 'b option
find_map_i f a
is likefind_map
, but the index of the element is also passed to the predicate functionf
.- since
- 1.3, but only
- since
- 2.1 with labels
val findi : (int -> 'a -> 'b option) -> 'a t -> 'b option
findi f a
is an alias tofind_map_i
.- since
- 0.3.4
- deprecated
since 1.3, use
find_map
instead. The version with labels is
- deprecated
since 2.1, use
find_map
instead.
val find_idx : ('a -> bool) -> 'a t -> (int * 'a) option
find_idx f a
returnsSome (i,x)
wherex
is thei
-th element ofa
, andf x
holds. Otherwise returnsNone
.- since
- 0.3.4
val lookup : cmp:'a ord -> 'a -> 'a t -> int option
lookup ~cmp key a
lookups the index of some keykey
in a sorted arraya
. Undefined behavior if the arraya
is not sorted wrt~cmp
. Complexity:O(log (n))
(dichotomic search).- returns
None
if the keykey
is not present, orSome i
(i
the index of the key) otherwise.
val lookup_exn : cmp:'a ord -> 'a -> 'a t -> int
lookup_exn ~cmp key a
is likelookup
, but- raises Not_found
if the key
key
is not present.
val bsearch : cmp:('a -> 'a -> int) -> 'a -> 'a t -> [ `All_lower | `All_bigger | `Just_after of int | `Empty | `At of int ]
bsearch ~cmp key a
finds the index of the objectkey
in the arraya
, provideda
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 arraya
(dichotomic search).- returns
`At i
ifcmp a.(i) key = 0
(for some i).`All_lower
if all elements ofa
are lower thankey
.`All_bigger
if all elements ofa
are bigger thankey
.`Just_after i
ifa.(i) < key < a.(i+1)
.`Empty
if the arraya
is empty.
- raises Invalid_argument
if the array is found to be unsorted w.r.t
cmp
.
- since
- 0.13
val for_all : ('a -> bool) -> 'a t -> bool
for_all f [|a1; ...; an|]
istrue
if all elements of the array satisfy the predicatef
. That is, it returns(f a1) && (f a2) && ... && (f an)
.
val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
for_all2 f [|a1; ...; an|] [|b1; ...; bn|]
istrue
if each pair of elementsai bi
satisfies the predicatef
. That is, it returns(f a1 b1) && (f a2 b2) && ... && (f an bn)
.- raises Invalid_argument
if arrays have distinct lengths. Allow different types.
- since
- 0.20
val exists : ('a -> bool) -> 'a t -> bool
exists f [|a1; ...; an|]
istrue
if at least one element of the array satisfies the predicatef
. That is, it returns(f a1) || (f a2) || ... || (f an)
.
val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
exists2 f [|a1; ...; an|] [|b1; ...; bn|]
istrue
if any pair of elementsai bi
satisfies the predicatef
. That is, it returns(f a1 b1) || (f a2 b2) || ... || (f an bn)
.- raises Invalid_argument
if arrays have distinct lengths. Allow different types.
- since
- 0.20
val fold2 : ('acc -> 'a -> 'b -> 'acc) -> 'acc -> 'a t -> 'b t -> 'acc
fold2 f init a b
fold on two arraysa
andb
stepwise. It computesf (... (f init a1 b1)...) an bn
.- raises Invalid_argument
if
a
andb
have distinct lengths.
- since
- 0.20
val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
iter2 f a b
iterates on the two arraysa
andb
stepwise. It is equivalent tof a0 b0; ...; f a.(length a - 1) b.(length b - 1); ()
.- raises Invalid_argument
if
a
andb
have distinct lengths.
- since
- 0.20
val shuffle : 'a t -> unit
shuffle a
randomly shuffles the arraya
, in place.
val shuffle_with : Stdlib.Random.State.t -> 'a t -> unit
shuffle_with rs a
randomly shuffles the arraya
(likeshuffle
) but a specialized random staters
is used to control the random numbers being produced during shuffling (for reproducibility).
val random_choose : 'a t -> 'a random_gen
random_choose a rs
randomly chooses an element ofa
.- raises Not_found
if the array/slice is empty.
IO
val pp : ?sep:string -> 'a printer -> 'a t printer
pp ~sep pp_item ppf a
formats the arraya
onppf
. Each element is formatted withpp_item
and elements are separated bysep
(defaults to ", ").
val pp_i : ?sep:string -> (int -> 'a printer) -> 'a t printer
pp_i ~sep pp_item ppf a
prints the arraya
onppf
. The printing functionpp_item
is giving both index and element. Elements are separated bysep
(defaults to ", ").
val map : ('a -> 'b) -> 'a t -> 'b t
map f a
applies functionf
to all elements ofa
, and builds an array with the results returned byf
:[| f a.(0); f a.(1); ...; f a.(length a - 1) |]
.
val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
map2 f a b
applies functionf
to all elements ofa
andb
, and builds an array with the results returned byf
:[| f a.(0) b.(0); ...; f a.(length a - 1) b.(length b - 1)|]
.- raises Invalid_argument
if
a
andb
have distinct lengths.
- since
- 0.20
val filter : ('a -> bool) -> 'a t -> 'a t
filter f a
filters elements out of the arraya
. Only the elements satisfying the given predicatef
will be kept.
val filter_map : ('a -> 'b option) -> 'a t -> 'b t
filter_map f [|a1; ...; an|]
calls(f a1) ... (f an)
and returns an arrayb
consisting of all elementsbi
such asf ai = Some bi
. Whenf
returnsNone
, the corresponding element ofa
is discarded.
val flat_map : ('a -> 'b t) -> 'a t -> 'b array
flat_map f a
transforms each element ofa
into an array, then flattens.
val except_idx : 'a t -> int -> 'a list
except_idx a i
removes the element ofa
at given indexi
, and returns the list of the other elements.
val (--) : int -> int -> int t
x -- y
creates an array containing integers in the rangex .. y
. Bounds included.
val (--^) : int -> int -> int t
x --^ y
creates an array containing integers in the rangex .. y
. Right bound excluded.- since
- 0.17
val random : 'a random_gen -> 'a t random_gen
val random_non_empty : 'a random_gen -> 'a t random_gen
val random_len : int -> 'a random_gen -> 'a t random_gen
Generic Functions
module type MONO_ARRAY = sig ... end
val sort_generic : (module MONO_ARRAY with type elt = 'elt and type t = 'arr) -> cmp:('elt -> 'elt -> int) -> 'arr -> unit
sort_generic (module M) ~cmp a
sorts the arraya
, without allocating (eats stack space though). Performance might be lower thanArray
.sort.- since
- 0.14