module Hashhe:Hash tables and hash functions (extension of standard library module)`sig`

..`end`

Hash tables are hashed association tables, with in-place modification.

Modified by B. Jeannet: functions `map`

, `copy`

and `print`

.

`type ``('a, 'b)`

hashtbl

`type ``'a`

compare = {

` ` |
`hash : ` |

` ` |
`equal : ` |

type`('a, 'b)`

t =`('a, 'b) hashtbl`

The type of hash tables from type

`'a`

to type `'b`

.`val create : ``int -> ('a, 'b) t`

`create n`

creates a new, empty hash table, with
initial size `n`

. For best results, `n`

should be on the
order of the expected number of elements that will be in
the table. The table grows as needed, so `n`

is just an
initial guess.`val clear : ``('a, 'b) t -> unit`

Empty a hash table.

`val add : ``('a, 'b) t -> 'a -> 'b -> unit`

`add tbl x y`

adds a binding of `x`

to `y`

in table `tbl`

.
Previous bindings for `x`

are not removed, but simply
hidden. That is, after performing `Hashhe.remove`

` tbl x`

,
the previous binding for `x`

, if any, is restored.
(Same behavior as with association lists.)`val copy : ``('a, 'b) t -> ('a, 'b) t`

Return a copy of the given hashtable.

`val find : ``('a, 'b) t -> 'a -> 'b`

`find tbl x`

returns the current binding of `x`

in `tbl`

,
or raises `Not_found`

if no such binding exists.`val find_all : ``('a, 'b) t -> 'a -> 'b list`

`find_all tbl x`

returns the list of all data
associated with `x`

in `tbl`

.
The current binding is returned first, then the previous
bindings, in reverse order of introduction in the table.`val mem : ``('a, 'b) t -> 'a -> bool`

`mem tbl x`

checks if `x`

is bound in `tbl`

.`val remove : ``('a, 'b) t -> 'a -> unit`

`remove tbl x`

removes the current binding of `x`

in `tbl`

,
restoring the previous binding if it exists.
It does nothing if `x`

is not bound in `tbl`

.`val replace : ``('a, 'b) t -> 'a -> 'b -> unit`

`replace tbl x y`

replaces the current binding of `x`

in `tbl`

by a binding of `x`

to `y`

. If `x`

is unbound in `tbl`

,
a binding of `x`

to `y`

is added to `tbl`

.
This is functionally equivalent to `Hashhe.remove`

` tbl x`

followed by `Hashhe.add`

` tbl x y`

.`val iter : ``('a -> 'b -> unit) -> ('a, 'b) t -> unit`

`iter f tbl`

applies `f`

to all bindings in table `tbl`

.
`f`

receives the key as first argument, and the associated value
as second argument. Each binding is presented exactly once to `f`

.
The order in which the bindings are passed to `f`

is unspecified.
However, if the table contains several bindings for the same key,
they are passed to `f`

in reverse order of introduction, that is,
the most recent binding is passed first.`val fold : ``('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c`

`fold f tbl init`

computes
`(f kN dN ... (f k1 d1 init)...)`

,
where `k1 ... kN`

are the keys of all bindings in `tbl`

,
and `d1 ... dN`

are the associated values.
Each binding is presented exactly once to `f`

.
The order in which the bindings are passed to `f`

is unspecified.
However, if the table contains several bindings for the same key,
they are passed to `f`

in reverse order of introduction, that is,
the most recent binding is passed first.`val map : ``('a -> 'b -> 'c) -> ('a, 'b) t -> ('a, 'c) t`

`map f tbl`

applies `f`

to all bindings in table `tbl`

and creates
a new hashtable associating the results of `f`

to the same key type. `f`

receives the key as first argument, and the associated value as second
argument. Each binding is presented exactly once to `f`

. The order in which
the bindings are passed to `f`

is unspecified. However, if the table
contains several bindings for the same key, they are passed to `f`

in reverse
order of introduction, that is, the most recent binding is passed first.`val length : ``('a, 'b) t -> int`

`length tbl`

returns the number of bindings in `tbl`

.
Multiple bindings are counted multiply, so `length`

gives the number of times `iter`

calls it first argument.`val print : ``?first:(unit, Format.formatter, unit) Pervasives.format ->`

?sep:(unit, Format.formatter, unit) Pervasives.format ->

?last:(unit, Format.formatter, unit) Pervasives.format ->

?firstbind:(unit, Format.formatter, unit) Pervasives.format ->

?sepbind:(unit, Format.formatter, unit) Pervasives.format ->

?lastbind:(unit, Format.formatter, unit) Pervasives.format ->

(Format.formatter -> 'a -> unit) ->

(Format.formatter -> 'b -> unit) ->

Format.formatter -> ('a, 'b) t -> unit

module type HashedType =`sig`

..`end`

The input signature of the functor

`Hashhe.Make`

.
module type S =`sig`

..`end`

The output signature of the functor

`Hashhe.Make`

.
module Make:

Functor building an implementation of the hashtable structure.

`val hash : ``'a -> int`

`hash x`

associates a positive integer to any value of
any type. It is guaranteed that
if `x = y`

or `Pervasives.compare x y = 0`

, then `hash x = hash y`

.
Moreover, `hash`

always terminates, even on cyclic
structures.`val hash_param : ``int -> int -> 'a -> int`

`hash_param n m x`

computes a hash value for `x`

, with the
same properties as for `hash`

. The two extra parameters `n`

and
`m`

give more precise control over hashing. Hashing performs a
depth-first, right-to-left traversal of the structure `x`

, stopping
after `n`

meaningful nodes were encountered, or `m`

nodes,
meaningful or not, were encountered. Meaningful nodes are: integers;
floating-point numbers; strings; characters; booleans; and constant
constructors. Larger values of `m`

and `n`

means that more
nodes are taken into account to compute the final hash
value, and therefore collisions are less likely to happen.
However, hashing takes longer. The parameters `m`

and `n`

govern the tradeoff between accuracy and speed.`val stdcompare : ``'a compare`

module Compare:`sig`

..`end`