module Data.Edison.Coll.LazyPairingHeap (
Heap,
empty,singleton,fromSeq,insert,insertSeq,union,unionSeq,delete,deleteAll,
deleteSeq,null,size,member,count,strict,structuralInvariant,
toSeq, lookup, lookupM, lookupAll, lookupWithDefault, fold, fold',
fold1, fold1', filter, partition, strictWith,
deleteMin,deleteMax,unsafeInsertMin,unsafeInsertMax,unsafeFromOrdSeq,
unsafeAppend,filterLT,filterLE,filterGT,filterGE,partitionLT_GE,
partitionLE_GT,partitionLT_GT,
minView,minElem,maxView,maxElem,foldr,foldr',foldl,foldl',
foldr1,foldr1',foldl1,foldl1',toOrdSeq,
unsafeMapMonotonic,
moduleName
) where
import Prelude hiding (null,foldr,foldl,foldr1,foldl1,lookup,filter)
import qualified Data.Edison.Coll as C ( CollX(..), OrdCollX(..),
Coll(..), OrdColl(..), toOrdList )
import qualified Data.Edison.Seq as S
import Data.Edison.Coll.Defaults
import Data.List (sort)
import Data.Monoid
import Data.Semigroup as SG
import Control.Monad
import qualified Control.Monad.Fail as Fail
import Test.QuickCheck
moduleName :: String
moduleName :: String
moduleName = String
"Data.Edison.Coll.LazyPairingHeap"
data Heap a = E
| H1 a (Heap a)
| H2 a !(Heap a) (Heap a)
structuralInvariant :: Heap a -> Bool
structuralInvariant :: forall a. Heap a -> Bool
structuralInvariant Heap a
E = Bool
True
structuralInvariant (H1 a
_ Heap a
h) = forall a. Heap a -> Bool
structuralInvariant Heap a
h
structuralInvariant (H2 a
_ Heap a
E Heap a
_) = Bool
False
structuralInvariant (H2 a
_ Heap a
l Heap a
r) = forall a. Heap a -> Bool
structuralInvariant Heap a
l Bool -> Bool -> Bool
&& forall a. Heap a -> Bool
structuralInvariant Heap a
r
makeH2 :: a -> Heap a -> Heap a -> Heap a
makeH2 :: forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x Heap a
E Heap a
xs = forall a. a -> Heap a -> Heap a
H1 a
x Heap a
xs
makeH2 a
x Heap a
h Heap a
xs = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
x Heap a
h Heap a
xs
empty :: Heap a
empty :: forall a. Heap a
empty = forall a. Heap a
E
singleton :: a -> Heap a
singleton :: forall a. a -> Heap a
singleton a
x = forall a. a -> Heap a -> Heap a
H1 a
x forall a. Heap a
E
insert :: Ord a => a -> Heap a -> Heap a
insert :: forall a. Ord a => a -> Heap a -> Heap a
insert a
x Heap a
E = forall a. a -> Heap a -> Heap a
H1 a
x forall a. Heap a
E
insert a
x h :: Heap a
h@(H1 a
y Heap a
b)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall a. a -> Heap a -> Heap a
H1 a
x Heap a
h
| Bool
otherwise = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
y (forall a. a -> Heap a -> Heap a
H1 a
x forall a. Heap a
E) Heap a
b
insert a
x h :: Heap a
h@(H2 a
y Heap a
a Heap a
b)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall a. a -> Heap a -> Heap a
H1 a
x Heap a
h
| Bool
otherwise = forall a. a -> Heap a -> Heap a
H1 a
y (forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => a -> Heap a -> Heap a
insert a
x Heap a
a) Heap a
b)
union :: Ord a => Heap a -> Heap a -> Heap a
union :: forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
E Heap a
h = Heap a
h
union hx :: Heap a
hx@(H1 a
_ Heap a
_) Heap a
E = Heap a
hx
union hx :: Heap a
hx@(H1 a
x Heap a
xs) hy :: Heap a
hy@(H1 a
y Heap a
ys)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
x Heap a
hy Heap a
xs
| Bool
otherwise = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
y Heap a
hx Heap a
ys
union hx :: Heap a
hx@(H1 a
x Heap a
xs) hy :: Heap a
hy@(H2 a
y Heap a
a Heap a
ys)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
x Heap a
hy Heap a
xs
| Bool
otherwise = forall a. a -> Heap a -> Heap a
H1 a
y (forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
hx Heap a
a) Heap a
ys)
union hx :: Heap a
hx@(H2 a
_ Heap a
_ Heap a
_) Heap a
E = Heap a
hx
union hx :: Heap a
hx@(H2 a
x Heap a
a Heap a
xs) hy :: Heap a
hy@(H1 a
y Heap a
ys)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall a. a -> Heap a -> Heap a
H1 a
x (forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
hy Heap a
a) Heap a
xs)
| Bool
otherwise = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
y Heap a
hx Heap a
ys
union hx :: Heap a
hx@(H2 a
x Heap a
a Heap a
xs) hy :: Heap a
hy@(H2 a
y Heap a
b Heap a
ys)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall a. a -> Heap a -> Heap a
H1 a
x (forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
hy Heap a
a) Heap a
xs)
| Bool
otherwise = forall a. a -> Heap a -> Heap a
H1 a
y (forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
hx Heap a
b) Heap a
ys)
delete :: Ord a => a -> Heap a -> Heap a
delete :: forall a. Ord a => a -> Heap a -> Heap a
delete a
y Heap a
h = case Heap a -> Maybe (Heap a)
del Heap a
h of Just Heap a
h' -> Heap a
h'
Maybe (Heap a)
Nothing -> Heap a
h
where del :: Heap a -> Maybe (Heap a)
del Heap a
E = forall a. Maybe a
Nothing
del (H1 a
x Heap a
xs) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> case Heap a -> Maybe (Heap a)
del Heap a
xs of
Just Heap a
ys -> forall a. a -> Maybe a
Just (forall a. a -> Heap a -> Heap a
H1 a
x Heap a
ys)
Maybe (Heap a)
Nothing -> forall a. Maybe a
Nothing
Ordering
EQ -> forall a. a -> Maybe a
Just Heap a
xs
Ordering
GT -> forall a. Maybe a
Nothing
del (H2 a
x Heap a
a Heap a
xs) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> case Heap a -> Maybe (Heap a)
del Heap a
a of
Just Heap a
a' -> forall a. a -> Maybe a
Just (forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x Heap a
a' Heap a
xs)
Maybe (Heap a)
Nothing -> case Heap a -> Maybe (Heap a)
del Heap a
xs of
Just Heap a
xs' -> forall a. a -> Maybe a
Just (forall a. a -> Heap a -> Heap a -> Heap a
H2 a
x Heap a
a Heap a
xs')
Maybe (Heap a)
Nothing -> forall a. Maybe a
Nothing
Ordering
EQ -> forall a. a -> Maybe a
Just (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
a Heap a
xs)
Ordering
GT -> forall a. Maybe a
Nothing
deleteAll :: Ord a => a -> Heap a -> Heap a
deleteAll :: forall a. Ord a => a -> Heap a -> Heap a
deleteAll a
_ Heap a
E = forall a. Heap a
E
deleteAll a
y h :: Heap a
h@(H1 a
x Heap a
xs) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> forall a. a -> Heap a -> Heap a
H1 a
x (forall a. Ord a => a -> Heap a -> Heap a
deleteAll a
y Heap a
xs)
Ordering
EQ -> forall a. Ord a => a -> Heap a -> Heap a
deleteAll a
y Heap a
xs
Ordering
GT -> Heap a
h
deleteAll a
y h :: Heap a
h@(H2 a
x Heap a
a Heap a
xs) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x (forall a. Ord a => a -> Heap a -> Heap a
deleteAll a
y Heap a
a) (forall a. Ord a => a -> Heap a -> Heap a
deleteAll a
y Heap a
xs)
Ordering
EQ -> forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => a -> Heap a -> Heap a
deleteAll a
y Heap a
a) (forall a. Ord a => a -> Heap a -> Heap a
deleteAll a
y Heap a
xs)
Ordering
GT -> Heap a
h
deleteSeq :: (Ord a,S.Sequence seq) => seq a -> Heap a -> Heap a
deleteSeq :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Heap a -> Heap a
deleteSeq = forall {a}. Ord a => [a] -> Heap a -> Heap a
delList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => [a] -> [a]
sort forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (s :: * -> *) a. Sequence s => s a -> [a]
S.toList
where delList :: [a] -> Heap a -> Heap a
delList [] Heap a
h = Heap a
h
delList (a
y:[a]
ys) Heap a
h = a -> [a] -> Heap a -> Heap a
del a
y [a]
ys Heap a
h
del :: a -> [a] -> Heap a -> Heap a
del a
_ [a]
_ Heap a
E = forall a. Heap a
E
del a
y [a]
ys h :: Heap a
h@(H1 a
x Heap a
xs) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> forall a. a -> Heap a -> Heap a
H1 a
x (a -> [a] -> Heap a -> Heap a
del a
y [a]
ys Heap a
xs)
Ordering
EQ -> [a] -> Heap a -> Heap a
delList [a]
ys Heap a
xs
Ordering
GT -> [a] -> Heap a -> Heap a
delList [a]
ys Heap a
h
del a
y [a]
ys h :: Heap a
h@(H2 a
x Heap a
a Heap a
xs) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> forall a. a -> Heap a -> Heap a
H1 a
x (a -> [a] -> Heap a -> Heap a
del a
y [a]
ys (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
a Heap a
xs))
Ordering
EQ -> [a] -> Heap a -> Heap a
delList [a]
ys (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
a Heap a
xs)
Ordering
GT -> [a] -> Heap a -> Heap a
delList [a]
ys Heap a
h
null :: Heap a -> Bool
null :: forall a. Heap a -> Bool
null Heap a
E = Bool
True
null Heap a
_ = Bool
False
size :: Heap a -> Int
size :: forall a. Heap a -> Int
size Heap a
E = Int
0
size (H1 a
_ Heap a
xs) = Int
1 forall a. Num a => a -> a -> a
+ forall a. Heap a -> Int
size Heap a
xs
size (H2 a
_ Heap a
h Heap a
xs) = Int
1 forall a. Num a => a -> a -> a
+ forall a. Heap a -> Int
size Heap a
h forall a. Num a => a -> a -> a
+ forall a. Heap a -> Int
size Heap a
xs
member :: Ord a => a -> Heap a -> Bool
member :: forall a. Ord a => a -> Heap a -> Bool
member a
_ Heap a
E = Bool
False
member a
x (H1 a
y Heap a
ys) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> Bool
False
Ordering
EQ -> Bool
True
Ordering
GT -> forall a. Ord a => a -> Heap a -> Bool
member a
x Heap a
ys
member a
x (H2 a
y Heap a
h Heap a
ys) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> Bool
False
Ordering
EQ -> Bool
True
Ordering
GT -> forall a. Ord a => a -> Heap a -> Bool
member a
x Heap a
h Bool -> Bool -> Bool
|| forall a. Ord a => a -> Heap a -> Bool
member a
x Heap a
ys
count :: Ord a => a -> Heap a -> Int
count :: forall a. Ord a => a -> Heap a -> Int
count a
_ Heap a
E = Int
0
count a
x (H1 a
y Heap a
ys) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> Int
0
Ordering
EQ -> Int
1 forall a. Num a => a -> a -> a
+ forall a. Ord a => a -> Heap a -> Int
count a
x Heap a
ys
Ordering
GT -> forall a. Ord a => a -> Heap a -> Int
count a
x Heap a
ys
count a
x (H2 a
y Heap a
h Heap a
ys) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> Int
0
Ordering
EQ -> Int
1 forall a. Num a => a -> a -> a
+ forall a. Ord a => a -> Heap a -> Int
count a
x Heap a
h forall a. Num a => a -> a -> a
+ forall a. Ord a => a -> Heap a -> Int
count a
x Heap a
ys
Ordering
GT -> forall a. Ord a => a -> Heap a -> Int
count a
x Heap a
h forall a. Num a => a -> a -> a
+ forall a. Ord a => a -> Heap a -> Int
count a
x Heap a
ys
deleteMin :: Ord a => Heap a -> Heap a
deleteMin :: forall a. Ord a => Heap a -> Heap a
deleteMin Heap a
E = forall a. Heap a
E
deleteMin (H1 a
_ Heap a
xs) = Heap a
xs
deleteMin (H2 a
_ Heap a
h Heap a
xs) = forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs
unsafeInsertMin :: Ord a => a -> Heap a -> Heap a
unsafeInsertMin :: forall a. Ord a => a -> Heap a -> Heap a
unsafeInsertMin = forall a. a -> Heap a -> Heap a
H1
unsafeInsertMax :: Ord a => a -> Heap a -> Heap a
unsafeInsertMax :: forall a. Ord a => a -> Heap a -> Heap a
unsafeInsertMax a
x Heap a
E = forall a. a -> Heap a -> Heap a
H1 a
x forall a. Heap a
E
unsafeInsertMax a
x (H1 a
y Heap a
ys) = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
y (forall a. a -> Heap a -> Heap a
H1 a
x forall a. Heap a
E) Heap a
ys
unsafeInsertMax a
x (H2 a
y Heap a
h Heap a
ys) = forall a. a -> Heap a -> Heap a
H1 a
y (forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => a -> Heap a -> Heap a
unsafeInsertMax a
x Heap a
h) Heap a
ys)
unsafeAppend :: Ord a => Heap a -> Heap a -> Heap a
unsafeAppend :: forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend Heap a
h Heap a
E = Heap a
h
unsafeAppend Heap a
E Heap a
h = Heap a
h
unsafeAppend (H1 a
x Heap a
xs) Heap a
h = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
x Heap a
h Heap a
xs
unsafeAppend (H2 a
x Heap a
a Heap a
xs) Heap a
h = forall a. a -> Heap a -> Heap a
H1 a
x (forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend Heap a
a Heap a
h) Heap a
xs)
filterLT :: Ord a => a -> Heap a -> Heap a
filterLT :: forall a. Ord a => a -> Heap a -> Heap a
filterLT a
_ Heap a
E = forall a. Heap a
E
filterLT a
y (H1 a
x Heap a
xs)
| a
x forall a. Ord a => a -> a -> Bool
< a
y = forall a. a -> Heap a -> Heap a
H1 a
x (forall a. Ord a => a -> Heap a -> Heap a
filterLT a
y Heap a
xs)
| Bool
otherwise = forall a. Heap a
E
filterLT a
y (H2 a
x Heap a
h Heap a
xs)
| a
x forall a. Ord a => a -> a -> Bool
< a
y = forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x (forall a. Ord a => a -> Heap a -> Heap a
filterLT a
y Heap a
h) (forall a. Ord a => a -> Heap a -> Heap a
filterLT a
y Heap a
xs)
| Bool
otherwise = forall a. Heap a
E
filterLE :: Ord a => a -> Heap a -> Heap a
filterLE :: forall a. Ord a => a -> Heap a -> Heap a
filterLE a
_ Heap a
E = forall a. Heap a
E
filterLE a
y (H1 a
x Heap a
xs)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall a. a -> Heap a -> Heap a
H1 a
x (forall a. Ord a => a -> Heap a -> Heap a
filterLE a
y Heap a
xs)
| Bool
otherwise = forall a. Heap a
E
filterLE a
y (H2 a
x Heap a
h Heap a
xs)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x (forall a. Ord a => a -> Heap a -> Heap a
filterLE a
y Heap a
h) (forall a. Ord a => a -> Heap a -> Heap a
filterLE a
y Heap a
xs)
| Bool
otherwise = forall a. Heap a
E
filterGT :: Ord a => a -> Heap a -> Heap a
filterGT :: forall a. Ord a => a -> Heap a -> Heap a
filterGT a
y Heap a
h = Heap a -> Heap a -> Heap a
fgt Heap a
h forall a. Heap a
E
where fgt :: Heap a -> Heap a -> Heap a
fgt Heap a
E Heap a
rest = Heap a
rest
fgt i :: Heap a
i@(H1 a
x Heap a
xs) Heap a
rest
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
i Heap a
rest
| Bool
otherwise = Heap a -> Heap a -> Heap a
fgt Heap a
xs Heap a
rest
fgt i :: Heap a
i@(H2 a
x Heap a
a Heap a
xs) Heap a
rest
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
i Heap a
rest
| Bool
otherwise = Heap a -> Heap a -> Heap a
fgt Heap a
a (Heap a -> Heap a -> Heap a
fgt Heap a
xs Heap a
rest)
filterGE :: Ord a => a -> Heap a -> Heap a
filterGE :: forall a. Ord a => a -> Heap a -> Heap a
filterGE a
y Heap a
h = Heap a -> Heap a -> Heap a
fge Heap a
h forall a. Heap a
E
where fge :: Heap a -> Heap a -> Heap a
fge Heap a
E Heap a
rest = Heap a
rest
fge i :: Heap a
i@(H1 a
x Heap a
xs) Heap a
rest
| a
x forall a. Ord a => a -> a -> Bool
>= a
y = forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
i Heap a
rest
| Bool
otherwise = Heap a -> Heap a -> Heap a
fge Heap a
xs Heap a
rest
fge i :: Heap a
i@(H2 a
x Heap a
a Heap a
xs) Heap a
rest
| a
x forall a. Ord a => a -> a -> Bool
>= a
y = forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
i Heap a
rest
| Bool
otherwise = Heap a -> Heap a -> Heap a
fge Heap a
a (Heap a -> Heap a -> Heap a
fge Heap a
xs Heap a
rest)
partitionLT_GE :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE :: forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE a
_ Heap a
E = (forall a. Heap a
E,forall a. Heap a
E)
partitionLT_GE a
y h :: Heap a
h@(H1 a
x Heap a
xs)
| a
x forall a. Ord a => a -> a -> Bool
< a
y = let (Heap a
xs',Heap a
xs'') = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE a
y Heap a
xs
in (forall a. a -> Heap a -> Heap a
H1 a
x Heap a
xs',Heap a
xs'')
| Bool
otherwise = (forall a. Heap a
E, Heap a
h)
partitionLT_GE a
y h :: Heap a
h@(H2 a
x Heap a
a Heap a
xs)
| a
x forall a. Ord a => a -> a -> Bool
< a
y = let (Heap a
a',Heap a
a'') = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE a
y Heap a
a
(Heap a
xs',Heap a
xs'') = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE a
y Heap a
xs
in (forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x Heap a
a' Heap a
xs',forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
a'' Heap a
xs'')
| Bool
otherwise = (forall a. Heap a
E, Heap a
h)
partitionLE_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT :: forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
_ Heap a
E = (forall a. Heap a
E,forall a. Heap a
E)
partitionLE_GT a
y h :: Heap a
h@(H1 a
x Heap a
xs)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = let (Heap a
xs',Heap a
xs'') = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
y Heap a
xs
in (forall a. a -> Heap a -> Heap a
H1 a
x Heap a
xs',Heap a
xs'')
| Bool
otherwise = (forall a. Heap a
E, Heap a
h)
partitionLE_GT a
y h :: Heap a
h@(H2 a
x Heap a
a Heap a
xs)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = let (Heap a
a',Heap a
a'') = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
y Heap a
a
(Heap a
xs',Heap a
xs'') = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
y Heap a
xs
in (forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x Heap a
a' Heap a
xs',forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
a'' Heap a
xs'')
| Bool
otherwise = (forall a. Heap a
E, Heap a
h)
partitionLT_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT :: forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
_ Heap a
E = (forall a. Heap a
E,forall a. Heap a
E)
partitionLT_GT a
y h :: Heap a
h@(H1 a
x Heap a
xs) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> let (Heap a
xs',Heap a
xs'') = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
y Heap a
xs
in (forall a. a -> Heap a -> Heap a
H1 a
x Heap a
xs',Heap a
xs'')
Ordering
EQ -> (forall a. Heap a
E, forall a. Ord a => a -> Heap a -> Heap a
filterGT a
y Heap a
xs)
Ordering
GT -> (forall a. Heap a
E, Heap a
h)
partitionLT_GT a
y h :: Heap a
h@(H2 a
x Heap a
a Heap a
xs) =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> let (Heap a
a',Heap a
a'') = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
y Heap a
a
(Heap a
xs',Heap a
xs'') = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
y Heap a
xs
in (forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x Heap a
a' Heap a
xs',forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
a'' Heap a
xs'')
Ordering
EQ -> (forall a. Heap a
E, forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => a -> Heap a -> Heap a
filterGT a
y Heap a
a) (forall a. Ord a => a -> Heap a -> Heap a
filterGT a
y Heap a
xs))
Ordering
GT -> (forall a. Heap a
E, Heap a
h)
toSeq :: S.Sequence seq => Heap a -> seq a
toSeq :: forall (seq :: * -> *) a. Sequence seq => Heap a -> seq a
toSeq Heap a
h = forall {s :: * -> *} {a}. Sequence s => Heap a -> s a -> s a
tol Heap a
h forall (s :: * -> *) a. Sequence s => s a
S.empty
where tol :: Heap a -> s a -> s a
tol Heap a
E s a
rest = s a
rest
tol (H1 a
x Heap a
xs) s a
rest = forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
x (Heap a -> s a -> s a
tol Heap a
xs s a
rest)
tol (H2 a
x Heap a
i Heap a
xs) s a
rest = forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
x forall a b. (a -> b) -> a -> b
$ Heap a -> s a -> s a
tol Heap a
i forall a b. (a -> b) -> a -> b
$ Heap a -> s a -> s a
tol Heap a
xs s a
rest
fold :: (a -> b -> b) -> b -> Heap a -> b
fold :: forall a b. (a -> b -> b) -> b -> Heap a -> b
fold a -> b -> b
_ b
c Heap a
E = b
c
fold a -> b -> b
f b
c (H1 a
x Heap a
xs) = a -> b -> b
f a
x (forall a b. (a -> b -> b) -> b -> Heap a -> b
fold a -> b -> b
f b
c Heap a
xs)
fold a -> b -> b
f b
c (H2 a
x Heap a
h Heap a
xs) = a -> b -> b
f a
x (forall a b. (a -> b -> b) -> b -> Heap a -> b
fold a -> b -> b
f (forall a b. (a -> b -> b) -> b -> Heap a -> b
fold a -> b -> b
f b
c Heap a
xs) Heap a
h)
fold' :: (a -> b -> b) -> b -> Heap a -> b
fold' :: forall a b. (a -> b -> b) -> b -> Heap a -> b
fold' a -> b -> b
_ b
c Heap a
E = b
c
fold' a -> b -> b
f b
c (H1 a
x Heap a
xs) = b
c seq :: forall a b. a -> b -> b
`seq` a -> b -> b
f a
x forall a b. (a -> b) -> a -> b
$! (forall a b. (a -> b -> b) -> b -> Heap a -> b
fold' a -> b -> b
f b
c Heap a
xs)
fold' a -> b -> b
f b
c (H2 a
x Heap a
h Heap a
xs) = b
c seq :: forall a b. a -> b -> b
`seq` a -> b -> b
f a
x forall a b. (a -> b) -> a -> b
$! (forall a b. (a -> b -> b) -> b -> Heap a -> b
fold' a -> b -> b
f (forall a b. (a -> b -> b) -> b -> Heap a -> b
fold' a -> b -> b
f b
c Heap a
xs) Heap a
h)
fold1 :: (a -> a -> a) -> Heap a -> a
fold1 :: forall a. (a -> a -> a) -> Heap a -> a
fold1 a -> a -> a
_ Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.fold1: empty heap"
fold1 a -> a -> a
f (H1 a
x Heap a
xs) = forall a b. (a -> b -> b) -> b -> Heap a -> b
fold a -> a -> a
f a
x Heap a
xs
fold1 a -> a -> a
f (H2 a
x Heap a
h Heap a
xs) = forall a b. (a -> b -> b) -> b -> Heap a -> b
fold a -> a -> a
f (forall a b. (a -> b -> b) -> b -> Heap a -> b
fold a -> a -> a
f a
x Heap a
xs) Heap a
h
fold1' :: (a -> a -> a) -> Heap a -> a
fold1' :: forall a. (a -> a -> a) -> Heap a -> a
fold1' a -> a -> a
_ Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.fold1': empty heap"
fold1' a -> a -> a
f (H1 a
x Heap a
xs) = forall a b. (a -> b -> b) -> b -> Heap a -> b
fold' a -> a -> a
f a
x Heap a
xs
fold1' a -> a -> a
f (H2 a
x Heap a
h Heap a
xs) = forall a b. (a -> b -> b) -> b -> Heap a -> b
fold' a -> a -> a
f (forall a b. (a -> b -> b) -> b -> Heap a -> b
fold' a -> a -> a
f a
x Heap a
xs) Heap a
h
filter :: Ord a => (a -> Bool) -> Heap a -> Heap a
filter :: forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
_ Heap a
E = forall a. Heap a
E
filter a -> Bool
p (H1 a
x Heap a
xs) = if a -> Bool
p a
x then forall a. a -> Heap a -> Heap a
H1 a
x (forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
xs) else forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
xs
filter a -> Bool
p (H2 a
x Heap a
h Heap a
xs) =
if a -> Bool
p a
x then forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x (forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
h) (forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
xs)
else forall a. Ord a => Heap a -> Heap a -> Heap a
union (forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
h) (forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
xs)
partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition :: forall a. Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition a -> Bool
_ Heap a
E = (forall a. Heap a
E, forall a. Heap a
E)
partition a -> Bool
p (H1 a
x Heap a
xs) = if a -> Bool
p a
x then (forall a. a -> Heap a -> Heap a
H1 a
x Heap a
xs',Heap a
xs'') else (Heap a
xs',forall a. a -> Heap a -> Heap a
H1 a
x Heap a
xs'')
where (Heap a
xs',Heap a
xs'') = forall a. Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition a -> Bool
p Heap a
xs
partition a -> Bool
p (H2 a
x Heap a
h Heap a
xs) =
if a -> Bool
p a
x then (forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x Heap a
h' Heap a
xs', forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h'' Heap a
xs'')
else (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h' Heap a
xs', forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x Heap a
h'' Heap a
xs'')
where (Heap a
h',Heap a
h'') = forall a. Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition a -> Bool
p Heap a
h
(Heap a
xs',Heap a
xs'') = forall a. Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition a -> Bool
p Heap a
xs
lookupAll :: (Ord a,S.Sequence seq) => a -> Heap a -> seq a
lookupAll :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
a -> Heap a -> seq a
lookupAll a
y Heap a
h = forall {s :: * -> *}. Sequence s => Heap a -> s a -> s a
look Heap a
h forall (s :: * -> *) a. Sequence s => s a
S.empty
where look :: Heap a -> s a -> s a
look Heap a
E s a
rest = s a
rest
look (H1 a
x Heap a
xs) s a
rest =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> Heap a -> s a -> s a
look Heap a
xs s a
rest
Ordering
EQ -> forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
x (Heap a -> s a -> s a
look Heap a
xs s a
rest)
Ordering
GT -> s a
rest
look (H2 a
x Heap a
i Heap a
xs) s a
rest =
case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
Ordering
LT -> Heap a -> s a -> s a
look Heap a
i forall a b. (a -> b) -> a -> b
$ Heap a -> s a -> s a
look Heap a
xs s a
rest
Ordering
EQ -> forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
x forall a b. (a -> b) -> a -> b
$ Heap a -> s a -> s a
look Heap a
i forall a b. (a -> b) -> a -> b
$ Heap a -> s a -> s a
look Heap a
xs s a
rest
Ordering
GT -> s a
rest
minView :: (Ord a, Fail.MonadFail m) => Heap a -> m (a, Heap a)
minView :: forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
minView Heap a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"LazyPairingHeap.minView: empty heap"
minView (H1 a
x Heap a
xs) = forall (m :: * -> *) a. Monad m => a -> m a
return (a
x,Heap a
xs)
minView (H2 a
x Heap a
h Heap a
xs) = forall (m :: * -> *) a. Monad m => a -> m a
return (a
x,forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs)
minElem :: Heap a -> a
minElem :: forall a. Heap a -> a
minElem Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.minElem: empty heap"
minElem (H1 a
x Heap a
_) = a
x
minElem (H2 a
x Heap a
_ Heap a
_) = a
x
maxView :: (Ord a, Fail.MonadFail m) => Heap a -> m (a, Heap a)
maxView :: forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
maxView Heap a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"LazyPairingHeap.maxView: empty heap"
maxView Heap a
xs = forall (m :: * -> *) a. Monad m => a -> m a
return (a
y,Heap a
xs')
where (Heap a
xs', a
y) = forall a. Ord a => Heap a -> (Heap a, a)
maxView' Heap a
xs
maxView' :: (Ord a) => Heap a -> (Heap a, a)
maxView' :: forall a. Ord a => Heap a -> (Heap a, a)
maxView' (H1 a
x Heap a
E) = (forall a. Heap a
E, a
x)
maxView' (H1 a
x Heap a
xs) = (forall a. a -> Heap a -> Heap a
H1 a
x Heap a
xs', a
y)
where (Heap a
xs', a
y) = forall a. Ord a => Heap a -> (Heap a, a)
maxView' Heap a
xs
maxView' (H2 a
x Heap a
a Heap a
E) = (forall a. a -> Heap a -> Heap a
H1 a
x Heap a
a', a
y)
where (Heap a
a', a
y) = forall a. Ord a => Heap a -> (Heap a, a)
maxView' Heap a
a
maxView' (H2 a
x Heap a
a Heap a
xs) =
if a
y forall a. Ord a => a -> a -> Bool
> a
z then (forall a. a -> Heap a -> Heap a -> Heap a
makeH2 a
x Heap a
a' Heap a
xs, a
y) else (forall a. a -> Heap a -> Heap a -> Heap a
H2 a
x Heap a
a Heap a
xs', a
z)
where (Heap a
a', a
y) = forall a. Ord a => Heap a -> (Heap a, a)
maxView' Heap a
a
(Heap a
xs', a
z) = forall a. Ord a => Heap a -> (Heap a, a)
maxView' Heap a
xs
maxView' Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.maxView': bug!"
maxElem :: Ord a => Heap a -> a
maxElem :: forall a. Ord a => Heap a -> a
maxElem Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.maxElem: empty heap"
maxElem (H1 a
x Heap a
E) = a
x
maxElem (H1 a
_ Heap a
xs) = forall a. Ord a => Heap a -> a
maxElem Heap a
xs
maxElem (H2 a
_ Heap a
h Heap a
E) = forall a. Ord a => Heap a -> a
maxElem Heap a
h
maxElem (H2 a
_ Heap a
h Heap a
xs) = forall a. Ord a => a -> a -> a
max (forall a. Ord a => Heap a -> a
maxElem Heap a
h) (forall a. Ord a => Heap a -> a
maxElem Heap a
xs)
foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr :: forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr a -> b -> b
_ b
c Heap a
E = b
c
foldr a -> b -> b
f b
c (H1 a
x Heap a
xs) = a -> b -> b
f a
x (forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr a -> b -> b
f b
c Heap a
xs)
foldr a -> b -> b
f b
c (H2 a
x Heap a
h Heap a
xs) = a -> b -> b
f a
x (forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr a -> b -> b
f b
c (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs))
foldr' :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' :: forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' a -> b -> b
_ b
c Heap a
E = b
c
foldr' a -> b -> b
f b
c (H1 a
x Heap a
xs) = b
c seq :: forall a b. a -> b -> b
`seq` a -> b -> b
f a
x forall a b. (a -> b) -> a -> b
$! (forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' a -> b -> b
f b
c Heap a
xs)
foldr' a -> b -> b
f b
c (H2 a
x Heap a
h Heap a
xs) = b
c seq :: forall a b. a -> b -> b
`seq` a -> b -> b
f a
x forall a b. (a -> b) -> a -> b
$! (forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' a -> b -> b
f b
c (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs))
foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl :: forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl b -> a -> b
_ b
c Heap a
E = b
c
foldl b -> a -> b
f b
c (H1 a
x Heap a
xs) = forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl b -> a -> b
f (b -> a -> b
f b
c a
x) Heap a
xs
foldl b -> a -> b
f b
c (H2 a
x Heap a
h Heap a
xs) = forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl b -> a -> b
f (b -> a -> b
f b
c a
x) (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs)
foldl' :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' :: forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' b -> a -> b
_ b
c Heap a
E = b
c
foldl' b -> a -> b
f b
c (H1 a
x Heap a
xs) = b
c seq :: forall a b. a -> b -> b
`seq` forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' b -> a -> b
f (b -> a -> b
f b
c a
x) Heap a
xs
foldl' b -> a -> b
f b
c (H2 a
x Heap a
h Heap a
xs) = b
c seq :: forall a b. a -> b -> b
`seq` forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' b -> a -> b
f (b -> a -> b
f b
c a
x) (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs)
foldr1 :: Ord a => (a -> a -> a) -> Heap a -> a
foldr1 :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1 a -> a -> a
_ Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.foldr1: empty heap"
foldr1 a -> a -> a
_ (H1 a
x Heap a
E) = a
x
foldr1 a -> a -> a
f (H1 a
x Heap a
xs) = a -> a -> a
f a
x (forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1 a -> a -> a
f Heap a
xs)
foldr1 a -> a -> a
f (H2 a
x Heap a
h Heap a
xs) = a -> a -> a
f a
x (forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1 a -> a -> a
f (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs))
foldr1' :: Ord a => (a -> a -> a) -> Heap a -> a
foldr1' :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1' a -> a -> a
_ Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.foldr1': empty heap"
foldr1' a -> a -> a
_ (H1 a
x Heap a
E) = a
x
foldr1' a -> a -> a
f (H1 a
x Heap a
xs) = a -> a -> a
f a
x forall a b. (a -> b) -> a -> b
$! (forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1' a -> a -> a
f Heap a
xs)
foldr1' a -> a -> a
f (H2 a
x Heap a
h Heap a
xs) = a -> a -> a
f a
x forall a b. (a -> b) -> a -> b
$! (forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1' a -> a -> a
f (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs))
foldl1 :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1 :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldl1 a -> a -> a
_ Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.foldl1: empty heap"
foldl1 a -> a -> a
f (H1 a
x Heap a
xs) = forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl a -> a -> a
f a
x Heap a
xs
foldl1 a -> a -> a
f (H2 a
x Heap a
h Heap a
xs) = forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl a -> a -> a
f a
x (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs)
foldl1' :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1' :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldl1' a -> a -> a
_ Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.foldl1': empty heap"
foldl1' a -> a -> a
f (H1 a
x Heap a
xs) = forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' a -> a -> a
f a
x Heap a
xs
foldl1' a -> a -> a
f (H2 a
x Heap a
h Heap a
xs) = forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' a -> a -> a
f a
x (forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
h Heap a
xs)
unsafeMapMonotonic :: (Ord a,Ord b) => (a -> b) -> Heap a -> Heap b
unsafeMapMonotonic :: forall a b. (Ord a, Ord b) => (a -> b) -> Heap a -> Heap b
unsafeMapMonotonic = forall {t} {a}. (t -> a) -> Heap t -> Heap a
mapm
where mapm :: (t -> a) -> Heap t -> Heap a
mapm t -> a
_ Heap t
E = forall a. Heap a
E
mapm t -> a
f (H1 t
x Heap t
xs) = forall a. a -> Heap a -> Heap a
H1 (t -> a
f t
x) ((t -> a) -> Heap t -> Heap a
mapm t -> a
f Heap t
xs)
mapm t -> a
f (H2 t
x Heap t
h Heap t
xs) = forall a. a -> Heap a -> Heap a -> Heap a
H2 (t -> a
f t
x) ((t -> a) -> Heap t -> Heap a
mapm t -> a
f Heap t
h) ((t -> a) -> Heap t -> Heap a
mapm t -> a
f Heap t
xs)
strict :: Heap a -> Heap a
strict :: forall a. Heap a -> Heap a
strict h :: Heap a
h@Heap a
E = Heap a
h
strict h :: Heap a
h@(H1 a
_ Heap a
xs) = forall a. Heap a -> Heap a
strict Heap a
xs seq :: forall a b. a -> b -> b
`seq` Heap a
h
strict h :: Heap a
h@(H2 a
_ Heap a
h' Heap a
xs) = forall a. Heap a -> Heap a
strict Heap a
h' seq :: forall a b. a -> b -> b
`seq` forall a. Heap a -> Heap a
strict Heap a
xs seq :: forall a b. a -> b -> b
`seq` Heap a
h
strictWith :: (a -> b) -> Heap a -> Heap a
strictWith :: forall a b. (a -> b) -> Heap a -> Heap a
strictWith a -> b
_ h :: Heap a
h@Heap a
E = Heap a
h
strictWith a -> b
f h :: Heap a
h@(H1 a
x Heap a
xs) = a -> b
f a
x seq :: forall a b. a -> b -> b
`seq` forall a b. (a -> b) -> Heap a -> Heap a
strictWith a -> b
f Heap a
xs seq :: forall a b. a -> b -> b
`seq` Heap a
h
strictWith a -> b
f h :: Heap a
h@(H2 a
x Heap a
h' Heap a
xs) = a -> b
f a
x seq :: forall a b. a -> b -> b
`seq` forall a b. (a -> b) -> Heap a -> Heap a
strictWith a -> b
f Heap a
h' seq :: forall a b. a -> b -> b
`seq` forall a b. (a -> b) -> Heap a -> Heap a
strictWith a -> b
f Heap a
xs seq :: forall a b. a -> b -> b
`seq` Heap a
h
fromSeq :: (Ord a,S.Sequence seq) => seq a -> Heap a
fromSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Heap a
fromSeq = forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
fromSeqUsingFoldr
insertSeq :: (Ord a,S.Sequence seq) => seq a -> Heap a -> Heap a
insertSeq :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Heap a -> Heap a
insertSeq = forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
insertSeqUsingFoldr
unionSeq :: (Ord a,S.Sequence seq) => seq (Heap a) -> Heap a
unionSeq :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq (Heap a) -> Heap a
unionSeq = forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingFoldl
unsafeFromOrdSeq :: (Ord a,S.Sequence seq) => seq a -> Heap a
unsafeFromOrdSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Heap a
unsafeFromOrdSeq = forall c a (seq :: * -> *).
(OrdCollX c a, Sequence seq) =>
seq a -> c
unsafeFromOrdSeqUsingUnsafeInsertMin
deleteMax :: Ord a => Heap a -> Heap a
deleteMax :: forall a. Ord a => Heap a -> Heap a
deleteMax = forall c a. OrdColl c a => c -> c
deleteMaxUsingMaxView
lookup :: Ord a => a -> Heap a -> a
lookup :: forall a. Ord a => a -> Heap a -> a
lookup = forall c a. Coll c a => a -> c -> a
lookupUsingLookupAll
lookupM :: (Ord a, Fail.MonadFail m) => a -> Heap a -> m a
lookupM :: forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Heap a -> m a
lookupM = forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
lookupMUsingLookupAll
lookupWithDefault :: Ord a => a -> a -> Heap a -> a
lookupWithDefault :: forall a. Ord a => a -> a -> Heap a -> a
lookupWithDefault = forall c a. Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupAll
toOrdSeq :: (Ord a,S.Sequence seq) => Heap a -> seq a
toOrdSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => Heap a -> seq a
toOrdSeq = forall c a (seq :: * -> *).
(OrdColl c a, Sequence seq) =>
c -> seq a
toOrdSeqUsingFoldr
instance Ord a => C.CollX (Heap a) a where
{singleton :: a -> Heap a
singleton = forall a. a -> Heap a
singleton; fromSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Heap a
fromSeq = forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Heap a
fromSeq; insert :: a -> Heap a -> Heap a
insert = forall a. Ord a => a -> Heap a -> Heap a
insert;
insertSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Heap a -> Heap a
insertSeq = forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Heap a -> Heap a
insertSeq; unionSeq :: forall (seq :: * -> *). Sequence seq => seq (Heap a) -> Heap a
unionSeq = forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq (Heap a) -> Heap a
unionSeq;
delete :: a -> Heap a -> Heap a
delete = forall a. Ord a => a -> Heap a -> Heap a
delete; deleteAll :: a -> Heap a -> Heap a
deleteAll = forall a. Ord a => a -> Heap a -> Heap a
deleteAll; deleteSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Heap a -> Heap a
deleteSeq = forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Heap a -> Heap a
deleteSeq;
null :: Heap a -> Bool
null = forall a. Heap a -> Bool
null; size :: Heap a -> Int
size = forall a. Heap a -> Int
size; member :: a -> Heap a -> Bool
member = forall a. Ord a => a -> Heap a -> Bool
member; count :: a -> Heap a -> Int
count = forall a. Ord a => a -> Heap a -> Int
count;
strict :: Heap a -> Heap a
strict = forall a. Heap a -> Heap a
strict;
structuralInvariant :: Heap a -> Bool
structuralInvariant = forall a. Heap a -> Bool
structuralInvariant; instanceName :: Heap a -> String
instanceName Heap a
_ = String
moduleName}
instance Ord a => C.OrdCollX (Heap a) a where
{deleteMin :: Heap a -> Heap a
deleteMin = forall a. Ord a => Heap a -> Heap a
deleteMin; deleteMax :: Heap a -> Heap a
deleteMax = forall a. Ord a => Heap a -> Heap a
deleteMax;
unsafeInsertMin :: a -> Heap a -> Heap a
unsafeInsertMin = forall a. Ord a => a -> Heap a -> Heap a
unsafeInsertMin; unsafeInsertMax :: a -> Heap a -> Heap a
unsafeInsertMax = forall a. Ord a => a -> Heap a -> Heap a
unsafeInsertMax;
unsafeFromOrdSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Heap a
unsafeFromOrdSeq = forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Heap a
unsafeFromOrdSeq; unsafeAppend :: Heap a -> Heap a -> Heap a
unsafeAppend = forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend;
filterLT :: a -> Heap a -> Heap a
filterLT = forall a. Ord a => a -> Heap a -> Heap a
filterLT; filterLE :: a -> Heap a -> Heap a
filterLE = forall a. Ord a => a -> Heap a -> Heap a
filterLE; filterGT :: a -> Heap a -> Heap a
filterGT = forall a. Ord a => a -> Heap a -> Heap a
filterGT;
filterGE :: a -> Heap a -> Heap a
filterGE = forall a. Ord a => a -> Heap a -> Heap a
filterGE; partitionLT_GE :: a -> Heap a -> (Heap a, Heap a)
partitionLT_GE = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE;
partitionLE_GT :: a -> Heap a -> (Heap a, Heap a)
partitionLE_GT = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT; partitionLT_GT :: a -> Heap a -> (Heap a, Heap a)
partitionLT_GT = forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT}
instance Ord a => C.Coll (Heap a) a where
{toSeq :: forall (seq :: * -> *). Sequence seq => Heap a -> seq a
toSeq = forall (seq :: * -> *) a. Sequence seq => Heap a -> seq a
toSeq; lookup :: a -> Heap a -> a
lookup = forall a. Ord a => a -> Heap a -> a
lookup; lookupM :: forall (m :: * -> *). MonadFail m => a -> Heap a -> m a
lookupM = forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Heap a -> m a
lookupM;
lookupAll :: forall (seq :: * -> *). Sequence seq => a -> Heap a -> seq a
lookupAll = forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
a -> Heap a -> seq a
lookupAll; lookupWithDefault :: a -> a -> Heap a -> a
lookupWithDefault = forall a. Ord a => a -> a -> Heap a -> a
lookupWithDefault;
fold :: forall b. (a -> b -> b) -> b -> Heap a -> b
fold = forall a b. (a -> b -> b) -> b -> Heap a -> b
fold; fold' :: forall b. (a -> b -> b) -> b -> Heap a -> b
fold' = forall a b. (a -> b -> b) -> b -> Heap a -> b
fold'; fold1 :: (a -> a -> a) -> Heap a -> a
fold1 = forall a. (a -> a -> a) -> Heap a -> a
fold1; fold1' :: (a -> a -> a) -> Heap a -> a
fold1' = forall a. (a -> a -> a) -> Heap a -> a
fold1';
filter :: (a -> Bool) -> Heap a -> Heap a
filter = forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter; partition :: (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition = forall a. Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition; strictWith :: forall b. (a -> b) -> Heap a -> Heap a
strictWith = forall a b. (a -> b) -> Heap a -> Heap a
strictWith}
instance Ord a => C.OrdColl (Heap a) a where
{minView :: forall (m :: * -> *). MonadFail m => Heap a -> m (a, Heap a)
minView = forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
minView; minElem :: Heap a -> a
minElem = forall a. Heap a -> a
minElem; maxView :: forall (m :: * -> *). MonadFail m => Heap a -> m (a, Heap a)
maxView = forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
maxView;
maxElem :: Heap a -> a
maxElem = forall a. Ord a => Heap a -> a
maxElem; foldr :: forall b. (a -> b -> b) -> b -> Heap a -> b
foldr = forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr; foldr' :: forall b. (a -> b -> b) -> b -> Heap a -> b
foldr' = forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr';
foldl :: forall b. (b -> a -> b) -> b -> Heap a -> b
foldl = forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl; foldl' :: forall b. (b -> a -> b) -> b -> Heap a -> b
foldl' = forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl'; foldr1 :: (a -> a -> a) -> Heap a -> a
foldr1 = forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1;
foldr1' :: (a -> a -> a) -> Heap a -> a
foldr1' = forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1'; foldl1 :: (a -> a -> a) -> Heap a -> a
foldl1 = forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldl1; foldl1' :: (a -> a -> a) -> Heap a -> a
foldl1' = forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldl1';
toOrdSeq :: forall (seq :: * -> *). Sequence seq => Heap a -> seq a
toOrdSeq = forall a (seq :: * -> *). (Ord a, Sequence seq) => Heap a -> seq a
toOrdSeq; unsafeMapMonotonic :: (a -> a) -> Heap a -> Heap a
unsafeMapMonotonic = forall a b. (Ord a, Ord b) => (a -> b) -> Heap a -> Heap b
unsafeMapMonotonic}
instance Ord a => Eq (Heap a) where
Heap a
xs == :: Heap a -> Heap a -> Bool
== Heap a
ys = forall c a. OrdColl c a => c -> [a]
C.toOrdList Heap a
xs forall a. Eq a => a -> a -> Bool
== forall c a. OrdColl c a => c -> [a]
C.toOrdList Heap a
ys
instance (Ord a, Show a) => Show (Heap a) where
showsPrec :: Int -> Heap a -> ShowS
showsPrec = forall c a. (Coll c a, Show a) => Int -> c -> ShowS
showsPrecUsingToList
instance (Ord a, Read a) => Read (Heap a) where
readsPrec :: Int -> ReadS (Heap a)
readsPrec = forall c a. (Coll c a, Read a) => Int -> ReadS c
readsPrecUsingFromList
instance (Ord a, Arbitrary a) => Arbitrary (Heap a) where
arbitrary :: Gen (Heap a)
arbitrary = forall a. (Int -> Gen a) -> Gen a
sized (\Int
n -> forall {t} {a}.
(Arbitrary a, Integral t, Ord a) =>
t -> Gen (Heap a)
arbTree Int
n)
where arbTree :: t -> Gen (Heap a)
arbTree t
0 = forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Heap a
E
arbTree t
n =
forall a. [(Int, Gen a)] -> Gen a
frequency [(Int
1, forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Heap a
E),
(Int
2, forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 forall a. Ord a => a -> Heap a -> Heap a
sift1 forall a. Arbitrary a => Gen a
arbitrary (t -> Gen (Heap a)
arbTree (t
n forall a. Num a => a -> a -> a
- t
1))),
(Int
3, forall (m :: * -> *) a1 a2 a3 r.
Monad m =>
(a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
liftM3 forall {a}. Ord a => a -> Heap a -> Heap a -> Heap a
sift forall a. Arbitrary a => Gen a
arbitrary (t -> Gen (Heap a)
arbTree (t
n forall a. Integral a => a -> a -> a
`div` t
4))
(t -> Gen (Heap a)
arbTree (t
n forall a. Integral a => a -> a -> a
`div` t
2)))]
sift :: a -> Heap a -> Heap a -> Heap a
sift a
x Heap a
E Heap a
a = a -> Heap a -> Heap a
sift1 a
x Heap a
a
sift a
x Heap a
a Heap a
E = let H1 a
x' Heap a
a' = a -> Heap a -> Heap a
sift1 a
x Heap a
a in forall a. a -> Heap a -> Heap a -> Heap a
H2 a
x' Heap a
a' forall a. Heap a
E
sift a
x Heap a
a Heap a
b
| a
x forall a. Ord a => a -> a -> Bool
<= a
ma Bool -> Bool -> Bool
&& a
x forall a. Ord a => a -> a -> Bool
<= a
mb = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
x Heap a
a Heap a
b
| a
ma forall a. Ord a => a -> a -> Bool
< a
x Bool -> Bool -> Bool
&& a
ma forall a. Ord a => a -> a -> Bool
<= a
mb = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
ma (a -> Heap a -> Heap a
siftInto a
x Heap a
a) Heap a
b
| Bool
otherwise = forall a. a -> Heap a -> Heap a -> Heap a
H2 a
mb Heap a
a (a -> Heap a -> Heap a
siftInto a
x Heap a
b)
where ma :: a
ma = forall a. Heap a -> a
minElem Heap a
a
mb :: a
mb = forall a. Heap a -> a
minElem Heap a
b
sift1 :: a -> Heap a -> Heap a
sift1 a
x Heap a
E = forall a. a -> Heap a -> Heap a
H1 a
x forall a. Heap a
E
sift1 a
x Heap a
a
| a
x forall a. Ord a => a -> a -> Bool
<= a
ma = forall a. a -> Heap a -> Heap a
H1 a
x Heap a
a
| Bool
otherwise = forall a. a -> Heap a -> Heap a
H1 a
ma (a -> Heap a -> Heap a
siftInto a
x Heap a
a)
where ma :: a
ma = forall a. Heap a -> a
minElem Heap a
a
siftInto :: a -> Heap a -> Heap a
siftInto a
x (H1 a
_ Heap a
a) = a -> Heap a -> Heap a
sift1 a
x Heap a
a
siftInto a
x (H2 a
_ Heap a
a Heap a
b) = a -> Heap a -> Heap a -> Heap a
sift a
x Heap a
a Heap a
b
siftInto a
_ Heap a
E = forall a. HasCallStack => String -> a
error String
"LazyPairingHeap.arbitrary: bug!"
instance (Ord a, CoArbitrary a) => CoArbitrary (Heap a) where
coarbitrary :: forall b. Heap a -> Gen b -> Gen b
coarbitrary Heap a
E = forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
coarbitrary (H1 a
x Heap a
a) = forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
1 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary Heap a
a
coarbitrary (H2 a
x Heap a
a Heap a
b) =
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
2 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary Heap a
a forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary Heap a
b
instance (Ord a) => Semigroup (Heap a) where
<> :: Heap a -> Heap a -> Heap a
(<>) = forall a. Ord a => Heap a -> Heap a -> Heap a
union
instance (Ord a) => Monoid (Heap a) where
mempty :: Heap a
mempty = forall a. Heap a
empty
mappend :: Heap a -> Heap a -> Heap a
mappend = forall a. Semigroup a => a -> a -> a
(SG.<>)
mconcat :: [Heap a] -> Heap a
mconcat = forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq (Heap a) -> Heap a
unionSeq
instance (Ord a) => Ord (Heap a) where
compare :: Heap a -> Heap a -> Ordering
compare = forall c a. OrdColl c a => c -> c -> Ordering
compareUsingToOrdList