(***********************************************************************)
(* *)
(* Objective Caml *)
(* *)
(* Xavier Leroy, projet Cristal, INRIA Rocquencourt *)
(* *)
(* Copyright 1996 Institut National de Recherche en Informatique et *)
(* en Automatique. All rights reserved. This file is distributed *)
(* under the terms of the GNU Library General Public License, with *)
(* the special exception on linking described in file ../LICENSE. *)
(* *)
(***********************************************************************)
(* $Id: map.mli,v 1.28 2001/12/10 12:33:54 xleroy Exp $ *)
(** Association tables over ordered types.
This module implements applicative association tables, also known as
finite maps or dictionaries, given a total ordering function
over the keys.
All operations over maps are purely applicative (no side-effects).
The implementation uses balanced binary trees, and therefore searching
and insertion take time logarithmic in the size of the map.
*)
module type S =
sig
type key
(** The type of the map keys. *)
type (+'a) t
(** The type of maps from type [key] to type ['a]. *)
val check: 'a t -> bool
(** [check t] checks the tree [t] for validity. It returns
true if the t is valid, false otherwise. It is primarily
intended for testing. It takes O(n) time and O(log n) memory. *)
val empty: 'a t
(** The empty map. *)
val singleton: key -> 'a -> 'a t
(** Creates a map with a single entry. *)
val count : 'a t -> int
(** Returns the number of entries in the tree. This takes O(n) time
and O(log n) stack. *)
val add: key -> 'a -> 'a t -> 'a t
(** [add x y m] returns a map containing the same bindings as
[m], plus a binding of [x] to [y]. If [x] was already bound
in [m], its previous binding disappears. *)
val find: key -> 'a t -> 'a
(** [find x m] returns the current binding of [x] in [m],
or raises [Not_found] if no such binding exists. *)
val remove: key -> 'a t -> 'a t
(** [remove x m] returns a map containing the same bindings as
[m], except for [x] which is unbound in the returned map. *)
val mem: key -> 'a t -> bool
(** [mem x m] returns [true] if [m] contains a binding for [x],
and [false] otherwise. *)
val iter: (key -> 'a -> unit) -> 'a t -> unit
(** [iter f m] applies [f] to all bindings in map [m].
[f] receives the key as first argument, and the associated value
as second argument. The order in which the bindings are passed to
[f] is unspecified. Only current bindings are presented to [f]:
bindings hidden by more recent bindings are not passed to [f]. *)
val map: ('a -> 'b) -> 'a t -> 'b t
(** [map f m] returns a map with same domain as [m], where the
associated value [a] of all bindings of [m] has been
replaced by the result of the application of [f] to [a].
The order in which the associated values are passed to [f]
is unspecified. *)
val mapi: (key -> 'a -> 'b) -> 'a t -> 'b t
(** Same as {!Map.S.map}, but the function receives as arguments
both the key and the associated value for each binding of
the map. *)
val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
(** [fold f m a] computes [(f kN dN ... (f k1 d1 a)...)],
where [k1 ... kN] are the keys of all bindings in [m],
and [d1 ... dN] are the associated data.
The order in which the bindings are presented to [f] is
unspecified. This takes O(N) time and O(log N) stack. *)
val fold_left: ('a -> key -> 'b -> 'a) -> 'a -> 'b t -> 'a
(** [fold_left] computes [(f ( ... (f a k1 d1) ... ) kN dN)],
where [k1 ... kN] are the keys of all bindings in [m],
and [d1 ... dN] are the associated data. The order in
the bindings are presented to [f] is gaurenteed to be
in increasing order- that is [Ord.compare ki kj < 0] is
gaurenteed to be true for all 1 <= i < j <= N. This takes
O(N) time and O(log N) stack. *)
val fold_right: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
(** [fold_right f m a] computes [(f kN dN ... (f k1 d1 a)...)],
where [k1 ... kN] are the keys of all bindings in [m],
and [d1 ... dN] are the associated data. The order in
the bindings are presented to [f] is gaurenteed to be
in decreasing order- that is [Ord.compare ki kj > 0] is
gaurenteed to be true for all 1 <= i < j <= N. This takes
O(N) time and O(log N) stack. *)
val to_list : 'a t -> (key * 'a) list
(** Converts the map to a list of tuples representation. The list
of tuples is gaurenteed to be sorted in increasing key order.
This takes O(N) time and O(log N) stack. *)
val to_key_list : 'a t -> key list
(** Creates a list of all keys that have associations in
the map. The list is gaurenteed to be sorted in increasing key
order. This takes O(N) time and O(log N) stack. *)
val to_val_list : 'a t -> 'a list
(** Creates a list of all data values that are associated with
keys in the map. The list is gaurenteed to be sorted in
increasing order of the keys they are associated with. Data
values are not gaurenteed to be unique. This takes O(N) time and
O(log N) stack. *)
val of_list : (key * 'a) list -> 'a t
(** Create a map from the given list of tuples. This is the reverse
of [to_list]. If the list is sorted in increasing key order,
this routine takes O(N) time and O(log N) stack. If the list
is not sorted, this routine takes O(N log N) time and O(log N)
stack.
*)
val of_list2 : key list -> 'a list -> 'a t
(** [of_list2 keylist datalist] creates a tree from a list of
keys and a list of data values. The [i]th element of the data
value list is associated with the [i]th key from the key list.
If the key list is sorted in increasing order, then this
function takes O(N) time and O(log N) stack. If the key list
is not sorted, then it takes O(N log N) time and O(log N) stack. *)
val enum : 'a t -> (key * 'a) Enum.t
(** Creates an enumeration of the key/value pairs of the map.
The order of the enumeration is gaurenteed to be sorted in
increasing key order. This function takes O(1) time and O(1)
stack. The enumeration created consumes at most O(log N) space
at any given time. Calling [next] costs at most O(log N) time
and O(1) stack. Calling [count] costs O(N) time and O(log N)
stack, and qualifies as fast. Calling [clone] costs O(1) time
and O(1) stack. *)
val enum_values : 'a t -> 'a Enum.t
(** Creates an enumeration of the the keys of the map.
The order of the enumeration is gaurenteed to be sorted in
increasing key order. This function takes O(1) time and O(1)
stack. The enumeration created consumes at most O(log N) space
at any given time. Calling [next] costs at most O(log N) time
and O(1) stack. Calling [count] costs O(N) time and O(log N)
stack, and qualifies as fast. Calling [clone] costs O(1) time
and O(1) stack. *)
val enum_keys : 'a t -> key Enum.t
(** Creates an enumeration of the the data values of the map.
The order of the enumeration is gaurenteed to be sorted in
increasing key order for the keys the data values are associated
with. This function takes O(1) time and O(1) stack. The
enumeration created consumes at most O(log N) space at any
given time. Calling [next] costs at most O(log N) time and
O(1) stack. Calling [count] costs O(N) time and O(log N)
stack, and qualifies as fast. Calling [clone] costs O(1)
time and O(1) stack. *)
val of_enum : (key * 'a) Enum.t -> 'a t
(** Creates a map from the given enumeration of key/value pairs.
If the enumeration has a fast count and the keys are sorted
in increasing order, than this function takes O(N) time and
O(log N) stack. If either of those conditions does not hold,
then this function takes O(N log N) time and O(log N) stack. *)
val of_enum2 : key Enum.t -> 'a Enum.t -> 'a t
(** Creates a map from an enumeration of keys and an enumeration
of data values. The [i]th key is associated with the [i]th
value. If the key enumeration has a fast count and the keys
are sorted in increasing order, than this function takes O(N)
time and O(log N) stack. If either of those conditions does
not hold, then this function takes O(N log N) time and O(log N)
stack. *)
val iter2: (key -> 'a option -> 'b option -> unit) -> 'a t -> 'b t -> unit
(** [iter2 f a b] calculates [f k1 A1 B1; ... ; f kN AN BN], where
[k1, ... kN] is the union of the set of all keys that have
associations in map [a] or map [b]. [Ai] is [Some(v)] when key
[ki] is associated with value [v] in map [a], and [None] if key
[ki] does not have a value associated with it in map [a].
Likewise, [Bi] is [Some(v)] when key [ki] is associated with
value [v] in map [b], and [None] if key [ki] does not have a
value associated with it in map [b]. It is gaurenteed that
the keys are presented to f in increasing order. *)
val iter2_both: (key -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit
val fold2: (key -> 'a option -> 'b option -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
val fold2_both: (key -> 'a -> 'b -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
val fold2_left: ('a -> key -> 'b option -> 'c option -> 'a) -> 'a -> 'b t -> 'c t -> 'a
val fold2_right: (key -> 'a option -> 'b option -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
val fold2_both_left: ('a -> key -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a
val fold2_both_right: (key -> 'a -> 'b -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
val compare: 'a t -> 'a t -> int
end
(** Output signature of the functor {!Map.Make}. *)
module Make (Ord : Type.Ordered) : S with type key = Ord.t
(** Functor building an implementation of the map structure
given a totally ordered type. *)