-
Notifications
You must be signed in to change notification settings - Fork 125
/
baseMapSig.ml
235 lines (198 loc) · 7.7 KB
/
baseMapSig.ml
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
(*
Copyright © 2011 MLstate
This file is part of OPA.
OPA is free software: you can redistribute it and/or modify it under the
terms of the GNU Affero General Public License, version 3, as published by
the Free Software Foundation.
OPA is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for
more details.
You should have received a copy of the GNU Affero General Public License
along with OPA. If not, see <http://www.gnu.org/licenses/>.
*)
module type S =
sig
type key
type +'a t
val empty : 'a t
val is_empty : 'a t -> bool
val singleton : key -> 'a -> 'a t
(**
Decons un non empty map
*)
val decons : 'a t -> 'a t * key * 'a * 'a t
(**
Overwrites the old value at that key.
*)
val add : key -> 'a -> 'a t -> 'a t
(**
Fails raising [Invalid_argument "Base.Map.safe_add"]
@raise Invalid_argument if the key is already present
*)
val safe_add : key -> 'a -> 'a t -> 'a t
(**
[replace key maping t]
Call the maping function from the previous value contained at that key,
and add the resulting value into the map.
*)
val replace : key -> ('a option -> 'a) -> 'a t -> 'a t
(**
@raise Not_found if the key is not present
*)
val find : key -> 'a t -> 'a
val findi : key -> 'a t -> key * 'a
(**
No exception if the key is not present.
*)
val remove : key -> 'a t -> 'a t
(**
@raise Not_found if the binding to update is not present
*)
val update : key -> ('a -> 'a) -> 'a t -> 'a t
(**
[update_default key updater default map]
Looks for the value of [key] in [map]
- if it is present then, replace it with [updater value]
- or else add the binding [key] -> [default] to the map
*)
val update_default : key -> ('a -> 'a) -> 'a -> 'a t -> 'a t
val mem : key -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val rev_iter : (key -> 'a -> unit) -> 'a t -> unit
(**
Returns an arbitrary element of the map.
@raise Not_found on the empty list
*)
val choose : 'a t -> (key * 'a)
(**
Returns an arbitrary element of the set if it is not_empty, or null
*)
val choose_opt : 'a t -> (key * 'a) option
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
val fold_map : (key -> 'a -> 'c -> 'c * 'b) -> 'a t -> 'c -> 'c * 'b t
val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
(** Takes two sets with the same key and apply the function to the key
and the two values associated.
The key are seen in increasing order
@raise Invalid_argument if the 2 map do not have the same keys
*)
val fold_map2: (key -> 'a -> 'b -> 'acc -> ('acc * 'result)) -> 'a t -> 'b t -> 'acc -> ('acc * 'result t)
(** [fold_range_compare f map kmin kmax acc] Like fold range but
[kmin] and [kmax] are not key type and the range selection is
computed with given [compare] function.
Note : in major cases use [fold_range] ([fold_range_compare
Ord.compare]).
Beware : forall key. [compare kmin key <= compare kmax
key]. *)
val fold_range_compare : ('c -> key -> int) ->
(key -> 'a -> 'b -> 'b) -> 'a t -> 'c -> 'c -> 'b -> 'b
(** [fold_range f map kmin kmax acc] Fold with [f] on [map]
beetween [kmin] and [kmax] includes. [acc |> f kmin vmin |>
... |> f kmax vmax]. *)
val fold_range: (key -> 'a -> 'b -> 'b) -> 'a t -> key -> key -> 'b -> 'b
val fold_length :
start:key -> length:int
-> (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
(** If [length] is negative, [start] is the end.
If [length] is zero the fold is void (accumulator returned).
Time cost is O(log n + length) and memory cost O(log n),
both for balanced trees. Constants are the same as in
DFS restricted to the parts of the tree with the sought keys,
plus all their ancestors, plus a thin margin. *)
val fold_rev : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val filter_keys : (key -> bool) -> 'a t -> 'a t
val filter_val : ('a -> bool) ->'a t -> 'a t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
(**
Check that both map contains the same keys,
and that the binded value is the same,
using the equality function for values
*)
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
module Iter :
(IterSig.S with type +'a element = key * 'a and type +'a structure = 'a t)
module RevIter :
(IterSig.S with type +'a element = key * 'a and type +'a structure = 'a t)
val nearest : key ->' a t -> key * 'a
(**
Find the naearest smaller entry in a map.
@raise Not_found if there is no smaller key in the map
*)
val find_inf : key -> 'a t -> key * 'a
(**
Find the naearest greater entry in a map.
@raise Not_found if there is no smaller key in the map
*)
val find_sup : key -> 'a t -> key * 'a
val from_list : (key * 'a) list -> 'a t
(**
Return an assoc list consitued of all bindings contained
in the map.
<!> The order of elements in the returned list is unspecified.
*)
val to_list : 'a t -> (key * 'a) list
(**
Same than [to_list] but with the guaranty that the assoc list is
sorted by keys, using the order used in the map.
The returned list is in increasing order of keys.
*)
val ordered_list : 'a t -> (key * 'a) list
(**
Same than [List.rev (ordered_list map)] but more efficient.
The returned list is in decreasing order of keys.
*)
val rev_ordered_list : 'a t -> (key * 'a) list
val keys : 'a t -> key list
val elts : 'a t -> 'a list
val random : 'a t -> key * 'a
val size : 'a t -> int
val height : 'a t -> int
val merge_i : (key -> 'a -> 'a -> 'a) -> 'a t -> 'a t -> 'a t
val merge : ('a -> 'a -> 'a) -> 'a t -> 'a t -> 'a t
(**
Fails raising [Invalid_argument "Base.Map.safe_add"].
@raise Invalid_argument is case of conflict
*)
val safe_merge : 'a t -> 'a t -> 'a t
val findi_opt : key -> 'a t -> (key * 'a) option
val find_opt : key -> 'a t -> 'a option
val min : 'a t -> key * 'a
val max : 'a t -> key * 'a
val rename : (key -> key) -> 'a t -> 'a t
(** Binding with Format for printing.
The first argument is a separator which will be
printed after each elt of the set.
If you does not want to see the separator after the last element, use an intermediate
list traduction. *)
val pp : (unit, Format.formatter, unit) format -> (Format.formatter -> key -> 'a -> unit) -> Format.formatter -> 'a t -> unit
(** exporting compare on key from Arg.compare *)
val compare_key : key -> key -> int
(** [diff m1 m2] returns the submap of [m1] containing all the keys that
are in [m1] but not in [m2]
ie it computes [m1 \ m2]
*)
val diff : 'a t -> _ t -> 'a t
(**
[diff2 m1 m2 m3] computes [m1 \ (m2 \ m3)], ie the submap of [m1]
containing all the keys that are in [m3] or not in [m2]
*)
val diff2 : 'a t -> _ t -> _ t -> 'a t
(**
If the two set have different key, give back an element in the left set not
in the right one, or in the right one not in the left one, or None.
See also [BaseSetSig.S.example_diff]
*)
val example_diff : 'a t -> 'a t -> (key * 'a) option
(**
Optimized initialization for huge maps, to avoid temporary unused balancing.
The key array should be sorted in increasing order, using the same order than the set.
The value array should have the same length than the key array.
{[
[| key0 ; key1 ; key2 |] [| val0 ; val1 ; val2 |]
]}
<!> Unoptimized on IntMap
*)
val from_sorted_array : key array -> 'a array -> 'a t
end