1(**************************************************************************)
2(*                                                                        *)
3(*                                 OCaml                                  *)
4(*                                                                        *)
5(*                       Pierre Chambart, OCamlPro                        *)
6(*           Mark Shinwell and Leo White, Jane Street Europe              *)
7(*                                                                        *)
8(*   Copyright 2013--2016 OCamlPro SAS                                    *)
9(*   Copyright 2014--2016 Jane Street Group LLC                           *)
10(*                                                                        *)
11(*   All rights reserved.  This file is distributed under the terms of    *)
12(*   the GNU Lesser General Public License version 2.1, with the          *)
13(*   special exception on linking described in the file LICENSE.          *)
14(*                                                                        *)
15(**************************************************************************)
16
17(** Uniform interface for common data structures over various things. *)
18
19module type Thing = sig
20  type t
21
22  include Hashtbl.HashedType with type t := t
23  include Map.OrderedType with type t := t
24
25  val output : out_channel -> t -> unit
26  val print : Format.formatter -> t -> unit
27end
28
29module Pair : functor (A : Thing) (B : Thing) -> Thing with type t = A.t * B.t
30
31module type S = sig
32  type t
33
34  module T : Thing with type t = t
35  include Thing with type t := T.t
36
37  module Set : sig
38    include Set.S
39      with type elt = T.t
40      and type t = Set.Make (T).t
41
42    val output : out_channel -> t -> unit
43    val print : Format.formatter -> t -> unit
44    val to_string : t -> string
45    val of_list : elt list -> t
46    val map : (elt -> elt) -> t -> t
47  end
48
49  module Map : sig
50    include Map.S
51      with type key = T.t
52      and type 'a t = 'a Map.Make (T).t
53
54    val filter_map : 'a t -> f:(key -> 'a -> 'b option) -> 'b t
55    val of_list : (key * 'a) list -> 'a t
56
57    (** [disjoint_union m1 m2] contains all bindings from [m1] and
58        [m2]. If some binding is present in both and the associated
59        value is not equal, a Fatal_error is raised *)
60    val disjoint_union : ?eq:('a -> 'a -> bool) -> ?print:(Format.formatter -> 'a -> unit) -> 'a t -> 'a t -> 'a t
61
62    (** [union_right m1 m2] contains all bindings from [m1] and [m2]. If
63        some binding is present in both, the one from [m2] is taken *)
64    val union_right : 'a t -> 'a t -> 'a t
65
66    (** [union_left m1 m2 = union_right m2 m1] *)
67    val union_left : 'a t -> 'a t -> 'a t
68
69    val union_merge : ('a -> 'a -> 'a) -> 'a t -> 'a t -> 'a t
70    val rename : key t -> key -> key
71    val map_keys : (key -> key) -> 'a t -> 'a t
72    val keys : 'a t -> Set.t
73    val data : 'a t -> 'a list
74    val of_set : (key -> 'a) -> Set.t -> 'a t
75    val transpose_keys_and_data : key t -> key t
76    val transpose_keys_and_data_set : key t -> Set.t t
77    val print :
78      (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit
79  end
80
81  module Tbl : sig
82    include Hashtbl.S
83      with type key = T.t
84      and type 'a t = 'a Hashtbl.Make (T).t
85
86    val to_list : 'a t -> (T.t * 'a) list
87    val of_list : (T.t * 'a) list -> 'a t
88
89    val to_map : 'a t -> 'a Map.t
90    val of_map : 'a Map.t -> 'a t
91    val memoize : 'a t -> (key -> 'a) -> key -> 'a
92    val map : 'a t -> ('a -> 'b) -> 'b t
93  end
94end
95
96module Make (T : Thing) : S with type t := T.t
97