Library

Module

Module type

Parameter

Class

Class type

Signature of functional LRU maps.

## Functional LRU map

Keys in `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.

`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`

.

`resize cap t`

a map with exactly the bindings in `t`

, but the capacity set to `cap`

.

## Access by `k`

`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`

.

`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`

`trim`

s the resulting map, ensuring it is not over capacity. It defaults to `true`

.

`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

`lru t`

is the least-recently-used binding in `t`

, or `None`

, when `t`

is empty.

`pop_lru t`

is `((k, v), t'`

, where `(k, v)`

is `lru t`

, and `t'`

is `t`

without that binding.

## Aggregate access

`fold f z t`

is `f k0 v0 (... (f kn vn z))`

. Binding are folded over in key-increasing order.

`iter f t`

applies `f`

to all the bindings in `t`

in key-increasing order

## Conversions

`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
```