package lru

  1. Overview
  2. Docs

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.

val is_empty : t -> bool

is_empty t is true iff t is empty.

val items : t -> int

items t is the number of bindings in t.

val size : t -> int

size t is the combined weight of bindings in t.

val capacity : t -> int

capacity t is the maximum combined weight of bindings this map will hold before they start being discarded in least-recently-used order.

val trim : t -> t

trim t is the map t', that contains as many most-recently-used bindings in t as its capacity permits (size t' <= capacity t'). If t is over capacity, bindings are discarded in least-recently-used order. Otherwise, t' == t.

val resize : int -> t -> t

resize cap t a map with exactly the bindings in t, but the capacity set to cap.

Access by k

val mem : k -> t -> bool

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

val find : ?promote:bool -> k -> t -> (v * t) option

find k t is (v, t'), where v is the value bound to k.

When promote is true, t' is t with the binding k -> v promoted to most-recently-used. Otherwise, t' == t. It defaults to true.

val add : ?trim:bool -> k -> v -> t -> t

add k v t is t with the binding k -> v. If k is already bound in t, the old binding is replaced. The binding k -> v is the most-recently-used.

When trim is true, add trims the resulting map, ensuring it is not over capacity. It defaults to true.

val remove : k -> t -> t

remove k t is t without the binding for k, or t, if k is not bound in t.

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

unadd 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)). Binding are folded over in key-increasing order.

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

iter f t applies f to all the bindings in t in key-increasing order

Conversions

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

to_list t are the bindings in t in key-increasing order.

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

of_list kvs is a map with bindings from kvs. Its size and capacity are the total weight of its bindings.

With respect to duplicates and the recently-used order, it behaves as if the bindings were added sequentially in the list order.

w = size (of_list kvs)

of_list kvs = List.fold_left (fun m (k, v) -> add k v m) (empty w) kvs

Pretty-printing

val pp : ?pp_size:(Format.formatter -> (int * int) -> unit) -> ?sep:(Format.formatter -> unit -> unit) -> (Format.formatter -> (k * v) -> unit) -> 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 size and capacity. ~sep and ~pp_size default to unspecified printers.