extracted/untrusted/myMap.mli

   1 (***********************************************************************)
   2 (*                                                                     *)
   3 (*                           Objective Caml                            *)
   4 (*                                                                     *)
   5 (*            Xavier Leroy, projet Cristal, INRIA Rocquencourt         *)
   6 (*                                                                     *)
   7 (*  Copyright 1996 Institut National de Recherche en Informatique et   *)
   8 (*  en Automatique.  All rights reserved.  This file is distributed    *)
   9 (*  under the terms of the GNU Library General Public License, with    *)
  10 (*  the special exception on linking described in file ../LICENSE.     *)
  11 (*                                                                     *)
  12 (***********************************************************************)
  13
  14 (* $Id: myMap.mli,v 1.3 2006/02/17 16:19:52 pottier Exp $ *)
  15
  16 (** Association tables over ordered types.
  17
  18    This module implements applicative association tables, also known as
  19    finite maps or dictionaries, given a total ordering function
  20    over the keys.
  21    All operations over maps are purely applicative (no side-effects).
  22    The implementation uses balanced binary trees, and therefore searching
  23    and insertion take time logarithmic in the size of the map.
  24 *)
  25
  26 module type OrderedType =
  27   sig
  28     type t
  29       (** The type of the map keys. *)
  30     val compare : t -> t -> int
  31       (** A total ordering function over the keys.
  32           This is a two-argument function [f] such that
  33           [f e1 e2] is zero if the keys [e1] and [e2] are equal,
  34           [f e1 e2] is strictly negative if [e1] is smaller than [e2],
  35           and [f e1 e2] is strictly positive if [e1] is greater than [e2].
  36           Example: a suitable ordering function is the generic structural
  37           comparison function {!Pervasives.compare}. *)
  38   end
  39 (** Input signature of the functor {!Map.Make}. *)
  40
  41 module type S =
  42   sig
  43     type key
  44     (** The type of the map keys. *)
  45
  46     type (+'a) t
  47     (** The type of maps from type [key] to type ['a]. *)
  48
  49     val empty: 'a t
  50     (** The empty map. *)
  51
  52     val is_empty: 'a t -> bool
  53     (** Test whether a map is empty or not. *)
  54
  55     val add: key -> 'a -> 'a t -> 'a t
  56     (** [add x y m] returns a map containing the same bindings as
  57        [m], plus a binding of [x] to [y]. If [x] was already bound
  58        in [m], its previous binding disappears. *)
  59
  60     val find: key -> 'a t -> 'a
  61     (** [find x m] returns the current binding of [x] in [m],
  62        or raises [Not_found] if no such binding exists. *)
  63
  64     val remove: key -> 'a t -> 'a t
  65     (** [remove x m] returns a map containing the same bindings as
  66        [m], except for [x] which is unbound in the returned map. *)
  67
  68     val mem: key -> 'a t -> bool
  69     (** [mem x m] returns [true] if [m] contains a binding for [x],
  70        and [false] otherwise. *)
  71
  72     val iter: (key -> 'a -> unit) -> 'a t -> unit
  73     (** [iter f m] applies [f] to all bindings in map [m].
  74        [f] receives the key as first argument, and the associated value
  75        as second argument.  The bindings are passed to [f] in increasing
  76        order with respect to the ordering over the type of the keys.
  77        Only current bindings are presented to [f]:
  78        bindings hidden by more recent bindings are not passed to [f]. *)
  79
  80     val map: ('a -> 'b) -> 'a t -> 'b t
  81     (** [map f m] returns a map with same domain as [m], where the
  82        associated value [a] of all bindings of [m] has been
  83        replaced by the result of the application of [f] to [a].
  84        The bindings are passed to [f] in increasing order
  85        with respect to the ordering over the type of the keys. *)
  86
  87     val mapi: (key -> 'a -> 'b) -> 'a t -> 'b t
  88     (** Same as {!Map.S.map}, but the function receives as arguments both the
  89        key and the associated value for each binding of the map. *)
  90
  91     val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
  92     (** [fold f m a] computes [(f kN dN ... (f k1 d1 a)...)],
  93        where [k1 ... kN] are the keys of all bindings in [m]
  94        (in increasing order), and [d1 ... dN] are the associated data. *)
  95
  96     val compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int
  97     (** Total ordering between maps.  The first argument is a total ordering
  98         used to compare data associated with equal keys in the two maps. *)
  99
 100     val equal: ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
 101     (** [equal cmp m1 m2] tests whether the maps [m1] and [m2] are
 102        equal, that is, contain equal keys and associate them with
 103        equal data.  [cmp] is the equality predicate used to compare
 104        the data associated with the keys. *)
 105
 106     type interval =
 107         key option * key option
 108     (** A type of key intervals. An interval consists of a lower bound
 109        and an upper bound, each of which can be absent. A key is
 110        considered to lie within the interval if it is both greater than
 111        (or equal to) the lower bound (if present) and less than (or
 112        equal to) the upper bound (if present). *)
 113
 114     val split: interval -> 'a t -> 'a t
 115     (* [split interval m] is a map that consists of all bindings in [m]
 116        whose keys lie within [interval]. *)
 117
 118     val minimum: 'a t -> key * 'a
 119     (* [minimum m] returns the binding that corresponds to the minimum
 120        (smallest) key within the map [m]. If [m] is empty, [Not_found]
 121        is raised. *)
 122
 123     val find_remove: key -> 'a t -> 'a * 'a t
 124     (** [find_remove x m] returns a pair of the current binding of [x]
 125         in [m], and a map containing the same bindings as [m], except
 126         for [x] which is unbound in the returned map. [Not_found] is
 127         raised if no binding for [x] exists. *)
 128
 129     val update: key -> ('a -> 'a) -> 'a t -> 'a t
 130     (** If [m] maps [x] to [d], then [update x f m] maps [x] to [f d]
 131         and coincides with [m] elsewhere. A binding for [x] in [m]
 132         must exist. *)
 133
 134     val restrict: (key -> bool) -> 'a t -> 'a t
 135     (** [restrict p m] is the restriction of the map [m] to only
 136         the keys that satisfy predicate [p]. *)
 137
 138   end
 139 (** Output signature of the functor {!Map.Make}. *)
 140
 141 module Make (Ord : OrderedType) : S with type key = Ord.t
 142 (** Functor building an implementation of the map structure
 143    given a totally ordered type. *)