{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
module Data.PQueue.Prio.Internals (
MinPQueue(..),
BinomForest(..),
BinomHeap,
BinomTree(..),
Zero(..),
Succ(..),
empty,
null,
size,
singleton,
insert,
insertBehind,
union,
getMin,
adjustMinWithKey,
adjustMinWithKeyA',
updateMinWithKey,
updateMinWithKeyA',
minViewWithKey,
mapWithKey,
mapKeysMonotonic,
mapMaybeWithKey,
mapEitherWithKey,
foldrWithKey,
foldlWithKey,
foldrU,
toAscList,
toDescList,
toListU,
insertMin,
insertMin',
insertMax',
fromList,
fromAscList,
foldrWithKeyU,
foldMapWithKeyU,
foldlWithKeyU,
foldlWithKeyU',
traverseWithKey,
mapMWithKey,
traverseWithKeyU,
seqSpine,
mapForest,
unions
) where
import Control.Applicative (liftA2, liftA3)
import Control.DeepSeq (NFData(rnf), deepseq)
import Data.Functor.Identity (Identity(Identity, runIdentity))
import qualified Data.List as List
import Data.PQueue.Internals.Foldable
#if MIN_VERSION_base(4,9,0)
import Data.Semigroup (Semigroup(..), stimesMonoid)
#else
import Data.Monoid ((<>))
#endif
import Prelude hiding (null, map)
#ifdef __GLASGOW_HASKELL__
import Data.Data
import GHC.Exts (build)
import Text.Read (Lexeme(Ident), lexP, parens, prec,
readPrec, readListPrec, readListPrecDefault)
#endif
import Data.Functor.WithIndex
import Data.Foldable.WithIndex
import Data.Traversable.WithIndex
#ifndef __GLASGOW_HASKELL__
build :: ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
build f = f (:) []
#endif
#if __GLASGOW_HASKELL__
instance (Data k, Data a, Ord k) => Data (MinPQueue k a) where
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MinPQueue k a -> c (MinPQueue k a)
gfoldl forall d b. Data d => c (d -> b) -> d -> c b
f forall g. g -> c g
z MinPQueue k a
m = forall g. g -> c g
z forall k a. Ord k => [(k, a)] -> MinPQueue k a
fromList forall d b. Data d => c (d -> b) -> d -> c b
`f` forall k a b.
Ord k =>
(k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKey (forall a b c. ((a, b) -> c) -> a -> b -> c
curry (:)) [] MinPQueue k a
m
toConstr :: MinPQueue k a -> Constr
toConstr MinPQueue k a
_ = Constr
fromListConstr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MinPQueue k a)
gunfold forall b r. Data b => c (b -> r) -> c r
k forall r. r -> c r
z Constr
c = case Constr -> Int
constrIndex Constr
c of
Int
1 -> forall b r. Data b => c (b -> r) -> c r
k (forall r. r -> c r
z forall k a. Ord k => [(k, a)] -> MinPQueue k a
fromList)
Int
_ -> forall a. HasCallStack => [Char] -> a
error [Char]
"gunfold"
dataTypeOf :: MinPQueue k a -> DataType
dataTypeOf MinPQueue k a
_ = DataType
queueDataType
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (MinPQueue k a))
dataCast1 forall d. Data d => c (t d)
f = forall {k1} {k2} (c :: k1 -> *) (t :: k2 -> k1) (t' :: k2 -> k1)
(a :: k2).
(Typeable t, Typeable t') =>
c (t a) -> Maybe (c (t' a))
gcast1 forall d. Data d => c (t d)
f
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (MinPQueue k a))
dataCast2 forall d e. (Data d, Data e) => c (t d e)
f = forall {k1} {k2} {k3} (c :: k1 -> *) (t :: k2 -> k3 -> k1)
(t' :: k2 -> k3 -> k1) (a :: k2) (b :: k3).
(Typeable t, Typeable t') =>
c (t a b) -> Maybe (c (t' a b))
gcast2 forall d e. (Data d, Data e) => c (t d e)
f
queueDataType :: DataType
queueDataType :: DataType
queueDataType = [Char] -> [Constr] -> DataType
mkDataType [Char]
"Data.PQueue.Prio.Min.MinPQueue" [Constr
fromListConstr]
fromListConstr :: Constr
fromListConstr :: Constr
fromListConstr = DataType -> [Char] -> [[Char]] -> Fixity -> Constr
mkConstr DataType
queueDataType [Char]
"fromList" [] Fixity
Prefix
#endif
#if MIN_VERSION_base(4,9,0)
instance Ord k => Semigroup (MinPQueue k a) where
<> :: MinPQueue k a -> MinPQueue k a -> MinPQueue k a
(<>) = forall k a.
Ord k =>
MinPQueue k a -> MinPQueue k a -> MinPQueue k a
union
stimes :: forall b. Integral b => b -> MinPQueue k a -> MinPQueue k a
stimes = forall b a. (Integral b, Monoid a) => b -> a -> a
stimesMonoid
{-# INLINABLE stimes #-}
#endif
instance Ord k => Monoid (MinPQueue k a) where
mempty :: MinPQueue k a
mempty = forall k a. MinPQueue k a
empty
#if !MIN_VERSION_base(4,11,0)
mappend = union
#endif
mconcat :: [MinPQueue k a] -> MinPQueue k a
mconcat = forall k a. Ord k => [MinPQueue k a] -> MinPQueue k a
unions
instance (Ord k, Show k, Show a) => Show (MinPQueue k a) where
showsPrec :: Int -> MinPQueue k a -> ShowS
showsPrec Int
p MinPQueue k a
xs = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10) forall a b. (a -> b) -> a -> b
$
[Char] -> ShowS
showString [Char]
"fromAscList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => a -> ShowS
shows (forall k a. Ord k => MinPQueue k a -> [(k, a)]
toAscList MinPQueue k a
xs)
instance (Read k, Read a) => Read (MinPQueue k a) where
#ifdef __GLASGOW_HASKELL__
readPrec :: ReadPrec (MinPQueue k 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 [Char]
"fromAscList" <- ReadPrec Lexeme
lexP
[(k, a)]
xs <- forall a. Read a => ReadPrec a
readPrec
forall (m :: * -> *) a. Monad m => a -> m a
return (forall k a. [(k, a)] -> MinPQueue k a
fromAscList [(k, a)]
xs)
readListPrec :: ReadPrec [MinPQueue k a]
readListPrec = 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
unions :: Ord k => [MinPQueue k a] -> MinPQueue k a
unions :: forall k a. Ord k => [MinPQueue k a] -> MinPQueue k a
unions = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' forall k a.
Ord k =>
MinPQueue k a -> MinPQueue k a -> MinPQueue k a
union forall k a. MinPQueue k a
empty
(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
(c -> d
f .: :: forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: a -> b -> c
g) a
x b
y = c -> d
f (a -> b -> c
g a
x b
y)
first' :: (a -> b) -> (a, c) -> (b, c)
first' :: forall a b c. (a -> b) -> (a, c) -> (b, c)
first' a -> b
f (a
a, c
c) = (a -> b
f a
a, c
c)
second' :: (b -> c) -> (a, b) -> (a, c)
second' :: forall b c a. (b -> c) -> (a, b) -> (a, c)
second' b -> c
f (a
a, b
b) = (a
a, b -> c
f b
b)
infixr 8 .:
data MinPQueue k a = Empty | MinPQ {-# UNPACK #-} !Int !k a !(BinomHeap k a)
data BinomForest rk k a =
Nil |
Skip (BinomForest (Succ rk) k a) |
Cons {-# UNPACK #-} !(BinomTree rk k a) (BinomForest (Succ rk) k a)
type BinomHeap = BinomForest Zero
data BinomTree rk k a = BinomTree !k a !(rk k a)
data Zero k a = Zero
data Succ rk k a = Succ {-# UNPACK #-} !(BinomTree rk k a) !(rk k a)
instance IFoldl' Zero where
foldlWithKey'_ :: forall b k a. (b -> k -> a -> b) -> b -> Zero k a -> b
foldlWithKey'_ b -> k -> a -> b
_ b
z ~Zero k a
Zero = b
z
instance IFoldMap Zero where
foldMapWithKey_ :: forall m k a. Monoid m => (k -> a -> m) -> Zero k a -> m
foldMapWithKey_ k -> a -> m
_ ~Zero k a
Zero = forall a. Monoid a => a
mempty
instance IFoldl' t => IFoldl' (Succ t) where
foldlWithKey'_ :: forall b k a. (b -> k -> a -> b) -> b -> Succ t k a -> b
foldlWithKey'_ b -> k -> a -> b
f b
z (Succ BinomTree t k a
t t k a
rk) = forall (t :: * -> * -> *) b k a.
IFoldl' t =>
(b -> k -> a -> b) -> b -> t k a -> b
foldlWithKey'_ b -> k -> a -> b
f b
z' t k a
rk
where
!z' :: b
z' = forall (t :: * -> * -> *) b k a.
IFoldl' t =>
(b -> k -> a -> b) -> b -> t k a -> b
foldlWithKey'_ b -> k -> a -> b
f b
z BinomTree t k a
t
instance IFoldMap t => IFoldMap (Succ t) where
foldMapWithKey_ :: forall m k a. Monoid m => (k -> a -> m) -> Succ t k a -> m
foldMapWithKey_ k -> a -> m
f (Succ BinomTree t k a
t t k a
rk) = forall (t :: * -> * -> *) m k a.
(IFoldMap t, Monoid m) =>
(k -> a -> m) -> t k a -> m
foldMapWithKey_ k -> a -> m
f BinomTree t k a
t forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> * -> *) m k a.
(IFoldMap t, Monoid m) =>
(k -> a -> m) -> t k a -> m
foldMapWithKey_ k -> a -> m
f t k a
rk
instance IFoldl' rk => IFoldl' (BinomTree rk) where
foldlWithKey'_ :: forall b k a. (b -> k -> a -> b) -> b -> BinomTree rk k a -> b
foldlWithKey'_ b -> k -> a -> b
f !b
z (BinomTree k
k a
a rk k a
rk) = forall (t :: * -> * -> *) b k a.
IFoldl' t =>
(b -> k -> a -> b) -> b -> t k a -> b
foldlWithKey'_ b -> k -> a -> b
f b
ft rk k a
rk
where
!ft :: b
ft = b -> k -> a -> b
f b
z k
k a
a
instance IFoldMap rk => IFoldMap (BinomTree rk) where
foldMapWithKey_ :: forall m k a. Monoid m => (k -> a -> m) -> BinomTree rk k a -> m
foldMapWithKey_ k -> a -> m
f (BinomTree k
k a
a rk k a
rk) = k -> a -> m
f k
k a
a forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> * -> *) m k a.
(IFoldMap t, Monoid m) =>
(k -> a -> m) -> t k a -> m
foldMapWithKey_ k -> a -> m
f rk k a
rk
instance IFoldl' t => IFoldl' (BinomForest t) where
foldlWithKey'_ :: forall b k a. (b -> k -> a -> b) -> b -> BinomForest t k a -> b
foldlWithKey'_ b -> k -> a -> b
_f b
z BinomForest t k a
Nil = b
z
foldlWithKey'_ b -> k -> a -> b
f !b
z (Skip BinomForest (Succ t) k a
ts) = forall (t :: * -> * -> *) b k a.
IFoldl' t =>
(b -> k -> a -> b) -> b -> t k a -> b
foldlWithKey'_ b -> k -> a -> b
f b
z BinomForest (Succ t) k a
ts
foldlWithKey'_ b -> k -> a -> b
f !b
z (Cons BinomTree t k a
t BinomForest (Succ t) k a
ts) = forall (t :: * -> * -> *) b k a.
IFoldl' t =>
(b -> k -> a -> b) -> b -> t k a -> b
foldlWithKey'_ b -> k -> a -> b
f b
ft BinomForest (Succ t) k a
ts
where
!ft :: b
ft = forall (t :: * -> * -> *) b k a.
IFoldl' t =>
(b -> k -> a -> b) -> b -> t k a -> b
foldlWithKey'_ b -> k -> a -> b
f b
z BinomTree t k a
t
instance IFoldMap t => IFoldMap (BinomForest t) where
foldMapWithKey_ :: forall m k a. Monoid m => (k -> a -> m) -> BinomForest t k a -> m
foldMapWithKey_ k -> a -> m
_f BinomForest t k a
Nil = forall a. Monoid a => a
mempty
foldMapWithKey_ k -> a -> m
f (Skip BinomForest (Succ t) k a
ts) = forall (t :: * -> * -> *) m k a.
(IFoldMap t, Monoid m) =>
(k -> a -> m) -> t k a -> m
foldMapWithKey_ k -> a -> m
f BinomForest (Succ t) k a
ts
foldMapWithKey_ k -> a -> m
f (Cons BinomTree t k a
t BinomForest (Succ t) k a
ts) = forall (t :: * -> * -> *) m k a.
(IFoldMap t, Monoid m) =>
(k -> a -> m) -> t k a -> m
foldMapWithKey_ k -> a -> m
f BinomTree t k a
t forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> * -> *) m k a.
(IFoldMap t, Monoid m) =>
(k -> a -> m) -> t k a -> m
foldMapWithKey_ k -> a -> m
f BinomForest (Succ t) k a
ts
instance (Ord k, Eq a) => Eq (MinPQueue k a) where
MinPQ Int
n1 k
k1 a
a1 BinomHeap k a
ts1 == :: MinPQueue k a -> MinPQueue k a -> Bool
== MinPQ Int
n2 k
k2 a
a2 BinomHeap k a
ts2 =
Int
n1 forall a. Eq a => a -> a -> Bool
== Int
n2 Bool -> Bool -> Bool
&& forall k a (rk :: * -> * -> *).
(Ord k, Eq a) =>
k
-> a -> BinomForest rk k a -> k -> a -> BinomForest rk k a -> Bool
eqExtract k
k1 a
a1 BinomHeap k a
ts1 k
k2 a
a2 BinomHeap k a
ts2
MinPQueue k a
Empty == MinPQueue k a
Empty = Bool
True
MinPQueue k a
_ == MinPQueue k a
_ = Bool
False
eqExtract :: (Ord k, Eq a) => k -> a -> BinomForest rk k a -> k -> a -> BinomForest rk k a -> Bool
k
k10 a
a10 BinomForest rk k a
ts10 k
k20 a
a20 BinomForest rk k a
ts20 =
k
k10 forall a. Eq a => a -> a -> Bool
== k
k20 Bool -> Bool -> Bool
&& a
a10 forall a. Eq a => a -> a -> Bool
== a
a20 Bool -> Bool -> Bool
&&
case (forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
extract BinomForest rk k a
ts10, forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
extract BinomForest rk k a
ts20) of
(Yes (Extract k
k1 a
a1 rk k a
_ BinomForest rk k a
ts1'), Yes (Extract k
k2 a
a2 rk k a
_ BinomForest rk k a
ts2'))
-> forall k a (rk :: * -> * -> *).
(Ord k, Eq a) =>
k
-> a -> BinomForest rk k a -> k -> a -> BinomForest rk k a -> Bool
eqExtract k
k1 a
a1 BinomForest rk k a
ts1' k
k2 a
a2 BinomForest rk k a
ts2'
(MExtract rk k a
No, MExtract rk k a
No) -> Bool
True
(MExtract rk k a, MExtract rk k a)
_ -> Bool
False
instance (Ord k, Ord a) => Ord (MinPQueue k a) where
MinPQ Int
_n1 k
k10 a
a10 BinomHeap k a
ts10 compare :: MinPQueue k a -> MinPQueue k a -> Ordering
`compare` MinPQ Int
_n2 k
k20 a
a20 BinomHeap k a
ts20 =
forall k a (rk :: * -> * -> *).
(Ord k, Ord a) =>
k
-> a
-> BinomForest rk k a
-> k
-> a
-> BinomForest rk k a
-> Ordering
cmpExtract k
k10 a
a10 BinomHeap k a
ts10 k
k20 a
a20 BinomHeap k a
ts20
MinPQueue k a
Empty `compare` MinPQueue k a
Empty = Ordering
EQ
MinPQueue k a
Empty `compare` MinPQ{} = Ordering
LT
MinPQ{} `compare` MinPQueue k a
Empty = Ordering
GT
cmpExtract :: (Ord k, Ord a) => k -> a -> BinomForest rk k a -> k -> a -> BinomForest rk k a -> Ordering
k
k10 a
a10 BinomForest rk k a
ts10 k
k20 a
a20 BinomForest rk k a
ts20 =
k
k10 forall a. Ord a => a -> a -> Ordering
`compare` k
k20 forall a. Semigroup a => a -> a -> a
<> a
a10 forall a. Ord a => a -> a -> Ordering
`compare` a
a20 forall a. Semigroup a => a -> a -> a
<>
case (forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
extract BinomForest rk k a
ts10, forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
extract BinomForest rk k a
ts20) of
(Yes (Extract k
k1 a
a1 rk k a
_ BinomForest rk k a
ts1'), Yes (Extract k
k2 a
a2 rk k a
_ BinomForest rk k a
ts2'))
-> forall k a (rk :: * -> * -> *).
(Ord k, Ord a) =>
k
-> a
-> BinomForest rk k a
-> k
-> a
-> BinomForest rk k a
-> Ordering
cmpExtract k
k1 a
a1 BinomForest rk k a
ts1' k
k2 a
a2 BinomForest rk k a
ts2'
(MExtract rk k a
No, Yes{}) -> Ordering
LT
(Yes{}, MExtract rk k a
No) -> Ordering
GT
(MExtract rk k a
No, MExtract rk k a
No) -> Ordering
EQ
empty :: MinPQueue k a
empty :: forall k a. MinPQueue k a
empty = forall k a. MinPQueue k a
Empty
null :: MinPQueue k a -> Bool
null :: forall k a. MinPQueue k a -> Bool
null MinPQueue k a
Empty = Bool
True
null MinPQueue k a
_ = Bool
False
size :: MinPQueue k a -> Int
size :: forall k a. MinPQueue k a -> Int
size MinPQueue k a
Empty = Int
0
size (MinPQ Int
n k
_ a
_ BinomHeap k a
_) = Int
n
singleton :: k -> a -> MinPQueue k a
singleton :: forall k a. k -> a -> MinPQueue k a
singleton k
k a
a = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
1 k
k a
a forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
insert :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert :: forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert k
k a
a MinPQueue k a
Empty = forall k a. k -> a -> MinPQueue k a
singleton k
k a
a
insert k
k a
a (MinPQ Int
n k
k' a
a' BinomHeap k a
ts)
| k
k forall a. Ord a => a -> a -> Bool
<= k
k' = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ (Int
n forall a. Num a => a -> a -> a
+ Int
1) k
k a
a (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMin (forall k a. k -> a -> BinomTree Zero k a
tip k
k' a
a') BinomHeap k a
ts)
| Bool
otherwise = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ (Int
n forall a. Num a => a -> a -> a
+ Int
1) k
k' a
a' (forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr (forall k a. k -> a -> BinomTree Zero k a
tip k
k a
a ) BinomHeap k a
ts)
insertBehind :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insertBehind :: forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insertBehind k
k a
v MinPQueue k a
q =
let ([(k, a)]
smaller, MinPQueue k a
larger) = forall k a.
Ord k =>
(k -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
spanKey (forall a. Ord a => a -> a -> Bool
<= k
k) MinPQueue k a
q
in forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert) (forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert k
k a
v MinPQueue k a
larger) [(k, a)]
smaller
spanKey :: Ord k => (k -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
spanKey :: forall k a.
Ord k =>
(k -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
spanKey k -> Bool
p MinPQueue k a
q = case forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
minViewWithKey MinPQueue k a
q of
Just (t :: (k, a)
t@(k
k, a
_), MinPQueue k a
q') | k -> Bool
p k
k ->
let ([(k, a)]
kas, MinPQueue k a
q'') = forall k a.
Ord k =>
(k -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
spanKey k -> Bool
p MinPQueue k a
q' in ((k, a)
t forall a. a -> [a] -> [a]
: [(k, a)]
kas, MinPQueue k a
q'')
Maybe ((k, a), MinPQueue k a)
_ -> ([], MinPQueue k a
q)
union :: Ord k => MinPQueue k a -> MinPQueue k a -> MinPQueue k a
union :: forall k a.
Ord k =>
MinPQueue k a -> MinPQueue k a -> MinPQueue k a
union (MinPQ Int
n1 k
k1 a
a1 BinomHeap k a
ts1) (MinPQ Int
n2 k
k2 a
a2 BinomHeap k a
ts2)
| k
k1 forall a. Ord a => a -> a -> Bool
<= k
k2 = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ (Int
n1 forall a. Num a => a -> a -> a
+ Int
n2) k
k1 a
a1 (k -> a -> BinomHeap k a
insMerge k
k2 a
a2)
| Bool
otherwise = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ (Int
n1 forall a. Num a => a -> a -> a
+ Int
n2) k
k2 a
a2 (k -> a -> BinomHeap k a
insMerge k
k1 a
a1)
where insMerge :: k -> a -> BinomHeap k a
insMerge k
k a
a = forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a
-> BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
carryForest (forall k a. k -> a -> BinomTree Zero k a
tip k
k a
a) BinomHeap k a
ts1 BinomHeap k a
ts2
union MinPQueue k a
Empty MinPQueue k a
q2 = MinPQueue k a
q2
union MinPQueue k a
q1 MinPQueue k a
Empty = MinPQueue k a
q1
getMin :: MinPQueue k a -> Maybe (k, a)
getMin :: forall k a. MinPQueue k a -> Maybe (k, a)
getMin (MinPQ Int
_ k
k a
a BinomHeap k a
_) = forall a. a -> Maybe a
Just (k
k, a
a)
getMin MinPQueue k a
_ = forall a. Maybe a
Nothing
adjustMinWithKey :: (k -> a -> a) -> MinPQueue k a -> MinPQueue k a
adjustMinWithKey :: forall k a. (k -> a -> a) -> MinPQueue k a -> MinPQueue k a
adjustMinWithKey k -> a -> a
_ MinPQueue k a
Empty = forall k a. MinPQueue k a
Empty
adjustMinWithKey k -> a -> a
f (MinPQ Int
n k
k a
a BinomHeap k a
ts) = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
n k
k (k -> a -> a
f k
k a
a) BinomHeap k a
ts
adjustMinWithKeyA' :: Applicative f => (MinPQueue k a -> r) -> (k -> a -> f a) -> MinPQueue k a -> f r
adjustMinWithKeyA' :: forall (f :: * -> *) k a r.
Applicative f =>
(MinPQueue k a -> r) -> (k -> a -> f a) -> MinPQueue k a -> f r
adjustMinWithKeyA' MinPQueue k a -> r
g k -> a -> f a
_ MinPQueue k a
Empty = forall (f :: * -> *) a. Applicative f => a -> f a
pure (MinPQueue k a -> r
g forall k a. MinPQueue k a
Empty)
adjustMinWithKeyA' MinPQueue k a -> r
g k -> a -> f a
f (MinPQ Int
n k
k a
a BinomHeap k a
ts) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\a
a' -> MinPQueue k a -> r
g (forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
n k
k a
a' BinomHeap k a
ts)) (k -> a -> f a
f k
k a
a)
updateMinWithKey :: Ord k => (k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
updateMinWithKey :: forall k a.
Ord k =>
(k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
updateMinWithKey k -> a -> Maybe a
_ MinPQueue k a
Empty = forall k a. MinPQueue k a
Empty
updateMinWithKey k -> a -> Maybe a
f (MinPQ Int
n k
k a
a BinomHeap k a
ts) = case k -> a -> Maybe a
f k
k a
a of
Maybe a
Nothing -> forall k a. Ord k => Int -> BinomHeap k a -> MinPQueue k a
extractHeap Int
n BinomHeap k a
ts
Just a
a' -> forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
n k
k a
a' BinomHeap k a
ts
updateMinWithKeyA'
:: (Applicative f, Ord k)
=> (MinPQueue k a -> r)
-> (k -> a -> f (Maybe a))
-> MinPQueue k a
-> f r
updateMinWithKeyA' :: forall (f :: * -> *) k a r.
(Applicative f, Ord k) =>
(MinPQueue k a -> r)
-> (k -> a -> f (Maybe a)) -> MinPQueue k a -> f r
updateMinWithKeyA' MinPQueue k a -> r
g k -> a -> f (Maybe a)
_ MinPQueue k a
Empty = forall (f :: * -> *) a. Applicative f => a -> f a
pure (MinPQueue k a -> r
g forall k a. MinPQueue k a
Empty)
updateMinWithKeyA' MinPQueue k a -> r
g k -> a -> f (Maybe a)
f (MinPQ Int
n k
k a
a BinomHeap k a
ts) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (MinPQueue k a -> r
g forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe a -> MinPQueue k a
tweak) (k -> a -> f (Maybe a)
f k
k a
a)
where
tweak :: Maybe a -> MinPQueue k a
tweak Maybe a
Nothing = forall k a. Ord k => Int -> BinomHeap k a -> MinPQueue k a
extractHeap Int
n BinomHeap k a
ts
tweak (Just a
a') = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
n k
k a
a' BinomHeap k a
ts
minViewWithKey :: Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
minViewWithKey :: forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
minViewWithKey MinPQueue k a
Empty = forall a. Maybe a
Nothing
minViewWithKey (MinPQ Int
n k
k a
a BinomHeap k a
ts) = forall a. a -> Maybe a
Just ((k
k, a
a), forall k a. Ord k => Int -> BinomHeap k a -> MinPQueue k a
extractHeap Int
n BinomHeap k a
ts)
mapWithKey :: (k -> a -> b) -> MinPQueue k a -> MinPQueue k b
mapWithKey :: forall k a b. (k -> a -> b) -> MinPQueue k a -> MinPQueue k b
mapWithKey k -> a -> b
f = forall a. Identity a -> a
runIdentity forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
traverseWithKeyU (forall a. a -> Identity a
Identity forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: k -> a -> b
f)
mapKeysMonotonic :: (k -> k') -> MinPQueue k a -> MinPQueue k' a
mapKeysMonotonic :: forall k k' a. (k -> k') -> MinPQueue k a -> MinPQueue k' a
mapKeysMonotonic k -> k'
_ MinPQueue k a
Empty = forall k a. MinPQueue k a
Empty
mapKeysMonotonic k -> k'
f (MinPQ Int
n k
k a
a BinomHeap k a
ts) = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
n (k -> k'
f k
k) a
a (forall k k' (rk :: * -> * -> *) a.
(k -> k')
-> (rk k a -> rk k' a) -> BinomForest rk k a -> BinomForest rk k' a
mapKeysMonoF k -> k'
f (forall a b. a -> b -> a
const forall k a. Zero k a
Zero) BinomHeap k a
ts)
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
mapMaybeWithKey :: forall k a b.
Ord k =>
(k -> a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
mapMaybeWithKey k -> a -> Maybe b
_ MinPQueue k a
Empty = forall k a. MinPQueue k a
Empty
mapMaybeWithKey k -> a -> Maybe b
f (MinPQ Int
_ k
k a
a BinomHeap k a
ts) = forall b a. b -> (a -> b) -> Maybe a -> b
maybe forall a. a -> a
id (forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert k
k) (k -> a -> Maybe b
f k
k a
a) (forall k a b (rk :: * -> * -> *).
Ord k =>
(k -> a -> Maybe b)
-> (rk k a -> MinPQueue k b) -> BinomForest rk k a -> MinPQueue k b
mapMaybeF k -> a -> Maybe b
f (forall a b. a -> b -> a
const forall k a. MinPQueue k a
Empty) BinomHeap k a
ts)
mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)
mapEitherWithKey :: forall k a b c.
Ord k =>
(k -> a -> Either b c)
-> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)
mapEitherWithKey k -> a -> Either b c
_ MinPQueue k a
Empty = (forall k a. MinPQueue k a
Empty, forall k a. MinPQueue k a
Empty)
mapEitherWithKey k -> a -> Either b c
f (MinPQ Int
_ k
k a
a BinomHeap k a
ts) = forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert k
k) (forall b c a. (b -> c) -> (a, b) -> (a, c)
second' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert k
k) (k -> a -> Either b c
f k
k a
a)
(forall k a b c (rk :: * -> * -> *).
Ord k =>
(k -> a -> Either b c)
-> (rk k a -> (MinPQueue k b, MinPQueue k c))
-> BinomForest rk k a
-> (MinPQueue k b, MinPQueue k c)
mapEitherF k -> a -> Either b c
f (forall a b. a -> b -> a
const (forall k a. MinPQueue k a
Empty, forall k a. MinPQueue k a
Empty)) BinomHeap k a
ts)
foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKey :: forall k a b.
Ord k =>
(k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKey k -> a -> b -> b
_ b
z MinPQueue k a
Empty = b
z
foldrWithKey k -> a -> b -> b
f b
z (MinPQ Int
_ k
k0 a
a0 BinomHeap k a
ts0) = k -> a -> b -> b
f k
k0 a
a0 (forall {rk :: * -> * -> *}. BinomForest rk k a -> b
foldF BinomHeap k a
ts0) where
foldF :: BinomForest rk k a -> b
foldF BinomForest rk k a
ts = case forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
extract BinomForest rk k a
ts of
Yes (Extract k
k a
a rk k a
_ BinomForest rk k a
ts') -> k -> a -> b -> b
f k
k a
a (BinomForest rk k a -> b
foldF BinomForest rk k a
ts')
MExtract rk k a
_ -> b
z
foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MinPQueue k a -> b
foldlWithKey :: forall k b a.
Ord k =>
(b -> k -> a -> b) -> b -> MinPQueue k a -> b
foldlWithKey b -> k -> a -> b
_ b
z MinPQueue k a
Empty = b
z
foldlWithKey b -> k -> a -> b
f b
z0 (MinPQ Int
_ k
k0 a
a0 BinomHeap k a
ts0) = forall {rk :: * -> * -> *}. b -> BinomForest rk k a -> b
foldF (b -> k -> a -> b
f b
z0 k
k0 a
a0) BinomHeap k a
ts0 where
foldF :: b -> BinomForest rk k a -> b
foldF b
z BinomForest rk k a
ts = case forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
extract BinomForest rk k a
ts of
Yes (Extract k
k a
a rk k a
_ BinomForest rk k a
ts') -> b -> BinomForest rk k a -> b
foldF (b -> k -> a -> b
f b
z k
k a
a) BinomForest rk k a
ts'
MExtract rk k a
_ -> b
z
{-# INLINABLE [1] toAscList #-}
toAscList :: Ord k => MinPQueue k a -> [(k, a)]
toAscList :: forall k a. Ord k => MinPQueue k a -> [(k, a)]
toAscList = forall k a b.
Ord k =>
(k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKey (forall a b c. ((a, b) -> c) -> a -> b -> c
curry (:)) []
{-# INLINABLE [1] toDescList #-}
toDescList :: Ord k => MinPQueue k a -> [(k, a)]
toDescList :: forall k a. Ord k => MinPQueue k a -> [(k, a)]
toDescList = forall k b a.
Ord k =>
(b -> k -> a -> b) -> b -> MinPQueue k a -> b
foldlWithKey (\[(k, a)]
z k
k a
a -> (k
k, a
a) forall a. a -> [a] -> [a]
: [(k, a)]
z) []
fromAscList :: [(k, a)] -> MinPQueue k a
{-# INLINE fromAscList #-}
fromAscList :: forall k a. [(k, a)] -> MinPQueue k a
fromAscList [(k, a)]
xs = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\MinPQueue k a
q (k
k, a
a) -> forall k a. k -> a -> MinPQueue k a -> MinPQueue k a
insertMax' k
k a
a MinPQueue k a
q) forall k a. MinPQueue k a
empty [(k, a)]
xs
{-# RULES
"toAscList" toAscList = \q -> build (\c n -> foldrWithKey (curry c) n q);
"toDescList" toDescList = \q -> build (\c n -> foldlWithKey (\z k a -> (k, a) `c` z) n q);
"toListU" toListU = \q -> build (\c n -> foldrWithKeyU (curry c) n q);
#-}
{-# NOINLINE toListU #-}
toListU :: MinPQueue k a -> [(k, a)]
toListU :: forall k a. MinPQueue k a -> [(k, a)]
toListU = forall k a b. (k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKeyU (forall a b c. ((a, b) -> c) -> a -> b -> c
curry (:)) []
foldrU :: (a -> b -> b) -> b -> MinPQueue k a -> b
foldrU :: forall a b k. (a -> b -> b) -> b -> MinPQueue k a -> b
foldrU = forall k a b. (k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKeyU forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const
insertMin :: k -> a -> MinPQueue k a -> MinPQueue k a
insertMin :: forall k a. k -> a -> MinPQueue k a -> MinPQueue k a
insertMin k
k a
a MinPQueue k a
Empty = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
1 k
k a
a forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
insertMin k
k a
a (MinPQ Int
n k
k' a
a' BinomHeap k a
ts) = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ (Int
n forall a. Num a => a -> a -> a
+ Int
1) k
k a
a (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMin (forall k a. k -> a -> BinomTree Zero k a
tip k
k' a
a') BinomHeap k a
ts)
insertMin' :: k -> a -> MinPQueue k a -> MinPQueue k a
insertMin' :: forall k a. k -> a -> MinPQueue k a -> MinPQueue k a
insertMin' k
k a
a MinPQueue k a
Empty = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
1 k
k a
a forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
insertMin' k
k a
a (MinPQ Int
n k
k' a
a' BinomHeap k a
ts) = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ (Int
n forall a. Num a => a -> a -> a
+ Int
1) k
k a
a (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMin' (forall k a. k -> a -> BinomTree Zero k a
tip k
k' a
a') BinomHeap k a
ts)
insertMax' :: k -> a -> MinPQueue k a -> MinPQueue k a
insertMax' :: forall k a. k -> a -> MinPQueue k a -> MinPQueue k a
insertMax' k
k a
a MinPQueue k a
Empty = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
1 k
k a
a forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
insertMax' k
k a
a (MinPQ Int
n k
k' a
a' BinomHeap k a
ts) = forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ (Int
n forall a. Num a => a -> a -> a
+ Int
1) k
k' a
a' (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMax' (forall k a. k -> a -> BinomTree Zero k a
tip k
k a
a) BinomHeap k a
ts)
{-# INLINE fromList #-}
fromList :: Ord k => [(k, a)] -> MinPQueue k a
fromList :: forall k a. Ord k => [(k, a)] -> MinPQueue k a
fromList [(k, a)]
xs = case forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
extract (forall k a. Ord k => [(k, a)] -> BinomHeap k a
fromListHeap [(k, a)]
xs) of
MExtract Zero k a
No -> forall k a. MinPQueue k a
Empty
Yes (Extract k
k a
v ~Zero k a
Zero BinomForest Zero k a
f) -> forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ (forall k a. BinomHeap k a -> Int
sizeHeap BinomForest Zero k a
f forall a. Num a => a -> a -> a
+ Int
1) k
k a
v BinomForest Zero k a
f
{-# INLINE fromListHeap #-}
fromListHeap :: Ord k => [(k, a)] -> BinomHeap k a
fromListHeap :: forall k a. Ord k => [(k, a)] -> BinomHeap k a
fromListHeap [(k, a)]
xs = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' forall {k} {a}.
Ord k =>
BinomForest Zero k a -> (k, a) -> BinomForest Zero k a
go forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil [(k, a)]
xs
where
go :: BinomForest Zero k a -> (k, a) -> BinomForest Zero k a
go BinomForest Zero k a
fr (k
k, a
a) = forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr' (forall k a. k -> a -> BinomTree Zero k a
tip k
k a
a) BinomForest Zero k a
fr
sizeHeap :: BinomHeap k a -> Int
sizeHeap :: forall k a. BinomHeap k a -> Int
sizeHeap = forall (rk :: * -> * -> *) k a.
Int -> Int -> BinomForest rk k a -> Int
go Int
0 Int
1
where
go :: Int -> Int -> BinomForest rk k a -> Int
go :: forall (rk :: * -> * -> *) k a.
Int -> Int -> BinomForest rk k a -> Int
go Int
acc Int
rk BinomForest rk k a
Nil = Int
rk seq :: forall a b. a -> b -> b
`seq` Int
acc
go Int
acc Int
rk (Skip BinomForest (Succ rk) k a
f) = forall (rk :: * -> * -> *) k a.
Int -> Int -> BinomForest rk k a -> Int
go Int
acc (Int
2 forall a. Num a => a -> a -> a
* Int
rk) BinomForest (Succ rk) k a
f
go Int
acc Int
rk (Cons BinomTree rk k a
_t BinomForest (Succ rk) k a
f) = forall (rk :: * -> * -> *) k a.
Int -> Int -> BinomForest rk k a -> Int
go (Int
acc forall a. Num a => a -> a -> a
+ Int
rk) (Int
2 forall a. Num a => a -> a -> a
* Int
rk) BinomForest (Succ rk) k a
f
tip :: k -> a -> BinomTree Zero k a
tip :: forall k a. k -> a -> BinomTree Zero k a
tip k
k a
a = forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k a
a forall k a. Zero k a
Zero
meld :: Ord k => BinomTree rk k a -> BinomTree rk k a -> BinomTree (Succ rk) k a
meld :: forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomTree rk k a -> BinomTree (Succ rk) k a
meld t1 :: BinomTree rk k a
t1@(BinomTree k
k1 a
v1 rk k a
ts1) t2 :: BinomTree rk k a
t2@(BinomTree k
k2 a
v2 rk k a
ts2)
| k
k1 forall a. Ord a => a -> a -> Bool
<= k
k2 = forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k1 a
v1 (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> rk k a -> Succ rk k a
Succ BinomTree rk k a
t2 rk k a
ts1)
| Bool
otherwise = forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k2 a
v2 (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> rk k a -> Succ rk k a
Succ BinomTree rk k a
t1 rk k a
ts2)
mergeForest :: Ord k => BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
mergeForest :: forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
mergeForest BinomForest rk k a
f1 BinomForest rk k a
f2 = case (BinomForest rk k a
f1, BinomForest rk k a
f2) of
(Skip BinomForest (Succ rk) k a
ts1, Skip BinomForest (Succ rk) k a
ts2) -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip forall a b. (a -> b) -> a -> b
$! forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
mergeForest BinomForest (Succ rk) k a
ts1 BinomForest (Succ rk) k a
ts2
(Skip BinomForest (Succ rk) k a
ts1, Cons BinomTree rk k a
t2 BinomForest (Succ rk) k a
ts2) -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t2 forall a b. (a -> b) -> a -> b
$! forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
mergeForest BinomForest (Succ rk) k a
ts1 BinomForest (Succ rk) k a
ts2
(Cons BinomTree rk k a
t1 BinomForest (Succ rk) k a
ts1, Skip BinomForest (Succ rk) k a
ts2) -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t1 forall a b. (a -> b) -> a -> b
$! forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
mergeForest BinomForest (Succ rk) k a
ts1 BinomForest (Succ rk) k a
ts2
(Cons BinomTree rk k a
t1 BinomForest (Succ rk) k a
ts1, Cons BinomTree rk k a
t2 BinomForest (Succ rk) k a
ts2) -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip forall a b. (a -> b) -> a -> b
$! forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a
-> BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
carryForest (forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomTree rk k a -> BinomTree (Succ rk) k a
meld BinomTree rk k a
t1 BinomTree rk k a
t2) BinomForest (Succ rk) k a
ts1 BinomForest (Succ rk) k a
ts2
(BinomForest rk k a
Nil, BinomForest rk k a
_) -> BinomForest rk k a
f2
(BinomForest rk k a
_, BinomForest rk k a
Nil) -> BinomForest rk k a
f1
carryForest :: Ord k => BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
carryForest :: forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a
-> BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
carryForest BinomTree rk k a
t0 BinomForest rk k a
f1 BinomForest rk k a
f2 = BinomTree rk k a
t0 seq :: forall a b. a -> b -> b
`seq` case (BinomForest rk k a
f1, BinomForest rk k a
f2) of
(Cons BinomTree rk k a
t1 BinomForest (Succ rk) k a
ts1, Cons BinomTree rk k a
t2 BinomForest (Succ rk) k a
ts2) -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t0 forall a b. (a -> b) -> a -> b
$! forall {rk :: * -> * -> *} {a}.
BinomTree rk k a
-> BinomTree rk k a
-> BinomForest (Succ rk) k a
-> BinomForest (Succ rk) k a
-> BinomForest (Succ rk) k a
carryMeld BinomTree rk k a
t1 BinomTree rk k a
t2 BinomForest (Succ rk) k a
ts1 BinomForest (Succ rk) k a
ts2
(Cons BinomTree rk k a
t1 BinomForest (Succ rk) k a
ts1, Skip BinomForest (Succ rk) k a
ts2) -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip forall a b. (a -> b) -> a -> b
$! forall {rk :: * -> * -> *} {a}.
BinomTree rk k a
-> BinomTree rk k a
-> BinomForest (Succ rk) k a
-> BinomForest (Succ rk) k a
-> BinomForest (Succ rk) k a
carryMeld BinomTree rk k a
t0 BinomTree rk k a
t1 BinomForest (Succ rk) k a
ts1 BinomForest (Succ rk) k a
ts2
(Skip BinomForest (Succ rk) k a
ts1, Cons BinomTree rk k a
t2 BinomForest (Succ rk) k a
ts2) -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip forall a b. (a -> b) -> a -> b
$! forall {rk :: * -> * -> *} {a}.
BinomTree rk k a
-> BinomTree rk k a
-> BinomForest (Succ rk) k a
-> BinomForest (Succ rk) k a
-> BinomForest (Succ rk) k a
carryMeld BinomTree rk k a
t0 BinomTree rk k a
t2 BinomForest (Succ rk) k a
ts1 BinomForest (Succ rk) k a
ts2
(Skip BinomForest (Succ rk) k a
ts1, Skip BinomForest (Succ rk) k a
ts2) -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t0 forall a b. (a -> b) -> a -> b
$! forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
mergeForest BinomForest (Succ rk) k a
ts1 BinomForest (Succ rk) k a
ts2
(BinomForest rk k a
Nil, BinomForest rk k a
_) -> forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr BinomTree rk k a
t0 BinomForest rk k a
f2
(BinomForest rk k a
_, BinomForest rk k a
Nil) -> forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr BinomTree rk k a
t0 BinomForest rk k a
f1
where carryMeld :: BinomTree rk k a
-> BinomTree rk k a
-> BinomForest (Succ rk) k a
-> BinomForest (Succ rk) k a
-> BinomForest (Succ rk) k a
carryMeld = forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a
-> BinomForest rk k a -> BinomForest rk k a -> BinomForest rk k a
carryForest forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomTree rk k a -> BinomTree (Succ rk) k a
meld
incr :: Ord k => BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr :: forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr BinomTree rk k a
t BinomForest rk k a
ts = BinomTree rk k a
t seq :: forall a b. a -> b -> b
`seq` case BinomForest rk k a
ts of
BinomForest rk k a
Nil -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
Skip BinomForest (Succ rk) k a
ts' -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t BinomForest (Succ rk) k a
ts'
Cons BinomTree rk k a
t' BinomForest (Succ rk) k a
ts' -> BinomForest (Succ rk) k a
ts' seq :: forall a b. a -> b -> b
`seq` forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip (forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr (forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomTree rk k a -> BinomTree (Succ rk) k a
meld BinomTree rk k a
t BinomTree rk k a
t') BinomForest (Succ rk) k a
ts')
incr' :: Ord k => BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr' :: forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr' BinomTree rk k a
t BinomForest rk k a
ts = BinomTree rk k a
t seq :: forall a b. a -> b -> b
`seq` case BinomForest rk k a
ts of
BinomForest rk k a
Nil -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
Skip BinomForest (Succ rk) k a
ts' -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t BinomForest (Succ rk) k a
ts'
Cons BinomTree rk k a
t' BinomForest (Succ rk) k a
ts' -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip forall a b. (a -> b) -> a -> b
$! forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr' (forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomTree rk k a -> BinomTree (Succ rk) k a
meld BinomTree rk k a
t BinomTree rk k a
t') BinomForest (Succ rk) k a
ts'
incrMin :: BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMin :: forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMin t :: BinomTree rk k a
t@(BinomTree k
k a
a rk k a
ts) BinomForest rk k a
tss = case BinomForest rk k a
tss of
BinomForest rk k a
Nil -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
Skip BinomForest (Succ rk) k a
tss' -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t BinomForest (Succ rk) k a
tss'
Cons BinomTree rk k a
t' BinomForest (Succ rk) k a
tss' -> BinomForest (Succ rk) k a
tss' seq :: forall a b. a -> b -> b
`seq` forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMin (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k a
a (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> rk k a -> Succ rk k a
Succ BinomTree rk k a
t' rk k a
ts)) BinomForest (Succ rk) k a
tss')
incrMin' :: BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMin' :: forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMin' t :: BinomTree rk k a
t@(BinomTree k
k a
a rk k a
ts) BinomForest rk k a
tss = case BinomForest rk k a
tss of
BinomForest rk k a
Nil -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
Skip BinomForest (Succ rk) k a
tss' -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t BinomForest (Succ rk) k a
tss'
Cons BinomTree rk k a
t' BinomForest (Succ rk) k a
tss' -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip forall a b. (a -> b) -> a -> b
$! forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMin' (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k a
a (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> rk k a -> Succ rk k a
Succ BinomTree rk k a
t' rk k a
ts)) BinomForest (Succ rk) k a
tss'
incrMax' :: BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMax' :: forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMax' BinomTree rk k a
t BinomForest rk k a
tss = BinomTree rk k a
t seq :: forall a b. a -> b -> b
`seq` case BinomForest rk k a
tss of
BinomForest rk k a
Nil -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
Skip BinomForest (Succ rk) k a
tss' -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
t BinomForest (Succ rk) k a
tss'
Cons (BinomTree k
k a
a rk k a
ts) BinomForest (Succ rk) k a
tss' -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip forall a b. (a -> b) -> a -> b
$! forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incrMax' (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k a
a (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> rk k a -> Succ rk k a
Succ BinomTree rk k a
t rk k a
ts)) BinomForest (Succ rk) k a
tss'
extractHeap :: Ord k => Int -> BinomHeap k a -> MinPQueue k a
Int
n BinomHeap k a
ts = Int
n seq :: forall a b. a -> b -> b
`seq` case forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
extract BinomHeap k a
ts of
MExtract Zero k a
No -> forall k a. MinPQueue k a
Empty
Yes (Extract k
k a
a Zero k a
_ BinomHeap k a
ts') -> forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ (Int
n forall a. Num a => a -> a -> a
- Int
1) k
k a
a BinomHeap k a
ts'
data rk k a = !k a !(rk k a) !(BinomForest rk k a)
data rk k a = No | Yes {-# UNPACK #-} !(Extract rk k a)
incrExtract :: Extract (Succ rk) k a -> Extract rk k a
(Extract k
minKey a
minVal (Succ BinomTree rk k a
kChild rk k a
kChildren) BinomForest (Succ rk) k a
ts)
= forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomForest rk k a -> Extract rk k a
Extract k
minKey a
minVal rk k a
kChildren (forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons BinomTree rk k a
kChild BinomForest (Succ rk) k a
ts)
incrExtract' :: Ord k => BinomTree rk k a -> Extract (Succ rk) k a -> Extract rk k a
BinomTree rk k a
t (Extract k
minKey a
minVal (Succ BinomTree rk k a
kChild rk k a
kChildren) BinomForest (Succ rk) k a
ts)
= forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomForest rk k a -> Extract rk k a
Extract k
minKey a
minVal rk k a
kChildren (forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip forall a b. (a -> b) -> a -> b
$ forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomForest rk k a -> BinomForest rk k a
incr (BinomTree rk k a
t forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> BinomTree rk k a -> BinomTree (Succ rk) k a
`meld` BinomTree rk k a
kChild) BinomForest (Succ rk) k a
ts)
extract :: Ord k => BinomForest rk k a -> MExtract rk k a
= forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
start
where
start :: Ord k => BinomForest rk k a -> MExtract rk k a
start :: forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
start BinomForest rk k a
Nil = forall (rk :: * -> * -> *) k a. MExtract rk k a
No
start (Skip BinomForest (Succ rk) k a
f) = case forall k (rk :: * -> * -> *) a.
Ord k =>
BinomForest rk k a -> MExtract rk k a
start BinomForest (Succ rk) k a
f of
MExtract (Succ rk) k a
No -> forall (rk :: * -> * -> *) k a. MExtract rk k a
No
Yes Extract (Succ rk) k a
ex -> forall (rk :: * -> * -> *) k a. Extract rk k a -> MExtract rk k a
Yes (forall (rk :: * -> * -> *) k a.
Extract (Succ rk) k a -> Extract rk k a
incrExtract Extract (Succ rk) k a
ex)
start (Cons t :: BinomTree rk k a
t@(BinomTree k
k a
v rk k a
ts) BinomForest (Succ rk) k a
f) = forall (rk :: * -> * -> *) k a. Extract rk k a -> MExtract rk k a
Yes forall a b. (a -> b) -> a -> b
$ case forall k (rk :: * -> * -> *) a.
Ord k =>
k -> BinomForest rk k a -> MExtract rk k a
go k
k BinomForest (Succ rk) k a
f of
MExtract (Succ rk) k a
No -> forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomForest rk k a -> Extract rk k a
Extract k
k a
v rk k a
ts (forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip BinomForest (Succ rk) k a
f)
Yes Extract (Succ rk) k a
ex -> forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> Extract (Succ rk) k a -> Extract rk k a
incrExtract' BinomTree rk k a
t Extract (Succ rk) k a
ex
go :: Ord k => k -> BinomForest rk k a -> MExtract rk k a
go :: forall k (rk :: * -> * -> *) a.
Ord k =>
k -> BinomForest rk k a -> MExtract rk k a
go k
_min_above BinomForest rk k a
Nil = k
_min_above seq :: forall a b. a -> b -> b
`seq` forall (rk :: * -> * -> *) k a. MExtract rk k a
No
go k
min_above (Skip BinomForest (Succ rk) k a
f) = case forall k (rk :: * -> * -> *) a.
Ord k =>
k -> BinomForest rk k a -> MExtract rk k a
go k
min_above BinomForest (Succ rk) k a
f of
MExtract (Succ rk) k a
No -> forall (rk :: * -> * -> *) k a. MExtract rk k a
No
Yes Extract (Succ rk) k a
ex -> forall (rk :: * -> * -> *) k a. Extract rk k a -> MExtract rk k a
Yes (forall (rk :: * -> * -> *) k a.
Extract (Succ rk) k a -> Extract rk k a
incrExtract Extract (Succ rk) k a
ex)
go k
min_above (Cons t :: BinomTree rk k a
t@(BinomTree k
k a
v rk k a
ts) BinomForest (Succ rk) k a
f)
| k
min_above forall a. Ord a => a -> a -> Bool
<= k
k = case forall k (rk :: * -> * -> *) a.
Ord k =>
k -> BinomForest rk k a -> MExtract rk k a
go k
min_above BinomForest (Succ rk) k a
f of
MExtract (Succ rk) k a
No -> forall (rk :: * -> * -> *) k a. MExtract rk k a
No
Yes Extract (Succ rk) k a
ex -> forall (rk :: * -> * -> *) k a. Extract rk k a -> MExtract rk k a
Yes (forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> Extract (Succ rk) k a -> Extract rk k a
incrExtract' BinomTree rk k a
t Extract (Succ rk) k a
ex)
| Bool
otherwise = case forall k (rk :: * -> * -> *) a.
Ord k =>
k -> BinomForest rk k a -> MExtract rk k a
go k
k BinomForest (Succ rk) k a
f of
MExtract (Succ rk) k a
No -> forall (rk :: * -> * -> *) k a. Extract rk k a -> MExtract rk k a
Yes (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomForest rk k a -> Extract rk k a
Extract k
k a
v rk k a
ts (forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip BinomForest (Succ rk) k a
f))
Yes Extract (Succ rk) k a
ex -> forall (rk :: * -> * -> *) k a. Extract rk k a -> MExtract rk k a
Yes (forall k (rk :: * -> * -> *) a.
Ord k =>
BinomTree rk k a -> Extract (Succ rk) k a -> Extract rk k a
incrExtract' BinomTree rk k a
t Extract (Succ rk) k a
ex)
mapForest :: (k -> a -> b) -> (rk k a -> rk k b) -> BinomForest rk k a -> BinomForest rk k b
mapForest :: forall k a b (rk :: * -> * -> *).
(k -> a -> b)
-> (rk k a -> rk k b) -> BinomForest rk k a -> BinomForest rk k b
mapForest k -> a -> b
f rk k a -> rk k b
fCh BinomForest rk k a
ts0 = case BinomForest rk k a
ts0 of
BinomForest rk k a
Nil -> forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
Skip BinomForest (Succ rk) k a
ts' -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip (forall k a b (rk :: * -> * -> *).
(k -> a -> b)
-> (rk k a -> rk k b) -> BinomForest rk k a -> BinomForest rk k b
mapForest k -> a -> b
f Succ rk k a -> Succ rk k b
fCh' BinomForest (Succ rk) k a
ts')
Cons (BinomTree k
k a
a rk k a
ts) BinomForest (Succ rk) k a
tss
-> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k (k -> a -> b
f k
k a
a) (rk k a -> rk k b
fCh rk k a
ts)) (forall k a b (rk :: * -> * -> *).
(k -> a -> b)
-> (rk k a -> rk k b) -> BinomForest rk k a -> BinomForest rk k b
mapForest k -> a -> b
f Succ rk k a -> Succ rk k b
fCh' BinomForest (Succ rk) k a
tss)
where fCh' :: Succ rk k a -> Succ rk k b
fCh' (Succ (BinomTree k
k a
a rk k a
ts) rk k a
tss)
= forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> rk k a -> Succ rk k a
Succ (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k (k -> a -> b
f k
k a
a) (rk k a -> rk k b
fCh rk k a
ts)) (rk k a -> rk k b
fCh rk k a
tss)
mapMaybeF :: Ord k => (k -> a -> Maybe b) -> (rk k a -> MinPQueue k b) ->
BinomForest rk k a -> MinPQueue k b
mapMaybeF :: forall k a b (rk :: * -> * -> *).
Ord k =>
(k -> a -> Maybe b)
-> (rk k a -> MinPQueue k b) -> BinomForest rk k a -> MinPQueue k b
mapMaybeF k -> a -> Maybe b
f rk k a -> MinPQueue k b
fCh BinomForest rk k a
ts0 = case BinomForest rk k a
ts0 of
BinomForest rk k a
Nil -> forall k a. MinPQueue k a
Empty
Skip BinomForest (Succ rk) k a
ts' -> forall k a b (rk :: * -> * -> *).
Ord k =>
(k -> a -> Maybe b)
-> (rk k a -> MinPQueue k b) -> BinomForest rk k a -> MinPQueue k b
mapMaybeF k -> a -> Maybe b
f Succ rk k a -> MinPQueue k b
fCh' BinomForest (Succ rk) k a
ts'
Cons (BinomTree k
k a
a rk k a
ts) BinomForest (Succ rk) k a
ts'
-> k -> a -> MinPQueue k b -> MinPQueue k b -> MinPQueue k b
insF k
k a
a (rk k a -> MinPQueue k b
fCh rk k a
ts) (forall k a b (rk :: * -> * -> *).
Ord k =>
(k -> a -> Maybe b)
-> (rk k a -> MinPQueue k b) -> BinomForest rk k a -> MinPQueue k b
mapMaybeF k -> a -> Maybe b
f Succ rk k a -> MinPQueue k b
fCh' BinomForest (Succ rk) k a
ts')
where insF :: k -> a -> MinPQueue k b -> MinPQueue k b -> MinPQueue k b
insF k
k a
a = forall b a. b -> (a -> b) -> Maybe a -> b
maybe forall a. a -> a
id (forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert k
k) (k -> a -> Maybe b
f k
k a
a) forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: forall k a.
Ord k =>
MinPQueue k a -> MinPQueue k a -> MinPQueue k a
union
fCh' :: Succ rk k a -> MinPQueue k b
fCh' (Succ (BinomTree k
k a
a rk k a
ts) rk k a
tss) =
k -> a -> MinPQueue k b -> MinPQueue k b -> MinPQueue k b
insF k
k a
a (rk k a -> MinPQueue k b
fCh rk k a
ts) (rk k a -> MinPQueue k b
fCh rk k a
tss)
mapEitherF :: Ord k => (k -> a -> Either b c) -> (rk k a -> (MinPQueue k b, MinPQueue k c)) ->
BinomForest rk k a -> (MinPQueue k b, MinPQueue k c)
mapEitherF :: forall k a b c (rk :: * -> * -> *).
Ord k =>
(k -> a -> Either b c)
-> (rk k a -> (MinPQueue k b, MinPQueue k c))
-> BinomForest rk k a
-> (MinPQueue k b, MinPQueue k c)
mapEitherF k -> a -> Either b c
f0 rk k a -> (MinPQueue k b, MinPQueue k c)
fCh BinomForest rk k a
ts0 = case BinomForest rk k a
ts0 of
BinomForest rk k a
Nil -> (forall k a. MinPQueue k a
Empty, forall k a. MinPQueue k a
Empty)
Skip BinomForest (Succ rk) k a
ts' -> forall k a b c (rk :: * -> * -> *).
Ord k =>
(k -> a -> Either b c)
-> (rk k a -> (MinPQueue k b, MinPQueue k c))
-> BinomForest rk k a
-> (MinPQueue k b, MinPQueue k c)
mapEitherF k -> a -> Either b c
f0 Succ rk k a -> (MinPQueue k b, MinPQueue k c)
fCh' BinomForest (Succ rk) k a
ts'
Cons (BinomTree k
k a
a rk k a
ts) BinomForest (Succ rk) k a
ts'
-> k
-> a
-> (MinPQueue k b, MinPQueue k c)
-> (MinPQueue k b, MinPQueue k c)
-> (MinPQueue k b, MinPQueue k c)
insF k
k a
a (rk k a -> (MinPQueue k b, MinPQueue k c)
fCh rk k a
ts) (forall k a b c (rk :: * -> * -> *).
Ord k =>
(k -> a -> Either b c)
-> (rk k a -> (MinPQueue k b, MinPQueue k c))
-> BinomForest rk k a
-> (MinPQueue k b, MinPQueue k c)
mapEitherF k -> a -> Either b c
f0 Succ rk k a -> (MinPQueue k b, MinPQueue k c)
fCh' BinomForest (Succ rk) k a
ts')
where
insF :: k
-> a
-> (MinPQueue k b, MinPQueue k c)
-> (MinPQueue k b, MinPQueue k c)
-> (MinPQueue k b, MinPQueue k c)
insF k
k a
a = forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert k
k) (forall b c a. (b -> c) -> (a, b) -> (a, c)
second' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
insert k
k) (k -> a -> Either b c
f0 k
k a
a) forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.:
(forall k a.
Ord k =>
MinPQueue k a -> MinPQueue k a -> MinPQueue k a
union forall {t} {t} {a} {t} {t} {b}.
(t -> t -> a) -> (t -> t -> b) -> (t, t) -> (t, t) -> (a, b)
`both` forall k a.
Ord k =>
MinPQueue k a -> MinPQueue k a -> MinPQueue k a
union)
fCh' :: Succ rk k a -> (MinPQueue k b, MinPQueue k c)
fCh' (Succ (BinomTree k
k a
a rk k a
ts) rk k a
tss) =
k
-> a
-> (MinPQueue k b, MinPQueue k c)
-> (MinPQueue k b, MinPQueue k c)
-> (MinPQueue k b, MinPQueue k c)
insF k
k a
a (rk k a -> (MinPQueue k b, MinPQueue k c)
fCh rk k a
ts) (rk k a -> (MinPQueue k b, MinPQueue k c)
fCh rk k a
tss)
both :: (t -> t -> a) -> (t -> t -> b) -> (t, t) -> (t, t) -> (a, b)
both t -> t -> a
f t -> t -> b
g (t
x1, t
x2) (t
y1, t
y2) = (t -> t -> a
f t
x1 t
y1, t -> t -> b
g t
x2 t
y2)
foldrWithKeyU :: (k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKeyU :: forall k a b. (k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKeyU k -> a -> b -> b
_ b
z MinPQueue k a
Empty = b
z
foldrWithKeyU k -> a -> b -> b
f b
z (MinPQ Int
_ k
k a
a BinomHeap k a
ts) = k -> a -> b -> b
f k
k a
a (forall k a b (rk :: * -> * -> *).
(k -> a -> b -> b)
-> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldrWithKeyF_ k -> a -> b -> b
f (forall a b. a -> b -> a
const forall a. a -> a
id) BinomHeap k a
ts b
z)
foldMapWithKeyU :: Monoid m => (k -> a -> m) -> MinPQueue k a -> m
foldMapWithKeyU :: forall m k a. Monoid m => (k -> a -> m) -> MinPQueue k a -> m
foldMapWithKeyU k -> a -> m
_ MinPQueue k a
Empty = forall a. Monoid a => a
mempty
foldMapWithKeyU k -> a -> m
f (MinPQ Int
_ k
k a
a BinomHeap k a
ts) = k -> a -> m
f k
k a
a forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> * -> *) m k a.
(IFoldMap t, Monoid m) =>
(k -> a -> m) -> t k a -> m
foldMapWithKey_ k -> a -> m
f BinomHeap k a
ts
foldlWithKeyU :: (b -> k -> a -> b) -> b -> MinPQueue k a -> b
foldlWithKeyU :: forall b k a. (b -> k -> a -> b) -> b -> MinPQueue k a -> b
foldlWithKeyU b -> k -> a -> b
_ b
z MinPQueue k a
Empty = b
z
foldlWithKeyU b -> k -> a -> b
f b
z0 (MinPQ Int
_ k
k0 a
a0 BinomHeap k a
ts) = forall k a b (rk :: * -> * -> *).
(k -> a -> b -> b)
-> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldlWithKeyF_ (\k
k a
a b
z -> b -> k -> a -> b
f b
z k
k a
a) (forall a b. a -> b -> a
const forall a. a -> a
id) BinomHeap k a
ts (b -> k -> a -> b
f b
z0 k
k0 a
a0)
foldlWithKeyU' :: (b -> k -> a -> b) -> b -> MinPQueue k a -> b
foldlWithKeyU' :: forall b k a. (b -> k -> a -> b) -> b -> MinPQueue k a -> b
foldlWithKeyU' b -> k -> a -> b
_ b
z MinPQueue k a
Empty = b
z
foldlWithKeyU' b -> k -> a -> b
f !b
z0 (MinPQ Int
_ k
k0 a
a0 BinomHeap k a
ts) = forall (t :: * -> * -> *) b k a.
IFoldl' t =>
(b -> k -> a -> b) -> b -> t k a -> b
foldlWithKey'_ b -> k -> a -> b
f (b -> k -> a -> b
f b
z0 k
k0 a
a0) BinomHeap k a
ts
map :: (a -> b) -> MinPQueue k a -> MinPQueue k b
map :: forall a b k. (a -> b) -> MinPQueue k a -> MinPQueue k b
map = forall k a b. (k -> a -> b) -> MinPQueue k a -> MinPQueue k b
mapWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const
traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
traverseWithKey :: forall k (f :: * -> *) a b.
(Ord k, Applicative f) =>
(k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
traverseWithKey k -> a -> f b
f MinPQueue k a
q = case forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
minViewWithKey MinPQueue k a
q of
Maybe ((k, a), MinPQueue k a)
Nothing -> forall (f :: * -> *) a. Applicative f => a -> f a
pure forall k a. MinPQueue k a
empty
Just ((k
k, a
a), MinPQueue k a
q') -> forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (forall k a. k -> a -> MinPQueue k a -> MinPQueue k a
insertMin k
k) (k -> a -> f b
f k
k a
a) (forall k (f :: * -> *) a b.
(Ord k, Applicative f) =>
(k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
traverseWithKey k -> a -> f b
f MinPQueue k a
q')
mapMWithKey :: (Ord k, Monad m) => (k -> a -> m b) -> MinPQueue k a -> m (MinPQueue k b)
mapMWithKey :: forall k (m :: * -> *) a b.
(Ord k, Monad m) =>
(k -> a -> m b) -> MinPQueue k a -> m (MinPQueue k b)
mapMWithKey k -> a -> m b
f = MinPQueue k b -> MinPQueue k a -> m (MinPQueue k b)
go forall k a. MinPQueue k a
empty
where
go :: MinPQueue k b -> MinPQueue k a -> m (MinPQueue k b)
go !MinPQueue k b
acc MinPQueue k a
q =
case forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
minViewWithKey MinPQueue k a
q of
Maybe ((k, a), MinPQueue k a)
Nothing -> forall (f :: * -> *) a. Applicative f => a -> f a
pure MinPQueue k b
acc
Just ((k
k, a
a), MinPQueue k a
q') -> do
b
b <- k -> a -> m b
f k
k a
a
let !acc' :: MinPQueue k b
acc' = forall k a. k -> a -> MinPQueue k a -> MinPQueue k a
insertMax' k
k b
b MinPQueue k b
acc
MinPQueue k b -> MinPQueue k a -> m (MinPQueue k b)
go MinPQueue k b
acc' MinPQueue k a
q'
traverseWithKeyU :: Applicative f => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
traverseWithKeyU :: forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
traverseWithKeyU k -> a -> f b
_ MinPQueue k a
Empty = forall (f :: * -> *) a. Applicative f => a -> f a
pure forall k a. MinPQueue k a
Empty
traverseWithKeyU k -> a -> f b
f (MinPQ Int
n k
k a
a BinomHeap k a
ts) = forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (forall k a. Int -> k -> a -> BinomHeap k a -> MinPQueue k a
MinPQ Int
n k
k) (k -> a -> f b
f k
k a
a) (forall (f :: * -> *) k a b (rk :: * -> * -> *).
Applicative f =>
(k -> a -> f b)
-> (rk k a -> f (rk k b))
-> BinomForest rk k a
-> f (BinomForest rk k b)
traverseForest k -> a -> f b
f (forall a b. a -> b -> a
const (forall (f :: * -> *) a. Applicative f => a -> f a
pure forall k a. Zero k a
Zero)) BinomHeap k a
ts)
{-# SPECIALIZE traverseForest :: (k -> a -> Identity b) -> (rk k a -> Identity (rk k b)) -> BinomForest rk k a ->
Identity (BinomForest rk k b) #-}
traverseForest :: (Applicative f) => (k -> a -> f b) -> (rk k a -> f (rk k b)) -> BinomForest rk k a -> f (BinomForest rk k b)
traverseForest :: forall (f :: * -> *) k a b (rk :: * -> * -> *).
Applicative f =>
(k -> a -> f b)
-> (rk k a -> f (rk k b))
-> BinomForest rk k a
-> f (BinomForest rk k b)
traverseForest k -> a -> f b
f rk k a -> f (rk k b)
fCh BinomForest rk k a
ts0 = case BinomForest rk k a
ts0 of
BinomForest rk k a
Nil -> forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
Skip BinomForest (Succ rk) k a
ts' -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) k a b (rk :: * -> * -> *).
Applicative f =>
(k -> a -> f b)
-> (rk k a -> f (rk k b))
-> BinomForest rk k a
-> f (BinomForest rk k b)
traverseForest k -> a -> f b
f Succ rk k a -> f (Succ rk k b)
fCh' BinomForest (Succ rk) k a
ts'
Cons (BinomTree k
k a
a rk k a
ts) BinomForest (Succ rk) k a
tss
-> forall (f :: * -> *) a b c d.
Applicative f =>
(a -> b -> c -> d) -> f a -> f b -> f c -> f d
liftA3 (\b
p rk k b
q -> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k b
p rk k b
q)) (k -> a -> f b
f k
k a
a) (rk k a -> f (rk k b)
fCh rk k a
ts) (forall (f :: * -> *) k a b (rk :: * -> * -> *).
Applicative f =>
(k -> a -> f b)
-> (rk k a -> f (rk k b))
-> BinomForest rk k a
-> f (BinomForest rk k b)
traverseForest k -> a -> f b
f Succ rk k a -> f (Succ rk k b)
fCh' BinomForest (Succ rk) k a
tss)
where
fCh' :: Succ rk k a -> f (Succ rk k b)
fCh' (Succ (BinomTree k
k a
a rk k a
ts) rk k a
tss)
= forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> rk k a -> Succ rk k a
Succ forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree k
k forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> a -> f b
f k
k a
a forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> rk k a -> f (rk k b)
fCh rk k a
ts) forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> rk k a -> f (rk k b)
fCh rk k a
tss
foldrWithKeyF_ :: (k -> a -> b -> b) -> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldrWithKeyF_ :: forall k a b (rk :: * -> * -> *).
(k -> a -> b -> b)
-> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldrWithKeyF_ k -> a -> b -> b
f rk k a -> b -> b
fCh BinomForest rk k a
ts0 b
z0 = case BinomForest rk k a
ts0 of
BinomForest rk k a
Nil -> b
z0
Skip BinomForest (Succ rk) k a
ts' -> forall k a b (rk :: * -> * -> *).
(k -> a -> b -> b)
-> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldrWithKeyF_ k -> a -> b -> b
f Succ rk k a -> b -> b
fCh' BinomForest (Succ rk) k a
ts' b
z0
Cons (BinomTree k
k a
a rk k a
ts) BinomForest (Succ rk) k a
ts'
-> k -> a -> b -> b
f k
k a
a (rk k a -> b -> b
fCh rk k a
ts (forall k a b (rk :: * -> * -> *).
(k -> a -> b -> b)
-> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldrWithKeyF_ k -> a -> b -> b
f Succ rk k a -> b -> b
fCh' BinomForest (Succ rk) k a
ts' b
z0))
where
fCh' :: Succ rk k a -> b -> b
fCh' (Succ (BinomTree k
k a
a rk k a
ts) rk k a
tss) b
z =
k -> a -> b -> b
f k
k a
a (rk k a -> b -> b
fCh rk k a
ts (rk k a -> b -> b
fCh rk k a
tss b
z))
foldlWithKeyF_ :: (k -> a -> b -> b) -> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldlWithKeyF_ :: forall k a b (rk :: * -> * -> *).
(k -> a -> b -> b)
-> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldlWithKeyF_ k -> a -> b -> b
f rk k a -> b -> b
fCh BinomForest rk k a
ts0 = case BinomForest rk k a
ts0 of
BinomForest rk k a
Nil -> forall a. a -> a
id
Skip BinomForest (Succ rk) k a
ts' -> forall k a b (rk :: * -> * -> *).
(k -> a -> b -> b)
-> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldlWithKeyF_ k -> a -> b -> b
f Succ rk k a -> b -> b
fCh' BinomForest (Succ rk) k a
ts'
Cons (BinomTree k
k a
a rk k a
ts) BinomForest (Succ rk) k a
ts'
-> forall k a b (rk :: * -> * -> *).
(k -> a -> b -> b)
-> (rk k a -> b -> b) -> BinomForest rk k a -> b -> b
foldlWithKeyF_ k -> a -> b -> b
f Succ rk k a -> b -> b
fCh' BinomForest (Succ rk) k a
ts' forall b c a. (b -> c) -> (a -> b) -> a -> c
. rk k a -> b -> b
fCh rk k a
ts forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> b -> b
f k
k a
a
where
fCh' :: Succ rk k a -> b -> b
fCh' (Succ (BinomTree k
k a
a rk k a
ts) rk k a
tss) =
rk k a -> b -> b
fCh rk k a
tss forall b c a. (b -> c) -> (a -> b) -> a -> c
. rk k a -> b -> b
fCh rk k a
ts forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> b -> b
f k
k a
a
mapKeysMonoF :: (k -> k') -> (rk k a -> rk k' a) -> BinomForest rk k a -> BinomForest rk k' a
mapKeysMonoF :: forall k k' (rk :: * -> * -> *) a.
(k -> k')
-> (rk k a -> rk k' a) -> BinomForest rk k a -> BinomForest rk k' a
mapKeysMonoF k -> k'
f rk k a -> rk k' a
fCh BinomForest rk k a
ts0 = case BinomForest rk k a
ts0 of
BinomForest rk k a
Nil -> forall (rk :: * -> * -> *) k a. BinomForest rk k a
Nil
Skip BinomForest (Succ rk) k a
ts' -> forall (rk :: * -> * -> *) k a.
BinomForest (Succ rk) k a -> BinomForest rk k a
Skip (forall k k' (rk :: * -> * -> *) a.
(k -> k')
-> (rk k a -> rk k' a) -> BinomForest rk k a -> BinomForest rk k' a
mapKeysMonoF k -> k'
f Succ rk k a -> Succ rk k' a
fCh' BinomForest (Succ rk) k a
ts')
Cons (BinomTree k
k a
a rk k a
ts) BinomForest (Succ rk) k a
ts'
-> forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> BinomForest (Succ rk) k a -> BinomForest rk k a
Cons (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree (k -> k'
f k
k) a
a (rk k a -> rk k' a
fCh rk k a
ts)) (forall k k' (rk :: * -> * -> *) a.
(k -> k')
-> (rk k a -> rk k' a) -> BinomForest rk k a -> BinomForest rk k' a
mapKeysMonoF k -> k'
f Succ rk k a -> Succ rk k' a
fCh' BinomForest (Succ rk) k a
ts')
where
fCh' :: Succ rk k a -> Succ rk k' a
fCh' (Succ (BinomTree k
k a
a rk k a
ts) rk k a
tss) =
forall (rk :: * -> * -> *) k a.
BinomTree rk k a -> rk k a -> Succ rk k a
Succ (forall (rk :: * -> * -> *) k a.
k -> a -> rk k a -> BinomTree rk k a
BinomTree (k -> k'
f k
k) a
a (rk k a -> rk k' a
fCh rk k a
ts)) (rk k a -> rk k' a
fCh rk k a
tss)
seqSpine :: MinPQueue k a -> b -> b
seqSpine :: forall k a b. MinPQueue k a -> b -> b
seqSpine MinPQueue k a
Empty b
z0 = b
z0
seqSpine (MinPQ Int
_ k
_ a
_ BinomHeap k a
ts0) b
z0 = BinomHeap k a
ts0 forall (rk :: * -> * -> *) k a b. BinomForest rk k a -> b -> b
`seqSpineF` b
z0 where
seqSpineF :: BinomForest rk k a -> b -> b
seqSpineF :: forall (rk :: * -> * -> *) k a b. BinomForest rk k a -> b -> b
seqSpineF BinomForest rk k a
ts b
z = case BinomForest rk k a
ts of
BinomForest rk k a
Nil -> b
z
Skip BinomForest (Succ rk) k a
ts' -> forall (rk :: * -> * -> *) k a b. BinomForest rk k a -> b -> b
seqSpineF BinomForest (Succ rk) k a
ts' b
z
Cons BinomTree rk k a
_ BinomForest (Succ rk) k a
ts' -> forall (rk :: * -> * -> *) k a b. BinomForest rk k a -> b -> b
seqSpineF BinomForest (Succ rk) k a
ts' b
z
class NFRank rk where
rnfRk :: (NFData k, NFData a) => rk k a -> ()
instance NFRank Zero where
rnfRk :: forall k a. (NFData k, NFData a) => Zero k a -> ()
rnfRk Zero k a
_ = ()
instance NFRank rk => NFRank (Succ rk) where
rnfRk :: forall k a. (NFData k, NFData a) => Succ rk k a -> ()
rnfRk (Succ BinomTree rk k a
t rk k a
ts) = BinomTree rk k a
t forall a b. NFData a => a -> b -> b
`deepseq` forall (rk :: * -> * -> *) k a.
(NFRank rk, NFData k, NFData a) =>
rk k a -> ()
rnfRk rk k a
ts
instance (NFData k, NFData a, NFRank rk) => NFData (BinomTree rk k a) where
rnf :: BinomTree rk k a -> ()
rnf (BinomTree k
k a
a rk k a
ts) = k
k forall a b. NFData a => a -> b -> b
`deepseq` a
a forall a b. NFData a => a -> b -> b
`deepseq` forall (rk :: * -> * -> *) k a.
(NFRank rk, NFData k, NFData a) =>
rk k a -> ()
rnfRk rk k a
ts
instance (NFData k, NFData a, NFRank rk) => NFData (BinomForest rk k a) where
rnf :: BinomForest rk k a -> ()
rnf BinomForest rk k a
Nil = ()
rnf (Skip BinomForest (Succ rk) k a
tss) = forall a. NFData a => a -> ()
rnf BinomForest (Succ rk) k a
tss
rnf (Cons BinomTree rk k a
t BinomForest (Succ rk) k a
tss) = BinomTree rk k a
t forall a b. NFData a => a -> b -> b
`deepseq` forall a. NFData a => a -> ()
rnf BinomForest (Succ rk) k a
tss
instance (NFData k, NFData a) => NFData (MinPQueue k a) where
rnf :: MinPQueue k a -> ()
rnf MinPQueue k a
Empty = ()
rnf (MinPQ Int
_ k
k a
a BinomHeap k a
ts) = k
k forall a b. NFData a => a -> b -> b
`deepseq` a
a forall a b. NFData a => a -> b -> b
`deepseq` forall a. NFData a => a -> ()
rnf BinomHeap k a
ts
instance Functor (MinPQueue k) where
fmap :: forall a b. (a -> b) -> MinPQueue k a -> MinPQueue k b
fmap = forall a b k. (a -> b) -> MinPQueue k a -> MinPQueue k b
map
instance FunctorWithIndex k (MinPQueue k) where
imap :: forall a b. (k -> a -> b) -> MinPQueue k a -> MinPQueue k b
imap = forall k a b. (k -> a -> b) -> MinPQueue k a -> MinPQueue k b
mapWithKey
instance Ord k => Foldable (MinPQueue k) where
foldr :: forall a b. (a -> b -> b) -> b -> MinPQueue k a -> b
foldr = forall k a b.
Ord k =>
(k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const
foldl :: forall b a. (b -> a -> b) -> b -> MinPQueue k a -> b
foldl b -> a -> b
f = forall k b a.
Ord k =>
(b -> k -> a -> b) -> b -> MinPQueue k a -> b
foldlWithKey (forall a b. a -> b -> a
const forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> a -> b
f)
length :: forall a. MinPQueue k a -> Int
length = forall k a. MinPQueue k a -> Int
size
null :: forall a. MinPQueue k a -> Bool
null = forall k a. MinPQueue k a -> Bool
null
instance Ord k => FoldableWithIndex k (MinPQueue k) where
ifoldr :: forall a b. (k -> a -> b -> b) -> b -> MinPQueue k a -> b
ifoldr = forall k a b.
Ord k =>
(k -> a -> b -> b) -> b -> MinPQueue k a -> b
foldrWithKey
ifoldl :: forall b a. (k -> b -> a -> b) -> b -> MinPQueue k a -> b
ifoldl k -> b -> a -> b
f = forall k b a.
Ord k =>
(b -> k -> a -> b) -> b -> MinPQueue k a -> b
foldlWithKey (forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> b -> a -> b
f)
instance Ord k => Traversable (MinPQueue k) where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
traverse = forall k (f :: * -> *) a b.
(Ord k, Applicative f) =>
(k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
traverseWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> MinPQueue k a -> m (MinPQueue k b)
mapM = forall k (m :: * -> *) a b.
(Ord k, Monad m) =>
(k -> a -> m b) -> MinPQueue k a -> m (MinPQueue k b)
mapMWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const
sequence :: forall (m :: * -> *) a.
Monad m =>
MinPQueue k (m a) -> m (MinPQueue k a)
sequence = forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM forall a. a -> a
id
instance Ord k => TraversableWithIndex k (MinPQueue k) where
itraverse :: forall (f :: * -> *) a b.
Applicative f =>
(k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
itraverse = forall k (f :: * -> *) a b.
(Ord k, Applicative f) =>
(k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
traverseWithKey