Module Btree.Map

A finite map implemented by a B tree.

Parameters

Signature

Map API

include Interfaces.MAP with type key = Key.t
type key = Key.t

Type of the keys

type 'a t

Type of a map with keys of type key and values of type 'a.

val is_empty : 'a t -> bool

Is the map empty?

val cardinal : 'a t -> int

cardinal map The cardinality of the map i.e. the number of key value pairs in the map.

val fold_left : ('accu -> key -> 'a -> 'accu) -> 'accu -> 'a t -> 'accu

fold_left f start map

Fold the bindings in the map map from left to right i.e. lexically ascending using the start value start for the accumulator and the folding function f where f is applied f accue key value yielding a new accumulator by consuming one key value pair.

val fold_right : ('accu -> key -> 'a -> 'accu) -> 'accu -> 'a t -> 'accu

fold_left f start map

Fold the bindings in the map map from right to left i.e. lexically descending using the start value start for the accumulator and the folding function f where f is applied f accu key value yielding a new accumulator by consuming one key value pair.

val bindings : 'a t -> (key * 'a) list

The list of key value pairs in the map in ascending order.

val find_opt : key -> 'a t -> 'a option

find_opt key map

Find the value which is bound to the key key in the map map. Return None if no value is bound to key.

val empty : 'a t

The empty map.

val add : key -> 'a -> 'a t -> 'a t

add key value map Add the key value pair key, value to the map. If the map has already a key value pair with the key key then overwrite the old value with the new value.

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

remove key map Remove the key value pair with the key key from the map map. If the key is not present, then do nothing.

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

update key f map

Update the value bound to the key key in the map map by the update function f. If no value is bound to key then f None is called. If value is bound to key then f (Some value) is called.

If f returns None then no value is added and the old binding is deleted (if it existed before).

If f return Some new_value then the old value is updated, if existed, or the new value is added if no old value existed before.

val of_list : (Key.t * 'a) list -> 'a t

Stream of key value pairs

All key value pairs of a finite map can be considered as a sorted list of key value pairs. It is possible to iterate over this sequence with the help of the function fold_left. However this function performs the whole iteration.

Sometimes it is desirable to iterate over the sequence of the sorted key value pairs and keep the control over the iteration. For that purpose it is convenient to have the finite map as a stream of key value pairs.

type 'a source

Type of a stream of key value pairs.

val make_source : 'a t -> 'a source

Convert the map into a stream of key value pairs.

val has_more : 'a source -> bool

Has the stream of key value pairs more elements?

val peek : 'a source -> Key.t * 'a

The next key value pair of the stream.

val advance : 'a source -> 'a source

advances source Advance the stream by one element.

Precondition: has_more source

module Source (Value : Interfaces.ANY) : sig ... end

Module which satisfies the interface Interfaces.SOURCE