{-# LANGUAGE CPP #-}
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,
foldlU',
foldMapU,
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
import qualified BinomialQueue.Internals as BQ
import qualified Data.PQueue.Prio.Internals as Prio
#ifdef __GLASGOW_HASKELL__
import GHC.Exts (build)
#else
build :: ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
build f = f (:) []
#endif
findMin :: MinQueue a -> a
findMin :: forall a. MinQueue a -> a
findMin = forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => [Char] -> a
error [Char]
"Error: findMin called on empty queue") forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. MinQueue a -> Maybe a
getMin
deleteMin :: Ord a => MinQueue a -> MinQueue a
deleteMin :: forall a. Ord a => MinQueue a -> MinQueue a
deleteMin MinQueue a
q = case forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView MinQueue a
q of
Maybe (a, MinQueue a)
Nothing -> forall a. MinQueue a
empty
Just (a
_, MinQueue a
q') -> MinQueue a
q'
deleteFindMin :: Ord a => MinQueue a -> (a, MinQueue a)
deleteFindMin :: forall a. Ord a => MinQueue a -> (a, MinQueue a)
deleteFindMin = forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => [Char] -> a
error [Char]
"Error: deleteFindMin called on empty queue") forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView
(!!) :: Ord a => MinQueue a -> Int -> a
MinQueue a
q !! :: forall a. Ord a => MinQueue a -> Int -> a
!! Int
n | Int
n forall a. Ord a => a -> a -> Bool
>= forall a. MinQueue a -> Int
size MinQueue a
q
= forall a. HasCallStack => [Char] -> a
error [Char]
"Data.PQueue.Min.!!: index too large"
MinQueue a
q !! Int
n = forall a. [a] -> Int -> a
(List.!!) (forall a. Ord a => MinQueue a -> [a]
toAscList MinQueue a
q) Int
n
{-# INLINE takeWhile #-}
takeWhile :: Ord a => (a -> Bool) -> MinQueue a -> [a]
takeWhile :: forall a. Ord a => (a -> Bool) -> MinQueue a -> [a]
takeWhile a -> Bool
p = forall a. (a -> Bool) -> [a] -> [a]
foldWhileFB a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => MinQueue a -> [a]
toAscList
{-# INLINE foldWhileFB #-}
foldWhileFB :: (a -> Bool) -> [a] -> [a]
foldWhileFB :: forall a. (a -> Bool) -> [a] -> [a]
foldWhileFB a -> Bool
p [a]
xs0 = 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 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 :: forall a. Ord a => (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 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 :: forall a. Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
span a -> Bool
p MinQueue a
queue = case 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'') = forall a. Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
span a -> Bool
p MinQueue a
q' in (a
x 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 :: forall a. Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
break a -> Bool
p = forall a. Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
span (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)
{-# INLINE take #-}
take :: Ord a => Int -> MinQueue a -> [a]
take :: forall a. Ord a => Int -> MinQueue a -> [a]
take Int
n = forall a. Int -> [a] -> [a]
List.take Int
n forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => MinQueue a -> [a]
toAscList
drop :: Ord a => Int -> MinQueue a -> MinQueue a
drop :: forall a. Ord a => Int -> MinQueue a -> MinQueue a
drop Int
n MinQueue a
queue = Int
n seq :: forall a b. a -> b -> b
`seq` case forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView MinQueue a
queue of
Just (a
_, MinQueue a
queue')
| Int
n forall a. Ord a => a -> a -> Bool
> Int
0 -> forall a. Ord a => Int -> MinQueue a -> MinQueue a
drop (Int
n 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 :: forall a. Ord a => Int -> MinQueue a -> ([a], MinQueue a)
splitAt Int
n MinQueue a
queue = Int
n seq :: forall a b. a -> b -> b
`seq` case forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
minView MinQueue a
queue of
Just (a
x, MinQueue a
queue')
| Int
n forall a. Ord a => a -> a -> Bool
> Int
0 -> let ([a]
xs, MinQueue a
queue'') = forall a. Ord a => Int -> MinQueue a -> ([a], MinQueue a)
splitAt (Int
n forall a. Num a => a -> a -> a
- Int
1) MinQueue a
queue' in (a
x 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 :: forall a. Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
filter a -> Bool
p = forall b a. Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b
mapMaybe (\a
x -> if a -> Bool
p a
x then forall a. a -> Maybe a
Just a
x else forall a. Maybe a
Nothing)
partition :: Ord a => (a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)
partition :: forall a.
Ord a =>
(a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)
partition a -> Bool
p = 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 forall a b. a -> Either a b
Left a
x else forall a b. b -> Either a b
Right a
x)
map :: Ord b => (a -> b) -> MinQueue a -> MinQueue b
map :: forall b a. Ord b => (a -> b) -> MinQueue a -> MinQueue b
map a -> b
f = forall a b. (a -> b -> b) -> b -> MinQueue a -> b
foldrU (forall a. Ord a => a -> MinQueue a -> MinQueue a
insert forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f) forall a. MinQueue a
empty
{-# INLINE toList #-}
toList :: Ord a => MinQueue a -> [a]
toList :: forall a. Ord a => MinQueue a -> [a]
toList = forall a. Ord a => MinQueue a -> [a]
toAscList
foldlDesc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b
foldlDesc :: forall a b. Ord a => (b -> a -> b) -> b -> MinQueue a -> b
foldlDesc = forall a b. Ord a => (a -> b -> b) -> b -> MinQueue a -> b
foldrAsc forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> b -> a -> c
flip
{-# INLINE fromDescList #-}
fromDescList :: [a] -> MinQueue a
fromDescList :: forall a. [a] -> MinQueue a
fromDescList [a]
xs = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. a -> MinQueue a -> MinQueue a
insertMinQ') forall a. MinQueue a
empty [a]
xs
elemsU :: MinQueue a -> [a]
elemsU :: forall a. MinQueue a -> [a]
elemsU = forall a. MinQueue a -> [a]
toListU
keysQueue :: Prio.MinPQueue k a -> MinQueue k
keysQueue :: forall k a. MinPQueue k a -> MinQueue k
keysQueue MinPQueue k a
Prio.Empty = forall a. MinQueue a
Empty
keysQueue (Prio.MinPQ Int
n k
k a
_ BinomHeap k a
ts) = forall a. Int -> a -> MinQueue a -> MinQueue a
MinQueue Int
n k
k (forall a. BinomHeap a -> MinQueue a
BQ.MinQueue (forall (pRk :: * -> * -> *) k a (rk :: * -> *).
(pRk k a -> rk k) -> BinomForest pRk k a -> BinomForest rk k
keysF (forall a b. a -> b -> a
const forall a. Zero a
Zero) BinomHeap k a
ts))
keysF :: (pRk k a -> rk k) -> Prio.BinomForest pRk k a -> BinomForest rk k
keysF :: forall (pRk :: * -> * -> *) k a (rk :: * -> *).
(pRk k a -> rk k) -> BinomForest pRk k a -> BinomForest rk k
keysF pRk k a -> rk k
f BinomForest pRk k a
ts0 = case BinomForest pRk k a
ts0 of
BinomForest pRk k a
Prio.Nil -> forall (rk :: * -> *) a. BinomForest rk a
Nil
Prio.Skip BinomForest (Succ pRk) k a
ts' -> forall (rk :: * -> *) a.
BinomForest (Succ rk) a -> BinomForest rk a
Skip (forall (pRk :: * -> * -> *) k a (rk :: * -> *).
(pRk k a -> rk k) -> BinomForest pRk k a -> BinomForest rk k
keysF Succ pRk k a -> Succ rk k
f' BinomForest (Succ pRk) k a
ts')
Prio.Cons (Prio.BinomTree k
k a
_ pRk k a
ts) BinomForest (Succ pRk) k a
ts'
-> forall (rk :: * -> *) a.
BinomTree rk a -> BinomForest (Succ rk) a -> BinomForest rk a
Cons (forall (rk :: * -> *) a. a -> rk a -> BinomTree rk a
BinomTree k
k (pRk k a -> rk k
f pRk k a
ts)) (forall (pRk :: * -> * -> *) k a (rk :: * -> *).
(pRk k a -> rk k) -> BinomForest pRk k a -> BinomForest rk k
keysF Succ pRk k a -> Succ rk k
f' BinomForest (Succ pRk) k a
ts')
where f' :: Succ pRk k a -> Succ rk k
f' (Prio.Succ (Prio.BinomTree k
k a
_ pRk k a
ts) pRk k a
tss) = forall (rk :: * -> *) a. BinomTree rk a -> rk a -> Succ rk a
Succ (forall (rk :: * -> *) a. a -> rk a -> BinomTree rk a
BinomTree k
k (pRk k a -> rk k
f pRk k a
ts)) (pRk k a -> rk k
f pRk k a
tss)