Hector.Poly
This module offers an implementation of vectors. A vector is a mutable data structure, which stores a sequence of values.
type 'a t = 'a vector
A synonym for the type of a vector.
An integer value of type length
represents the length of a sequence. For example, it can be the length of an array, the length of a vector, or the length of a segment of an array of vector. A length is nonnegative.
An integer value of type capacity
represents the capacity of a vector. A capacity is nonnegative.
val create : unit -> 'a vector
create()
creates a new vector of length 0 and capacity 0.
make n x
creates a new vector of length n
and capacity n
and initializes this vector by storing the value x
everywhere. n
must be a valid capacity.
init n f
creates a new vector of length n
and capacity n
and initializes it, from left to right, by computing and storing the value f i
at index i
. n
must be a valid capacity.
copy v
creates a new vector whose length and capacity are length v
and initializes it with a copy of the data stored in the vector v
.
sub v i n
produces a new vector whose elements are the elements of the vector segment determined by vector v
, index i
, and length n
. i
and n
must describe a valid segment of the vector v
.
concat vs
produces a new vector whose sequence of elements is the concatenation of the sequences of elements of the vectors in the list vs
.
get v i
fetches the element that lies at index i
in the vector v
. i
must be comprised in the semi-open interval [0, length v)
.
set v i x
overwrites the element that lies at index i
in the vector v
with the value x
. i
must be comprised in the semi-open interval [0, length v)
.
val top : 'a vector -> 'a
If the vector v
is nonempty, top v
returns its last element. If the vector v
is empty, top v
raises Not_found
.
val get_last : 'a vector -> 'a
get_last
is a synonym for top
.
val top_opt : 'a vector -> 'a option
If the vector v
is nonempty, top_opt v
returns its last element. If the vector v
is empty, top_opt v
returns None
.
val find_last : 'a vector -> 'a option
find_last
is a synonym for top_opt
.
fill v i n x
writes the value x
into every slot of the vector segment determined by vector v
, index i
, and length n
. i
and n
must describe a valid segment of the vector v
.
blit v i v' i' n
copies data from the vector segment determined by vector v
, index i
, and length n
into the vector segment determined by vector v'
, index i'
, and length n
. It works correctly even if the source and destination segments overlap. i
and n
must describe a valid segment of the vector v
. i'
and n
must describe a valid segment of the vector v'
.
unsafe_get v i
fetches the element that lies at index i
in the vector v
. i
must be comprised in the semi-open interval [0, length v)
. No bounds check is performed. If the index i
is out of bounds, memory safety can be compromised. Use at your own risk!
unsafe_set v i x
overwrites the element that lies at index i
in the vector v
with the value x
. i
must be comprised in the semi-open interval [0, length v)
. No bounds check is performed. If the index i
is out of bounds, memory safety can be compromised. Use at your own risk!
val unsafe_borrow : 'a vector -> 'a array
unsafe_borrow v
returns the data array that is part of the internal representation of the vector v
. The length of this data array is at least length v
, and can be greater than length v
. Beyond this guarantee, the length of this data array is unspecified; it is not necessarily the capacity of the vector. As long as the vector v
is not modified by other means, the segment of the data array delimited by the semi-open interval [0, length v)
can be safely read and written.
val push : 'a vector -> 'a -> unit
push v x
extends the vector v
with the element x
. The length of the vector v
is increased by one. If necessary, the capacity of the vector v
is increased.
val add_last : 'a vector -> 'a -> unit
add_last
is a synonym for push
.
val push_array : 'a vector -> 'a array -> unit
push_array v a
extends the vector v
with the elements of the array a
. The length of the vector v
is increased by the length of the array a
. If necessary, the capacity of the vector v
is increased.
val append_array : 'a vector -> 'a array -> unit
append_array
is a synonym for push_array
.
push_array_segment v a i n
extends the vector v
with the elements of the array segment determined by array a
, index i
, and length n
. The length of the vector v
is increased by n
. If necessary, the capacity of the vector v
is increased. i
and n
must describe a valid segment of the array a
.
append_array_segment
is a synonym for push_array_segment
.
push_vector v v'
extends the vector v
with the elements of the vector v'
. The length of the vector v
is increased by the length of the array v'
. If necessary, the capacity of the vector v
is increased.
val push_list : 'a vector -> 'a list -> unit
push_list v xs
extends the vector v
with the elements of the list xs
. The length of the vector v
is increased by the length of the list xs
. If necessary, the capacity of the vector v
is increased.
val append_list : 'a vector -> 'a list -> unit
append_list
is a synonym for push_list
.
val push_seq : 'a vector -> 'a Seq.t -> unit
push_seq v xs
extends the vector v
with the elements of the sequence xs
. The length of the vector v
is increased by the length of the sequence xs
. If necessary, the capacity of the vector v
is increased. The sequence xs
is demanded just once.
val append_seq : 'a vector -> 'a Seq.t -> unit
append_seq
is a synonym for push_seq
.
val push_iter : 'a vector -> (('a -> unit) -> 'c -> unit) -> 'c -> unit
push_iter v iter c
pushes each element of the collection c
in turn onto the vector v
. The function iter
is used to iterate over the elements of c
. In other words, push_iter v iter c
is equivalent to iter (push v) c
.
val append_iter : 'a vector -> (('a -> unit) -> 'c -> unit) -> 'c -> unit
append_iter
is a synonym for push_iter
.
val pop : 'a vector -> 'a
If the vector v
is nonempty, pop v
removes and returns its last element. The length of the vector is decreased by one; its capacity is unchanged. If the vector v
is empty, pop v
raises Not_found
.
val pop_last : 'a vector -> 'a
pop_last
is a synonym for pop
.
val pop_opt : 'a vector -> 'a option
If the vector v
is nonempty, pop_opt v
removes and returns its last element. The length of the vector is decreased by one; its capacity is unchanged. If the vector v
is empty, pop_opt v
returns None
.
val pop_last_opt : 'a vector -> 'a option
pop_last_opt
is a synonym for pop_opt
.
val drop : 'a vector -> unit
If the vector v
is nonempty, drop v
removes its last element. If the vector v
is empty, drop v
has no effect. drop v
is equivalent to if is_empty v then () else ignore (pop v)
.
val remove_last : 'a vector -> unit
remove_last
is a synonym for drop
.
While iteration is ongoing, the vector must not be modified. For example, in iter f v
, the function f
is not allowed to modify the vector v
. This rule applies to all iteration functions.
val iter : ('a -> unit) -> 'a vector -> unit
iter f v
applies the function f
in turn, from left to right, to each element x
of the vector v
.
val iter_down : ('a -> unit) -> 'a vector -> unit
iter_down f v
applies the function f
in turn, from right to left, to each element x
of the vector v
.
val iteri : (int -> 'a -> unit) -> 'a vector -> unit
iteri f v
applies the function f
in turn, from left to right, to each index i
and corresponding element x
of the vector v
.
val fold_left : ('s -> 'a -> 's) -> 's -> 'a vector -> 's
fold_left f s v
applies the function f
in turn, from left to right, to each element x
of the vector v
. A state, whose initial value is s
, is threaded through this sequence of function invocations, and is eventually returned.
val fold_right : ('a -> 's -> 's) -> 'a vector -> 's -> 's
fold_right f v s
applies the function f
in turn, from right to left, to each element x
of the vector v
. A state, whose initial value is s
, is threaded through this sequence of function invocations, and is eventually returned.
While transformation is ongoing, the vector must not be modified. For example, in map f v
, the function f
is not allowed to modify the vector v
. This rule applies to all transformation functions.
map f v
applies the function f
in turn, from left to right, to each element x
of the vector v
, and constructs a new vector of the results of these calls.
mapi f v
applies the function f
in turn, from left to right, to each index i
and corresponding element x
of the vector v
, and constructs a new vector of the results of these calls.
filter f v
applies the function f
in turn, from left to right, to each element x
of the vector v
, and constructs a new vector containing just the elements x
such that f x
returned true
.
filter_map f v
applies the function f
in turn, from left to right, to each element x
of the vector v
, and constructs a new vector containing just the values y
such that f x
returned Some y
.
While searching is in progress, the vector must not be modified. For example, in exists f v
, the function f
is not allowed to modify the vector v
. This rule applies to all search functions.
val exists : ('a -> bool) -> 'a vector -> bool
exists f v
determines whether at least one element x
of the vector v
satisfies the predicate f
. The vector is scanned from left to right.
val for_all : ('a -> bool) -> 'a vector -> bool
for_all f v
determines whether all elements x
of the vector v
satisfy the predicate f
. The vector is scanned from left to right.
val find : ('a -> bool) -> 'a vector -> int
find f v
finds the leftmost element x
of the vector v
such that f x
is true, and returns its index. If no such element exists, then find f v
raises Not_found
.
While comparison is in progress, the vector must not be modified. For example, in equal eq v v'
, the function eq
is not allowed to modify the vector v
. This rule applies to all comparison functions.
Provided eq
is an equality on elements, equal eq
is the pointwise equality of vectors. In other words, equal eq v v'
determines whether the sequences of elements of the vectors v
and v'
are pointwise equal, using the function eq
to test whether two elements are equal.
Provided cmp
is a preorder on elements, compare cmp
is the lexicographic preorder on vectors. In other words, compare cmp v v'
compares the sequences of elements of the vectors v
and v'
, according to the lexicographic preorder, and using the function cmp
to compare two elements.
Caution: compare
behaves like List.compare
, not like Dynarray.compare
. Dynarray.compare
implements a preorder on vectors that is not is the lexicographic preorder.
val sort : ('a -> 'a -> int) -> 'a vector -> unit
sort cmp v
sorts the vector v
, in place, according to the preorder cmp
.
sort
is currently a synonym for stable_sort
.
val stable_sort : ('a -> 'a -> int) -> 'a vector -> unit
stable_sort cmp v
sorts the vector v
, in place, according to the preorder cmp
. This is a stable sort: if two elements are equivalent according to cmp
then their relative order in the sequence is preserved. This is a merge sort algorithm; it is the same algorithm as in Array.stable_sort
.
val fast_sort : ('a -> 'a -> int) -> 'a vector -> unit
fast_sort cmp v
sorts the vector v
, in place, according to the preorder cmp
.
fast_sort
is currently a synonym for stable_sort
.
val of_array : 'a array -> 'a vector
of_array a
returns a new vector whose elements are the elements of the array a
. The length and capacity of the new vector are the length of the array a
.
val of_list : 'a list -> 'a vector
of_list xs
returns a new vector whose elements are the elements of the list xs
. The length and capacity of the new vector are the length of the list xs
.
val of_seq : 'a Seq.t -> 'a vector
of_seq xs
returns a new vector whose elements are the elements of the sequence xs
. The length and capacity of the new vector are the length of the sequence xs
.
val to_array : 'a vector -> 'a array
to_array v
creates a new array whose elements are the elements of the vector v
. The length of the new array is the length of the vector v
.
val to_list : 'a vector -> 'a list
to_list v
creates a new list whose elements are the elements of the vector v
. The length of the new list is the length of the vector v
.
val to_seq : 'a vector -> 'a Seq.t
to_seq v
creates a sequence whose elements are the elements of the vector v
. The length of this sequence is the length of the vector v
. This sequence can be demanded as many times as one wishes. However, this sequence is valid only as long as the vector v
is not modified. As soon as v
is modified, this sequence must no longer be used.
val to_seq_rev : 'a vector -> 'a Seq.t
to_seq_rev v
creates a sequence whose elements are the elements of the vector v
, in reverse order. The length of this sequence is the length of the vector v
. This sequence can be demanded as many times as one wishes. However, this sequence is valid only as long as the vector v
is not modified. As soon as v
is modified, this sequence must no longer be used.
val show : ('a -> string) -> 'a vector -> string
show f v
returns a textual representation of the contents of the vector v
. The user-supplied function f
is used to obtain a textual representation of each element.
val is_empty : 'a vector -> bool
s_empty v
is equivalent to length v = 0
.
If n
is less than length v
, then truncate v n
sets the length of the vector v
to n
. Otherwise, nothing happens. In either case, the capacity of the vector v
is unchanged. This is a constant-time operation.
val clear : 'a vector -> unit
clear v
is equivalent to truncate v 0
. The length of the vector v
becomes zero. Its capacity is unchanged.
val reset : 'a vector -> unit
reset v
sets the length and the capacity of the vector v
to zero.
ensure_capacity v c
ensures that the capacity of the vector v
is at least c
. If necessary, the capacity of the vector v
is increased.
ensure_extra_capacity v delta
ensures that the capacity of the vector v
is at least length v + delta
. If necessary, the capacity of the vector v
is increased. The increment delta
must be nonnegative.
val fit_capacity : 'a vector -> unit
fit_capacity v
ensures that the capacity of the vector v
matches its length. If necessary, the capacity of the vector v
is decreased.
set_capacity v c
ensures that the capacity of the vector v
is exactly c
. If c
is less than length v
, then the vector v
is truncated: some elements are lost. Otherwise, the elements of the vector v
are preserved, and its capacity is decreased or increased as necessary.
module Stack : sig ... end
This module offers the same API as the standard library module Stdlib.Stack
, but is implemented using vectors.