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. *) |
---|