varray 0.2 (latest) · OCaml Package

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_argument
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_argument
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_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:

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 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 (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

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:

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

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

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

module Root
  (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!

package varray