Module type Varray.S

The signature of a varray.

type 'a t

The type of a varray.

type 'a elt

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

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.

Internals

module Backend : sig ... end

The 'a array and 'a elt types.

module Unsafe : Internals(Backend).UNSAFE

The internal operations, safely concealed behind an abstract signature!