Module type F.S

Signature of functional LRU maps.

Functional LRU map

type t

A map.

type k

Keys in t.

type v

Values in t.

val empty : int -> t

empty cap is an empty map with capacity cap.

raises Invalid_argument

when cap < 0.

val is_empty : t -> bool

is_empty t is true iff there are no bindings in t.

val size : t -> int

size t is the number of bindings in t.

Limiting the weight of bindings

val weight : t -> int

weight t is the combined weight of bindings in t.

val capacity : t -> int

capacity t is the maximum combined weight of bindings that trim will retain.

val resize : int -> t -> t

resize cap t sets t's capacity to cap, while leaving the bindings unchanged.

raises Invalid_argument

when cap < 0.

val trim : t -> t

trim t is t', where weight t' <= capacity t'.

This is achieved by discarding bindings in LRU-to-MRU order.

Access by k

val mem : k -> t -> bool

mem k t is true iff k is bound in t.

val find : k -> t -> v option

find k t is Some v when k -> v is bound in t, or None otherwise.

val promote : k -> t -> t

promote k t is t with the binding for k promoted to most-recently-used, or t if k is not bound in t.

val add : k -> v -> t -> t

add k v t adds the binding k -> v to t as the most-recently-used binding.

Note add does not remove bindings. To ensure that the resulting map is not over capacity, compose with trim.

val remove : k -> t -> t

remove k t is t without a binding for k.

val pop : k -> t -> (v * t) option

pop k t is (v, t'), where v is the value bound to k, and t' is t without the binding k -> t, or None if k is not bound in t.

Access to least-recently-used bindings

val lru : t -> (k * v) option

lru t is the least-recently-used binding in t, or None, when t is empty.

val drop_lru : t -> t

drop_lru t is t without the binding lru t, or t, when t is empty.

val pop_lru : t -> ((k * v) * t) option

pop_lru t is ((k, v), t', where (k, v) is lru t, and t' is t without that binding.

Aggregate access

val fold : (k -> v -> 'a -> 'a) -> 'a -> t -> 'a

fold f z t is f k0 v0 (... (f kn vn z)), where k0 -> v0 is LRU and kn -> vn is MRU.

val fold_k : (k -> v -> 'a -> 'a) -> 'a -> t -> 'a

fold_k f z t folds in key-increasing order, ignoring the recently-used ordering.

Note fold_k is faster than fold.

val iter : (k -> v -> unit) -> t -> unit

iter f t applies f to all the bindings in t in in LRU-to-MRU order.

val iter_k : (k -> v -> unit) -> t -> unit

iter_k f t applies f in key-increasing order, ignoring the recently-used ordering.

Note iter_k is faster than iter.

Conversions

val of_list : (k * v) list -> t

of_list kvs is a map with bindings kvs, where the order of the list becomes LRU-to-MRU ordering, and its capacity is set to its weight.

The resulting t has the same shape as if the bindings were sequentially added in list order, except for capacity.

val to_list : t -> (k * v) list

to_list t are the bindings in t in LRU-to-MRU order.

Pretty-printing

val pp : ?⁠pp_size:(Stdlib.Format.formatter -> (int * int) -> unit) -> ?⁠sep:(Stdlib.Format.formatter -> unit -> unit) -> (Stdlib.Format.formatter -> (k * v) -> unit) -> Stdlib.Format.formatter -> t -> unit

pp ~pp_size ~sep pp_kv ppf t pretty-prints t to ppf, using pp_kv to print the bindings, ~sep to separate them, and ~pp_size to print the weight and capacity. ~sep and ~pp_size default to unspecified printers.