hector 20240805 · OCaml Package

This module offers an implementation of vectors. A vector is a mutable data structure, which stores a sequence of values.

type !'a vector

The type of a vector.

type 'a t = 'a vector

A synonym for the type of a vector.

type length = int

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.

type capacity = int

An integer value of type capacity represents the capacity of a vector. A capacity is nonnegative.

type index = int

An integer value of type index represents an index into a sequence of elements.

Creating

val create : unit -> 'a vector

create() creates a new vector of length 0 and capacity 0.

val make : length -> 'a -> 'a vector

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.

val init : length -> (index -> 'a) -> 'a vector

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.

val copy : 'a vector -> 'a vector

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.

val sub : 'a vector -> index -> length -> 'a vector

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.

val concat : 'a vector list -> 'a vector

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.

Reading and writing

val get : 'a vector -> index -> 'a

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

val set : 'a vector -> index -> 'a -> unit

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.

val fill : 'a vector -> index -> length -> 'a -> unit

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.

val blit : 'a vector -> index -> 'a vector -> index -> length -> unit

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 access

val unsafe_get : 'a vector -> index -> 'a

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!

val unsafe_set : 'a vector -> index -> 'a -> unit

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.

Pushing

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.

val push_array_segment : 'a vector -> 'a array -> index -> length -> unit

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.

val append_array_segment : 'a vector -> 'a array -> index -> length -> unit

append_array_segment is a synonym for push_array_segment.

val push_vector : 'a vector -> 'a vector -> unit

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 append : 'a vector -> 'a vector -> unit

append is a synonym for push_vector.

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.

Popping

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.

Iterating

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.

Transforming

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.

val map : ('a -> 'b) -> 'a vector -> 'b vector

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.

val mapi : (index -> 'a -> 'b) -> 'a vector -> 'b vector

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.

val filter : ('a -> bool) -> 'a vector -> 'a vector

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.

val filter_map : ('a -> 'b option) -> 'a vector -> 'b vector

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.

Searching

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.

Comparing and sorting

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.

val equal : ('a -> 'a -> bool) -> 'a vector -> 'a vector -> bool

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.

val compare : ('a -> 'a -> int) -> 'a vector -> 'a vector -> int

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.

Converting

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.

Showing

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.

Length

val length : 'a vector -> length

length v is the (logical) length of the vector v.

val is_empty : 'a vector -> bool

s_empty v is equivalent to length v = 0.

val truncate : 'a vector -> length -> unit

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.

Capacity

val reset : 'a vector -> unit

reset v sets the length and the capacity of the vector v to zero.

val ensure_capacity : 'a vector -> capacity -> unit

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.

val ensure_extra_capacity : 'a vector -> capacity -> unit

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.

val set_capacity : 'a vector -> capacity -> unit

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.

The Stack API

module Stack : sig ... end

This module offers the same API as the standard library module Stdlib.Stack, but is implemented using vectors.

package hector