module ExtendableArray:`sig`

..`end`

Extendable (also called dynamic) arrays, growing as necessary.

Extendable arrays are commonly defined by two dimensions: their length and capacity. The first dimension tells how many elements are currently actually stored in the array, while the second dimension tells how many elements could be stored in the array without having to redimension (and hence reallocate) it.

Extendable arrays store elements in the same way as array
(*i. e.* at the lowest indexes), as opposed to sparse arrays.

The present implementation uses `Utils.u2`

indexes, thus having a
maximum length of `65536`

.

`type ``'a`

t

The type of extendable arrays.

`val make : ``int -> int -> 'a -> 'a t`

`make len cap init`

returns an extendable array with an initial
length of `len`

and capacity `cap`

, each element being initialized to
`init`

.
Raises `Invalid_argument`

if the passed length or capacity is too
large, or negative.`val from_array : ``exn -> 'a array -> 'a -> 'a t`

Constructs an extendable array from a bare one.
The second element is used to fill the part of the array between its
length and its capacity, if any.
Raises

`Invalid_argument`

if the passed array is too large, or negative.`val to_array : ``'a t -> 'a array`

Constructs a bare array from an extendable one.

`val length : ``'a t -> int`

Returns the length of the passed array.

`val capacity : ``'a t -> int`

Returns the capacity of the passed array.

`val get : ``'a t -> Utils.u2 -> 'a`

`get a i`

returns the element of `a`

at index `i`

.
Raises `Invalid_argument`

if `i`

is out of bounds.`val set : ``'a t -> Utils.u2 -> 'a -> unit`

`set a i x`

changes the element of `a`

at index `i`

to `x`

.
`Invalid_argument`

if `i`

is out of bounds.`val find : ``('a -> bool) -> 'a t -> Utils.u2`

`index p a`

returns the lowest index `i`

of `a`

such that
`p (get a i)`

is `true`

.
Raises `Not_found`

if such an index does not exist.`val add : ``exn -> 'a t -> 'a -> 'a -> bool -> Utils.u2`

`add e a x z addit`

extends array `a`

by an element set to `x`

.
Returns the index of the added element. `addit`

indicates whether an
unused element `z`

should be added to the array. The `z`

value is
also used to fill the part of the array between its length and its
capacity, if any.
Raises `e`

if the array cannot be extended.`val add_if_not_found : ``exn -> ('a -> bool) -> 'a t -> 'a -> 'a -> bool -> Utils.u2`

`add_if_not_found e p a x z add`

returns the lowest index `i`

of `a`

such that `p (get a i)`

is `true`

. If such an index does not exist in
`a`

, a new element `x`

is added to the array.
Equivalent to `try find p a with Not_found -> add e a x z addit`

.
Raises `e`

if the array cannot be extended.`val equal : ``('a -> 'a -> bool) -> 'a t -> 'a t -> bool`

Equality over extendable arrays.

`val compare : ``('a -> 'a -> int) -> 'a t -> 'a t -> int`

Comparison over extendable arrays.

`val hash : ``('a -> int) -> 'a t -> int`

Hash function over extendable arrays.

`val to_string : ``('a -> string) -> 'a t -> string`

Converts the passed extendable array into a string.