-- 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.0.0 -- | General purpose priority queue, supporting extract-minimum operations. -- -- An amortized running time is given for each operation, with n -- referring to the length of the sequence and 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. The spine of the heap is maintained strictly, ensuring -- that computations happen as they are performed. -- -- This implementation does not guarantee stable behavior. -- -- WARNING: toList and toAscList are not -- equivalent, unlike for example Data.Map. module Data.PQueue.Min -- | A priority queue implementation. Implemented as a find-min wrapper -- around a binomial heap. -- -- If you wish to perform folds on a priority queue that respect order, -- use foldrAsc or foldlAsc. -- -- For any operation op in Eq or Ord, queue1 -- op queue2 is equivalent to toAscList queue1 -- op toAscList queue2. 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 findMin :: MinQueue a -> a getMin :: MinQueue a -> Maybe a deleteMin :: (Ord a) => MinQueue a -> MinQueue a deleteFindMin :: (Ord a) => MinQueue a -> (a, MinQueue a) 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 . -- Data.List.map f . toList. map :: (Ord b) => (a -> b) -> MinQueue a -> MinQueue b -- | O(n). Assumes that the function it is given is monotonic, and -- applies this function to every element of the priority queue, as in -- fmap. If it is not, the result is undefined. mapMonotonic :: (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). 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 -- | O(n). Unordered right fold on a priority queue. foldrU :: (a -> b -> b) -> b -> MinQueue a -> b foldlU :: (b -> a -> b) -> b -> MinQueue a -> b traverseU :: (Applicative f, Ord b) => (a -> f b) -> MinQueue a -> f (MinQueue b) elemsU :: MinQueue a -> [a] 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 (Ord a) => Monoid (MinQueue a) instance (Read a) => Read (MinQueue a) instance (Ord a, Show a) => Show (MinQueue 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. 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 -- | 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. alterMin :: (a -> a) -> MinPQueue k a -> MinPQueue k a -- | O(1). Alter the value at the minimum key. If the queue is -- empty, does nothing. alterMinWithKey :: (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 == List.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 == List.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, Ord b) => (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, Ord b) => (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 (Ord k) => Traversable (MinPQueue k) instance (Ord k) => Foldable (MinPQueue k) instance Functor (MinPQueue k) instance (Read k, Read a) => Read (MinPQueue k a) instance (Ord k, Show k, Show a) => Show (MinPQueue k a) instance (Ord k) => Monoid (MinPQueue k a) -- | General purpose priority queue, supporting extract-minimum operations. -- Each element is associated with a key, and the priority queue -- supports viewing and extracting the element with the minimum key. -- -- An amortized running time is given for each operation, with n -- referring to the length of the sequence and 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. The spine of the heap is maintained lazily. -- -- This implementation does 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. -- -- This implementation offers a number of methods of the form -- xxxU, where U stands for unordered. No -- guarantees 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 -- | 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. alterMax :: (a -> a) -> MaxPQueue k a -> MaxPQueue k a -- | O(1). Alter the value at the maximum key. If the queue is -- empty, does nothing. alterMaxWithKey :: (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 -- (toAscList 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 -- (toAscList 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) (toAscList 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) -- (toAscList 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 ascending order. keys :: (Ord k) => MaxPQueue k a -> [k] -- | O(n log n). Return all elements of the queue in ascending 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 toAscList. -- -- 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, Ord b) => (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, Ord b) => (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 (Eq a, Ord k) => Eq (MaxPQueue k a) instance (Ord k, Ord a) => Ord (MaxPQueue k a) instance (Eq a) => Eq (Down a) instance (Ord k) => Traversable (MaxPQueue k) instance (Ord k) => Foldable (MaxPQueue k) instance Functor (MaxPQueue k) instance Functor Down instance (Ord a) => Ord (Down a) module Data.PQueue.Max data MaxQueue a empty :: MaxQueue a singleton :: a -> MaxQueue a insert :: (Ord a) => a -> MaxQueue a -> MaxQueue a union :: (Ord a) => MaxQueue a -> MaxQueue a -> MaxQueue a unions :: (Ord a) => [MaxQueue a] -> MaxQueue a null :: MaxQueue a -> Bool size :: MaxQueue a -> Int findMax :: MaxQueue a -> a getMax :: MaxQueue a -> Maybe a deleteMax :: (Ord a) => MaxQueue a -> MaxQueue a deleteFindMax :: (Ord a) => MaxQueue a -> (a, MaxQueue a) maxView :: (Ord a) => MaxQueue a -> Maybe (a, MaxQueue a) map :: (Ord b) => (a -> b) -> MaxQueue a -> MaxQueue b mapMonotonic :: (a -> b) -> MaxQueue a -> MaxQueue b foldr :: (Ord a) => (a -> b -> b) -> b -> MaxQueue a -> b foldl :: (Ord a) => (b -> a -> b) -> b -> MaxQueue a -> b traverse :: (Applicative f, Ord a, Ord b) => (a -> f b) -> MaxQueue a -> f (MaxQueue b) take :: (Ord a) => Int -> MaxQueue a -> [a] drop :: (Ord a) => Int -> MaxQueue a -> MaxQueue a splitAt :: (Ord a) => Int -> MaxQueue a -> ([a], MaxQueue a) takeWhile :: (Ord a) => (a -> Bool) -> MaxQueue a -> [a] dropWhile :: (Ord a) => (a -> Bool) -> MaxQueue a -> MaxQueue a span :: (Ord a) => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a) break :: (Ord a) => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a) filter :: (Ord a) => (a -> Bool) -> MaxQueue a -> MaxQueue a partition :: (Ord a) => (a -> Bool) -> MaxQueue a -> (MaxQueue a, MaxQueue a) fromList :: (Ord a) => [a] -> MaxQueue a fromDescList :: [a] -> MaxQueue a fromAscList :: [a] -> MaxQueue a elems :: (Ord a) => MaxQueue a -> [a] toList :: (Ord a) => MaxQueue a -> [a] toDescList :: (Ord a) => MaxQueue a -> [a] pqueueKeys :: MaxPQueue k a -> MaxQueue k foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b toListU :: (Ord a) => MaxQueue a -> [a] seqSpine :: MaxQueue a -> b -> b instance (Ord a) => Eq (MaxQueue a) instance (Ord a) => Ord (MaxQueue a)