-- |
--   Module      :  Data.Edison.Coll.SplayHeap
--   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)
--
--   Splay heaps.
--
--   If 'minElem' is called frequently, then SplayHeap should
--   be used in conjunction with "Data.Edison.Coll.MinHeap".
--
--   /References:/
--
-- * Chris Okasaki. /Purely Functional Data Structures/. 1998.
--   Section 5.4.

module Data.Edison.Coll.SplayHeap (
    -- * Type of splay 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,foldl',lookup,filter)
import qualified Data.Edison.Coll as C
import qualified Data.Edison.Seq as S
import Data.Edison.Coll.Defaults
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.SplayHeap"

data Heap a = E | T (Heap a) a (Heap a)

-- invariants:
--    * Binary Search Tree order (allowing duplicates)

structuralInvariant :: Ord a => Heap a -> Bool
structuralInvariant :: forall a. Ord a => Heap a -> Bool
structuralInvariant Heap a
t = Maybe a -> Maybe a -> Heap a -> Bool
forall {a}. Ord a => Maybe a -> Maybe a -> Heap a -> Bool
bounded Maybe a
forall a. Maybe a
Nothing Maybe a
forall a. Maybe a
Nothing Heap a
t
   where bounded :: Maybe a -> Maybe a -> Heap a -> Bool
bounded Maybe a
_ Maybe a
_ Heap a
E = Bool
True
         bounded Maybe a
lo Maybe a
hi (T Heap a
l a
x Heap a
r)  = Maybe a -> a -> Bool
forall {a}. Ord a => Maybe a -> a -> Bool
cmp_l Maybe a
lo a
x
                                 Bool -> Bool -> Bool
&& a -> Maybe a -> Bool
forall {a}. Ord a => a -> Maybe a -> Bool
cmp_r a
x Maybe a
hi
                                 Bool -> Bool -> Bool
&& Maybe a -> Maybe a -> Heap a -> Bool
bounded Maybe a
lo (a -> Maybe a
forall a. a -> Maybe a
Just a
x) Heap a
l
                                 Bool -> Bool -> Bool
&& Maybe a -> Maybe a -> Heap a -> Bool
bounded (a -> Maybe a
forall a. a -> Maybe a
Just a
x) Maybe a
hi Heap a
r

         cmp_l :: Maybe a -> a -> Bool
cmp_l Maybe a
Nothing  a
_ = Bool
True
         cmp_l (Just a
x) a
y = a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y

         cmp_r :: a -> Maybe a -> Bool
cmp_r a
_ Maybe a
Nothing  = Bool
True
         cmp_r a
x (Just a
y) = a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y


empty     :: Heap a
singleton :: a -> Heap a
fromSeq   :: (Ord a,S.Sequence s) => s a -> Heap a
insert    :: Ord a => a -> Heap a -> Heap a
insertSeq :: (Ord a,S.Sequence s) => s a -> Heap a -> Heap a
union     :: Ord a => Heap a -> Heap a -> Heap a
unionSeq  :: (Ord a,S.Sequence s) => s (Heap a) -> Heap a
delete    :: Ord a => a -> Heap a -> Heap a
deleteAll :: Ord a => a -> Heap a -> Heap a
deleteSeq :: (Ord a,S.Sequence s) => s a -> Heap a -> Heap a
null      :: Heap a -> Bool
size      :: Heap a -> Int
member    :: Ord a => a -> Heap a -> Bool
count     :: Ord a => a -> Heap a -> Int
strict    :: Heap a -> Heap a

toSeq     :: (Ord a, S.Sequence s) => Heap a -> s a
lookup    :: Ord a => a -> Heap a -> a
lookupM   :: (Ord a, Fail.MonadFail m) => a -> Heap a -> m a
lookupAll :: (Ord a,S.Sequence s) => a -> Heap a -> s a
lookupWithDefault :: Ord a => a -> a -> Heap a -> a
fold      :: Ord a => (a -> b -> b) -> b -> Heap a -> b
fold1     :: Ord a => (a -> a -> a) -> Heap a -> a
fold'     :: Ord a => (a -> b -> b) -> b -> Heap a -> b
fold1'    :: Ord a => (a -> a -> a) -> Heap a -> a
filter    :: Ord a => (a -> Bool) -> Heap a -> Heap a
partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
strictWith :: (a -> b) -> Heap a -> Heap a

deleteMin        :: Ord a => Heap a -> Heap a
deleteMax        :: Ord a => Heap a -> Heap a
unsafeInsertMin  :: Ord a => a -> Heap a -> Heap a
unsafeInsertMax  :: Ord a => a -> Heap a -> Heap a
unsafeFromOrdSeq :: (Ord a,S.Sequence s) => s a -> Heap a
unsafeAppend     :: Ord a => Heap a -> Heap a -> Heap a
filterLT         :: Ord a => a -> Heap a -> Heap a
filterLE         :: Ord a => a -> Heap a -> Heap a
filterGT         :: Ord a => a -> Heap a -> Heap a
filterGE         :: Ord a => a -> Heap a -> Heap a
partitionLT_GE   :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT   :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT   :: Ord a => a -> Heap a -> (Heap a, Heap a)

minView  :: (Ord a, Fail.MonadFail m) => Heap a -> m (a, Heap a)
minElem  :: Ord a => Heap a -> a
maxView  :: (Ord a, Fail.MonadFail m) => Heap a -> m (a, Heap a)
maxElem  :: Ord a => Heap a -> a
foldr    :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldl    :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldr1   :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1   :: Ord a => (a -> a -> a) -> Heap a -> a
foldr'   :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldl'   :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldr1'  :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1'  :: Ord a => (a -> a -> a) -> Heap a -> a
toOrdSeq :: (Ord a,S.Sequence s) => Heap a -> s a

unsafeMapMonotonic :: (a -> b) -> Heap a -> Heap b

empty :: forall a. Heap a
empty = Heap a
forall a. Heap a
E
singleton :: forall a. a -> Heap a
singleton a
x = Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
forall a. Heap a
E a
x Heap a
forall a. Heap a
E

insert :: forall a. Ord a => a -> Heap a -> Heap a
insert a
x Heap a
xs = Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
b
  where (Heap a
a,Heap a
b) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
x Heap a
xs

union :: forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
E Heap a
ys = Heap a
ys
union (T Heap a
a a
x Heap a
b) Heap a
ys = Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (Heap a -> Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
c Heap a
a) a
x (Heap a -> Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a -> Heap a
union Heap a
d Heap a
b)
  where (Heap a
c,Heap a
d) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
x Heap a
ys

delete :: forall a. Ord a => a -> Heap a -> Heap a
delete a
x Heap a
xs =
  let (Heap a
a,Heap a
b) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
x Heap a
xs
  in case Heap a -> Maybe (a, Heap a)
forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
maxView Heap a
a of
       Maybe (a, Heap a)
Nothing -> Heap a
b
       Just (a
y, Heap a
a')
         | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y -> Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a' a
y Heap a
b
         | Bool
otherwise -> Heap a -> Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend Heap a
a' Heap a
b

deleteAll :: forall a. Ord a => a -> Heap a -> Heap a
deleteAll a
x Heap a
xs = Heap a -> Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend Heap a
a Heap a
b
  where (Heap a
a,Heap a
b) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
x Heap a
xs

null :: forall a. Heap a -> Bool
null Heap a
E = Bool
True
null (T Heap a
_ a
_ Heap a
_) = Bool
False

size :: forall a. Heap a -> Int
size = Int -> Heap a -> Int
forall {t} {a}. Num t => t -> Heap a -> t
sz Int
0
  where sz :: t -> Heap a -> t
sz t
n Heap a
E = t
n
        sz t
n (T Heap a
a a
_ Heap a
b) = t -> Heap a -> t
sz (t -> Heap a -> t
sz (t
1t -> t -> t
forall a. Num a => a -> a -> a
+t
n) Heap a
a) Heap a
b

member :: forall a. Ord a => a -> Heap a -> Bool
member a
_ Heap a
E = Bool
False
member a
x (T Heap a
a a
y Heap a
b) = if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y then a -> Heap a -> Bool
forall a. Ord a => a -> Heap a -> Bool
member a
x Heap a
a else a
xa -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
y Bool -> Bool -> Bool
|| a -> Heap a -> Bool
forall a. Ord a => a -> Heap a -> Bool
member a
x Heap a
b

count :: forall a. Ord a => a -> Heap a -> Int
count = Int -> a -> Heap a -> Int
forall {a} {t}. (Ord a, Num t) => t -> a -> Heap a -> t
cnt Int
0
  where cnt :: t -> a -> Heap a -> t
cnt t
n a
_ Heap a
E = t
n
        cnt t
n a
x (T Heap a
a a
y Heap a
b)
          | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y = t -> a -> Heap a -> t
cnt t
n a
x Heap a
a
          | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y = t -> a -> Heap a -> t
cnt t
n a
x Heap a
b
          | Bool
otherwise = t -> a -> Heap a -> t
cnt (t -> a -> Heap a -> t
cnt (t
1t -> t -> t
forall a. Num a => a -> a -> a
+t
n) a
x Heap a
a) a
x Heap a
b

toSeq :: forall a (s :: * -> *). (Ord a, Sequence s) => Heap a -> s a
toSeq Heap a
xs = Heap a -> s a -> s a
forall {s :: * -> *} {a}. Sequence s => Heap a -> s a -> s a
tos Heap a
xs s a
forall (s :: * -> *) a. Sequence s => s a
S.empty
  where tos :: Heap a -> s a -> s a
tos Heap a
E s a
rest = s a
rest
        tos (T Heap a
a a
x Heap a
b) s a
rest = 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 (Heap a -> s a -> s a
tos Heap a
a (Heap a -> s a -> s a
tos Heap a
b s a
rest))

lookup :: forall a. Ord a => a -> Heap a -> a
lookup a
_ Heap a
E = String -> a
forall a. HasCallStack => String -> a
error String
"SplayHeap.lookup: empty heap"
lookup a
x (T Heap a
a a
y Heap a
b)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y     = a -> Heap a -> a
forall a. Ord a => a -> Heap a -> a
lookup a
x Heap a
a
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y     = a -> Heap a -> a
forall a. Ord a => a -> Heap a -> a
lookup a
x Heap a
b
  | Bool
otherwise = a
y

lookupM :: forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Heap a -> m a
lookupM a
_ Heap a
E = String -> m a
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"SplayHeap.lookup: empty heap"
lookupM a
x (T Heap a
a a
y Heap a
b)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y     = a -> Heap a -> m a
forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Heap a -> m a
lookupM a
x Heap a
a
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y     = a -> Heap a -> m a
forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Heap a -> m a
lookupM a
x Heap a
b
  | Bool
otherwise = a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
y

lookupWithDefault :: forall a. Ord a => a -> a -> Heap a -> a
lookupWithDefault a
d a
_ Heap a
E = a
d
lookupWithDefault a
d a
x (T Heap a
a a
y Heap a
b)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y     = a -> a -> Heap a -> a
forall a. Ord a => a -> a -> Heap a -> a
lookupWithDefault a
d a
x Heap a
a
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y     = a -> a -> Heap a -> a
forall a. Ord a => a -> a -> Heap a -> a
lookupWithDefault a
d a
x Heap a
b
  | Bool
otherwise = a
y

lookupAll :: forall a (s :: * -> *). (Ord a, Sequence s) => a -> Heap a -> s a
lookupAll a
x Heap a
xs = Heap a -> a -> s a -> s a
forall {a} {s :: * -> *}.
(Ord a, Sequence s) =>
Heap a -> a -> s a -> s a
look Heap a
xs a
x s a
forall (s :: * -> *) a. Sequence s => s a
S.empty
  where look :: Heap a -> a -> s a -> s a
look Heap a
E a
_ s a
rest = s a
rest
        look (T Heap a
a a
y Heap a
b) a
x s a
rest
          | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y     = Heap a -> a -> s a -> s a
look Heap a
a a
x s a
rest
          | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
y     = Heap a -> a -> s a -> s a
look Heap a
b a
x s a
rest
          | Bool
otherwise = Heap a -> a -> s a -> s a
look Heap a
a a
x (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 (Heap a -> a -> s a -> s a
look Heap a
b a
x s a
rest))

fold :: forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold a -> b -> b
_ b
e Heap a
E = b
e
fold a -> b -> b
f b
e (T Heap a
a a
x Heap a
b) = a -> b -> b
f a
x ((a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold a -> b -> b
f ((a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold a -> b -> b
f b
e Heap a
b) Heap a
a)

fold' :: forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold' a -> b -> b
_ b
e Heap a
E = b
e
fold' a -> b -> b
f b
e (T Heap a
a a
x Heap a
b) = b
e b -> b -> b
forall a b. a -> b -> b
`seq` a -> b -> b
f a
x (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! ((a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold' a -> b -> b
f ((a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold' a -> b -> b
f b
e Heap a
b) Heap a
a)

fold1 :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
fold1 a -> a -> a
_ Heap a
E = String -> a
forall a. HasCallStack => String -> a
error String
"SplayHeap.fold1: empty heap"
fold1 a -> a -> a
f (T Heap a
a a
x Heap a
b) = (a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold a -> a -> a
f ((a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold a -> a -> a
f a
x Heap a
b) Heap a
a

fold1' :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
fold1' a -> a -> a
_ Heap a
E = String -> a
forall a. HasCallStack => String -> a
error String
"SplayHeap.fold1': empty heap"
fold1' a -> a -> a
f (T Heap a
a a
x Heap a
b) = (a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold' a -> a -> a
f ((a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold' a -> a -> a
f a
x Heap a
b) Heap a
a

filter :: forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
_ Heap a
E = Heap a
forall a. Heap a
E
filter a -> Bool
p (T Heap a
a a
x Heap a
b)
  | a -> Bool
p a
x       = Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T ((a -> Bool) -> Heap a -> Heap a
forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
a) a
x ((a -> Bool) -> Heap a -> Heap a
forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
b)
  | Bool
otherwise = Heap a -> Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend ((a -> Bool) -> Heap a -> Heap a
forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
a) ((a -> Bool) -> Heap a -> Heap a
forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter a -> Bool
p Heap a
b)

partition :: forall a. Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition a -> Bool
_ Heap a
E = (Heap a
forall a. Heap a
E, Heap a
forall a. Heap a
E)
partition a -> Bool
p (T Heap a
a a
x Heap a
b)
    | a -> Bool
p a
x       = (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a0 a
x Heap a
b0, Heap a -> Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend Heap a
a1 Heap a
b1)
    | Bool
otherwise = (Heap a -> Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend Heap a
a0 Heap a
b0, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a1 a
x Heap a
b1)
  where (Heap a
a0,Heap a
a1) = (a -> Bool) -> Heap a -> (Heap a, Heap a)
forall a. Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition a -> Bool
p Heap a
a
        (Heap a
b0,Heap a
b1) = (a -> Bool) -> Heap a -> (Heap a, Heap a)
forall a. Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition a -> Bool
p Heap a
b

deleteMin :: forall a. Ord a => Heap a -> Heap a
deleteMin Heap a
E = Heap a
forall a. Heap a
E
deleteMin (T Heap a
a a
x Heap a
b) = Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
del Heap a
a a
x Heap a
b
  where del :: Heap t -> t -> Heap t -> Heap t
del Heap t
E t
_ Heap t
b = Heap t
b
        del (T Heap t
E t
_ Heap t
b) t
y Heap t
c = Heap t -> t -> Heap t -> Heap t
forall a. Heap a -> a -> Heap a -> Heap a
T Heap t
b t
y Heap t
c
        del (T (T Heap t
a t
x Heap t
b) t
y Heap t
c) t
z Heap t
d = Heap t -> t -> Heap t -> Heap t
forall a. Heap a -> a -> Heap a -> Heap a
T (Heap t -> t -> Heap t -> Heap t
del Heap t
a t
x Heap t
b) t
y (Heap t -> t -> Heap t -> Heap t
forall a. Heap a -> a -> Heap a -> Heap a
T Heap t
c t
z Heap t
d)

deleteMax :: forall a. Ord a => Heap a -> Heap a
deleteMax Heap a
E = Heap a
forall a. Heap a
E
deleteMax (T Heap a
a a
x Heap a
b) = Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
del Heap a
a a
x Heap a
b
  where del :: Heap t -> t -> Heap t -> Heap t
del Heap t
a t
_ Heap t
E = Heap t
a
        del Heap t
a t
x (T Heap t
b t
_ Heap t
E) = Heap t -> t -> Heap t -> Heap t
forall a. Heap a -> a -> Heap a -> Heap a
T Heap t
a t
x Heap t
b
        del Heap t
a t
x (T Heap t
b t
y (T Heap t
c t
z Heap t
d)) = Heap t -> t -> Heap t -> Heap t
forall a. Heap a -> a -> Heap a -> Heap a
T (Heap t -> t -> Heap t -> Heap t
forall a. Heap a -> a -> Heap a -> Heap a
T Heap t
a t
x Heap t
b) t
y (Heap t -> t -> Heap t -> Heap t
del Heap t
c t
z Heap t
d)

unsafeInsertMin :: forall a. Ord a => a -> Heap a -> Heap a
unsafeInsertMin a
x Heap a
xs = Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
forall a. Heap a
E a
x Heap a
xs
unsafeInsertMax :: forall a. Ord a => a -> Heap a -> Heap a
unsafeInsertMax a
x Heap a
xs = Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
xs a
x Heap a
forall a. Heap a
E

unsafeAppend :: forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend Heap a
a Heap a
b = case Heap a -> Maybe (a, Heap a)
forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
maxView Heap a
a of
                       Maybe (a, Heap a)
Nothing      -> Heap a
b
                       Just (a
x, Heap a
a') -> Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a' a
x Heap a
b

filterLT :: forall a. Ord a => a -> Heap a -> Heap a
filterLT a
_ Heap a
E = Heap a
forall a. Heap a
E
filterLT a
k t :: Heap a
t@(T Heap a
a a
x Heap a
b) =
  if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
k then a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLT a
k Heap a
a
  else case Heap a
b of
         Heap a
E -> Heap a
t
         T Heap a
ba a
y Heap a
bb ->
           if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
k then Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLT a
k Heap a
ba)
                     else Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
ba) a
y (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLT a
k Heap a
bb)

filterLE :: forall a. Ord a => a -> Heap a -> Heap a
filterLE a
_ Heap a
E = Heap a
forall a. Heap a
E
filterLE a
k t :: Heap a
t@(T Heap a
a a
x Heap a
b) =
  if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k then a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLE a
k Heap a
a
  else case Heap a
b of
         Heap a
E -> Heap a
t
         T Heap a
ba a
y Heap a
bb ->
           if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k then Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLE a
k Heap a
ba)
                    else Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
ba) a
y (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLE a
k Heap a
bb)

filterGT :: forall a. Ord a => a -> Heap a -> Heap a
filterGT a
_ Heap a
E = Heap a
forall a. Heap a
E
filterGT a
k t :: Heap a
t@(T Heap a
a a
x Heap a
b) =
  if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
k then a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGT a
k Heap a
b
  else case Heap a
a of
         Heap a
E -> Heap a
t
         T Heap a
aa a
y Heap a
ab ->
           if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
k then Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGT a
k Heap a
ab) a
x Heap a
b
                     else Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGT a
k Heap a
aa) a
y (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
ab a
x Heap a
b)

filterGE :: forall a. Ord a => a -> Heap a -> Heap a
filterGE a
_ Heap a
E = Heap a
forall a. Heap a
E
filterGE a
k t :: Heap a
t@(T Heap a
a a
x Heap a
b) =
  if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
k then a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGE a
k Heap a
b
  else case Heap a
a of
         Heap a
E -> Heap a
t
         T Heap a
aa a
y Heap a
ab ->
           if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
k then Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGE a
k Heap a
ab) a
x Heap a
b
                    else Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGE a
k Heap a
aa) a
y (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
ab a
x Heap a
b)

partitionLT_GE :: forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE a
_ Heap a
E = (Heap a
forall a. Heap a
E,Heap a
forall a. Heap a
E)
partitionLT_GE a
k t :: Heap a
t@(T Heap a
a a
x Heap a
b) =
  if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
k then
    case Heap a
a of
      Heap a
E -> (Heap a
forall a. Heap a
E,Heap a
t)
      T Heap a
aa a
y Heap a
ab ->
        if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
k then
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE a
k Heap a
aa
          in (Heap a
small, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
big a
y (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
ab a
x Heap a
b))
        else
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE a
k Heap a
ab
          in (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
aa a
y Heap a
small, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
big a
x Heap a
b)
  else
    case Heap a
b of
      Heap a
E -> (Heap a
t,Heap a
forall a. Heap a
E)
      T Heap a
ba a
y Heap a
bb ->
        if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
k then
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE a
k Heap a
ba
          in (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
small, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
big a
y Heap a
bb)
        else
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE a
k Heap a
bb
          in (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
ba) a
y Heap a
small, Heap a
big)

partitionLE_GT :: forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
_ Heap a
E = (Heap a
forall a. Heap a
E,Heap a
forall a. Heap a
E)
partitionLE_GT a
k t :: Heap a
t@(T Heap a
a a
x Heap a
b) =
  if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k then
    case Heap a
a of
      Heap a
E -> (Heap a
forall a. Heap a
E,Heap a
t)
      T Heap a
aa a
y Heap a
ab ->
        if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k then
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
k Heap a
aa
          in (Heap a
small, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
big a
y (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
ab a
x Heap a
b))
        else
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
k Heap a
ab
          in (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
aa a
y Heap a
small, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
big a
x Heap a
b)
  else
    case Heap a
b of
      Heap a
E -> (Heap a
t,Heap a
forall a. Heap a
E)
      T Heap a
ba a
y Heap a
bb ->
        if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k then
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
k Heap a
ba
          in (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
small, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
big a
y Heap a
bb)
        else
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT a
k Heap a
bb
          in (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
ba) a
y Heap a
small, Heap a
big)


-- could specialize calls to filterLT/filterGT
partitionLT_GT :: forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
_ Heap a
E = (Heap a
forall a. Heap a
E,Heap a
forall a. Heap a
E)
partitionLT_GT a
k t :: Heap a
t@(T Heap a
a a
x Heap a
b) =
  if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k then
    case Heap a
a of
      Heap a
E -> (Heap a
forall a. Heap a
E,Heap a
t)
      T Heap a
aa a
y Heap a
ab ->
        if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k then
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
k Heap a
aa
          in (Heap a
small, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
big a
y (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
ab a
x Heap a
b))
        else if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
k then
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
k Heap a
ab
          in (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
aa a
y Heap a
small, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
big a
x Heap a
b)
        else (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLT a
k Heap a
aa, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGT a
k Heap a
ab) a
x Heap a
b)
  else if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
k then
    case Heap a
b of
      Heap a
E -> (Heap a
t,Heap a
forall a. Heap a
E)
      T Heap a
ba a
y Heap a
bb ->
        if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k then
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
k Heap a
ba
          in (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
small, Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
big a
y Heap a
bb)
        else if a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
k then
          let (Heap a
small,Heap a
big) = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT a
k Heap a
bb
          in (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
ba) a
y Heap a
small, Heap a
big)
        else (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLT a
k Heap a
ba), a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGT a
k Heap a
bb)
  else (a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLT a
k Heap a
a, a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGT a
k Heap a
b)

minView :: forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
minView Heap a
E = String -> m (a, Heap a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"SplayHeap.minView: empty heap"
minView (T Heap a
a a
x Heap a
b) = (a, Heap a) -> m (a, Heap a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
y, Heap a
ys)
  where (a
y,Heap a
ys) = Heap a -> a -> Heap a -> (a, Heap a)
forall {a}. Heap a -> a -> Heap a -> (a, Heap a)
minv Heap a
a a
x Heap a
b
        minv :: Heap a -> a -> Heap a -> (a, Heap a)
minv Heap a
E a
x Heap a
b = (a
x,Heap a
b)
        minv (T Heap a
E a
x Heap a
b) a
y Heap a
c = (a
x,Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
b a
y Heap a
c)
        minv (T (T Heap a
a a
x Heap a
b) a
y Heap a
c) a
z Heap a
d = (a
w,Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
ab a
y (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
c a
z Heap a
d))
          where (a
w,Heap a
ab) = Heap a -> a -> Heap a -> (a, Heap a)
minv Heap a
a a
x Heap a
b

minElem :: forall a. Ord a => Heap a -> a
minElem Heap a
E = String -> a
forall a. HasCallStack => String -> a
error String
"SplayHeap.minElem: empty heap"
minElem (T Heap a
a a
x Heap a
_) = Heap a -> a -> a
forall {t}. Heap t -> t -> t
minel Heap a
a a
x
  where minel :: Heap t -> t -> t
minel Heap t
E t
x = t
x
        minel (T Heap t
a t
x Heap t
_) t
_ = Heap t -> t -> t
minel Heap t
a t
x


maxView :: forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
maxView Heap a
E = String -> m (a, Heap a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"SplayHeap.maxView: empty heap"
maxView (T Heap a
a a
x Heap a
b) = (a, Heap a) -> m (a, Heap a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
y,Heap a
ys)
  where (Heap a
ys,a
y) = Heap a -> a -> Heap a -> (Heap a, a)
forall {a}. Heap a -> a -> Heap a -> (Heap a, a)
maxv Heap a
a a
x Heap a
b
        maxv :: Heap a -> a -> Heap a -> (Heap a, a)
maxv Heap a
a a
x Heap a
E = (Heap a
a,a
x)
        maxv Heap a
a a
x (T Heap a
b a
y Heap a
E) = (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
b,a
y)
        maxv Heap a
a a
x (T Heap a
b a
y (T Heap a
c a
z Heap a
d)) = (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T (Heap a -> a -> Heap a -> Heap a
forall a. Heap a -> a -> Heap a -> Heap a
T Heap a
a a
x Heap a
b) a
y Heap a
cd,a
w)
          where (Heap a
cd,a
w) = Heap a -> a -> Heap a -> (Heap a, a)
maxv Heap a
c a
z Heap a
d

maxElem :: forall a. Ord a => Heap a -> a
maxElem Heap a
E = String -> a
forall a. HasCallStack => String -> a
error String
"SplayHeap.minElem: empty heap"
maxElem (T Heap a
_ a
x Heap a
b) = a -> Heap a -> a
forall {t}. t -> Heap t -> t
maxel a
x Heap a
b
  where maxel :: t -> Heap t -> t
maxel t
x Heap t
E = t
x
        maxel t
_ (T Heap t
_ t
x Heap t
b) = t -> Heap t -> t
maxel t
x Heap t
b

foldr :: forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr a -> b -> b
_ b
e Heap a
E = b
e
foldr a -> b -> b
f b
e (T Heap a
a a
x Heap a
b) = (a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr a -> b -> b
f (a -> b -> b
f a
x ((a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr a -> b -> b
f b
e Heap a
b)) Heap a
a

foldr' :: forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' a -> b -> b
_ b
e Heap a
E = b
e
foldr' a -> b -> b
f b
e (T Heap a
a a
x Heap a
b) = (a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' a -> b -> b
f (a -> b -> b
f a
x (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! ((a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' a -> b -> b
f b
e Heap a
b)) Heap a
a

foldl :: forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl b -> a -> b
_ b
e Heap a
E = b
e
foldl b -> a -> b
f b
e (T Heap a
a a
x Heap a
b) = (b -> a -> b) -> b -> Heap a -> b
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl b -> a -> b
f (b -> a -> b
f ((b -> a -> b) -> b -> Heap a -> b
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl b -> a -> b
f b
e Heap a
a) a
x) Heap a
b

foldl' :: forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' b -> a -> b
_ b
e Heap a
E = b
e
foldl' b -> a -> b
f b
e (T Heap a
a a
x Heap a
b) = b
e b -> b -> b
forall a b. a -> b -> b
`seq` (b -> a -> b) -> b -> Heap a -> b
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' b -> a -> b
f ((b -> a -> b
f (b -> a -> b) -> b -> a -> b
forall a b. (a -> b) -> a -> b
$! ((b -> a -> b) -> b -> Heap a -> b
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' b -> a -> b
f b
e Heap a
a)) a
x) Heap a
b

foldr1 :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1 a -> a -> a
_ Heap a
E = String -> a
forall a. HasCallStack => String -> a
error String
"SplayHeap.foldr1: empty heap"
foldr1 a -> a -> a
f (T Heap a
a a
x Heap a
b) = (a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr a -> a -> a
f ((a -> a -> a) -> a -> Heap a -> a
forall {t}. Ord t => (t -> t -> t) -> t -> Heap t -> t
myfold a -> a -> a
f a
x Heap a
b) Heap a
a
  where myfold :: (t -> t -> t) -> t -> Heap t -> t
myfold t -> t -> t
_ t
x Heap t
E = t
x
        myfold t -> t -> t
f t
x (T Heap t
a t
y Heap t
b) = t -> t -> t
f t
x ((t -> t -> t) -> t -> Heap t -> t
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr t -> t -> t
f ((t -> t -> t) -> t -> Heap t -> t
myfold t -> t -> t
f t
y Heap t
b) Heap t
a)

foldr1' :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1' a -> a -> a
_ Heap a
E = String -> a
forall a. HasCallStack => String -> a
error String
"SplayHeap.foldr1': empty heap"
foldr1' a -> a -> a
f (T Heap a
a a
x Heap a
b) = (a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' a -> a -> a
f ((a -> a -> a) -> a -> Heap a -> a
forall {t}. Ord t => (t -> t -> t) -> t -> Heap t -> t
myfold a -> a -> a
f a
x Heap a
b) Heap a
a
  where myfold :: (a -> a -> a) -> a -> Heap a -> a
myfold a -> a -> a
_ a
x Heap a
E = a
x
        myfold a -> a -> a
f a
x (T Heap a
a a
y Heap a
b) = a -> a -> a
f a
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! ((a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' a -> a -> a
f ((a -> a -> a) -> a -> Heap a -> a
myfold a -> a -> a
f a
y Heap a
b) Heap a
a)

foldl1 :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldl1 a -> a -> a
_ Heap a
E = String -> a
forall a. HasCallStack => String -> a
error String
"SplayHeap.foldl1: empty heap"
foldl1 a -> a -> a
f (T Heap a
a a
x Heap a
b) = (a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl a -> a -> a
f ((a -> a -> a) -> Heap a -> a -> a
forall {a}. Ord a => (a -> a -> a) -> Heap a -> a -> a
myfold a -> a -> a
f Heap a
a a
x) Heap a
b
  where myfold :: (a -> a -> a) -> Heap a -> a -> a
myfold a -> a -> a
_ Heap a
E a
x = a
x
        myfold a -> a -> a
f (T Heap a
a a
x Heap a
b) a
y = a -> a -> a
f ((a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl a -> a -> a
f ((a -> a -> a) -> Heap a -> a -> a
myfold a -> a -> a
f Heap a
a a
x) Heap a
b) a
y

foldl1' :: forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldl1' a -> a -> a
_ Heap a
E = String -> a
forall a. HasCallStack => String -> a
error String
"SplayHeap.foldl1': empty heap"
foldl1' a -> a -> a
f (T Heap a
a a
x Heap a
b) = (a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' a -> a -> a
f ((a -> a -> a) -> Heap a -> a -> a
forall {a}. Ord a => (a -> a -> a) -> Heap a -> a -> a
myfold a -> a -> a
f Heap a
a a
x) Heap a
b
  where myfold :: (a -> a -> a) -> Heap a -> a -> a
myfold a -> a -> a
_ Heap a
E a
x = a
x
        myfold a -> a -> a
f (T Heap a
a a
x Heap a
b) a
y = (a -> a -> a
f (a -> a -> a) -> a -> a -> a
forall a b. (a -> b) -> a -> b
$! ((a -> a -> a) -> a -> Heap a -> a
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl a -> a -> a
f ((a -> a -> a) -> Heap a -> a -> a
myfold a -> a -> a
f Heap a
a a
x) Heap a
b)) a
y

toOrdSeq :: forall a (s :: * -> *). (Ord a, Sequence s) => Heap a -> s a
toOrdSeq Heap a
xs = Heap a -> s a -> s a
forall {s :: * -> *} {a}. Sequence s => Heap a -> s a -> s a
tos Heap a
xs s a
forall (s :: * -> *) a. Sequence s => s a
S.empty
  where tos :: Heap a -> s a -> s a
tos Heap a
E s a
rest = s a
rest
        tos (T Heap a
a a
x Heap a
b) s a
rest = Heap a -> s a -> s a
tos Heap a
a (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 (Heap a -> s a -> s a
tos Heap a
b s a
rest))

unsafeMapMonotonic :: forall a b. (a -> b) -> Heap a -> Heap b
unsafeMapMonotonic a -> b
_ Heap a
E = Heap b
forall a. Heap a
E
unsafeMapMonotonic a -> b
f (T Heap a
a a
x Heap a
b) =
  Heap b -> b -> Heap b -> Heap b
forall a. Heap a -> a -> Heap a -> Heap a
T ((a -> b) -> Heap a -> Heap b
forall a b. (a -> b) -> Heap a -> Heap b
unsafeMapMonotonic a -> b
f Heap a
a) (a -> b
f a
x) ((a -> b) -> Heap a -> Heap b
forall a b. (a -> b) -> Heap a -> Heap b
unsafeMapMonotonic a -> b
f Heap a
b)

strict :: forall a. Heap a -> Heap a
strict h :: Heap a
h@Heap a
E = Heap a
h
strict h :: Heap a
h@(T Heap a
l a
_ Heap a
r) = Heap a -> Heap a
forall a. Heap a -> Heap a
strict Heap a
l Heap a -> Heap a -> Heap a
forall a b. a -> b -> b
`seq` Heap a -> Heap a
forall a. Heap a -> Heap a
strict Heap a
r Heap a -> Heap a -> Heap a
forall a b. a -> b -> b
`seq` Heap a
h

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@(T Heap a
l a
x Heap a
r) = a -> b
f a
x b -> Heap a -> Heap a
forall a b. a -> b -> b
`seq` (a -> b) -> Heap a -> Heap a
forall a b. (a -> b) -> Heap a -> Heap a
strictWith a -> b
f Heap a
l Heap a -> Heap a -> Heap a
forall a b. a -> b -> b
`seq` (a -> b) -> Heap a -> Heap a
forall a b. (a -> b) -> Heap a -> Heap a
strictWith a -> b
f Heap a
r Heap a -> Heap a -> Heap a
forall a b. a -> b -> b
`seq` Heap a
h

-- the remaining functions all use defaults

fromSeq :: forall a (s :: * -> *). (Ord a, Sequence s) => s a -> Heap a
fromSeq = s a -> Heap a
forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
fromSeqUsingFoldr
insertSeq :: forall a (s :: * -> *).
(Ord a, Sequence s) =>
s a -> Heap a -> Heap a
insertSeq = s a -> Heap a -> Heap a
forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
insertSeqUsingFoldr
unionSeq :: forall a (s :: * -> *). (Ord a, Sequence s) => s (Heap a) -> Heap a
unionSeq = s (Heap a) -> Heap a
forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingReduce
deleteSeq :: forall a (s :: * -> *).
(Ord a, Sequence s) =>
s a -> Heap a -> Heap a
deleteSeq = s a -> Heap a -> Heap a
forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
deleteSeqUsingDelete
unsafeFromOrdSeq :: forall a (s :: * -> *). (Ord a, Sequence s) => s a -> Heap a
unsafeFromOrdSeq = s a -> Heap a
forall c a (seq :: * -> *).
(OrdCollX c a, Sequence seq) =>
seq a -> c
unsafeFromOrdSeqUsingUnsafeInsertMin

-- instance declarations

instance Ord a => C.CollX (Heap a) a where
  {singleton :: a -> Heap a
singleton = a -> Heap a
forall a. a -> Heap a
singleton; fromSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Heap a
fromSeq = seq a -> Heap a
forall a (s :: * -> *). (Ord a, Sequence s) => s a -> Heap a
fromSeq; insert :: a -> Heap a -> Heap a
insert = a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
insert;
   insertSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Heap a -> Heap a
insertSeq = seq a -> Heap a -> Heap a
forall a (s :: * -> *).
(Ord a, Sequence s) =>
s a -> Heap a -> Heap a
insertSeq; unionSeq :: forall (seq :: * -> *). Sequence seq => seq (Heap a) -> Heap a
unionSeq = seq (Heap a) -> Heap a
forall a (s :: * -> *). (Ord a, Sequence s) => s (Heap a) -> Heap a
unionSeq;
   delete :: a -> Heap a -> Heap a
delete = a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
delete; deleteAll :: a -> Heap a -> Heap a
deleteAll = a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
deleteAll; deleteSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Heap a -> Heap a
deleteSeq = seq a -> Heap a -> Heap a
forall a (s :: * -> *).
(Ord a, Sequence s) =>
s a -> Heap a -> Heap a
deleteSeq;
   null :: Heap a -> Bool
null = Heap a -> Bool
forall a. Heap a -> Bool
null; size :: Heap a -> Int
size = Heap a -> Int
forall a. Heap a -> Int
size; member :: a -> Heap a -> Bool
member = a -> Heap a -> Bool
forall a. Ord a => a -> Heap a -> Bool
member; count :: a -> Heap a -> Int
count = a -> Heap a -> Int
forall a. Ord a => a -> Heap a -> Int
count;
   strict :: Heap a -> Heap a
strict = Heap a -> Heap a
forall a. Heap a -> Heap a
strict;
   structuralInvariant :: Heap a -> Bool
structuralInvariant = Heap a -> Bool
forall a. Ord 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 = Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a
deleteMin; deleteMax :: Heap a -> Heap a
deleteMax = Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a
deleteMax;
   unsafeInsertMin :: a -> Heap a -> Heap a
unsafeInsertMin = a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
unsafeInsertMin; unsafeInsertMax :: a -> Heap a -> Heap a
unsafeInsertMax = a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
unsafeInsertMax;
   unsafeFromOrdSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Heap a
unsafeFromOrdSeq = seq a -> Heap a
forall a (s :: * -> *). (Ord a, Sequence s) => s a -> Heap a
unsafeFromOrdSeq; unsafeAppend :: Heap a -> Heap a -> Heap a
unsafeAppend = Heap a -> Heap a -> Heap a
forall a. Ord a => Heap a -> Heap a -> Heap a
unsafeAppend;
   filterLT :: a -> Heap a -> Heap a
filterLT = a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLT; filterLE :: a -> Heap a -> Heap a
filterLE = a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterLE; filterGT :: a -> Heap a -> Heap a
filterGT = a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGT;
   filterGE :: a -> Heap a -> Heap a
filterGE = a -> Heap a -> Heap a
forall a. Ord a => a -> Heap a -> Heap a
filterGE; partitionLT_GE :: a -> Heap a -> (Heap a, Heap a)
partitionLT_GE = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GE;
   partitionLE_GT :: a -> Heap a -> (Heap a, Heap a)
partitionLE_GT = a -> Heap a -> (Heap a, Heap a)
forall a. Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT; partitionLT_GT :: a -> Heap a -> (Heap a, Heap a)
partitionLT_GT = a -> Heap a -> (Heap a, Heap a)
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 = Heap a -> seq a
forall a (s :: * -> *). (Ord a, Sequence s) => Heap a -> s a
toSeq; lookup :: a -> Heap a -> a
lookup = a -> Heap a -> a
forall a. Ord a => a -> Heap a -> a
lookup; lookupM :: forall (m :: * -> *). MonadFail m => a -> Heap a -> m a
lookupM = a -> Heap a -> m a
forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Heap a -> m a
lookupM;
   lookupAll :: forall (seq :: * -> *). Sequence seq => a -> Heap a -> seq a
lookupAll = a -> Heap a -> seq a
forall a (s :: * -> *). (Ord a, Sequence s) => a -> Heap a -> s a
lookupAll; lookupWithDefault :: a -> a -> Heap a -> a
lookupWithDefault = a -> a -> Heap a -> a
forall a. Ord a => a -> a -> Heap a -> a
lookupWithDefault;
   fold :: forall b. (a -> b -> b) -> b -> Heap a -> b
fold = (a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold; fold' :: forall b. (a -> b -> b) -> b -> Heap a -> b
fold' = (a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
fold'; fold1 :: (a -> a -> a) -> Heap a -> a
fold1 = (a -> a -> a) -> Heap a -> a
forall a. Ord a => (a -> a -> a) -> Heap a -> a
fold1; fold1' :: (a -> a -> a) -> Heap a -> a
fold1' = (a -> a -> a) -> Heap a -> a
forall a. Ord a => (a -> a -> a) -> Heap a -> a
fold1';
   strictWith :: forall b. (a -> b) -> Heap a -> Heap a
strictWith = (a -> b) -> Heap a -> Heap a
forall a b. (a -> b) -> Heap a -> Heap a
strictWith;
   filter :: (a -> Bool) -> Heap a -> Heap a
filter = (a -> Bool) -> Heap a -> Heap a
forall a. Ord a => (a -> Bool) -> Heap a -> Heap a
filter; partition :: (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition = (a -> Bool) -> Heap a -> (Heap a, Heap a)
forall a. Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
partition}

instance Ord a => C.OrdColl (Heap a) a where
  {minView :: forall (m :: * -> *). MonadFail m => Heap a -> m (a, Heap a)
minView = Heap a -> m (a, Heap a)
forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
minView; minElem :: Heap a -> a
minElem = Heap a -> a
forall a. Ord a => Heap a -> a
minElem; maxView :: forall (m :: * -> *). MonadFail m => Heap a -> m (a, Heap a)
maxView = Heap a -> m (a, Heap a)
forall a (m :: * -> *).
(Ord a, MonadFail m) =>
Heap a -> m (a, Heap a)
maxView;
   maxElem :: Heap a -> a
maxElem = Heap a -> a
forall a. Ord a => Heap a -> a
maxElem; foldr :: forall b. (a -> b -> b) -> b -> Heap a -> b
foldr = (a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr; foldr' :: forall b. (a -> b -> b) -> b -> Heap a -> b
foldr' = (a -> b -> b) -> b -> Heap a -> b
forall a b. Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr'; foldl :: forall b. (b -> a -> b) -> b -> Heap a -> b
foldl = (b -> a -> b) -> b -> Heap a -> b
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl;
   foldl' :: forall b. (b -> a -> b) -> b -> Heap a -> b
foldl' = (b -> a -> b) -> b -> Heap a -> b
forall a b. Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl'; foldr1 :: (a -> a -> a) -> Heap a -> a
foldr1 = (a -> a -> a) -> Heap a -> a
forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1; foldr1' :: (a -> a -> a) -> Heap a -> a
foldr1' = (a -> a -> a) -> Heap a -> a
forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldr1';
   foldl1 :: (a -> a -> a) -> Heap a -> a
foldl1 = (a -> a -> a) -> Heap a -> a
forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldl1; foldl1' :: (a -> a -> a) -> Heap a -> a
foldl1' = (a -> a -> a) -> Heap a -> a
forall a. Ord a => (a -> a -> a) -> Heap a -> a
foldl1'; toOrdSeq :: forall (seq :: * -> *). Sequence seq => Heap a -> seq a
toOrdSeq = Heap a -> seq a
forall a (s :: * -> *). (Ord a, Sequence s) => Heap a -> s a
toOrdSeq;
   unsafeMapMonotonic :: (a -> a) -> Heap a -> Heap a
unsafeMapMonotonic = (a -> a) -> Heap a -> Heap a
forall a 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 = Heap a -> [a]
forall c a. OrdColl c a => c -> [a]
C.toOrdList Heap a
xs [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== Heap a -> [a]
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 = Int -> Heap a -> ShowS
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 = Int -> ReadS (Heap a)
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 = do [a]
xs <- Gen [a]
forall a. Arbitrary a => Gen a
arbitrary
                 Heap a -> Gen (Heap a)
forall a. a -> Gen a
forall (m :: * -> *) a. Monad m => a -> m a
return ([a] -> Heap a
forall c a. CollX c a => [a] -> c
C.fromList [a]
xs)

instance (Ord a,CoArbitrary a) => CoArbitrary (Heap a) where
  coarbitrary :: forall b. Heap a -> Gen b -> Gen b
coarbitrary Heap a
E = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
  coarbitrary (T Heap a
a a
x Heap a
b) =
    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
. Heap a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
forall b. Heap a -> Gen b -> Gen b
coarbitrary Heap a
a (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
. Heap a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
forall b. Heap a -> Gen b -> Gen b
coarbitrary Heap a
b

instance (Ord a) => Semigroup (Heap a) where
    <> :: Heap a -> Heap a -> Heap a
(<>) = 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  = Heap a
forall a. Heap a
empty
    mappend :: Heap a -> Heap a -> Heap a
mappend = Heap a -> Heap a -> Heap a
forall a. Semigroup a => a -> a -> a
(SG.<>)
    mconcat :: [Heap a] -> Heap a
mconcat = [Heap a] -> Heap a
forall a (s :: * -> *). (Ord a, Sequence s) => s (Heap a) -> Heap a
unionSeq

instance (Ord a) => Ord (Heap a) where
    compare :: Heap a -> Heap a -> Ordering
compare = Heap a -> Heap a -> Ordering
forall c a. OrdColl c a => c -> c -> Ordering
compareUsingToOrdList