Module Vec

module Vec: sig .. end

Dynamically resizable arrays.

type 'a t

Resizable vector of 'a elements.

Construction and Extraction

val limit_for : 'a -> int

limit_for x is the maximum number of elements of the same type as x that may be stored in a vector.

Ensure 0 < limit_for x

val make : int -> 'a -> 'a t

make n x is a vector of length n, with each element equal to x.
Raises Invalid_argument "exceeds limit" if n > Vec.limit_for x

Require n >= 0

val create : int -> 'a -> 'a t

Synonym for Vec.make.

val init : int -> (int -> 'a) -> 'a t

init n f is a vector with length n. Element i is f i.
Raises Invalid_argument "exceeds limit" if n > Vec.limit_for x

Require n >= 0

val copy : 'a t -> 'a t

copy v is a copy of v; the elements are shared by v and the copy.

val to_list : 'a t -> 'a list

to_list v is a list of the elements of v in their positional order.

val of_list : 'a list -> 'a t

of_list l is a vector of the elements of l in their positional order.
Raises Invalid_argument "exceeds limit" if length l >Vec.limit_for x

Require not (l = [])

val to_array : 'a t -> 'a array

to_array v is an array with the elements of v.

val of_array : 'a array -> 'a t

of_array a is a vector with the elements of a.

Require Array.size a > 0

Size

val length : 'a t -> int

length v is the number of elements in v.

Ensure 0 <= Vec.length v <= Vec.limit v

val limit : 'a t -> int

Maximum number of elements possible in this vector.

Ensure 0 <= Vec.length v <= Vec.limit v

val is_empty : 'a t -> bool

is_empty v holds if and only if Vec.length v = 0.

val grow : 'a t -> int -> 'a -> unit

grow v n x grows the size of v to n, filling in the newly created slots with x.
Raises Invalid_argument "exceeds limit" if n > Vec.limitv

Require n > Vec.length v

val grow_init : 'a t -> int -> (int -> 'a) -> unit

grow_init v n f grows the size of v to n, filling in each newly created slots i with f i.
Raises Invalid_argument "exceeds limit" if n > Vec.limitv

Require n > Vec.length v

val shrink : 'a t -> int -> unit

shrink v n shrinks the size of v to n. Takes time linear in proportion with Vec.length v - n.

Require 0 <= n <= Vec.length v

val clear : 'a t -> unit

clear v removes all elements from v. Takes time linear in proportion with Vec.length v.

clear is a synonym for Vec.shrink 0.

Access

val get : 'a t -> int -> 'a

get v i is the ith element v.

Require 0 <= i < Vec.length v

val set : 'a t -> int -> 'a -> unit

set v i x stores x as element i of v.

Require 0 <= i < Vec.length v

val set_all : 'a t -> int -> int -> 'a -> unit

set_all v i j x stores x in elements i...j-1 of v.

Require 0 <= i <= j <= Vec.length v

val push : 'a t -> 'a -> unit

push v x extends the length of the v by 1. The new last element is x.
Raises Invalid_argument "exceeds limit" if length l =Vec.limit v

val pop : 'a t -> 'a

pop v removes the last element of v.
Returns prior last element of v

Require not ( Vec.is_empty v)

val top : 'a t -> 'a

top v is the last element of v.

Require not ( Vec.is_empty v)

val insert : 'a t -> int -> 'a -> unit

insert v i x inserts x into position i of v, pushing elements at position i and above up by 1. The length v increases by 1.
Raises Invalid_argument "exceeds limit" if length l =Vec.limit v

Require 0 <= i <= Vec.length v
Takes time proportionate to Vec.length v - i + 1

val delete : 'a t -> int -> unit

delete v i removes the element at position i of v, pulling elements above down by 1. The length of v decreases by 1. Vec.swap_out v i is faster if you do not need to preserve the order of the elements.

Require 0 <= i < Vec.length v
Takes time proportionate to Vec.length v - n

val swap : 'a t -> int -> int -> unit

swap v i j swaps the elements at positions i and j of v.

Require 0 <= i && i < Vec.length v
Require 0 <= j && j < Vec.length v
Takes constant time.

val swap_out : 'a t -> int -> unit

swap_out v i replaces the element at position i of v with the last element of v, and decreases the length of v by 1. This is faster than Vec.delete v i if you do not need to preserve the order of the elements.

Require 0 <= i && i < Vec.length v
Takes constant time.

Iteration

val rev : 'a t -> unit

rev v reverses the order of elements in v.

val iter : ('a -> unit) -> 'a t -> unit

iter c v evaluates c on each element of v. It is equivalent to c (get v 0); ...; c (get v (length v - 1).

val iter_const : ('a -> 'b -> unit) -> 'a -> 'b t -> unit

iter_const c x v is Vec.iter (c x) v, only faster since applying closures is slow.

val iteri : (int -> 'a -> unit) -> 'a t -> unit

Like Vec.iter, but the command takes the index of the element as the first argument

val iteri_const : ('a -> int -> 'b -> unit) -> 'a -> 'b t -> unit

iteri_const c x v is Vec.iteri (c x) v, only faster since applying closures is slow.

val modify : ('a -> 'a) -> 'a t -> unit

modify f v replaces each element of v with f of that element.

val modify_const : ('a -> 'b -> 'b) -> 'a -> 'b t -> unit

modify_const f x v is Vec.modify (f x) v, only faster since applying closures is slow.

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

fold_left f l v computes f (... (f (f l (Vec.get

 v i))
      (

Vec.get v (i+1)) ...) (Vec.get v (Vec.length v - 1)).

val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b

fold_right f v r computes f (Vec.get

 v i) (... (f
      (

Vec.get v (j-2)) (f (Vec.get v (Vec.length

 v -
      1)) r)) ...)

val foldi_left : ('a -> int -> 'b -> 'a) -> 'a -> 'b t -> 'a

fold_lefti f l v computes f (... (f (f l i (Vec.get

 v
      i)) (i+1) (

Vec.get v (i+1))) ...) (j-1) (Vec.get

 v
      (

Vec.length v - 1)).

val foldi_right : (int -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

foldi_right f v r computes f i (Vec.get

 v i) (... (f
      (j-2) (

Vec.get v (j-2)) (f (j-1) (Vec.get

 v
      (

Vec.length v - 1)) r)) ...)

val fold_left_const : ('a -> 'b -> 'c -> 'b) -> 'a -> 'b -> 'c t -> 'b

fold_left_const f x l v is Vec.fold_left (f x) l v, only faster since applying closures is slow.

val fold_right_const : ('a -> 'b -> 'c -> 'c) -> 'a -> 'b t -> 'c -> 'c

fold_right_const f x v r is Vec.fold_right (f x) v r, only faster since applying closures is slow.

val foldi_left_const : ('a -> 'b -> int -> 'c -> 'b) -> 'a -> 'b -> 'c t -> 'b

fold_lefti f x l v is Vec.foldi_left (f x) l v, only faster since applying closures is slow.

val foldi_right_const : ('a -> int -> 'b -> 'c -> 'c) -> 'a -> 'b t -> 'c -> 'c

foldi_right_const f x v r is Vec.foldi_right (f x) v r, only faster since applying closures is slow.

Scanning

val mem : 'a -> 'a t -> bool

mem x v holds if x is an element of v.

val exists : ('a -> bool) -> 'a t -> bool

exists p v holds if some element of v satisfies p.

Note result is false if Vec.is_empty v.

val exists_const : ('a -> 'b -> bool) -> 'a -> 'b t -> bool

exists p x v is Vec.exists (p x) v, but faster since applying closures is slow.

val for_all : ('a -> bool) -> 'a t -> bool

all p v holds if every element of v satisfies p.

Note result is true if Vec.is_empty v.

val for_all_const : ('a -> 'b -> bool) -> 'a -> 'b t -> bool

for_all_const p x v is Vec.for_all (p x) v, but faster since applying closures is slow.

Searching

val find : ('a -> bool) -> 'a t -> 'a

find p v is the first element of v satisfying p.
Raises Not_found if no element of v satisfies p

val find_const : ('a -> 'b -> bool) -> 'a -> 'b t -> 'b

find_const p x v is Vec.find (p x) v, but faster since applying closures is slow.

val first : ('a -> bool) -> 'a t -> int

first p v is the index of the first element of v satisfying p.
Raises Not_found if no element of v satisfies p

val first_const : ('a -> 'b -> bool) -> 'a -> 'b t -> int

first_const p x v is Vec.first (p x) v, but faster since applying closures is slow.

val filter : ('a -> bool) -> 'a t -> unit

filter p v removes those elements of v not satisfying p

val filter_const : ('a -> 'b -> bool) -> 'a -> 'b t -> unit

filter_const p x v is Vec.filter (p x) v, only faster since applying closures is slow.

val filteri : (int -> 'a -> bool) -> 'a t -> unit

Like Vec.filter, but the predicate takes the index of the element as the first argument.

val filteri_const : ('a -> int -> 'b -> bool) -> 'a -> 'b t -> unit

filteri_const p x v is Vec.filteri (p x) v, only faster since applying closures is slow.

val fast_filter : ('a -> bool) -> 'a t -> unit

Like Vec.filter, but does not preserve the order of elements.

val fast_filter_const : ('a -> 'b -> bool) -> 'a -> 'b t -> unit

fast_filter_const p x v is Vec.fast_filter (p x) v, only faster since applying closures is slow.

Sorting

val sort : ('a -> 'a -> int) -> 'a t -> unit

sort c v sorts elements of v in ascending order as defined by the comparison function c. c x y returns a negative number if x comes before y, a positive number if x comes after y and zero if x and y are order equivalent.

val stable_sort : ('a -> 'a -> int) -> 'a t -> unit

stable_sort c v sorts elements of v in ascending order as defined by the comparison function c. c x y returns a negative number if x comes before y, a positive number if x comes after y and zero if x and y are order equivalent.

The sort is stable in that adjacent order equivalent elements remain in their original order.

Hosted by the

^* web site.
^*Other names and brands may be claimed as the property of others.