gMap.ml 5.47 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
module type S = sig

  (* Keys are assumed to have a natural total order. *)

  type key

  (* The type of maps whose data have type ['a]. *)

  type 'a t

  (* The empty map. *)

  val empty: 'a t

  (* [lookup k m] looks up the value associated to the key [k] in the
     map [m], and raises [Not_found] if no value is bound to [k]. *)

  val lookup: key -> 'a t -> 'a
  val find: key -> 'a t -> 'a

  (* [add k d m] returns a map whose bindings are all bindings in [m],
     plus a binding of the key [k] to the datum [d]. If a binding
     already exists for [k], it is overridden. *)

  val add: key -> 'a -> 'a t -> 'a t

  (* [strict_add k d m] returns a map whose bindings are all bindings
     in [m], plus a binding of the key [k] to the datum [d]. If a
     binding already exists for [k] then [Unchanged] is raised. *)

  exception Unchanged

  val strict_add: key -> 'a -> 'a t -> 'a t

  (* [fine_add decide k d m] returns a map whose bindings are all
     bindings in [m], plus a binding of the key [k] to the datum
     [d]. If a binding from [k] to [d0] already exists, then the
     resulting map contains a binding from [k] to [decide d0 d]. *)

  type 'a decision = 'a -> 'a -> 'a

  val fine_add: 'a decision -> key -> 'a -> 'a t -> 'a t

  (* [mem k m] tells whether the key [k] appears in the domain of the
     map [m]. *)

  val mem: key -> 'a t -> bool

  (* [singleton k d] returns a map whose only binding is from [k] to [d]. *)

  val singleton: key -> 'a -> 'a t

  (* [is_empty m] returns [true] if and only if the map [m] defines no
     bindings at all. *)

  val is_empty: 'a t -> bool

  (* [is_singleton s] returns [Some x] if [s] is a singleton
     containing [x] as its only element; otherwise, it returns
     [None]. *)

  val is_singleton: 'a t -> (key * 'a) option

  (* [cardinal m] returns [m]'s cardinal, that is, the number of keys
     it binds, or, in other words, the cardinal of its domain. *)

  val cardinal: 'a t -> int

  (* [choose m] returns an arbitrarily chosen binding in [m], if [m]
     is nonempty, and raises [Not_found] otherwise. *)

  val choose: 'a t -> key * 'a

  (* [lookup_and_remove k m] looks up the value [v] associated to the
     key [k] in the map [m], and raises [Not_found] if no value is
     bound to [k]. The call returns the value [v], together with the
     map [m] deprived from the binding from [k] to [v]. *)

  val lookup_and_remove: key -> 'a t -> 'a * 'a t
  val find_and_remove: key -> 'a t -> 'a * 'a t

  (* [remove k m] is the map [m] deprived from any binding for [k]. *)

  val remove: key -> 'a t -> 'a t

  (* [union m1 m2] returns the union of the maps [m1] and
     [m2]. Bindings in [m2] take precedence over those in [m1]. *)

  val union: 'a t -> 'a t -> 'a t

  (* [fine_union decide m1 m2] returns the union of the maps [m1] and
     [m2]. If a key [k] is bound to [x1] (resp. [x2]) within [m1]
     (resp. [m2]), then [decide] is called. It is passed [x1] and
     [x2], and must return the value that shall be bound to [k] in the
     final map. *)

  val fine_union: 'a decision -> 'a t -> 'a t -> 'a t

  (* [iter f m] invokes [f k x], in turn, for each binding from key
     [k] to element [x] in the map [m]. Keys are presented to [f] in
     increasing order. *)

  val iter: (key -> 'a -> unit) -> 'a t -> unit

  (* [fold f m seed] invokes [f k d accu], in turn, for each binding
     from key [k] to datum [d] in the map [m]. Keys are presented to
     [f] in increasing order. The initial value of [accu] is [seed];
     then, at each new call, its value is the value returned by the
     previous invocation of [f]. The value returned by [fold] is the
     final value of [accu]. *)

  val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

  (* [fold_rev] performs exactly the same job as [fold], but presents
     keys to [f] in the opposite order. *)

  val fold_rev: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

  (* It is valid to evaluate [iter2 f m1 m2] if and only if [m1] and
     [m2] have equal domains. Doing so invokes [f k x1 x2], in turn,
     for each key [k] bound to [x1] in [m1] and to [x2] in
     [m2]. Bindings are presented to [f] in increasing order. *)

  val iter2: (key -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit

  (* [map f m] returns the map obtained by composing the map [m] with
     the function [f]; that is, the map $k\mapsto f(m(k))$. *)

  val map: ('a -> 'b) -> 'a t -> 'b t

  (* [endo_map] is similar to [map], but attempts to physically share
     its result with its input. This saves memory when [f] is the
     identity function. *)

  val endo_map: ('a -> 'a) -> 'a t -> 'a t

  (* If [dcompare] is an ordering over data, then [compare dcompare]
     is an ordering over maps. *)

  val compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int

  (* A map's domain is a set. Thus, to be able to perform operations
     on domains, we need set operations, provided by the [Domain]
     sub-module. The two-way connection between maps and their domains
     is given by two additional functions, [domain] and
     [lift]. [domain m] returns [m]'s domain. [lift f s] returns the
     map $k\mapsto f(k)$, where $k$ ranges over a set of keys [s]. *)

  module Domain : GSet.S with type element = key

  val domain: 'a t -> Domain.t
  val lift: (key -> 'a) -> Domain.t -> 'a t

  (* [corestrict m d] performs a co-restriction of the map [m] to the
     domain [d]. That is, it returns the map $k\mapsto m(k)$, where
     $k$ ranges over all keys bound in [m] but \emph{not} present in
     [d]. *)

  val corestrict: 'a t -> Domain.t -> 'a t

end