-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Reliable, persistent, fast priority queues.
--
-- A fast, reliable priority queue implementation based on a binomial
-- heap.
@package pqueue
@version 1.4.2.0
-- | General purpose priority queue, supporting extract-minimum operations.
--
-- An amortized running time is given for each operation, with n
-- referring to the length of the sequence and k being the
-- integral index used by some operations. These bounds hold even in a
-- persistent (shared) setting.
--
-- This implementation is based on a binomial heap augmented with a
-- global root.
--
-- This implementation does not guarantee stable behavior.
--
-- 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.
module Data.PQueue.Min
-- | A priority queue with elements of type a. Supports extracting
-- the minimum element.
data MinQueue a
-- | <math>. The empty priority queue.
empty :: MinQueue a
-- | <math>. Is this the empty priority queue?
null :: MinQueue a -> Bool
-- | <math>. The number of elements in the queue.
size :: MinQueue a -> Int
-- | <math>. Returns the minimum element. Throws an error on an empty
-- queue.
findMin :: MinQueue a -> a
-- | <math>. Returns the minimum element of the queue, if the queue
-- is nonempty.
getMin :: MinQueue a -> Maybe a
-- | <math>. Deletes the minimum element. If the queue is empty, does
-- nothing.
deleteMin :: Ord a => MinQueue a -> MinQueue a
-- | <math>. Extracts the minimum element. Throws an error on an
-- empty queue.
deleteFindMin :: Ord a => MinQueue a -> (a, MinQueue a)
-- | Retrieves the minimum element of the queue, and the queue stripped of
-- that element, or Nothing if passed an empty queue.
minView :: Ord a => MinQueue a -> Maybe (a, MinQueue a)
-- | <math>. Construct a priority queue with a single element.
singleton :: a -> MinQueue a
-- | Amortized <math>, worst-case <math>. Insert an element
-- into the priority queue.
insert :: Ord a => a -> MinQueue a -> MinQueue a
-- | Amortized <math>, worst-case <math>. Take the union of two
-- priority queues.
union :: Ord a => MinQueue a -> MinQueue a -> MinQueue a
-- | Takes the union of a list of priority queues. Equivalent to
-- foldl' union empty.
unions :: Ord a => [MinQueue a] -> MinQueue a
-- | <math>/. Index (subscript) operator, starting from 0. queue
-- !! k returns the (k+1)th smallest element in the queue.
-- Equivalent to toAscList queue !! k.
(!!) :: Ord a => MinQueue a -> Int -> a
-- | <math>/. take k, applied to a queue
-- queue, returns a list of the smallest k elements of
-- queue, or all elements of queue itself if k
-- >= size queue.
take :: Ord a => Int -> MinQueue a -> [a]
-- | <math>/. drop k, applied to a queue
-- queue, returns queue with the smallest k
-- elements deleted, or an empty queue if k >= size
-- queue.
drop :: Ord a => Int -> MinQueue a -> MinQueue a
-- | <math>/. Equivalent to (take k queue, drop k
-- queue).
splitAt :: Ord a => Int -> MinQueue a -> ([a], MinQueue a)
-- | takeWhile, applied to a predicate p and a queue
-- queue, returns the longest prefix (possibly empty) of
-- queue of elements that satisfy p.
takeWhile :: Ord a => (a -> Bool) -> MinQueue a -> [a]
-- | dropWhile p queue returns the queue remaining after
-- takeWhile p queue.
dropWhile :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
-- | span, applied to a predicate p and a queue
-- queue, returns a tuple where first element is longest prefix
-- (possibly empty) of queue of elements that satisfy p
-- and second element is the remainder of the queue.
span :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
-- | break, applied to a predicate p and a queue
-- queue, returns a tuple where first element is longest prefix
-- (possibly empty) of queue of elements that do not
-- satisfy p and second element is the remainder of the
-- queue.
break :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
-- | <math>. Returns the queue with all elements not satisfying
-- p removed.
filter :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
-- | <math>. Returns a pair where the first queue contains all
-- elements satisfying p, and the second queue contains all
-- elements not satisfying p.
partition :: Ord a => (a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)
-- | <math>. Map elements and collect the Just results.
mapMaybe :: Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b
-- | <math>. Map elements and separate the Left and
-- Right results.
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MinQueue a -> (MinQueue b, MinQueue c)
-- | <math>. Creates a new priority queue containing the images of
-- the elements of this queue. Equivalent to fromList .
-- map f . toList.
map :: Ord b => (a -> b) -> MinQueue a -> MinQueue b
-- | <math>. Performs a right fold on the elements of a priority
-- queue in ascending order.
foldrAsc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b
-- | <math>. Performs a left fold on the elements of a priority queue
-- in ascending order.
foldlAsc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b
-- | <math>. Performs a right fold on the elements of a priority
-- queue in descending order. foldrDesc f z q == foldlAsc (flip f) z
-- q.
foldrDesc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b
-- | <math>. Performs a left fold on the elements of a priority queue
-- in descending order. foldlDesc f z q == foldrAsc (flip f) z
-- q.
foldlDesc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b
-- | <math>. Returns the elements of the priority queue in ascending
-- order. Equivalent to toAscList.
--
-- If the order of the elements is irrelevant, consider using
-- toListU.
toList :: Ord a => MinQueue a -> [a]
-- | <math>. Extracts the elements of the priority queue in ascending
-- order.
toAscList :: Ord a => MinQueue a -> [a]
-- | <math>. Extracts the elements of the priority queue in
-- descending order.
toDescList :: Ord a => MinQueue a -> [a]
-- | <math>. Constructs a priority queue from an unordered list.
fromList :: Ord a => [a] -> MinQueue a
-- | <math>. Constructs a priority queue from an ascending list.
-- Warning: Does not check the precondition.
--
-- Performance note: Code using this function in a performance-sensitive
-- context with an argument that is a "good producer" for list fusion
-- should be compiled with -fspec-constr or -O2. For
-- example, fromAscList . map f needs one of these options for
-- best results.
fromAscList :: [a] -> MinQueue a
-- | <math>. Constructs a priority queue from an descending list.
-- Warning: Does not check the precondition.
fromDescList :: [a] -> MinQueue a
mapU :: (a -> b) -> MinQueue a -> MinQueue b
-- | <math>. Unordered right fold on a priority queue.
foldrU :: (a -> b -> b) -> b -> MinQueue a -> b
-- | <math>. Unordered left fold on a priority queue. This is rarely
-- what you want; foldrU and foldlU' are more likely to
-- perform well.
foldlU :: (b -> a -> b) -> b -> MinQueue a -> b
-- | <math>. Unordered strict left fold on a priority queue.
foldlU' :: (b -> a -> b) -> b -> MinQueue a -> b
-- | <math>. Unordered monoidal fold on a priority queue.
foldMapU :: Monoid m => (a -> m) -> MinQueue a -> m
-- | Equivalent to toListU.
elemsU :: MinQueue a -> [a]
-- | <math>. Returns the elements of the queue, in no particular
-- order.
toListU :: MinQueue a -> [a]
-- | Constructs a priority queue out of the keys of the specified
-- MinPQueue.
keysQueue :: MinPQueue k a -> MinQueue k
-- | <math>. seqSpine q r forces the spine of q and
-- returns r.
--
-- Note: The spine of a MinQueue 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,
-- mapU can leave expensive thunks in the structure and repeated
-- applications of that function can create thunk chains.
seqSpine :: MinQueue a -> b -> b
-- | General purpose priority queue. Each element is associated with a
-- key, and the priority queue supports viewing and extracting the
-- element with the minimum 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.
module Data.PQueue.Prio.Min
-- | A priority queue where values of type a are annotated with
-- keys of type k. The queue supports extracting the element
-- with minimum key.
data MinPQueue k a
-- | <math>. Returns the empty priority queue.
empty :: MinPQueue k a
-- | <math>. Constructs a singleton priority queue.
singleton :: k -> a -> MinPQueue k a
-- | Amortized <math>, worst-case <math>. Inserts an element
-- with the specified key into the queue.
insert :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
-- | <math> (an earlier implementation had <math> 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.
insertBehind :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
-- | Amortized <math>, worst-case <math>. Returns the union of
-- the two specified queues.
union :: Ord k => MinPQueue k a -> MinPQueue k a -> MinPQueue k a
-- | The union of a list of queues: (unions == foldl
-- union empty).
unions :: Ord k => [MinPQueue k a] -> MinPQueue k a
-- | <math>. Checks if this priority queue is empty.
null :: MinPQueue k a -> Bool
-- | <math>. Returns the size of this priority queue.
size :: MinPQueue k a -> Int
-- | <math>. The minimal (key, element) in the queue. Calls
-- error if empty.
findMin :: MinPQueue k a -> (k, a)
-- | <math>. The minimal (key, element) in the queue, if the queue is
-- nonempty.
getMin :: MinPQueue k a -> Maybe (k, a)
-- | <math>. Deletes the minimal (key, element) in the queue. Returns
-- an empty queue if the queue is empty.
deleteMin :: Ord k => MinPQueue k a -> MinPQueue k a
-- | <math>. Delete and find the element with the minimum key. Calls
-- error if empty.
deleteFindMin :: Ord k => MinPQueue k a -> ((k, a), MinPQueue k a)
-- | <math>. Alter the value at the minimum key. If the queue is
-- empty, does nothing.
adjustMin :: (a -> a) -> MinPQueue k a -> MinPQueue k a
-- | <math>. Alter the value at the minimum key in an
-- Applicative context. If the queue is empty, does nothing.
adjustMinA :: Applicative f => (a -> f a) -> MinPQueue k a -> f (MinPQueue k a)
-- | <math>. Alter the value at the minimum key. If the queue is
-- empty, does nothing.
adjustMinWithKey :: (k -> a -> a) -> MinPQueue k a -> MinPQueue k a
-- | <math> per operation. Alter the value at the minimum key in an
-- Applicative context. If the queue is empty, does nothing.
adjustMinWithKeyA :: Applicative f => (k -> a -> f a) -> MinPQueue k a -> f (MinPQueue k a)
-- | <math>. (Actually <math> if there's no deletion.) Update
-- the value at the minimum key. If the queue is empty, does nothing.
updateMin :: Ord k => (a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
-- | <math> per operation. (Actually <math> if there's no
-- deletion.) Update the value at the minimum key. If the queue is empty,
-- does nothing.
updateMinA :: (Applicative f, Ord k) => (a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a)
-- | <math>. (Actually <math> if there's no deletion.) Update
-- the value at the minimum key. If the queue is empty, does nothing.
updateMinWithKey :: Ord k => (k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
-- | <math> per operation. (Actually <math> if there's no
-- deletion.) Update the value at the minimum key in an
-- Applicative context. If the queue is empty, does nothing.
updateMinWithKeyA :: (Applicative f, Ord k) => (k -> a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a)
-- | <math>. Retrieves the value associated with the minimal key of
-- the queue, and the queue stripped of that element, or Nothing
-- if passed an empty queue.
minView :: Ord k => MinPQueue k a -> Maybe (a, MinPQueue k a)
-- | <math>. Retrieves the minimal (key, value) pair of the map, and
-- the map stripped of that element, or Nothing if passed an empty
-- map.
minViewWithKey :: Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
-- | <math>. Map a function over all values in the queue.
map :: (a -> b) -> MinPQueue k a -> MinPQueue k b
-- | <math>. Map a function over all values in the queue.
mapWithKey :: (k -> a -> b) -> MinPQueue k a -> MinPQueue k b
-- | <math>. mapKeys f q is the queue obtained by
-- applying f to each key of q.
mapKeys :: Ord k' => (k -> k') -> MinPQueue k a -> MinPQueue k' a
-- | <math>. 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.
mapKeysMonotonic :: (k -> k') -> MinPQueue k a -> MinPQueue k' a
-- | <math>. Fold the keys and values in the map, such that
-- foldrWithKey f z q == foldr (uncurry f) z
-- (toAscList q).
--
-- If you do not care about the traversal order, consider using
-- foldrWithKeyU.
foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MinPQueue k a -> b
-- | <math>. Fold the keys and values in the map, such that
-- foldlWithKey f z q == foldl (uncurry . f) z
-- (toAscList q).
--
-- If you do not care about the traversal order, consider using
-- foldlWithKeyU.
foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MinPQueue k a -> b
-- | <math>. Traverses the elements of the queue in ascending order
-- by key. (traverseWithKey f q == fromAscList $
-- traverse (uncurry f) (toAscList 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.
traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
-- | 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 () =
-- ⊥.
mapMWithKey :: (Ord k, Monad m) => (k -> a -> m b) -> MinPQueue k a -> m (MinPQueue k b)
-- | <math>/. Takes the first k (key, value) pairs in the
-- queue, or the first n if k >= n. (take
-- k q == take k (toAscList q))
take :: Ord k => Int -> MinPQueue k a -> [(k, a)]
-- | <math>/. Deletes the first k (key, value) pairs in the
-- queue, or returns an empty queue if k >= n.
drop :: Ord k => Int -> MinPQueue k a -> MinPQueue k a
-- | <math>/. Equivalent to (take k q, drop k
-- q).
splitAt :: Ord k => Int -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
-- | Takes the longest possible prefix of elements satisfying the
-- predicate. (takeWhile p q == takeWhile (p .
-- snd) (toAscList q))
takeWhile :: Ord k => (a -> Bool) -> MinPQueue k a -> [(k, a)]
-- | Takes the longest possible prefix of elements satisfying the
-- predicate. (takeWhile p q == takeWhile (uncurry p)
-- (toAscList q))
takeWhileWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> [(k, a)]
-- | Removes the longest possible prefix of elements satisfying the
-- predicate.
dropWhile :: Ord k => (a -> Bool) -> MinPQueue k a -> MinPQueue k a
-- | Removes the longest possible prefix of elements satisfying the
-- predicate.
dropWhileWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
-- | Equivalent to (takeWhile p q, dropWhile p q).
span :: Ord k => (a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
-- | Equivalent to (takeWhileWithKey p q,
-- dropWhileWithKey p q).
spanWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
-- | Equivalent to span (not . p).
break :: Ord k => (a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
-- | Equivalent to spanWithKey ( k a -> not (p k a))
-- q.
breakWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
-- | <math>. Filter all values that satisfy the predicate.
filter :: Ord k => (a -> Bool) -> MinPQueue k a -> MinPQueue k a
-- | <math>. Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
-- | <math>. 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.
partition :: Ord k => (a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
-- | <math>. 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) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
-- | <math>. Map values and collect the Just results.
mapMaybe :: Ord k => (a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
-- | <math>. Map values and collect the Just results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
-- | <math>. Map values and separate the Left and Right
-- results.
mapEither :: Ord k => (a -> Either b c) -> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)
-- | <math>. Map values and separate the Left and Right
-- results.
mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)
-- | <math>. Constructs a priority queue from an unordered list.
fromList :: Ord k => [(k, a)] -> MinPQueue k a
-- | <math>. Build a priority queue from an ascending list of (key,
-- value) pairs. The precondition is not checked.
fromAscList :: [(k, a)] -> MinPQueue k a
-- | <math>. Build a priority queue from a descending list of (key,
-- value) pairs. The precondition is not checked.
fromDescList :: [(k, a)] -> MinPQueue k a
-- | <math>. Return all keys of the queue in ascending order.
keys :: Ord k => MinPQueue k a -> [k]
-- | <math>. Return all elements of the queue in ascending order by
-- key.
elems :: Ord k => MinPQueue k a -> [a]
-- | <math>. Equivalent to toAscList.
assocs :: Ord k => MinPQueue k a -> [(k, a)]
-- | <math>. Return all (key, value) pairs in ascending order by key.
toAscList :: Ord k => MinPQueue k a -> [(k, a)]
-- | <math>. Return all (key, value) pairs in descending order by
-- key.
toDescList :: Ord k => MinPQueue k a -> [(k, a)]
-- | <math>. Equivalent to toAscList.
--
-- If the traversal order is irrelevant, consider using toListU.
toList :: Ord k => MinPQueue k a -> [(k, a)]
-- | <math>. An unordered right fold over the elements of the queue,
-- in no particular order.
foldrU :: (a -> b -> b) -> b -> MinPQueue k a -> b
-- | <math>. An unordered monoidal fold over the elements of the
-- queue, in no particular order.
foldMapWithKeyU :: Monoid m => (k -> a -> m) -> MinPQueue k a -> m
-- | <math>. An unordered right fold over the elements of the queue,
-- in no particular order.
foldrWithKeyU :: (k -> a -> b -> b) -> b -> MinPQueue k a -> b
-- | <math>. 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 -> MinPQueue k a -> b
-- | <math>. An unordered strict left fold over the elements of the
-- queue, in no particular order.
foldlU' :: (b -> a -> b) -> b -> MinPQueue k a -> b
-- | <math>. 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 -> MinPQueue k a -> b
-- | <math>. An unordered strict left fold over the elements of the
-- queue, in no particular order.
foldlWithKeyU' :: (b -> k -> a -> b) -> b -> MinPQueue k a -> b
-- | <math>. 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.
traverseU :: Applicative f => (a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
-- | <math>. 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) -> MinPQueue k a -> f (MinPQueue k b)
-- | <math>. Return all keys of the queue in no particular order.
keysU :: MinPQueue k a -> [k]
-- | <math>. Return all elements of the queue in no particular order.
elemsU :: MinPQueue k a -> [a]
-- | <math>. Equivalent to toListU.
assocsU :: MinPQueue k a -> [(k, a)]
-- | <math>. Returns all (key, value) pairs in the queue in no
-- particular order.
toListU :: MinPQueue k a -> [(k, a)]
-- | <math>. seqSpine q r forces the spine of q and
-- returns r.
--
-- Note: The spine of a MinPQueue 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.
seqSpine :: MinPQueue k a -> b -> b
-- | 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.
module Data.PQueue.Prio.Max
-- | A priority queue where values of type a are annotated with
-- keys of type k. The queue supports extracting the element
-- with maximum key.
data MaxPQueue k a
-- | <math>. Returns the empty priority queue.
empty :: MaxPQueue k a
-- | <math>. Constructs a singleton priority queue.
singleton :: k -> a -> MaxPQueue k a
-- | Amortized <math>, worst-case <math>. Inserts an element
-- with the specified key into the queue.
insert :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
-- | <math> (an earlier implementation had <math> 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.
insertBehind :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
-- | Amortized <math>, worst-case <math>. Returns the union of
-- the two specified queues.
union :: Ord k => MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
-- | The union of a list of queues: (unions == foldl
-- union empty).
unions :: Ord k => [MaxPQueue k a] -> MaxPQueue k a
-- | <math>. Checks if this priority queue is empty.
null :: MaxPQueue k a -> Bool
-- | <math>. Returns the size of this priority queue.
size :: MaxPQueue k a -> Int
-- | <math>. The maximal (key, element) in the queue. Calls
-- error if empty.
findMax :: MaxPQueue k a -> (k, a)
-- | <math>. The maximal (key, element) in the queue, if the queue is
-- nonempty.
getMax :: MaxPQueue k a -> Maybe (k, a)
-- | <math>. Delete and find the element with the maximum key. Calls
-- error if empty.
deleteMax :: Ord k => MaxPQueue k a -> MaxPQueue k a
-- | <math>. Delete and find the element with the maximum key. Calls
-- error if empty.
deleteFindMax :: Ord k => MaxPQueue k a -> ((k, a), MaxPQueue k a)
-- | <math>. Alter the value at the maximum key. If the queue is
-- empty, does nothing.
adjustMax :: (a -> a) -> MaxPQueue k a -> MaxPQueue k a
-- | <math> per operation. Alter the value at the maximum key in an
-- Applicative context. If the queue is empty, does nothing.
adjustMaxA :: Applicative f => (a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a)
-- | <math>. Alter the value at the maximum key. If the queue is
-- empty, does nothing.
adjustMaxWithKey :: (k -> a -> a) -> MaxPQueue k a -> MaxPQueue k a
-- | <math> per operation. Alter the value at the maximum key in an
-- Applicative context. If the queue is empty, does nothing.
adjustMaxWithKeyA :: Applicative f => (k -> a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a)
-- | <math>. (Actually <math> if there's no deletion.) Update
-- the value at the maximum key. If the queue is empty, does nothing.
updateMax :: Ord k => (a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
-- | <math> per operation. (Actually <math> if there's no
-- deletion.) Update the value at the maximum key in an
-- Applicative context. If the queue is empty, does nothing.
updateMaxA :: (Applicative f, Ord k) => (a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a)
-- | <math>. (Actually <math> if there's no deletion.) Update
-- the value at the maximum key. If the queue is empty, does nothing.
updateMaxWithKey :: Ord k => (k -> a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
-- | <math> per operation. (Actually <math> if there's no
-- deletion.) Update the value at the maximum key in an
-- Applicative context. If the queue is empty, does nothing.
updateMaxWithKeyA :: (Applicative f, Ord k) => (k -> a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a)
-- | <math>. 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.
maxView :: Ord k => MaxPQueue k a -> Maybe (a, MaxPQueue k a)
-- | <math>. Retrieves the maximal (key, value) pair of the map, and
-- the map stripped of that element, or Nothing if passed an empty
-- map.
maxViewWithKey :: Ord k => MaxPQueue k a -> Maybe ((k, a), MaxPQueue k a)
-- | <math>. Map a function over all values in the queue.
map :: (a -> b) -> MaxPQueue k a -> MaxPQueue k b
-- | <math>. Map a function over all values in the queue.
mapWithKey :: (k -> a -> b) -> MaxPQueue k a -> MaxPQueue k b
-- | <math>. Map a function over all values in the queue.
mapKeys :: Ord k' => (k -> k') -> MaxPQueue k a -> MaxPQueue k' a
-- | <math>. 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.
mapKeysMonotonic :: (k -> k') -> MaxPQueue k a -> MaxPQueue k' a
-- | <math>. 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.
foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
-- | <math>. 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.
foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
-- | <math>. 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.
traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
-- | 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 () =
-- ⊥.
mapMWithKey :: (Ord k, Monad m) => (k -> a -> m b) -> MaxPQueue k a -> m (MaxPQueue k b)
-- | <math>/. Takes the first k (key, value) pairs in the
-- queue, or the first n if k >= n. (take
-- k q == take k (toDescList q))
take :: Ord k => Int -> MaxPQueue k a -> [(k, a)]
-- | <math>/. Deletes the first k (key, value) pairs in the
-- queue, or returns an empty queue if k >= n.
drop :: Ord k => Int -> MaxPQueue k a -> MaxPQueue k a
-- | <math>/. Equivalent to (take k q, drop k
-- q).
splitAt :: Ord k => Int -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
-- | Takes the longest possible prefix of elements satisfying the
-- predicate. (takeWhile p q == takeWhile (p .
-- snd) (toDescList q))
takeWhile :: Ord k => (a -> Bool) -> MaxPQueue k a -> [(k, a)]
-- | Takes the longest possible prefix of elements satisfying the
-- predicate. (takeWhile p q == takeWhile (uncurry p)
-- (toDescList q))
takeWhileWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> [(k, a)]
-- | Removes the longest possible prefix of elements satisfying the
-- predicate.
dropWhile :: Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
-- | Removes the longest possible prefix of elements satisfying the
-- predicate.
dropWhileWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
-- | Equivalent to (takeWhile p q, dropWhile p q).
span :: Ord k => (a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
-- | Equivalent to spanWithKey (k a -> not (p k a))
-- q.
spanWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
-- | Equivalent to span (not . p).
break :: Ord k => (a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
-- | Equivalent to spanWithKey (k a -> not (p k a))
-- q.
breakWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
-- | <math>. Filter all values that satisfy the predicate.
filter :: Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
-- | <math>. Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
-- | <math>. 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.
partition :: Ord k => (a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a)
-- | <math>. 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)
-- | <math>. Map values and collect the Just results.
mapMaybe :: Ord k => (a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b
-- | <math>. Map values and collect the Just results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b
-- | <math>. Map values and separate the Left and Right
-- results.
mapEither :: Ord k => (a -> Either b c) -> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c)
-- | <math>. 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)
-- | <math>. Build a priority queue from the list of (key, value)
-- pairs.
fromList :: Ord k => [(k, a)] -> MaxPQueue k a
-- | <math>. Build a priority queue from an ascending list of (key,
-- value) pairs. The precondition is not checked.
fromAscList :: [(k, a)] -> MaxPQueue k a
-- | <math>. Build a priority queue from a descending list of (key,
-- value) pairs. The precondition is not checked.
fromDescList :: [(k, a)] -> MaxPQueue k a
-- | <math>. Return all keys of the queue in descending order.
keys :: Ord k => MaxPQueue k a -> [k]
-- | <math>. Return all elements of the queue in descending order by
-- key.
elems :: Ord k => MaxPQueue k a -> [a]
-- | <math>. Equivalent to toDescList.
assocs :: Ord k => MaxPQueue k a -> [(k, a)]
-- | <math>. Return all (key, value) pairs in ascending order by key.
toAscList :: Ord k => MaxPQueue k a -> [(k, a)]
-- | <math>. Return all (key, value) pairs in descending order by
-- key.
toDescList :: Ord k => MaxPQueue k a -> [(k, a)]
-- | <math>. Equivalent to toDescList.
--
-- If the traversal order is irrelevant, consider using toListU.
toList :: Ord k => MaxPQueue k a -> [(k, a)]
-- | <math>. An unordered right fold over the elements of the queue,
-- in no particular order.
foldrU :: (a -> b -> b) -> b -> MaxPQueue k a -> b
-- | <math>. An unordered right fold over the elements of the queue,
-- in no particular order.
foldrWithKeyU :: (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
-- | <math>. An unordered monoidal fold over the elements of the
-- queue, in no particular order.
foldMapWithKeyU :: Monoid m => (k -> a -> m) -> MaxPQueue k a -> m
-- | <math>. 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
-- | <math>. An unordered strict left fold over the elements of the
-- queue, in no particular order.
foldlU' :: (b -> a -> b) -> b -> MaxPQueue k a -> b
-- | <math>. 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
-- | <math>. An unordered left fold over the elements of the queue,
-- in no particular order.
foldlWithKeyU' :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
-- | <math>. 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.
traverseU :: Applicative f => (a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
-- | <math>. 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)
-- | <math>. Return all keys of the queue in no particular order.
keysU :: MaxPQueue k a -> [k]
-- | <math>. Return all elements of the queue in no particular order.
elemsU :: MaxPQueue k a -> [a]
-- | <math>. Equivalent to toListU.
assocsU :: MaxPQueue k a -> [(k, a)]
-- | <math>. Returns all (key, value) pairs in the queue in no
-- particular order.
toListU :: MaxPQueue k a -> [(k, a)]
-- | <math>. 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.
seqSpine :: MaxPQueue k a -> b -> b
-- | General purpose priority queue, supporting view-maximum operations.
--
-- An amortized running time is given for each operation, with n
-- referring to the length of the sequence and k being the
-- integral index used by some operations. These bounds hold even in a
-- persistent (shared) setting.
--
-- This implementation is based on a binomial heap augmented with a
-- global root.
--
-- This implementation does not guarantee stable behavior.
--
-- 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.
module Data.PQueue.Max
-- | A priority queue with elements of type a. Supports extracting
-- the maximum element. Implemented as a wrapper around MinQueue.
data MaxQueue a
-- | <math>. The empty priority queue.
empty :: MaxQueue a
-- | <math>. Is this the empty priority queue?
null :: MaxQueue a -> Bool
-- | <math>. The number of elements in the queue.
size :: MaxQueue a -> Int
-- | <math>. Returns the maximum element of the queue. Throws an
-- error on an empty queue.
findMax :: MaxQueue a -> a
-- | <math>. The top (maximum) element of the queue, if there is one.
getMax :: MaxQueue a -> Maybe a
-- | <math>. Deletes the maximum element of the queue. Does nothing
-- on an empty queue.
deleteMax :: Ord a => MaxQueue a -> MaxQueue a
-- | <math>. Extracts the maximum element of the queue. Throws an
-- error on an empty queue.
deleteFindMax :: Ord a => MaxQueue a -> (a, MaxQueue a)
-- | <math>. Delete the top (maximum) element of the sequence, if
-- there is one.
delete :: Ord a => MaxQueue a -> Maybe (MaxQueue a)
-- | <math>. Extract the top (maximum) element of the sequence, if
-- there is one.
maxView :: Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
-- | <math>. Construct a priority queue with a single element.
singleton :: a -> MaxQueue a
-- | <math>. Insert an element into the priority queue.
insert :: Ord a => a -> MaxQueue a -> MaxQueue a
-- | <math>. Take the union of two priority queues.
union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
-- | Takes the union of a list of priority queues. Equivalent to
-- foldl union empty.
unions :: Ord a => [MaxQueue a] -> MaxQueue a
-- | <math>/. Returns the (k+1)th largest element of the
-- queue.
(!!) :: Ord a => MaxQueue a -> Int -> a
-- | <math>/. Returns the list of the k largest elements of
-- the queue, in descending order, or all elements of the queue, if k
-- >= n.
take :: Ord a => Int -> MaxQueue a -> [a]
-- | <math>/. Returns the queue with the k largest elements
-- deleted, or the empty queue if k >= n.
drop :: Ord a => Int -> MaxQueue a -> MaxQueue a
-- | <math>/. Equivalent to (take k queue, drop k queue).
splitAt :: Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)
-- | takeWhile, applied to a predicate p and a queue
-- queue, returns the longest prefix (possibly empty) of
-- queue of elements that satisfy p.
takeWhile :: Ord a => (a -> Bool) -> MaxQueue a -> [a]
-- | dropWhile p queue returns the queue remaining after
-- takeWhile p queue.
dropWhile :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
-- | span, applied to a predicate p and a queue
-- queue, returns a tuple where first element is longest prefix
-- (possibly empty) of queue of elements that satisfy p
-- and second element is the remainder of the queue.
span :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
-- | break, applied to a predicate p and a queue
-- queue, returns a tuple where first element is longest prefix
-- (possibly empty) of queue of elements that do not
-- satisfy p and second element is the remainder of the
-- queue.
break :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
-- | <math>. Returns a queue of those elements which satisfy the
-- predicate.
filter :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
-- | <math>. Returns a pair of queues, where the left queue contains
-- those elements that satisfy the predicate, and the right queue
-- contains those that do not.
partition :: Ord a => (a -> Bool) -> MaxQueue a -> (MaxQueue a, MaxQueue a)
-- | <math>. Maps a function over the elements of the queue, and
-- collects the Just values.
mapMaybe :: Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue b
-- | <math>. Maps a function over the elements of the queue, and
-- separates the Left and Right values.
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MaxQueue a -> (MaxQueue b, MaxQueue c)
-- | <math>. Creates a new priority queue containing the images of
-- the elements of this queue. Equivalent to fromList .
-- map f . toList.
map :: Ord b => (a -> b) -> MaxQueue a -> MaxQueue b
-- | <math>. Performs a right-fold on the elements of a priority
-- queue in ascending order. foldrAsc f z q ==
-- foldlDesc (flip f) z q.
foldrAsc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
-- | <math>. Performs a left-fold on the elements of a priority queue
-- in descending order. foldlAsc f z q == foldrDesc
-- (flip f) z q.
foldlAsc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
-- | <math>. Performs a right-fold on the elements of a priority
-- queue in descending order.
foldrDesc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
-- | <math>. Performs a left-fold on the elements of a priority queue
-- in descending order.
foldlDesc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
-- | <math>. Returns the elements of the priority queue in ascending
-- order. Equivalent to toDescList.
--
-- If the order of the elements is irrelevant, consider using
-- toListU.
toList :: Ord a => MaxQueue a -> [a]
-- | <math>. Extracts the elements of the priority queue in ascending
-- order.
toAscList :: Ord a => MaxQueue a -> [a]
-- | <math>. Extracts the elements of the priority queue in
-- descending order.
toDescList :: Ord a => MaxQueue a -> [a]
-- | <math>. Constructs a priority queue from an unordered list.
fromList :: Ord a => [a] -> MaxQueue a
-- | <math>. Constructs a priority queue from an ascending list.
-- Warning: Does not check the precondition.
fromAscList :: [a] -> MaxQueue a
-- | <math>. Constructs a priority queue from a descending list.
-- Warning: Does not check the precondition.
fromDescList :: [a] -> MaxQueue a
-- | <math>. Assumes that the function it is given is monotonic, and
-- applies this function to every element of the priority queue. Does
-- not check the precondition.
mapU :: (a -> b) -> MaxQueue a -> MaxQueue b
-- | <math>. Unordered right fold on a priority queue.
foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b
-- | <math>. Unordered left fold on a priority queue. This is rarely
-- what you want; foldrU and foldlU' are more likely to
-- perform well.
foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b
-- | <math>. Unordered strict left fold on a priority queue.
foldlU' :: (b -> a -> b) -> b -> MaxQueue a -> b
-- | <math>. Unordered monoidal fold on a priority queue.
foldMapU :: Monoid m => (a -> m) -> MaxQueue a -> m
-- | Equivalent to toListU.
elemsU :: MaxQueue a -> [a]
-- | <math>. Returns a list of the elements of the priority queue, in
-- no particular order.
toListU :: MaxQueue a -> [a]
-- | <math>. Constructs a priority queue from the keys of a
-- MaxPQueue.
keysQueue :: MaxPQueue k a -> MaxQueue k
-- | <math>. seqSpine q r forces the spine of q and
-- returns r.
--
-- Note: The spine of a MaxQueue 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,
-- mapU can leave expensive thunks in the structure and repeated
-- applications of that function can create thunk chains.
seqSpine :: MaxQueue a -> b -> b
instance (Data.Data.Data a, GHC.Classes.Ord a) => Data.Data.Data (Data.PQueue.Max.MaxQueue a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.PQueue.Max.MaxQueue a)
instance GHC.Classes.Ord a => GHC.Classes.Eq (Data.PQueue.Max.MaxQueue a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.PQueue.Max.MaxQueue a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Data.PQueue.Max.MaxQueue a)
instance GHC.Read.Read a => GHC.Read.Read (Data.PQueue.Max.MaxQueue a)
instance GHC.Classes.Ord a => GHC.Base.Semigroup (Data.PQueue.Max.MaxQueue a)
instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.PQueue.Max.MaxQueue a)