flex-array 1.1.0 · OCaml Package

Flexible arrays.

Flexible arrays are arrays whose size can be changed by adding or removing elements at either end (one at a time).

This is an implementation of flexible arrays using Braun trees, following

Rob Hoogerwoord A logarithmic implementation of flexible arrays http://alexandria.tue.nl/repository/notdare/772185.pdf

All operations (get, set, cons, tail, snoc, liat) have logarithmic time complexity and logarithmic stack space.

type +'a t

The type of flexible arrays. This is an immutable data structure. Values of type 'a t can be compared using structural equality = (provided the elements of type 'a can).

val empty : 'a t

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

make n v returns a flexible array of size n, initialized with v. All the elements of this new array are physically equal to v (in the sense of the == predicate). Time complexity O(log n).

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

init n f returns a flexible array of size n, with elements f 0, f 1, ..., f (n-1). Time complexity O(n). Caveat: function f is applied only once per index, but not in increasing order of indices.

val of_array : 'a array -> 'a t

of_array a returns a flexible array of size List.length l, with the elements of l in order. Time complexity O(n). Merely a shortcut built over init.

val of_list : 'a list -> 'a t

of_list l returns a flexible array of size List.length l, with the elements of l in order. Time complexity O(n). Logarithmic stack space.

val length : 'a t -> int

Time complexity O(1).

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

get a i returns the element at index i in array a. The first element has index 0. Raises Invalid_argument if i is outside the range 0 to length a - 1.

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

set a i v returns a new array with all elements are identical to those of a, except at index i where the element is v. Raises Invalid_argument if i is outside the range 0 to length a - 1.

val cons : 'a -> 'a t -> 'a t

cons v a returns a new array obtained by appending the value v at the front of array a.

val tail : 'a t -> 'a t

tail a returns a new array obtained by removing the value at the front of array a. Raises Invalid_argument if a has length 0.

val snoc : 'a t -> 'a -> 'a t

snoc v a returns a new array obtained by appending the value v at the end of array a.

val liat : 'a t -> 'a t

liat a returns a new array obtained by removing the value at the end of array a. Raises Invalid_argument if a has length 0.

Iterators

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

iter f a applies function f in turn to all the elements of a. It is equivalent to f (get a 0); f (get a 1); ...; f (get a (n - 1); () where n is the length of the array a, but runs faster. Time complexity O(n). Space complexity O(n). Constant stack space.

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

Same as iter, but the function is applied with the index of the element as first argument, and the element itself as second argument.

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

fold f x a computes f (... (f (f x (get a 0)) (get a 1)) ...) (get a (n-1)), where n is the length of the array a, but runs faster. Time complexity O(n). Space complexity O(n). Constant stack space.

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

Same as fold, but the function is applied with the index of the element as second argument.

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

map f a returns a new flexible array with elements f (get a 0), ..., f (get a (n-1) where n is the length of a.

package flex-array

Iterators