(* 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. *)