package patricia-tree

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Parameters
Signature

Package patricia-tree
- Library patricia-tree
  - PatriciaTree
    
    NODE
    
    NODE_WITH_ID
    
    HASH_CONSED_NODE
    
    BASE_MAP
    
    HETEROGENEOUS_MAP
    
    WithForeign
    
    HETEROGENEOUS_SET
    
    BaseMap
    
    WithForeign
    
    SET
    
    BaseMap
    
    WithForeign
    
    MAP_WITH_VALUE
    
    BaseMap
    
    WithForeign
    
    WithForeign
    
    MAP
    
    BaseMap
    
    WithForeign
    
    WithForeign
    
    KEY
    
    HETEROGENEOUS_KEY
    
    VALUE
    
    Value
    
    HETEROGENEOUS_VALUE
    
    HomogeneousValue
    
    WrappedHomogeneousValue
    
    HASHED_VALUE
    
    HETEROGENEOUS_HASHED_VALUE
    
    HashedValue
    
    HeterogeneousHashedValue
    
    MakeMap
    
    BaseMap
    
    WithForeign
    
    WithForeign
    
    MakeSet
    
    BaseMap
    
    WithForeign
    
    MakeHeterogeneousSet
    
    BaseMap
    
    WithForeign
    
    MakeHeterogeneousMap
    
    WithForeign
    
    MakeCustomMap
    
    BaseMap
    
    WithForeign
    
    WithForeign
    
    MakeCustomSet
    
    BaseMap
    
    WithForeign
    
    MakeCustomHeterogeneousMap
    
    WithForeign
    
    MakeCustomHeterogeneousSet
    
    BaseMap
    
    WithForeign
    
    MakeHashconsedMap
    
    BaseMap
    
    WithForeign
    
    WithForeign
    
    MakeHashconsedSet
    
    BaseMap
    
    WithForeign
    
    MakeHashconsedHeterogeneousSet
    
    BaseMap
    
    WithForeign
    
    MakeHashconsedHeterogeneousMap
    
    WithForeign
    
    SimpleNode
    
    NodeWithId
    
    SetNode
    
    WeakNode
    
    WeakSetNode
    
    HashconsedNode
    
    HashconsedSetNode
- Sources
  - patricia-tree
    
    patriciaTree.ml

Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module `PatriciaTree.MakeHashconsedMap`Source

Hash-consed version of MAP. See Hash-consed maps and sets for the differences between hash-consed and non hash-consed maps.

This is a generative functor, as calling it creates a new hash-table to store the created nodes, and a reference to store the next unallocated identifier. Maps/sets from different hash-consing functors (even if these functors have the same arguments) will have different (incompatible) numbering systems and be stored in different hash-tables (thus they will never be physically equal).

since v0.10.0

Parameters

module Key : KEY

module Value : HASHED_VALUE

Signature

include MAP_WITH_VALUE with type key = Key.t and type 'a value = 'a Value.t

Sourcetype key = Key.t

The type of keys.

Sourcetype 'a t

A map from key to values of type 'a value.

Sourcetype 'a value = 'a Value.t

Type for values, this is a divergence from Stdlib's Map, but becomes equivalent to it when using MAP, which is just MAP_WITH_VALUE with type 'a value = 'a. On the other hand, it allows defining maps with fixed values, which is useful for hash-consing.

since v0.10.0

Source

module BaseMap : 
  HETEROGENEOUS_MAP
    with type 'a t = 'a t
     and type _ key = key
     and type ('a, 'b) value = ('a, 'b value) snd

Underlying basemap, for cross map/set operations

Basic functions

Sourceval empty : 'a t

The empty map.

Sourceval is_empty : 'a t -> bool

Test if a map is empty; O(1) complexity.

Sourceval unsigned_min_binding : 'a t -> key * 'a value

Returns the (key,value) pair where Key.to_int key is minimal (in the unsigned representation of integers); O(log n) complexity.

raises Not_found
if the map is empty.

Sourceval unsigned_max_binding : 'a t -> key * 'a value

Returns the (key,value) pair where Key.to_int key is maximal (in the unsigned representation of integers); O(log n) complexity.

raises Not_found
if the map is empty.

Sourceval singleton : key -> 'a value -> 'a t

singleton key value creates a map with a single binding, O(1) complexity.

Sourceval cardinal : 'a t -> int

The size of the map. O(n) complexity.

Sourceval is_singleton : 'a t -> (key * 'a value) option

is_singleton m is Some (k,v) iff m is singleton k v.

Sourceval find : key -> 'a t -> 'a value

Return an element in the map, or raise Not_found, O(log(n)) complexity.

Sourceval find_opt : key -> 'a t -> 'a value option

Return an element in the map, or None, O(log(n)) complexity.

Sourceval mem : key -> 'a t -> bool

mem key map returns true if and only if key is bound in map. O(log(n)) complexity.

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

Returns a map with the element removed, O(log(n)) complexity. Returns a physically equal map if the element is absent.

Sourceval pop_unsigned_minimum : 'a t -> (key * 'a value * 'a t) option

pop_unsigned_minimum m returns None if is_empty m, or Some(key,value,m') where (key,value) = unsigned_min_binding m and m' = remove m key. O(log(n)) complexity. Uses the unsigned order on KEY.to_int.

Sourceval pop_unsigned_maximum : 'a t -> (key * 'a value * 'a t) option

pop_unsigned_maximum m returns None if is_empty m, or Some(key,value,m') where (key,value) = unsigned_max_binding m and m' = remove m key. O(log(n)) complexity. Uses the unsigned order on KEY.to_int.

Sourceval insert : key -> ('a value option -> 'a value) -> 'a t -> 'a t

insert key f map modifies or insert an element of the map; f takes None if the value was not previously bound, and Some old where old is the previously bound value otherwise. The function preserves physical equality when possible. O(log(n)) complexity. Preserves physical equality if the new value is physically equal to the old.

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

update key f map modifies, insert, or remove an element from the map; f takes None if the value was not previously bound, and Some old where old is the previously bound value otherwise. The function preserves physical equality when possible. It returns None if the element should be removed O(log(n)) complexity. Preserves physical equality if the new value is physically equal to the old.

Sourceval add : key -> 'a value -> 'a t -> 'a t

Unconditionally adds a value in the map (independently from whether the old value existed). O(log(n)) complexity. Preserves physical equality if the new value is physically equal to the old.

Iterators

Sourceval split : key -> 'a t -> 'a t * 'a value option * 'a t

split key map splits the map into:

submap of map whose keys are smaller than key
value associated to key (if present)
submap of map whose keys are bigger than key

Uses the unsigned order on KEY.to_int.

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

Iterate on each (key,value) pair of the map, in increasing unsigned order of KEY.to_int.

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

Fold on each (key,value) pair of the map, in increasing unsigned order of KEY.to_int.

Source

val fold_on_nonequal_inter : 
  (key -> 'a value -> 'a value -> 'acc -> 'acc) ->
  'a t ->
  'a t ->
  'acc ->
  'acc

fold_on_nonequal_inter f m1 m2 acc returns f key_n value1_n value2n (... (f key_1 value1_1 value2_1 acc)) where (key_1, value1_1, value2_1) ... (key_n, value1_n, value2_n) are the bindings that exist in both maps (m1 ∩ m2) whose values are physically different. Calls to f are performed in the unsigned order of KEY.to_int.

Source

val fold_on_nonequal_union : 
  (key -> 'a value option -> 'a value option -> 'acc -> 'acc) ->
  'a t ->
  'a t ->
  'acc ->
  'acc

fold_on_nonequal_union f m1 m2 acc returns f key_n value1_n value2n (... (f key_1 value1_1 value2_1 acc)) where (key_1, value1_1, value2_1) ... (key_n, value1_n, value2_n) are the bindings that exists in either map (m1 ∪ m2) whose values are physically different. Calls to f.f are performed in the unsigned order of KEY.to_int.

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

Returns the submap containing only the key->value pairs satisfying the given predicate. f is called in increasing unsigned order of KEY.to_int.

Sourceval for_all : (key -> 'a value -> bool) -> 'a t -> bool

Returns true if the predicate holds on all map bindings. Short-circuiting. f is called in increasing unsigned order of KEY.to_int.

In the following, the *no_share function allows taking arguments of different types (but cannot share subtrees of the map), while the default functions attempt to preserve and benefit from sharing the subtrees (using physical equality to detect sharing).

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

map f m returns a map where the value bound to each key is replaced by f value. The subtrees for which the returned value is physically the same (i.e. f key value == value for all the keys in the subtree) are guaranteed to be physically equal to the original subtree. O(n) complexity. f is called in increasing unsigned order of KEY.to_int.

Sourceval map_no_share : ('a value -> 'b value) -> 'a t -> 'b t

map_no_share f m returns a map where the value bound to each key is replaced by f value. O(n) complexity. f is called in increasing unsigned order of KEY.to_int.

Sourceval mapi : (key -> 'a value -> 'a value) -> 'a t -> 'a t

mapi f m returns a map where the value bound to each key is replaced by f key value. The subtrees for which the returned value is physically the same (i.e. f key value == value for all the keys in the subtree) are guaranteed to be physically equal to the original subtree. O(n) complexity. f is called in increasing unsigned order of KEY.to_int.

Sourceval mapi_no_share : (key -> 'a value -> 'b value) -> 'a t -> 'b t

mapi_no_share f m returns a map where the value bound to each key is replaced by f key value. O(n) complexity. f is called in increasing unsigned order of KEY.to_int.

Sourceval filter_map : (key -> 'a value -> 'a value option) -> 'a t -> 'a t

filter_map m f returns a map where the value bound to each key is removed (if f key value returns None), or is replaced by v ((if f key value returns Some v). The subtrees for which the returned value is physically the same (i.e. f key value = Some v with value == v for all the keys in the subtree) are guaranteed to be physically equal to the original subtree. O(n) complexity. f is called in increasing unsigned order of KEY.to_int.

Sourceval filter_map_no_share : (key -> 'a value -> 'b value option) -> 'a t -> 'b t

filter_map m f returns a map where the value bound to each key is removed (if f key value returns None), or is replaced by v ((if f key value returns Some v). O(n) complexity. f is called in increasing unsigned order of KEY.to_int.

Operations on pairs of maps

The following functions combine two maps. It is key for the performance, when we have large maps who share common subtrees, not to visit the nodes in these subtrees. Hence, we have specialized versions of these functions that assume properties of the function parameter (reflexive relation, idempotent operation, etc.)

When we cannot enjoy these properties, our functions explicitly say so (with a nonreflexive or nonidempotent prefix). The names are a bit long, but having these names avoids using an ineffective code by default, by forcing to know and choose between the fast and slow version.

It is also important to not visit a subtree when there merging this subtree with Empty; hence we provide union and inter operations.

Source

val reflexive_same_domain_for_all2 : 
  (key -> 'a value -> 'a value -> bool) ->
  'a t ->
  'a t ->
  bool

reflexive_same_domain_for_all2 f map1 map2 returns true if map1 and map2 have the same keys, and f key value1 value2 returns true for each mapping pair of keys. We assume that f is reflexive (i.e. f key value value returns true) to avoid visiting physically equal subtrees of map1 and map2. The complexity is O(log(n)*Delta) where Delta is the number of different keys between map1 and map2.

Source

val nonreflexive_same_domain_for_all2 : 
  (key -> 'a value -> 'b value -> bool) ->
  'a t ->
  'b t ->
  bool

nonreflexive_same_domain_for_all2 f map1 map2 returns true if map1 and map2 have the same keys, and f key value1 value2 returns true for each mapping pair of keys. The complexity is O(min(|map1|,|map2|)).

Source

val reflexive_subset_domain_for_all2 : 
  (key -> 'a value -> 'a value -> bool) ->
  'a t ->
  'a t ->
  bool

reflexive_subset_domain_for_all2 f map1 map2 returns true if all the keys of map1 also are in map2, and f key (find map1 key) (find map2 key) returns true when both keys are present in the map. We assume that f is reflexive (i.e. f key value value returns true) to avoid visiting physically equal subtrees of map1 and map2. The complexity is O(log(n)*Delta) where Delta is the number of different keys between map1 and map2.

Source

val idempotent_union : 
  (key -> 'a value -> 'a value -> 'a value) ->
  'a t ->
  'a t ->
  'a t

idempotent_union f map1 map2 returns a map whose keys is the union of the keys of map1 and map2. f is used to combine the values a key is mapped in both maps. We assume that f is idempotent (i.e. f key value value == value) to avoid visiting physically equal subtrees of map1 and map2, and also to preserve physical equality of the subtreess in that case. The complexity is O(log(n)*Delta) where Delta is the number of different keys between map1 and map2. f is called in increasing unsigned order of KEY.to_int. f is never called on physically equal values.

Source

val idempotent_inter : 
  (key -> 'a value -> 'a value -> 'a value) ->
  'a t ->
  'a t ->
  'a t

idempotent_inter f map1 map2 returns a map whose keys is the intersection of the keys of map1 and map2. f is used to combine the values a key is mapped in both maps. We assume that f is idempotent (i.e. f key value value == value) to avoid visiting physically equal subtrees of map1 and map2, and also to preserve physical equality of the subtrees in that case. The complexity is O(log(n)*Delta) where Delta is the number of different keys between map1 and map2. f is called in increasing unsigned order of KEY.to_int!. f is never called on physically equal values.

Source

val nonidempotent_inter_no_share : 
  (key -> 'a value -> 'b value -> 'c value) ->
  'a t ->
  'b t ->
  'c t

nonidempotent_inter_no_share f map1 map2 returns a map whose keys is the intersection of the keys of map1 and map2. f is used to combine the values a key is mapped in both maps. f does not need to be idempotent, which imply that we have to visit physically equal subtrees of map1 and map2. The complexity is O(log(n)*min(|map1|,|map2|)). f is called in increasing unsigned order of KEY.to_int. f is called on every shared binding.

Source

val idempotent_inter_filter : 
  (key -> 'a value -> 'a value -> 'a value option) ->
  'a t ->
  'a t ->
  'a t

idempotent_inter_filter f m1 m2 is like idempotent_inter (assuming idempotence, using and preserving physically equal subtrees), but it also removes the key->value bindings for which f returns None.

Source

val slow_merge : 
  (key -> 'a value option -> 'b value option -> 'c value option) ->
  'a t ->
  'b t ->
  'c t

slow_merge f m1 m2 returns a map whose keys are a subset of the keys of m1 and m2. The f function is used to combine keys, similarly to the Map.merge function. This funcion has to traverse all the bindings in m1 and m2; its complexity is O(|m1|+|m2|). Use one of faster functions above if you can.

Sourceval disjoint : 'a t -> 'a t -> bool

Sourcemodule WithForeign (Map2 : BASE_MAP with type _ key = key) : sig ... end

Combination with other kinds of maps. Map2 must use the same KEY.to_int function.

Source

val pretty : 
  ?pp_sep:(Format.formatter -> unit -> unit) ->
  (Format.formatter -> key -> 'a value -> unit) ->
  Format.formatter ->
  'a t ->
  unit

Pretty prints all bindings of the map. pp_sep is called once between each binding pair and defaults to Format.pp_print_cut.

Conversion functions

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

to_seq m iterates the whole map, in increasing unsigned order of KEY.to_int

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

to_rev_seq m iterates the whole map, in decreasing unsigned order of KEY.to_int

Sourceval add_seq : (key * 'a value) Seq.t -> 'a t -> 'a t

add_seq s m adds all bindings of the sequence s to m in order.

Sourceval of_seq : (key * 'a value) Seq.t -> 'a t

of_seq s creates a new map from the bindings of s. If a key is bound multiple times in s, the latest binding is kept

Sourceval of_list : (key * 'a value) list -> 'a t

of_list l creates a new map from the bindings of l. If a key is bound multiple times in l, the latest binding is kept

Sourceval to_list : 'a t -> (key * 'a value) list

to_list m returns the bindings of m as a list, in increasing unsigned order of KEY.to_int

Sourceval to_int : 'a t -> int

Returns the hash-consed id of the map. Unlike NODE_WITH_ID.to_int, hash-consing ensures that maps which contain the same keys (compared by KEY.to_int) and values (compared by HASHED_VALUE.polyeq) will always be physically equal and have the same identifier.

Note that when using physical equality as HASHED_VALUE.polyeq, some maps of different types a t and b t may be given the same identifier. See the end of the documentation of HASHED_VALUE.polyeq for details.

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

Constant time equality using the hash-consed nodes identifiers. This is equivalent to physical equality. Two nodes are equal if their trees contain the same bindings, where keys are compared by KEY.to_int and values are compared by HASHED_VALUE.polyeq.

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

Constant time comparison using the hash-consed node identifiers. This order is fully arbitrary, but it is total and can be used to sort nodes. It is based on node ids which depend on the order in which the nodes where created (older nodes having smaller ids).

One useful property of this order is that child nodes will always have a smaller identifier than their parents.

package patricia-tree

Module PatriciaTree.MakeHashconsedMapSource

Parameters

Signature

Basic functions

Iterators

Operations on pairs of maps

Conversion functions

Module `PatriciaTree.MakeHashconsedMap`Source