varray 0.1 · OCaml Package

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!

Parameters

module V : S

Signature

type 'a t

The type of a varray.

type 'a elt = 'a V.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

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

This part can be ignored as it exposes no user-facing functionality!.. but the design pattern is neat. The Root functor requires access to internal operations, that should neither be called nor implemented by a user of this library.

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!

This could not have been written as:

module Unsafe : UNSAFE with type 'a array = 'a array
                        and type 'a elt = 'a elt

Since the signature UNSAFE can't be type constrained without also having all its internal functions be public. The Internals functor circumvent this rule by exposing an opaque signature parametrized by the type constraints.

package varray