Safe Haskell	None
Language	Haskell2010

Queue.Prio.Hash

Contents

HashPSQ
Construction
Querying
Insertion
Deletion
Alteration
Mapping
Folding

Synopsis

data HashPSQ k p v
empty :: HashPSQ k p v
singleton :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v
fromList :: (Hashable k, Ord k, Ord p) => [(k, p, v)] -> HashPSQ k p v
null :: HashPSQ k p v -> Bool
size :: HashPSQ k p v -> Int
member :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Bool
lookup :: (Ord k, Hashable k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v)
findMin :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v)
minView :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
atMostView :: (Hashable k, Ord k, Ord p) => p -> HashPSQ k p v -> ([(k, p, v)], HashPSQ k p v)
insert :: (Ord k, Hashable k, Ord p) => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
insertView :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)
delete :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> HashPSQ k p v
deleteView :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v)
alter :: (Hashable k, Ord k, Ord p) => (Maybe (p, v) -> (b, Maybe (p, v))) -> k -> HashPSQ k p v -> (b, HashPSQ k p v)
alterMin :: (Hashable k, Ord k, Ord p) => (Maybe (k, p, v) -> (b, Maybe (k, p, v))) -> HashPSQ k p v -> (b, HashPSQ k p v)
map :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w
unsafeMapMonotonic :: (k -> p -> v -> (q, w)) -> HashPSQ k p v -> HashPSQ k q w
toList :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [(k, p, v)]
keys :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [k]
fold' :: (k -> p -> v -> a -> a) -> a -> HashPSQ k p v -> a

HashPSQ

data HashPSQ k p v #

A priority search queue with keys of type k and priorities of type p and values of type v. It is strict in keys, priorities and values.

Instances

Functor (HashPSQ k p)
Instance details Defined in Data.HashPSQ.Internal Methods fmap :: (a -> b) -> HashPSQ k p a -> HashPSQ k p b # (<$) :: a -> HashPSQ k p b -> HashPSQ k p a #
Foldable (HashPSQ k p)
Instance details Defined in Data.HashPSQ.Internal Methods fold :: Monoid m => HashPSQ k p m -> m # foldMap :: Monoid m => (a -> m) -> HashPSQ k p a -> m # foldr :: (a -> b -> b) -> b -> HashPSQ k p a -> b # foldr' :: (a -> b -> b) -> b -> HashPSQ k p a -> b # foldl :: (b -> a -> b) -> b -> HashPSQ k p a -> b # foldl' :: (b -> a -> b) -> b -> HashPSQ k p a -> b # foldr1 :: (a -> a -> a) -> HashPSQ k p a -> a # foldl1 :: (a -> a -> a) -> HashPSQ k p a -> a # toList :: HashPSQ k p a -> [a] # null :: HashPSQ k p a -> Bool # length :: HashPSQ k p a -> Int # elem :: Eq a => a -> HashPSQ k p a -> Bool # maximum :: Ord a => HashPSQ k p a -> a # minimum :: Ord a => HashPSQ k p a -> a # sum :: Num a => HashPSQ k p a -> a # product :: Num a => HashPSQ k p a -> a #
Traversable (HashPSQ k p)
Instance details Defined in Data.HashPSQ.Internal Methods traverse :: Applicative f => (a -> f b) -> HashPSQ k p a -> f (HashPSQ k p b) # sequenceA :: Applicative f => HashPSQ k p (f a) -> f (HashPSQ k p a) # mapM :: Monad m => (a -> m b) -> HashPSQ k p a -> m (HashPSQ k p b) # sequence :: Monad m => HashPSQ k p (m a) -> m (HashPSQ k p a) #
(Eq k, Eq p, Eq v, Hashable k, Ord k, Ord p) => Eq (HashPSQ k p v)
Instance details Defined in Data.HashPSQ.Internal Methods (==) :: HashPSQ k p v -> HashPSQ k p v -> Bool # (/=) :: HashPSQ k p v -> HashPSQ k p v -> Bool #
(Show p, Show k, Show v) => Show (HashPSQ k p v)
Instance details Defined in Data.HashPSQ.Internal Methods showsPrec :: Int -> HashPSQ k p v -> ShowS # show :: HashPSQ k p v -> String # showList :: [HashPSQ k p v] -> ShowS #
(NFData p, NFData k, NFData v) => NFData (HashPSQ k p v)
Instance details Defined in Data.HashPSQ.Internal Methods rnf :: HashPSQ k p v -> () #

Construction

empty :: HashPSQ k p v #

O(1) The empty queue.

singleton :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v #

O(1) Build a queue with one element.

fromList :: (Hashable k, Ord k, Ord p) => [(k, p, v)] -> HashPSQ k p v #

O(n*min(n,W)) Build a queue from a list of (key, priority, value) tuples. If the list contains more than one priority and value for the same key, the last priority and value for the key is retained.

Querying

null :: HashPSQ k p v -> Bool #

O(1) True if the queue is empty.

size :: HashPSQ k p v -> Int #

O(n) The number of elements stored in the PSQ.

member :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Bool #

O(min(n,W)) Check if a key is present in the the queue.

lookup :: (Ord k, Hashable k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v) #

O(min(n,W)) The priority and value of a given key, or Nothing if the key is not bound.

findMin :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v) #

O(1) The element with the lowest priority.

minView :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v) #

O(min(n,W)) Retrieve the binding with the least priority, and the rest of the queue stripped of that binding.

atMostView :: (Hashable k, Ord k, Ord p) => p -> HashPSQ k p v -> ([(k, p, v)], HashPSQ k p v) #

Return a list of elements ordered by key whose priorities are at most pt, and the rest of the queue stripped of these elements. The returned list of elements can be in any order: no guarantees there.

Insertion

insert :: (Ord k, Hashable k, Ord p) => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v #

O(min(n,W)) Insert a new key, priority and value into the queue. If the key is already present in the queue, the associated priority and value are replaced with the supplied priority and value.

insertView :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v) #

O(min(n,W)) Insert a new key, priority and value into the queue. If the key is already present in the queue, then the evicted priority and value can be found the first element of the returned tuple.

Deletion

delete :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> HashPSQ k p v #

O(min(n,W)) Delete a key and its priority and value from the queue. When the key is not a member of the queue, the original queue is returned.

deleteView :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v) #

O(min(n,W)) Delete a key and its priority and value from the queue. If the key was present, the associated priority and value are returned in addition to the updated queue.

Alteration

alter :: (Hashable k, Ord k, Ord p) => (Maybe (p, v) -> (b, Maybe (p, v))) -> k -> HashPSQ k p v -> (b, HashPSQ k p v) #

O(min(n,W)) The expression alter f k queue alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a queue. It also allows you to calculate an additional value b.

alterMin :: (Hashable k, Ord k, Ord p) => (Maybe (k, p, v) -> (b, Maybe (k, p, v))) -> HashPSQ k p v -> (b, HashPSQ k p v) #

O(min(n,W)) A variant of alter which works on the element with the minimum priority. Unlike alter, this variant also allows you to change the key of the element.

Mapping

map :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w #

O(n) Modify every value in the queue.

unsafeMapMonotonic :: (k -> p -> v -> (q, w)) -> HashPSQ k p v -> HashPSQ k q w #

O(n) Maps a function over the values and priorities of the queue. The function f must be monotonic with respect to the priorities. I.e. if x < y, then fst (f k x v) < fst (f k y v). The precondition is not checked. If f is not monotonic, then the result will be invalid.

Folding

toList :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [(k, p, v)] #

O(n) Convert a queue to a list of (key, priority, value) tuples. The order of the list is not specified.

keys :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [k] #

O(n) Obtain the list of present keys in the queue.

fold' :: (k -> p -> v -> a -> a) -> a -> HashPSQ k p v -> a #

O(n) Strict fold over every key, priority and value in the queue. The order in which the fold is performed is not specified.