module PQueue where

newtype PQueue a b = PQueue [(a,b)] deriving Int -> PQueue a b -> ShowS
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall a b. (Show a, Show b) => Int -> PQueue a b -> ShowS
forall a b. (Show a, Show b) => [PQueue a b] -> ShowS
forall a b. (Show a, Show b) => PQueue a b -> String
showList :: [PQueue a b] -> ShowS
$cshowList :: forall a b. (Show a, Show b) => [PQueue a b] -> ShowS
show :: PQueue a b -> String
$cshow :: forall a b. (Show a, Show b) => PQueue a b -> String
showsPrec :: Int -> PQueue a b -> ShowS
$cshowsPrec :: forall a b. (Show a, Show b) => Int -> PQueue a b -> ShowS
Show

empty :: PQueue a b
empty = forall a b. [(a, b)] -> PQueue a b
PQueue []

insert :: PQueue a b -> (a, b) -> PQueue a b
insert (PQueue [(a, b)]
q) v :: (a, b)
v@(a
p,b
a) = forall a b. [(a, b)] -> PQueue a b
PQueue forall a b. (a -> b) -> a -> b
$ [(a, b)] -> [(a, b)]
insert' [(a, b)]
q where
   insert' :: [(a, b)] -> [(a, b)]
insert' [] = [(a, b)
v]
   insert' q :: [(a, b)]
q@(v' :: (a, b)
v'@(a
p',b
_):[(a, b)]
q') | a
p forall a. Ord a => a -> a -> Bool
< a
p'    = (a, b)
v forall a. a -> [a] -> [a]
: [(a, b)]
q
			    | Bool
otherwise = (a, b)
v' forall a. a -> [a] -> [a]
: [(a, b)] -> [(a, b)]
insert' [(a, b)]
q'

inspect :: PQueue a b -> Maybe ((a, b), PQueue a b)
inspect (PQueue [(a, b)]
q) = case [(a, b)]
q of
	[] -> forall a. Maybe a
Nothing
	((a, b)
x:[(a, b)]
xs) -> forall a. a -> Maybe a
Just ((a, b)
x,forall a b. [(a, b)] -> PQueue a b
PQueue [(a, b)]
xs)

remove :: PQueue a (a, a) -> a -> PQueue a (a, a)
remove (PQueue [(a, (a, a))]
q) a
i = forall a b. [(a, b)] -> PQueue a b
PQueue forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
filter (\((a
_,(a
_,a
i')))->a
i'forall a. Eq a => a -> a -> Bool
/=a
i) [(a, (a, a))]
q