type 'x queue = Kolejka of 'x * int * 'x queue * 'x queue | Pusta

exception Empty

let empty = Pusta

let is_empty q = (q = Pusta)

let rec join d1 d2 =
    let pusty_z_pelnym d puste =
        let Kolejka(wart, gl, lewy, prawy) = d
        in let d3 = join puste prawy
        in match d3 with
        | Kolejka(_, gl_d3, _, _) ->
            if gl_d3 + 1 < gl then
                Kolejka(wart, gl_d3 + 1, lewy, d3)
            else
                Kolejka(wart, gl, d3, lewy)
        | Pusta ->
            Kolejka(wart, 0, lewy, d3)

    in let pelny_z_pelnym (Kolejka(wart_l, gl_l, lewy_l, prawy_l)) (Kolejka(wart_p, gl_p, lewy_p, prawy_p)) =
        let d3 = join prawy_l d2
        in match d3 with
        | Kolejka(_, gl_nowy, _, _) ->
            if gl_nowy + 1 < gl_l then Kolejka(wart_l, gl_nowy + 1, lewy_l, d3)
            else Kolejka(wart_l, gl_l, d3, lewy_l)
        | Pusta -> Pusta

    in let zamien d1 d2 =
        match d1, d2 with
        | Pusta, _ -> (d2, d1)
        | _, Pusta -> (d1, d2)
        | _, _ ->
            let Kolejka(w1, _, _, _) = d1
            in let Kolejka(w2, _, _, _) = d2
            in if w1 < w2 then (d1, d2) else (d2, d1)

    in let (d1, d2) = zamien d1 d2
    in match d1, d2 with
    | Kolejka(_, _, _, _), Kolejka(_, _, _, _) -> pelny_z_pelnym d1 d2
    | Kolejka(_, _, _, _), Pusta -> pusty_z_pelnym d1 d2
    | Pusta, Pusta -> Pusta
    | _, _ -> failwith("Coś poszlo nie tak...")
;;

let add e q = join (Kolejka(e, 0, Pusta, Pusta)) q

let delete_min q =
    match q with
    | Pusta -> raise Empty
    | Kolejka(e, _, lewy, prawy) -> (e, join lewy prawy)
;;