module Vec:Dynamically resizable arrays.`sig`

..`end`

`type ``'a`

t

Resizable vector of

`'a`

elements.`val limit_for : ``'a -> int`

`limit_for x`

is the maximum number of elements of the same type
as `x`

that may be stored in a vector.

- Ensure
`0 < limit_for x`

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

`make n x`

is a vector of length `n`

, with each element equal to
`x`

.`Invalid_argument`

"exceeds limit" if `n > `

`Vec.limit_for`

` x`

- Require
`n >= 0`

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

Synonym for

`Vec.make`

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

`init n f`

is a vector with length `n`

. Element `i`

is `f i`

.`Invalid_argument`

"exceeds limit" if `n > `

`Vec.limit_for`

` x`

- Require
`n >= 0`

`val copy : ``'a t -> 'a t`

`copy v`

is a copy of `v`

; the elements are shared by `v`

and
the copy.`val to_list : ``'a t -> 'a list`

`to_list v`

is a list of the elements of `v`

in their
positional order.`val of_list : ``'a list -> 'a t`

`of_list l`

is a vector of the elements of `l`

in their
positional order.`Invalid_argument`

"exceeds limit"
if `length l >`

`Vec.limit_for`

` x`

- Require
`not (l = [])`

`val to_array : ``'a t -> 'a array`

`to_array v`

is an array with the elements of `v`

.`val of_array : ``'a array -> 'a t`

`of_array a`

is a vector with the elements of `a`

.

- Require
`Array.size a > 0`

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

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

`val is_empty : ``'a t -> bool`

`val grow : ``'a t -> int -> 'a -> unit`

`grow v n x`

grows the size of `v`

to `n`

, filling in the newly
created slots with `x`

.`Invalid_argument`

"exceeds limit"
if `n > `

`Vec.limit`

`v`

- Require
`n >`

`Vec.length`

`v`

`val grow_init : ``'a t -> int -> (int -> 'a) -> unit`

`grow_init v n f`

grows the size of `v`

to `n`

, filling in each newly
created slots `i`

with `f i`

.`Invalid_argument`

"exceeds limit"
if `n > `

`Vec.limit`

`v`

- Require
`n >`

`Vec.length`

`v`

`val shrink : ``'a t -> int -> unit`

`shrink v n`

shrinks the size of `v`

to `n`

. Takes time linear
in proportion with `Vec.length`

` v - n`

.

- Require
`0 <= n <=`

`Vec.length`

`v`

`val clear : ``'a t -> unit`

`clear v`

removes all elements from `v`

. Takes time linear in
proportion with `Vec.length`

` v`

.
`clear`

is a synonym for `Vec.shrink`

`0`

.

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

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

`val set_all : ``'a t -> int -> int -> 'a -> unit`

`val push : ``'a t -> 'a -> unit`

`push v x`

extends the length of the `v`

by `1`

. The new last
element is `x`

.`Invalid_argument`

"exceeds limit"
if `length l =`

`Vec.limit`

` v`

`val pop : ``'a t -> 'a`

`val top : ``'a t -> 'a`

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

`insert v i x`

inserts `x`

into position `i`

of `v`

, pushing
elements at position `i`

and above up by `1`

. The length `v`

increases by `1`

.`Invalid_argument`

"exceeds limit"
if `length l =`

`Vec.limit`

` v`

- Require
`0 <= i <=`

`Vec.length`

`v`

- Takes time proportionate to
`Vec.length`

`v - i + 1`

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

`delete v i`

removes the element at position `i`

of `v`

, pulling
elements above down by `1`

. The length of `v`

decreases by
`1`

. `Vec.swap_out`

`v i`

is faster if you do not need to
preserve the order of the elements.

- Require
`0 <= i <`

`Vec.length`

`v`

- Takes time proportionate to
`Vec.length`

`v - n`

`val swap : ``'a t -> int -> int -> unit`

`swap v i j`

swaps the elements at positions `i`

and `j`

of `v`

.

- Require
`0 <= i && i <`

`Vec.length`

`v`

- Require
`0 <= j && j <`

`Vec.length`

`v`

- Takes constant time.

`val swap_out : ``'a t -> int -> unit`

`swap_out v i`

replaces the element at position `i`

of `v`

with
the last element of `v`

, and decreases the length of `v`

by `1`

.
This is faster than `Vec.delete`

`v i`

if you do not need to
preserve the order of the elements.

- Require
`0 <= i && i <`

`Vec.length`

`v`

- Takes constant time.

`val rev : ``'a t -> unit`

`rev v`

reverses the order of elements in `v`

.`val iter : ``('a -> unit) -> 'a t -> unit`

`iter c v`

evaluates `c`

on each element of `v`

. It is
equivalent to `c (get v 0); ...; c (get v (length v - 1)`

.`val iter_const : ``('a -> 'b -> unit) -> 'a -> 'b t -> unit`

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

Like

`Vec.iter`

, but the command takes the index of the element
as the first argument`val iteri_const : ``('a -> int -> 'b -> unit) -> 'a -> 'b t -> unit`

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

`modify f v`

replaces each element of `v`

with `f`

of that element.`val modify_const : ``('a -> 'b -> 'b) -> 'a -> 'b t -> unit`

`val fold_left : ``('a -> 'b -> 'a) -> 'a -> 'b t -> 'a`

`fold_left f l v`

computes `f (... (f (f l (`

`Vec.get`

```
v i))
(
```

`Vec.get`

` v (i+1)) ...) (Vec.get v (`

`Vec.length`

` v - 1))`

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

`fold_right f v r`

computes `f (`

`Vec.get`

```
v i) (... (f
(
```

`Vec.get`

` v (j-2)) (f (`

`Vec.get`

` v (`

`Vec.length`

```
v -
1)) r)) ...)
```

`val foldi_left : ``('a -> int -> 'b -> 'a) -> 'a -> 'b t -> 'a`

`fold_lefti f l v`

computes `f (... (f (f l i (`

`Vec.get`

```
v
i)) (i+1) (
```

`Vec.get`

` v (i+1))) ...) (j-1) (`

`Vec.get`

```
v
(
```

`Vec.length`

` v - 1))`

.`val foldi_right : ``(int -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b`

`foldi_right f v r`

computes `f i (`

`Vec.get`

```
v i) (... (f
(j-2) (
```

`Vec.get`

` v (j-2)) (f (j-1) (`

`Vec.get`

```
v
(
```

`Vec.length`

` v - 1)) r)) ...)`

`val fold_left_const : ``('a -> 'b -> 'c -> 'b) -> 'a -> 'b -> 'c t -> 'b`

`val fold_right_const : ``('a -> 'b -> 'c -> 'c) -> 'a -> 'b t -> 'c -> 'c`

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

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

`foldi_right_const f x v r`

is `Vec.foldi_right`

` (f x) v r`

, only
faster since applying closures is slow.`val mem : ``'a -> 'a t -> bool`

`mem x v`

holds if `x`

is an element of `v`

.`val exists : ``('a -> bool) -> 'a t -> bool`

`val exists_const : ``('a -> 'b -> bool) -> 'a -> 'b t -> bool`

`val for_all : ``('a -> bool) -> 'a t -> bool`

`val for_all_const : ``('a -> 'b -> bool) -> 'a -> 'b t -> bool`

`val find : ``('a -> bool) -> 'a t -> 'a`

`find p v`

is the first element of `v`

satisfying `p`

.`Not_found`

if no element of `v`

satisfies `p`

`val find_const : ``('a -> 'b -> bool) -> 'a -> 'b t -> 'b`

`val first : ``('a -> bool) -> 'a t -> int`

`first p v `

is the index of the first element of `v`

satisfying
`p`

.`Not_found`

if no element of `v`

satisfies `p`

`val first_const : ``('a -> 'b -> bool) -> 'a -> 'b t -> int`

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

`filter p v`

removes those elements of `v`

not satisfying `p`

`val filter_const : ``('a -> 'b -> bool) -> 'a -> 'b t -> unit`

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

Like

`Vec.filter`

, but the predicate takes the index of the
element as the first argument.`val filteri_const : ``('a -> int -> 'b -> bool) -> 'a -> 'b t -> unit`

`val fast_filter : ``('a -> bool) -> 'a t -> unit`

Like

`Vec.filter`

, but does not preserve the order of elements.`val fast_filter_const : ``('a -> 'b -> bool) -> 'a -> 'b t -> unit`

`val sort : ``('a -> 'a -> int) -> 'a t -> unit`

`sort c v`

sorts elements of v in ascending order as defined by
the comparison function c. `c x y`

returns a negative number if
x comes before y, a positive number if x comes after y and zero
if x and y are order equivalent.`val stable_sort : ``('a -> 'a -> int) -> 'a t -> unit`

`stable_sort c v`

sorts elements of v in ascending order as
defined by the comparison function c. `c x y`

returns a
negative number if x comes before y, a positive number if x
comes after y and zero if x and y are order equivalent.
The sort is stable in that adjacent order equivalent elements
remain in their original order.

Hosted by the