-- 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.5.0.0


-- | General purpose priority queue. Each element is associated with a
--   <i>key</i>, 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 <tt>k1 &lt;= k2</tt> and <tt>k2 &lt;= k1</tt>, then there
--   are no guarantees about the relative order in which <tt>k1</tt>,
--   <tt>k2</tt>, 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
--   <tt>xxxU</tt>, where <tt>U</tt> 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 keys of type <tt>k</tt> are annotated with
--   values of type <tt>a</tt>. The queue supports extracting the key-value
--   pair with minimum key.
data MinPQueue k a

-- | A bidirectional pattern synonym for an empty priority queue.
pattern Empty :: MinPQueue k a

-- | A bidirectional pattern synonym for working with the minimum view of a
--   <a>MinPQueue</a>. Using <tt>:&lt;</tt> to construct a queue performs
--   an insertion in &lt;math&gt; amortized time. When matching on <tt>(k,
--   a) :&lt; q</tt>, forcing <tt>q</tt> takes &lt;math&gt; time.
pattern (:<) :: Ord k => (k, a) -> MinPQueue k a -> MinPQueue k a
infixr 5 :<

-- | &lt;math&gt;. Returns the empty priority queue.
empty :: MinPQueue k a

-- | &lt;math&gt;. Constructs a singleton priority queue.
singleton :: k -> a -> MinPQueue k a

-- | Amortized &lt;math&gt;, worst-case &lt;math&gt;. Inserts an element
--   with the specified key into the queue.
insert :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a

-- | &lt;math&gt; (an earlier implementation had &lt;math&gt; 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.

-- | <i>Deprecated: This function is not reliable.</i>
insertBehind :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a

-- | Amortized &lt;math&gt;, worst-case &lt;math&gt;. 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: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: Ord k => [MinPQueue k a] -> MinPQueue k a

-- | &lt;math&gt;. Checks if this priority queue is empty.
null :: MinPQueue k a -> Bool

-- | &lt;math&gt;. Returns the size of this priority queue.
size :: MinPQueue k a -> Int

-- | &lt;math&gt;. The minimal (key, element) in the queue. Calls
--   <a>error</a> if empty.
findMin :: MinPQueue k a -> (k, a)

-- | &lt;math&gt;. The minimal (key, element) in the queue, if the queue is
--   nonempty.
getMin :: MinPQueue k a -> Maybe (k, a)

-- | &lt;math&gt;. 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

-- | &lt;math&gt;. Delete and find the element with the minimum key. Calls
--   <a>error</a> if empty.
deleteFindMin :: Ord k => MinPQueue k a -> ((k, a), MinPQueue k a)

-- | &lt;math&gt;. Alter the value at the minimum key. If the queue is
--   empty, does nothing.
adjustMin :: (a -> a) -> MinPQueue k a -> MinPQueue k a

-- | &lt;math&gt;. Alter the value at the minimum key in an
--   <a>Applicative</a> context. If the queue is empty, does nothing.
adjustMinA :: Applicative f => (a -> f a) -> MinPQueue k a -> f (MinPQueue k a)

-- | &lt;math&gt;. Alter the value at the minimum key. If the queue is
--   empty, does nothing.
adjustMinWithKey :: (k -> a -> a) -> MinPQueue k a -> MinPQueue k a

-- | &lt;math&gt; per operation. Alter the value at the minimum key in an
--   <a>Applicative</a> context. If the queue is empty, does nothing.
adjustMinWithKeyA :: Applicative f => (k -> a -> f a) -> MinPQueue k a -> f (MinPQueue k a)

-- | &lt;math&gt;. (Actually &lt;math&gt; 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

-- | &lt;math&gt; per operation. (Actually &lt;math&gt; 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)

-- | &lt;math&gt;. (Actually &lt;math&gt; 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

-- | &lt;math&gt; per operation. (Actually &lt;math&gt; if there's no
--   deletion.) Update the value at the minimum key in an
--   <a>Applicative</a> 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)

-- | &lt;math&gt;. Retrieves the value associated with the minimal key of
--   the queue, and the queue stripped of that element, or <a>Nothing</a>
--   if passed an empty queue.
minView :: Ord k => MinPQueue k a -> Maybe (a, MinPQueue k a)

-- | &lt;math&gt;. Retrieves the minimal (key, value) pair of the map, and
--   the map stripped of that element, or <a>Nothing</a> if passed an empty
--   map.
minViewWithKey :: Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)

-- | &lt;math&gt;. Map a function over all values in the queue.
map :: (a -> b) -> MinPQueue k a -> MinPQueue k b

-- | &lt;math&gt;. Map a function over all values in the queue.
mapWithKey :: (k -> a -> b) -> MinPQueue k a -> MinPQueue k b

-- | &lt;math&gt;. <tt><a>mapKeys</a> f q</tt> is the queue obtained by
--   applying <tt>f</tt> to each key of <tt>q</tt>.
mapKeys :: Ord k' => (k -> k') -> MinPQueue k a -> MinPQueue k' a

-- | &lt;math&gt;. <tt><a>mapKeysMonotonic</a> f q == <tt>mapKeys</tt> f
--   q</tt>, but only works when <tt>f</tt> is (weakly) monotonic. <i>The
--   precondition is not checked.</i> This function has better performance
--   than <tt>mapKeys</tt>.
--   
--   Note: if the given function returns bottom for any of the keys in the
--   queue, then the portion of the queue which is bottom is
--   <i>unspecified</i>.
mapKeysMonotonic :: (k -> k') -> MinPQueue k a -> MinPQueue k' a

-- | &lt;math&gt;. Fold the keys and values in the map, such that
--   <tt><a>foldrWithKey</a> f z q == <a>foldr</a> (<a>uncurry</a> f) z
--   (<a>toAscList</a> q)</tt>.
--   
--   If you do not care about the traversal order, consider using
--   <a>foldrWithKeyU</a>.
foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MinPQueue k a -> b

-- | &lt;math&gt;. Fold the keys and values in the map, such that
--   <tt><a>foldlWithKey</a> f z q == <a>foldl</a> (<a>uncurry</a> . f) z
--   (<a>toAscList</a> q)</tt>.
--   
--   If you do not care about the traversal order, consider using
--   <a>foldlWithKeyU</a>.
foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MinPQueue k a -> b

-- | &lt;math&gt;. Traverses the elements of the queue in ascending order
--   by key. (<tt><a>traverseWithKey</a> f q == <a>fromAscList</a> <a>$</a>
--   <a>traverse</a> (<a>uncurry</a> f) (<a>toAscList</a> q)</tt>)
--   
--   If you do not care about the <i>order</i> of the traversal, consider
--   using <a>traverseWithKeyU</a>.
--   
--   If you are working in a strict monad, consider using
--   <a>mapMWithKey</a>.
traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)

-- | A strictly accumulating version of <a>traverseWithKey</a>. This works
--   well in <a>IO</a> and strict <tt>State</tt>, and is likely what you
--   want for other "strict" monads, where <tt>⊥ &gt;&gt;= pure () =
--   ⊥</tt>.
mapMWithKey :: (Ord k, Monad m) => (k -> a -> m b) -> MinPQueue k a -> m (MinPQueue k b)

-- | &lt;math&gt;/. Takes the first <tt>k</tt> (key, value) pairs in the
--   queue, or the first <tt>n</tt> if <tt>k &gt;= n</tt>. (<tt><a>take</a>
--   k q == <a>take</a> k (<a>toAscList</a> q)</tt>)
take :: Ord k => Int -> MinPQueue k a -> [(k, a)]

-- | &lt;math&gt;/. Deletes the first <tt>k</tt> (key, value) pairs in the
--   queue, or returns an empty queue if <tt>k &gt;= n</tt>.
drop :: Ord k => Int -> MinPQueue k a -> MinPQueue k a

-- | &lt;math&gt;/. Equivalent to <tt>(<a>take</a> k q, <a>drop</a> k
--   q)</tt>.
splitAt :: Ord k => Int -> MinPQueue k a -> ([(k, a)], MinPQueue k a)

-- | Takes the longest possible prefix of elements satisfying the
--   predicate. (<tt><a>takeWhile</a> p q == <a>takeWhile</a> (p .
--   <a>snd</a>) (<a>toAscList</a> q)</tt>)
takeWhile :: Ord k => (a -> Bool) -> MinPQueue k a -> [(k, a)]

-- | Takes the longest possible prefix of elements satisfying the
--   predicate. (<tt><a>takeWhile</a> p q == <a>takeWhile</a> (uncurry p)
--   (<a>toAscList</a> q)</tt>)
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 <tt>(<a>takeWhile</a> p q, <a>dropWhile</a> p q)</tt>.
span :: Ord k => (a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)

-- | Equivalent to <tt>(<a>takeWhileWithKey</a> p q,
--   <a>dropWhileWithKey</a> p q)</tt>.
spanWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)

-- | Equivalent to <tt><a>span</a> (<a>not</a> . p)</tt>.
break :: Ord k => (a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)

-- | Equivalent to <tt><a>spanWithKey</a> ( k a -&gt; <a>not</a> (p k a))
--   q</tt>.
breakWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)

-- | &lt;math&gt;. Filter all values that satisfy the predicate.
filter :: Ord k => (a -> Bool) -> MinPQueue k a -> MinPQueue k a

-- | &lt;math&gt;. Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a

-- | &lt;math&gt;. 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)

-- | &lt;math&gt;. 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)

-- | &lt;math&gt;. Map values and collect the <a>Just</a> results.
mapMaybe :: Ord k => (a -> Maybe b) -> MinPQueue k a -> MinPQueue k b

-- | &lt;math&gt;. Map values and collect the <a>Just</a> results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MinPQueue k a -> MinPQueue k b

-- | &lt;math&gt;. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEither :: Ord k => (a -> Either b c) -> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)

-- | &lt;math&gt;. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)

-- | &lt;math&gt;. Constructs a priority queue from an unordered list.
fromList :: Ord k => [(k, a)] -> MinPQueue k a

-- | &lt;math&gt;. Build a priority queue from an ascending list of (key,
--   value) pairs. <i>The precondition is not checked.</i>
fromAscList :: [(k, a)] -> MinPQueue k a

-- | &lt;math&gt;. Build a priority queue from a descending list of (key,
--   value) pairs. <i>The precondition is not checked.</i>
fromDescList :: [(k, a)] -> MinPQueue k a

-- | &lt;math&gt;. Return all keys of the queue in ascending order.
keys :: Ord k => MinPQueue k a -> [k]

-- | &lt;math&gt;. Return all elements of the queue in ascending order by
--   key.
elems :: Ord k => MinPQueue k a -> [a]

-- | &lt;math&gt;. Equivalent to <a>toAscList</a>.
assocs :: Ord k => MinPQueue k a -> [(k, a)]

-- | &lt;math&gt;. Return all (key, value) pairs in ascending order by key.
toAscList :: Ord k => MinPQueue k a -> [(k, a)]

-- | &lt;math&gt;. Return all (key, value) pairs in descending order by
--   key.
toDescList :: Ord k => MinPQueue k a -> [(k, a)]

-- | &lt;math&gt;. Equivalent to <a>toAscList</a>.
--   
--   If the traversal order is irrelevant, consider using <a>toListU</a>.
toList :: Ord k => MinPQueue k a -> [(k, a)]

-- | &lt;math&gt;. An unordered right fold over the elements of the queue,
--   in no particular order.
foldrU :: (a -> b -> b) -> b -> MinPQueue k a -> b

-- | &lt;math&gt;. An unordered monoidal fold over the elements of the
--   queue, in no particular order.
foldMapWithKeyU :: forall m k a. Monoid m => (k -> a -> m) -> MinPQueue k a -> m

-- | &lt;math&gt;. An unordered right fold over the elements of the queue,
--   in no particular order.
foldrWithKeyU :: (k -> a -> b -> b) -> b -> MinPQueue k a -> b

-- | &lt;math&gt;. An unordered left fold over the elements of the queue,
--   in no particular order. This is rarely what you want; <a>foldrU</a>
--   and <a>foldlU'</a> are more likely to perform well.
foldlU :: (b -> a -> b) -> b -> MinPQueue k a -> b

-- | &lt;math&gt;. An unordered strict left fold over the elements of the
--   queue, in no particular order.
foldlU' :: (b -> a -> b) -> b -> MinPQueue k a -> b

-- | &lt;math&gt;. An unordered left fold over the elements of the queue,
--   in no particular order. This is rarely what you want;
--   <a>foldrWithKeyU</a> and <a>foldlWithKeyU'</a> are more likely to
--   perform well.
foldlWithKeyU :: (b -> k -> a -> b) -> b -> MinPQueue k a -> b

-- | &lt;math&gt;. 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

-- | &lt;math&gt;. 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)

-- | &lt;math&gt;. 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 :: forall f k a b. Applicative f => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)

-- | &lt;math&gt;. Return all keys of the queue in no particular order.
keysU :: MinPQueue k a -> [k]

-- | &lt;math&gt;. Return all elements of the queue in no particular order.
elemsU :: MinPQueue k a -> [a]

-- | &lt;math&gt;. Equivalent to <a>toListU</a>.
assocsU :: MinPQueue k a -> [(k, a)]

-- | &lt;math&gt;. Returns all (key, value) pairs in the queue in no
--   particular order.
toListU :: MinPQueue k a -> [(k, a)]

-- | &lt;math&gt;. <tt>seqSpine q r</tt> forces the spine of <tt>q</tt> and
--   returns <tt>r</tt>.
--   
--   Note: The spine of a <a>MinPQueue</a> is stored somewhat lazily. In
--   earlier versions of this package, some operations could produce chains
--   of thunks along the spine, occasionally necessitating manual forcing.
--   Now, all operations are careful to force enough to avoid this problem.

-- | <i>Deprecated: This function is no longer necessary or useful.</i>
seqSpine :: MinPQueue k a -> b -> b


-- | General purpose priority queue. Each element is associated with a
--   <i>key</i>, 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 <tt>k1 &lt;= k2</tt> and <tt>k2 &lt;= k1</tt>, then there
--   are no guarantees about the relative order in which <tt>k1</tt>,
--   <tt>k2</tt>, 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
--   <tt>xxxU</tt>, where <tt>U</tt> 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 <tt>a</tt> are annotated with
--   keys of type <tt>k</tt>. The queue supports extracting the element
--   with maximum key.
data MaxPQueue k a

-- | &lt;math&gt;. Returns the empty priority queue.
empty :: MaxPQueue k a

-- | &lt;math&gt;. Constructs a singleton priority queue.
singleton :: k -> a -> MaxPQueue k a

-- | Amortized &lt;math&gt;, worst-case &lt;math&gt;. Inserts an element
--   with the specified key into the queue.
insert :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a

-- | &lt;math&gt; (an earlier implementation had &lt;math&gt; 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.

-- | <i>Deprecated: This function is not reliable.</i>
insertBehind :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a

-- | Amortized &lt;math&gt;, worst-case &lt;math&gt;. 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: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: Ord k => [MaxPQueue k a] -> MaxPQueue k a

-- | &lt;math&gt;. Checks if this priority queue is empty.
null :: MaxPQueue k a -> Bool

-- | &lt;math&gt;. Returns the size of this priority queue.
size :: MaxPQueue k a -> Int

-- | &lt;math&gt;. The maximal (key, element) in the queue. Calls
--   <a>error</a> if empty.
findMax :: MaxPQueue k a -> (k, a)

-- | &lt;math&gt;. The maximal (key, element) in the queue, if the queue is
--   nonempty.
getMax :: MaxPQueue k a -> Maybe (k, a)

-- | &lt;math&gt;. Delete and find the element with the maximum key. Calls
--   <a>error</a> if empty.
deleteMax :: Ord k => MaxPQueue k a -> MaxPQueue k a

-- | &lt;math&gt;. Delete and find the element with the maximum key. Calls
--   <a>error</a> if empty.
deleteFindMax :: Ord k => MaxPQueue k a -> ((k, a), MaxPQueue k a)

-- | &lt;math&gt;. Alter the value at the maximum key. If the queue is
--   empty, does nothing.
adjustMax :: (a -> a) -> MaxPQueue k a -> MaxPQueue k a

-- | &lt;math&gt; per operation. Alter the value at the maximum key in an
--   <a>Applicative</a> context. If the queue is empty, does nothing.
adjustMaxA :: Applicative f => (a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a)

-- | &lt;math&gt;. Alter the value at the maximum key. If the queue is
--   empty, does nothing.
adjustMaxWithKey :: (k -> a -> a) -> MaxPQueue k a -> MaxPQueue k a

-- | &lt;math&gt; per operation. Alter the value at the maximum key in an
--   <a>Applicative</a> context. If the queue is empty, does nothing.
adjustMaxWithKeyA :: Applicative f => (k -> a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a)

-- | &lt;math&gt;. (Actually &lt;math&gt; 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

-- | &lt;math&gt; per operation. (Actually &lt;math&gt; if there's no
--   deletion.) Update the value at the maximum key in an
--   <a>Applicative</a> context. If the queue is empty, does nothing.
updateMaxA :: (Applicative f, Ord k) => (a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a)

-- | &lt;math&gt;. (Actually &lt;math&gt; 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

-- | &lt;math&gt; per operation. (Actually &lt;math&gt; if there's no
--   deletion.) Update the value at the maximum key in an
--   <a>Applicative</a> 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)

-- | &lt;math&gt;. Retrieves the value associated with the maximum key of
--   the queue, and the queue stripped of that element, or <a>Nothing</a>
--   if passed an empty queue.
maxView :: Ord k => MaxPQueue k a -> Maybe (a, MaxPQueue k a)

-- | &lt;math&gt;. Retrieves the maximal (key, value) pair of the map, and
--   the map stripped of that element, or <a>Nothing</a> if passed an empty
--   map.
maxViewWithKey :: Ord k => MaxPQueue k a -> Maybe ((k, a), MaxPQueue k a)

-- | &lt;math&gt;. Map a function over all values in the queue.
map :: (a -> b) -> MaxPQueue k a -> MaxPQueue k b

-- | &lt;math&gt;. Map a function over all values in the queue.
mapWithKey :: (k -> a -> b) -> MaxPQueue k a -> MaxPQueue k b

-- | &lt;math&gt;. Map a function over all values in the queue.
mapKeys :: Ord k' => (k -> k') -> MaxPQueue k a -> MaxPQueue k' a

-- | &lt;math&gt;. <tt><a>mapKeysMonotonic</a> f q == <a>mapKeys</a> f
--   q</tt>, but only works when <tt>f</tt> is strictly monotonic. <i>The
--   precondition is not checked.</i> This function has better performance
--   than <a>mapKeys</a>.
mapKeysMonotonic :: (k -> k') -> MaxPQueue k a -> MaxPQueue k' a

-- | &lt;math&gt;. Fold the keys and values in the map, such that
--   <tt><a>foldrWithKey</a> f z q == <a>foldr</a> (<a>uncurry</a> f) z
--   (<a>toDescList</a> q)</tt>.
--   
--   If you do not care about the traversal order, consider using
--   <a>foldrWithKeyU</a>.
foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MaxPQueue k a -> b

-- | &lt;math&gt;. Fold the keys and values in the map, such that
--   <tt><a>foldlWithKey</a> f z q == <a>foldl</a> (<a>uncurry</a> . f) z
--   (<a>toDescList</a> q)</tt>.
--   
--   If you do not care about the traversal order, consider using
--   <a>foldlWithKeyU</a>.
foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MaxPQueue k a -> b

-- | &lt;math&gt;. Traverses the elements of the queue in descending order
--   by key. (<tt><a>traverseWithKey</a> f q == <a>fromDescList</a>
--   <a>$</a> <a>traverse</a> (<a>uncurry</a> f) (<a>toDescList</a>
--   q)</tt>)
--   
--   If you do not care about the <i>order</i> of the traversal, consider
--   using <a>traverseWithKeyU</a>.
--   
--   If you are working in a strict monad, consider using
--   <a>mapMWithKey</a>.
traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)

-- | A strictly accumulating version of <a>traverseWithKey</a>. This works
--   well in <a>IO</a> and strict <tt>State</tt>, and is likely what you
--   want for other "strict" monads, where <tt>⊥ &gt;&gt;= pure () =
--   ⊥</tt>.
mapMWithKey :: (Ord k, Monad m) => (k -> a -> m b) -> MaxPQueue k a -> m (MaxPQueue k b)

-- | &lt;math&gt;/. Takes the first <tt>k</tt> (key, value) pairs in the
--   queue, or the first <tt>n</tt> if <tt>k &gt;= n</tt>. (<tt><a>take</a>
--   k q == <a>take</a> k (<a>toDescList</a> q)</tt>)
take :: Ord k => Int -> MaxPQueue k a -> [(k, a)]

-- | &lt;math&gt;/. Deletes the first <tt>k</tt> (key, value) pairs in the
--   queue, or returns an empty queue if <tt>k &gt;= n</tt>.
drop :: Ord k => Int -> MaxPQueue k a -> MaxPQueue k a

-- | &lt;math&gt;/. Equivalent to <tt>(<a>take</a> k q, <a>drop</a> k
--   q)</tt>.
splitAt :: Ord k => Int -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)

-- | Takes the longest possible prefix of elements satisfying the
--   predicate. (<tt><a>takeWhile</a> p q == <a>takeWhile</a> (p .
--   <a>snd</a>) (<a>toDescList</a> q)</tt>)
takeWhile :: Ord k => (a -> Bool) -> MaxPQueue k a -> [(k, a)]

-- | Takes the longest possible prefix of elements satisfying the
--   predicate. (<tt><a>takeWhile</a> p q == <a>takeWhile</a> (uncurry p)
--   (<a>toDescList</a> q)</tt>)
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 <tt>(<a>takeWhile</a> p q, <a>dropWhile</a> p q)</tt>.
span :: Ord k => (a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)

-- | Equivalent to <tt><a>spanWithKey</a> (k a -&gt; <a>not</a> (p k a))
--   q</tt>.
spanWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)

-- | Equivalent to <tt><a>span</a> (<a>not</a> . p)</tt>.
break :: Ord k => (a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)

-- | Equivalent to <tt><a>spanWithKey</a> (k a -&gt; <a>not</a> (p k a))
--   q</tt>.
breakWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)

-- | &lt;math&gt;. Filter all values that satisfy the predicate.
filter :: Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a

-- | &lt;math&gt;. Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a

-- | &lt;math&gt;. 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)

-- | &lt;math&gt;. 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)

-- | &lt;math&gt;. Map values and collect the <a>Just</a> results.
mapMaybe :: Ord k => (a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b

-- | &lt;math&gt;. Map values and collect the <a>Just</a> results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b

-- | &lt;math&gt;. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEither :: Ord k => (a -> Either b c) -> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c)

-- | &lt;math&gt;. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c)

-- | &lt;math&gt;. Build a priority queue from the list of (key, value)
--   pairs.
fromList :: Ord k => [(k, a)] -> MaxPQueue k a

-- | &lt;math&gt;. Build a priority queue from an ascending list of (key,
--   value) pairs. <i>The precondition is not checked.</i>
fromAscList :: [(k, a)] -> MaxPQueue k a

-- | &lt;math&gt;. Build a priority queue from a descending list of (key,
--   value) pairs. <i>The precondition is not checked.</i>
fromDescList :: [(k, a)] -> MaxPQueue k a

-- | &lt;math&gt;. Return all keys of the queue in descending order.
keys :: Ord k => MaxPQueue k a -> [k]

-- | &lt;math&gt;. Return all elements of the queue in descending order by
--   key.
elems :: Ord k => MaxPQueue k a -> [a]

-- | &lt;math&gt;. Equivalent to <a>toDescList</a>.
assocs :: Ord k => MaxPQueue k a -> [(k, a)]

-- | &lt;math&gt;. Return all (key, value) pairs in ascending order by key.
toAscList :: Ord k => MaxPQueue k a -> [(k, a)]

-- | &lt;math&gt;. Return all (key, value) pairs in descending order by
--   key.
toDescList :: Ord k => MaxPQueue k a -> [(k, a)]

-- | &lt;math&gt;. Equivalent to <a>toDescList</a>.
--   
--   If the traversal order is irrelevant, consider using <a>toListU</a>.
toList :: Ord k => MaxPQueue k a -> [(k, a)]

-- | &lt;math&gt;. An unordered right fold over the elements of the queue,
--   in no particular order.
foldrU :: (a -> b -> b) -> b -> MaxPQueue k a -> b

-- | &lt;math&gt;. An unordered right fold over the elements of the queue,
--   in no particular order.
foldrWithKeyU :: (k -> a -> b -> b) -> b -> MaxPQueue k a -> b

-- | &lt;math&gt;. An unordered monoidal fold over the elements of the
--   queue, in no particular order.
foldMapWithKeyU :: Monoid m => (k -> a -> m) -> MaxPQueue k a -> m

-- | &lt;math&gt;. An unordered left fold over the elements of the queue,
--   in no particular order. This is rarely what you want; <a>foldrU</a>
--   and <a>foldlU'</a> are more likely to perform well.
foldlU :: (b -> a -> b) -> b -> MaxPQueue k a -> b

-- | &lt;math&gt;. An unordered strict left fold over the elements of the
--   queue, in no particular order.
foldlU' :: (b -> a -> b) -> b -> MaxPQueue k a -> b

-- | &lt;math&gt;. An unordered left fold over the elements of the queue,
--   in no particular order. This is rarely what you want;
--   <a>foldrWithKeyU</a> and <a>foldlWithKeyU'</a> are more likely to
--   perform well.
foldlWithKeyU :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b

-- | &lt;math&gt;. An unordered left fold over the elements of the queue,
--   in no particular order.
foldlWithKeyU' :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b

-- | &lt;math&gt;. 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)

-- | &lt;math&gt;. 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)

-- | &lt;math&gt;. Return all keys of the queue in no particular order.
keysU :: MaxPQueue k a -> [k]

-- | &lt;math&gt;. Return all elements of the queue in no particular order.
elemsU :: MaxPQueue k a -> [a]

-- | &lt;math&gt;. Equivalent to <a>toListU</a>.
assocsU :: MaxPQueue k a -> [(k, a)]

-- | &lt;math&gt;. Returns all (key, value) pairs in the queue in no
--   particular order.
toListU :: MaxPQueue k a -> [(k, a)]

-- | &lt;math&gt;. <tt>seqSpine q r</tt> forces the spine of <tt>q</tt> and
--   returns <tt>r</tt>.
--   
--   Note: The spine of a <a>MaxPQueue</a> is stored somewhat lazily. In
--   earlier versions of this package, some operations could produce chains
--   of thunks along the spine, occasionally necessitating manual forcing.
--   Now, all operations are careful to force enough to avoid this problem.

-- | <i>Deprecated: This function is no longer necessary or useful.</i>
seqSpine :: MaxPQueue k a -> b -> b


-- | General purpose priority queue, supporting extract-minimum operations.
--   
--   An amortized running time is given for each operation, with <i>n</i>
--   referring to the length of the sequence and <i>k</i> 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
--   <tt>xxxU</tt>, where <tt>U</tt> 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 <tt>a</tt>. Supports extracting
--   the minimum element.
data MinQueue a

-- | A bidirectional pattern synonym for an empty priority queue.
pattern Empty :: MinQueue a

-- | A bidirectional pattern synonym for working with the minimum view of a
--   <a>MinQueue</a>. Using <tt>:&lt;</tt> to construct a queue performs an
--   insertion in &lt;math&gt; amortized time. When matching on <tt>a :&lt;
--   q</tt>, forcing <tt>q</tt> takes &lt;math&gt; time.
pattern (:<) :: Ord a => a -> MinQueue a -> MinQueue a
infixr 5 :<

-- | &lt;math&gt;. The empty priority queue.
empty :: MinQueue a

-- | &lt;math&gt;. Is this the empty priority queue?
null :: MinQueue a -> Bool

-- | &lt;math&gt;. The number of elements in the queue.
size :: MinQueue a -> Int

-- | &lt;math&gt;. Returns the minimum element. Throws an error on an empty
--   queue.
findMin :: MinQueue a -> a

-- | &lt;math&gt;. Returns the minimum element of the queue, if the queue
--   is nonempty.
getMin :: MinQueue a -> Maybe a

-- | &lt;math&gt;. Deletes the minimum element. If the queue is empty, does
--   nothing.
deleteMin :: Ord a => MinQueue a -> MinQueue a

-- | &lt;math&gt;. 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 <a>Nothing</a> if passed an empty queue.
minView :: Ord a => MinQueue a -> Maybe (a, MinQueue a)

-- | &lt;math&gt;. Construct a priority queue with a single element.
singleton :: a -> MinQueue a

-- | Amortized &lt;math&gt;, worst-case &lt;math&gt;. Insert an element
--   into the priority queue.
insert :: Ord a => a -> MinQueue a -> MinQueue a

-- | Amortized &lt;math&gt;, worst-case &lt;math&gt;. 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
--   <tt><a>foldl'</a> <a>union</a> <a>empty</a></tt>.
unions :: Ord a => [MinQueue a] -> MinQueue a

-- | &lt;math&gt;/. Index (subscript) operator, starting from 0. <tt>queue
--   !! k</tt> returns the <tt>(k+1)</tt>th smallest element in the queue.
--   Equivalent to <tt>toAscList queue !! k</tt>.
(!!) :: Ord a => MinQueue a -> Int -> a

-- | &lt;math&gt;/. <a>take</a> <tt>k</tt>, applied to a queue
--   <tt>queue</tt>, returns a list of the smallest <tt>k</tt> elements of
--   <tt>queue</tt>, or all elements of <tt>queue</tt> itself if <tt>k
--   &gt;= <a>size</a> queue</tt>.
take :: Ord a => Int -> MinQueue a -> [a]

-- | &lt;math&gt;/. <a>drop</a> <tt>k</tt>, applied to a queue
--   <tt>queue</tt>, returns <tt>queue</tt> with the smallest <tt>k</tt>
--   elements deleted, or an empty queue if <tt>k &gt;= size
--   <tt>queue</tt></tt>.
drop :: Ord a => Int -> MinQueue a -> MinQueue a

-- | &lt;math&gt;/. Equivalent to <tt>(<a>take</a> k queue, <a>drop</a> k
--   queue)</tt>.
splitAt :: Ord a => Int -> MinQueue a -> ([a], MinQueue a)

-- | <a>takeWhile</a>, applied to a predicate <tt>p</tt> and a queue
--   <tt>queue</tt>, returns the longest prefix (possibly empty) of
--   <tt>queue</tt> of elements that satisfy <tt>p</tt>.
takeWhile :: Ord a => (a -> Bool) -> MinQueue a -> [a]

-- | <a>dropWhile</a> <tt>p queue</tt> returns the queue remaining after
--   <a>takeWhile</a> <tt>p queue</tt>.
dropWhile :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a

-- | <a>span</a>, applied to a predicate <tt>p</tt> and a queue
--   <tt>queue</tt>, returns a tuple where first element is longest prefix
--   (possibly empty) of <tt>queue</tt> of elements that satisfy <tt>p</tt>
--   and second element is the remainder of the queue.
span :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)

-- | <a>break</a>, applied to a predicate <tt>p</tt> and a queue
--   <tt>queue</tt>, returns a tuple where first element is longest prefix
--   (possibly empty) of <tt>queue</tt> of elements that <i>do not
--   satisfy</i> <tt>p</tt> and second element is the remainder of the
--   queue.
break :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)

-- | &lt;math&gt;. Returns the queue with all elements not satisfying
--   <tt>p</tt> removed.
filter :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a

-- | &lt;math&gt;. Returns a pair where the first queue contains all
--   elements satisfying <tt>p</tt>, and the second queue contains all
--   elements not satisfying <tt>p</tt>.
partition :: Ord a => (a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)

-- | &lt;math&gt;. Map elements and collect the <a>Just</a> results.
mapMaybe :: Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b

-- | &lt;math&gt;. Map elements and separate the <a>Left</a> and
--   <a>Right</a> results.
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MinQueue a -> (MinQueue b, MinQueue c)

-- | &lt;math&gt;. Creates a new priority queue containing the images of
--   the elements of this queue. Equivalent to <tt><a>fromList</a> .
--   <a>map</a> f . toList</tt>.
map :: Ord b => (a -> b) -> MinQueue a -> MinQueue b

-- | &lt;math&gt;. Performs a right fold on the elements of a priority
--   queue in ascending order.
foldrAsc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b

-- | &lt;math&gt;. Performs a left fold on the elements of a priority queue
--   in ascending order.
foldlAsc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b

-- | &lt;math&gt;. Performs a right fold on the elements of a priority
--   queue in descending order. <tt>foldrDesc f z q == foldlAsc (flip f) z
--   q</tt>.
foldrDesc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b

-- | &lt;math&gt;. Performs a left fold on the elements of a priority queue
--   in descending order. <tt>foldlDesc f z q == foldrAsc (flip f) z
--   q</tt>.
foldlDesc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b

-- | &lt;math&gt;. Returns the elements of the priority queue in ascending
--   order. Equivalent to <a>toAscList</a>.
--   
--   If the order of the elements is irrelevant, consider using
--   <a>toListU</a>.
toList :: Ord a => MinQueue a -> [a]

-- | &lt;math&gt;. Extracts the elements of the priority queue in ascending
--   order.
toAscList :: Ord a => MinQueue a -> [a]

-- | &lt;math&gt;. Extracts the elements of the priority queue in
--   descending order.
toDescList :: Ord a => MinQueue a -> [a]

-- | &lt;math&gt;. Constructs a priority queue from an unordered list.
fromList :: Ord a => [a] -> MinQueue a

-- | &lt;math&gt;. Constructs a priority queue from an ascending list.
--   <i>Warning</i>: 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 <tt>-fspec-constr</tt> or <tt>-O2</tt>. For
--   example, <tt>fromAscList . map f</tt> needs one of these options for
--   best results.
fromAscList :: [a] -> MinQueue a

-- | &lt;math&gt;. Constructs a priority queue from an descending list.
--   <i>Warning</i>: Does not check the precondition.
fromDescList :: [a] -> MinQueue a

-- | &lt;math&gt;. Assumes that the function it is given is (weakly)
--   monotonic, and applies this function to every element of the priority
--   queue, as in <a>fmap</a>. If the function is not monotonic, the result
--   is undefined.
mapU :: (a -> b) -> MinQueue a -> MinQueue b

-- | &lt;math&gt;. Unordered right fold on a priority queue.
foldrU :: (a -> b -> b) -> b -> MinQueue a -> b

-- | &lt;math&gt;. Unordered left fold on a priority queue. This is rarely
--   what you want; <a>foldrU</a> and <a>foldlU'</a> are more likely to
--   perform well.
foldlU :: (b -> a -> b) -> b -> MinQueue a -> b

-- | &lt;math&gt;. Unordered strict left fold on a priority queue.
foldlU' :: (b -> a -> b) -> b -> MinQueue a -> b

-- | &lt;math&gt;. Unordered monoidal fold on a priority queue.
foldMapU :: Monoid m => (a -> m) -> MinQueue a -> m

-- | Equivalent to <a>toListU</a>.
elemsU :: MinQueue a -> [a]

-- | &lt;math&gt;. 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
--   <a>MinPQueue</a>.
keysQueue :: MinPQueue k a -> MinQueue k

-- | &lt;math&gt;. <tt>seqSpine q r</tt> forces the spine of <tt>q</tt> and
--   returns <tt>r</tt>.
--   
--   Note: The spine of a <a>MinQueue</a> is stored somewhat lazily. In
--   earlier versions of this package, some operations could produce chains
--   of thunks along the spine, occasionally necessitating manual forcing.
--   Now, all operations are careful to force enough to avoid this problem.

-- | <i>Deprecated: This function is no longer necessary or useful.</i>
seqSpine :: MinQueue a -> b -> b


-- | General purpose priority queue, supporting view-maximum operations.
--   
--   An amortized running time is given for each operation, with <i>n</i>
--   referring to the length of the sequence and <i>k</i> 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
--   <tt>xxxU</tt>, where <tt>U</tt> 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 <tt>a</tt>. Supports extracting
--   the maximum element. Implemented as a wrapper around <a>MinQueue</a>.
data MaxQueue a

-- | &lt;math&gt;. The empty priority queue.
empty :: MaxQueue a

-- | &lt;math&gt;. Is this the empty priority queue?
null :: MaxQueue a -> Bool

-- | &lt;math&gt;. The number of elements in the queue.
size :: MaxQueue a -> Int

-- | &lt;math&gt;. Returns the maximum element of the queue. Throws an
--   error on an empty queue.
findMax :: MaxQueue a -> a

-- | &lt;math&gt;. The top (maximum) element of the queue, if there is one.
getMax :: MaxQueue a -> Maybe a

-- | &lt;math&gt;. Deletes the maximum element of the queue. Does nothing
--   on an empty queue.
deleteMax :: Ord a => MaxQueue a -> MaxQueue a

-- | &lt;math&gt;. Extracts the maximum element of the queue. Throws an
--   error on an empty queue.
deleteFindMax :: Ord a => MaxQueue a -> (a, MaxQueue a)

-- | &lt;math&gt;. Delete the top (maximum) element of the sequence, if
--   there is one.
delete :: Ord a => MaxQueue a -> Maybe (MaxQueue a)

-- | &lt;math&gt;. Extract the top (maximum) element of the sequence, if
--   there is one.
maxView :: Ord a => MaxQueue a -> Maybe (a, MaxQueue a)

-- | &lt;math&gt;. Construct a priority queue with a single element.
singleton :: a -> MaxQueue a

-- | &lt;math&gt;. Insert an element into the priority queue.
insert :: Ord a => a -> MaxQueue a -> MaxQueue a

-- | &lt;math&gt;. 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
--   <tt><a>foldl</a> <a>union</a> <a>empty</a></tt>.
unions :: Ord a => [MaxQueue a] -> MaxQueue a

-- | &lt;math&gt;/. Returns the <tt>(k+1)</tt>th largest element of the
--   queue.
(!!) :: Ord a => MaxQueue a -> Int -> a

-- | &lt;math&gt;/. Returns the list of the <tt>k</tt> largest elements of
--   the queue, in descending order, or all elements of the queue, if <tt>k
--   &gt;= n</tt>.
take :: Ord a => Int -> MaxQueue a -> [a]

-- | &lt;math&gt;/. Returns the queue with the <tt>k</tt> largest elements
--   deleted, or the empty queue if <tt>k &gt;= n</tt>.
drop :: Ord a => Int -> MaxQueue a -> MaxQueue a

-- | &lt;math&gt;/. Equivalent to <tt>(take k queue, drop k queue)</tt>.
splitAt :: Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)

-- | <a>takeWhile</a>, applied to a predicate <tt>p</tt> and a queue
--   <tt>queue</tt>, returns the longest prefix (possibly empty) of
--   <tt>queue</tt> of elements that satisfy <tt>p</tt>.
takeWhile :: Ord a => (a -> Bool) -> MaxQueue a -> [a]

-- | <a>dropWhile</a> <tt>p queue</tt> returns the queue remaining after
--   <a>takeWhile</a> <tt>p queue</tt>.
dropWhile :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a

-- | <a>span</a>, applied to a predicate <tt>p</tt> and a queue
--   <tt>queue</tt>, returns a tuple where first element is longest prefix
--   (possibly empty) of <tt>queue</tt> of elements that satisfy <tt>p</tt>
--   and second element is the remainder of the queue.
span :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)

-- | <a>break</a>, applied to a predicate <tt>p</tt> and a queue
--   <tt>queue</tt>, returns a tuple where first element is longest prefix
--   (possibly empty) of <tt>queue</tt> of elements that <i>do not
--   satisfy</i> <tt>p</tt> and second element is the remainder of the
--   queue.
break :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)

-- | &lt;math&gt;. Returns a queue of those elements which satisfy the
--   predicate.
filter :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a

-- | &lt;math&gt;. 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)

-- | &lt;math&gt;. Maps a function over the elements of the queue, and
--   collects the <a>Just</a> values.
mapMaybe :: Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue b

-- | &lt;math&gt;. Maps a function over the elements of the queue, and
--   separates the <a>Left</a> and <a>Right</a> values.
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MaxQueue a -> (MaxQueue b, MaxQueue c)

-- | &lt;math&gt;. Creates a new priority queue containing the images of
--   the elements of this queue. Equivalent to <tt><a>fromList</a> .
--   <a>map</a> f . toList</tt>.
map :: Ord b => (a -> b) -> MaxQueue a -> MaxQueue b

-- | &lt;math&gt;. Performs a right-fold on the elements of a priority
--   queue in ascending order. <tt><a>foldrAsc</a> f z q ==
--   <a>foldlDesc</a> (flip f) z q</tt>.
foldrAsc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b

-- | &lt;math&gt;. Performs a left-fold on the elements of a priority queue
--   in descending order. <tt><a>foldlAsc</a> f z q == <a>foldrDesc</a>
--   (flip f) z q</tt>.
foldlAsc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b

-- | &lt;math&gt;. Performs a right-fold on the elements of a priority
--   queue in descending order.
foldrDesc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b

-- | &lt;math&gt;. Performs a left-fold on the elements of a priority queue
--   in descending order.
foldlDesc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b

-- | &lt;math&gt;. Returns the elements of the priority queue in ascending
--   order. Equivalent to <a>toDescList</a>.
--   
--   If the order of the elements is irrelevant, consider using
--   <a>toListU</a>.
toList :: Ord a => MaxQueue a -> [a]

-- | &lt;math&gt;. Extracts the elements of the priority queue in ascending
--   order.
toAscList :: Ord a => MaxQueue a -> [a]

-- | &lt;math&gt;. Extracts the elements of the priority queue in
--   descending order.
toDescList :: Ord a => MaxQueue a -> [a]

-- | &lt;math&gt;. Constructs a priority queue from an unordered list.
fromList :: Ord a => [a] -> MaxQueue a

-- | &lt;math&gt;. Constructs a priority queue from an ascending list.
--   <i>Warning</i>: Does not check the precondition.
fromAscList :: [a] -> MaxQueue a

-- | &lt;math&gt;. Constructs a priority queue from a descending list.
--   <i>Warning</i>: Does not check the precondition.
fromDescList :: [a] -> MaxQueue a

-- | &lt;math&gt;. Assumes that the function it is given is monotonic, and
--   applies this function to every element of the priority queue. <i>Does
--   not check the precondition</i>.
mapU :: (a -> b) -> MaxQueue a -> MaxQueue b

-- | &lt;math&gt;. Unordered right fold on a priority queue.
foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b

-- | &lt;math&gt;. Unordered left fold on a priority queue. This is rarely
--   what you want; <a>foldrU</a> and <a>foldlU'</a> are more likely to
--   perform well.
foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b

-- | &lt;math&gt;. Unordered strict left fold on a priority queue.
foldlU' :: (b -> a -> b) -> b -> MaxQueue a -> b

-- | &lt;math&gt;. Unordered monoidal fold on a priority queue.
foldMapU :: Monoid m => (a -> m) -> MaxQueue a -> m

-- | Equivalent to <a>toListU</a>.
elemsU :: MaxQueue a -> [a]

-- | &lt;math&gt;. Returns a list of the elements of the priority queue, in
--   no particular order.
toListU :: MaxQueue a -> [a]

-- | &lt;math&gt;. Constructs a priority queue from the keys of a
--   <a>MaxPQueue</a>.
keysQueue :: MaxPQueue k a -> MaxQueue k

-- | &lt;math&gt;. <tt>seqSpine q r</tt> forces the spine of <tt>q</tt> and
--   returns <tt>r</tt>.
--   
--   Note: The spine of a <a>MaxQueue</a> is stored somewhat lazily. In
--   earlier versions of this package, some operations could produce chains
--   of thunks along the spine, occasionally necessitating manual forcing.
--   Now, all operations are careful to force enough to avoid this problem.

-- | <i>Deprecated: This function is no longer necessary or useful.</i>
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)
