← Back to branch summary

~ubuntu-branches/debian/sid/frama-c/sid

« back to all changes in this revision

Viewing changes to src/lib/mergemap.mli

  • Committer: Bazaar Package Importer
  • Author(s): Mehdi Dogguy
  • Date: 2009-06-03 08:19:25 UTC
  • Revision ID: james.westby@ubuntu.com-20090603081925-kihvxvt0wy3zc4ar
Tags: upstream-20081201.dfsg
Import upstream version 20081201.dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/lib/mergemap.mli
 
1
(**************************************************************************)
 
2
(*                                                                        *)
 
3
(*  This file is part of Frama-C.                                         *)
 
4
(*                                                                        *)
 
5
(*  Copyright (C) 2007-2008                                               *)
 
6
(*    CEA (Commissariat � l'�nergie Atomique)                             *)
 
7
(*                                                                        *)
 
8
(*  you can redistribute it and/or modify it under the terms of the GNU   *)
 
9
(*  Lesser General Public License as published by the Free Software       *)
 
10
(*  Foundation, version 2.1.                                              *)
 
11
(*                                                                        *)
 
12
(*  It is distributed in the hope that it will be useful,                 *)
 
13
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
 
14
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *)
 
15
(*  GNU Lesser General Public License for more details.                   *)
 
16
(*                                                                        *)
 
17
(*  See the GNU Lesser General Public License version 2.1                 *)
 
18
(*  for more details (enclosed in the file licenses/LGPLv2.1).            *)
 
19
(*                                                                        *)
 
20
(**************************************************************************)
 
21
 
 
22
(* $Id: mergemap.mli,v 1.2 2008/11/04 10:05:05 uid568 Exp $ *)
 
23
 
 
24
(** Association tables over ordered types.
 
25
 
 
26
   This module implements applicative association tables, also known as
 
27
   finite maps or dictionaries, given a total ordering function
 
28
   over the keys.
 
29
   All operations over maps are purely applicative (no side-effects).
 
30
   The implementation uses balanced binary trees, and therefore searching
 
31
   and insertion take time logarithmic in the size of the map. 
 
32
*)
 
33
 
 
34
module type S =
 
35
  sig
 
36
    type key
 
37
    (** The type of the map keys. *)
 
38
 
 
39
    type (+'a) t
 
40
    (** The type of maps from type [key] to type ['a]. *)
 
41
 
 
42
    val empty: 'a t
 
43
    (** The empty map. *)
 
44
 
 
45
    val is_empty: 'a t -> bool
 
46
    (** Test whether a map is empty or not. *)
 
47
 
 
48
    val add: key -> 'a -> 'a t -> 'a t
 
49
    (** [add x y m] returns a map containing the same bindings as
 
50
       [m], plus a binding of [x] to [y]. If [x] was already bound
 
51
       in [m], its previous binding disappears. *)
 
52
 
 
53
    val find: key -> 'a t -> 'a
 
54
    (** [find x m] returns the current binding of [x] in [m],
 
55
       or raises [Not_found] if no such binding exists. *)
 
56
 
 
57
    val remove: key -> 'a t -> 'a t
 
58
    (** [remove x m] returns a map containing the same bindings as
 
59
       [m], except for [x] which is unbound in the returned map. *)
 
60
 
 
61
    val mem: key -> 'a t -> bool
 
62
    (** [mem x m] returns [true] if [m] contains a binding for [x],
 
63
       and [false] otherwise. *)
 
64
 
 
65
    val iter: (key -> 'a -> unit) -> 'a t -> unit
 
66
    (** [iter f m] applies [f] to all bindings in map [m].
 
67
       [f] receives the key as first argument, and the associated value
 
68
       as second argument.  The bindings are passed to [f] in increasing
 
69
       order with respect to the ordering over the type of the keys.
 
70
       Only current bindings are presented to [f]:
 
71
       bindings hidden by more recent bindings are not passed to [f]. *)
 
72
 
 
73
    val map: ('a -> 'b) -> 'a t -> 'b t
 
74
    (** [map f m] returns a map with same domain as [m], where the
 
75
       associated value [a] of all bindings of [m] has been
 
76
       replaced by the result of the application of [f] to [a].
 
77
       The bindings are passed to [f] in increasing order
 
78
       with respect to the ordering over the type of the keys. *)
 
79
 
 
80
    val mapi: (key -> 'a -> 'b) -> 'a t -> 'b t
 
81
    (** Same as {!Map.S.map}, but the function receives as arguments both the
 
82
       key and the associated value for each binding of the map. *)
 
83
 
 
84
    val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
 
85
    (** [fold f m a] computes [(f kN dN ... (f k1 d1 a)...)],
 
86
       where [k1 ... kN] are the keys of all bindings in [m]
 
87
       (in increasing order), and [d1 ... dN] are the associated data. *)
 
88
 
 
89
    val compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int
 
90
    (** Total ordering between maps.  The first argument is a total ordering
 
91
        used to compare data associated with equal keys in the two maps. *)
 
92
 
 
93
    val equal: ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
 
94
    (** [equal cmp m1 m2] tests whether the maps [m1] and [m2] are
 
95
       equal, that is, contain equal keys and associate them with
 
96
       equal data.  [cmp] is the equality predicate used to compare
 
97
       the data associated with the keys. *)
 
98
 
 
99
    val fold2 :  ?skip:('a t -> 'b t -> bool) -> 
 
100
      ('a option -> 'b option -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
 
101
      (* fold on two maps at a time skipping some subtrees. *)
 
102
 
 
103
  end
 
104
(** Output signature of the functor {!Map.Make}. *)
 
105
 
 
106
module Make (Ord : Map.OrderedType) : S with type key = Ord.t
 
107
(** Functor building an implementation of the map structure
 
108
   given a totally ordered type. *)
 
109