Module `Varray`

A varray is a variable sized array, also known as a resizable or dynamic array.

Just like an array, random access / update is O(1). But you can also grow the varray by appending or prepending an element in constant time. Insertion and deletion at a specific index cost O(^k√N) for any constant k ≥ 1 of your choosing.

For convenience, the recommended complexity tradeoff between time and memory is provided below with the constant parameter k = 2. You will find the internal building blocks at the end of this documentation to create a custom Varray with different asymptotics.

type 'a t: The type of a varray.

type 'a elt = 'a: The type of elements stored in the varray.

Dynamic collection

val push_back : 'a t -> 'a elt -> unit: push_back t x adds a new element x at the end of the varray t. O(k) amortized.

val pop_back : 'a t -> 'a elt: pop_back t removes and returns the rightmost element of the varray t. O(k) amortized.

val push_front : 'a t -> 'a elt -> unit: push_front t x inserts a new element x at position 0, on the left side of the varray t. Every previous element of t is shifted one to the right. O(k) amortized.

val pop_front : 'a t -> 'a elt: pop_front t removes and returns the leftmost element at position 0 of the varray t. Every element of t is shifted one to the right. O(k) amortized.

val insert_at : 'a t -> int -> 'a elt -> unit

insert_at t i x inserts the element x at position i in the varray t. Every element on the right of i is shifted by one. O(k² × ^k√N)

insert_at t 0 x is the same as push_front t x
insert_at t (length t) x is the same as push_back t x

raises Invalid_arg: if i is negative or larger than length t.

val pop_at : 'a t -> int -> 'a elt

pop_at t i removes and returns the element t.(i). Every element on the right of i is shifted by one to the left. O(k² × ^k√N)

pop_at t 0 is the same as pop_front t
pop_at t (length t - 1) is the same as pop_back t

raises Invalid_arg: if i is negative or larger than length t - 1.

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

delete_at t i removes the element t.(i). Every element on the right of i is shifted by one to the left. O(k² × ^k√N)

raises Invalid_arg: if i is negative or larger than length t - 1.

Freeze during traversals

val protect : 'a t -> (unit -> 'b) -> 'b: protect t fn marks t as protected during the execution of fn (). All operations that would update the length of t by pushing or poping elements will raise a Failure indicating that the traversal is unsafe.

Array

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

get t i returns the ith element of the varray. Indexing starts from 0 upto length t - 1. O(k)

raises Invalid_argument: if i is negative or larger than length t - 1.

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

set t i v updates the value of the ith element to x. O(k)

raises Invalid_argument: if i is negative or larger than length t - 1.

val length : 'a t -> int: length t returns the number of elements stored in t. O(1)

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

make n x returns a new varray of length n, where all the elements are initialized to the value x.

raises Invalid_argument: if n is negative.

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

init n f returns a new array of length n, where the element at position i is initialized to f i.

raises Invalid_argument: if n is negative.

val empty : unit -> 'a t: empty () is a new varray of length 0.

val is_empty : 'a t -> bool: is_empty t returns true when the varray t has length 0.

Copying elements

val append : 'a t -> 'a t -> 'a t: append a b returns a new varray by concatening the elements of a with those of b.

val concat : 'a t list -> 'a t: concat ts returns a new varray whose elements are in the same order as the values from the list of varrays ts.

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

sub t i n returns a new varray of length n, containing the elements from the range i, i+n-1 of the varray t.

raises Invalid_argument: if the range i, i + n - 1 is invalid for t.

val copy : 'a t -> 'a t: copy t returns a new varray containing the same sequence of elements as t.

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

fill t pos len x modifies the varray t in place, by setting the value x in the range pos, pos + len - 1.

raises Invalid_argument: if the range pos, pos + len -1 is invalid.

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

blit src src_pos dst dst_pos len updates the varray dst in place, by copying the range src_pos, src_pos + len - 1 of values from src into the destination range dst_pos, dst_pos + len - 1 of dst.

raises Invalid_argument: if the ranges are invalid for either varray.

Traversals

val iter : ('a elt -> unit) -> 'a t -> unit: iter f t calls the function f on all elements of t, from left to right.

val iteri : (int -> 'a elt -> unit) -> 'a t -> unit: iteri f t calls f i t.(i) on all the indexes i of t, from left to right.

val map : ('a elt -> 'b elt) -> 'a t -> 'b t: map f t returns a new varray, whose elements are f x for each x from the varray t.

val mapi : (int -> 'a elt -> 'b elt) -> 'a t -> 'b t: mapi f t returns a new varray, whose elements are f i t.(i) for each index i of the varray t.

val fold_left : ('a -> 'b elt -> 'a) -> 'a -> 'b t -> 'a: fold_left f z t computes f (... (f (f z t.(0)) t.(1)) ...) t.(length t - 1).

val fold_right : ('a elt -> 'b -> 'b) -> 'a t -> 'b -> 'b: fold_right f t z computes f t.(0) (f t.(1) (... (f z t.(length t - 1)))).

val fold_left_map : ('a -> 'b elt -> 'a * 'c elt) -> 'a -> 'b t -> 'a * 'c t: fold_left_map is a combination of fold_left and map, that threads an accumulator.

Iterators on two varrays

val iter2 : ('a elt -> 'b elt -> unit) -> 'a t -> 'b t -> unit

iter2 f xs ys calls f xs.(i) ys.(i) for each index i from left to right.

raises Invalid_argument: if the two varrays have different lengths.

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

map2 f xs ys returns a new varray whose ith element is f xs.(i) ys.(i).

raises Invalid_argument: if the two varrays have different lengths.

Predicates

val for_all : ('a elt -> bool) -> 'a t -> bool: for_all f t holds when f is satisfied by all the elements of t.

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

for_all2 f xs ys holds when f xs.(i) ys.(i) is satisfied by all indexes i.

raises Invalid_argument: if the two varrays have different lengths.

val exists : ('a elt -> bool) -> 'a t -> bool: exists f t holds when f is satisfied by one of the elements of t.

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

exists2 f xs ys holds when an index i exists such that f xs.(i) ys.(i) is satisfied.

raises Invalid_argument: if the two varrays have different lengths.

val find_opt : ('a elt -> bool) -> 'a t -> 'a elt option: find_opt f t returns the leftmost element of t that satisfies f.

val find_map : ('a elt -> 'b option) -> 'a t -> 'b option: find_map f t returns the first result of f of the form Some v.

val mem : 'a elt -> 'a t -> bool: mem x t is true when x is equal ( = ) to an element of the varray t.

val memq : 'a elt -> 'a t -> bool: Same as mem, but memq x t uses physical equality ( == ) for comparison.

Sort

val sort : ('a elt -> 'a elt -> int) -> 'a t -> unit: sort cmp t updates t inplace by sorting the elements in increasing order according to cmp.

val stable_sort : ('a elt -> 'a elt -> int) -> 'a t -> unit: Same as sort, but equal elements are kept in the same relative order.

val fast_sort : ('a elt -> 'a elt -> int) -> 'a t -> unit: Same as sort.

Conversions

type 'a array = 'a Stdlib.Array.t: The array type used behind the scene as a backend by the varray.

val of_array : 'a array -> 'a t: of_array arr returns a new varray containing all the elements of the array arr.

val to_array : 'a t -> 'a array: to_array t returns a new array containing all the elements of the varray t.

val of_list : 'a elt list -> 'a t: of_list xs returns a new varray containing all the elements of the list xs.

val to_list : 'a t -> 'a elt list: to_list t returns a list of all the elements of t.

Signature

module Internals : functor (X : sig ... end) -> sig ... end: The signature of the internal operations, required by the Root functor below.

module type S = sig ... end: The signature of a varray.

Build your own

Module	`get`, `set` `push`, `pop`	`insert_at` `delete_at`	Memory overhead
`Circular`	O(1)	O(N)	O(N)
`Root (Circular)`	O(1)	O(²√N)	O(²√N)
`Root (Root (Circular))`	O(1)	O(³√N)	O(N^2/3)
`Root^k-1 (Circular)`	O(k)	O(k² × ^k√N)	O(N^{k-1 / k})

module type ARRAY = sig ... end

module Make : functor (Array : ARRAY) -> S with type 'a array = 'a Array.t and type 'a elt = 'a Array.elt: Make (Array) returns a circular varray using Array as its backend. The resulting varray has parameter k = 1, meaning that push and pop at both ends is O(1) but random insertion and deletions are O(N).

module Circular : S with type 'a array = 'a Stdlib.Array.t and type 'a elt = 'a

module Root : functor (V : S) -> S with type 'a array = 'a V.array and type 'a elt = 'a V.elt: Root (Varray) nests an existing Varray to improve the performances of random insertion and deletion. However, it does so at the price that random access and insertion and deletion at the ends will be a constant time slower!