lru 0.1.1 · OCaml Package

Make(K)(V) is the LRU map with bindings K.t -> V.t. The weight of an individual binding is the Weighted.weight of V.t.

Parameters

module K : Ordered

module V : Weighted

Signature

Functional LRU map

type t

A map.

type k = K.t

Keys in t.

type v = V.t

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 resize : int -> t -> t

resize cap t is a map with capacity cap, holding the same bindings as t. When the size of t is greater than cap, least-recently-used bindings are discarded to fit cap.

Access by `k`

val mem : k -> t -> bool

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

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

find k t is (v, t'), where v is the value bound to k and t' is a map where the binding k -> v has been promoted to most-recently-used. When k is not bound in t, the result in None.

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

add k v t is t with the binding k -> v. If k is alread bound in t, the old binding is replaced. In either case, the binding k -> v is the most-recently-used.

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 : ?cap:int -> (k * v) list -> t

of_list kvs is a map with the bindings from kvs. If there are multiple bindings for the same k, it is unspecified which one is chosen.

~cap is the capacity of the new map. It defaults to the total weight of bindings in kvs. If given, and smaller than then total weight of vs, bindings are discarded from the left of the list.

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.

package lru