package grenier

  1. Overview
  2. Docs

Module Maxtrie.PatMapSharingSource

Immutable maps whose keys are non-negative integers.

Maps use the representation of PatSet, with one binding per node instead of a bitmap: Patricia tries in which every node hoists the largest key of its subtree. A map with n bindings has exactly n nodes, there are no internal branching nodes, and the depth of a tree is bounded by the number of bits of an integer. The binding with the largest key is at the root.

Keys must be non-negative: add, singleton, and update raise Invalid_argument on a negative key; the other operations treat negative keys as absent.

This is PatMap with mutable children (for Sharing): 'a t is invariant.

The interface follows Stdlib.Map.S. Functions that take a key-dependent function apply it in increasing order of keys.

Sourcetype key = int
Sourcetype 'a t

The type of maps from key to 'a.

Construction

Sourceval empty : 'a t
Sourceval singleton : key -> 'a -> 'a t
Sourceval add : key -> 'a -> 'a t -> 'a t

add k v m binds k to v. If k is already bound to a value that is physically equal to v, then m itself is returned.

Sourceval update : key -> ('a option -> 'a option) -> 'a t -> 'a t

update k f m binds k according to f, which receives the current binding of k, if any. If f returns its argument (or None when there was no binding), then m itself is returned.

Sourceval remove : key -> 'a t -> 'a t

remove k m removes the binding of k. If k is not bound, then m itself is returned.

Sourceval union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t

union f m1 m2 has the bindings of m1 and m2. When a key k is bound in both, to v1 and v2, f k v1 v2 decides: None drops the key, Some v binds it to v. If the result has the same keys as m2 and physically equal values, then m2 itself is returned.

Sourceval inter : (key -> 'a -> 'b -> 'c option) -> 'a t -> 'b t -> 'c t

inter f m1 m2 has the keys bound in both m1 and m2; for each such key k, bound to v1 and v2, f k v1 v2 decides the binding.

Sourceval diff : 'a t -> 'b t -> 'a t

diff m1 m2 is m1 deprived of the keys bound in m2. If no key is removed, then m1 itself is returned.

Sourceval filter : (key -> 'a -> bool) -> 'a t -> 'a t

filter p m has the bindings of m that satisfy p. If all of them do, then m itself is returned.

Sourceval filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t
Sourceval partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
Sourceval map : ('a -> 'b) -> 'a t -> 'b t
Sourceval mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
Sourceval split : key -> 'a t -> 'a t * 'a option * 'a t

split k m is (l, data, r) where l has the bindings of m whose keys are less than k, r those whose keys are greater than k, and data is the binding of k, if any.

Sourceval of_list : (key * 'a) list -> 'a t
Sourceval of_seq : (key * 'a) Seq.t -> 'a t
Sourceval add_seq : (key * 'a) Seq.t -> 'a t -> 'a t

Queries

Sourceval is_empty : 'a t -> bool

is_empty m determines whether m is empty. Constant time.

Sourceval is_singleton : 'a t -> bool

is_singleton m determines whether m has exactly one binding. Constant time.

Sourceval cardinal : 'a t -> int
Sourceval mem : key -> 'a t -> bool
Sourceval find : key -> 'a t -> 'a
Sourceval find_opt : key -> 'a t -> 'a option
Sourceval min_binding : 'a t -> key * 'a

min_binding m is the binding with the least key.

Sourceval min_binding_opt : 'a t -> (key * 'a) option
Sourceval max_binding : 'a t -> key * 'a

max_binding m is the binding with the greatest key. Constant time.

Sourceval max_binding_opt : 'a t -> (key * 'a) option
Sourceval choose : 'a t -> key * 'a

choose m is a binding of m (currently max_binding m, which takes constant time).

Sourceval choose_opt : 'a t -> (key * 'a) option
Sourceval find_first : (key -> bool) -> 'a t -> key * 'a

find_first p m is the binding with the least key that satisfies p. Unlike Stdlib.Map.find_first, p need not be monotonic.

Sourceval find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
Sourceval disjoint : 'a t -> 'b t -> bool

disjoint m1 m2 determines whether m1 and m2 have no key in common.

Sourceval equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool

equal eq m1 m2 determines whether m1 and m2 have the same keys, bound to values related by eq.

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

compare cmp is a total order on maps, compatible with equal. It is a structural order, not the lexicographic order on bindings.

Sourceval changes : (key -> 'a option -> 'a option -> unit) -> 'a t -> 'a t -> unit

changes f m1 m2 calls f k x y, in increasing order of keys, for every key k such that x, the binding of k in m1, and y, its binding in m2, are not physically equal (None when there is no binding). Subtrees that the two maps share are skipped without being visited, so when m2 was derived from m1 by a few updates, the cost depends on the number of updates (times the depth), not on the size of the maps. Does not allocate (besides what f does and the options it receives).

Iteration

Sourceval iter : (key -> 'a -> unit) -> 'a t -> unit
Sourceval fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
Sourceval for_all : (key -> 'a -> bool) -> 'a t -> bool
Sourceval exists : (key -> 'a -> bool) -> 'a t -> bool
Sourceval bindings : 'a t -> (key * 'a) list

bindings m is the list of the bindings of m in increasing order of keys.

Sourceval to_seq : 'a t -> (key * 'a) Seq.t
Sourceval to_rev_seq : 'a t -> (key * 'a) Seq.t

Debugging

Sourceval check : 'a t -> unit

check m verifies the internal invariants of m and raises Failure if one is violated. It is intended for testing.

Sharing

Sourcemodule Sharing : sig ... end

Comparisons with sharing. Sharing.equal eq and Sharing.compare cmp return the same results as equal eq and compare cmp, but as a side effect they make the equal subtrees of their arguments physically equal. Later comparisons of these maps are then faster, and duplicate subtrees can be reclaimed. A subtree is replaced with one whose values are related by eq (or cmp returns 0): use these functions only when such values are interchangeable, for instance with a structural equality. This is invisible to the other operations and safe with concurrent domains.