stdlib.mli 17.7 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
(***********************************************************************)
(*                                                                     *)
(*                           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 10483 2010-05-31 12:48:13Z doligez $ *)

François Bobot's avatar
François Bobot committed
16 17
module Map : sig

18 19 20 21 22 23 24 25 26 27 28 29 30
(** 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 OrderedType =
  sig
    type t
Andrei Paskevich's avatar
Andrei Paskevich committed
31 32
    (** The type of the map keys. *)

33
    val compare : t -> t -> int
Andrei Paskevich's avatar
Andrei Paskevich committed
34 35 36 37 38 39 40
    (** A total ordering function over the keys.
        This is a two-argument function [f] such that
        [f e1 e2] is zero if the keys [e1] and [e2] are equal,
        [f e1 e2] is strictly negative if [e1] is smaller than [e2],
        and [f e1 e2] is strictly positive if [e1] is greater than [e2].
        Example: a suitable ordering function is the generic structural
        comparison function {!Pervasives.compare}. *)
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
  end
(** Input signature of the functor {!Map.Make}. *)

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 empty: 'a t
    (** The empty map. *)

    val is_empty: 'a t -> bool
    (** Test whether a map is empty or not. *)

    val mem: key -> 'a t -> bool
    (** [mem x m] returns [true] if [m] contains a binding for [x],
Andrei Paskevich's avatar
Andrei Paskevich committed
60
        and [false] otherwise. *)
61 62 63

    val add: key -> 'a -> 'a t -> 'a t
    (** [add x y m] returns a map containing the same bindings as
Andrei Paskevich's avatar
Andrei Paskevich committed
64 65
        [m], plus a binding of [x] to [y]. If [x] was already bound
        in [m], its previous binding disappears. *)
66 67 68 69

    val singleton: key -> 'a -> 'a t
    (** [singleton x y] returns the one-element map that contains a binding [y]
        for [x].
Andrei Paskevich's avatar
Andrei Paskevich committed
70
        @since 3.12.0 *)
71 72 73

    val remove: key -> 'a t -> 'a t
    (** [remove x m] returns a map containing the same bindings as
Andrei Paskevich's avatar
Andrei Paskevich committed
74
        [m], except for [x] which is unbound in the returned map. *)
75 76 77 78 79 80

    val merge:
         (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
    (** [merge f m1 m2] computes a map whose keys is a subset of keys of [m1]
        and of [m2]. The presence of each such binding, and the corresponding
        value, is determined with the function [f].
Andrei Paskevich's avatar
Andrei Paskevich committed
81
        @since 3.12.0 *)
82 83 84 85 86 87 88

    val compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int
    (** Total ordering between maps.  The first argument is a total ordering
        used to compare data associated with equal keys in the two maps. *)

    val equal: ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
    (** [equal cmp m1 m2] tests whether the maps [m1] and [m2] are
Andrei Paskevich's avatar
Andrei Paskevich committed
89 90 91
        equal, that is, contain equal keys and associate them with
        equal data.  [cmp] is the equality predicate used to compare
        the data associated with the keys. *)
92 93 94 95 96 97 98 99

    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 bindings are passed to [f] in increasing
       order with respect to the ordering over the type of the keys. *)

    val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
Andrei Paskevich's avatar
Andrei Paskevich committed
100 101 102
    (** [fold f m a] computes [(f kN dN ... (f k1 d1 a)...)], where
        [k1 ... kN] are the keys of all bindings in [m] (in increasing
        order), and [d1 ... dN] are the associated data. *)
103 104 105 106

    val for_all: (key -> 'a -> bool) -> 'a t -> bool
    (** [for_all p m] checks if all the bindings of the map
        satisfy the predicate [p].
Andrei Paskevich's avatar
Andrei Paskevich committed
107
        @since 3.12.0 *)
108 109 110 111

    val exists: (key -> 'a -> bool) -> 'a t -> bool
    (** [exists p m] checks if at least one binding of the map
        satisfy the predicate [p].
Andrei Paskevich's avatar
Andrei Paskevich committed
112
        @since 3.12.0 *)
113 114 115 116

    val filter: (key -> 'a -> bool) -> 'a t -> 'a t
    (** [filter p m] returns the map with all the bindings in [m]
        that satisfy predicate [p].
Andrei Paskevich's avatar
Andrei Paskevich committed
117
        @since 3.12.0 *)
118 119 120 121 122 123

    val partition: (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
    (** [partition p m] returns a pair of maps [(m1, m2)], where
        [m1] contains all the bindings of [s] that satisfy the
        predicate [p], and [m2] is the map with all the bindings of
        [s] that do not satisfy [p].
Andrei Paskevich's avatar
Andrei Paskevich committed
124
        @since 3.12.0 *)
125 126 127

    val cardinal: 'a t -> int
    (** Return the number of bindings of a map.
Andrei Paskevich's avatar
Andrei Paskevich committed
128
        @since 3.12.0 *)
129 130 131

    val bindings: 'a t -> (key * 'a) list
    (** Return the list of all bindings of the given map.
Andrei Paskevich's avatar
Andrei Paskevich committed
132 133 134 135
        The returned list is sorted in increasing order with respect
        to the ordering [Ord.compare], where [Ord] is the argument
        given to {!Map.Make}.
        @since 3.12.0 *)
136 137 138

    val min_binding: 'a t -> (key * 'a)
    (** Return the smallest binding of the given map
Andrei Paskevich's avatar
Andrei Paskevich committed
139 140 141
        (with respect to the [Ord.compare] ordering), or raise
        [Not_found] if the map is empty.
        @since 3.12.0 *)
142 143

    val max_binding: 'a t -> (key * 'a)
Andrei Paskevich's avatar
Andrei Paskevich committed
144 145 146
    (** Same as {!Map.S.max_binding}, but returns the largest
        binding of the given map.
        @since 3.12.0 *)
147 148 149

    val choose: 'a t -> (key * 'a)
    (** Return one binding of the given map, or raise [Not_found] if
Andrei Paskevich's avatar
Andrei Paskevich committed
150 151 152
        the map is empty. Which binding is chosen is unspecified,
        but equal bindings will be chosen for equal maps.
        @since 3.12.0 *)
153 154 155 156 157 158 159 160 161

    val split: key -> 'a t -> 'a t * 'a option * 'a t
    (** [split x m] returns a triple [(l, data, r)], where
          [l] is the map with all the bindings of [m] whose key
        is strictly less than [x];
          [r] is the map with all the bindings of [m] whose key
        is strictly greater than [x];
          [data] is [None] if [m] contains no binding for [x],
          or [Some v] if [m] binds [v] to [x].
Andrei Paskevich's avatar
Andrei Paskevich committed
162
        @since 3.12.0 *)
163 164 165

    val find: key -> 'a t -> 'a
    (** [find x m] returns the current binding of [x] in [m],
Andrei Paskevich's avatar
Andrei Paskevich committed
166
        or raises [Not_found] if no such binding exists. *)
167 168

    val map: ('a -> 'b) -> 'a t -> 'b t
Andrei Paskevich's avatar
Andrei Paskevich committed
169 170 171 172 173
    (** [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 bindings are passed to [f] in increasing order
        with respect to the ordering over the type of the keys. *)
174 175

    val mapi: (key -> 'a -> 'b) -> 'a t -> 'b t
Andrei Paskevich's avatar
Andrei Paskevich committed
176 177
    (** Same as {!Map.S.map}, but the function receives as arguments both
        the key and the associated value for each binding of the map. *)
178 179


180 181
    (** {3} Added into why stdlib version *)

182 183 184
    val is_num_elt : int -> 'a t -> bool
    (** check if the map has the given number of elements *)

185 186
    val change : ('a option -> 'a option) -> key -> 'a t -> 'a t
    (** [change f x m] returns a map containing the same bindings as
187 188 189 190
        [m], except the binding of [x] in [m] is changed from [y] to
        [f (Some y)] if [m] contains a binding of [x], otherwise the
        binding of [x] becomes [f None].

191
        [change f x m] corresponds to a more efficient way to do
192 193 194
        [match (try f (Some (find x m)) with Not_found -> f None) with
          | None -> m
          | Some v -> add x v] *)
195 196

    val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
Andrei Paskevich's avatar
Andrei Paskevich committed
197 198 199 200
    (** [union f m1 m2] computes a map whose keys is a subset of keys
        of [m1] and of [m2]. If a binding is present in [m1] (resp. [m2])
        and not in [m2] (resp. [m1]) the same binding is present in
        the result. The function [f] is called only in ambiguous cases. *)
201

202 203
    val inter : (key -> 'a -> 'b -> 'c option) -> 'a t -> 'b t -> 'c t
    (** [inter f m1 m2] computes a map whose keys is a subset of
Andrei Paskevich's avatar
Andrei Paskevich committed
204
        the intersection of keys of [m1] and of [m2]. *)
205

206 207 208 209 210 211 212
    val diff : (key -> 'a -> 'b -> 'a option) -> 'a t -> 'b t -> 'a t
    (** [diff f m1 m2] computes a map whose keys is a subset of keys
        of [m1]. [f] is applied on key which belongs to [m1] and [m2]
        if [f] returns [None] the binding is removed from [m1],
        otherwise [Some d1] is returned, the key binds to [d1] in [m1] *)

    val submap : (key -> 'a -> 'b -> bool) -> 'a t -> 'b t -> bool
Andrei Paskevich's avatar
Andrei Paskevich committed
213 214
    (** [submap pr m1 m2] verifies that all the keys in m1 are in m2
        and that for each such binding pr is verified. *)
215

216 217 218 219
    val disjoint : (key -> 'a -> 'b -> bool) -> 'a t -> 'b t -> bool
    (** [disjoint pr m1 m2] verifies that for every common key in m1
        and m2, pr is verified. *)

220 221 222
    val set_union : 'a t -> 'a t -> 'a t
    (** [set_union = union (fun _ x _ -> Some x)] *)

223 224 225 226 227 228 229 230 231
    val set_inter : 'a t -> 'b t -> 'a t
    (** [set_inter = inter (fun _ x _ -> Some x)] *)

    val set_diff : 'a t -> 'b t -> 'a t
    (** [set_diff = diff (fun _ _ _ -> None)] *)

    val set_submap : 'a t -> 'b t -> bool
    (** [set_submap = submap (fun _ _ _ -> true)] *)

232 233 234
    val set_disjoint : 'a t -> 'b t -> bool
    (** [set_disjoint = disjoint (fun _ _ _ -> false)] *)

235 236
    val find_def : 'a -> key -> 'a t -> 'a
    (** [find_def x d m] returns the current binding of [x] in [m],
237 238
        or return [d] if no such binding exists. *)

239 240
    val find_opt : key -> 'a t -> 'a option
    (** [find_opt x m] returns the [Some] of the current binding
241 242
        of [x] in [m], or return [None] if no such binding exists. *)

243 244 245 246
    val find_exn : exn -> key -> 'a t -> 'a
    (** [find_exn exn x d m] returns the current binding
        of [x] in [m], or raise [exn] if no such binding exists. *)

247 248 249 250 251 252
    val map_filter: ('a -> 'b option) -> 'a t -> 'b t
    (** Same as {!Map.S.map}, but may remove bindings. *)

    val mapi_filter: (key -> 'a -> 'b option) -> 'a t -> 'b t
    (** Same as {!Map.S.mapi}, but may remove bindings. *)

François Bobot's avatar
François Bobot committed
253
    val mapi_fold:
254
      (key -> 'a -> 'acc -> 'acc * 'b) -> 'a t -> 'acc -> 'acc * 'b t
255 256
    (** fold and map at the same time *)

257 258 259
    val fold2_inter: (key -> 'a -> 'b -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
    (** fold the common keys of two map at the same time *)

260 261 262
    val fold2_union:
      (key -> 'a option -> 'b option -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
    (** fold the keys which appear in one of the two maps *)
263

264 265 266 267 268
    val translate : (key -> key) -> 'a t -> 'a t
    (** [translate f m] translates the keys in the map [m] by the
        function [f]. [f] must be strictly monotone on the key of [m].
        Otherwise it raises invalid_arg *)

269 270 271 272
    val mapi_filter_fold:
      (key -> 'a -> 'acc -> 'acc * 'b option) -> 'a t -> 'acc -> 'acc * 'b t
    (** Same as {!Map.S.mapi_fold}, but may remove bindings. *)

273 274 275
    val add_new : exn -> key -> 'a -> 'a t -> 'a t
    (** [add_new e x v m] binds [x] to [v] in [m] if [x] is not bound,
        and raises [e] otherwise. *)
276

277 278 279 280 281 282 283 284 285 286 287 288
    val keys: 'a t -> key list
    (** Return the list of all keys of the given map.
        The returned list is sorted in increasing order with respect
        to the ordering [Ord.compare], where [Ord] is the argument
        given to {!Map.Make}. *)

    val values: 'a t -> 'a list
    (** Return the list of all values of the given map.
        The returned list is sorted in increasing order with respect
        to the ordering [Ord.compare] of the keys, where [Ord] is the argument
        given to {!Map.Make}. *)

289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
    (** enumeration: zipper style *)
    type 'a enumeration

    val val_enum : 'a enumeration -> (key * 'a) option
    (** get the current key value pair of the enumeration, return None
        if the enumeration reach the end *)

    val start_enum : 'a t -> 'a enumeration
    (** start the enumeration of the given map *)

    val next_enum : 'a enumeration -> 'a enumeration
    (** get the next step of the enumeration *)

    val start_ge_enum : key -> 'a t -> 'a enumeration
    (** start the enumeration of the given map at the first key which
        is greater or equal than the given one *)

    val next_ge_enum : key -> 'a enumeration -> 'a enumeration
    (** get the next (or same) step of the enumeration which key is
        greater or equal to the given key *)

310 311 312 313 314 315 316 317
    module type Set =
    sig
      type elt = key
      type set = unit t
      type t = set
      (** The type of sets of type [elt]. *)

      val empty: t
Andrei Paskevich's avatar
Andrei Paskevich committed
318
      (** The empty set. *)
319 320

      val is_empty: t -> bool
Andrei Paskevich's avatar
Andrei Paskevich committed
321
      (** Test whether a set is empty or not. *)
322 323

      val mem: elt -> t -> bool
Andrei Paskevich's avatar
Andrei Paskevich committed
324 325
      (** [mem x s] returns [true] if [s] contains [x],
          and [false] otherwise. *)
326 327

      val add: elt -> t -> t
Andrei Paskevich's avatar
Andrei Paskevich committed
328 329
      (** [add x s] returns a set containing the same elements as
          [s], plus [x]. *)
330 331

      val singleton: elt -> t
Andrei Paskevich's avatar
Andrei Paskevich committed
332
      (** [singleton x] returns the one-element set that contains [x]. *)
333 334

      val remove: elt -> t -> t
Andrei Paskevich's avatar
Andrei Paskevich committed
335 336
      (** [remove x s] returns a set containing the same elements as [s],
          except for [x]. *)
337 338

      val merge: (elt -> bool -> bool -> bool) -> t -> t -> t
Andrei Paskevich's avatar
Andrei Paskevich committed
339 340 341
      (** [merge f s1 s2] computes a set whose elts is a subset of elts
          of [s1] and of [s2]. The presence of each such element is
          determined with the function [f]. *)
342 343

      val compare: t -> t -> int
Andrei Paskevich's avatar
Andrei Paskevich committed
344
      (** Total ordering between sets. *)
345 346

      val equal: t -> t -> bool
Andrei Paskevich's avatar
Andrei Paskevich committed
347
      (** [equal s1 s2] tests whether the sets [s1] and [s2] are equal. *)
348 349

      val subset: t -> t -> bool
Andrei Paskevich's avatar
Andrei Paskevich committed
350
      (** [subset s1 s2] tests whether the set [s1] is a subset of [s2]. *)
351

352 353 354 355
      val disjoint: t -> t -> bool
      (** [disjoint s1 s2] tests whether the sets [s1] and [s2]
          are disjoint. *)

356
      val iter: (elt -> unit) -> t -> unit
Andrei Paskevich's avatar
Andrei Paskevich committed
357 358 359
      (** [iter f s] applies [f] to all elements of [s].
          The elements are passed to [f] in increasing order with respect
          to the ordering over the type of the elts. *)
360 361

      val fold: (elt -> 'a -> 'a) -> t -> 'a -> 'a
Andrei Paskevich's avatar
Andrei Paskevich committed
362 363
      (** [fold f s a] computes [(f eN ... (f e1 a)...)],
          where [e1 ... eN] are the element of [s] in increasing order. *)
364 365

      val for_all: (elt -> bool) -> t -> bool
Andrei Paskevich's avatar
Andrei Paskevich committed
366 367
      (** [for_all p s] checks if all the elements of [s] satisfy
          the predicate [p]. *)
368 369

      val exists: (elt -> bool) -> t -> bool
Andrei Paskevich's avatar
Andrei Paskevich committed
370 371
      (** [exists p s] checks if at least one element of [s] satisfies
          the predicate [p]. *)
372 373

      val filter: (elt -> bool) -> t -> t
Andrei Paskevich's avatar
Andrei Paskevich committed
374 375
      (** [filter p s] returns the set with all the elements of [s]
          that satisfy predicate [p]. *)
376 377

      val partition: (elt -> bool) -> t -> t * t
Andrei Paskevich's avatar
Andrei Paskevich committed
378 379 380 381
      (** [partition p s] returns a pair of sets [(s1, s2)], where
          [s1] contains all the elements of [s] that satisfy the
          predicate [p], and [s2] is the map with all the elements
          of [s] that do not satisfy [p]. *)
382 383

      val cardinal: t -> int
Andrei Paskevich's avatar
Andrei Paskevich committed
384
      (** Return the number of elements in a set. *)
385 386

      val elements: t -> elt list
Andrei Paskevich's avatar
Andrei Paskevich committed
387 388
      (** Return the list of all elements of the given set.
          The returned list is sorted in increasing order. *)
389 390

      val min_elt: t -> elt
Andrei Paskevich's avatar
Andrei Paskevich committed
391 392
      (** Return the smallest element of the given set or raise
          [Not_found] if the set is empty. *)
393 394

      val max_elt: t -> elt
Andrei Paskevich's avatar
Andrei Paskevich committed
395 396
      (** Return the largest element of the given set or raise
          [Not_found] if the set is empty. *)
397 398

      val choose: t -> elt
Andrei Paskevich's avatar
Andrei Paskevich committed
399 400 401
      (** Return one element of the given set, or raise [Not_found] if
          the set is empty. Which element is chosen is unspecified,
          but equal elements will be chosen for equal sets. *)
402 403

      val split: elt -> t -> t * bool * t
Andrei Paskevich's avatar
Andrei Paskevich committed
404 405 406 407 408 409
      (** [split x s] returns a triple [(l, mem, r)], where
          [l] is the set with all the elements of [s] that are
          strictly less than [x];
          [r] is the set with all the elements of [s] that are
          strictly greater than [x];
          [mem] is [true] if [x] belongs to [s] and [false] otherwise. *)
410

411 412
      val change : (bool -> bool) -> elt -> t -> t
      (** [change f x s] returns a set containing the same elements as
Andrei Paskevich's avatar
Andrei Paskevich committed
413 414
          [s], except [x] which is added to [s] if [f (mem x s)] returns
          [true] and removed otherwise. *)
415 416

      val union : t -> t -> t
Andrei Paskevich's avatar
Andrei Paskevich committed
417
      (** [union f s1 s2] computes the union of two sets *)
418 419

      val inter : t -> t -> t
Andrei Paskevich's avatar
Andrei Paskevich committed
420
      (** [inter f s1 s2] computes the intersection of two sets *)
421 422

      val diff : t -> t -> t
Andrei Paskevich's avatar
Andrei Paskevich committed
423
      (** [diss f s1 s2] computes the difference of two sets *)
François Bobot's avatar
François Bobot committed
424

425
      val fold2:  (elt -> 'a -> 'a) -> t -> t -> 'a -> 'a
426 427
      (** [fold2 f s1 s2 a] computes [(f eN ... (f e1 a) ...)],
          where [e1 ... eN] are the elements of [union s1 s2]
428 429
          in increasing order. *)

430
      val translate : (elt -> elt) -> t -> t
Andrei Paskevich's avatar
Andrei Paskevich committed
431 432 433
      (** [translate f s] translates the elements in the set [s] by the
          function [f]. [f] must be strictly monotone on the elements of [s].
          Otherwise it raises invalid_arg *)
434

435 436 437
      val add_new : exn -> elt -> t -> t
      (** [add_new e x s] adds [x] to [s] if [s] does not contain [x],
          and raises [e] otherwise. *)
438 439 440 441

      val is_num_elt : int -> t -> bool
      (** check if the map has the given number of elements *)

442
    end
443

444
    module Set : Set
445

446
  end
447

448 449
(** Output signature of the functor {!Map.Make}. *)

450
module Make (Ord : OrderedType) : S with type key = Ord.t
451
(** Functor building an implementation of the map/set structure
Andrei Paskevich's avatar
Andrei Paskevich committed
452
    given a totally ordered type. *)
François Bobot's avatar
François Bobot committed
453 454

end