-
Notifications
You must be signed in to change notification settings - Fork 125
/
sortHashtbl.mli
82 lines (67 loc) · 1.97 KB
/
sortHashtbl.mli
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
(*
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/>.
*)
(**
Hashtbl with sorted wrt their input order.
@author Mathieu Barbin
*)
(**
this structure comes when :
+ you don't need to remove elt, (just replace)
+ you want to find quickly elt from keys
+ you want to preserve input ordered in iter and fold
+ you need both rev and normal quick and tail
+ you dont care about the size of the table. (we use several redondant
structures for keeping the tail recusive for folding in both direction)
*)
type ('a, 'b) t
val create : int -> ('a, 'b) t
val clear : ('a, 'b) t -> unit
val add : ('a, 'b) t -> 'a -> 'b -> unit
val replace : ('a, 'b) t -> 'a -> 'b -> unit
(**
Same complexity than [Hashtbl.find]
*)
val find_opt : ('a, 'b) t -> 'a -> 'b option
(**
tail rec, O(n)
*)
val to_list : ('a, 'b) t -> ('a * 'b) list
(**
tail rec, O(n)
*)
val to_rev_list : ('a, 'b) t -> ('a * 'b) list
(**
Same complexity than [Hashtbl.mem]
*)
val mem : ('a, 'b) t -> 'a -> bool
(**
tail rec, O(n)
*)
val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
(**
tail rec, O(n)
*)
val rev_iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
(**
tail rec, O(n)
*)
val fold_left : ('a -> 'b -> 'c -> 'a) -> 'a -> ('b, 'c) t -> 'a
(**
tail rec, O(n)
*)
val fold_right : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
(**
Same complexity than [Hashtbl.length]
*)
val length : ('a, 'b) t -> int