packages feed

pqueue 1.0.0 → 1.0.1

raw patch · 7 files changed

+358/−155 lines, 7 files

Files

Data/PQueue/Internals.hs view
@@ -39,13 +39,7 @@  import Prelude hiding (foldl, foldr, null) --- | 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@.+-- | A priority queue with elements of type @a@.  Supports extracting the minimum element. data MinQueue a = Empty | MinQueue {-# UNPACK #-} !Int a !(BinomHeap a)  #ifdef __GLASGOW_HASKELL__@@ -168,10 +162,13 @@ size Empty = 0 size (MinQueue n _ _) = n +-- | Returns the minimum element of the queue, if the queue is nonempty. getMin :: MinQueue a -> Maybe a getMin (MinQueue _ x _) = Just x getMin _ = Nothing +-- | 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) minView Empty = Nothing minView (MinQueue n x ts) = Just (x, case extractHeap ts of@@ -427,6 +424,7 @@ foldrU _ z Empty = z foldrU f z (MinQueue _ x ts) = x `f` foldr f z ts +-- | /O(n)/.  Unordered left fold on a priority queue. foldlU :: (b -> a -> b) -> b -> MinQueue a -> b foldlU _ z Empty = z foldlU f z (MinQueue _ x ts) = foldl f (z `f` x) ts
Data/PQueue/Max.hs view
@@ -1,33 +1,50 @@ {-# LANGUAGE CPP #-} +-----------------------------------------------------------------------------+-- |+-- Module      :  Data.PQueue.Min+-- Copyright   :  (c) Louis Wasserman 2010+-- License     :  BSD-style+-- Maintainer  :  libraries@haskell.org+-- Stability   :  experimental+-- Portability :  portable+--+-- General purpose priority queue, supporting maxView-maximum 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 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 ( 	MaxQueue,-	-- * Construction+	-- * Basic operations 	empty,-	singleton,-	insert,-	union,-	unions,-	-- * Query 	null,-	size,-	-- ** Maximum view+	size, +	-- * Query operations 	findMax, 	getMax, 	deleteMax, 	deleteFindMax, 	maxView,-	-- * Traversal-	-- ** Map-	map,-	mapMonotonic,-	-- ** Fold-	foldr,-	foldl,-	-- ** Traverse-	traverse,+	-- * Construction operations+	singleton,+	insert,+	union,+	unions, 	-- * Subsets-	-- ** Indexed+	-- ** Extracting subsets+	(!!), 	take, 	drop, 	splitAt,@@ -36,35 +53,49 @@ 	dropWhile, 	span, 	break,-	-- *** Filter+	-- * Filter/Map 	filter, 	partition,+	mapMaybe,+	mapEither,+	-- * Fold\/Functor\/Traversable variations+	map,+	foldrAsc,+	foldlAsc,+	foldrDesc,+	foldlDesc, 	-- * List operations-	-- ** Conversion from lists-	fromList,-	fromDescList,-	fromAscList,-	-- ** Conversion to lists-	elems, 	toList,+	toAscList, 	toDescList,-	-- * Conversion with MaxPQueue-	pqueueKeys,+	fromList,+	fromAscList,+	fromDescList, 	-- * Unordered operations+	mapU, 	foldrU, 	foldlU,+	traverseU,+	elemsU, 	toListU,-	-- * Helper methods+	-- * Miscellaneous operations+	keysQueue, 	seqSpine) where -import Control.Applicative hiding (empty)-import Data.Maybe hiding (mapMaybe)+import Control.Applicative (Applicative(..), (<$>))+ import Data.Monoid-import qualified Data.List as List-import qualified Data.PQueue.Prio.Max as Q+import Data.Maybe hiding (mapMaybe)+import Data.Foldable hiding (toList)+import Data.Traversable+import Data.Ord -import Prelude hiding (map, filter, break, span, takeWhile, dropWhile, splitAt, take, drop, (!!), null, foldr, foldl)+import qualified Data.PQueue.Min as Min+import qualified Data.PQueue.Prio.Max.Internals as Prio+import Data.PQueue.Prio.Max.Internals (Down(..)) +import Prelude hiding (null, foldr, foldl, take, drop, takeWhile, dropWhile, splitAt, span, break, (!!), filter)+ #ifdef __GLASGOW_HASKELL__ import GHC.Exts (build) import Text.Read (Lexeme(Ident), lexP, parens, prec,@@ -75,143 +106,241 @@ build f = f (:) [] #endif -newtype MaxQueue a = MaxQ (Q.MaxPQueue a ()) deriving (Eq, Ord)--null :: MaxQueue a -> Bool-null (MaxQ q) = Q.null q+-- | A priority queue implementation.  Implemented as a wrapper around "Data.PQueue.Min". +-- /Warning/: the 'Functor', 'Foldable', and 'Traversable' instances of this type /ignore ordering/.+-- For 'Functor', it is guaranteed that if @f@ is a monotonic function, then @'fmap' f@ on a valid+-- 'MaxQueue' will return a valid 'MaxQueue'.  An analogous guarantee holds for 'traverse'.  (Note:+-- if passed constant-time operations, every function in 'Functor', 'Foldable', and 'Traversable'+-- will run in /O(n)/.)+-- +-- If you wish to perform folds on a priority queue that respect order, use 'foldrDesc' or+-- 'foldlDesc'.+newtype MaxQueue a = MaxQ (Min.MinQueue (Down a))+# if __GLASGOW_HASKELL__+	deriving (Eq, Ord, Data, Typeable)+# else+	deriving (Eq, Ord)+# endif -size :: MaxQueue a -> Int-size (MaxQ q) = Q.size q+instance (Ord a, Show a) => Show (MaxQueue a) where+	showsPrec p xs = showParen (p > 10) $+		showString "fromDescList " . shows (toDescList xs)+		+instance Read a => Read (MaxQueue a) where+#ifdef __GLASGOW_HASKELL__+	readPrec = parens $ prec 10 $ do+		Ident "fromDescList" <- lexP+		xs <- readPrec+		return (fromDescList xs) -empty :: MaxQueue a-empty = MaxQ Q.empty+	readListPrec = readListPrecDefault+#else+	readsPrec p = readParen (p > 10) $ \ r -> do+		("fromDescList",s) <- lex r+		(xs,t) <- reads s+		return (fromDescList xs,t)+#endif -singleton :: a -> MaxQueue a-singleton a = MaxQ (Q.singleton a ())+instance Ord a => Monoid (MaxQueue a) where+	mempty = empty+	mappend = union -insert :: Ord a => a -> MaxQueue a -> MaxQueue a-insert a (MaxQ q) = MaxQ (Q.insert a () q)+-- | /O(1)/.  The empty priority queue.+empty :: MaxQueue a+empty = MaxQ Min.empty -union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a-MaxQ q1 `union` MaxQ q2 = MaxQ (q1 `Q.union` q2)+-- | /O(1)/.  Is this the empty priority queue?+null :: MaxQueue a -> Bool+null (MaxQ q) = Min.null q -unions :: Ord a => [MaxQueue a] -> MaxQueue a-unions qs = MaxQ (Q.unions [q | MaxQ q <- qs])+-- | /O(1)/.  The number of elements in the queue.+size :: MaxQueue a -> Int+size (MaxQ q) = Min.size q +-- | /O(1)/.  Returns the maximum element of the queue.  Throws an error on an empty queue. findMax :: MaxQueue a -> a-findMax = fromMaybe (error "Error: findMax called on an empty queue") . getMax+findMax = fromMaybe (error "Error: findMax called on empty queue") . getMax +-- | /O(1)/.  The top (maximum) element of the queue, if there is one. getMax :: MaxQueue a -> Maybe a-getMax (MaxQ q) = fst <$> Q.getMax q+getMax (MaxQ q) = unDown <$> Min.getMin q +-- | /O(log n)/.  Deletes the maximum element of the queue.  Does nothing on an empty queue. deleteMax :: Ord a => MaxQueue a -> MaxQueue a-deleteMax (MaxQ q) = MaxQ (Q.deleteMax q)+deleteMax (MaxQ q) = MaxQ (Min.deleteMin q) +-- | /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)-deleteFindMax = fromMaybe (error "Error: deleteFindMax called on an empty queue") . maxView+deleteFindMax = fromMaybe (error "Error: deleteFindMax called on empty queue") . maxView +-- | /O(log n)/.  Extract the top (maximum) element of the sequence, if there is one. maxView :: Ord a => MaxQueue a -> Maybe (a, MaxQueue a)-maxView (MaxQ q) = do-	((a, _), q') <- Q.maxViewWithKey q-	return (a, MaxQ q')--map :: Ord b => (a -> b) -> MaxQueue a -> MaxQueue b-map f (MaxQ q) = MaxQ (Q.mapKeys f q)--mapMonotonic :: (a -> b) -> MaxQueue a -> MaxQueue b-mapMonotonic f (MaxQ q) = MaxQ (Q.mapKeysMonotonic f q)+maxView (MaxQ q) = case Min.minView q of+	Nothing	-> Nothing+	Just (Down x, q')+		-> Just (x, MaxQ q')+		+-- | /O(log n)/.  Delete the top (maximum) element of the sequence, if there is one.+delete :: Ord a => MaxQueue a -> Maybe (MaxQueue a)+delete = fmap snd . maxView -traverse :: (Applicative f, Ord a, Ord b) => (a -> f b) -> MaxQueue a -> f (MaxQueue b)-traverse f q = case maxView q of-	Nothing		-> pure empty-	Just (a, q')	-> insert <$> f a <*> traverse f q'+-- | /O(1)/.  Construct a priority queue with a single element.+singleton :: a -> MaxQueue a+singleton = MaxQ . Min.singleton . Down -foldr :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b-foldr f z (MaxQ q) = Q.foldrWithKey (const . f) z q+-- | /O(1)/.  Insert an element into the priority queue.  +insert :: Ord a => a -> MaxQueue a -> MaxQueue a+x `insert` MaxQ q = MaxQ (Down x `Min.insert` q) -foldl :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b-foldl f z (MaxQ q) = Q.foldlWithKey (\ z -> const . f z) z q+-- | /O(log (min(n1,n2)))/.  Take the union of two priority queues.+union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a+MaxQ q1 `union` MaxQ q2 = MaxQ (q1 `Min.union` q2) -foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b-foldrU f z (MaxQ q) = Q.foldrWithKeyU (const . f) z q+-- | Takes the union of a list of priority queues.  Equivalent to @'foldl' 'union' 'empty'@.+unions :: Ord a => [MaxQueue a] -> MaxQueue a+unions qs = MaxQ (Min.unions [q | MaxQ q <- qs]) -foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b-foldlU f z (MaxQ q) = Q.foldlWithKeyU (\ z -> const . f z) z q+-- | /O(k log n)/.  Returns the @(k+1)@th largest element of the queue.+(!!) :: Ord a => MaxQueue a -> Int -> a+MaxQ q !! n = unDown ((Min.!!) q n) --- {-# INLINE take #-}+{-# INLINE take #-}+-- | /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]-take k (MaxQ q) = List.map fst (Q.take k q)+take k (MaxQ q) = [a | Down a <- Min.take k q] +-- | /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-drop k (MaxQ q) = MaxQ (Q.drop k q)+drop k (MaxQ q) = MaxQ (Min.drop k q) +-- | /O(k log n)/.  Equivalent to @(take k queue, drop k queue)@. splitAt :: Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)-splitAt k (MaxQ q) = case Q.splitAt k q of-	(xs, q') -> (List.map fst xs, MaxQ q')-+splitAt k (MaxQ q) = (map unDown xs, MaxQ q') where+	(xs, q') = Min.splitAt k q+	+-- | '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]-takeWhile p (MaxQ q) = List.map fst (Q.takeWhileWithKey (const . p) q)+takeWhile p (MaxQ q) = map unDown (Min.takeWhile (p . unDown) q) +-- | 'dropWhile' @p queue@ returns the queue remaining after 'takeWhile' @p queue@. dropWhile :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a-dropWhile p (MaxQ q) = MaxQ (Q.dropWhileWithKey (const . p) q)+dropWhile p (MaxQ q) = MaxQ (Min.dropWhile (p . unDown) q) +-- | '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)-span p (MaxQ q) = case Q.spanWithKey (const . p) q of-	(xs, q') -> (List.map fst xs, MaxQ q')+span p (MaxQ q) = (map unDown xs, MaxQ q') where+	(xs, q') = Min.span (p . unDown) q +-- | '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)-break p (MaxQ q) = case Q.breakWithKey (const . p) q of-	(xs, q') -> (List.map fst xs, MaxQ q')+break p = span (not . p) +-- | /O(n)/.  Returns a queue of those elements which satisfy the predicate. filter :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a-filter f (MaxQ q) = MaxQ (Q.filterWithKey (const . f) q)+filter p (MaxQ q) = MaxQ (Min.filter (p . unDown) q) +-- | /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)-partition p (MaxQ q) = case Q.partitionWithKey (const . p) q of-	(q0, q1) -> (MaxQ q0, MaxQ q1)+partition p (MaxQ q) = (MaxQ q0, MaxQ q1)+	where	(q0, q1) = Min.partition (p . unDown) q -{-# INLINE elems #-}-elems :: Ord a => MaxQueue a -> [a]-elems = toList+-- | /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+mapMaybe f (MaxQ q) = MaxQ (Min.mapMaybe (\ (Down x) -> Down <$> f x) q) -{-# INLINE toList #-}-toList :: Ord a => MaxQueue a -> [a]-toList (MaxQ q) = Q.keys q+-- | /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)+mapEither f (MaxQ q) = (MaxQ q0, MaxQ q1)+	where	(q0, q1) = Min.mapEither (either (Left . Down) (Right . Down) . f . unDown) q -{-# INLINE toDescList #-}-toDescList :: Ord a => MaxQueue a -> [a]-toDescList = toList+-- | /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+mapU f (MaxQ q) = MaxQ (Min.mapU (\ (Down a) -> Down (f a)) q) -{-# INLINE toAscList #-}-toAscList :: Ord a => MaxQueue a -> [a]-toAscList (MaxQ q) = List.map fst (Q.toAscList q)+-- | /O(n)/.  Unordered right fold on a priority queue.+foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b+foldrU f z (MaxQ q) = Min.foldrU (flip (foldr f)) z q +-- | /O(n)/.  Unordered left fold on a priority queue.+foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b+foldlU f z (MaxQ q) = Min.foldlU (foldl f) z q+ {-# INLINE elemsU #-}-elemsU :: Ord a => MaxQueue a -> [a]+-- | Equivalent to 'toListU'.+elemsU :: MaxQueue a -> [a] elemsU = toListU  {-# INLINE toListU #-}-toListU :: Ord a => MaxQueue a -> [a]-toListU (MaxQ q) = Q.keysU q+-- | /O(n)/.  Returns a list of the elements of the priority queue, in no particular order.+toListU :: MaxQueue a -> [a]+toListU (MaxQ q) = map unDown (Min.toListU q) -{-# INLINE fromList #-}-fromList :: Ord a => [a] -> MaxQueue a-fromList as = MaxQ (Q.fromList [(a, ()) | a <- as])+-- | /O(n)/.  Assumes that the function it is given is monotonic, in some sense, and performs the 'traverse' operation.+-- If the function is not monotonic, the result is undefined.+traverseU :: (Applicative f, Ord b) => (a -> f b) -> MaxQueue a -> f (MaxQueue b)+traverseU f (MaxQ q) = MaxQ <$> Min.traverseU (traverse f) q -{-# INLINE fromDescList #-}-fromDescList :: [a] -> MaxQueue a-fromDescList as = MaxQ (Q.fromDescList [(a, ()) | a <- as])+-- | /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+foldrAsc = foldlDesc . flip +-- | /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+foldlAsc = foldrDesc . flip++-- | /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+foldrDesc f z (MaxQ q) = Min.foldrAsc (flip (foldr f)) z q++-- | /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+foldlDesc f z (MaxQ q) = Min.foldlAsc (foldl f) z q++{-# INLINE toAscList #-}+-- | /O(n log n)/.  Extracts the elements of the priority queue in ascending order.+toAscList :: Ord a => MaxQueue a -> [a]+toAscList q = build (\ c nil -> foldrAsc c nil q)++{-# INLINE toDescList #-}+-- | /O(n log n)/.  Extracts the elements of the priority queue in descending order.+toDescList :: Ord a => MaxQueue a -> [a]+toDescList q = build (\ c nil -> foldrDesc c nil q)++{-# INLINE toList #-}+-- | /O(n)/.  Returns the elements of the priority queue in no particular order.+toList :: Ord a => MaxQueue a -> [a]+toList (MaxQ q) = map unDown (Min.toList q)+ {-# INLINE fromAscList #-}+-- | /O(n)/.  Constructs a priority queue from an ascending list.  /Warning/: Does not check the precondition.  fromAscList :: [a] -> MaxQueue a-fromAscList as = MaxQ (Q.fromAscList [(a, ()) | a <- as])+fromAscList = MaxQ . Min.fromDescList . map Down -pqueueKeys :: Q.MaxPQueue k a -> MaxQueue k-#ifdef __GLASGOW_HASKELL__-pqueueKeys q = MaxQ (() <$ q)-#else-pqueueKeys q = MaxQ (fmap (const ()) q)-#endif+{-# INLINE fromDescList #-}+-- | /O(n)/.  Constructs a priority queue from a descending list.  /Warning/: Does not check the precondition.+fromDescList :: [a] -> MaxQueue a+fromDescList = MaxQ . Min.fromAscList . map Down +{-# INLINE fromList #-}+-- | /O(n log n)/.  Constructs a priority queue from an unordered list.+fromList :: Ord a => [a] -> MaxQueue a+fromList = foldr insert empty++-- | /O(n)/.  Constructs a priority queue from the keys of a 'Prio.MaxPQueue'.+keysQueue :: Prio.MaxPQueue k a -> MaxQueue k+keysQueue (Prio.MaxPQ q) = MaxQ (Min.keysQueue q)++-- | /O(log n)/.  Forces the spine of the heap. seqSpine :: MaxQueue a -> b -> b-seqSpine (MaxQ q) = Q.seqSpine q+seqSpine (MaxQ q) = Min.seqSpine q
Data/PQueue/Min.hs view
@@ -16,13 +16,14 @@ -- 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.+-- The spine of the heap is maintained lazily.  To force the spine of the heap,+-- use 'seqSpine'. -- -- This implementation does not guarantee stable behavior. -- --- /WARNING:/ 'toList' and 'toAscList' are /not/ equivalent, unlike for example--- "Data.Map".+-- 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 ( 	MinQueue,@@ -59,11 +60,12 @@ 	mapEither, 	-- * Fold\/Functor\/Traversable variations 	map,-	mapMonotonic, 	foldrAsc, 	foldlAsc, 	foldrDesc, 	foldlDesc,+	traverseAsc,+	traverseDesc, 	-- * List operations 	toList, 	toAscList,@@ -72,6 +74,7 @@ 	fromAscList, 	fromDescList, 	-- * Unordered operations+	mapU, 	foldrU, 	foldlU, 	traverseU,@@ -130,14 +133,17 @@ 	mappend = union 	mconcat = unions +-- | /O(1)/.  Returns the minimum element.  Throws an error on an empty queue. findMin :: MinQueue a -> a findMin = fromMaybe (error "Error: findMin called on empty queue") . getMin +-- | /O(log n)/.  Deletes the minimum element.  If the queue is empty, does nothing. deleteMin :: Ord a => MinQueue a -> MinQueue a deleteMin q = case minView q of 	Nothing		-> empty 	Just (_, q')	-> q' +-- | /O(log n)/.  Extracts the minimum element.  Throws an error on an empty queue. deleteFindMin :: Ord a => MinQueue a -> (a, MinQueue a) deleteFindMin = fromMaybe (error "Error: deleteFindMin called on empty queue") . minView @@ -258,6 +264,14 @@ foldlDesc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b foldlDesc = foldrAsc . flip +-- | /O(n log n)/.  Equivalent to @'fromList' <$> 'traverse' f ('toAscList' q)@.+traverseAsc :: (Applicative f, Ord a, Ord b) => (a -> f b) -> MinQueue a -> f (MinQueue b)+traverseAsc f = foldrAsc (\ a q -> insert <$> f a <*> q) (pure empty)++-- | /O(n log n)/.  Equivalent to @'fromList' <$> 'traverse' f ('toDescList' q)@.+traverseDesc :: (Applicative f, Ord a, Ord b) => (a -> f b) -> MinQueue a -> f (MinQueue b)+traverseDesc f = foldrDesc (\ a q -> insert <$> f a <*> q) (pure empty)+ {-# INLINE fromList #-} -- | /O(n)/.  Constructs a priority queue from an unordered list. fromList :: Ord a => [a] -> MinQueue a@@ -277,13 +291,22 @@ fromDescList :: [a] -> MinQueue a fromDescList = foldl' (flip insertMinQ) empty +-- | 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+mapU = mapMonotonic+ {-# INLINE elemsU #-}+-- | Equivalent to 'toListU'. elemsU :: MinQueue a -> [a] elemsU = toListU +-- | Returns the elements of the queue, in no particular order. toListU :: MinQueue a -> [a] toListU q = build (\ c n -> foldrU c n q) +-- | /O(n)/.  Iterates over the elements of the queue in no particular order, but returns a valid queue that+-- respects the order of the returned elements. traverseU :: (Applicative f, Ord b) => (a -> f b) -> MinQueue a -> f (MinQueue b) traverseU f = foldrU (\ a q -> insert <$> f a <*> q) (pure empty)
Data/PQueue/Prio/Max.hs view
@@ -9,24 +9,25 @@ -- Stability   :  experimental -- Portability :  portable ----- General purpose priority queue, supporting extract-minimum operations.+-- 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.+-- viewing and extracting the element with the maximum 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.+-- 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.------ 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.+-- 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 are made on the execution or traversal order of+-- unordered.  No guarantees whatsoever are made on the execution or traversal order of -- these functions. ----------------------------------------------------------------------------- module Data.PQueue.Prio.Max (@@ -120,6 +121,7 @@ import Data.Foldable hiding (toList) import Data.Traversable import Data.Maybe hiding (mapMaybe)+import Data.PQueue.Prio.Max.Internals  import Prelude hiding (map, filter, break, span, takeWhile, dropWhile, splitAt, take, drop, (!!), null, foldr, foldl) @@ -141,18 +143,24 @@ second' :: (b -> c) -> (a, b) -> (a, c) second' f (a, b) = (a, f b) -newtype Down a = Down {unDown :: a} deriving (Eq)---- | A priority queue where values of type @a@ are annotated with keys of type @k@.--- The queue supports extracting the element with maximum key.-newtype MaxPQueue k a = MaxPQ (Q.MinPQueue (Down k) a) deriving (Eq, Ord)+instance (Ord k, Show k, Show a) => Show (MaxPQueue k a) where+	showsPrec p xs = showParen (p > 10) $+		showString "fromDescList " . shows (toDescList xs) -instance Ord a => Ord (Down a) where-	Down a `compare` Down b = b `compare` a-	Down a <= Down b = b <= a+instance (Read k, Read a) => Read (MaxPQueue k a) where+#ifdef __GLASGOW_HASKELL__+	readPrec = parens $ prec 10 $ do+		Ident "fromDescList" <- lexP+		xs <- readPrec+		return (fromDescList xs) -instance Functor Down where-	fmap f (Down a) = Down (f a)+	readListPrec = readListPrecDefault+#else+	readsPrec p = readParen (p > 10) $ \ r -> do+		("fromDescList",s) <- lex r+		(xs,t) <- reads s+		return (fromDescList xs,t)+#endif  instance Functor (MaxPQueue k) where 	fmap f (MaxPQ q) = MaxPQ (fmap f q)
+ Data/PQueue/Prio/Max/Internals.hs view
@@ -0,0 +1,41 @@+{-# LANGUAGE CPP #-}++module Data.PQueue.Prio.Max.Internals where++import Control.Applicative++import Data.Foldable+import Data.Traversable+# if __GLASGOW_HASKELL__+import Data.Data+# endif++import Prelude hiding (foldr, foldl)++import Data.PQueue.Prio.Internals (MinPQueue)++newtype Down a = Down {unDown :: a} +# if __GLASGOW_HASKELL__+	deriving (Eq, Data, Typeable)+# else+	deriving (Eq)+# endif++-- | A priority queue where values of type @a@ are annotated with keys of type @k@.+-- The queue supports extracting the element with maximum key.+newtype MaxPQueue k a = MaxPQ (MinPQueue (Down k) a) deriving (Eq, Ord)++instance Ord a => Ord (Down a) where+	Down a `compare` Down b = b `compare` a+	Down a <= Down b = b <= a++instance Functor Down where+	fmap f (Down a) = Down (f a)+++instance Foldable Down where+	foldr f z (Down a) = a `f` z+	foldl f z (Down a) = z `f` a++instance Traversable Down where+	traverse f (Down a) = Down <$> f a
Data/PQueue/Prio/Min.hs view
@@ -17,10 +17,13 @@ -- 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.+-- 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+-- 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
pqueue.cabal view
@@ -1,5 +1,5 @@ Name:		pqueue-Version:	1.0.0+Version:	1.0.1 Category:	Data Structures Author:		Louis Wasserman License:	BSD3@@ -26,6 +26,7 @@   other-modules:         Data.PQueue.Prio.Internals         Data.PQueue.Internals+        Data.PQueue.Prio.Max.Internals    if impl(ghc) {     extensions: DeriveDataTypeable