module type OrderedSig = sig
	type t
	val eq : t -> t -> bool
	val lt : t -> t -> bool
	val leq : t -> t -> bool
end

module Int : OrderedSig = struct

	type t = int
	let eq (a : t) (b : t) = a=b
	let lt (a : t) (b : t) = a<b
	let leq (a : t) (b : t) = a<=b
end


module type BinomialHeapSig = sig
  	type elem
  	type tree = Node of int * elem * tree list
  	type t = tree list


	val empty : t -> t
	val isEmpty : t -> bool

	val insert : elem -> t -> t
	val merge : t -> t -> t

	val findMin : t -> elem

	val deleteMin : t -> t

 end

module BinomialHeap (S : OrderedSig) : BinomialHeapSig = struct
	type elem = S.t
(* Something about t and tree types, not sure about def*)
	type t
	(* Fix *)
  	type tree = Node of int * elem * tree list

	let empty = []
	let isEmpty (ts : t) : bool = ts <> []
	let root ((_, x, _) : tree) = x
	let rank ((r, _, _) : tree) = r

	let rec insertTree (t1 : t) (t2 : t) =
		match (t1, t2) with
			| (t1, []) -> [t1]
			| (t1, t2 as t :: ts) -> if rank t1 < rank t
				then t :: ts
				else insertTree(link (t1, t) ts)

	let link ((r, x1, c1) : tree) ((_, x2, c2) : tree) =
			if Elem.leq x1 x2
			then Node(r+1, x1, t2 :: c1)
			else Node(r+1, x2, t1 :: c2)

	let insert (e : elem) (tr : t) =
		match (e, tree) with
			| (e, []) -> [e]
			| (e, (t :: ts)) ->
				if rank t < rank f then f:: ts else insTree (link (t, t ), ts')

	let merge ts1 ts2 =
		match (ts1, ts2) with
			| (ts1, []) -> ts1
			| ([], ts2) -> []
			| (t1 :: t1s, t2 :: t2s) ->
				if (rank t1) < (rank t2) then t1 :: merge t1s ts2
				else if (rank t2) < (rank t1) then t2 :: merge ts1 t2s
				else insertTree (link t1 t2), merge t1s t2s


	let removeMinTree t =
		match t with
			| [] -> raise Failure("Empty")
			| t -> (t, [])
			| t :: ts ->
				let (t', ts') = removeMinTree ts in
				if Elem.leq (root t) (root t') then (t, ts) else (t', t::ts')


	let findMin ts =
		let (t, _) = removeMinTree ts in
		root t

	let deleteMin ts =
		let (Node(_, x, ts1), ts2) = removeMinTree ts in
		merge (rev ts1, ts2)
end