sig
  type 'a sequence = ('a -> unit) -> unit
  type 'a ktree = unit -> [ `Nil | `Node of 'a * 'a CCTrie.ktree list ]
  module type WORD =
    sig
      type t
      type char_
      val compare : CCTrie.WORD.char_ -> CCTrie.WORD.char_ -> int
      val to_seq : CCTrie.WORD.t -> CCTrie.WORD.char_ CCTrie.sequence
      val of_list : CCTrie.WORD.char_ list -> CCTrie.WORD.t
    end
  module type S =
    sig
      type char_
      type key
      type 'a t
      val empty : 'a CCTrie.S.t
      val is_empty : 'a CCTrie.S.t -> bool
      val add : CCTrie.S.key -> 'a -> 'a CCTrie.S.t -> 'a CCTrie.S.t
      val remove : CCTrie.S.key -> 'a CCTrie.S.t -> 'a CCTrie.S.t
      val find : CCTrie.S.key -> 'a CCTrie.S.t -> 'a option
      val find_exn : CCTrie.S.key -> 'a CCTrie.S.t -> 'a
      val longest_prefix : CCTrie.S.key -> 'a CCTrie.S.t -> CCTrie.S.key
      val update :
        CCTrie.S.key ->
        ('a option -> 'a option) -> 'a CCTrie.S.t -> 'a CCTrie.S.t
      val fold :
        ('b -> CCTrie.S.key -> 'a -> 'b) -> 'b -> 'a CCTrie.S.t -> 'b
      val mapi : (CCTrie.S.key -> 'a -> 'b) -> 'a CCTrie.S.t -> 'b CCTrie.S.t
      val map : ('a -> 'b) -> 'a CCTrie.S.t -> 'b CCTrie.S.t
      val iter : (CCTrie.S.key -> 'a -> unit) -> 'a CCTrie.S.t -> unit
      val fold_values : ('b -> 'a -> 'b) -> 'b -> 'a CCTrie.S.t -> 'b
      val iter_values : ('a -> unit) -> 'a CCTrie.S.t -> unit
      val merge :
        ('a -> 'a -> 'a option) ->
        'a CCTrie.S.t -> 'a CCTrie.S.t -> 'a CCTrie.S.t
      val size : 'a CCTrie.S.t -> int
      val to_list : 'a CCTrie.S.t -> (CCTrie.S.key * 'a) list
      val of_list : (CCTrie.S.key * 'a) list -> 'a CCTrie.S.t
      val to_seq : 'a CCTrie.S.t -> (CCTrie.S.key * 'a) CCTrie.sequence
      val of_seq : (CCTrie.S.key * 'a) CCTrie.sequence -> 'a CCTrie.S.t
      val to_seq_values : 'a CCTrie.S.t -> 'a CCTrie.sequence
      val to_tree :
        'a CCTrie.S.t ->
        [ `Char of CCTrie.S.char_ | `Switch | `Val of 'a ] CCTrie.ktree
      val above :
        CCTrie.S.key -> 'a CCTrie.S.t -> (CCTrie.S.key * 'a) CCTrie.sequence
      val below :
        CCTrie.S.key -> 'a CCTrie.S.t -> (CCTrie.S.key * 'a) CCTrie.sequence
      val check_invariants : 'a CCTrie.S.t -> bool
    end
  module Make :
    functor (W : WORD) ->
      sig
        type char_ = W.char_
        type key = W.t
        type 'a t
        val empty : 'a t
        val is_empty : 'a t -> bool
        val add : key -> 'a -> 'a t -> 'a t
        val remove : key -> 'a t -> 'a t
        val find : key -> 'a t -> 'a option
        val find_exn : key -> 'a t -> 'a
        val longest_prefix : key -> 'a t -> key
        val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
        val fold : ('b -> key -> 'a -> 'b) -> 'b -> 'a t -> 'b
        val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
        val map : ('a -> 'b) -> 'a t -> 'b t
        val iter : (key -> 'a -> unit) -> 'a t -> unit
        val fold_values : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
        val iter_values : ('a -> unit) -> 'a t -> unit
        val merge : ('a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
        val size : 'a t -> int
        val to_list : 'a t -> (key * 'a) list
        val of_list : (key * 'a) list -> 'a t
        val to_seq : 'a t -> (key * 'a) sequence
        val of_seq : (key * 'a) sequence -> 'a t
        val to_seq_values : 'a t -> 'a sequence
        val to_tree : 'a t -> [ `Char of char_ | `Switch | `Val of 'a ] ktree
        val above : key -> 'a t -> (key * 'a) sequence
        val below : key -> 'a t -> (key * 'a) sequence
        val check_invariants : 'a t -> bool
      end
  module type ORDERED =
    sig type t val compare : CCTrie.ORDERED.t -> CCTrie.ORDERED.t -> int end
  module MakeArray :
    functor (X : ORDERED) ->
      sig
        type char_ = X.t
        type key = X.t array
        type 'a t
        val empty : 'a t
        val is_empty : 'a t -> bool
        val add : key -> 'a -> 'a t -> 'a t
        val remove : key -> 'a t -> 'a t
        val find : key -> 'a t -> 'a option
        val find_exn : key -> 'a t -> 'a
        val longest_prefix : key -> 'a t -> key
        val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
        val fold : ('b -> key -> 'a -> 'b) -> 'b -> 'a t -> 'b
        val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
        val map : ('a -> 'b) -> 'a t -> 'b t
        val iter : (key -> 'a -> unit) -> 'a t -> unit
        val fold_values : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
        val iter_values : ('a -> unit) -> 'a t -> unit
        val merge : ('a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
        val size : 'a t -> int
        val to_list : 'a t -> (key * 'a) list
        val of_list : (key * 'a) list -> 'a t
        val to_seq : 'a t -> (key * 'a) sequence
        val of_seq : (key * 'a) sequence -> 'a t
        val to_seq_values : 'a t -> 'a sequence
        val to_tree : 'a t -> [ `Char of char_ | `Switch | `Val of 'a ] ktree
        val above : key -> 'a t -> (key * 'a) sequence
        val below : key -> 'a t -> (key * 'a) sequence
        val check_invariants : 'a t -> bool
      end
  module MakeList :
    functor (X : ORDERED) ->
      sig
        type char_ = X.t
        type key = X.t list
        type 'a t
        val empty : 'a t
        val is_empty : 'a t -> bool
        val add : key -> 'a -> 'a t -> 'a t
        val remove : key -> 'a t -> 'a t
        val find : key -> 'a t -> 'a option
        val find_exn : key -> 'a t -> 'a
        val longest_prefix : key -> 'a t -> key
        val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
        val fold : ('b -> key -> 'a -> 'b) -> 'b -> 'a t -> 'b
        val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
        val map : ('a -> 'b) -> 'a t -> 'b t
        val iter : (key -> 'a -> unit) -> 'a t -> unit
        val fold_values : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
        val iter_values : ('a -> unit) -> 'a t -> unit
        val merge : ('a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
        val size : 'a t -> int
        val to_list : 'a t -> (key * 'a) list
        val of_list : (key * 'a) list -> 'a t
        val to_seq : 'a t -> (key * 'a) sequence
        val of_seq : (key * 'a) sequence -> 'a t
        val to_seq_values : 'a t -> 'a sequence
        val to_tree : 'a t -> [ `Char of char_ | `Switch | `Val of 'a ] ktree
        val above : key -> 'a t -> (key * 'a) sequence
        val below : key -> 'a t -> (key * 'a) sequence
        val check_invariants : 'a t -> bool
      end
  module String :
    sig
      type char_ = char
      type key = string
      type 'a t
      val empty : 'a t
      val is_empty : 'a t -> bool
      val add : key -> 'a -> 'a t -> 'a t
      val remove : key -> 'a t -> 'a t
      val find : key -> 'a t -> 'a option
      val find_exn : key -> 'a t -> 'a
      val longest_prefix : key -> 'a t -> key
      val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
      val fold : ('b -> key -> 'a -> 'b) -> 'b -> 'a t -> 'b
      val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
      val map : ('a -> 'b) -> 'a t -> 'b t
      val iter : (key -> 'a -> unit) -> 'a t -> unit
      val fold_values : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
      val iter_values : ('a -> unit) -> 'a t -> unit
      val merge : ('a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
      val size : 'a t -> int
      val to_list : 'a t -> (key * 'a) list
      val of_list : (key * 'a) list -> 'a t
      val to_seq : 'a t -> (key * 'a) sequence
      val of_seq : (key * 'a) sequence -> 'a t
      val to_seq_values : 'a t -> 'a sequence
      val to_tree : 'a t -> [ `Char of char_ | `Switch | `Val of 'a ] ktree
      val above : key -> 'a t -> (key * 'a) sequence
      val below : key -> 'a t -> (key * 'a) sequence
      val check_invariants : 'a t -> bool
    end
end