{-# LANGUAGE NoMonomorphismRestriction #-}
module Data.Heap.Class (Heap(..), Entry(..), union, uncons) where
import Data.Entry (Entry (..))

-- | Synonym for @'merge'@.
union :: (Ord a, Heap f) => f a -> f a -> f a
union :: f a -> f a -> f a
union = f a -> f a -> f a
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> f a -> f a
merge
{-# INLINE union #-}

-- | Synonym for @'viewMin'@.
uncons :: (Ord a, Heap f) => f a -> Maybe (a, f a)
uncons :: f a -> Maybe (a, f a)
uncons = f a -> Maybe (a, f a)
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> Maybe (a, f a)
viewMin
{-# INLINE uncons #-}

class Heap f where
  empty     :: Ord a => f a
  null      :: Ord a => f a -> Bool
  insert    :: Ord a =>   a -> f a -> f a
  merge     :: Ord a => f a -> f a -> f a
  findMin   :: Ord a => f a -> Maybe a
  deleteMin :: Ord a => f a -> Maybe (f a)
  singleton :: Ord a => a -> f a
  singleton = (a -> f a -> f a) -> f a -> a -> f a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> f a -> f a
forall (f :: * -> *) a. (Heap f, Ord a) => a -> f a -> f a
insert f a
forall (f :: * -> *) a. (Heap f, Ord a) => f a
empty
  {-# INLINE singleton #-}
  viewMin :: Ord a => f a -> Maybe (a, f a)
  viewMin f a
q = (,) (a -> f a -> (a, f a)) -> Maybe a -> Maybe (f a -> (a, f a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f a -> Maybe a
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> Maybe a
findMin f a
q Maybe (f a -> (a, f a)) -> Maybe (f a) -> Maybe (a, f a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> f a -> Maybe (f a)
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> Maybe (f a)
deleteMin f a
q
  {-# INLINE viewMin #-}
  fromList :: Ord a => [a] -> f a
  fromList = (a -> f a -> f a) -> f a -> [a] -> f a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> f a -> f a
forall (f :: * -> *) a. (Heap f, Ord a) => a -> f a -> f a
insert f a
forall (f :: * -> *) a. (Heap f, Ord a) => f a
empty
  {-# INLINE fromList #-}
  toList :: Ord a => f a -> [a]
  toList =
    let go :: f a -> [a]
go f a
q =
          case f a -> Maybe (a, f a)
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> Maybe (a, f a)
viewMin f a
q of
            Maybe (a, f a)
Nothing -> []
            Just (a
x, f a
q') -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: f a -> [a]
go f a
q'
    in f a -> [a]
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> [a]
go
  {-# INLINE toList #-}
  span :: Ord a => (a -> Bool) -> f a -> (f a, f a)
  span a -> Bool
p =
    let go :: f a -> (f a, f a)
go f a
q =
          case f a -> Maybe (a, f a)
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> Maybe (a, f a)
viewMin f a
q of
            Maybe (a, f a)
Nothing -> (f a
forall (f :: * -> *) a. (Heap f, Ord a) => f a
empty, f a
q)
            Just (a
x, f a
r)
              | a -> Bool
p a
x -> let (f a
yes, f a
no) = f a -> (f a, f a)
go f a
r
                       in (a -> f a -> f a
forall (f :: * -> *) a. (Heap f, Ord a) => a -> f a -> f a
insert a
x f a
yes, f a
no)
              | Bool
otherwise -> (f a
forall (f :: * -> *) a. (Heap f, Ord a) => f a
empty, f a
q)
    in f a -> (f a, f a)
go
  {-# INLINE span #-}