Module `Varray`Source

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.

Sourcetype 'a t

The type of a varray.

Sourcetype 'a elt = 'a

The type of elements stored in the varray.

Dynamic collection

Sourceval 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.

Sourceval pop_back : 'a t -> 'a elt

pop_back t removes and returns the rightmost element of the varray t. O(k) amortized.

Sourceval 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.

Sourceval 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.

Sourceval 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_argument
if i is negative or larger than length t.

Sourceval 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_argument
if i is negative or larger than length t - 1.

Sourceval 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_argument
if i is negative or larger than length t - 1.

Freeze during traversals

The previous operations all fail when the varray is being traversed:

Sourceval 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

Sourceval 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.

Sourceval 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.

Sourceval length : 'a t -> int

length t returns the number of elements stored in t. O(1)

Sourceval 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.

Sourceval 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.

Sourceval empty : unit -> 'a t

empty () is a new varray of length 0.

Sourceval is_empty : 'a t -> bool

is_empty t returns true when the varray t has length 0.

Copying elements

Sourceval append : 'a t -> 'a t -> 'a t

append a b returns a new varray by concatening the elements of a with those of b.

Sourceval 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.

Sourceval 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.

Sourceval copy : 'a t -> 'a t

copy t returns a new varray containing the same sequence of elements as t.

Sourceval 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.

Sourceval 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

Sourceval iter : ('a elt -> unit) -> 'a t -> unit

iter f t calls the function f on all elements of t, from left to right.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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).

Sourceval 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)))).

Sourceval 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

Sourceval 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.

Sourceval 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

Sourceval for_all : ('a elt -> bool) -> 'a t -> bool

for_all f t holds when f is satisfied by all the elements of t.

Sourceval 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.

Sourceval exists : ('a elt -> bool) -> 'a t -> bool

exists f t holds when f is satisfied by one of the elements of t.

Sourceval 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.

Sourceval find_opt : ('a elt -> bool) -> 'a t -> 'a elt option

find_opt f t returns the leftmost element of t that satisfies f.

Sourceval 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.

Sourceval mem : 'a elt -> 'a t -> bool

mem x t is true when x is equal ( = ) to an element of the varray t.

Sourceval memq : 'a elt -> 'a t -> bool

Same as mem, but memq x t uses physical equality ( == ) for comparison.

Sort

Sourceval 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.

Sourceval stable_sort : ('a elt -> 'a elt -> int) -> 'a t -> unit

Same as sort, but equal elements are kept in the same relative order.

Sourceval fast_sort : ('a elt -> 'a elt -> int) -> 'a t -> unit

Same as sort.

Conversions

Sourcetype 'a array = 'a Array.t

The array type used behind the scene as a backend by the varray.

Sourceval of_array : 'a array -> 'a t

of_array arr returns a new varray containing all the elements of the array arr.

Sourceval to_array : 'a t -> 'a array

to_array t returns a new array containing all the elements of the varray t.

Sourceval of_list : 'a elt list -> 'a t

of_list xs returns a new varray containing all the elements of the list xs.

Sourceval to_list : 'a t -> 'a elt list

to_list t returns a list of all the elements of t.

Signature

Sourcemodule Internals (X : sig ... end) : sig ... end

The signature of the internal operations, required by the Root functor below.

Sourcemodule type S = sig ... end

The signature of a varray.

Build your own

The family of varrays is defined by calling the Root functor as many times as required:

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})

The first step is to choose a backend Array that will be used to store the elements:

Sourcemodule type ARRAY = sig ... end

The array will be used partially, with some elements in an undefined state. It is guaranteed that all operations always use valid indexes.

Some good candidates from the standard library are Array for polymorphic values, BigArray.Array1 for numbers, Bytes for characters, or Weak for weak pointers.

Source

module Make
  (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).

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

Circular is a predefined circular varray using a polymorphic Stdlib.Array.