-
Notifications
You must be signed in to change notification settings - Fork 270
/
bitvec_order.mli
165 lines (113 loc) · 5.44 KB
/
bitvec_order.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
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
(** Provides comparators for use with Janestreet Libraries.
A comparator is a comparison function paired with a type that
is unique to this function and that acts as the witness of
equality between two comparison functions.
Comparators are extensively used in the Janestreet's suite of
libraries, e.g., Base, Core_kernel, Core, etc. Comparators are
used to create sets, maps, hashtables, to instantiate interfaces,
and algorithms that require comparison.
This module provides two comparators, [ascending] and
[descending], which represent two corresponding orderings, as
well as the [natural] comparator, which is the default ordering
that equals with the [ascending] order, which should be used in
cases where a particular ordering doesn't matter.
This library interface is designed from the point of view of the
library user, to minimize verbosity and maximize readability and
the ease of use.
For example, an empty set is created as
{[let words = Set.empty Bitvec_order.natural]},
and it has type
{[(Bitvec.t,Bitvec_order.natural) set]}
(See the note on comparators below for the old style comparators)
This module also provides (implements) the [Base.Comparator.S]
interface that is required by a few Janestreet functors, in
particular, you can construct the type of a set of bitvectors,
as
{[type t = Set.M(Bitvec_oder)]}, or for a mapping from
bitvectors to OCaml [int] it would be
{[type t = int Map.M(Bitvec_order)]}
And to instantiate the [Comparable.S] interface,
{include Comparable.Make(Bitvec_order)}.
See also, [Bitvec_binprot] that provide support for
the binable interfaces.
Finally, for even more concise and readable syntax we provide
the [Comparators] module that designed to be opened, since it
defines properly prefixed identifiers, which will unlikely clash
with any existing name, so that the above examples could be
expressed
{[
open Bitvec_order.Comparators
let words = Set.empty bitvec_order
type words = (bitvec, bitvec_order) Set.t
let decreasing x y = bitvec_descending.compare x y
]}
{2 The old style comparators}
Historically, the comparator in the Janestreet libraries had two
representations - as a record that contains the [compare]
function, and as a module that contains this record and an
instance of the witness type. The former representation is mostly
used for internal purposes, while the latter is expected in most
of the public functions, like [Set.empty], [Map.empty] in the form
of the first-class module, or in different [Make*] functors. In
this library, when we use the word comparator to refer to the
latter representation, i.e., to the module. When the underlying
comparator record is needed, it could be obtained through the
[comparator] field of the module.
The older versions of Core and Base libraries were accepting the
comparator as a record, so instead of writing
{[Set.empty Bitvec_order.natural]}
the following notation should be used
{[Set.empty Bitvec_order.Natural.comparator]}
*)
type t = Bitvec.t
(** [compare x y] orders [x] and [y] in the natural order. *)
val compare : t -> t -> int
(** type index for the increasing order *)
type ascending
(** type index for the decreasing order *)
type descending
(** we use the increasing order as the natural ordering *)
type natural = ascending
(** a type abbreviation for a comparator packed into a module.
See the note about the historical meaning of the word comparator.
*)
type ('a,'b) comparator = (module Base.Comparator.S
with type t = 'a
and type comparator_witness = 'b)
(** [natural] the packed comparator that sorts in the natural order *)
val natural : (t, natural) comparator
(** [ascending] the packed comparator that sorts in the increasing order *)
val ascending : (t, ascending) comparator
(** [descending] the packed comparator that sorts in the decreasing order *)
val descending : (t, descending) comparator
(** [natural] the comparator that sorts in the natural order *)
module Natural : Base.Comparator.S
with type t = t
and type comparator_witness = natural
(** [natural] the comparator that sorts in the natural order *)
module Ascending : Base.Comparator.S
with type t = t
and type comparator_witness = ascending
(** [natural] the comparator that sorts in the natural order *)
module Descending : Base.Comparator.S
with type t = t
and type comparator_witness = descending
(** provides the natural order by default *)
include Base.Comparator.S
with type t := t
and type comparator_witness = natural
(** Open this module to make the following fields available *)
module Comparators : sig
(** the default ordering for bitvectors *)
type bitvec_order = natural
(** [bitvec_compare x y] orders [x] and [y] in the natural order *)
val bitvec_compare : t -> t -> int
(** [bitvec_equal x y] is true if [x] is equal to [y]. *)
val bitvec_equal : t -> t -> bool
(** [natural] the packed comparator that sorts in the natural order *)
val bitvec_order : (t, natural) comparator
(** [ascending] the packed comparator that sorts in the increasing order *)
val bitvec_ascending : (t, ascending) comparator
(** [descending] the packed comparator that sorts in the decreasing order *)
val bitvec_descending : (t, descending) comparator
end