-- |
--   Module      :  Data.Edison.Coll.LazyPairingHeap
--   Copyright   :  Copyright (c) 1998-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)
--
--   Lazy Paring Heaps
--
--   /References:/
--
-- * Chris Okasaki. /Purely Functional Data Structures/. 1998.
--   Section 6.5.

module Data.Edison.Coll.LazyPairingHeap (
    -- * Type of pairing heaps
    Heap, -- 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,

    -- * Documentation
    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)


-- Invariants:
--   * left child of H2 not empty
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

-- second arg is not empty
-- not used!
-- link E h = h
-- link (H1 x b) a = H2 x a b
-- link (H2 x a b) a' = H1 x (union (union a a') b)

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
        {-
           could write the two GT cases as
             delList (dropWhile (< x) ys) h
           but this is only a win if we expect many of the ys
           to be missing from the tree.  However, we expect most
           of the ys to be present.
        -}

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

-- not exported
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


-- the remaining functions all use default definitions

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 declarations

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