module Data.Edison.Coll.MinHeap (
Min,
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,
toColl,fromColl,
moduleName
) where
import Prelude hiding (null,foldr,foldl,foldr1,foldl1,lookup,filter)
import qualified Data.Edison.Coll as C
import qualified Data.Edison.Seq as S
import Data.Edison.Coll.Defaults
import Data.Edison.Seq.Defaults (tokenMatch,maybeParens)
import Data.Monoid
import qualified Data.Semigroup as SG
import Control.Monad
import qualified Control.Monad.Fail as Fail
import Test.QuickCheck
data Min h a = E | M a h deriving (Min h a -> Min h a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall h a. (Eq a, Eq h) => Min h a -> Min h a -> Bool
/= :: Min h a -> Min h a -> Bool
$c/= :: forall h a. (Eq a, Eq h) => Min h a -> Min h a -> Bool
== :: Min h a -> Min h a -> Bool
$c== :: forall h a. (Eq a, Eq h) => Min h a -> Min h a -> Bool
Eq)
moduleName :: String
moduleName :: String
moduleName = String
"Data.Edison.Coll.MinHeap"
structuralInvariant :: (Ord a,C.OrdColl h a) => Min h a -> Bool
structuralInvariant :: forall a h. (Ord a, OrdColl h a) => Min h a -> Bool
structuralInvariant Min h a
E = Bool
True
structuralInvariant (M a
x h
h) = if forall c a. CollX c a => c -> Bool
C.null h
h then Bool
True else a
x forall a. Ord a => a -> a -> Bool
<= forall c a. OrdColl c a => c -> a
C.minElem h
h
empty :: Min h a
singleton :: (C.CollX h a,Ord a) => a -> Min h a
fromSeq :: (C.OrdColl h a,Ord a,S.Sequence s) => s a -> Min h a
insert :: (C.OrdCollX h a,Ord a) => a -> Min h a -> Min h a
insertSeq :: (C.OrdColl h a,Ord a,S.Sequence s) => s a -> Min h a -> Min h a
union :: (C.OrdCollX h a,Ord a) => Min h a -> Min h a -> Min h a
unionSeq :: (C.OrdColl h a,Ord a,S.Sequence s) => s (Min h a) -> Min h a
delete :: (C.OrdColl h a,Ord a) => a -> Min h a -> Min h a
deleteAll :: (C.OrdColl h a,Ord a) => a -> Min h a -> Min h a
deleteSeq :: (C.OrdColl h a,Ord a,S.Sequence s) => s a -> Min h a -> Min h a
null :: Min h a -> Bool
size :: C.CollX h a => Min h a -> Int
member :: (C.CollX h a,Ord a) => a -> Min h a -> Bool
count :: (C.CollX h a,Ord a) => a -> Min h a -> Int
strict :: (C.CollX h a,Ord a) => Min h a -> Min h a
toSeq :: (C.Coll h a,S.Sequence s) => Min h a -> s a
lookup :: (C.Coll h a,Ord a) => a -> Min h a -> a
lookupM :: (C.Coll h a, Ord a, Fail.MonadFail m) => a -> Min h a -> m a
lookupAll :: (C.Coll h a,Ord a,S.Sequence s) => a -> Min h a -> s a
lookupWithDefault :: (C.Coll h a,Ord a) => a -> a -> Min h a -> a
fold :: (C.Coll h a) => (a -> b -> b) -> b -> Min h a -> b
fold1 :: (C.Coll h a) => (a -> a -> a) -> Min h a -> a
fold' :: (C.Coll h a) => (a -> b -> b) -> b -> Min h a -> b
fold1' :: (C.Coll h a) => (a -> a -> a) -> Min h a -> a
filter :: (C.OrdColl h a) => (a -> Bool) -> Min h a -> Min h a
partition :: (C.OrdColl h a) => (a -> Bool) -> Min h a -> (Min h a, Min h a)
strictWith :: (C.OrdColl h a) => (a -> b) -> Min h a -> Min h a
deleteMin :: (C.OrdColl h a,Ord a) => Min h a -> Min h a
deleteMax :: (C.OrdCollX h a,Ord a) => Min h a -> Min h a
unsafeInsertMin :: (C.OrdCollX h a,Ord a) => a -> Min h a -> Min h a
unsafeInsertMax :: (C.OrdCollX h a,Ord a) => a -> Min h a -> Min h a
unsafeFromOrdSeq :: (C.OrdCollX h a,Ord a,S.Sequence s) => s a -> Min h a
unsafeAppend :: (C.OrdCollX h a,Ord a) => Min h a -> Min h a -> Min h a
filterLT :: (C.OrdCollX h a,Ord a) => a -> Min h a -> Min h a
filterLE :: (C.OrdCollX h a,Ord a) => a -> Min h a -> Min h a
filterGT :: (C.OrdColl h a,Ord a) => a -> Min h a -> Min h a
filterGE :: (C.OrdColl h a,Ord a) => a -> Min h a -> Min h a
partitionLT_GE :: (C.OrdColl h a,Ord a) => a -> Min h a -> (Min h a, Min h a)
partitionLE_GT :: (C.OrdColl h a,Ord a) => a -> Min h a -> (Min h a, Min h a)
partitionLT_GT :: (C.OrdColl h a,Ord a) => a -> Min h a -> (Min h a, Min h a)
minView :: (C.OrdColl h a, Ord a, Fail.MonadFail m) => Min h a -> m (a, Min h a)
minElem :: (C.OrdColl h a,Ord a) => Min h a -> a
maxView :: (C.OrdColl h a, Ord a, Fail.MonadFail m) => Min h a -> m (a, Min h a)
maxElem :: (C.OrdColl h a,Ord a) => Min h a -> a
foldr :: (C.OrdColl h a,Ord a) => (a -> b -> b) -> b -> Min h a -> b
foldl :: (C.OrdColl h a,Ord a) => (b -> a -> b) -> b -> Min h a -> b
foldr1 :: (C.OrdColl h a,Ord a) => (a -> a -> a) -> Min h a -> a
foldl1 :: (C.OrdColl h a,Ord a) => (a -> a -> a) -> Min h a -> a
foldr' :: (C.OrdColl h a,Ord a) => (a -> b -> b) -> b -> Min h a -> b
foldl' :: (C.OrdColl h a,Ord a) => (b -> a -> b) -> b -> Min h a -> b
foldr1' :: (C.OrdColl h a,Ord a) => (a -> a -> a) -> Min h a -> a
foldl1' :: (C.OrdColl h a,Ord a) => (a -> a -> a) -> Min h a -> a
toOrdSeq :: (C.OrdColl h a,Ord a,S.Sequence s) => Min h a -> s a
unsafeMapMonotonic :: (C.OrdColl h a,Ord a) =>
(a -> a) -> Min h a -> Min h a
fromColl :: C.OrdColl h a => h -> Min h a
fromColl :: forall h a. OrdColl h a => h -> Min h a
fromColl = forall h a. OrdColl h a => h -> Min h a
fromPrim
toColl :: C.OrdColl h a => Min h a -> h
toColl :: forall h a. OrdColl h a => Min h a -> h
toColl = forall c a. OrdCollX c a => Min c a -> c
toPrim
fromPrim :: (C.OrdColl c a) => c -> Min c a
fromPrim :: forall h a. OrdColl h a => h -> Min h a
fromPrim c
xs = case forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> m (a, c)
C.minView c
xs of
Maybe (a, c)
Nothing -> forall h a. Min h a
E
Just (a
x, c
xs') -> forall h a. a -> h -> Min h a
M a
x c
xs'
toPrim :: (C.OrdCollX c a) => Min c a -> c
toPrim :: forall c a. OrdCollX c a => Min c a -> c
toPrim Min c a
E = forall c a. CollX c a => c
C.empty
toPrim (M a
x c
xs) = forall c a. OrdCollX c a => a -> c -> c
C.unsafeInsertMin a
x c
xs
empty :: forall h a. Min h a
empty = forall h a. Min h a
E
singleton :: forall h a. (CollX h a, Ord a) => a -> Min h a
singleton a
x = forall h a. a -> h -> Min h a
M a
x forall c a. CollX c a => c
C.empty
fromSeq :: forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s a -> Min h a
fromSeq = forall h a. OrdColl h a => h -> Min h a
fromPrim forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
C.fromSeq
insert :: forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
insert a
x Min h a
E = forall h a. a -> h -> Min h a
M a
x forall c a. CollX c a => c
C.empty
insert a
x (M a
y h
xs)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall h a. a -> h -> Min h a
M a
x (forall c a. OrdCollX c a => a -> c -> c
C.unsafeInsertMin a
y h
xs)
| Bool
otherwise = forall h a. a -> h -> Min h a
M a
y (forall c a. CollX c a => a -> c -> c
C.insert a
x h
xs)
insertSeq :: forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s a -> Min h a -> Min h a
insertSeq s a
xs Min h a
E = forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s a -> Min h a
fromSeq s a
xs
insertSeq s a
xs (M a
y h
ys) =
case forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> m (a, c)
C.minView h
xs_ys of
Maybe (a, h)
Nothing -> forall h a. a -> h -> Min h a
M a
y forall c a. CollX c a => c
C.empty
Just (a
x, h
rest)
| a
x forall a. Ord a => a -> a -> Bool
< a
y -> forall h a. a -> h -> Min h a
M a
x (forall c a. CollX c a => a -> c -> c
C.insert a
y h
rest)
| Bool
otherwise -> forall h a. a -> h -> Min h a
M a
y h
xs_ys
where xs_ys :: h
xs_ys = forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
C.insertSeq s a
xs h
ys
union :: forall h a. (OrdCollX h a, Ord a) => Min h a -> Min h a -> Min h a
union Min h a
E Min h a
ys = Min h a
ys
union Min h a
xs Min h a
E = Min h a
xs
union (M a
x h
xs) (M a
y h
ys)
| a
x forall a. Ord a => a -> a -> Bool
<= a
y = forall h a. a -> h -> Min h a
M a
x (forall c a. CollX c a => c -> c -> c
C.union h
xs (forall c a. OrdCollX c a => a -> c -> c
C.unsafeInsertMin a
y h
ys))
| Bool
otherwise = forall h a. a -> h -> Min h a
M a
y (forall c a. CollX c a => c -> c -> c
C.union (forall c a. OrdCollX c a => a -> c -> c
C.unsafeInsertMin a
x h
xs) h
ys)
unionSeq :: forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s (Min h a) -> Min h a
unionSeq = forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingReduce
delete :: forall h a. (OrdColl h a, Ord a) => a -> Min h a -> Min h a
delete a
_ Min h a
E = forall h a. Min h a
E
delete a
x m :: Min h a
m@(M a
y h
ys)
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall h a. a -> h -> Min h a
M a
y (forall c a. CollX c a => a -> c -> c
C.delete a
x h
ys)
| a
x forall a. Eq a => a -> a -> Bool
== a
y = forall h a. OrdColl h a => h -> Min h a
fromPrim h
ys
| Bool
otherwise = Min h a
m
deleteAll :: forall h a. (OrdColl h a, Ord a) => a -> Min h a -> Min h a
deleteAll a
_ Min h a
E = forall h a. Min h a
E
deleteAll a
x m :: Min h a
m@(M a
y h
ys)
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall h a. a -> h -> Min h a
M a
y (forall c a. CollX c a => a -> c -> c
C.deleteAll a
x h
ys)
| a
x forall a. Eq a => a -> a -> Bool
== a
y = forall h a. OrdColl h a => h -> Min h a
fromPrim (forall c a. CollX c a => a -> c -> c
C.deleteAll a
x h
ys)
| Bool
otherwise = Min h a
m
deleteSeq :: forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s a -> Min h a -> Min h a
deleteSeq = forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
deleteSeqUsingDelete
null :: forall h a. Min h a -> Bool
null Min h a
E = Bool
True
null (M a
_ h
_) = Bool
False
size :: forall h a. CollX h a => Min h a -> Int
size Min h a
E = Int
0
size (M a
_ h
xs) = Int
1 forall a. Num a => a -> a -> a
+ forall c a. CollX c a => c -> Int
C.size h
xs
member :: forall h a. (CollX h a, Ord a) => a -> Min h a -> Bool
member a
_ Min h a
E = Bool
False
member a
x (M a
y h
ys)
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall c a. CollX c a => a -> c -> Bool
C.member a
x h
ys
| Bool
otherwise = (a
x forall a. Eq a => a -> a -> Bool
== a
y)
count :: forall h a. (CollX h a, Ord a) => a -> Min h a -> Int
count a
_ Min h a
E = Int
0
count a
x (M a
y h
ys)
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall c a. CollX c a => a -> c -> Int
C.count a
x h
ys
| a
x forall a. Eq a => a -> a -> Bool
== a
y = Int
1 forall a. Num a => a -> a -> a
+ forall c a. CollX c a => a -> c -> Int
C.count a
x h
ys
| Bool
otherwise = Int
0
toSeq :: forall h a (s :: * -> *). (Coll h a, Sequence s) => Min h a -> s a
toSeq Min h a
E = forall (s :: * -> *) a. Sequence s => s a
S.empty
toSeq (M a
x h
xs) = forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
x (forall c a (seq :: * -> *). (Coll c a, Sequence seq) => c -> seq a
C.toSeq h
xs)
lookup :: forall h a. (Coll h a, Ord a) => a -> Min h a -> a
lookup a
x (M a
y h
ys)
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall c a. Coll c a => a -> c -> a
C.lookup a
x h
ys
| a
x forall a. Eq a => a -> a -> Bool
== a
y = a
y
lookup a
_ Min h a
_ = forall a. HasCallStack => String -> a
error String
"MinHeap.lookup: empty heap"
lookupM :: forall h a (m :: * -> *).
(Coll h a, Ord a, MonadFail m) =>
a -> Min h a -> m a
lookupM a
x (M a
y h
ys)
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
C.lookupM a
x h
ys
| a
x forall a. Eq a => a -> a -> Bool
== a
y = forall (m :: * -> *) a. Monad m => a -> m a
return a
y
lookupM a
_ Min h a
_ = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"lookupM.lookup: XXX"
lookupAll :: forall h a (s :: * -> *).
(Coll h a, Ord a, Sequence s) =>
a -> Min h a -> s a
lookupAll a
x (M a
y h
ys)
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
C.lookupAll a
x h
ys
| a
x forall a. Eq a => a -> a -> Bool
== a
y = forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
y (forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
C.lookupAll a
x h
ys)
lookupAll a
_ Min h a
_ = forall (s :: * -> *) a. Sequence s => s a
S.empty
lookupWithDefault :: forall h a. (Coll h a, Ord a) => a -> a -> Min h a -> a
lookupWithDefault a
d a
x (M a
y h
ys)
| a
x forall a. Ord a => a -> a -> Bool
> a
y = forall c a. Coll c a => a -> a -> c -> a
C.lookupWithDefault a
d a
x h
ys
| a
x forall a. Eq a => a -> a -> Bool
== a
y = a
y
lookupWithDefault a
d a
_ Min h a
_ = a
d
fold :: forall h a b. Coll h a => (a -> b -> b) -> b -> Min h a -> b
fold a -> b -> b
_ b
e Min h a
E = b
e
fold a -> b -> b
f b
e (M a
x h
xs) = a -> b -> b
f a
x (forall c a b. Coll c a => (a -> b -> b) -> b -> c -> b
C.fold a -> b -> b
f b
e h
xs)
fold' :: forall h a b. Coll h a => (a -> b -> b) -> b -> Min h a -> b
fold' a -> b -> b
_ b
e Min h a
E = b
e
fold' a -> b -> b
f b
e (M a
x h
xs) = a -> b -> b
f a
x forall a b. (a -> b) -> a -> b
$! (forall c a b. Coll c a => (a -> b -> b) -> b -> c -> b
C.fold' a -> b -> b
f b
e h
xs)
fold1 :: forall h a. Coll h a => (a -> a -> a) -> Min h a -> a
fold1 a -> a -> a
_ Min h a
E = forall a. HasCallStack => String -> a
error String
"MinHeap.fold1: empty heap"
fold1 a -> a -> a
f (M a
x h
xs) = forall c a b. Coll c a => (a -> b -> b) -> b -> c -> b
C.fold a -> a -> a
f a
x h
xs
fold1' :: forall h a. Coll h a => (a -> a -> a) -> Min h a -> a
fold1' a -> a -> a
_ Min h a
E = forall a. HasCallStack => String -> a
error String
"MinHeap.fold1': empty heap"
fold1' a -> a -> a
f (M a
x h
xs) = forall c a b. Coll c a => (a -> b -> b) -> b -> c -> b
C.fold' a -> a -> a
f a
x h
xs
filter :: forall h a. OrdColl h a => (a -> Bool) -> Min h a -> Min h a
filter a -> Bool
_ Min h a
E = forall h a. Min h a
E
filter a -> Bool
p (M a
x h
xs)
| a -> Bool
p a
x = forall h a. a -> h -> Min h a
M a
x (forall c a. Coll c a => (a -> Bool) -> c -> c
C.filter a -> Bool
p h
xs)
| Bool
otherwise = forall h a. OrdColl h a => h -> Min h a
fromPrim (forall c a. Coll c a => (a -> Bool) -> c -> c
C.filter a -> Bool
p h
xs)
partition :: forall h a.
OrdColl h a =>
(a -> Bool) -> Min h a -> (Min h a, Min h a)
partition a -> Bool
_ Min h a
E = (forall h a. Min h a
E, forall h a. Min h a
E)
partition a -> Bool
p (M a
x h
xs)
| a -> Bool
p a
x = (forall h a. a -> h -> Min h a
M a
x h
ys, forall h a. OrdColl h a => h -> Min h a
fromPrim h
zs)
| Bool
otherwise = (forall h a. OrdColl h a => h -> Min h a
fromPrim h
ys, forall h a. a -> h -> Min h a
M a
x h
zs)
where (h
ys,h
zs) = forall c a. Coll c a => (a -> Bool) -> c -> (c, c)
C.partition a -> Bool
p h
xs
deleteMin :: forall h a. (OrdColl h a, Ord a) => Min h a -> Min h a
deleteMin Min h a
E = forall h a. Min h a
E
deleteMin (M a
_ h
xs) = forall h a. OrdColl h a => h -> Min h a
fromPrim h
xs
deleteMax :: forall h a. (OrdCollX h a, Ord a) => Min h a -> Min h a
deleteMax Min h a
E = forall h a. Min h a
E
deleteMax (M a
x h
xs)
| forall c a. CollX c a => c -> Bool
C.null h
xs = forall h a. Min h a
E
| Bool
otherwise = forall h a. a -> h -> Min h a
M a
x (forall c a. OrdCollX c a => c -> c
C.deleteMax h
xs)
unsafeInsertMin :: forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
unsafeInsertMin a
x Min h a
xs = forall h a. a -> h -> Min h a
M a
x (forall c a. OrdCollX c a => Min c a -> c
toPrim Min h a
xs)
unsafeInsertMax :: forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
unsafeInsertMax a
x Min h a
E = forall h a. a -> h -> Min h a
M a
x forall c a. CollX c a => c
C.empty
unsafeInsertMax a
x (M a
y h
ys) = forall h a. a -> h -> Min h a
M a
y (forall c a. OrdCollX c a => a -> c -> c
C.unsafeInsertMax a
x h
ys)
unsafeFromOrdSeq :: forall h a (s :: * -> *).
(OrdCollX h a, Ord a, Sequence s) =>
s a -> Min h a
unsafeFromOrdSeq s a
xs =
case forall (s :: * -> *) (m :: * -> *) a.
(Sequence s, MonadFail m) =>
s a -> m (a, s a)
S.lview s a
xs of
Maybe (a, s a)
Nothing -> forall h a. Min h a
E
Just (a
x,s a
xs') -> forall h a. a -> h -> Min h a
M a
x (forall c a (seq :: * -> *).
(OrdCollX c a, Sequence seq) =>
seq a -> c
C.unsafeFromOrdSeq s a
xs')
unsafeAppend :: forall h a. (OrdCollX h a, Ord a) => Min h a -> Min h a -> Min h a
unsafeAppend Min h a
E Min h a
ys = Min h a
ys
unsafeAppend (M a
x h
xs) Min h a
ys = forall h a. a -> h -> Min h a
M a
x (forall c a. OrdCollX c a => c -> c -> c
C.unsafeAppend h
xs (forall c a. OrdCollX c a => Min c a -> c
toPrim Min h a
ys))
filterLT :: forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
filterLT a
x (M a
y h
ys) | a
y forall a. Ord a => a -> a -> Bool
< a
x = forall h a. a -> h -> Min h a
M a
y (forall c a. OrdCollX c a => a -> c -> c
C.filterLT a
x h
ys)
filterLT a
_ Min h a
_ = forall h a. Min h a
E
filterLE :: forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
filterLE a
x (M a
y h
ys) | a
y forall a. Ord a => a -> a -> Bool
<= a
x = forall h a. a -> h -> Min h a
M a
y (forall c a. OrdCollX c a => a -> c -> c
C.filterLE a
x h
ys)
filterLE a
_ Min h a
_ = forall h a. Min h a
E
filterGT :: forall h a. (OrdColl h a, Ord a) => a -> Min h a -> Min h a
filterGT a
x (M a
y h
ys) | a
y forall a. Ord a => a -> a -> Bool
<= a
x = forall h a. OrdColl h a => h -> Min h a
fromPrim (forall c a. OrdCollX c a => a -> c -> c
C.filterGT a
x h
ys)
filterGT a
_ Min h a
h = Min h a
h
filterGE :: forall h a. (OrdColl h a, Ord a) => a -> Min h a -> Min h a
filterGE a
x (M a
y h
ys) | a
y forall a. Ord a => a -> a -> Bool
< a
x = forall h a. OrdColl h a => h -> Min h a
fromPrim (forall c a. OrdCollX c a => a -> c -> c
C.filterGE a
x h
ys)
filterGE a
_ Min h a
h = Min h a
h
partitionLT_GE :: forall h a.
(OrdColl h a, Ord a) =>
a -> Min h a -> (Min h a, Min h a)
partitionLT_GE a
x (M a
y h
ys)
| a
y forall a. Ord a => a -> a -> Bool
< a
x = (forall h a. a -> h -> Min h a
M a
y h
lows, forall h a. OrdColl h a => h -> Min h a
fromPrim h
highs)
where (h
lows,h
highs) = forall c a. OrdCollX c a => a -> c -> (c, c)
C.partitionLT_GE a
x h
ys
partitionLT_GE a
_ Min h a
h = (forall h a. Min h a
E, Min h a
h)
partitionLE_GT :: forall h a.
(OrdColl h a, Ord a) =>
a -> Min h a -> (Min h a, Min h a)
partitionLE_GT a
x (M a
y h
ys)
| a
y forall a. Ord a => a -> a -> Bool
<= a
x = (forall h a. a -> h -> Min h a
M a
y h
lows, forall h a. OrdColl h a => h -> Min h a
fromPrim h
highs)
where (h
lows,h
highs) = forall c a. OrdCollX c a => a -> c -> (c, c)
C.partitionLE_GT a
x h
ys
partitionLE_GT a
_ Min h a
h = (forall h a. Min h a
E, Min h a
h)
partitionLT_GT :: forall h a.
(OrdColl h a, Ord a) =>
a -> Min h a -> (Min h a, Min h a)
partitionLT_GT a
x (M a
y h
ys)
| a
y forall a. Ord a => a -> a -> Bool
< a
x = let (h
lows,h
highs) = forall c a. OrdCollX c a => a -> c -> (c, c)
C.partitionLT_GT a
x h
ys
in (forall h a. a -> h -> Min h a
M a
y h
lows, forall h a. OrdColl h a => h -> Min h a
fromPrim h
highs)
| a
y forall a. Eq a => a -> a -> Bool
== a
x = (forall h a. Min h a
E, forall h a. OrdColl h a => h -> Min h a
fromPrim (forall c a. OrdCollX c a => a -> c -> c
C.filterGT a
x h
ys))
partitionLT_GT a
_ Min h a
h = (forall h a. Min h a
E, Min h a
h)
minView :: forall h a (m :: * -> *).
(OrdColl h a, Ord a, MonadFail m) =>
Min h a -> m (a, Min h a)
minView Min h a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"MinHeap.minView: empty heap"
minView (M a
x h
xs) = forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, forall h a. OrdColl h a => h -> Min h a
fromPrim h
xs)
minElem :: forall h a. (OrdColl h a, Ord a) => Min h a -> a
minElem Min h a
E = forall a. HasCallStack => String -> a
error String
"MinHeap.minElem: empty heap"
minElem (M a
x h
_) = a
x
maxView :: forall h a (m :: * -> *).
(OrdColl h a, Ord a, MonadFail m) =>
Min h a -> m (a, Min h a)
maxView Min h a
E = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"MinHeap.maxView: empty heap"
maxView (M a
x h
xs) = case forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> m (a, c)
C.maxView h
xs of
Maybe (a, h)
Nothing -> forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, forall h a. Min h a
E)
Just (a
y,h
ys) -> forall (m :: * -> *) a. Monad m => a -> m a
return (a
y, forall h a. a -> h -> Min h a
M a
x h
ys)
maxElem :: forall h a. (OrdColl h a, Ord a) => Min h a -> a
maxElem Min h a
E = forall a. HasCallStack => String -> a
error String
"MinHeap.minElem: empty heap"
maxElem (M a
x h
xs)
| forall c a. CollX c a => c -> Bool
C.null h
xs = a
x
| Bool
otherwise = forall c a. OrdColl c a => c -> a
C.maxElem h
xs
foldr :: forall h a b.
(OrdColl h a, Ord a) =>
(a -> b -> b) -> b -> Min h a -> b
foldr a -> b -> b
_ b
e Min h a
E = b
e
foldr a -> b -> b
f b
e (M a
x h
xs) = a -> b -> b
f a
x (forall c a b. OrdColl c a => (a -> b -> b) -> b -> c -> b
C.foldr a -> b -> b
f b
e h
xs)
foldr' :: forall h a b.
(OrdColl h a, Ord a) =>
(a -> b -> b) -> b -> Min h a -> b
foldr' a -> b -> b
_ b
e Min h a
E = b
e
foldr' a -> b -> b
f b
e (M a
x h
xs) = a -> b -> b
f a
x forall a b. (a -> b) -> a -> b
$! (forall c a b. OrdColl c a => (a -> b -> b) -> b -> c -> b
C.foldr' a -> b -> b
f b
e h
xs)
foldl :: forall h a b.
(OrdColl h a, Ord a) =>
(b -> a -> b) -> b -> Min h a -> b
foldl b -> a -> b
_ b
e Min h a
E = b
e
foldl b -> a -> b
f b
e (M a
x h
xs) = forall c a b. OrdColl c a => (b -> a -> b) -> b -> c -> b
C.foldl b -> a -> b
f (b -> a -> b
f b
e a
x) h
xs
foldl' :: forall h a b.
(OrdColl h a, Ord a) =>
(b -> a -> b) -> b -> Min h a -> b
foldl' b -> a -> b
_ b
e Min h a
E = b
e
foldl' b -> a -> b
f b
e (M a
x h
xs) = b
e seq :: forall a b. a -> b -> b
`seq` forall c a b. OrdColl c a => (b -> a -> b) -> b -> c -> b
C.foldl' b -> a -> b
f (b -> a -> b
f b
e a
x) h
xs
foldr1 :: forall h a. (OrdColl h a, Ord a) => (a -> a -> a) -> Min h a -> a
foldr1 a -> a -> a
_ Min h a
E = forall a. HasCallStack => String -> a
error String
"MinHeap.foldr1: empty heap"
foldr1 a -> a -> a
f (M a
x h
xs)
| forall c a. CollX c a => c -> Bool
C.null h
xs = a
x
| Bool
otherwise = a -> a -> a
f a
x (forall c a. OrdColl c a => (a -> a -> a) -> c -> a
C.foldr1 a -> a -> a
f h
xs)
foldr1' :: forall h a. (OrdColl h a, Ord a) => (a -> a -> a) -> Min h a -> a
foldr1' a -> a -> a
_ Min h a
E = forall a. HasCallStack => String -> a
error String
"MinHeap.foldr1': empty heap"
foldr1' a -> a -> a
f (M a
x h
xs)
| forall c a. CollX c a => c -> Bool
C.null h
xs = a
x
| Bool
otherwise = a -> a -> a
f a
x forall a b. (a -> b) -> a -> b
$! (forall c a. OrdColl c a => (a -> a -> a) -> c -> a
C.foldr1' a -> a -> a
f h
xs)
foldl1 :: forall h a. (OrdColl h a, Ord a) => (a -> a -> a) -> Min h a -> a
foldl1 a -> a -> a
_ Min h a
E = forall a. HasCallStack => String -> a
error String
"MinHeap.foldl1: empty heap"
foldl1 a -> a -> a
f (M a
x h
xs) = forall c a b. OrdColl c a => (b -> a -> b) -> b -> c -> b
C.foldl a -> a -> a
f a
x h
xs
foldl1' :: forall h a. (OrdColl h a, Ord a) => (a -> a -> a) -> Min h a -> a
foldl1' a -> a -> a
_ Min h a
E = forall a. HasCallStack => String -> a
error String
"MinHeap.foldl1': empty heap"
foldl1' a -> a -> a
f (M a
x h
xs) = forall c a b. OrdColl c a => (b -> a -> b) -> b -> c -> b
C.foldl' a -> a -> a
f a
x h
xs
toOrdSeq :: forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
Min h a -> s a
toOrdSeq Min h a
E = forall (s :: * -> *) a. Sequence s => s a
S.empty
toOrdSeq (M a
x h
xs) = forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
x (forall c a (seq :: * -> *).
(OrdColl c a, Sequence seq) =>
c -> seq a
C.toOrdSeq h
xs)
unsafeMapMonotonic :: forall h a. (OrdColl h a, Ord a) => (a -> a) -> Min h a -> Min h a
unsafeMapMonotonic = forall cin a cout b.
(OrdColl cin a, OrdCollX cout b) =>
(a -> b) -> cin -> cout
unsafeMapMonotonicUsingFoldr
strict :: forall h a. (CollX h a, Ord a) => Min h a -> Min h a
strict h :: Min h a
h@Min h a
E = Min h a
h
strict h :: Min h a
h@(M a
_ h
xs) = forall c a. CollX c a => c -> c
C.strict h
xs seq :: forall a b. a -> b -> b
`seq` Min h a
h
strictWith :: forall h a b. OrdColl h a => (a -> b) -> Min h a -> Min h a
strictWith a -> b
_ h :: Min h a
h@Min h a
E = Min h a
h
strictWith a -> b
f h :: Min h a
h@(M a
x h
xs) = a -> b
f a
x seq :: forall a b. a -> b -> b
`seq` forall c a b. Coll c a => (a -> b) -> c -> c
C.strictWith a -> b
f h
xs seq :: forall a b. a -> b -> b
`seq` Min h a
h
instance (C.OrdColl h a, Ord a) => C.CollX (Min h a) a where
{singleton :: a -> Min h a
singleton = forall h a. (CollX h a, Ord a) => a -> Min h a
singleton; fromSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Min h a
fromSeq = forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s a -> Min h a
fromSeq; insert :: a -> Min h a -> Min h a
insert = forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
insert;
insertSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Min h a -> Min h a
insertSeq = forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s a -> Min h a -> Min h a
insertSeq; unionSeq :: forall (seq :: * -> *). Sequence seq => seq (Min h a) -> Min h a
unionSeq = forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s (Min h a) -> Min h a
unionSeq;
delete :: a -> Min h a -> Min h a
delete = forall h a. (OrdColl h a, Ord a) => a -> Min h a -> Min h a
delete; deleteAll :: a -> Min h a -> Min h a
deleteAll = forall h a. (OrdColl h a, Ord a) => a -> Min h a -> Min h a
deleteAll; deleteSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Min h a -> Min h a
deleteSeq = forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s a -> Min h a -> Min h a
deleteSeq;
null :: Min h a -> Bool
null = forall h a. Min h a -> Bool
null; size :: Min h a -> Int
size = forall h a. CollX h a => Min h a -> Int
size; member :: a -> Min h a -> Bool
member = forall h a. (CollX h a, Ord a) => a -> Min h a -> Bool
member; count :: a -> Min h a -> Int
count = forall h a. (CollX h a, Ord a) => a -> Min h a -> Int
count;
strict :: Min h a -> Min h a
strict = forall h a. (CollX h a, Ord a) => Min h a -> Min h a
strict;
structuralInvariant :: Min h a -> Bool
structuralInvariant = forall a h. (Ord a, OrdColl h a) => Min h a -> Bool
structuralInvariant; instanceName :: Min h a -> String
instanceName Min h a
_ = String
moduleName}
instance (C.OrdColl h a, Ord a) => C.OrdCollX (Min h a) a where
{deleteMin :: Min h a -> Min h a
deleteMin = forall h a. (OrdColl h a, Ord a) => Min h a -> Min h a
deleteMin; deleteMax :: Min h a -> Min h a
deleteMax = forall h a. (OrdCollX h a, Ord a) => Min h a -> Min h a
deleteMax;
unsafeInsertMin :: a -> Min h a -> Min h a
unsafeInsertMin = forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
unsafeInsertMin; unsafeInsertMax :: a -> Min h a -> Min h a
unsafeInsertMax = forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
unsafeInsertMax;
unsafeFromOrdSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Min h a
unsafeFromOrdSeq = forall h a (s :: * -> *).
(OrdCollX h a, Ord a, Sequence s) =>
s a -> Min h a
unsafeFromOrdSeq; unsafeAppend :: Min h a -> Min h a -> Min h a
unsafeAppend = forall h a. (OrdCollX h a, Ord a) => Min h a -> Min h a -> Min h a
unsafeAppend;
filterLT :: a -> Min h a -> Min h a
filterLT = forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
filterLT; filterLE :: a -> Min h a -> Min h a
filterLE = forall h a. (OrdCollX h a, Ord a) => a -> Min h a -> Min h a
filterLE; filterGT :: a -> Min h a -> Min h a
filterGT = forall h a. (OrdColl h a, Ord a) => a -> Min h a -> Min h a
filterGT;
filterGE :: a -> Min h a -> Min h a
filterGE = forall h a. (OrdColl h a, Ord a) => a -> Min h a -> Min h a
filterGE; partitionLT_GE :: a -> Min h a -> (Min h a, Min h a)
partitionLT_GE = forall h a.
(OrdColl h a, Ord a) =>
a -> Min h a -> (Min h a, Min h a)
partitionLT_GE;
partitionLE_GT :: a -> Min h a -> (Min h a, Min h a)
partitionLE_GT = forall h a.
(OrdColl h a, Ord a) =>
a -> Min h a -> (Min h a, Min h a)
partitionLE_GT; partitionLT_GT :: a -> Min h a -> (Min h a, Min h a)
partitionLT_GT = forall h a.
(OrdColl h a, Ord a) =>
a -> Min h a -> (Min h a, Min h a)
partitionLT_GT}
instance (C.OrdColl h a, Ord a) => C.Coll (Min h a) a where
{toSeq :: forall (seq :: * -> *). Sequence seq => Min h a -> seq a
toSeq = forall h a (s :: * -> *). (Coll h a, Sequence s) => Min h a -> s a
toSeq; lookup :: a -> Min h a -> a
lookup = forall h a. (Coll h a, Ord a) => a -> Min h a -> a
lookup; lookupM :: forall (m :: * -> *). MonadFail m => a -> Min h a -> m a
lookupM = forall h a (m :: * -> *).
(Coll h a, Ord a, MonadFail m) =>
a -> Min h a -> m a
lookupM;
lookupAll :: forall (seq :: * -> *). Sequence seq => a -> Min h a -> seq a
lookupAll = forall h a (s :: * -> *).
(Coll h a, Ord a, Sequence s) =>
a -> Min h a -> s a
lookupAll; lookupWithDefault :: a -> a -> Min h a -> a
lookupWithDefault = forall h a. (Coll h a, Ord a) => a -> a -> Min h a -> a
lookupWithDefault;
fold :: forall b. (a -> b -> b) -> b -> Min h a -> b
fold = forall h a b. Coll h a => (a -> b -> b) -> b -> Min h a -> b
fold; fold' :: forall b. (a -> b -> b) -> b -> Min h a -> b
fold' = forall h a b. Coll h a => (a -> b -> b) -> b -> Min h a -> b
fold'; fold1 :: (a -> a -> a) -> Min h a -> a
fold1 = forall h a. Coll h a => (a -> a -> a) -> Min h a -> a
fold1; fold1' :: (a -> a -> a) -> Min h a -> a
fold1' = forall h a. Coll h a => (a -> a -> a) -> Min h a -> a
fold1';
filter :: (a -> Bool) -> Min h a -> Min h a
filter = forall h a. OrdColl h a => (a -> Bool) -> Min h a -> Min h a
filter; partition :: (a -> Bool) -> Min h a -> (Min h a, Min h a)
partition = forall h a.
OrdColl h a =>
(a -> Bool) -> Min h a -> (Min h a, Min h a)
partition; strictWith :: forall b. (a -> b) -> Min h a -> Min h a
strictWith = forall h a b. OrdColl h a => (a -> b) -> Min h a -> Min h a
strictWith}
instance (C.OrdColl h a, Ord a) => C.OrdColl (Min h a) a where
{minView :: forall (m :: * -> *). MonadFail m => Min h a -> m (a, Min h a)
minView = forall h a (m :: * -> *).
(OrdColl h a, Ord a, MonadFail m) =>
Min h a -> m (a, Min h a)
minView; minElem :: Min h a -> a
minElem = forall h a. (OrdColl h a, Ord a) => Min h a -> a
minElem; maxView :: forall (m :: * -> *). MonadFail m => Min h a -> m (a, Min h a)
maxView = forall h a (m :: * -> *).
(OrdColl h a, Ord a, MonadFail m) =>
Min h a -> m (a, Min h a)
maxView;
maxElem :: Min h a -> a
maxElem = forall h a. (OrdColl h a, Ord a) => Min h a -> a
maxElem; foldr :: forall b. (a -> b -> b) -> b -> Min h a -> b
foldr = forall h a b.
(OrdColl h a, Ord a) =>
(a -> b -> b) -> b -> Min h a -> b
foldr; foldr' :: forall b. (a -> b -> b) -> b -> Min h a -> b
foldr' = forall h a b.
(OrdColl h a, Ord a) =>
(a -> b -> b) -> b -> Min h a -> b
foldr';
foldl :: forall b. (b -> a -> b) -> b -> Min h a -> b
foldl = forall h a b.
(OrdColl h a, Ord a) =>
(b -> a -> b) -> b -> Min h a -> b
foldl; foldl' :: forall b. (b -> a -> b) -> b -> Min h a -> b
foldl' = forall h a b.
(OrdColl h a, Ord a) =>
(b -> a -> b) -> b -> Min h a -> b
foldl'; foldr1 :: (a -> a -> a) -> Min h a -> a
foldr1 = forall h a. (OrdColl h a, Ord a) => (a -> a -> a) -> Min h a -> a
foldr1; foldr1' :: (a -> a -> a) -> Min h a -> a
foldr1' = forall h a. (OrdColl h a, Ord a) => (a -> a -> a) -> Min h a -> a
foldr1';
foldl1 :: (a -> a -> a) -> Min h a -> a
foldl1 = forall h a. (OrdColl h a, Ord a) => (a -> a -> a) -> Min h a -> a
foldl1; foldl1' :: (a -> a -> a) -> Min h a -> a
foldl1' = forall h a. (OrdColl h a, Ord a) => (a -> a -> a) -> Min h a -> a
foldl1'; toOrdSeq :: forall (seq :: * -> *). Sequence seq => Min h a -> seq a
toOrdSeq = forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
Min h a -> s a
toOrdSeq;
unsafeMapMonotonic :: (a -> a) -> Min h a -> Min h a
unsafeMapMonotonic = forall h a. (OrdColl h a, Ord a) => (a -> a) -> Min h a -> Min h a
unsafeMapMonotonic}
instance (C.OrdColl h a, Show h) => Show (Min h a) where
showsPrec :: Int -> Min h a -> ShowS
showsPrec Int
i Min h a
xs String
rest
| Int
i forall a. Eq a => a -> a -> Bool
== Int
0 = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [ String
moduleName,String
".fromColl ",forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (forall h a. OrdColl h a => Min h a -> h
toColl Min h a
xs) String
rest]
| Bool
otherwise = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [String
"(",String
moduleName,String
".fromColl ",forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (forall h a. OrdColl h a => Min h a -> h
toColl Min h a
xs) (Char
')'forall a. a -> [a] -> [a]
:String
rest)]
instance (C.OrdColl h a, Read h) => Read (Min h a) where
readsPrec :: Int -> ReadS (Min h a)
readsPrec Int
_ String
xs = forall a. ReadS a -> ReadS a
maybeParens forall {h} {a}.
(Read h, OrdColl h a) =>
String -> [(Min h a, String)]
p String
xs
where p :: String -> [(Min h a, String)]
p String
ys = forall (m :: * -> *). MonadPlus m => String -> String -> m String
tokenMatch (String
moduleNameforall a. [a] -> [a] -> [a]
++String
".fromColl") String
ys
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall a. Read a => Int -> ReadS a
readsPrec Int
10
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \(h
coll,String
rest) -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall h a. OrdColl h a => h -> Min h a
fromColl h
coll,String
rest)
instance (C.OrdColl h a,Arbitrary h,Arbitrary a) => Arbitrary (Min h a) where
arbitrary :: Gen (Min h a)
arbitrary = do h
xs <- forall a. Arbitrary a => Gen a
arbitrary
a
x <- forall a. Arbitrary a => Gen a
arbitrary
Int
i <- forall a. Arbitrary a => Gen a
arbitrary :: Gen Int
forall (m :: * -> *) a. Monad m => a -> m a
return (if forall c a. CollX c a => c -> Bool
C.null h
xs Bool -> Bool -> Bool
|| a
x forall a. Ord a => a -> a -> Bool
<= forall c a. OrdColl c a => c -> a
C.minElem h
xs then forall h a. a -> h -> Min h a
M a
x h
xs
else if forall a. Integral a => a -> Bool
odd Int
i then forall h a. a -> h -> Min h a
M (forall c a. OrdColl c a => c -> a
C.minElem h
xs) h
xs
else forall h a. OrdColl h a => h -> Min h a
fromPrim h
xs)
instance (C.OrdColl h a,CoArbitrary h,CoArbitrary a) => CoArbitrary (Min h a) where
coarbitrary :: forall b. Min h a -> Gen b -> Gen b
coarbitrary Min h a
E = forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
coarbitrary (M a
x h
xs) = 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 h
xs
instance (C.OrdColl h a) => SG.Semigroup (Min h a) where
<> :: Min h a -> Min h a -> Min h a
(<>) = forall h a. (OrdCollX h a, Ord a) => Min h a -> Min h a -> Min h a
union
instance (C.OrdColl h a) => Monoid (Min h a) where
mempty :: Min h a
mempty = forall h a. Min h a
empty
mappend :: Min h a -> Min h a -> Min h a
mappend = forall a. Semigroup a => a -> a -> a
(SG.<>)
mconcat :: [Min h a] -> Min h a
mconcat = forall h a (s :: * -> *).
(OrdColl h a, Ord a, Sequence s) =>
s (Min h a) -> Min h a
unionSeq
instance (Eq h, C.OrdColl h a) => Ord (Min h a) where
compare :: Min h a -> Min h a -> Ordering
compare = forall c a. OrdColl c a => c -> c -> Ordering
compareUsingToOrdList