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.
Dynamic collection
val push_back : 'a t -> 'a elt -> unit
push_back t x
adds a new elementx
at the end of the varrayt
. O(k) amortized.
val pop_back : 'a t -> 'a elt
pop_back t
removes and returns the rightmost element of the varrayt
. O(k) amortized.
val push_front : 'a t -> 'a elt -> unit
push_front t x
inserts a new elementx
at position0
, on the left side of the varrayt
. Every previous element oft
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 position0
of the varrayt
. Every element oft
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 elementx
at positioni
in the varrayt
. Every element on the right ofi
is shifted by one. O(k² × k√N)insert_at t 0 x
is the same aspush_front t x
insert_at t (length t) x
is the same aspush_back t x
- raises Invalid_arg
if
i
is negative or larger thanlength t
.
val pop_at : 'a t -> int -> 'a elt
pop_at t i
removes and returns the elementt.(i)
. Every element on the right ofi
is shifted by one to the left. O(k² × k√N)pop_at t 0
is the same aspop_front t
pop_at t (length t - 1)
is the same aspop_back t
- raises Invalid_arg
if
i
is negative or larger thanlength t - 1
.
val delete_at : 'a t -> int -> unit
delete_at t i
removes the elementt.(i)
. Every element on the right ofi
is shifted by one to the left. O(k² × k√N)- raises Invalid_arg
if
i
is negative or larger thanlength t - 1
.
Freeze during traversals
val protect : 'a t -> (unit -> 'b) -> 'b
protect t fn
markst
as protected during the execution offn ()
. All operations that would update the length oft
by pushing or poping elements will raise aFailure
indicating that the traversal is unsafe.
Array
val get : 'a t -> int -> 'a elt
get t i
returns thei
th element of the varray. Indexing starts from0
uptolength t - 1
. O(k)- raises Invalid_argument
if
i
is negative or larger thanlength t - 1
.
val set : 'a t -> int -> 'a elt -> unit
set t i v
updates the value of thei
th element tox
. O(k)- raises Invalid_argument
if
i
is negative or larger thanlength t - 1
.
val length : 'a t -> int
length t
returns the number of elements stored int
. O(1)
val make : int -> 'a elt -> 'a t
make n x
returns a new varray of lengthn
, where all the elements are initialized to the valuex
.- raises Invalid_argument
if
n
is negative.
val init : int -> (int -> 'a elt) -> 'a t
init n f
returns a new array of lengthn
, where the element at positioni
is initialized tof i
.- raises Invalid_argument
if
n
is negative.
val empty : unit -> 'a t
empty ()
is a new varray of length0
.
val is_empty : 'a t -> bool
is_empty t
returns true when the varrayt
has length0
.
Copying elements
val append : 'a t -> 'a t -> 'a t
append a b
returns a new varray by concatening the elements ofa
with those ofb
.
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 varraysts
.
val sub : 'a t -> int -> int -> 'a t
sub t i n
returns a new varray of lengthn
, containing the elements from the rangei, i+n-1
of the varrayt
.- raises Invalid_argument
if the range
i, i + n - 1
is invalid fort
.
val fill : 'a t -> int -> int -> 'a elt -> unit
fill t pos len x
modifies the varrayt
in place, by setting the valuex
in the rangepos, 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 varraydst
in place, by copying the rangesrc_pos, src_pos + len - 1
of values fromsrc
into the destination rangedst_pos, dst_pos + len - 1
ofdst
.- 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 functionf
on all elements oft
, from left to right.
val iteri : (int -> 'a elt -> unit) -> 'a t -> unit
iteri f t
callsf i t.(i)
on all the indexesi
oft
, from left to right.
val map : ('a elt -> 'b elt) -> 'a t -> 'b t
map f t
returns a new varray, whose elements aref x
for eachx
from the varrayt
.
val mapi : (int -> 'a elt -> 'b elt) -> 'a t -> 'b t
mapi f t
returns a new varray, whose elements aref i t.(i)
for each indexi
of the varrayt
.
val fold_left : ('a -> 'b elt -> 'a) -> 'a -> 'b t -> 'a
fold_left f z t
computesf (... (f (f z t.(0)) t.(1)) ...) t.(length t - 1)
.
Iterators on two varrays
Predicates
val for_all : ('a elt -> bool) -> 'a t -> bool
for_all f t
holds whenf
is satisfied by all the elements oft
.
val for_all2 : ('a elt -> 'b elt -> bool) -> 'a t -> 'b t -> bool
for_all2 f xs ys
holds whenf xs.(i) ys.(i)
is satisfied by all indexesi
.- raises Invalid_argument
if the two varrays have different lengths.
val exists : ('a elt -> bool) -> 'a t -> bool
exists f t
holds whenf
is satisfied by one of the elements oft
.
val exists2 : ('a elt -> 'b elt -> bool) -> 'a t -> 'b t -> bool
exists2 f xs ys
holds when an indexi
exists such thatf 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 oft
that satisfiesf
.
val find_map : ('a elt -> 'b option) -> 'a t -> 'b option
find_map f t
returns the first result off
of the formSome v
.
Sort
val sort : ('a elt -> 'a elt -> int) -> 'a t -> unit
sort cmp t
updatest
inplace by sorting the elements in increasing order according tocmp
.
Conversions
val of_array : 'a array -> 'a t
of_array arr
returns a new varray containing all the elements of the arrayarr
.
val to_array : 'a t -> 'a array
to_array t
returns a new array containing all the elements of the varrayt
.
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 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 usingArray
as its backend. The resulting varray has parameterk = 1
, meaning thatpush
andpop
at both ends is O(1) but random insertion and deletions are O(N).
module Root : functor (V : S) -> S with type 'a array = 'a V.array and type 'a elt = 'a V.elt
Root (Varray)
nests an existingVarray
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!