module Control.Monad.Adaptive.PriorityQueue(
PriorityQueue,
empty,
insert,
insertM,
min
) where
import Prelude hiding(min)
import qualified Data.List(insert)
import Control.Monad(ap)
empty :: PriorityQueue a
insert :: Ord a => a -> PriorityQueue a -> PriorityQueue a
insertM :: Monad m =>
(a -> a -> m Ordering) -> a -> PriorityQueue a -> m (PriorityQueue a)
min :: PriorityQueue a -> Maybe (a, PriorityQueue a)
newtype PriorityQueue a = PQ [a]
empty = PQ []
insert a (PQ l) = PQ (Data.List.insert a l)
insertM cmp a (PQ l) = return PQ `ap` ins l
where ins [] = return [a]
ins (b:l) = do o <- cmp a b
case o of LT -> return (a:b:l)
_ -> return (b:) `ap` ins l
min (PQ []) = Nothing
min (PQ (x:xs)) = Just (x,PQ xs)