Previous  Up  Next

Module BatDynArray

module BatDynArray: sig .. end

Dynamic arrays.

A dynamic array is equivalent to an OCaml array that will resize itself when elements are added or removed, except that floats are boxed and that no initialization element is required.

For all the traversal functions (iter, fold, map, etc.), what happens when the array that is being traversed is mutated is not defined.

type 'a t 
include BatEnum.Enumerable
include BatInterfaces.Mappable
exception Invalid_arg of int * string * string

When an operation on an array fails, Invalid_arg is raised. The integer is the value that made the operation fail, the first string contains the function name that has been called and the second string contains the parameter name that made the operation fail.

Array creation 
val create : unit -> 'a t

create() returns a new empty dynamic array.

val make : int -> 'a t

make count returns an array with some memory already allocated so up to count elements can be stored into it without resizing.

val init : int -> (int -> 'a) -> 'a t

init n f returns an array of n elements filled with values returned by f 0 , f 1, ... f (n-1).

val singleton : 'a -> 'a t

Create an array consisting of exactly one element.

Array manipulation functions 
val get : 'a t -> int -> 'a

get darr idx gets the element in darr at index idx. If darr has len elements in it, then the valid indexes range from 0 to len-1.

val set : 'a t -> int -> 'a -> unit

set darr idx v sets the element of darr at index idx to value v. The previous value is overwritten.

val upd : 'a t -> int -> ('a -> 'a) -> unit

upd darr idx f sets the element of darr at index idx to value f (get darr idx)). The previous value is overwritten.

val length : 'a t -> int

Return the number of elements in the array.

val empty : 'a t -> bool

Return true if the number of elements in the array is 0.

val first : 'a t -> 'a

first darr returns the first element of darr.

val last : 'a t -> 'a

last darr returns the last element of darr.

val left : 'a t -> int -> 'a t

left r len returns the array containing the len first characters of r. If r contains less than len characters, it returns r.

val right : 'a t -> int -> 'a t

right r len returns the array containing the len last characters of r. If r contains less than len characters, it returns r.

val head : 'a t -> int -> 'a t

Alias for BatDynArray.left

val tail : 'a t -> int -> 'a t

tail r pos returns the array containing all but the pos first characters of r.

val insert : 'a t -> int -> 'a -> unit

insert darr idx v inserts v into darr at index idx. All elements of darr with an index greater than or equal to idx have their index incremented (are moved up one place) to make room for the new element.

val add : 'a t -> 'a -> unit

add darr v appends v onto the end of darr. v becomes the new last element of darr.

val append : 'a t -> 'a t -> unit

append src dst adds all elements of src to the end of dst.

val delete : 'a t -> int -> unit

delete darr idx deletes the element of darr at idx. All elements with an index greater than idx have their index decremented (are moved down one place) to fill in the hole.

val delete_last : 'a t -> unit

delete_last darr deletes the last element of darr. This is equivalent of doing delete darr ((length darr) - 1).

val delete_range : 'a t -> int -> int -> unit

delete_range darr idx len deletes len elements starting at index idx. All elements with an index greater than idx+len are moved to fill in the hole.

val clear : 'a t -> unit

remove all elements from the array and resize it to 0.

val blit : 'a t -> int -> 'a t -> int -> int -> unit

blit src srcidx dst dstidx len copies len elements from src starting with index srcidx to dst starting at dstidx.

val compact : 'a t -> unit

compact darr ensures that the space allocated by the array is minimal.

Array copy and conversion 
val enum : 'a t -> 'a BatEnum.t

enum darr returns the enumeration of darr elements.

val of_enum : 'a BatEnum.t -> 'a t

of_enum e returns an array that holds, in order, the elements of e.

val range : 'a t -> int BatEnum.t

range a returns an enumeration of all valid indices of the given array, that is, range a = 0 --^ ((length a) -1 )

val to_list : 'a t -> 'a list

to_list darr returns the elements of darr in order as a list.

val of_list : 'a list -> 'a t

of_list lst returns a dynamic array with the elements of lst in it in order.

val to_array : 'a t -> 'a array

to_array darr returns the elements of darr in order as an array.

val of_array : 'a array -> 'a t

of_array arr returns an array with the elements of arr in it in order.

val copy : 'a t -> 'a t

copy a returns a fresh copy of a, such that no modification of a affects the copy, or vice versa (all new memory is allocated for the copy).

val sub : 'a t -> int -> int -> 'a t

sub a start len returns an array holding the subset of len elements from a starting with the element at index idx.

val fill : 'a t -> int -> int -> 'a -> unit

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

val split : ('a * 'b) t -> 'a t * 'b t

split a converts the array of pairs a into a pair of arrays.

val combine : 'a t -> 'b t -> ('a * 'b) t

combine a b converts arrays [a0,...aN] [b0,...,bN] into an array of pairs [(a0,b0),...,(aN,bN)].

Array functional support 
val iter : ('a -> unit) -> 'a t -> unit

iter f darr calls the function f on every element of darr. It is equivalent to for i = 0 to length darr - 1 do f (get darr i) done;

val iteri : (int -> 'a -> unit) -> 'a t -> unit

iteri f darr calls the function f on every element of darr. It is equivalent to for i = 0 to length darr - 1 do f i (get darr i) done;

val map : ('a -> 'b) -> 'a t -> 'b t

map f darr applies the function f to every element of darr and creates a dynamic array from the results - similar to List.map or Array.map.

val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

mapi f darr applies the function f to every element of darr and creates a dynamic array from the results - similar to List.mapi or Array.mapi.

val modify : ('a -> 'a) -> 'a t -> unit

modify f a replaces every element x of a with f x.

val modifyi : (int -> 'a -> 'a) -> 'a t -> unit

Same as BatDynArray.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_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

fold_left f x darr computes f ( ... ( f ( f a0 x) a1) ) ... )
    aN, where a0,a1..aN are the indexed elements of darr.

val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b

fold_right f darr x computes  f a0 (f a1 ( ... ( f aN x )
    ... ) ) , where a0,a1..aN are the indexed elements of darr.

val fold_lefti : ('a -> int -> 'b -> 'a) -> 'a -> 'b t -> 'a

As fold_left, but with the index of the element as additional argument.

val fold_righti : (int -> 'b -> 'a -> 'a) -> 'b t -> 'a -> 'a

As fold_right, but with the index of the element as additional argument.

val reduce : ('a -> 'a -> 'a) -> 'a t -> 'a

reduce f a is fold_left f a0 [a1, ... aN]. This is useful for merging a group of things that have no reasonable default value to return if the group is empty.

val keep : ('a -> bool) -> 'a t -> unit

keep p darr removes in place all the element x of darr such that p x = false

Note In previous versions, this function used to be called BatDynArray.filter. As this caused incompatibilities with comprehension of dynamic arrays, the function name has been changed.

val filter : ('a -> bool) -> 'a t -> 'a t

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.

Note This function replaces another function called filter, available in previous versions of the library. As the old function was incompatible with comprehension of dynamic arrays, its name was changed to BatDynArray.keep.

val find_all : ('a -> bool) -> 'a t -> 'a t

find_all is another name for filter.

val filteri : (int -> 'a -> bool) -> 'a t -> 'a t

As filter but with the index passed to the predicate.

val filter_map : ('a -> 'b option) -> 'a t -> 'b t

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 partition : ('a -> bool) -> 'a t -> 'a t * 'a t

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 for_all : ('a -> bool) -> 'a t -> 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 t -> 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 t -> 'a

find p a returns the first element of array a that satisfies the predicate p.

val findi : ('a -> bool) -> 'a t -> int

findi p a returns the index of the first element of array a that satisfies the predicate p.

val index_of : ('a -> bool) -> 'a t -> int

Alias for BatDynArray.findi

val mem : 'a -> 'a t -> bool

mem m a is true if and only if m is equal to an element of a.

val memq : 'a -> 'a t -> bool

Same as BatDynArray.mem but uses physical equality instead of structural equality to compare array elements.

val rev : 'a t -> 'a t

Array reversal.

val rev_in_place : 'a t -> unit

In-place array reversal. The given array is updated.

val max : 'a t -> 'a

max a returns the largest value in a as judged by Pervasives.compare

val min : 'a t -> 'a

min a returns the smallest value in a as judged by Pervasives.compare

val min_max : 'a t -> 'a * 'a

min_max a returns the (smallest, largest) pair of values from a as judged by Pervasives.compare

val sum : int t -> int

sum l returns the sum of the integers of l.

val fsum : float t -> float

fsum l returns the sum of the floats of l.

val kahan_sum : float t -> 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 BatDynArray.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 t -> float

avg l returns the average of l

val favg : float t -> float

favg l returns the average of l

Operations on two arrays 
val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit

iter2 f [a0, a1, ..., an] [b0, b1, ..., bn] performs calls f a0 b0, f a1 b1, ..., f an bn in that order.

val iter2i : (int -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit

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.

val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

As BatDynArray.map but on two arrays.

val map2i : (int -> 'a -> 'b -> 'c) ->
       'a t -> 'b t -> 'c t

As BatDynArray.mapi but on two arrays.

val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

As BatDynArray.for_all but on two arrays.

val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

As BatDynArray.exists but on two arrays.

val cartesian_product : 'a t -> 'b t -> ('a * 'b) t

Cartesian product of the two arrays.

Array resizers 
type resizer_t = currslots:int -> oldlength:int -> newlength:int -> int

The type of a resizer function.

Resizer functions are called whenever elements are added to or removed from the dynamic array to determine what the current number of storage spaces in the array should be. The three named arguments passed to a resizer are the current number of storage spaces in the array, the length of the array before the elements are added or removed, and the length the array will be after the elements are added or removed. If elements are being added, newlength will be larger than oldlength, if elements are being removed, newlength will be smaller than oldlength. If the resizer function returns exactly oldlength, the size of the array is only changed when adding an element while there is not enough space for it.

By default, all dynamic arrays are created with the default_resizer. When a dynamic array is created from another dynamic array (using copy, map , etc. ) the resizer of the copy will be the same as the original dynamic array resizer. To change the resizer, use the set_resizer function.

val set_resizer : 'a t -> resizer_t -> unit

Change the resizer for this array.

val get_resizer : 'a t -> resizer_t

Get the current resizer function for a given array

val default_resizer : resizer_t

The default resizer function the library is using - in this version of DynArray, this is the exponential_resizer but should change in next versions.

val exponential_resizer : resizer_t

The exponential resizer- The default resizer except when the resizer is being copied from some other darray.

exponential_resizer works by doubling or halving the number of slots until they "fit". If the number of slots is less than the new length, the number of slots is doubled until it is greater than the new length (or Sys.max_array_size is reached).

If the number of slots is more than four times the new length, the number of slots is halved until it is less than four times the new length.

Allowing darrays to fall below 25% utilization before shrinking them prevents "thrashing". Consider the case where the caller is constantly adding a few elements, and then removing a few elements, causing the length to constantly cross above and below a power of two. Shrinking the array when it falls below 50% would causing the underlying array to be constantly allocated and deallocated. A few elements would be added, causing the array to be reallocated and have a usage of just above 50%. Then a few elements would be remove, and the array would fall below 50% utilization and be reallocated yet again. The bulk of the array, untouched, would be copied and copied again. By setting the threshold at 25% instead, such "thrashing" only occurs with wild swings- adding and removing huge numbers of elements (more than half of the elements in the array).

exponential_resizer is a good performing resizer for most applications. A list allocates 2 words for every element, while an array (with large numbers of elements) allocates only 1 word per element (ignoring unboxed floats). On insert, exponential_resizer keeps the amount of wasted "extra" array elements below 50%, meaning that less than 2 words per element are used. Even on removals where the amount of wasted space is allowed to rise to 75%, that only means that darray is using 4 words per element. This is generally not a significant overhead.

Furthermore, exponential_resizer minimizes the number of copies needed- appending n elements into an empty darray with initial size 0 requires between n and 2n elements of the array be copied- O(n) work, or O(1) work per element (on average). A similar argument can be made that deletes from the end of the array are O(1) as well (obviously deletes from anywhere else are O(n) work- you have to move the n or so elements above the deleted element down).

val step_resizer : int -> resizer_t

The stepwise resizer- another example of a resizer function, this time of a parameterized resizer.

The resizer returned by step_resizer step returns the smallest multiple of step larger than newlength if currslots is less then newlength-step or greater than newlength.

For example, to make an darray with a step of 10, a length of len, and a null of null, you would do: make ~resizer:(step_resizer 10) len null

val conservative_exponential_resizer : resizer_t

conservative_exponential_resizer is an example resizer function which uses the oldlength parameter. It only shrinks the array on inserts- no deletes shrink the array, only inserts. It does this by comparing the oldlength and newlength parameters. Other than that, it acts like exponential_resizer.

val create_with : resizer_t -> 'a t

create a new dynamic array that uses the given resizer.

Unsafe operations

*

val unsafe_get : 'a t -> int -> 'a
val unsafe_set : 'a t -> int -> 'a -> unit
val unsafe_upd : 'a t -> int -> ('a -> 'a) -> unit
Boilerplate code
Printing
val print : ?first:string ->
       ?last:string ->
       ?sep:string ->
       ('a BatInnerIO.output -> 'b -> unit) ->
       'a BatInnerIO.output -> 'b t -> unit
module Exceptionless: sig .. end

Operations on DynArray without exceptions.