(*
This file is part of licht.

licht is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

licht 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 General Public License for more details.

You should have received a copy of the GNU General Public License
along with licht.  If not, see <http://www.gnu.org/licenses/>.
*)

module type KEY = sig

    type 'a t

    val comp: 'a t -> 'b t -> ('a, 'b) Tools.cmp

    val repr: Format.formatter -> 'a t -> unit

end

module Make (El : KEY) : sig

  type t

  (** Create an empty tree *)
  val empty: t

  (** Return the element in the tree with the given key *)
  val find: 'a El.t -> t -> 'a

  (** Add one element in the tree, if the element is already present, it is replaced. *)
  val add: 'a El.t -> 'a -> t -> t

  (** Check if the key exists *)
  val member: 'a El.t -> t -> bool

  val remove: 'a El.t -> t -> t

  (** This type is used in the fold function as existencial type *)
  type container = C : ('a El.t * 'a) -> container [@@unboxed]

  val fold: ('a -> container -> 'a) -> 'a -> t -> 'a

  (** Return one element of the given tree, or raise Not_found if the tree is
  empty. Which element is chosen is unspecified, but equal elements will be
  chosen for equal trees. *) 
  val choose: t -> container

  (** Represent the content in dot syntax *)
  val repr: Format.formatter -> t -> unit

end