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 : int -> 'a -> 'a t -> 'a t
set n c r 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_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 id_map : ('a -> 'a) -> 'a t -> 'a t
id_map f v returns a vect isomorphic to v where each element of index
i equals f (get v i). It is very similar to map, but tries to share
as much data as possible with the original vect; for example,
id_map (fun x -> x) v == v. This can lead to significative space savings
if f leaves many values unmodified.
For each element, the new value f x and the old one x are compared
with <>. Operates in O(n) time.
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.