module PQueue where

newtype PQueue a b = PQueue [(a,b)] deriving Int -> PQueue a b -> ShowS
[PQueue a b] -> ShowS
PQueue a b -> String
(Int -> PQueue a b -> ShowS)
-> (PQueue a b -> String)
-> ([PQueue a b] -> ShowS)
-> Show (PQueue a b)
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 = [(a, b)] -> PQueue a b
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) = [(a, b)] -> PQueue a b
forall a b. [(a, b)] -> PQueue a b
PQueue ([(a, b)] -> PQueue a b) -> [(a, b)] -> PQueue a b
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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
p'    = (a, b)
v (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)]
q
			    | Bool
otherwise = (a, b)
v' (a, b) -> [(a, b)] -> [(a, b)]
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
	[] -> Maybe ((a, b), PQueue a b)
forall a. Maybe a
Nothing
	((a, b)
x:[(a, b)]
xs) -> ((a, b), PQueue a b) -> Maybe ((a, b), PQueue a b)
forall a. a -> Maybe a
Just ((a, b)
x,[(a, b)] -> PQueue a b
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 = [(a, (a, a))] -> PQueue a (a, a)
forall a b. [(a, b)] -> PQueue a b
PQueue ([(a, (a, a))] -> PQueue a (a, a))
-> [(a, (a, a))] -> PQueue a (a, a)
forall a b. (a -> b) -> a -> b
$ ((a, (a, a)) -> Bool) -> [(a, (a, a))] -> [(a, (a, a))]
forall a. (a -> Bool) -> [a] -> [a]
filter (\((a
_,(a
_,a
i')))->a
i'a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/=a
i) [(a, (a, a))]
q