module Make: functor (R : RANDOMACCESS) -> functor (PARAM : sigval max_height : int
val leaf_size : int
end) -> sig .. end
| Parameters: |
R |
: |
RANDOMACCESS
|
PARAM |
: |
sig val max_height : int val leaf_size : int end
|
|
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_container : 'a R.t -> 'a t
of_array s returns a vect corresponding to the container s.
Operates in O(n) time.
val to_container : 'a t -> 'a R.t
to_container r returns a container corresponding to the vect r.
val to_list : 'a t -> 'a list
Returns a list with the elements contained in the vect.
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
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)).
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 explicity.
Operations
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 : int -> 'a t -> 'a
get n r returns the (n+1)th element from the vect r; i.e.
get 0 r 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 set : 'a t -> int -> 'a -> 'a t
set r n c returns a copy of the r vect where the (n+1)th element
(see also get) has been set to c.
Operates in worst-case O(log size) time.
val sub : int -> int -> 'a t -> '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 and n + 1 in the
original vect. 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.
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 : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
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 : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
as fold_left
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 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 map, but the
function is applied to the index of the element as first argument,
and the element itself as second argument.
val filter : ('a -> bool) -> 'a t -> 'a t
filter f v returns a vect with the elements x from v such that
f x returns true. Operates in O(n) time.
val filter_map : ('a -> 'b option) -> 'a t -> 'b t
filter_map f e returns a vect consisting in all elements
x such that f y returns Some x , where y is an element
of e.
val find_all : ('a -> bool) -> 'a t -> 'a t
find_all is another name for Array.filter.
val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
partition p a returns a pair of arrays (a1, a2), where
a1 is the array of all the elements of a that
satisfy the predicate p, and a2 is the array of all the
elements of a that do not satisfy p.
The order of the elements in the input array is preserved.
val print : ?first:string ->
?last:string ->
?sep:string ->
('a BatInnerIO.output -> 'b -> unit) ->
'a BatInnerIO.output -> 'b t -> unit