Copyright	(c) Eric Mertens 2018
License	ISC
Maintainer	emertens@gmail.com
Safe Haskell	Safe-Inferred
Language	Haskell2010

Advent.PQueue

Description

Priority queue with Int priorities returning smallest priority first.

Synopsis

newtype PQueue a = PQ (IntMap [a])
pattern Empty :: PQueue a
pattern (:<|) :: a -> PQueue a -> PQueue a
null :: PQueue a -> Bool
singleton :: Int -> a -> PQueue a
insert :: Int -> a -> PQueue a -> PQueue a
view :: PQueue a -> Maybe (a, PQueue a)
viewWithPriority :: PQueue a -> Maybe (Int, a, PQueue a)
fromList :: [(Int, a)] -> PQueue a

Documentation

newtype PQueue a Source #

Priority queue. No guarantees are made regarding the order entries with the same priority are returned in.

Constructors

PQ (IntMap [a])

Instances

Instances details

Functor PQueue Source #
Instance details Defined in Advent.PQueue Methods fmap :: (a -> b) -> PQueue a -> PQueue b # (<$) :: a -> PQueue b -> PQueue a #
Foldable PQueue Source #
Instance details Defined in Advent.PQueue Methods fold :: Monoid m => PQueue m -> m # foldMap :: Monoid m => (a -> m) -> PQueue a -> m # foldMap' :: Monoid m => (a -> m) -> PQueue a -> m # foldr :: (a -> b -> b) -> b -> PQueue a -> b # foldr' :: (a -> b -> b) -> b -> PQueue a -> b # foldl :: (b -> a -> b) -> b -> PQueue a -> b # foldl' :: (b -> a -> b) -> b -> PQueue a -> b # foldr1 :: (a -> a -> a) -> PQueue a -> a # foldl1 :: (a -> a -> a) -> PQueue a -> a # toList :: PQueue a -> [a] # null :: PQueue a -> Bool # length :: PQueue a -> Int # elem :: Eq a => a -> PQueue a -> Bool # maximum :: Ord a => PQueue a -> a # minimum :: Ord a => PQueue a -> a # sum :: Num a => PQueue a -> a # product :: Num a => PQueue a -> a #
Traversable PQueue Source #
Instance details Defined in Advent.PQueue Methods traverse :: Applicative f => (a -> f b) -> PQueue a -> f (PQueue b) # sequenceA :: Applicative f => PQueue (f a) -> f (PQueue a) # mapM :: Monad m => (a -> m b) -> PQueue a -> m (PQueue b) # sequence :: Monad m => PQueue (m a) -> m (PQueue a) #
Read a => Read (PQueue a) Source #
Instance details Defined in Advent.PQueue Methods readsPrec :: Int -> ReadS (PQueue a) # readList :: ReadS [PQueue a] # readPrec :: ReadPrec (PQueue a) # readListPrec :: ReadPrec [PQueue a] #
Show a => Show (PQueue a) Source #	Show a `PQueue` using `fromList` `>>>` `show (singleton 1 'a')`"fromList [(1,'a')]"
Instance details Defined in Advent.PQueue Methods showsPrec :: Int -> PQueue a -> ShowS # show :: PQueue a -> String # showList :: [PQueue a] -> ShowS #

pattern Empty :: PQueue a Source #

Empty priority queue

pattern (:<|) :: a -> PQueue a -> PQueue a Source #

Pattern for extracting an element with the minimum priority from the queue. See also: view

null :: PQueue a -> Bool Source #

Test if a queue has no elements.

singleton Source #

Arguments

:: Int	priority
-> a	value
-> PQueue a

Construct a priority queue from a single priority and value.

insert Source #

Arguments

:: Int	priority
-> a	value
-> PQueue a
-> PQueue a

Insert a new value into the queue given a priority.

view :: PQueue a -> Maybe (a, PQueue a) Source #

Match the lowest priority entry in a queue returning the corresponding value and queue without that entry. See also: (:<|)

viewWithPriority :: PQueue a -> Maybe (Int, a, PQueue a) Source #

Match the lowest priority entry in a queue returning the corresponding priority, value and queue without that entry.

fromList :: [(Int, a)] -> PQueue a Source #

Construct a priority queue from a list of priorities and values.