-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Reliable, persistent, fast priority queues.
--
-- A fast, reliable priority queue implementation based on a binomial
-- heap.
@package pqueue
@version 1.4.1.4
-- | 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. The spine of the heap is maintained lazily. To force the
-- spine of the heap, use seqSpine.
--
-- 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
-- | O(1). The empty priority queue.
empty :: MinQueue a
-- | O(1). Is this the empty priority queue?
null :: MinQueue a -> Bool
-- | O(1). The number of elements in the queue.
size :: MinQueue a -> Int
-- | O(1). Returns the minimum element. Throws an error on an empty
-- queue.
findMin :: MinQueue a -> a
-- | Returns the minimum element of the queue, if the queue is nonempty.
getMin :: MinQueue a -> Maybe a
-- | O(log n). Deletes the minimum element. If the queue is empty,
-- does nothing.
deleteMin :: Ord a => MinQueue a -> MinQueue a
-- | O(log n). 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)
-- | O(1). Construct a priority queue with a single element.
singleton :: a -> MinQueue a
-- | Amortized O(1), worst-case O(log n). Insert an element
-- into the priority queue.
insert :: Ord a => a -> MinQueue a -> MinQueue a
-- | Amortized O(log (min(n,m))), worst-case O(log (max
-- (n,m))). 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
-- | O(k log n). 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
-- | O(k log n). 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]
-- | O(k log n). 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
-- | O(k log n). 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)
-- | O(n). Returns the queue with all elements not satisfying
-- p removed.
filter :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
-- | O(n). 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)
-- | O(n). Map elements and collect the Just results.
mapMaybe :: Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b
-- | O(n). Map elements and separate the Left and
-- Right results.
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MinQueue a -> (MinQueue b, MinQueue c)
-- | O(n). 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
-- | O(n log n). Performs a right-fold on the elements of a priority
-- queue in ascending order.
foldrAsc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b
-- | O(n log n). Performs a left-fold on the elements of a priority
-- queue in ascending order.
foldlAsc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b
-- | O(n log n). 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
-- | O(n log n). 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
-- | O(n log n). 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]
-- | O(n log n). Extracts the elements of the priority queue in
-- ascending order.
toAscList :: Ord a => MinQueue a -> [a]
-- | O(n log n). Extracts the elements of the priority queue in
-- descending order.
toDescList :: Ord a => MinQueue a -> [a]
-- | O(n). Constructs a priority queue from an unordered list.
fromList :: Ord a => [a] -> MinQueue a
-- | O(n). Constructs a priority queue from an ascending list.
-- Warning: Does not check the precondition.
fromAscList :: [a] -> MinQueue a
-- | O(n). Constructs a priority queue from an descending list.
-- Warning: Does not check the precondition.
fromDescList :: [a] -> MinQueue a
-- | Maps a function over the elements of the queue, ignoring order. This
-- function is only safe if the function is monotonic. This function
-- does not check the precondition.
mapU :: (a -> b) -> MinQueue a -> MinQueue b
-- | O(n). Unordered right fold on a priority queue.
foldrU :: (a -> b -> b) -> b -> MinQueue a -> b
-- | O(n). Unordered left fold on a priority queue.
foldlU :: (b -> a -> b) -> b -> MinQueue a -> b
-- | Equivalent to toListU.
elemsU :: MinQueue a -> [a]
-- | O(n). 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
-- | Forces the spine of the priority queue.
seqSpine :: MinQueue a -> b -> b
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Data.PQueue.Internals.MinQueue a)
instance GHC.Read.Read a => GHC.Read.Read (Data.PQueue.Internals.MinQueue a)
instance GHC.Classes.Ord a => GHC.Base.Semigroup (Data.PQueue.Internals.MinQueue a)
instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.PQueue.Internals.MinQueue a)
-- | 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. The spine of the heap is maintained lazily. To force the
-- spine of the heap, use seqSpine.
--
-- 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
-- | O(1). The empty priority queue.
empty :: MaxQueue a
-- | O(1). Is this the empty priority queue?
null :: MaxQueue a -> Bool
-- | O(1). The number of elements in the queue.
size :: MaxQueue a -> Int
-- | O(1). Returns the maximum element of the queue. Throws an error
-- on an empty queue.
findMax :: MaxQueue a -> a
-- | O(1). The top (maximum) element of the queue, if there is one.
getMax :: MaxQueue a -> Maybe a
-- | O(log n). Deletes the maximum element of the queue. Does
-- nothing on an empty queue.
deleteMax :: Ord a => MaxQueue a -> MaxQueue a
-- | O(log n). Extracts the maximum element of the queue. Throws an
-- error on an empty queue.
deleteFindMax :: Ord a => MaxQueue a -> (a, MaxQueue a)
-- | O(log n). Delete the top (maximum) element of the sequence, if
-- there is one.
delete :: Ord a => MaxQueue a -> Maybe (MaxQueue a)
-- | O(log n). Extract the top (maximum) element of the sequence, if
-- there is one.
maxView :: Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
-- | O(1). Construct a priority queue with a single element.
singleton :: a -> MaxQueue a
-- | O(1). Insert an element into the priority queue.
insert :: Ord a => a -> MaxQueue a -> MaxQueue a
-- | O(log (min(n1,n2))). 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
-- | O(k log n). Returns the (k+1)th largest element of the
-- queue.
(!!) :: Ord a => MaxQueue a -> Int -> a
-- | O(k log n). 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]
-- | O(k log n). Returns the queue with the k largest
-- elements deleted, or the empty queue if k >= n.
drop :: Ord a => Int -> MaxQueue a -> MaxQueue a
-- | O(k log n). 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)
-- | O(n). Returns a queue of those elements which satisfy the
-- predicate.
filter :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
-- | O(n). 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)
-- | O(n). Maps a function over the elements of the queue, and
-- collects the Just values.
mapMaybe :: Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue b
-- | O(n). 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>. map f xs is the list obtained by
-- applying f to each element of xs, i.e.,
--
--
-- map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
-- map f [x1, x2, ...] == [f x1, f x2, ...]
--
--
--
-- >>> map (+1) [1, 2, 3]
--
map :: (a -> b) -> [a] -> [b]
-- | O(n log n). 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
-- | O(n log n). 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
-- | O(n log n). Performs a right-fold on the elements of a priority
-- queue in descending order.
foldrDesc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
-- | O(n log n). Performs a left-fold on the elements of a priority
-- queue in descending order.
foldlDesc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
-- | O(n log n). 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]
-- | O(n log n). Extracts the elements of the priority queue in
-- ascending order.
toAscList :: Ord a => MaxQueue a -> [a]
-- | O(n log n). Extracts the elements of the priority queue in
-- descending order.
toDescList :: Ord a => MaxQueue a -> [a]
-- | O(n log n). Constructs a priority queue from an unordered list.
fromList :: Ord a => [a] -> MaxQueue a
-- | O(n). Constructs a priority queue from an ascending list.
-- Warning: Does not check the precondition.
fromAscList :: [a] -> MaxQueue a
-- | O(n). Constructs a priority queue from a descending list.
-- Warning: Does not check the precondition.
fromDescList :: [a] -> MaxQueue a
-- | O(n). 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
-- | O(n). Unordered right fold on a priority queue.
foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b
-- | O(n). Unordered left fold on a priority queue.
foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b
-- | Equivalent to toListU.
elemsU :: MaxQueue a -> [a]
-- | O(n). Returns a list of the elements of the priority queue, in
-- no particular order.
toListU :: MaxQueue a -> [a]
-- | O(n). Constructs a priority queue from the keys of a
-- MaxPQueue.
keysQueue :: MaxPQueue k a -> MaxQueue k
-- | O(log n). Forces the spine of the heap.
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)
-- | 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 do not hold in a
-- persistent context.
--
-- This implementation is based on a binomial heap augmented with a
-- global root. The spine of the heap is maintained lazily. To force the
-- spine of the heap, use seqSpine.
--
-- We do not guarantee stable behavior. Ties are broken arbitrarily --
-- that is, if k1 <= k2 and k2 <= k1, then there
-- are no guarantees about the relative order in which k1,
-- k2, and their associated elements are returned. (Unlike
-- Data.Map, we allow multiple elements with the same key.)
--
-- This implementation offers a number of methods of the form
-- xxxU, where U stands for unordered. No guarantees
-- whatsoever are made on the execution or traversal order of these
-- functions.
module Data.PQueue.Prio.Min
-- | A priority queue where values of type a are annotated with
-- keys of type k. The queue supports extracting the element
-- with minimum key.
data MinPQueue k a
-- | O(1). Returns the empty priority queue.
empty :: MinPQueue k a
-- | O(1). Constructs a singleton priority queue.
singleton :: k -> a -> MinPQueue k a
-- | Amortized O(1), worst-case O(log n). Inserts an element
-- with the specified key into the queue.
insert :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
-- | O(n) (an earlier implementation had O(1) but was buggy).
-- Insert an element with the specified key into the priority queue,
-- putting it behind elements whose key compares equal to the inserted
-- one.
insertBehind :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
-- | Amortized O(log(min(n1, n2))), worst-case O(log(max(n1,
-- n2))). 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
-- | O(1). Checks if this priority queue is empty.
null :: MinPQueue k a -> Bool
-- | O(1). Returns the size of this priority queue.
size :: MinPQueue k a -> Int
-- | O(1). The minimal (key, element) in the queue. Calls
-- error if empty.
findMin :: MinPQueue k a -> (k, a)
-- | O(1). The minimal (key, element) in the queue, if the queue is
-- nonempty.
getMin :: MinPQueue k a -> Maybe (k, a)
-- | O(log n). 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
-- | O(log n). Delete and find the element with the minimum key.
-- Calls error if empty.
deleteFindMin :: Ord k => MinPQueue k a -> ((k, a), MinPQueue k a)
-- | O(1). Alter the value at the minimum key. If the queue is
-- empty, does nothing.
adjustMin :: (a -> a) -> MinPQueue k a -> MinPQueue k a
-- | O(1). Alter the value at the minimum key. If the queue is
-- empty, does nothing.
adjustMinWithKey :: (k -> a -> a) -> MinPQueue k a -> MinPQueue k a
-- | O(log n). (Actually O(1) 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
-- | O(log n). (Actually O(1) 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
-- | O(log n). 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)
-- | O(log n). 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)
-- | O(n). Map a function over all values in the queue.
map :: (a -> b) -> MinPQueue k a -> MinPQueue k b
-- | O(n). Map a function over all values in the queue.
mapWithKey :: (k -> a -> b) -> MinPQueue k a -> MinPQueue k b
-- | O(n). 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
-- | O(n). mapKeysMonotonic f q == mapKeys f
-- q, but only works when f is strictly monotonic. The
-- precondition is not checked. This function has better performance
-- than mapKeys.
mapKeysMonotonic :: (k -> k') -> MinPQueue k a -> MinPQueue k' a
-- | O(n log n). 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
-- | O(n log n). 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
-- | O(n log n). 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.
traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
-- | O(k log n). Takes the first k (key, value) pairs in
-- the queue, or the first n if k >= n.
-- (take k q == take k (toAscList q))
take :: Ord k => Int -> MinPQueue k a -> [(k, a)]
-- | O(k log n). 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
-- | O(k log n). 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)
-- | O(n). Filter all values that satisfy the predicate.
filter :: Ord k => (a -> Bool) -> MinPQueue k a -> MinPQueue k a
-- | O(n). Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
-- | O(n). Partition the queue according to a predicate. The first
-- queue contains all elements which satisfy the predicate, the second
-- all elements that fail the predicate.
partition :: Ord k => (a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
-- | O(n). Partition the queue according to a predicate. The first
-- queue contains all elements which satisfy the predicate, the second
-- all elements that fail the predicate.
partitionWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
-- | O(n). Map values and collect the Just results.
mapMaybe :: Ord k => (a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
-- | O(n). Map values and collect the Just results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
-- | O(n). 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)
-- | O(n). 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)
-- | O(n). Build a priority queue from the list of (key, value)
-- pairs.
fromList :: Ord k => [(k, a)] -> MinPQueue k a
-- | O(n). Build a priority queue from an ascending list of (key,
-- value) pairs. The precondition is not checked.
fromAscList :: [(k, a)] -> MinPQueue k a
-- | O(n). Build a priority queue from a descending list of (key,
-- value) pairs. The precondition is not checked.
fromDescList :: [(k, a)] -> MinPQueue k a
-- | O(n log n). Return all keys of the queue in ascending order.
keys :: Ord k => MinPQueue k a -> [k]
-- | O(n log n). Return all elements of the queue in ascending order
-- by key.
elems :: Ord k => MinPQueue k a -> [a]
-- | O(n log n). Equivalent to toAscList.
assocs :: Ord k => MinPQueue k a -> [(k, a)]
-- | O(n log n). Return all (key, value) pairs in ascending order by
-- key.
toAscList :: Ord k => MinPQueue k a -> [(k, a)]
-- | O(n log n). Return all (key, value) pairs in descending order
-- by key.
toDescList :: Ord k => MinPQueue k a -> [(k, a)]
-- | O(n log n). Equivalent to toAscList.
--
-- If the traversal order is irrelevant, consider using toListU.
toList :: Ord k => MinPQueue k a -> [(k, a)]
-- | O(n). An unordered right fold over the elements of the queue,
-- in no particular order.
foldrU :: (a -> b -> b) -> b -> MinPQueue k a -> b
-- | O(n). An unordered right fold over the elements of the queue,
-- in no particular order.
foldrWithKeyU :: (k -> a -> b -> b) -> b -> MinPQueue k a -> b
-- | O(n). An unordered left fold over the elements of the queue, in
-- no particular order.
foldlU :: (b -> a -> b) -> b -> MinPQueue k a -> b
-- | O(n). An unordered left fold over the elements of the queue, in
-- no particular order.
foldlWithKeyU :: (b -> k -> a -> b) -> b -> MinPQueue k a -> b
-- | O(n). An unordered traversal over a priority queue, in no
-- particular order. While there is no guarantee in which order the
-- elements are traversed, the resulting priority queue will be perfectly
-- valid.
traverseU :: Applicative f => (a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
-- | O(n). An unordered traversal over a priority queue, in no
-- particular order. While there is no guarantee in which order the
-- elements are traversed, the resulting priority queue will be perfectly
-- valid.
traverseWithKeyU :: Applicative f => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
-- | O(n). Return all keys of the queue in no particular order.
keysU :: MinPQueue k a -> [k]
-- | O(n). Return all elements of the queue in no particular order.
elemsU :: MinPQueue k a -> [a]
-- | O(n). Equivalent to toListU.
assocsU :: MinPQueue k a -> [(k, a)]
-- | O(n). Returns all (key, value) pairs in the queue in no
-- particular order.
toListU :: MinPQueue k a -> [(k, a)]
-- | O(log n). Analogous to deepseq in the deepseq
-- package, but only forces the spine of the binomial heap.
seqSpine :: MinPQueue k a -> b -> b
instance GHC.Classes.Ord k => GHC.Base.Semigroup (Data.PQueue.Prio.Internals.MinPQueue k a)
instance GHC.Classes.Ord k => GHC.Base.Monoid (Data.PQueue.Prio.Internals.MinPQueue k a)
instance (GHC.Classes.Ord k, GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (Data.PQueue.Prio.Internals.MinPQueue k a)
instance (GHC.Read.Read k, GHC.Read.Read a) => GHC.Read.Read (Data.PQueue.Prio.Internals.MinPQueue k a)
instance GHC.Base.Functor (Data.PQueue.Prio.Internals.MinPQueue k)
instance GHC.Classes.Ord k => Data.Foldable.Foldable (Data.PQueue.Prio.Internals.MinPQueue k)
instance GHC.Classes.Ord k => Data.Traversable.Traversable (Data.PQueue.Prio.Internals.MinPQueue k)
-- | 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 do not hold in a
-- persistent context.
--
-- This implementation is based on a binomial heap augmented with a
-- global root. The spine of the heap is maintained lazily. To force the
-- spine of the heap, use seqSpine.
--
-- 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
-- | O(1). Returns the empty priority queue.
empty :: MaxPQueue k a
-- | O(1). Constructs a singleton priority queue.
singleton :: k -> a -> MaxPQueue k a
-- | Amortized O(1), worst-case O(log n). Inserts an element
-- with the specified key into the queue.
insert :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
-- | O(n) (an earlier implementation had O(1) but was buggy).
-- Insert an element with the specified key into the priority queue,
-- putting it behind elements whose key compares equal to the inserted
-- one.
insertBehind :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
-- | Amortized O(log(min(n1, n2))), worst-case O(log(max(n1,
-- n2))). 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
-- | O(1). Checks if this priority queue is empty.
null :: MaxPQueue k a -> Bool
-- | O(1). Returns the size of this priority queue.
size :: MaxPQueue k a -> Int
-- | O(1). The maximal (key, element) in the queue. Calls
-- error if empty.
findMax :: MaxPQueue k a -> (k, a)
-- | O(1). The maximal (key, element) in the queue, if the queue is
-- nonempty.
getMax :: MaxPQueue k a -> Maybe (k, a)
-- | O(log n). Delete and find the element with the maximum key.
-- Calls error if empty.
deleteMax :: Ord k => MaxPQueue k a -> MaxPQueue k a
-- | O(log n). Delete and find the element with the maximum key.
-- Calls error if empty.
deleteFindMax :: Ord k => MaxPQueue k a -> ((k, a), MaxPQueue k a)
-- | O(1). Alter the value at the maximum key. If the queue is
-- empty, does nothing.
adjustMax :: (a -> a) -> MaxPQueue k a -> MaxPQueue k a
-- | O(1). Alter the value at the maximum key. If the queue is
-- empty, does nothing.
adjustMaxWithKey :: (k -> a -> a) -> MaxPQueue k a -> MaxPQueue k a
-- | O(log n). (Actually O(1) if there's no deletion.) Update
-- the value at the maximum key. If the queue is empty, does nothing.
updateMax :: Ord k => (a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
-- | O(log n). (Actually O(1) if there's no deletion.) Update
-- the value at the maximum key. If the queue is empty, does nothing.
updateMaxWithKey :: Ord k => (k -> a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
-- | O(log n). Retrieves the value associated with the maximum key
-- of the queue, and the queue stripped of that element, or
-- Nothing if passed an empty queue.
maxView :: Ord k => MaxPQueue k a -> Maybe (a, MaxPQueue k a)
-- | O(log n). Retrieves the maximal (key, value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
maxViewWithKey :: Ord k => MaxPQueue k a -> Maybe ((k, a), MaxPQueue k a)
-- | O(n). Map a function over all values in the queue.
map :: (a -> b) -> MaxPQueue k a -> MaxPQueue k b
-- | O(n). Map a function over all values in the queue.
mapWithKey :: (k -> a -> b) -> MaxPQueue k a -> MaxPQueue k b
-- | O(n). Map a function over all values in the queue.
mapKeys :: Ord k' => (k -> k') -> MaxPQueue k a -> MaxPQueue k' a
-- | O(n). mapKeysMonotonic f q == mapKeys f
-- q, but only works when f is strictly monotonic. The
-- precondition is not checked. This function has better performance
-- than mapKeys.
mapKeysMonotonic :: (k -> k') -> MaxPQueue k a -> MaxPQueue k' a
-- | O(n log n). Fold the keys and values in the map, such that
-- foldrWithKey f z q == foldr (uncurry f) z
-- (toDescList q).
--
-- If you do not care about the traversal order, consider using
-- foldrWithKeyU.
foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
-- | O(n log n). Fold the keys and values in the map, such that
-- foldlWithKey f z q == foldl (uncurry . f) z
-- (toDescList q).
--
-- If you do not care about the traversal order, consider using
-- foldlWithKeyU.
foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
-- | O(n log n). Traverses the elements of the queue in descending
-- order by key. (traverseWithKey f q == fromDescList
-- $ traverse (uncurry f) (toDescList
-- q))
--
-- If you do not care about the order of the traversal, consider
-- using traverseWithKeyU.
traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
-- | O(k log n). Takes the first k (key, value) pairs in
-- the queue, or the first n if k >= n.
-- (take k q == take k (toDescList q))
take :: Ord k => Int -> MaxPQueue k a -> [(k, a)]
-- | O(k log n). 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
-- | O(k log n). 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)
-- | O(n). Filter all values that satisfy the predicate.
filter :: Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
-- | O(n). Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
-- | O(n). Partition the queue according to a predicate. The first
-- queue contains all elements which satisfy the predicate, the second
-- all elements that fail the predicate.
partition :: Ord k => (a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a)
-- | O(n). Partition the queue according to a predicate. The first
-- queue contains all elements which satisfy the predicate, the second
-- all elements that fail the predicate.
partitionWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a)
-- | O(n). Map values and collect the Just results.
mapMaybe :: Ord k => (a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b
-- | O(n). Map values and collect the Just results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b
-- | O(n). 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)
-- | O(n). Map values and separate the Left and Right
-- results.
mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c)
-- | O(n). Build a priority queue from the list of (key, value)
-- pairs.
fromList :: Ord k => [(k, a)] -> MaxPQueue k a
-- | O(n). Build a priority queue from an ascending list of (key,
-- value) pairs. The precondition is not checked.
fromAscList :: [(k, a)] -> MaxPQueue k a
-- | O(n). Build a priority queue from a descending list of (key,
-- value) pairs. The precondition is not checked.
fromDescList :: [(k, a)] -> MaxPQueue k a
-- | O(n log n). Return all keys of the queue in descending order.
keys :: Ord k => MaxPQueue k a -> [k]
-- | O(n log n). Return all elements of the queue in descending
-- order by key.
elems :: Ord k => MaxPQueue k a -> [a]
-- | O(n log n). Equivalent to toDescList.
assocs :: Ord k => MaxPQueue k a -> [(k, a)]
-- | O(n log n). Return all (key, value) pairs in ascending order by
-- key.
toAscList :: Ord k => MaxPQueue k a -> [(k, a)]
-- | O(n log n). Return all (key, value) pairs in descending order
-- by key.
toDescList :: Ord k => MaxPQueue k a -> [(k, a)]
-- | O(n log n). Equivalent to toDescList.
--
-- If the traversal order is irrelevant, consider using toListU.
toList :: Ord k => MaxPQueue k a -> [(k, a)]
-- | O(n). An unordered right fold over the elements of the queue,
-- in no particular order.
foldrU :: (a -> b -> b) -> b -> MaxPQueue k a -> b
-- | O(n). An unordered right fold over the elements of the queue,
-- in no particular order.
foldrWithKeyU :: (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
-- | O(n). An unordered left fold over the elements of the queue, in
-- no particular order.
foldlU :: (b -> a -> b) -> b -> MaxPQueue k a -> b
-- | O(n). An unordered left fold over the elements of the queue, in
-- no particular order.
foldlWithKeyU :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
-- | O(n). An unordered traversal over a priority queue, in no
-- particular order. While there is no guarantee in which order the
-- elements are traversed, the resulting priority queue will be perfectly
-- valid.
traverseU :: Applicative f => (a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
-- | O(n). An unordered traversal over a priority queue, in no
-- particular order. While there is no guarantee in which order the
-- elements are traversed, the resulting priority queue will be perfectly
-- valid.
traverseWithKeyU :: Applicative f => (k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
-- | O(n). Return all keys of the queue in no particular order.
keysU :: MaxPQueue k a -> [k]
-- | O(n). Return all elements of the queue in no particular order.
elemsU :: MaxPQueue k a -> [a]
-- | O(n). Equivalent to toListU.
assocsU :: MaxPQueue k a -> [(k, a)]
-- | O(n). Returns all (key, value) pairs in the queue in no
-- particular order.
toListU :: MaxPQueue k a -> [(k, a)]
-- | O(log n). Analogous to deepseq in the deepseq
-- package, but only forces the spine of the binomial heap.
seqSpine :: MaxPQueue k a -> b -> b
instance GHC.Classes.Ord k => GHC.Base.Semigroup (Data.PQueue.Prio.Max.Internals.MaxPQueue k a)
instance GHC.Classes.Ord k => GHC.Base.Monoid (Data.PQueue.Prio.Max.Internals.MaxPQueue k a)
instance (GHC.Classes.Ord k, GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (Data.PQueue.Prio.Max.Internals.MaxPQueue k a)
instance (GHC.Read.Read k, GHC.Read.Read a) => GHC.Read.Read (Data.PQueue.Prio.Max.Internals.MaxPQueue k a)
instance GHC.Base.Functor (Data.PQueue.Prio.Max.Internals.MaxPQueue k)
instance GHC.Classes.Ord k => Data.Foldable.Foldable (Data.PQueue.Prio.Max.Internals.MaxPQueue k)
instance GHC.Classes.Ord k => Data.Traversable.Traversable (Data.PQueue.Prio.Max.Internals.MaxPQueue k)