{-# LANGUAGE CPP #-}
module Data.PQueue.Max (
MaxQueue,
empty,
null,
size,
findMax,
getMax,
deleteMax,
deleteFindMax,
delete,
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,
foldlU',
foldMapU,
elemsU,
toListU,
keysQueue,
seqSpine) where
import Control.DeepSeq (NFData(rnf))
import Data.Maybe (fromMaybe)
#if MIN_VERSION_base(4,9,0)
import Data.Semigroup (Semigroup(..), stimesMonoid)
#endif
import Data.Foldable (foldl')
import qualified Data.PQueue.Min as Min
import qualified Data.PQueue.Prio.Max.Internals as Prio
import Data.PQueue.Internals.Down (Down(..))
import Prelude hiding (null, map, 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 (MaxQueue a -> MaxQueue a -> Bool
forall a. Ord a => MaxQueue a -> MaxQueue a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: MaxQueue a -> MaxQueue a -> Bool
$c/= :: forall a. Ord a => MaxQueue a -> MaxQueue a -> Bool
== :: MaxQueue a -> MaxQueue a -> Bool
$c== :: forall a. Ord a => MaxQueue a -> MaxQueue a -> Bool
Eq, MaxQueue a -> MaxQueue a -> Bool
MaxQueue a -> MaxQueue a -> Ordering
MaxQueue a -> MaxQueue a -> MaxQueue a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (MaxQueue a)
forall a. Ord a => MaxQueue a -> MaxQueue a -> Bool
forall a. Ord a => MaxQueue a -> MaxQueue a -> Ordering
forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
min :: MaxQueue a -> MaxQueue a -> MaxQueue a
$cmin :: forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
max :: MaxQueue a -> MaxQueue a -> MaxQueue a
$cmax :: forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
>= :: MaxQueue a -> MaxQueue a -> Bool
$c>= :: forall a. Ord a => MaxQueue a -> MaxQueue a -> Bool
> :: MaxQueue a -> MaxQueue a -> Bool
$c> :: forall a. Ord a => MaxQueue a -> MaxQueue a -> Bool
<= :: MaxQueue a -> MaxQueue a -> Bool
$c<= :: forall a. Ord a => MaxQueue a -> MaxQueue a -> Bool
< :: MaxQueue a -> MaxQueue a -> Bool
$c< :: forall a. Ord a => MaxQueue a -> MaxQueue a -> Bool
compare :: MaxQueue a -> MaxQueue a -> Ordering
$ccompare :: forall a. Ord a => MaxQueue a -> MaxQueue a -> Ordering
Ord, MaxQueue a -> DataType
MaxQueue a -> Constr
forall {a}. (Data a, Ord a) => Typeable (MaxQueue a)
forall a. (Data a, Ord a) => MaxQueue a -> DataType
forall a. (Data a, Ord a) => MaxQueue a -> Constr
forall a.
(Data a, Ord a) =>
(forall b. Data b => b -> b) -> MaxQueue a -> MaxQueue a
forall a u.
(Data a, Ord a) =>
Int -> (forall d. Data d => d -> u) -> MaxQueue a -> u
forall a u.
(Data a, Ord a) =>
(forall d. Data d => d -> u) -> MaxQueue a -> [u]
forall a r r'.
(Data a, Ord a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> MaxQueue a -> r
forall a r r'.
(Data a, Ord a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> MaxQueue a -> r
forall a (m :: * -> *).
(Data a, Ord a, Monad m) =>
(forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
forall a (m :: * -> *).
(Data a, Ord a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
forall a (c :: * -> *).
(Data a, Ord a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MaxQueue a)
forall a (c :: * -> *).
(Data a, Ord a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxQueue a -> c (MaxQueue a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (MaxQueue a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (MaxQueue a))
forall a.
Typeable a
-> (forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MaxQueue a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxQueue a -> c (MaxQueue a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (MaxQueue a))
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, Ord a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, Ord a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Ord a, Monad m) =>
(forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> MaxQueue a -> u
$cgmapQi :: forall a u.
(Data a, Ord a) =>
Int -> (forall d. Data d => d -> u) -> MaxQueue a -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> MaxQueue a -> [u]
$cgmapQ :: forall a u.
(Data a, Ord a) =>
(forall d. Data d => d -> u) -> MaxQueue a -> [u]
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> MaxQueue a -> r
$cgmapQr :: forall a r r'.
(Data a, Ord a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> MaxQueue a -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> MaxQueue a -> r
$cgmapQl :: forall a r r'.
(Data a, Ord a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> MaxQueue a -> r
gmapT :: (forall b. Data b => b -> b) -> MaxQueue a -> MaxQueue a
$cgmapT :: forall a.
(Data a, Ord a) =>
(forall b. Data b => b -> b) -> MaxQueue a -> MaxQueue a
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (MaxQueue a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (MaxQueue a))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (MaxQueue a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (MaxQueue a))
dataTypeOf :: MaxQueue a -> DataType
$cdataTypeOf :: forall a. (Data a, Ord a) => MaxQueue a -> DataType
toConstr :: MaxQueue a -> Constr
$ctoConstr :: forall a. (Data a, Ord a) => MaxQueue a -> Constr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MaxQueue a)
$cgunfold :: forall a (c :: * -> *).
(Data a, Ord a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MaxQueue a)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxQueue a -> c (MaxQueue a)
$cgfoldl :: forall a (c :: * -> *).
(Data a, Ord a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxQueue a -> c (MaxQueue a)
Data)
# else
deriving (Eq, Ord)
# endif
instance NFData a => NFData (MaxQueue a) where
rnf :: MaxQueue a -> ()
rnf (MaxQ MinQueue (Down a)
q) = forall a. NFData a => a -> ()
rnf MinQueue (Down a)
q
instance (Ord a, Show a) => Show (MaxQueue a) where
showsPrec :: Int -> MaxQueue a -> ShowS
showsPrec Int
p MaxQueue a
xs = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10) forall a b. (a -> b) -> a -> b
$
String -> ShowS
showString String
"fromDescList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => a -> ShowS
shows (forall a. Ord a => MaxQueue a -> [a]
toDescList MaxQueue a
xs)
instance Read a => Read (MaxQueue a) where
#ifdef __GLASGOW_HASKELL__
readPrec :: ReadPrec (MaxQueue a)
readPrec = forall a. ReadPrec a -> ReadPrec a
parens forall a b. (a -> b) -> a -> b
$ forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 forall a b. (a -> b) -> a -> b
$ do
Ident String
"fromDescList" <- ReadPrec Lexeme
lexP
[a]
xs <- forall a. Read a => ReadPrec a
readPrec
forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. [a] -> MaxQueue a
fromDescList [a]
xs)
readListPrec :: ReadPrec [MaxQueue a]
readListPrec = forall a. Read a => ReadPrec [a]
readListPrecDefault
#else
readsPrec p = readParen (p > 10) $ \r -> do
("fromDescList",s) <- lex r
(xs,t) <- reads s
return (fromDescList xs,t)
#endif
#if MIN_VERSION_base(4,9,0)
instance Ord a => Semigroup (MaxQueue a) where
<> :: MaxQueue a -> MaxQueue a -> MaxQueue a
(<>) = forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
union
stimes :: forall b. Integral b => b -> MaxQueue a -> MaxQueue a
stimes = forall b a. (Integral b, Monoid a) => b -> a -> a
stimesMonoid
{-# INLINABLE stimes #-}
#endif
instance Ord a => Monoid (MaxQueue a) where
mempty :: MaxQueue a
mempty = forall a. MaxQueue a
empty
#if !MIN_VERSION_base(4,11,0)
mappend = union
#endif
mconcat :: [MaxQueue a] -> MaxQueue a
mconcat = forall a. Ord a => [MaxQueue a] -> MaxQueue a
unions
empty :: MaxQueue a
empty :: forall a. MaxQueue a
empty = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ forall a. MinQueue a
Min.empty
null :: MaxQueue a -> Bool
null :: forall a. MaxQueue a -> Bool
null (MaxQ MinQueue (Down a)
q) = forall a. MinQueue a -> Bool
Min.null MinQueue (Down a)
q
size :: MaxQueue a -> Int
size :: forall a. MaxQueue a -> Int
size (MaxQ MinQueue (Down a)
q) = forall a. MinQueue a -> Int
Min.size MinQueue (Down a)
q
findMax :: MaxQueue a -> a
findMax :: forall a. MaxQueue a -> a
findMax = forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => String -> a
error String
"Error: findMax called on empty queue") forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. MaxQueue a -> Maybe a
getMax
getMax :: MaxQueue a -> Maybe a
getMax :: forall a. MaxQueue a -> Maybe a
getMax (MaxQ MinQueue (Down a)
q) = forall a. Down a -> a
unDown forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. MinQueue a -> Maybe a
Min.getMin MinQueue (Down a)
q
deleteMax :: Ord a => MaxQueue a -> MaxQueue a
deleteMax :: forall a. Ord a => MaxQueue a -> MaxQueue a
deleteMax (MaxQ MinQueue (Down a)
q) = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall a. Ord a => MinQueue a -> MinQueue a
Min.deleteMin MinQueue (Down a)
q)
deleteFindMax :: Ord a => MaxQueue a -> (a, MaxQueue a)
deleteFindMax :: forall a. Ord a => MaxQueue a -> (a, MaxQueue a)
deleteFindMax = forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => String -> a
error String
"Error: deleteFindMax called on empty queue") forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
maxView
maxView :: Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
maxView :: forall a. Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
maxView (MaxQ MinQueue (Down a)
q) = case forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
Min.minView MinQueue (Down a)
q of
Maybe (Down a, MinQueue (Down a))
Nothing -> forall a. Maybe a
Nothing
Just (Down a
x, MinQueue (Down a)
q')
-> forall a. a -> Maybe a
Just (a
x, forall a. MinQueue (Down a) -> MaxQueue a
MaxQ MinQueue (Down a)
q')
delete :: Ord a => MaxQueue a -> Maybe (MaxQueue a)
delete :: forall a. Ord a => MaxQueue a -> Maybe (MaxQueue a)
delete = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
maxView
singleton :: a -> MaxQueue a
singleton :: forall a. a -> MaxQueue a
singleton = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> MinQueue a
Min.singleton forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Down a
Down
insert :: Ord a => a -> MaxQueue a -> MaxQueue a
a
x insert :: forall a. Ord a => a -> MaxQueue a -> MaxQueue a
`insert` MaxQ MinQueue (Down a)
q = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall a. a -> Down a
Down a
x forall a. Ord a => a -> MinQueue a -> MinQueue a
`Min.insert` MinQueue (Down a)
q)
union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
MaxQ MinQueue (Down a)
q1 union :: forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
`union` MaxQ MinQueue (Down a)
q2 = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (MinQueue (Down a)
q1 forall a. Ord a => MinQueue a -> MinQueue a -> MinQueue a
`Min.union` MinQueue (Down a)
q2)
unions :: Ord a => [MaxQueue a] -> MaxQueue a
unions :: forall a. Ord a => [MaxQueue a] -> MaxQueue a
unions [MaxQueue a]
qs = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall a. Ord a => [MinQueue a] -> MinQueue a
Min.unions [MinQueue (Down a)
q | MaxQ MinQueue (Down a)
q <- [MaxQueue a]
qs])
(!!) :: Ord a => MaxQueue a -> Int -> a
MaxQ MinQueue (Down a)
q !! :: forall a. Ord a => MaxQueue a -> Int -> a
!! Int
n = forall a. Down a -> a
unDown (forall a. Ord a => MinQueue a -> Int -> a
(Min.!!) MinQueue (Down a)
q Int
n)
{-# INLINE take #-}
take :: Ord a => Int -> MaxQueue a -> [a]
take :: forall a. Ord a => Int -> MaxQueue a -> [a]
take Int
k (MaxQ MinQueue (Down a)
q) = [a
a | Down a
a <- forall a. Ord a => Int -> MinQueue a -> [a]
Min.take Int
k MinQueue (Down a)
q]
drop :: Ord a => Int -> MaxQueue a -> MaxQueue a
drop :: forall a. Ord a => Int -> MaxQueue a -> MaxQueue a
drop Int
k (MaxQ MinQueue (Down a)
q) = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall a. Ord a => Int -> MinQueue a -> MinQueue a
Min.drop Int
k MinQueue (Down a)
q)
splitAt :: Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)
splitAt :: forall a. Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)
splitAt Int
k (MaxQ MinQueue (Down a)
q) = (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Down a -> a
unDown [Down a]
xs, forall a. MinQueue (Down a) -> MaxQueue a
MaxQ MinQueue (Down a)
q') where
([Down a]
xs, MinQueue (Down a)
q') = forall a. Ord a => Int -> MinQueue a -> ([a], MinQueue a)
Min.splitAt Int
k MinQueue (Down a)
q
takeWhile :: Ord a => (a -> Bool) -> MaxQueue a -> [a]
takeWhile :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> [a]
takeWhile a -> Bool
p (MaxQ MinQueue (Down a)
q) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Down a -> a
unDown (forall a. Ord a => (a -> Bool) -> MinQueue a -> [a]
Min.takeWhile (a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinQueue (Down a)
q)
dropWhile :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
dropWhile :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
dropWhile a -> Bool
p (MaxQ MinQueue (Down a)
q) = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall a. Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
Min.dropWhile (a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinQueue (Down a)
q)
span :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
span :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
span a -> Bool
p (MaxQ MinQueue (Down a)
q) = (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Down a -> a
unDown [Down a]
xs, forall a. MinQueue (Down a) -> MaxQueue a
MaxQ MinQueue (Down a)
q') where
([Down a]
xs, MinQueue (Down a)
q') = forall a. Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
Min.span (a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinQueue (Down a)
q
break :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
break :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
break a -> Bool
p = forall a. Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
span (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)
filter :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
filter :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
filter a -> Bool
p (MaxQ MinQueue (Down a)
q) = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall a. Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
Min.filter (a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinQueue (Down a)
q)
partition :: Ord a => (a -> Bool) -> MaxQueue a -> (MaxQueue a, MaxQueue a)
partition :: forall a.
Ord a =>
(a -> Bool) -> MaxQueue a -> (MaxQueue a, MaxQueue a)
partition a -> Bool
p (MaxQ MinQueue (Down a)
q) = (forall a. MinQueue (Down a) -> MaxQueue a
MaxQ MinQueue (Down a)
q0, forall a. MinQueue (Down a) -> MaxQueue a
MaxQ MinQueue (Down a)
q1)
where (MinQueue (Down a)
q0, MinQueue (Down a)
q1) = forall a.
Ord a =>
(a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)
Min.partition (a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinQueue (Down a)
q
mapMaybe :: Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue b
mapMaybe :: forall b a. Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue b
mapMaybe a -> Maybe b
f (MaxQ MinQueue (Down a)
q) = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall b a. Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b
Min.mapMaybe (\(Down a
x) -> forall a. a -> Down a
Down forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Maybe b
f a
x) MinQueue (Down a)
q)
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MaxQueue a -> (MaxQueue b, MaxQueue c)
mapEither :: forall b c a.
(Ord b, Ord c) =>
(a -> Either b c) -> MaxQueue a -> (MaxQueue b, MaxQueue c)
mapEither a -> Either b c
f (MaxQ MinQueue (Down a)
q) = (forall a. MinQueue (Down a) -> MaxQueue a
MaxQ MinQueue (Down b)
q0, forall a. MinQueue (Down a) -> MaxQueue a
MaxQ MinQueue (Down c)
q1)
where (MinQueue (Down b)
q0, MinQueue (Down c)
q1) = forall b c a.
(Ord b, Ord c) =>
(a -> Either b c) -> MinQueue a -> (MinQueue b, MinQueue c)
Min.mapEither (forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (forall a b. a -> Either a b
Left forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Down a
Down) (forall a b. b -> Either a b
Right forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Down a
Down) forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Either b c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinQueue (Down a)
q
map :: Ord b => (a -> b) -> MaxQueue a -> MaxQueue b
map :: forall b a. Ord b => (a -> b) -> MaxQueue a -> MaxQueue b
map a -> b
f (MaxQ MinQueue (Down a)
q) = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall b a. Ord b => (a -> b) -> MinQueue a -> MinQueue b
Min.map (\(Down a
x) -> forall a. a -> Down a
Down (a -> b
f a
x)) MinQueue (Down a)
q)
mapU :: (a -> b) -> MaxQueue a -> MaxQueue b
mapU :: forall a b. (a -> b) -> MaxQueue a -> MaxQueue b
mapU a -> b
f (MaxQ MinQueue (Down a)
q) = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall a b. (a -> b) -> MinQueue a -> MinQueue b
Min.mapU (\(Down a
a) -> forall a. a -> Down a
Down (a -> b
f a
a)) MinQueue (Down a)
q)
foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b
foldrU :: forall a b. (a -> b -> b) -> b -> MaxQueue a -> b
foldrU a -> b -> b
f b
z (MaxQ MinQueue (Down a)
q) = forall a b. (a -> b -> b) -> b -> MinQueue a -> b
Min.foldrU (forall a b c. (a -> b -> c) -> b -> a -> c
flip (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f)) b
z MinQueue (Down a)
q
foldMapU :: Monoid m => (a -> m) -> MaxQueue a -> m
foldMapU :: forall m a. Monoid m => (a -> m) -> MaxQueue a -> m
foldMapU a -> m
f (MaxQ MinQueue (Down a)
q) = forall m a. Monoid m => (a -> m) -> MinQueue a -> m
Min.foldMapU (a -> m
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinQueue (Down a)
q
foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b
foldlU :: forall b a. (b -> a -> b) -> b -> MaxQueue a -> b
foldlU b -> a -> b
f b
z (MaxQ MinQueue (Down a)
q) = forall b a. (b -> a -> b) -> b -> MinQueue a -> b
Min.foldlU (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
f) b
z MinQueue (Down a)
q
foldlU' :: (b -> a -> b) -> b -> MaxQueue a -> b
foldlU' :: forall b a. (b -> a -> b) -> b -> MaxQueue a -> b
foldlU' b -> a -> b
f b
z (MaxQ MinQueue (Down a)
q) = forall b a. (b -> a -> b) -> b -> MinQueue a -> b
Min.foldlU' (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
f) b
z MinQueue (Down a)
q
{-# INLINE elemsU #-}
elemsU :: MaxQueue a -> [a]
elemsU :: forall a. MaxQueue a -> [a]
elemsU = forall a. MaxQueue a -> [a]
toListU
{-# INLINE toListU #-}
toListU :: MaxQueue a -> [a]
toListU :: forall a. MaxQueue a -> [a]
toListU (MaxQ MinQueue (Down a)
q) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Down a -> a
unDown (forall a. MinQueue a -> [a]
Min.toListU MinQueue (Down a)
q)
foldrAsc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
foldrAsc :: forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
foldrAsc = forall a b. Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
foldlDesc forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> b -> a -> c
flip
foldlAsc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
foldlAsc :: forall a b. Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
foldlAsc = forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
foldrDesc forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> b -> a -> c
flip
foldrDesc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
foldrDesc :: forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
foldrDesc a -> b -> b
f b
z (MaxQ MinQueue (Down a)
q) = forall a b. Ord a => (a -> b -> b) -> b -> MinQueue a -> b
Min.foldrAsc (forall a b c. (a -> b -> c) -> b -> a -> c
flip (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f)) b
z MinQueue (Down a)
q
foldlDesc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
foldlDesc :: forall a b. Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
foldlDesc b -> a -> b
f b
z (MaxQ MinQueue (Down a)
q) = forall a b. Ord a => (b -> a -> b) -> b -> MinQueue a -> b
Min.foldlAsc (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
f) b
z MinQueue (Down a)
q
{-# INLINE toAscList #-}
toAscList :: Ord a => MaxQueue a -> [a]
toAscList :: forall a. Ord a => MaxQueue a -> [a]
toAscList MaxQueue a
q = forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\a -> b -> b
c b
nil -> forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
foldrAsc a -> b -> b
c b
nil MaxQueue a
q)
{-# INLINE toDescList #-}
toDescList :: Ord a => MaxQueue a -> [a]
toDescList :: forall a. Ord a => MaxQueue a -> [a]
toDescList MaxQueue a
q = forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\a -> b -> b
c b
nil -> forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
foldrDesc a -> b -> b
c b
nil MaxQueue a
q)
{-# INLINE toList #-}
toList :: Ord a => MaxQueue a -> [a]
toList :: forall a. Ord a => MaxQueue a -> [a]
toList (MaxQ MinQueue (Down a)
q) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Down a -> a
unDown (forall a. Ord a => MinQueue a -> [a]
Min.toList MinQueue (Down a)
q)
{-# INLINE fromAscList #-}
fromAscList :: [a] -> MaxQueue a
fromAscList :: forall a. [a] -> MaxQueue a
fromAscList = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. [a] -> MinQueue a
Min.fromDescList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Down a
Down
{-# INLINE fromDescList #-}
fromDescList :: [a] -> MaxQueue a
fromDescList :: forall a. [a] -> MaxQueue a
fromDescList = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. [a] -> MinQueue a
Min.fromAscList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Down a
Down
{-# INLINE fromList #-}
fromList :: Ord a => [a] -> MaxQueue a
fromList :: forall a. Ord a => [a] -> MaxQueue a
fromList = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => [a] -> MinQueue a
Min.fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Down a
Down
keysQueue :: Prio.MaxPQueue k a -> MaxQueue k
keysQueue :: forall k a. MaxPQueue k a -> MaxQueue k
keysQueue (Prio.MaxPQ MinPQueue (Down k) a
q) = forall a. MinQueue (Down a) -> MaxQueue a
MaxQ (forall k a. MinPQueue k a -> MinQueue k
Min.keysQueue MinPQueue (Down k) a
q)
seqSpine :: MaxQueue a -> b -> b
seqSpine :: forall a b. MaxQueue a -> b -> b
seqSpine (MaxQ MinQueue (Down a)
q) = forall a b. MinQueue a -> b -> b
Min.seqSpine MinQueue (Down a)
q