-- 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
--   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 keys of type k are annotated with
--   values of type a. 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
--   MinPQueue. Using :< to construct a queue performs
--   an insertion in <math> amortized time. When matching on (k,
--   a) :< q, forcing q takes <math> time.
pattern (:<) :: Ord k => (k, a) -> MinPQueue k a -> MinPQueue k a
infixr 5 :<

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

-- | Deprecated: This function is not reliable.
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 (weakly) monotonic. The
--   precondition is not checked. This function has better performance
--   than mapKeys.
--   
--   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
--   unspecified.
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. 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.

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

-- | Deprecated: This function is not reliable.
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. 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.

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

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

-- | 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
--   MinQueue. Using :< to construct a queue performs an
--   insertion in <math> amortized time. When matching on a :<
--   q, forcing q takes <math> time.
pattern (:<) :: Ord a => a -> MinQueue a -> MinQueue a
infixr 5 :<

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

-- | <math>. Assumes that the function it is given is (weakly)
--   monotonic, and applies this function to every element of the priority
--   queue, as in fmap. If the function is not monotonic, the result
--   is undefined.
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. 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.

-- | Deprecated: This function is no longer necessary or useful.
seqSpine :: MinQueue 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. 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.

-- | Deprecated: This function is no longer necessary or useful.
seqSpine :: MaxQueue a -> b -> b
instance (GHC.Internal.Data.Data.Data a, GHC.Classes.Ord a) => GHC.Internal.Data.Data.Data (Data.PQueue.Max.MaxQueue a)
instance GHC.Classes.Ord a => GHC.Classes.Eq (Data.PQueue.Max.MaxQueue a)
instance GHC.Classes.Ord a => GHC.Internal.Base.Monoid (Data.PQueue.Max.MaxQueue a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.PQueue.Max.MaxQueue a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.PQueue.Max.MaxQueue a)
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.PQueue.Max.MaxQueue a)
instance GHC.Classes.Ord a => GHC.Internal.Base.Semigroup (Data.PQueue.Max.MaxQueue a)
instance (GHC.Classes.Ord a, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Data.PQueue.Max.MaxQueue a)
