Module Batteries.Vect

module Vect: BatVect

type 'a t

The type of a polymorphic vect.

exception Out_of_bounds

Raised when an operation violates the bounds of the vect.

val max_length : int

Maximum length of the vect.

Creation and conversions

val empty : 'a t

The empty vect.

val singleton : 'a -> 'a t

Returns a vect of length 1 holding only the given element.

val of_array : 'a array -> 'a t

of_array s returns a vect corresponding to the array s. Operates in O(n) time.

val to_array : 'a t -> 'a array

to_array r returns an array corresponding to the vect r.

val to_list : 'a t -> 'a list

Returns a list with the elements contained in the vect.

val of_list : 'a list -> 'a t

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

make i c returns a vect of length i whose elements are all equal to c; it is similar to Array.make

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

init n f returns a fresh vect of length n, with element number i initialized to the result of f i. In other terms, init n f tabulates the results of f applied to the integers 0 to n-1.

Raises Invalid_argument if n < 0 or n > max_length.

Properties

val is_empty : 'a t -> bool

Returns whether the vect is empty or not.

val height : 'a t -> int

Returns the height (depth) of the vect.

val length : 'a t -> int

Returns the length of the vect (O(1)).

Operations

val balance : 'a t -> 'a t

balance r returns a balanced copy of the r vect. Note that vects are automatically rebalanced when their height exceeds a given threshold, but balance allows to invoke that operation explicitly.

val concat : 'a t -> 'a t -> 'a t

concat r u concatenates the r and u vects. In general, it operates in O(log(min n1 n2)) amortized time. Small vects are treated specially and can be appended/prepended in amortized O(1) time.

val append : 'a -> 'a t -> 'a t

append c r returns a new vect with the c element at the end in amortized O(1) time.

val prepend : 'a -> 'a t -> 'a t

prepend c r returns a new vect with the c character at the beginning in amortized O(1) time.

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

get v n returns the (n+1)th element from the vect v; i.e. get v 0 returns the first element. Operates in worst-case O(log size) time.

Raises Out_of_bounds if a character out of bounds is requested.

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

as get

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

set v n c returns a copy of the v vect where the (n+1)th element (see also get) has been set to c. Operates in worst-case O(log size) time.

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

modify v n f is equivalent to set v n (f (get v n)), but more efficient. Operates in worst-case O(log size) time.

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

destructive_set v n c sets the element of index n in the v vect to c. This operation is destructive, and will also affect vects sharing the modified leaf with v. Use with caution.

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

sub m n r returns a sub-vect of r containing all the elements whose indexes range from m to m + n - 1 (included).

Raises Out_of_bounds in the same cases as Array.sub. Operates in worst-case O(log size) time.

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

insert n r u returns a copy of the u vect where r has been inserted between the elements with index n - 1 and n in the original vect; after insertion, the first element of r (if any) is at index n. The length of the new vect is length u + length r. Operates in amortized O(log(size r) + log(size u)) time.

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

remove m n r returns the vect resulting from deleting the elements with indexes ranging from m to m + n - 1 (included) from the original vect r. The length of the new vect is length r - n. Operates in amortized O(log(size r)) time.

Conversion

val enum : 'a t -> 'a BatEnum.t

Returns an enumeration of the elements of the vector. Behavior of the enumeration is undefined if the contents of the vector changes afterwards.

val of_enum : 'a BatEnum.t -> 'a t

Build a vector from an enumeration.

val backwards : 'a t -> 'a BatEnum.t

Returns an enumeration of the elements of a vector, from last to first. Behavior of the enumeration is undefined if the contents of the vector changes afterwards.

val of_backwards : 'a BatEnum.t -> 'a t

Build a vector from an enumeration, from last to first.

Iteration and higher-order functions

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

iter f r applies f to all the elements in the r vect, in order.

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

Operates like iter, but also passes the index of the character to the given function.

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

rangeiter f m n r applies f to all the elements whose indices k satisfy m <= k < m + n. It is thus equivalent to iter f (sub m n r), but does not create an intermediary vect. rangeiter operates in worst-case O(n + log m) time, which improves on the O(n log m) bound from an explicit loop using get.

Raises Out_of_bounds in the same cases as sub.

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

fold_left f a r computes f (... (f (f a r0) r1)...) rN-1 where rn = Vect.get n r and N = length r.

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

An alias for BatVect.fold_left

val reduce : ('a -> 'a -> 'a) -> 'a t -> 'a

as BatVect.fold_left, but no initial value - just applies reducing function to elements from left to right.

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

fold_right f r a computes f (r0 ... (f rN-2 (f rN-1 a)) ...)) where rn = Vect.get n r and N = length r.

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

As BatVect.fold, but with the position of each value passed to the folding function

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

map f v returns a vect isomorphic to v where each element of index i equals f (get v i). Therefore, the height of the returned vect is the same as that of the original one. Operates in O(n) time.

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

Same as BatVect.map, but the function is applied to the index of the element as first argument, and the element itself as second argument.

Predicates

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

for_all p [a0; a1; ...; an] checks if all elements of the vect satisfy the predicate p. That is, it returns (p a0) && (p a1) && ... && (p an).

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

exists p [a0; a1; ...; an] checks if at least one element of the vect satisfies the predicate p. That is, it returns (p a0) || (p a1) || ... || (p an).

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

find p v returns the first element of vect v that satisfies the predicate p.

Raises Not_found if there is no value that satisfies p in the vect v.

val find_opt : ('a -> bool) -> 'a t -> 'a option

find_opt p v returns Some a, where a is the first element of vect v that satisfies the predicate p, or None if no such element exists.

Since 2.7.0

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

mem a v is true if and only if a is equal to an element of v.

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

Same as Vect.mem but uses physical equality instead of structural equality to compare vect elements.

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

findi p v returns the index of the first element of vect v that satisfies the predicate p.

Raises Not_found if there is no value that satisfies p in the vect v.

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

filter f v returns a vect with the elements a from v such that f a returns true. Operates in O(n) time.

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

filter_map f v returns a vect consisting of all elements b such that f a returns Some b , where a is an element of v.

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

find_all is another name for Vect.filter.

val partition : ('a -> bool) -> 'a t -> 'a t * 'a t

partition p v returns a pair of vects (v1, v2), where v1 is the vect of all the elements of v that satisfy the predicate p, and v2 is the vect of all the elements of v that do not satisfy p. The order of the elements in the input vect is preserved.

Convenience Functions

val first : 'a t -> 'a

val last : 'a t -> 'a

These return the first and last values in the vector

val shift : 'a t -> 'a * 'a t

Return the first element of a vector and its last n-1 elements.

val pop : 'a t -> 'a * 'a t

Return the last element of a vector and its first n-1 elements.

Boilerplate code

val print : ?first:string ->
       ?last:string ->
       ?sep:string ->
       ('a BatInnerIO.output -> 'b -> unit) ->
       'a BatInnerIO.output -> 'b t -> unit

val compare : 'a BatOrd.comp -> 'a t BatOrd.comp

val equal : 'a BatOrd.eq -> 'a t BatOrd.eq

val ord : 'a BatOrd.ord -> 'a t BatOrd.ord

Override modules

module Labels: sig .. end

Operations on BatVect with labels.

Functorial interface

module type RANDOMACCESS = sig .. end

module Make: functor (R : RANDOMACCESS) -> functor (PARAM : sig

val max_height : int

val leaf_size : int

end) -> sig .. end