module PrioQueue_Sol
    ( Queue
    , empty
    , insert
    , pull
    )
where

import Data.Function (on)

data Tree b = Leaf | Node (Tree b) b (Tree b)

meld :: (b -> b -> Ordering) -> Tree b -> Tree b -> Tree b
meld _ Leaf t = t
meld _ t Leaf = t
meld cmp n1@(Node l1 a1 r1) n2@(Node l2 a2 r2)
    | cmp a1 a2 == LT = Node (meld cmp n2 r1) a1 l1
    | otherwise = Node (meld cmp n1 r2) a2 l2

newtype Queue a = Queue (Tree (a,Integer))

empty :: Queue a
empty = Queue Leaf

cmpPrio :: (a, Integer) -> (a, Integer) -> Ordering
cmpPrio = compare `on` snd

insert :: a -> Integer -> Queue a -> Queue a
insert x p (Queue q) = Queue (meld cmpPrio (Node Leaf (x,p) Leaf) q)

pull :: Queue a -> Maybe (a, Queue a)
pull (Queue Leaf) = Nothing
pull (Queue (Node l a r)) = Just (fst a, Queue (meld cmpPrio l r))