(* Author: Alain Frisch.
Public domain.
*)
(** Bounded-size memoization tables *)
(** This module implements memoization tables with random access and
bounded size. This can be useful to memoize functions without consuming
a lot of memory. *)
type ('a,'b) t
(** Memoization tables with keys of type ['a] to values of type ['b]. *)
val create: int -> ('a,'b) t
(** [create n] creates a new memoization table with [n] slots. *)
val get: ('a,'b) t -> ('a -> 'a -> bool) -> 'a -> int -> 'b Lazy.t -> 'b
(** [get tbl cmp x i v] tries to fetch a previously computed value for
the key [x] in the table [tbl] in the slot [i]. If the result is not
available in the table, the result is computed by forcing the lazy
argument v. It may be kept it in the table for a later
call. This is the case in particular if the slot [i] was empty.
Otherwise, the decision to keep the value for old key or to
reuse the slot for the key [x] is not specified.
The current implementation, however, is such that, if we consider
the sequence of all the calls for a given slot, and if
one the keys appears strictly more often than half of the time
in this sequence, then this key "wins": its result is the one
which is kept in the table.
Keys are compared for equality using the function [cmp].
*)
val clear: ('a,'b) t -> unit
(** [clear tbl] removes all the keys and the associated values from
the table. *)