{-# LANGUAGE CPP #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}
module Data.PQueue.Min (
MinQueue,
empty,
null,
size,
findMin,
getMin,
deleteMin,
deleteFindMin,
minView,
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 Prelude hiding (null, take, drop, takeWhile, dropWhile, splitAt, span, break, (!!), filter, map)
import Data.Foldable (foldl')
import Data.Maybe (fromMaybe)
#if MIN_VERSION_base(4,9,0)
import Data.Semigroup (Semigroup((<>)))
#endif
import qualified Data.List as List
import Data.PQueue.Internals
#ifdef __GLASGOW_HASKELL__
import GHC.Exts (build)
import Text.Read (Lexeme(Ident), lexP, parens, prec,
readPrec, readListPrec, readListPrecDefault)
#else
build :: ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
build f = f (:) []
#endif
instance (Ord a, Show a) => Show (MinQueue a) where
showsPrec :: Int -> MinQueue a -> ShowS
showsPrec Int
p MinQueue a
xs = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
String -> ShowS
showString String
"fromAscList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> ShowS
forall a. Show a => a -> ShowS
shows (MinQueue a -> [a]
forall a. Ord a => MinQueue a -> [a]
toAscList MinQueue a
xs)
instance Read a => Read (MinQueue a) where
#ifdef __GLASGOW_HASKELL__
readPrec :: ReadPrec (MinQueue a)
readPrec = ReadPrec (MinQueue a) -> ReadPrec (MinQueue a)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (MinQueue a) -> ReadPrec (MinQueue a))
-> ReadPrec (MinQueue a) -> ReadPrec (MinQueue a)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (MinQueue a) -> ReadPrec (MinQueue a)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (MinQueue a) -> ReadPrec (MinQueue a))
-> ReadPrec (MinQueue a) -> ReadPrec (MinQueue a)
forall a b. (a -> b) -> a -> b
$ do
Ident String
"fromAscList" <- ReadPrec Lexeme
lexP
[a]
xs <- ReadPrec [a]
forall a. Read a => ReadPrec a
readPrec
MinQueue a -> ReadPrec (MinQueue a)
forall (m :: * -> *) a. Monad m => a -> m a
return ([a] -> MinQueue a
forall a. [a] -> MinQueue a
fromAscList [a]
xs)
readListPrec :: ReadPrec [MinQueue a]
readListPrec = ReadPrec [MinQueue a]
forall a. Read a => ReadPrec [a]
readListPrecDefault
#else
readsPrec p = readParen (p > 10) $ \r -> do
("fromAscList",s) <- lex r
(xs,t) <- reads s
return (fromAscList xs,t)
#endif
#if MIN_VERSION_base(4,9,0)
instance Ord a => Semigroup (MinQueue a) where
<> :: MinQueue a -> MinQueue a -> MinQueue a
(<>) = MinQueue a -> MinQueue a -> MinQueue a
forall a. Ord a => MinQueue a -> MinQueue a -> MinQueue a
union
#endif
instance Ord a => Monoid (MinQueue a) where
mempty :: MinQueue a
mempty = MinQueue a
forall a. MinQueue a
empty
mappend :: MinQueue a -> MinQueue a -> MinQueue a
mappend = MinQueue a -> MinQueue a -> MinQueue a
forall a. Ord a => MinQueue a -> MinQueue a -> MinQueue a
union
mconcat :: [MinQueue a] -> MinQueue a
mconcat = [MinQueue a] -> MinQueue a
forall a. Ord a => [MinQueue a] -> MinQueue a
unions
findMin :: MinQueue a -> a
findMin :: MinQueue a -> a
findMin = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe (String -> a
forall a. HasCallStack => String -> a
error String
"Error: findMin called on empty queue") (Maybe a -> a) -> (MinQueue a -> Maybe a) -> MinQueue a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MinQueue a -> Maybe a
forall a. MinQueue a -> Maybe a
getMin
deleteMin :: Ord a => MinQueue a -> MinQueue a
deleteMin :: MinQueue a -> MinQueue a
deleteMin MinQueue a
q = case MinQueue a -> Maybe (a, MinQueue a)
forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView MinQueue a
q of
Maybe (a, MinQueue a)
Nothing -> MinQueue a
forall a. MinQueue a
empty
Just (a
_, MinQueue a
q') -> MinQueue a
q'
deleteFindMin :: Ord a => MinQueue a -> (a, MinQueue a)
deleteFindMin :: MinQueue a -> (a, MinQueue a)
deleteFindMin = (a, MinQueue a) -> Maybe (a, MinQueue a) -> (a, MinQueue a)
forall a. a -> Maybe a -> a
fromMaybe (String -> (a, MinQueue a)
forall a. HasCallStack => String -> a
error String
"Error: deleteFindMin called on empty queue") (Maybe (a, MinQueue a) -> (a, MinQueue a))
-> (MinQueue a -> Maybe (a, MinQueue a))
-> MinQueue a
-> (a, MinQueue a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MinQueue a -> Maybe (a, MinQueue a)
forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView
unions :: Ord a => [MinQueue a] -> MinQueue a
unions :: [MinQueue a] -> MinQueue a
unions = (MinQueue a -> MinQueue a -> MinQueue a)
-> MinQueue a -> [MinQueue a] -> MinQueue a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl MinQueue a -> MinQueue a -> MinQueue a
forall a. Ord a => MinQueue a -> MinQueue a -> MinQueue a
union MinQueue a
forall a. MinQueue a
empty
(!!) :: Ord a => MinQueue a -> Int -> a
MinQueue a
q !! :: MinQueue a -> Int -> a
!! Int
n | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= MinQueue a -> Int
forall a. MinQueue a -> Int
size MinQueue a
q
= String -> a
forall a. HasCallStack => String -> a
error String
"Data.PQueue.Min.!!: index too large"
MinQueue a
q !! Int
n = [a] -> Int -> a
forall a. [a] -> Int -> a
(List.!!) (MinQueue a -> [a]
forall a. Ord a => MinQueue a -> [a]
toAscList MinQueue a
q) Int
n
{-# INLINE takeWhile #-}
takeWhile :: Ord a => (a -> Bool) -> MinQueue a -> [a]
takeWhile :: (a -> Bool) -> MinQueue a -> [a]
takeWhile a -> Bool
p = (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
foldWhileFB a -> Bool
p ([a] -> [a]) -> (MinQueue a -> [a]) -> MinQueue a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MinQueue a -> [a]
forall a. Ord a => MinQueue a -> [a]
toAscList
{-# INLINE foldWhileFB #-}
foldWhileFB :: (a -> Bool) -> [a] -> [a]
foldWhileFB :: (a -> Bool) -> [a] -> [a]
foldWhileFB a -> Bool
p [a]
xs0 = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\a -> b -> b
c b
nil -> let
consWhile :: a -> b -> b
consWhile a
x b
xs
| a -> Bool
p a
x = a
x a -> b -> b
`c` b
xs
| Bool
otherwise = b
nil
in (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
consWhile b
nil [a]
xs0)
dropWhile :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
dropWhile :: (a -> Bool) -> MinQueue a -> MinQueue a
dropWhile a -> Bool
p = MinQueue a -> MinQueue a
drop' where
drop' :: MinQueue a -> MinQueue a
drop' MinQueue a
q = case MinQueue a -> Maybe (a, MinQueue a)
forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView MinQueue a
q of
Just (a
x, MinQueue a
q') | a -> Bool
p a
x -> MinQueue a -> MinQueue a
drop' MinQueue a
q'
Maybe (a, MinQueue a)
_ -> MinQueue a
q
span :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
span :: (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
span a -> Bool
p MinQueue a
queue = case MinQueue a -> Maybe (a, MinQueue a)
forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView MinQueue a
queue of
Just (a
x, MinQueue a
q')
| a -> Bool
p a
x -> let ([a]
ys, MinQueue a
q'') = (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
forall a. Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
span a -> Bool
p MinQueue a
q' in (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
ys, MinQueue a
q'')
Maybe (a, MinQueue a)
_ -> ([], MinQueue a
queue)
break :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
break :: (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
break a -> Bool
p = (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
forall a. Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
span (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)
{-# INLINE take #-}
take :: Ord a => Int -> MinQueue a -> [a]
take :: Int -> MinQueue a -> [a]
take Int
n = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
List.take Int
n ([a] -> [a]) -> (MinQueue a -> [a]) -> MinQueue a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MinQueue a -> [a]
forall a. Ord a => MinQueue a -> [a]
toAscList
drop :: Ord a => Int -> MinQueue a -> MinQueue a
drop :: Int -> MinQueue a -> MinQueue a
drop Int
n MinQueue a
queue = Int
n Int -> MinQueue a -> MinQueue a
`seq` case MinQueue a -> Maybe (a, MinQueue a)
forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView MinQueue a
queue of
Just (a
_, MinQueue a
queue')
| Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 -> Int -> MinQueue a -> MinQueue a
forall a. Ord a => Int -> MinQueue a -> MinQueue a
drop (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) MinQueue a
queue'
Maybe (a, MinQueue a)
_ -> MinQueue a
queue
splitAt :: Ord a => Int -> MinQueue a -> ([a], MinQueue a)
splitAt :: Int -> MinQueue a -> ([a], MinQueue a)
splitAt Int
n MinQueue a
queue = Int
n Int -> ([a], MinQueue a) -> ([a], MinQueue a)
`seq` case MinQueue a -> Maybe (a, MinQueue a)
forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView MinQueue a
queue of
Just (a
x, MinQueue a
queue')
| Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 -> let ([a]
xs, MinQueue a
queue'') = Int -> MinQueue a -> ([a], MinQueue a)
forall a. Ord a => Int -> MinQueue a -> ([a], MinQueue a)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) MinQueue a
queue' in (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs, MinQueue a
queue'')
Maybe (a, MinQueue a)
_ -> ([], MinQueue a
queue)
filter :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
filter :: (a -> Bool) -> MinQueue a -> MinQueue a
filter a -> Bool
p = (a -> Maybe a) -> MinQueue a -> MinQueue a
forall b a. Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b
mapMaybe (\a
x -> if a -> Bool
p a
x then a -> Maybe a
forall a. a -> Maybe a
Just a
x else Maybe a
forall a. Maybe a
Nothing)
partition :: Ord a => (a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)
partition :: (a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)
partition a -> Bool
p = (a -> Either a a) -> MinQueue a -> (MinQueue a, MinQueue a)
forall b c a.
(Ord b, Ord c) =>
(a -> Either b c) -> MinQueue a -> (MinQueue b, MinQueue c)
mapEither (\a
x -> if a -> Bool
p a
x then a -> Either a a
forall a b. a -> Either a b
Left a
x else a -> Either a a
forall a b. b -> Either a b
Right a
x)
map :: Ord b => (a -> b) -> MinQueue a -> MinQueue b
map :: (a -> b) -> MinQueue a -> MinQueue b
map a -> b
f = (a -> MinQueue b -> MinQueue b)
-> MinQueue b -> MinQueue a -> MinQueue b
forall a b. (a -> b -> b) -> b -> MinQueue a -> b
foldrU (b -> MinQueue b -> MinQueue b
forall a. Ord a => a -> MinQueue a -> MinQueue a
insert (b -> MinQueue b -> MinQueue b)
-> (a -> b) -> a -> MinQueue b -> MinQueue b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f) MinQueue b
forall a. MinQueue a
empty
{-# INLINE toAscList #-}
toAscList :: Ord a => MinQueue a -> [a]
toAscList :: MinQueue a -> [a]
toAscList MinQueue a
queue = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\a -> b -> b
c b
nil -> (a -> b -> b) -> b -> MinQueue a -> b
forall a b. Ord a => (a -> b -> b) -> b -> MinQueue a -> b
foldrAsc a -> b -> b
c b
nil MinQueue a
queue)
{-# INLINE toDescList #-}
toDescList :: Ord a => MinQueue a -> [a]
toDescList :: MinQueue a -> [a]
toDescList MinQueue a
queue = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\a -> b -> b
c b
nil -> (a -> b -> b) -> b -> MinQueue a -> b
forall a b. Ord a => (a -> b -> b) -> b -> MinQueue a -> b
foldrDesc a -> b -> b
c b
nil MinQueue a
queue)
{-# INLINE toList #-}
toList :: Ord a => MinQueue a -> [a]
toList :: MinQueue a -> [a]
toList = MinQueue a -> [a]
forall a. Ord a => MinQueue a -> [a]
toAscList
{-# RULES
"toAscList" forall q . toAscList q = build (\c nil -> foldrAsc c nil q);
-- inlining doesn't seem to be working out =/
"toDescList" forall q . toDescList q = build (\c nil -> foldrDesc c nil q);
#-}
foldrDesc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b
foldrDesc :: (a -> b -> b) -> b -> MinQueue a -> b
foldrDesc = (b -> a -> b) -> b -> MinQueue a -> b
forall a b. Ord a => (b -> a -> b) -> b -> MinQueue a -> b
foldlAsc ((b -> a -> b) -> b -> MinQueue a -> b)
-> ((a -> b -> b) -> b -> a -> b)
-> (a -> b -> b)
-> b
-> MinQueue a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> b -> a -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip
foldlDesc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b
foldlDesc :: (b -> a -> b) -> b -> MinQueue a -> b
foldlDesc = (a -> b -> b) -> b -> MinQueue a -> b
forall a b. Ord a => (a -> b -> b) -> b -> MinQueue a -> b
foldrAsc ((a -> b -> b) -> b -> MinQueue a -> b)
-> ((b -> a -> b) -> a -> b -> b)
-> (b -> a -> b)
-> b
-> MinQueue a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> a -> b) -> a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip
{-# INLINE fromList #-}
fromList :: Ord a => [a] -> MinQueue a
fromList :: [a] -> MinQueue a
fromList = (a -> MinQueue a -> MinQueue a) -> MinQueue a -> [a] -> MinQueue a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> MinQueue a -> MinQueue a
forall a. Ord a => a -> MinQueue a -> MinQueue a
insert MinQueue a
forall a. MinQueue a
empty
{-# RULES
"fromList" fromList = foldr insert empty;
"fromAscList" fromAscList = foldr insertMinQ empty;
#-}
{-# INLINE fromAscList #-}
fromAscList :: [a] -> MinQueue a
fromAscList :: [a] -> MinQueue a
fromAscList = (a -> MinQueue a -> MinQueue a) -> MinQueue a -> [a] -> MinQueue a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> MinQueue a -> MinQueue a
forall a. a -> MinQueue a -> MinQueue a
insertMinQ MinQueue a
forall a. MinQueue a
empty
fromDescList :: [a] -> MinQueue a
fromDescList :: [a] -> MinQueue a
fromDescList = (MinQueue a -> a -> MinQueue a) -> MinQueue a -> [a] -> MinQueue a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> MinQueue a -> MinQueue a) -> MinQueue a -> a -> MinQueue a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> MinQueue a -> MinQueue a
forall a. a -> MinQueue a -> MinQueue a
insertMinQ) MinQueue a
forall a. MinQueue a
empty
mapU :: (a -> b) -> MinQueue a -> MinQueue b
mapU :: (a -> b) -> MinQueue a -> MinQueue b
mapU = (a -> b) -> MinQueue a -> MinQueue b
forall a b. (a -> b) -> MinQueue a -> MinQueue b
mapMonotonic
{-# INLINE elemsU #-}
elemsU :: MinQueue a -> [a]
elemsU :: MinQueue a -> [a]
elemsU = MinQueue a -> [a]
forall a. MinQueue a -> [a]
toListU
toListU :: MinQueue a -> [a]
toListU :: MinQueue a -> [a]
toListU MinQueue a
q = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\a -> b -> b
c b
n -> (a -> b -> b) -> b -> MinQueue a -> b
forall a b. (a -> b -> b) -> b -> MinQueue a -> b
foldrU a -> b -> b
c b
n MinQueue a
q)
{-# RULES
"foldr/toListU" forall f z q . foldr f z (toListU q) = foldrU f z q;
"foldl/toListU" forall f z q . foldl f z (toListU q) = foldlU f z q;
#-}