## Module Vecmodule Vec:Extensible arrays.
This module implements extensible arrays. All operations are
purely applicative (no side-effects). The implementation, based
on the implementation of Set, uses balanced binary trees, so that
insertion, deletions, and updates take logarithmic time in the
size of the array. `type `
The type of extensible arrays (vec) of elements of type
`'a` `exception Vec_index_out_of_bounds`
Raised when a vec is accessed out of bounds
`val empty : `
The empty vec.
`val singleton : ` `singleton d` creates a vec consisting of exactly the element `d` `val create : ` `create d n` creates a vec of length `n` , where each cell
contains `d` .`val length : `
Returns the length of the vec.
`val is_empty : `
Tests whether a vec is empty or not.
`val get : ` `get i v` gets element `i` of vec `v` ; the first element of `v`
is element 0.`val set : ` `set i d v` sets the element in position `i` of vec `v` to value `d` .
The position must already exist.`val append : ` `append d v` extends the vec `v` , by adding the element `d` at
the end.`val setappend : ` `setappend d0 d i v` sets the element in position `i` of `v` to
value `d` , if `v` is long enough. Otherwise, it extends `v`
with as many elements `d0` as needed, then appends the value `d`
in position `i` .`val concat : ` `concat v1 v2` concatenates the vecs `v1` and `v2` .`val pop : ` `pop i v` returns (e, v'), where `e` is the element in position `i`
of vec `v` , and `v'` is obtained by removing `e` from `v` .`val remove : ` `remove i v` removes the element in position `i` of vec `v` .`val insert : ` `insert i d v` inserts element `d` in position `i` of vec `v` .
All elements following `i` are shifted right by 1. If `i` is 0,
then `d` is inserted in the first position of the vec. If `i` is
`length v` , then `d` is inserted at the end of `v` , extending it
by 1.`val sub : ` `sub i j v` returns the sub-vec of `v` consisting of all elements
with indices `k` with `i` <= `k` < `j` .`val iter : ` `iter f v` applies `f` to all elements in `v` . The elements are
passed to `f` in increasing index order.`val iteri : `
Similar to iter, but the function is passed also the index of the
element to which it is applied.
`val reviter : ` `reviter f v` applies `f` to all elements in `v` . The elements are
passed to `f` in decreasing index order.`val rangeiter : ` `rangeiter f i j v` applies `f` to all elements in `v` that have
index `k` with `i` <= `k` < `j` . The elements are passed to `f`
in increasing index order.`val rangeiteri : ` `rangeiteri f i j v` is the same as `rangeiter f i j v` , but `f`
is applied also to the index of each element.`val revrangeiter : ` `revrangeiter f v i j` applies `f` to all elements in `v` that have
index `k` with `i` <= `k` < `j` . The elements are passed to `f`
in decreasing index order.`val revrangeiteri : ` `revrangeiteri f i j v` is the same as `revrangeiter f i j v` ,
but `f` is applied also to the index of each element.`val map : ` `map f v` returns a vec, obtained by applying the function `f`
to each element of `v` . The elements are passed to `f` in
increasing order.`val mapi : ` `mapi f v` is the same as `map f v` , but the function `f` is
applied also to the index of each element.`val fold : ` `fold f v a` computes `(f dN ... (f d0 a)...)` , where ```
d0
... dN
``` are data in the vec, in increasing order.`val foldi : ` `foldi f v a` computes `(f N dN ... (f 1 d0 a)...)` , where
`d0 ... dN` are data in the vec, in increasing order.`val rangefoldi : ` `rangefoldi f i j v` folds function `f` over the elements in the
range i, i+1, ..., j-1 of the vector `v` . The function `f` is
passed the index of the vec element, the element itself, and the
accumulation. The folding proceeds in increasing index
order.`val revrangefoldi : ` `revrangefoldi f i j v` is equivalent to `rangefoldi f i j v` ,
except that the folding proceeds in decreasing, rather than
increasing, index order.`val of_list : ` `of_list l` returns a vec consisting of the elements of `l` , in
the same order.`val to_list : ` `to_list v` returns a list containing the elements of vec `v` ,
in the order in which they appear in `v` .`val of_array : ` `of_array a` returns a vec consisting of the elements of array `a` , in
the same order.`val to_array : ` `to_array v` returns either None, if the vector is empty, or Some of an
array containing the elements of vec `v` , in the order in which they
appear in `v` . The option type is needed, as there is no way to make
an array of zero length without specifying one element of the array.`val visit_post : ` `visit_post ve vn a` implements a post-order visit to the tree representation of `a` .
`ve` is the evaluation of an empty tree. For an internal node with data `d` and
left and right children that evaluate to `l` , `r` , the function returns `vn l d r` .`val visit_in : `
`visit_in ve vl vr a` implements an in-order visit to the tree representation of `a` .
`ve` is the evaluation of an empty tree. For an internal node with data `d` and
left and right children `cl` , `cr` , the function returns `vr (vl cl' d) cr'` ,
where `cl'` is the evaluation of `cl` , and `cr'` is the evaluation of `cr` .
Moreover, `cr'` is computed only after `vl cl' d` is computed. |