sig
  module Key : Comparator.S
  module Tree :
    sig
      type 'a t = (Key.t, 'a, Key.comparator) Tree.t
      val empty : 'a t
      val singleton : Key.t -> 'a -> 'a t
      val of_alist :
        (Key.t * 'a) list -> [ `Duplicate_key of Key.t | `Ok of 'a t ]
      val of_alist_exn : (Key.t * 'a) list -> 'a t
      val of_alist_multi : (Key.t * 'a) list -> 'a list t
      val of_alist_fold :
        (Key.t * 'a) list -> init:'b -> f:('b -> 'a -> 'b) -> 'b t
      val of_alist_reduce : (Key.t * 'a) list -> f:('a -> 'a -> 'a) -> 'a t
      val of_sorted_array : (Key.t * 'a) array -> 'a t Or_error.t
      val of_sorted_array_unchecked : (Key.t * 'a) array -> 'a t
      val of_tree : 'a t -> 'a t
      val invariants : 'a t -> bool
      val is_empty : 'a t -> bool
      val length : 'a t -> int
      val add : 'a t -> key:Key.t -> data:'a -> 'a t
      val add_multi : 'a list t -> key:Key.t -> data:'a -> 'a list t
      val change : 'a t -> Key.t -> ('a option -> 'a option) -> 'a t
      val find : 'a t -> Key.t -> 'a option
      val find_exn : 'a t -> Key.t -> 'a
      val remove : 'a t -> Key.t -> 'a t
      val mem : 'a t -> Key.t -> bool
      val iter : 'a t -> f:(key:Key.t -> data:'a -> unit) -> unit
      val iter2 :
        'a t ->
        'b t ->
        f:(key:Key.t ->
           data:[ `Both of 'a * 'b | `Left of 'a | `Right of 'b ] -> unit) ->
        unit
      val map : 'a t -> f:('a -> 'b) -> 'b t
      val mapi : 'a t -> f:(key:Key.t -> data:'a -> 'b) -> 'b t
      val fold :
        'a t -> init:'b -> f:(key:Key.t -> data:'a -> 'b -> 'b) -> 'b
      val fold_right :
        'a t -> init:'b -> f:(key:Key.t -> data:'a -> 'b -> 'b) -> 'b
      val filter : 'a t -> f:(key:Key.t -> data:'a -> bool) -> 'a t
      val filter_map : 'a t -> f:('a -> 'b option) -> 'b t
      val filter_mapi : 'a t -> f:(key:Key.t -> data:'a -> 'b option) -> 'b t
      val compare_direct : ('a -> 'a -> int) -> 'a t -> 'a t -> int
      val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
      val keys : 'a t -> Key.t list
      val data : 'a t -> 'a list
      val to_alist : 'a t -> (Key.t * 'a) list
      val validate :
        name:(Key.t -> string) -> 'a Validate.check -> 'a t Validate.check
      val merge :
        'a t ->
        'b t ->
        f:(key:Key.t ->
           [ `Both of 'a * 'b | `Left of 'a | `Right of 'b ] -> 'c option) ->
        'c t
      val symmetric_diff :
        'a t ->
        'a t ->
        data_equal:('a -> 'a -> bool) ->
        (Key.t * [ `Left of 'a | `Right of 'a | `Unequal of 'a * 'a ]) list
      val min_elt : 'a t -> (Key.t * 'a) option
      val min_elt_exn : 'a t -> Key.t * 'a
      val max_elt : 'a t -> (Key.t * 'a) option
      val max_elt_exn : 'a t -> Key.t * 'a
      val for_all : 'a t -> f:('a -> bool) -> bool
      val exists : 'a t -> f:('a -> bool) -> bool
      val fold_range_inclusive :
        'a t ->
        min:Key.t ->
        max:Key.t -> init:'b -> f:(key:Key.t -> data:'a -> 'b -> 'b) -> 'b
      val range_to_alist :
        'a t -> min:Key.t -> max:Key.t -> (Key.t * 'a) list
      val prev_key : 'a t -> Key.t -> (Key.t * 'a) option
      val next_key : 'a t -> Key.t -> (Key.t * 'a) option
      val rank : 'a t -> Key.t -> int option
      val to_tree : 'a t -> 'a t
      val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
      val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
    end
  type 'a t = (Key.t, 'a, Key.comparator) t
  val empty : 'a t
  val singleton : Key.t -> 'a -> 'a t
  val of_alist :
    (Key.t * 'a) list -> [ `Duplicate_key of Key.t | `Ok of 'a t ]
  val of_alist_exn : (Key.t * 'a) list -> 'a t
  val of_alist_multi : (Key.t * 'a) list -> 'a list t
  val of_alist_fold :
    (Key.t * 'a) list -> init:'b -> f:('b -> 'a -> 'b) -> 'b t
  val of_alist_reduce : (Key.t * 'a) list -> f:('a -> 'a -> 'a) -> 'a t
  val of_sorted_array : (Key.t * 'a) array -> 'a t Or_error.t
  val of_sorted_array_unchecked : (Key.t * 'a) array -> 'a t
  val of_tree : 'a Tree.t -> 'a t
  val invariants : 'a t -> bool
  val is_empty : 'a t -> bool
  val length : 'a t -> int
  val add : 'a t -> key:Key.t -> data:'a -> 'a t
  val add_multi : 'a list t -> key:Key.t -> data:'a -> 'a list t
  val change : 'a t -> Key.t -> ('a option -> 'a option) -> 'a t
  val find : 'a t -> Key.t -> 'a option
  val find_exn : 'a t -> Key.t -> 'a
  val remove : 'a t -> Key.t -> 'a t
  val mem : 'a t -> Key.t -> bool
  val iter : 'a t -> f:(key:Key.t -> data:'a -> unit) -> unit
  val iter2 :
    'a t ->
    'b t ->
    f:(key:Key.t ->
       data:[ `Both of 'a * 'b | `Left of 'a | `Right of 'b ] -> unit) ->
    unit
  val map : 'a t -> f:('a -> 'b) -> 'b t
  val mapi : 'a t -> f:(key:Key.t -> data:'a -> 'b) -> 'b t
  val fold : 'a t -> init:'b -> f:(key:Key.t -> data:'a -> 'b -> 'b) -> 'b
  val fold_right :
    'a t -> init:'b -> f:(key:Key.t -> data:'a -> 'b -> 'b) -> 'b
  val filter : 'a t -> f:(key:Key.t -> data:'a -> bool) -> 'a t
  val filter_map : 'a t -> f:('a -> 'b option) -> 'b t
  val filter_mapi : 'a t -> f:(key:Key.t -> data:'a -> 'b option) -> 'b t
  val compare_direct : ('a -> 'a -> int) -> 'a t -> 'a t -> int
  val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
  val keys : 'a t -> Key.t list
  val data : 'a t -> 'a list
  val to_alist : 'a t -> (Key.t * 'a) list
  val validate :
    name:(Key.t -> string) -> 'a Validate.check -> 'a t Validate.check
  val merge :
    'a t ->
    'b t ->
    f:(key:Key.t ->
       [ `Both of 'a * 'b | `Left of 'a | `Right of 'b ] -> 'c option) ->
    'c t
  val symmetric_diff :
    'a t ->
    'a t ->
    data_equal:('a -> 'a -> bool) ->
    (Key.t * [ `Left of 'a | `Right of 'a | `Unequal of 'a * 'a ]) list
  val min_elt : 'a t -> (Key.t * 'a) option
  val min_elt_exn : 'a t -> Key.t * 'a
  val max_elt : 'a t -> (Key.t * 'a) option
  val max_elt_exn : 'a t -> Key.t * 'a
  val for_all : 'a t -> f:('a -> bool) -> bool
  val exists : 'a t -> f:('a -> bool) -> bool
  val fold_range_inclusive :
    'a t ->
    min:Key.t ->
    max:Key.t -> init:'b -> f:(key:Key.t -> data:'a -> 'b -> 'b) -> 'b
  val range_to_alist : 'a t -> min:Key.t -> max:Key.t -> (Key.t * 'a) list
  val prev_key : 'a t -> Key.t -> (Key.t * 'a) option
  val next_key : 'a t -> Key.t -> (Key.t * 'a) option
  val rank : 'a t -> Key.t -> int option
  val to_tree : 'a t -> 'a Tree.t
  val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
  val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
  val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
end