-- |
--   Module      :  Data.Edison.Coll.MinHeap
--   Copyright   :  Copyright (c) 1999, 2008 Chris Okasaki
--   License     :  MIT; see COPYRIGHT file for terms and conditions
--
--   Maintainer  :  robdockins AT fastmail DOT fm
--   Stability   :  stable
--   Portability :  GHC, Hugs (MPTC and FD)
--
--   A generic adaptor for bags to keep the minimum element separately.

module Data.Edison.Coll.MinHeap (
    -- * Min heap adaptor type
    Min, -- instance of Coll/CollX, OrdColl/OrdCollX

    -- * CollX operations
    empty,singleton,fromSeq,insert,insertSeq,union,unionSeq,delete,deleteAll,
    deleteSeq,null,size,member,count,strict,structuralInvariant,

    -- * Coll operations
    toSeq, lookup, lookupM, lookupAll, lookupWithDefault, fold, fold',
    fold1, fold1', filter, partition, strictWith,

    -- * OrdCollX operations
    deleteMin,deleteMax,unsafeInsertMin,unsafeInsertMax,unsafeFromOrdSeq,
    unsafeAppend,filterLT,filterLE,filterGT,filterGE,partitionLT_GE,
    partitionLE_GT,partitionLT_GT,

    -- * OrdColl operations
    minView,minElem,maxView,maxElem,foldr,foldr',foldl,foldl',
    foldr1,foldr1',foldl1,foldl1',toOrdSeq,
    unsafeMapMonotonic,

    -- * Other supported operations
    toColl,fromColl,

    -- * Documentation
    moduleName
) where

import Prelude hiding (null,foldr,foldl,foldr1,foldl1,foldl',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
(Min h a -> Min h a -> Bool)
-> (Min h a -> Min h a -> Bool) -> Eq (Min h a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall h a. (Eq a, Eq h) => 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
/= :: 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 h -> Bool
forall c a. CollX c a => c -> Bool
C.null h
h then Bool
True else a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= h -> a
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 = h -> Min h a
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 = Min h a -> h
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 c -> Maybe (a, c)
forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> m (a, c)
forall (m :: * -> *). MonadFail m => c -> m (a, c)
C.minView c
xs of
                Maybe (a, c)
Nothing -> Min c a
forall h a. Min h a
E
                Just (a
x, c
xs') -> a -> c -> Min c a
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 = c
forall c a. CollX c a => c
C.empty
toPrim (M a
x c
xs) = a -> c -> c
forall c a. OrdCollX c a => a -> c -> c
C.unsafeInsertMin a
x c
xs

empty :: forall h a. Min h a
empty = Min h a
forall h a. Min h a
E
singleton :: forall h a. (CollX h a, Ord a) => a -> Min h a
singleton a
x = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x h
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 = h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim (h -> Min h a) -> (s a -> h) -> s a -> Min h a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. s a -> h
forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
forall (seq :: * -> *). Sequence seq => seq a -> h
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 = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x h
forall c a. CollX c a => c
C.empty
insert a
x (M a
y h
xs)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y    = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x (a -> h -> h
forall c a. OrdCollX c a => a -> c -> c
C.unsafeInsertMin a
y h
xs)
  | Bool
otherwise = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y (a -> h -> h
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 = s a -> Min h a
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 h -> Maybe (a, h)
forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> m (a, c)
forall (m :: * -> *). MonadFail m => h -> m (a, h)
C.minView h
xs_ys of
      Maybe (a, h)
Nothing -> a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y h
forall c a. CollX c a => c
C.empty
      Just (a
x, h
rest)
          | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y     -> a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x (a -> h -> h
forall c a. CollX c a => a -> c -> c
C.insert a
y h
rest)
          | Bool
otherwise -> a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y h
xs_ys
  where xs_ys :: h
xs_ys = s a -> h -> h
forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
forall (seq :: * -> *). Sequence seq => seq a -> h -> h
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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y    = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x (h -> h -> h
forall c a. CollX c a => c -> c -> c
C.union h
xs (a -> h -> h
forall c a. OrdCollX c a => a -> c -> c
C.unsafeInsertMin a
y h
ys))
  | Bool
otherwise = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y (h -> h -> h
forall c a. CollX c a => c -> c -> c
C.union (a -> h -> h
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 = s (Min h a) -> Min h a
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 = Min h a
forall h a. Min h a
E
delete a
x m :: Min h a
m@(M a
y h
ys)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y     = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y (a -> h -> h
forall c a. CollX c a => a -> c -> c
C.delete a
x h
ys)
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y    = h -> Min h a
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 = Min h a
forall h a. Min h a
E
deleteAll a
x m :: Min h a
m@(M a
y h
ys)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y     = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y (a -> h -> h
forall c a. CollX c a => a -> c -> c
C.deleteAll a
x h
ys)
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y    = h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim (a -> h -> h
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 = s a -> Min h a -> Min h a
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ h -> Int
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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y     = a -> h -> Bool
forall c a. CollX c a => a -> c -> Bool
C.member a
x h
ys
  | Bool
otherwise = (a
x a -> a -> Bool
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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y     = a -> h -> Int
forall c a. CollX c a => a -> c -> Int
C.count a
x h
ys
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y    = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> h -> Int
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 = s a
forall (s :: * -> *) a. Sequence s => s a
S.empty
toSeq (M a
x h
xs) = a -> s a -> s a
forall a. a -> s a -> s a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
x (h -> s a
forall c a (seq :: * -> *). (Coll c a, Sequence seq) => c -> seq a
forall (seq :: * -> *). Sequence seq => h -> 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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y  = a -> h -> a
forall c a. Coll c a => a -> c -> a
C.lookup a
x h
ys
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = a
y
lookup a
_ Min h a
_ = String -> 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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y  = a -> h -> m a
forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
forall (m :: * -> *). MonadFail m => a -> h -> m a
C.lookupM a
x h
ys
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
y
lookupM a
_ Min h a
_ = String -> m a
forall a. String -> m 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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y  = a -> h -> s a
forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
forall (seq :: * -> *). Sequence seq => a -> h -> seq a
C.lookupAll a
x h
ys
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = a -> s a -> s a
forall a. a -> s a -> s a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
y (a -> h -> s a
forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
forall (seq :: * -> *). Sequence seq => a -> h -> seq a
C.lookupAll a
x h
ys)
lookupAll a
_ Min h a
_ = s 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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y  = a -> a -> h -> a
forall c a. Coll c a => a -> a -> c -> a
C.lookupWithDefault a
d a
x h
ys
  | a
x a -> a -> Bool
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 ((a -> b -> b) -> b -> h -> b
forall b. (a -> b -> b) -> b -> h -> b
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 (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! ((a -> b -> b) -> b -> h -> b
forall b. (a -> b -> b) -> b -> h -> 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 = String -> a
forall a. HasCallStack => String -> a
error String
"MinHeap.fold1: empty heap"
fold1 a -> a -> a
f (M a
x h
xs) = (a -> a -> a) -> a -> h -> a
forall b. (a -> b -> b) -> b -> h -> b
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 = String -> a
forall a. HasCallStack => String -> a
error String
"MinHeap.fold1': empty heap"
fold1' a -> a -> a
f (M a
x h
xs) = (a -> a -> a) -> a -> h -> a
forall b. (a -> b -> b) -> b -> h -> b
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 = Min h a
forall h a. Min h a
E
filter a -> Bool
p (M a
x h
xs)
  | a -> Bool
p a
x       = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x ((a -> Bool) -> h -> h
forall c a. Coll c a => (a -> Bool) -> c -> c
C.filter a -> Bool
p h
xs)
  | Bool
otherwise = h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim ((a -> Bool) -> h -> h
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 = (Min h a
forall h a. Min h a
E, Min h a
forall h a. Min h a
E)
partition a -> Bool
p (M a
x h
xs)
    | a -> Bool
p a
x       = (a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x h
ys, h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim h
zs)
    | Bool
otherwise = (h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim h
ys, a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x h
zs)
  where (h
ys,h
zs) = (a -> Bool) -> h -> (h, h)
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 = Min h a
forall h a. Min h a
E
deleteMin (M a
_ h
xs) = h -> Min h a
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 = Min h a
forall h a. Min h a
E
deleteMax (M a
x h
xs)
  | h -> Bool
forall c a. CollX c a => c -> Bool
C.null h
xs   = Min h a
forall h a. Min h a
E
  | Bool
otherwise = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x (h -> h
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 = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x (Min h a -> h
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 = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x h
forall c a. CollX c a => c
C.empty
unsafeInsertMax a
x (M a
y h
ys) = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y (a -> h -> h
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 s a -> Maybe (a, s a)
forall (s :: * -> *) (m :: * -> *) a.
(Sequence s, MonadFail m) =>
s a -> m (a, s a)
forall (m :: * -> *) a. MonadFail m => s a -> m (a, s a)
S.lview s a
xs of
    Maybe (a, s a)
Nothing      -> Min h a
forall h a. Min h a
E
    Just (a
x,s a
xs') -> a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x (s a -> h
forall c a (seq :: * -> *).
(OrdCollX c a, Sequence seq) =>
seq a -> c
forall (seq :: * -> *). Sequence seq => seq a -> h
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 = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x (h -> h -> h
forall c a. OrdCollX c a => c -> c -> c
C.unsafeAppend h
xs (Min h a -> h
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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x  = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y (a -> h -> h
forall c a. OrdCollX c a => a -> c -> c
C.filterLT a
x h
ys)
filterLT a
_ Min h 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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
x = a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y (a -> h -> h
forall c a. OrdCollX c a => a -> c -> c
C.filterLE a
x h
ys)
filterLE a
_ Min h 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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
x = h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim (a -> h -> h
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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x  = h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim (a -> h -> h
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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x = (a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y h
lows, h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim h
highs)
  where (h
lows,h
highs) = a -> h -> (h, h)
forall c a. OrdCollX c a => a -> c -> (c, c)
C.partitionLT_GE a
x h
ys
partitionLT_GE a
_ Min h a
h = (Min h a
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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
x = (a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y h
lows, h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim h
highs)
  where (h
lows,h
highs) = a -> h -> (h, h)
forall c a. OrdCollX c a => a -> c -> (c, c)
C.partitionLE_GT a
x h
ys
partitionLE_GT a
_ Min h a
h = (Min h a
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 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x  = let (h
lows,h
highs) = a -> h -> (h, h)
forall c a. OrdCollX c a => a -> c -> (c, c)
C.partitionLT_GT a
x h
ys
             in (a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
y h
lows, h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim h
highs)
  | a
y a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x = (Min h a
forall h a. Min h a
E, h -> Min h a
forall h a. OrdColl h a => h -> Min h a
fromPrim (a -> h -> h
forall c a. OrdCollX c a => a -> c -> c
C.filterGT a
x h
ys))
partitionLT_GT a
_ Min h a
h = (Min h a
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 = String -> m (a, Min h a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"MinHeap.minView: empty heap"
minView (M a
x h
xs) = (a, Min h a) -> m (a, Min h a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, h -> Min h a
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 = String -> a
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 = String -> m (a, Min h a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"MinHeap.maxView: empty heap"
maxView (M a
x h
xs) = case h -> Maybe (a, h)
forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> m (a, c)
forall (m :: * -> *). MonadFail m => h -> m (a, h)
C.maxView h
xs of
                     Maybe (a, h)
Nothing     -> (a, Min h a) -> m (a, Min h a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, Min h a
forall h a. Min h a
E)
                     Just (a
y,h
ys) -> (a, Min h a) -> m (a, Min h a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
y, a -> h -> Min h a
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 = String -> a
forall a. HasCallStack => String -> a
error String
"MinHeap.minElem: empty heap"
maxElem (M a
x h
xs)
  | h -> Bool
forall c a. CollX c a => c -> Bool
C.null h
xs   = a
x
  | Bool
otherwise = h -> a
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 ((a -> b -> b) -> b -> h -> b
forall b. (a -> b -> b) -> b -> h -> b
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 (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! ((a -> b -> b) -> b -> h -> b
forall b. (a -> b -> b) -> b -> h -> 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) = (b -> a -> b) -> b -> h -> b
forall b. (b -> a -> b) -> b -> h -> b
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 b -> b -> b
forall a b. a -> b -> b
`seq` (b -> a -> b) -> b -> h -> b
forall b. (b -> a -> b) -> b -> h -> b
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 = String -> a
forall a. HasCallStack => String -> a
error String
"MinHeap.foldr1: empty heap"
foldr1 a -> a -> a
f (M a
x h
xs)
  | h -> Bool
forall c a. CollX c a => c -> Bool
C.null h
xs   = a
x
  | Bool
otherwise = a -> a -> a
f a
x ((a -> a -> a) -> h -> a
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 = String -> a
forall a. HasCallStack => String -> a
error String
"MinHeap.foldr1': empty heap"
foldr1' a -> a -> a
f (M a
x h
xs)
  | h -> Bool
forall c a. CollX c a => c -> Bool
C.null h
xs = a
x
  | Bool
otherwise = a -> a -> a
f a
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! ((a -> a -> a) -> h -> a
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 = String -> a
forall a. HasCallStack => String -> a
error String
"MinHeap.foldl1: empty heap"
foldl1 a -> a -> a
f (M a
x h
xs) = (a -> a -> a) -> a -> h -> a
forall b. (b -> a -> b) -> b -> h -> b
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 = String -> a
forall a. HasCallStack => String -> a
error String
"MinHeap.foldl1': empty heap"
foldl1' a -> a -> a
f (M a
x h
xs) = (a -> a -> a) -> a -> h -> a
forall b. (b -> a -> b) -> b -> h -> b
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 = s a
forall (s :: * -> *) a. Sequence s => s a
S.empty
toOrdSeq (M a
x h
xs) = a -> s a -> s a
forall a. a -> s a -> s a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
x (h -> s a
forall c a (seq :: * -> *).
(OrdColl c a, Sequence seq) =>
c -> seq a
forall (seq :: * -> *). Sequence seq => h -> seq a
C.toOrdSeq h
xs)

unsafeMapMonotonic :: forall h a. (OrdColl h a, Ord a) => (a -> a) -> Min h a -> Min h a
unsafeMapMonotonic = (a -> a) -> Min h a -> Min h a
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) = h -> h
forall c a. CollX c a => c -> c
C.strict h
xs h -> Min h a -> Min h a
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 b -> Min h a -> Min h a
forall a b. a -> b -> b
`seq` (a -> b) -> h -> h
forall b. (a -> b) -> h -> h
forall c a b. Coll c a => (a -> b) -> c -> c
C.strictWith a -> b
f h
xs h -> Min h a -> Min h a
forall a b. a -> b -> b
`seq` Min h a
h


-- instance declarations

instance (C.OrdColl h a, Ord a) => C.CollX (Min h a) a where
  {singleton :: a -> Min h a
singleton = a -> Min h a
forall h a. (CollX h a, Ord a) => a -> Min h a
singleton; fromSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Min h a
fromSeq = seq a -> Min h a
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 = a -> Min h a -> Min h a
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 = seq a -> Min h a -> Min h a
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 = seq (Min h a) -> Min h a
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 = a -> Min h a -> Min h a
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 = a -> Min h a -> Min h a
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 = seq a -> Min h a -> Min h a
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 = Min h a -> Bool
forall h a. Min h a -> Bool
null; size :: Min h a -> Int
size = Min h a -> Int
forall h a. CollX h a => Min h a -> Int
size; member :: a -> Min h a -> Bool
member = a -> Min h a -> Bool
forall h a. (CollX h a, Ord a) => a -> Min h a -> Bool
member; count :: a -> Min h a -> Int
count = a -> Min h a -> Int
forall h a. (CollX h a, Ord a) => a -> Min h a -> Int
count;
   strict :: Min h a -> Min h a
strict = Min h a -> Min h a
forall h a. (CollX h a, Ord a) => Min h a -> Min h a
strict;
   structuralInvariant :: Min h a -> Bool
structuralInvariant = Min h a -> Bool
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 = Min h a -> Min h a
forall h a. (OrdColl h a, Ord a) => Min h a -> Min h a
deleteMin; deleteMax :: Min h a -> Min h a
deleteMax = Min h a -> Min h a
forall h a. (OrdCollX h a, Ord a) => Min h a -> Min h a
deleteMax;
   unsafeInsertMin :: a -> Min h a -> Min h a
unsafeInsertMin = a -> Min h a -> Min h a
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 = a -> Min h a -> Min h a
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 = seq a -> Min h a
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 = 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
unsafeAppend;
   filterLT :: a -> Min h a -> Min h a
filterLT = a -> Min h a -> Min h a
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 = a -> Min h a -> Min h a
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 = a -> Min h a -> Min h a
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 = a -> Min h a -> Min h a
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 = a -> Min h a -> (Min h a, Min h a)
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 = a -> Min h a -> (Min h a, Min h a)
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 = a -> Min h a -> (Min h a, Min h a)
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 = Min h a -> seq a
forall h a (s :: * -> *). (Coll h a, Sequence s) => Min h a -> s a
toSeq; lookup :: a -> Min h a -> a
lookup = a -> Min h a -> a
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 = a -> Min h a -> m a
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 = a -> Min h a -> seq a
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 = a -> a -> Min h a -> a
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 = (a -> b -> b) -> b -> Min h a -> b
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' = (a -> b -> b) -> b -> Min h a -> b
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 = (a -> a -> a) -> Min h a -> a
forall h a. Coll h a => (a -> a -> a) -> Min h a -> a
fold1; fold1' :: (a -> a -> a) -> Min h a -> a
fold1' = (a -> a -> a) -> Min h a -> a
forall h a. Coll h a => (a -> a -> a) -> Min h a -> a
fold1';
   filter :: (a -> Bool) -> Min h a -> Min h a
filter = (a -> Bool) -> Min h a -> Min h a
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 = (a -> Bool) -> Min h a -> (Min h a, Min h a)
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 = (a -> b) -> Min h a -> Min h a
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 = Min h a -> m (a, Min h a)
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 = Min h a -> a
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 = Min h a -> m (a, Min h a)
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 = Min h a -> a
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 = (a -> b -> b) -> b -> Min h a -> b
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' = (a -> b -> b) -> b -> Min h a -> b
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 = (b -> a -> b) -> b -> Min h a -> b
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' = (b -> a -> b) -> b -> Min h a -> b
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 = (a -> a -> a) -> Min h a -> a
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' = (a -> a -> a) -> Min h a -> a
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 = (a -> a -> a) -> Min h a -> a
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' = (a -> a -> a) -> Min h a -> a
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 = Min h a -> seq a
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 = (a -> a) -> Min h a -> Min h a
forall h a. (OrdColl h a, Ord a) => (a -> a) -> Min h a -> Min h a
unsafeMapMonotonic}

-- instance Eq is derived

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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = [String] -> String
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [    String
moduleName,String
".fromColl ",Int -> h -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (Min h a -> h
forall h a. OrdColl h a => Min h a -> h
toColl Min h a
xs) String
rest]
     | Bool
otherwise = [String] -> String
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [String
"(",String
moduleName,String
".fromColl ",Int -> h -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (Min h a -> h
forall h a. OrdColl h a => Min h a -> h
toColl Min h a
xs) (Char
')'Char -> ShowS
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 = ReadS (Min h a) -> ReadS (Min h a)
forall a. ReadS a -> ReadS a
maybeParens ReadS (Min h a)
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 = String -> String -> [String]
forall (m :: * -> *). MonadPlus m => String -> String -> m String
tokenMatch (String
moduleNameString -> ShowS
forall a. [a] -> [a] -> [a]
++String
".fromColl") String
ys
                      [String] -> (String -> [(h, String)]) -> [(h, String)]
forall a b. [a] -> (a -> [b]) -> [b]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Int -> String -> [(h, String)]
forall a. Read a => Int -> ReadS a
readsPrec Int
10
                      [(h, String)]
-> ((h, String) -> [(Min h a, String)]) -> [(Min h a, String)]
forall a b. [a] -> (a -> [b]) -> [b]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \(h
coll,String
rest) -> (Min h a, String) -> [(Min h a, String)]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (h -> Min h a
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 <- Gen h
forall a. Arbitrary a => Gen a
arbitrary
                 a
x  <- Gen a
forall a. Arbitrary a => Gen a
arbitrary
                 Int
i  <- Gen Int
forall a. Arbitrary a => Gen a
arbitrary :: Gen Int
                 Min h a -> Gen (Min h a)
forall a. a -> Gen a
forall (m :: * -> *) a. Monad m => a -> m a
return (if h -> Bool
forall c a. CollX c a => c -> Bool
C.null h
xs Bool -> Bool -> Bool
|| a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= h -> a
forall c a. OrdColl c a => c -> a
C.minElem h
xs then a -> h -> Min h a
forall h a. a -> h -> Min h a
M a
x h
xs
                         else if Int -> Bool
forall a. Integral a => a -> Bool
odd Int
i then a -> h -> Min h a
forall h a. a -> h -> Min h a
M (h -> a
forall c a. OrdColl c a => c -> a
C.minElem h
xs) h
xs
                                       else h -> Min h a
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 = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
  coarbitrary (M a
x h
xs) = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
1 (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Gen b -> Gen b
forall b. a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary a
x (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. h -> Gen b -> Gen b
forall b. h -> Gen b -> Gen b
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
(<>) = 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  = Min h a
forall h a. Min h a
empty
    mappend :: Min h a -> Min h a -> Min h a
mappend = Min h a -> Min h a -> Min h a
forall a. Semigroup a => a -> a -> a
(SG.<>)
    mconcat :: [Min h a] -> Min h a
mconcat = [Min h a] -> Min h a
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 = Min h a -> Min h a -> Ordering
forall c a. OrdColl c a => c -> c -> Ordering
compareUsingToOrdList