Previous  Up  Next

Module Hash_queue.Array

module Array: Core_array
type 'a t = 'a array 
val typerep_of_t : 'a Typerep_lib.Std.Typerep.t -> 'a t Typerep_lib.Std.Typerep.t
val typename_of_t : 'a Typerep_lib.Std.Typename.t -> 'a t Typerep_lib.Std.Typename.t
include Binary_searchable.S1
include Container.S1
Note: Array.length is not constant for a given array, as one can reduce it with Array.truncate
val max_length : int
Maximum length of a normal array. The maximum length of a float array is max_length/2 on 32-bit machines and max_length on 64-bit machines.
val get : 'a t -> 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.

Raise Invalid_argument "index out of bounds" if n is outside the range 0 to (Array.length a - 1).

val set : 'a t -> 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.

Raise Invalid_argument "index out of bounds" if n is outside the range 0 to Array.length a - 1.

val unsafe_get : 'a t -> int -> 'a
Unsafe version of get. Can cause arbitrary behavior when used for an out-of-bounds array access
val unsafe_set : 'a t -> int -> 'a -> unit
Unsafe version of set. Can cause arbitrary behavior when used for an out-of-bounds array access
val create : len:int -> 'a -> 'a t
create ~len x creates an array of length len with the value x populated in each element
val init : int -> f:(int -> 'a) -> 'a t
init n ~f creates an array of length n where the ith element is initialized with f i (starting at zero)
val make_matrix : dimx:int -> dimy:int -> 'a -> 'a t t
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).

Raise 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 append : 'a t -> 'a t -> 'a t
Array.append v1 v2 returns a fresh array containing the concatenation of the arrays v1 and v2.
val concat : 'a t list -> 'a t
Same as Array.append, but concatenates a list of arrays.
val copy : 'a t -> 'a t
Array.copy a returns a copy of a, that is, a fresh array containing the same elements as a.
val fill : 'a t -> pos:int -> len: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.

Raise Invalid_argument "Array.fill" if ofs and len do not designate a valid subarray of a.

include Blit.S1
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.

Raise Invalid_argument "Array.blit" 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.

int_blit and float_blit provide fast bound-checked blits for immediate data types. The unsafe versions do not bound-check the arguments.

module Int: sig .. end
module Float: sig .. end
val of_list : 'a list -> 'a t
Array.of_list l returns a fresh array containing the elements of l.
val map : f:('a -> 'b) -> 'a t -> 'b t
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 : f:(int -> 'a -> unit) -> 'a t -> 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 : f:(int -> 'a -> 'b) -> 'a t -> 'b t
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 foldi : 'a t -> init:'b -> f:(int -> 'b -> 'a -> 'b) -> 'b
val fold_right : 'a t -> f:('a -> 'b -> 'b) -> init:'b -> 'b
Array.fold_right f a ~init computes f a.(0) (f a.(1) ( ... (f a.(n-1) init) ...)), where n is the length of the array a.

All sort functions in this module sort in increasing order by default.
val sort : ?pos:int -> ?len:int -> 'a t -> cmp:('a -> 'a -> int) -> unit
sort uses constant heap space. stable_sort uses linear heap space.

To sort only part of the array, specify pos to be the index to start sorting from and len indicating how many elements to sort.

val stable_sort : 'a t -> cmp:('a -> 'a -> int) -> unit
val is_sorted : 'a t -> cmp:('a -> 'a -> int) -> bool
val is_sorted_strictly : 'a t -> cmp:('a -> 'a -> int) -> bool
is_sorted_strictly xs ~cmp iff is_sorted xs ~cmp and no two consecutive elements in xs are equal according to cmp
val concat_map : 'a t -> f:('a -> 'b array) -> 'b array
same as List.concat_map
val partition_tf : 'a t -> f:('a -> bool) -> 'a t * 'a t
val partitioni_tf : 'a t -> f:(int -> 'a -> bool) -> 'a t * 'a t
val cartesian_product : 'a t -> 'b t -> ('a * 'b) t
val normalize : 'a t -> int -> int
normalize array index returns a new index into the array such that if index is less than zero, the returned index will "wrap around" -- i.e. array.(normalize array (-1)) returns the last element of the array.
val slice : 'a t -> int -> int -> 'a t
slice array start stop returns a fresh array including elements array.(start) through array.(stop-1) with the small tweak that the start and stop positions are normalized and a stop index of 0 means the same thing a stop index of Array.length array. In summary, it's mostly like the slicing in Python or Matlab. One difference is that a stop value of 0 here is like not specifying a stop value in Python.
val nget : 'a t -> int -> 'a
Array access with normalized index.
val nset : 'a t -> int -> 'a -> unit
Array modification with normalized index.
val filter_opt : 'a option t -> 'a t
filter_opt array returns a new array where None entries are omitted and Some x entries are replaced with x. Note that this changes the index at which elements will appear.
val filter_map : 'a t -> f:('a -> 'b option) -> 'b t
filter_map ~f array maps f over array and filters None out of the results.
val filter_mapi : 'a t -> f:(int -> 'a -> 'b option) -> 'b t
Same as filter_map but uses Array.mapi.
val iter2_exn : 'a t -> 'b t -> f:('a -> 'b -> unit) -> unit
Functions with 2 suffix raise an exception if the lengths aren't the same.
val map2_exn : 'a t -> 'b t -> f:('a -> 'b -> 'c) -> 'c t
val fold2_exn : 'a t ->
       'b t -> init:'c -> f:('c -> 'a -> 'b -> 'c) -> 'c
val for_all2_exn : 'a t -> 'b t -> f:('a -> 'b -> bool) -> bool
for_all2_exn t1 t2 ~f fails if length t1 <> length t2.
val filter : f:('a -> bool) -> 'a t -> 'a t
filter ~f array removes the elements for which f returns false.
val filteri : f:(int -> 'a -> bool) -> 'a t -> 'a t
Like filter except f also receives the index.
val swap : 'a t -> int -> int -> unit
swap arr i j swaps the value at index i with that at index j.
val rev_inplace : 'a t -> unit
rev_inplace t reverses t in place
val of_list_rev : 'a list -> 'a t
of_list_rev l converts from list then reverses in place
val of_list_map : 'a list -> f:('a -> 'b) -> 'b t
of_list_map l ~f is the same as of_list (List.map l ~f)
val of_list_rev_map : 'a list -> f:('a -> 'b) -> 'b t
of_list_rev_map l ~f is the same as rev_inplace (of_list_map l ~f)
val replace : 'a t -> int -> f:('a -> 'a) -> unit
replace t i ~f = t.(i) <- f (t.(i)).
val replace_all : 'a t -> f:('a -> 'a) -> unit
modifies an array in place -- ar.(i) will be set to f(ar.(i))
val find_exn : 'a t -> f:('a -> bool) -> 'a
find_exn f t returns the first a in t for which f t.(i) is true. It raises Not_found if there is no such a.
val findi : 'a t -> f:(int -> 'a -> bool) -> (int * 'a) option
findi t f returns the first index i of t for which f i t.(i) is true
val findi_exn : 'a t -> f:(int -> 'a -> bool) -> int * 'a
findi_exn t f returns the first index i of t for which f i t.(i) is true. It raises Not_found if there is no such element.
val find_consecutive_duplicate : 'a t -> equal:('a -> 'a -> bool) -> ('a * 'a) option
find_consecutive_duplicate t ~equal returns the first pair of consecutive elements (a1, a2) in t such that equal a1 a2. They are returned in the same order as they appear in t.
val reduce : 'a t -> f:('a -> 'a -> 'a) -> 'a option
reduce f [a1; ...; an] is Some (f (... (f (f a1 a2) a3) ...) an). Returns None on the empty array.
val reduce_exn : 'a t -> f:('a -> 'a -> 'a) -> 'a
val permute : ?random_state:Core_random.State.t -> 'a t -> unit
permute ?random_state t randomly permutes t in place.

permute side affects random_state by repeated calls to Random.State.int. If random_state is not supplied, permute uses Random.State.default.

val combine : 'a t -> 'b t -> ('a * 'b) t
combine ar combines two arrays to an array of pairs.
val split : ('a * 'b) t -> 'a t * 'b t
split ar splits an array of pairs into two arrays of single elements.
val sorted_copy : 'a t -> cmp:('a -> 'a -> int) -> 'a t
sorted_copy ar cmp returns a shallow copy of ar that is sorted. Similar to List.sort
val last : 'a t -> 'a
val empty : unit -> 'a t
empty () creates an empty array
val equal : 'a t -> 'a t -> equal:('a -> 'a -> bool) -> bool
val truncate : 'a t -> len:int -> unit
truncate t ~len drops length t - len elements from the end of t, changing t so that length t = len afterwards. truncate raises if len <= 0 || len > length t.
module Infix: sig .. end
val to_sequence : 'a t -> 'a Sequence.t
to_sequence t converts t to a sequence. t is copied internally so that future modifications of t do not change the sequence.
val to_sequence_mutable : 'a t -> 'a Sequence.t
to_sequence_mutable t converts t to a sequence. t is shared with the sequence and modifications of t will result in modification of the sequence.
module Permissioned: sig .. end
The Permissioned module gives the ability to restrict permissions on an array, so you can give a function read-only access to an array, create an immutable array, etc. 
val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val bin_t : 'a Bin_prot.Type_class.t -> 'a t Bin_prot.Type_class.t
val bin_read_t : 'a Bin_prot.Read.reader -> 'a t Bin_prot.Read.reader
val __bin_read_t__ : 'a Bin_prot.Read.reader -> (int -> 'a t) Bin_prot.Read.reader
val bin_reader_t : 'a Bin_prot.Type_class.reader -> 'a t Bin_prot.Type_class.reader
val bin_size_t : 'a Bin_prot.Size.sizer -> 'a t Bin_prot.Size.sizer
val bin_write_t : 'a Bin_prot.Write.writer -> 'a t Bin_prot.Write.writer
val bin_writer_t : 'a Bin_prot.Type_class.writer -> 'a t Bin_prot.Type_class.writer

Note: Array.length is not constant for a given array, as one can reduce it with Array.truncate

Maximum length of a normal array. The maximum length of a float array is max_length/2 on 32-bit machines and max_length on 64-bit machines.

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.

Raise Invalid_argument "index out of bounds" if n is outside the range 0 to (Array.length a - 1).

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.

Raise Invalid_argument "index out of bounds" if n is outside the range 0 to Array.length a - 1.

Unsafe version of get. Can cause arbitrary behavior when used for an out-of-bounds array access

Unsafe version of set. Can cause arbitrary behavior when used for an out-of-bounds array access

create ~len x creates an array of length len with the value x populated in each element

init n ~f creates an array of length n where the ith element is initialized with f i (starting at zero)

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).

Raise 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.

Array.append v1 v2 returns a fresh array containing the concatenation of the arrays v1 and v2.

Same as Array.append, but concatenates a list of arrays.

Array.copy a returns a copy of a, that is, a fresh array containing the same elements as a.

Array.fill a ofs len x modifies the array a in place, storing x in elements number ofs to ofs + len - 1.

Raise Invalid_argument "Array.fill" if ofs and len do not designate a valid subarray of a.

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.

Raise Invalid_argument "Array.blit" 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.

int_blit and float_blit provide fast bound-checked blits for immediate data types. The unsafe versions do not bound-check the arguments.

Array.of_list l returns a fresh array containing the elements of l.

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) |].

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.

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.

Array.fold_right f a ~init computes f a.(0) (f a.(1) ( ... (f a.(n-1) init) ...)), where n is the length of the array a.

All sort functions in this module sort in increasing order by default.

sort uses constant heap space. stable_sort uses linear heap space.

To sort only part of the array, specify pos to be the index to start sorting from and len indicating how many elements to sort.

is_sorted_strictly xs ~cmp iff is_sorted xs ~cmp and no two consecutive elements in xs are equal according to cmp

same as List.concat_map

normalize array index returns a new index into the array such that if index is less than zero, the returned index will "wrap around" -- i.e. array.(normalize array (-1)) returns the last element of the array.

slice array start stop returns a fresh array including elements array.(start) through array.(stop-1) with the small tweak that the start and stop positions are normalized and a stop index of 0 means the same thing a stop index of Array.length array. In summary, it's mostly like the slicing in Python or Matlab. One difference is that a stop value of 0 here is like not specifying a stop value in Python.

Array access with normalized index.

Array modification with normalized index.

filter_opt array returns a new array where None entries are omitted and Some x entries are replaced with x. Note that this changes the index at which elements will appear.

filter_map ~f array maps f over array and filters None out of the results.

Same as filter_map but uses Array.mapi.

Functions with 2 suffix raise an exception if the lengths aren't the same.

for_all2_exn t1 t2 ~f fails if length t1 <> length t2.

filter ~f array removes the elements for which f returns false.

Like filter except f also receives the index.

swap arr i j swaps the value at index i with that at index j.

rev_inplace t reverses t in place

of_list_rev l converts from list then reverses in place

of_list_map l ~f is the same as of_list (List.map l ~f)

of_list_rev_map l ~f is the same as rev_inplace (of_list_map l ~f)

replace t i ~f = t.(i) <- f (t.(i)).

modifies an array in place -- ar.(i) will be set to f(ar.(i))

find_exn f t returns the first a in t for which f t.(i) is true. It raises Not_found if there is no such a.

findi t f returns the first index i of t for which f i t.(i) is true

findi_exn t f returns the first index i of t for which f i t.(i) is true. It raises Not_found if there is no such element.

find_consecutive_duplicate t ~equal returns the first pair of consecutive elements (a1, a2) in t such that equal a1 a2. They are returned in the same order as they appear in t.

reduce f [a1; ...; an] is Some (f (... (f (f a1 a2) a3) ...) an). Returns None on the empty array.

permute ?random_state t randomly permutes t in place.

permute side affects random_state by repeated calls to Random.State.int. If random_state is not supplied, permute uses Random.State.default.

combine ar combines two arrays to an array of pairs.

split ar splits an array of pairs into two arrays of single elements.

sorted_copy ar cmp returns a shallow copy of ar that is sorted. Similar to List.sort

empty () creates an empty array

truncate t ~len drops length t - len elements from the end of t, changing t so that length t = len afterwards. truncate raises if len <= 0 || len > length t.

to_sequence t converts t to a sequence. t is copied internally so that future modifications of t do not change the sequence.

to_sequence_mutable t converts t to a sequence. t is shared with the sequence and modifications of t will result in modification of the sequence.

The Permissioned module gives the ability to restrict permissions on an array, so you can give a function read-only access to an array, create an immutable array, etc.

The meaning of the 'perms parameter is as usual (see the Perms module for more details) with the non-obvious difference that you don't need any permissions to extract the length of an array. This was done for simplicity because some information about the length of an array can leak out even if you only have write permissions since you can catch out-of-bounds errors.

of_array_id and to_array_id return the same underlying array. On the other hand, to_array (inherited from Container.S1_permissions below) makes a copy.

To create a new (possibly immutable) copy of an array a, use copy (of_array_id a). More generally, any function that takes a (possibly mutable) t can be called on an array by calling of_array_id on it first.

There is a conceptual type equality between 'a Array.t and ('a, read_write) Array.Permissioned.t. The reason for not exposing this as an actual type equality is that we also want:

Since we don't control the definition of 'a array, this would require a type ('a, 'perms) Array.Permissioned.t which is abstract, except that ('a, read_write) Array.Permissioned.t is concrete, which is not possible.

to_sequence_immutable t converts t to a sequence. Unlike to_sequence, to_sequence_immutable does not need to copy t since it is immutable.

These functions are in Container.S1_permissions, but they are re-exposed here so that their types can be changed to make them more permissive (see comment above).

counterparts of regular array functions above