pqueue-1.4.2.0: Reliable, persistent, fast priority queues.
Copyright(c) Louis Wasserman 2010
LicenseBSD-style
Maintainerlibraries@haskell.org
Stabilityexperimental
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

Data.PQueue.Prio.Max

Description

General purpose priority queue. Each element is associated with a key, and the priority queue supports viewing and extracting the element with the maximum key.

A worst-case bound is given for each operation. In some cases, an amortized bound is also specified; these bounds hold even in a persistent context.

This implementation is based on a binomial heap augmented with a global root.

We do not guarantee stable behavior. Ties are broken arbitrarily -- that is, if k1 <= k2 and k2 <= k1, then there are no guarantees about the relative order in which k1, k2, and their associated elements are returned. (Unlike Data.Map, we allow multiple elements with the same key.)

This implementation offers a number of methods of the form xxxU, where U stands for unordered. No guarantees whatsoever are made on the execution or traversal order of these functions.

Synopsis

Documentation

data MaxPQueue k a Source #

A priority queue where values of type a are annotated with keys of type k. The queue supports extracting the element with maximum key.

Instances

Instances details
Functor (MaxPQueue k) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

fmap :: (a -> b) -> MaxPQueue k a -> MaxPQueue k b #

(<$) :: a -> MaxPQueue k b -> MaxPQueue k a #

Ord k => Foldable (MaxPQueue k) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

fold :: Monoid m => MaxPQueue k m -> m #

foldMap :: Monoid m => (a -> m) -> MaxPQueue k a -> m #

foldMap' :: Monoid m => (a -> m) -> MaxPQueue k a -> m #

foldr :: (a -> b -> b) -> b -> MaxPQueue k a -> b #

foldr' :: (a -> b -> b) -> b -> MaxPQueue k a -> b #

foldl :: (b -> a -> b) -> b -> MaxPQueue k a -> b #

foldl' :: (b -> a -> b) -> b -> MaxPQueue k a -> b #

foldr1 :: (a -> a -> a) -> MaxPQueue k a -> a #

foldl1 :: (a -> a -> a) -> MaxPQueue k a -> a #

toList :: MaxPQueue k a -> [a] #

null :: MaxPQueue k a -> Bool #

length :: MaxPQueue k a -> Int #

elem :: Eq a => a -> MaxPQueue k a -> Bool #

maximum :: Ord a => MaxPQueue k a -> a #

minimum :: Ord a => MaxPQueue k a -> a #

sum :: Num a => MaxPQueue k a -> a #

product :: Num a => MaxPQueue k a -> a #

Ord k => Traversable (MaxPQueue k) Source #

Traverses in descending order. mapM is strictly accumulating like mapMWithKey.

Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

traverse :: Applicative f => (a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b) #

sequenceA :: Applicative f => MaxPQueue k (f a) -> f (MaxPQueue k a) #

mapM :: Monad m => (a -> m b) -> MaxPQueue k a -> m (MaxPQueue k b) #

sequence :: Monad m => MaxPQueue k (m a) -> m (MaxPQueue k a) #

(Ord k, Eq a) => Eq (MaxPQueue k a) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

(==) :: MaxPQueue k a -> MaxPQueue k a -> Bool #

(/=) :: MaxPQueue k a -> MaxPQueue k a -> Bool #

(Data k, Data a, Ord k) => Data (MaxPQueue k a) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> MaxPQueue k a -> c (MaxPQueue k a) #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (MaxPQueue k a) #

toConstr :: MaxPQueue k a -> Constr #

dataTypeOf :: MaxPQueue k a -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (MaxPQueue k a)) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (MaxPQueue k a)) #

gmapT :: (forall b. Data b => b -> b) -> MaxPQueue k a -> MaxPQueue k a #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> MaxPQueue k a -> r #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> MaxPQueue k a -> r #

gmapQ :: (forall d. Data d => d -> u) -> MaxPQueue k a -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> MaxPQueue k a -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> MaxPQueue k a -> m (MaxPQueue k a) #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> MaxPQueue k a -> m (MaxPQueue k a) #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> MaxPQueue k a -> m (MaxPQueue k a) #

(Ord k, Ord a) => Ord (MaxPQueue k a) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

compare :: MaxPQueue k a -> MaxPQueue k a -> Ordering #

(<) :: MaxPQueue k a -> MaxPQueue k a -> Bool #

(<=) :: MaxPQueue k a -> MaxPQueue k a -> Bool #

(>) :: MaxPQueue k a -> MaxPQueue k a -> Bool #

(>=) :: MaxPQueue k a -> MaxPQueue k a -> Bool #

max :: MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a #

min :: MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a #

(Read k, Read a) => Read (MaxPQueue k a) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

(Ord k, Show k, Show a) => Show (MaxPQueue k a) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

showsPrec :: Int -> MaxPQueue k a -> ShowS #

show :: MaxPQueue k a -> String #

showList :: [MaxPQueue k a] -> ShowS #

Ord k => Semigroup (MaxPQueue k a) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

(<>) :: MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a #

sconcat :: NonEmpty (MaxPQueue k a) -> MaxPQueue k a #

stimes :: Integral b => b -> MaxPQueue k a -> MaxPQueue k a #

Ord k => Monoid (MaxPQueue k a) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

mempty :: MaxPQueue k a #

mappend :: MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a #

mconcat :: [MaxPQueue k a] -> MaxPQueue k a #

(NFData k, NFData a) => NFData (MaxPQueue k a) Source # 
Instance details

Defined in Data.PQueue.Prio.Max.Internals

Methods

rnf :: MaxPQueue k a -> () #

Construction

empty :: MaxPQueue k a Source #

\(O(1)\). Returns the empty priority queue.

singleton :: k -> a -> MaxPQueue k a Source #

\(O(1)\). Constructs a singleton priority queue.

insert :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a Source #

Amortized \(O(1)\), worst-case \(O(\log n)\). Inserts an element with the specified key into the queue.

insertBehind :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a Source #

\(O(n)\) (an earlier implementation had \(O(1)\) but was buggy). Insert an element with the specified key into the priority queue, putting it behind elements whose key compares equal to the inserted one.

union :: Ord k => MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a Source #

Amortized \(O(\log \min(n_1,n_2))\), worst-case \(O(\log \max(n_1,n_2))\). Returns the union of the two specified queues.

unions :: Ord k => [MaxPQueue k a] -> MaxPQueue k a Source #

The union of a list of queues: (unions == foldl union empty).

Query

null :: MaxPQueue k a -> Bool Source #

\(O(1)\). Checks if this priority queue is empty.

size :: MaxPQueue k a -> Int Source #

\(O(1)\). Returns the size of this priority queue.

Maximum view

findMax :: MaxPQueue k a -> (k, a) Source #

\(O(1)\). The maximal (key, element) in the queue. Calls error if empty.

getMax :: MaxPQueue k a -> Maybe (k, a) Source #

\(O(1)\). The maximal (key, element) in the queue, if the queue is nonempty.

deleteMax :: Ord k => MaxPQueue k a -> MaxPQueue k a Source #

\(O(\log n)\). Delete and find the element with the maximum key. Calls error if empty.

deleteFindMax :: Ord k => MaxPQueue k a -> ((k, a), MaxPQueue k a) Source #

\(O(\log n)\). Delete and find the element with the maximum key. Calls error if empty.

adjustMax :: (a -> a) -> MaxPQueue k a -> MaxPQueue k a Source #

\(O(1)\). Alter the value at the maximum key. If the queue is empty, does nothing.

adjustMaxA :: Applicative f => (a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a) Source #

\(O(1)\) per operation. Alter the value at the maximum key in an Applicative context. If the queue is empty, does nothing.

Since: 1.4.2

adjustMaxWithKey :: (k -> a -> a) -> MaxPQueue k a -> MaxPQueue k a Source #

\(O(1)\). Alter the value at the maximum key. If the queue is empty, does nothing.

adjustMaxWithKeyA :: Applicative f => (k -> a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a) Source #

\(O(1)\) per operation. Alter the value at the maximum key in an Applicative context. If the queue is empty, does nothing.

Since: 1.4.2

updateMax :: Ord k => (a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a Source #

\(O(\log n)\). (Actually \(O(1)\) if there's no deletion.) Update the value at the maximum key. If the queue is empty, does nothing.

updateMaxA :: (Applicative f, Ord k) => (a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a) Source #

\(O(\log n)\) per operation. (Actually \(O(1)\) if there's no deletion.) Update the value at the maximum key in an Applicative context. If the queue is empty, does nothing.

Since: 1.4.2

updateMaxWithKey :: Ord k => (k -> a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a Source #

\(O(\log n)\). (Actually \(O(1)\) if there's no deletion.) Update the value at the maximum key. If the queue is empty, does nothing.

updateMaxWithKeyA :: (Applicative f, Ord k) => (k -> a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a) Source #

\(O(\log n)\) per operation. (Actually \(O(1)\) if there's no deletion.) Update the value at the maximum key in an Applicative context. If the queue is empty, does nothing.

Since: 1.4.2

maxView :: Ord k => MaxPQueue k a -> Maybe (a, MaxPQueue k a) Source #

\(O(\log n)\). Retrieves the value associated with the maximum key of the queue, and the queue stripped of that element, or Nothing if passed an empty queue.

maxViewWithKey :: Ord k => MaxPQueue k a -> Maybe ((k, a), MaxPQueue k a) Source #

\(O(\log n)\). Retrieves the maximal (key, value) pair of the map, and the map stripped of that element, or Nothing if passed an empty map.

Traversal

Map

map :: (a -> b) -> MaxPQueue k a -> MaxPQueue k b Source #

\(O(n)\). Map a function over all values in the queue.

mapWithKey :: (k -> a -> b) -> MaxPQueue k a -> MaxPQueue k b Source #

\(O(n)\). Map a function over all values in the queue.

mapKeys :: Ord k' => (k -> k') -> MaxPQueue k a -> MaxPQueue k' a Source #

\(O(n)\). Map a function over all values in the queue.

mapKeysMonotonic :: (k -> k') -> MaxPQueue k a -> MaxPQueue k' a Source #

\(O(n)\). mapKeysMonotonic f q == mapKeys f q, but only works when f is strictly monotonic. The precondition is not checked. This function has better performance than mapKeys.

Fold

foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MaxPQueue k a -> b Source #

\(O(n \log n)\). Fold the keys and values in the map, such that foldrWithKey f z q == foldr (uncurry f) z (toDescList q).

If you do not care about the traversal order, consider using foldrWithKeyU.

foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MaxPQueue k a -> b Source #

\(O(n \log n)\). Fold the keys and values in the map, such that foldlWithKey f z q == foldl (uncurry . f) z (toDescList q).

If you do not care about the traversal order, consider using foldlWithKeyU.

Traverse

traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b) Source #

\(O(n \log n)\). Traverses the elements of the queue in descending order by key. (traverseWithKey f q == fromDescList $ traverse (uncurry f) (toDescList q))

If you do not care about the order of the traversal, consider using traverseWithKeyU.

If you are working in a strict monad, consider using mapMWithKey.

mapMWithKey :: (Ord k, Monad m) => (k -> a -> m b) -> MaxPQueue k a -> m (MaxPQueue k b) Source #

A strictly accumulating version of traverseWithKey. This works well in IO and strict State, and is likely what you want for other "strict" monads, where ⊥ >>= pure () = ⊥.

Subsets

Indexed

take :: Ord k => Int -> MaxPQueue k a -> [(k, a)] Source #

\(O(k \log n)\)/. Takes the first k (key, value) pairs in the queue, or the first n if k >= n. (take k q == take k (toDescList q))

drop :: Ord k => Int -> MaxPQueue k a -> MaxPQueue k a Source #

\(O(k \log n)\)/. Deletes the first k (key, value) pairs in the queue, or returns an empty queue if k >= n.

splitAt :: Ord k => Int -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a) Source #

\(O(k \log n)\)/. Equivalent to (take k q, drop k q).

Predicates

takeWhile :: Ord k => (a -> Bool) -> MaxPQueue k a -> [(k, a)] Source #

Takes the longest possible prefix of elements satisfying the predicate. (takeWhile p q == takeWhile (p . snd) (toDescList q))

takeWhileWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> [(k, a)] Source #

Takes the longest possible prefix of elements satisfying the predicate. (takeWhile p q == takeWhile (uncurry p) (toDescList q))

dropWhile :: Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a Source #

Removes the longest possible prefix of elements satisfying the predicate.

dropWhileWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a Source #

Removes the longest possible prefix of elements satisfying the predicate.

span :: Ord k => (a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a) Source #

Equivalent to (takeWhile p q, dropWhile p q).

spanWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a) Source #

Equivalent to spanWithKey (k a -> not (p k a)) q.

break :: Ord k => (a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a) Source #

Equivalent to span (not . p).

breakWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a) Source #

Equivalent to spanWithKey (k a -> not (p k a)) q.

Filter

filter :: Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a Source #

\(O(n)\). Filter all values that satisfy the predicate.

filterWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a Source #

\(O(n)\). Filter all values that satisfy the predicate.

partition :: Ord k => (a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a) Source #

\(O(n)\). Partition the queue according to a predicate. The first queue contains all elements which satisfy the predicate, the second all elements that fail the predicate.

partitionWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a) Source #

\(O(n)\). Partition the queue according to a predicate. The first queue contains all elements which satisfy the predicate, the second all elements that fail the predicate.

mapMaybe :: Ord k => (a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b Source #

\(O(n)\). Map values and collect the Just results.

mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b Source #

\(O(n)\). Map values and collect the Just results.

mapEither :: Ord k => (a -> Either b c) -> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c) Source #

\(O(n)\). Map values and separate the Left and Right results.

mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c) Source #

\(O(n)\). Map values and separate the Left and Right results.

List operations

Conversion from lists

fromList :: Ord k => [(k, a)] -> MaxPQueue k a Source #

\(O(n)\). Build a priority queue from the list of (key, value) pairs.

fromAscList :: [(k, a)] -> MaxPQueue k a Source #

\(O(n)\). Build a priority queue from an ascending list of (key, value) pairs. The precondition is not checked.

fromDescList :: [(k, a)] -> MaxPQueue k a Source #

\(O(n)\). Build a priority queue from a descending list of (key, value) pairs. The precondition is not checked.

Conversion to lists

keys :: Ord k => MaxPQueue k a -> [k] Source #

\(O(n \log n)\). Return all keys of the queue in descending order.

elems :: Ord k => MaxPQueue k a -> [a] Source #

\(O(n \log n)\). Return all elements of the queue in descending order by key.

assocs :: Ord k => MaxPQueue k a -> [(k, a)] Source #

\(O(n \log n)\). Equivalent to toDescList.

toAscList :: Ord k => MaxPQueue k a -> [(k, a)] Source #

\(O(n \log n)\). Return all (key, value) pairs in ascending order by key.

toDescList :: Ord k => MaxPQueue k a -> [(k, a)] Source #

\(O(n \log n)\). Return all (key, value) pairs in descending order by key.

toList :: Ord k => MaxPQueue k a -> [(k, a)] Source #

\(O(n \log n)\). Equivalent to toDescList.

If the traversal order is irrelevant, consider using toListU.

Unordered operations

foldrU :: (a -> b -> b) -> b -> MaxPQueue k a -> b Source #

\(O(n)\). An unordered right fold over the elements of the queue, in no particular order.

foldrWithKeyU :: (k -> a -> b -> b) -> b -> MaxPQueue k a -> b Source #

\(O(n)\). An unordered right fold over the elements of the queue, in no particular order.

foldMapWithKeyU :: Monoid m => (k -> a -> m) -> MaxPQueue k a -> m Source #

\(O(n)\). An unordered monoidal fold over the elements of the queue, in no particular order.

Since: 1.4.2

foldlU :: (b -> a -> b) -> b -> MaxPQueue k a -> b Source #

\(O(n)\). An unordered left fold over the elements of the queue, in no particular order. This is rarely what you want; foldrU and foldlU' are more likely to perform well.

foldlU' :: (b -> a -> b) -> b -> MaxPQueue k a -> b Source #

\(O(n)\). An unordered strict left fold over the elements of the queue, in no particular order.

Since: 1.4.2

foldlWithKeyU :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b Source #

\(O(n)\). An unordered left fold over the elements of the queue, in no particular order. This is rarely what you want; foldrWithKeyU and foldlWithKeyU' are more likely to perform well.

foldlWithKeyU' :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b Source #

\(O(n)\). An unordered left fold over the elements of the queue, in no particular order.

Since: 1.4.2

traverseU :: Applicative f => (a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b) Source #

\(O(n)\). An unordered traversal over a priority queue, in no particular order. While there is no guarantee in which order the elements are traversed, the resulting priority queue will be perfectly valid.

traverseWithKeyU :: Applicative f => (k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b) Source #

\(O(n)\). An unordered traversal over a priority queue, in no particular order. While there is no guarantee in which order the elements are traversed, the resulting priority queue will be perfectly valid.

keysU :: MaxPQueue k a -> [k] Source #

\(O(n)\). Return all keys of the queue in no particular order.

elemsU :: MaxPQueue k a -> [a] Source #

\(O(n)\). Return all elements of the queue in no particular order.

assocsU :: MaxPQueue k a -> [(k, a)] Source #

\(O(n)\). Equivalent to toListU.

toListU :: MaxPQueue k a -> [(k, a)] Source #

\(O(n)\). Returns all (key, value) pairs in the queue in no particular order.

Helper methods

seqSpine :: MaxPQueue k a -> b -> b Source #

\(O(\log n)\). seqSpine q r forces the spine of q and returns r.

Note: The spine of a MaxPQueue is stored somewhat lazily. Most operations take great care to prevent chains of thunks from accumulating along the spine to the detriment of performance. However, mapKeysMonotonic can leave expensive thunks in the structure and repeated applications of that function can create thunk chains.