module Data.PQueue.Max (
MaxQueue,
empty,
null,
size,
findMax,
getMax,
deleteMax,
deleteFindMax,
maxView,
singleton,
insert,
union,
unions,
(!!),
take,
drop,
splitAt,
takeWhile,
dropWhile,
span,
break,
filter,
partition,
mapMaybe,
mapEither,
map,
foldrAsc,
foldlAsc,
foldrDesc,
foldlDesc,
toList,
toAscList,
toDescList,
fromList,
fromAscList,
fromDescList,
mapU,
foldrU,
foldlU,
elemsU,
toListU,
keysQueue,
seqSpine) where
import Control.Applicative (Applicative(..), (<$>))
import Control.DeepSeq
import Data.Monoid
import Data.Maybe hiding (mapMaybe)
import Data.Foldable hiding (toList)
import Data.Traversable
import Data.Ord
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,
readPrec, readListPrec, readListPrecDefault)
import Data.Data
#else
build :: ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
build f = f (:) []
#endif
newtype MaxQueue a = MaxQ (Min.MinQueue (Down a))
# if __GLASGOW_HASKELL__
deriving (Eq, Ord, Data, Typeable)
# else
deriving (Eq, Ord)
# endif
instance NFData a => NFData (MaxQueue a) where
rnf (MaxQ q) = rnf 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)
readListPrec = readListPrecDefault
#else
readsPrec p = readParen (p > 10) $ \ r -> do
("fromDescList",s) <- lex r
(xs,t) <- reads s
return (fromDescList xs,t)
#endif
instance Ord a => Monoid (MaxQueue a) where
mempty = empty
mappend = union
empty :: MaxQueue a
empty = MaxQ Min.empty
null :: MaxQueue a -> Bool
null (MaxQ q) = Min.null q
size :: MaxQueue a -> Int
size (MaxQ q) = Min.size q
findMax :: MaxQueue a -> a
findMax = fromMaybe (error "Error: findMax called on empty queue") . getMax
getMax :: MaxQueue a -> Maybe a
getMax (MaxQ q) = unDown <$> Min.getMin q
deleteMax :: Ord a => MaxQueue a -> MaxQueue a
deleteMax (MaxQ q) = MaxQ (Min.deleteMin q)
deleteFindMax :: Ord a => MaxQueue a -> (a, MaxQueue a)
deleteFindMax = fromMaybe (error "Error: deleteFindMax called on empty queue") . maxView
maxView :: Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
maxView (MaxQ q) = case Min.minView q of
Nothing -> Nothing
Just (Down x, q')
-> Just (x, MaxQ q')
delete :: Ord a => MaxQueue a -> Maybe (MaxQueue a)
delete = fmap snd . maxView
singleton :: a -> MaxQueue a
singleton = MaxQ . Min.singleton . Down
insert :: Ord a => a -> MaxQueue a -> MaxQueue a
x `insert` MaxQ q = MaxQ (Down x `Min.insert` q)
union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
MaxQ q1 `union` MaxQ q2 = MaxQ (q1 `Min.union` q2)
unions :: Ord a => [MaxQueue a] -> MaxQueue a
unions qs = MaxQ (Min.unions [q | MaxQ q <- qs])
(!!) :: Ord a => MaxQueue a -> Int -> a
MaxQ q !! n = unDown ((Min.!!) q n)
take :: Ord a => Int -> MaxQueue a -> [a]
take k (MaxQ q) = [a | Down a <- Min.take k q]
drop :: Ord a => Int -> MaxQueue a -> MaxQueue a
drop k (MaxQ q) = MaxQ (Min.drop k q)
splitAt :: Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)
splitAt k (MaxQ q) = (map unDown xs, MaxQ q') where
(xs, q') = Min.splitAt k q
takeWhile :: Ord a => (a -> Bool) -> MaxQueue a -> [a]
takeWhile p (MaxQ q) = map unDown (Min.takeWhile (p . unDown) q)
dropWhile :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
dropWhile p (MaxQ q) = MaxQ (Min.dropWhile (p . unDown) q)
span :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
span p (MaxQ q) = (map unDown xs, MaxQ q') where
(xs, q') = Min.span (p . unDown) q
break :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
break p = span (not . p)
filter :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
filter p (MaxQ q) = MaxQ (Min.filter (p . unDown) q)
partition :: Ord a => (a -> Bool) -> MaxQueue a -> (MaxQueue a, MaxQueue a)
partition p (MaxQ q) = (MaxQ q0, MaxQ q1)
where (q0, q1) = Min.partition (p . unDown) q
mapMaybe :: Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue b
mapMaybe f (MaxQ q) = MaxQ (Min.mapMaybe (\ (Down x) -> Down <$> f x) q)
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
mapU :: (a -> b) -> MaxQueue a -> MaxQueue b
mapU f (MaxQ q) = MaxQ (Min.mapU (\ (Down a) -> Down (f a)) q)
foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b
foldrU f z (MaxQ q) = Min.foldrU (flip (foldr f)) z q
foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b
foldlU f z (MaxQ q) = Min.foldlU (foldl f) z q
elemsU :: MaxQueue a -> [a]
elemsU = toListU
toListU :: MaxQueue a -> [a]
toListU (MaxQ q) = map unDown (Min.toListU q)
foldrAsc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
foldrAsc = foldlDesc . flip
foldlAsc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
foldlAsc = foldrDesc . flip
foldrDesc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
foldrDesc f z (MaxQ q) = Min.foldrAsc (flip (foldr f)) z q
foldlDesc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
foldlDesc f z (MaxQ q) = Min.foldlAsc (foldl f) z q
toAscList :: Ord a => MaxQueue a -> [a]
toAscList q = build (\ c nil -> foldrAsc c nil q)
toDescList :: Ord a => MaxQueue a -> [a]
toDescList q = build (\ c nil -> foldrDesc c nil q)
toList :: Ord a => MaxQueue a -> [a]
toList (MaxQ q) = map unDown (Min.toList q)
fromAscList :: [a] -> MaxQueue a
fromAscList = MaxQ . Min.fromDescList . map Down
fromDescList :: [a] -> MaxQueue a
fromDescList = MaxQ . Min.fromAscList . map Down
fromList :: Ord a => [a] -> MaxQueue a
fromList = foldr insert empty
keysQueue :: Prio.MaxPQueue k a -> MaxQueue k
keysQueue (Prio.MaxPQ q) = MaxQ (Min.keysQueue q)
seqSpine :: MaxQueue a -> b -> b
seqSpine (MaxQ q) = Min.seqSpine q