package union-find-lattice

  1. Overview
  2. Docs
package union-find-lattice
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module type PersistentArray.SSource

Persistent array implementation. I.E. array which keep track of their history and allow rollback. They appear immutable. This implementation is pretty much exactly the one described by [Cochon and Filliâtre, 2007].

Every array operation get, set, size, diff reroot's the array at the given version. For best performance, avoid jumping between versions too often.

Sourcetype 'a t

The type of persistent arrays

Array creation

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

init n f creates the array [|f 0; f 1; ...; f (n-1)|]. O(n) complexity.

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

make n x creates the array [|x; x; ...; x|] with length n. O(n) complexity.

Sourceval of_array : 'a array -> 'a t

of_array arr creates the persistent array containing the same elements as arr This copies the array, so future modifications to arr will not corrupt the persistent array. O(Array.length arr) complexity.

Sourceval of_list : 'a list -> 'a t

of_list l creates a persistent array with the same elements as l. O(List.length l) complexity.

Array operations

All operations reroot the given array. This is constant time for mutliple accesses to the same version. When switching versions however, the cost is linear in the number of updates (set operations) between both version.

Sourceval size : 'a t -> int

size t is the size (number of elements) of the array t

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

get t i returns the i-th element of the array. O(1) complexity (after reroot).

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

set t i v returns a new array whose values are the same as t except at position i, where the value is v. O(1) complexity (after reroot).

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

pretty ~pp_sep pp_elt t prints the array at t, using pp_elt to print elements and pp_sep to separate them. pp_sep defaults to printing a semicolon and a space).

Sourceval diff : 'a t -> 'a t -> ('a * 'a) IntHashtable.t * 'a t option

diff a b create a table of differences i -> (a.(i), b.(i)) between a and b Requires a and b to share a common root (i.e. derive from the same init or make).

The diff table may include identical values i -> (v,v), these correspond to changes that are reverted on the chain from a to b. For example: let b = set (set a i x) i a.(i).

For performance: have a be the one closest to reroot (i.e. the last modified value).

O(d) complexity (after reroot at a), where d is the number of updates (set operations) between a and b.

Versioned persistent arrays also return the element with the lowest version tag.

Sourceval diff_key : 'a t -> 'a t -> unit IntHashtable.t * 'a t option

diff_key a b is the same as diff a b, but only returns the keys i such that a.(i) and b.(i) may be different.

Versioned persistent arrays also return the element with the lowest version tag.

Array resizing

It is possible to extend persistent arrays (i.e. add elements at the back). These operations retro-actively modify all previous versions. They will all appear as though they always had the new size, so a get old_version i that would have failed before resize will now succeed.

Sourceval append : 'a t -> 'a array -> unit

append t arr extends t by adding the values from arr at the end. This modifies t and all previous versions of t. O(size t + Array.length arr) complexity (after reroot).

Sourceval extend : 'a t -> int -> 'a -> unit

extend t n x extends t by appending n times the value x: [|t.(0); ...; t.(size t - 1); x; ...; x|]. This modifies t and all previous versions of t. O(size t + n) complexity.

  • raises Invalid_argument

    if n is negative or if size t + n > Sys.max_array_length.

Iterators

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

map f t creates a new persistent array, initialized by [|f (get t 0); ...; f (get t (size t) - 1)|]

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

iter f t calls f on every element in order: f (get t 0); ...; f (get t (size t - 1))

Sourceval fold : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc

fold f init t is f (... f init (get t 0) ...) (get t (size t - 1))