package flex-array

  1. Overview
  2. Docs
On This Page
  1. Iterators
package flex-array
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Flex_arraySource

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.

Sourcetype +'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).

Sourceval empty : 'a t
Sourceval 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).

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval length : 'a t -> int

Time complexity O(1).

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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. Time complexity O(n). Logarithmic stack space.

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

mapi f a returns a new flexible array with elements f 0 (get a 0), ..., f (n-1) (get a (n-1) where n is the length of a. Time complexity O(n). Logarithmic stack space.

Sourceval pp : ?pp_sep:(Format.formatter -> unit -> unit) -> (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit

pp ?pp_sep pp_v fmt a prints items of flexible array a using pp_v to print each item, and calling pp_sep between items (pp_sep defaults to Format.pp_print_cut. Does nothing on empty flexible arrays.)

  • since 1.2.0