package lru

  1. Overview
  2. Docs

Module F.MakeSource

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

Sourcetype t

A map.

Sourcetype k = K.t

Keys in t.

Sourcetype v = V.t

Values in t.

Sourceval empty : int -> t

empty cap is an empty map with capacity cap.

Sourceval is_empty : t -> bool

is_empty t is true iff t is empty.

Sourceval items : t -> int

items t is the number of bindings in t.

Sourceval size : t -> int

size t is the combined weight of bindings in t.

Sourceval 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.

Sourceval 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

Sourceval mem : k -> t -> bool

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

Sourceval 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.

Sourceval 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.

Sourceval remove : k -> t -> t

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

Sourceval 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

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

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

Sourceval drop_lru : t -> t

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

Sourceval 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

Sourceval 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.

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

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

Conversions

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

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

Sourceval 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

Sourceval 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.