-- | 

module Control.Comonad.Heap.Pointed
  (Heap(..)
  ,Root
  ,pattern Root
  ,popMin
  ,singleton
  ,(<+>)
  ,dijkstra
  ,monusSort
  ,fromList)
  where

import qualified Control.Comonad.Heap as NonEmpty
import Control.Comonad.Heap (pattern Root)

import qualified Data.Set as Set

import Data.Data ( Data, Typeable )
import GHC.Generics ( Generic, Generic1 )
import Control.DeepSeq (NFData(..))

import Control.Applicative
import Test.QuickCheck
import Data.Bifunctor
import Data.Bifoldable
import Data.Bitraversable

import Data.List (unfoldr)

import Data.Monus
import Data.Monus.Dist
import Data.Monus.Max
import Data.Tuple (swap)
import Data.List.NonEmpty (nonEmpty)

type Root = NonEmpty.Heap

data Heap w a
  = Leaf
  | Node {-# UNPACK #-} !(Root w a)
  deriving (Int -> Heap w a -> ShowS
[Heap w a] -> ShowS
Heap w a -> String
(Int -> Heap w a -> ShowS)
-> (Heap w a -> String) -> ([Heap w a] -> ShowS) -> Show (Heap w a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall w a. (Show w, Show a) => Int -> Heap w a -> ShowS
forall w a. (Show w, Show a) => [Heap w a] -> ShowS
forall w a. (Show w, Show a) => Heap w a -> String
showList :: [Heap w a] -> ShowS
$cshowList :: forall w a. (Show w, Show a) => [Heap w a] -> ShowS
show :: Heap w a -> String
$cshow :: forall w a. (Show w, Show a) => Heap w a -> String
showsPrec :: Int -> Heap w a -> ShowS
$cshowsPrec :: forall w a. (Show w, Show a) => Int -> Heap w a -> ShowS
Show, ReadPrec [Heap w a]
ReadPrec (Heap w a)
Int -> ReadS (Heap w a)
ReadS [Heap w a]
(Int -> ReadS (Heap w a))
-> ReadS [Heap w a]
-> ReadPrec (Heap w a)
-> ReadPrec [Heap w a]
-> Read (Heap w a)
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
forall w a. (Read w, Read a) => ReadPrec [Heap w a]
forall w a. (Read w, Read a) => ReadPrec (Heap w a)
forall w a. (Read w, Read a) => Int -> ReadS (Heap w a)
forall w a. (Read w, Read a) => ReadS [Heap w a]
readListPrec :: ReadPrec [Heap w a]
$creadListPrec :: forall w a. (Read w, Read a) => ReadPrec [Heap w a]
readPrec :: ReadPrec (Heap w a)
$creadPrec :: forall w a. (Read w, Read a) => ReadPrec (Heap w a)
readList :: ReadS [Heap w a]
$creadList :: forall w a. (Read w, Read a) => ReadS [Heap w a]
readsPrec :: Int -> ReadS (Heap w a)
$creadsPrec :: forall w a. (Read w, Read a) => Int -> ReadS (Heap w a)
Read, Heap w a -> Heap w a -> Bool
(Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Bool) -> Eq (Heap w a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall w a. (Eq w, Eq a) => Heap w a -> Heap w a -> Bool
/= :: Heap w a -> Heap w a -> Bool
$c/= :: forall w a. (Eq w, Eq a) => Heap w a -> Heap w a -> Bool
== :: Heap w a -> Heap w a -> Bool
$c== :: forall w a. (Eq w, Eq a) => Heap w a -> Heap w a -> Bool
Eq, Eq (Heap w a)
Eq (Heap w a)
-> (Heap w a -> Heap w a -> Ordering)
-> (Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Heap w a)
-> (Heap w a -> Heap w a -> Heap w a)
-> Ord (Heap w a)
Heap w a -> Heap w a -> Bool
Heap w a -> Heap w a -> Ordering
Heap w a -> Heap w a -> Heap w a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {w} {a}. (Ord w, Ord a) => Eq (Heap w a)
forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Ordering
forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Heap w a
min :: Heap w a -> Heap w a -> Heap w a
$cmin :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Heap w a
max :: Heap w a -> Heap w a -> Heap w a
$cmax :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Heap w a
>= :: Heap w a -> Heap w a -> Bool
$c>= :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
> :: Heap w a -> Heap w a -> Bool
$c> :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
<= :: Heap w a -> Heap w a -> Bool
$c<= :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
< :: Heap w a -> Heap w a -> Bool
$c< :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
compare :: Heap w a -> Heap w a -> Ordering
$ccompare :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Ordering
Ord, (forall a b. (a -> b) -> Heap w a -> Heap w b)
-> (forall a b. a -> Heap w b -> Heap w a) -> Functor (Heap w)
forall a b. a -> Heap w b -> Heap w a
forall a b. (a -> b) -> Heap w a -> Heap w b
forall w a b. a -> Heap w b -> Heap w a
forall w a b. (a -> b) -> Heap w a -> Heap w b
forall (f :: Type -> Type).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> Heap w b -> Heap w a
$c<$ :: forall w a b. a -> Heap w b -> Heap w a
fmap :: forall a b. (a -> b) -> Heap w a -> Heap w b
$cfmap :: forall w a b. (a -> b) -> Heap w a -> Heap w b
Functor, (forall m. Monoid m => Heap w m -> m)
-> (forall m a. Monoid m => (a -> m) -> Heap w a -> m)
-> (forall m a. Monoid m => (a -> m) -> Heap w a -> m)
-> (forall a b. (a -> b -> b) -> b -> Heap w a -> b)
-> (forall a b. (a -> b -> b) -> b -> Heap w a -> b)
-> (forall b a. (b -> a -> b) -> b -> Heap w a -> b)
-> (forall b a. (b -> a -> b) -> b -> Heap w a -> b)
-> (forall a. (a -> a -> a) -> Heap w a -> a)
-> (forall a. (a -> a -> a) -> Heap w a -> a)
-> (forall a. Heap w a -> [a])
-> (forall a. Heap w a -> Bool)
-> (forall a. Heap w a -> Int)
-> (forall a. Eq a => a -> Heap w a -> Bool)
-> (forall a. Ord a => Heap w a -> a)
-> (forall a. Ord a => Heap w a -> a)
-> (forall a. Num a => Heap w a -> a)
-> (forall a. Num a => Heap w a -> a)
-> Foldable (Heap w)
forall a. Eq a => a -> Heap w a -> Bool
forall a. Num a => Heap w a -> a
forall a. Ord a => Heap w a -> a
forall m. Monoid m => Heap w m -> m
forall a. Heap w a -> Bool
forall a. Heap w a -> Int
forall a. Heap w a -> [a]
forall a. (a -> a -> a) -> Heap w a -> a
forall w a. Eq a => a -> Heap w a -> Bool
forall w a. Num a => Heap w a -> a
forall w a. Ord a => Heap w a -> a
forall m a. Monoid m => (a -> m) -> Heap w a -> m
forall w m. Monoid m => Heap w m -> m
forall w a. Heap w a -> Bool
forall w a. Heap w a -> Int
forall w a. Heap w a -> [a]
forall b a. (b -> a -> b) -> b -> Heap w a -> b
forall a b. (a -> b -> b) -> b -> Heap w a -> b
forall w a. (a -> a -> a) -> Heap w a -> a
forall w m a. Monoid m => (a -> m) -> Heap w a -> m
forall w b a. (b -> a -> b) -> b -> Heap w a -> b
forall w a b. (a -> b -> b) -> b -> Heap w a -> b
forall (t :: Type -> Type).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: forall a. Num a => Heap w a -> a
$cproduct :: forall w a. Num a => Heap w a -> a
sum :: forall a. Num a => Heap w a -> a
$csum :: forall w a. Num a => Heap w a -> a
minimum :: forall a. Ord a => Heap w a -> a
$cminimum :: forall w a. Ord a => Heap w a -> a
maximum :: forall a. Ord a => Heap w a -> a
$cmaximum :: forall w a. Ord a => Heap w a -> a
elem :: forall a. Eq a => a -> Heap w a -> Bool
$celem :: forall w a. Eq a => a -> Heap w a -> Bool
length :: forall a. Heap w a -> Int
$clength :: forall w a. Heap w a -> Int
null :: forall a. Heap w a -> Bool
$cnull :: forall w a. Heap w a -> Bool
toList :: forall a. Heap w a -> [a]
$ctoList :: forall w a. Heap w a -> [a]
foldl1 :: forall a. (a -> a -> a) -> Heap w a -> a
$cfoldl1 :: forall w a. (a -> a -> a) -> Heap w a -> a
foldr1 :: forall a. (a -> a -> a) -> Heap w a -> a
$cfoldr1 :: forall w a. (a -> a -> a) -> Heap w a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> Heap w a -> b
$cfoldl' :: forall w b a. (b -> a -> b) -> b -> Heap w a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Heap w a -> b
$cfoldl :: forall w b a. (b -> a -> b) -> b -> Heap w a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Heap w a -> b
$cfoldr' :: forall w a b. (a -> b -> b) -> b -> Heap w a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Heap w a -> b
$cfoldr :: forall w a b. (a -> b -> b) -> b -> Heap w a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> Heap w a -> m
$cfoldMap' :: forall w m a. Monoid m => (a -> m) -> Heap w a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Heap w a -> m
$cfoldMap :: forall w m a. Monoid m => (a -> m) -> Heap w a -> m
fold :: forall m. Monoid m => Heap w m -> m
$cfold :: forall w m. Monoid m => Heap w m -> m
Foldable, Functor (Heap w)
Foldable (Heap w)
Functor (Heap w)
-> Foldable (Heap w)
-> (forall (f :: Type -> Type) a b.
    Applicative f =>
    (a -> f b) -> Heap w a -> f (Heap w b))
-> (forall (f :: Type -> Type) a.
    Applicative f =>
    Heap w (f a) -> f (Heap w a))
-> (forall (m :: Type -> Type) a b.
    Monad m =>
    (a -> m b) -> Heap w a -> m (Heap w b))
-> (forall (m :: Type -> Type) a.
    Monad m =>
    Heap w (m a) -> m (Heap w a))
-> Traversable (Heap w)
forall w. Functor (Heap w)
forall w. Foldable (Heap w)
forall w (m :: Type -> Type) a.
Monad m =>
Heap w (m a) -> m (Heap w a)
forall w (f :: Type -> Type) a.
Applicative f =>
Heap w (f a) -> f (Heap w a)
forall w (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Heap w a -> m (Heap w b)
forall w (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Heap w a -> f (Heap w b)
forall (t :: Type -> Type).
Functor t
-> Foldable t
-> (forall (f :: Type -> Type) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: Type -> Type) a.
    Applicative f =>
    t (f a) -> f (t a))
-> (forall (m :: Type -> Type) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: Type -> Type) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: Type -> Type) a.
Monad m =>
Heap w (m a) -> m (Heap w a)
forall (f :: Type -> Type) a.
Applicative f =>
Heap w (f a) -> f (Heap w a)
forall (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Heap w a -> m (Heap w b)
forall (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Heap w a -> f (Heap w b)
sequence :: forall (m :: Type -> Type) a.
Monad m =>
Heap w (m a) -> m (Heap w a)
$csequence :: forall w (m :: Type -> Type) a.
Monad m =>
Heap w (m a) -> m (Heap w a)
mapM :: forall (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Heap w a -> m (Heap w b)
$cmapM :: forall w (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Heap w a -> m (Heap w b)
sequenceA :: forall (f :: Type -> Type) a.
Applicative f =>
Heap w (f a) -> f (Heap w a)
$csequenceA :: forall w (f :: Type -> Type) a.
Applicative f =>
Heap w (f a) -> f (Heap w a)
traverse :: forall (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Heap w a -> f (Heap w b)
$ctraverse :: forall w (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Heap w a -> f (Heap w b)
Traversable, Typeable (Heap w a)
Typeable (Heap w a)
-> (forall (c :: Type -> Type).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Heap w a -> c (Heap w a))
-> (forall (c :: Type -> Type).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Heap w a))
-> (Heap w a -> Constr)
-> (Heap w a -> DataType)
-> (forall (t :: Type -> Type) (c :: Type -> Type).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (Heap w a)))
-> (forall (t :: Type -> Type -> Type) (c :: Type -> Type).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (Heap w a)))
-> ((forall b. Data b => b -> b) -> Heap w a -> Heap w a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Heap w a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Heap w a -> r)
-> (forall u. (forall d. Data d => d -> u) -> Heap w a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> Heap w a -> u)
-> (forall (m :: Type -> Type).
    Monad m =>
    (forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a))
-> (forall (m :: Type -> Type).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a))
-> (forall (m :: Type -> Type).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a))
-> Data (Heap w a)
Heap w a -> DataType
Heap w a -> Constr
(forall b. Data b => b -> b) -> Heap w a -> Heap w a
forall a.
Typeable a
-> (forall (c :: Type -> Type).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: Type -> Type).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: Type -> Type) (c :: Type -> Type).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: Type -> Type -> Type) (c :: Type -> Type).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: Type -> Type).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: Type -> Type).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: Type -> Type).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> Heap w a -> u
forall u. (forall d. Data d => d -> u) -> Heap w a -> [u]
forall {w} {a}. (Data w, Data a) => Typeable (Heap w a)
forall w a. (Data w, Data a) => Heap w a -> DataType
forall w a. (Data w, Data a) => Heap w a -> Constr
forall w a.
(Data w, Data a) =>
(forall b. Data b => b -> b) -> Heap w a -> Heap w a
forall w a u.
(Data w, Data a) =>
Int -> (forall d. Data d => d -> u) -> Heap w a -> u
forall w a u.
(Data w, Data a) =>
(forall d. Data d => d -> u) -> Heap w a -> [u]
forall w a r r'.
(Data w, Data a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
forall w a r r'.
(Data w, Data a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
forall w a (m :: Type -> Type).
(Data w, Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
forall w a (m :: Type -> Type).
(Data w, Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
forall w a (c :: Type -> Type).
(Data w, Data a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Heap w a)
forall w a (c :: Type -> Type).
(Data w, Data a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Heap w a -> c (Heap w a)
forall w a (t :: Type -> Type) (c :: Type -> Type).
(Data w, Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Heap w a))
forall w a (t :: Type -> Type -> Type) (c :: Type -> Type).
(Data w, Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Heap w a))
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
forall (m :: Type -> Type).
Monad m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
forall (m :: Type -> Type).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
forall (c :: Type -> Type).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Heap w a)
forall (c :: Type -> Type).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Heap w a -> c (Heap w a)
forall (t :: Type -> Type) (c :: Type -> Type).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Heap w a))
forall (t :: Type -> Type -> Type) (c :: Type -> Type).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Heap w a))
gmapMo :: forall (m :: Type -> Type).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
$cgmapMo :: forall w a (m :: Type -> Type).
(Data w, Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
gmapMp :: forall (m :: Type -> Type).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
$cgmapMp :: forall w a (m :: Type -> Type).
(Data w, Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
gmapM :: forall (m :: Type -> Type).
Monad m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
$cgmapM :: forall w a (m :: Type -> Type).
(Data w, Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Heap w a -> u
$cgmapQi :: forall w a u.
(Data w, Data a) =>
Int -> (forall d. Data d => d -> u) -> Heap w a -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> Heap w a -> [u]
$cgmapQ :: forall w a u.
(Data w, Data a) =>
(forall d. Data d => d -> u) -> Heap w a -> [u]
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
$cgmapQr :: forall w a r r'.
(Data w, Data a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
$cgmapQl :: forall w a r r'.
(Data w, Data a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
gmapT :: (forall b. Data b => b -> b) -> Heap w a -> Heap w a
$cgmapT :: forall w a.
(Data w, Data a) =>
(forall b. Data b => b -> b) -> Heap w a -> Heap w a
dataCast2 :: forall (t :: Type -> Type -> Type) (c :: Type -> Type).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Heap w a))
$cdataCast2 :: forall w a (t :: Type -> Type -> Type) (c :: Type -> Type).
(Data w, Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Heap w a))
dataCast1 :: forall (t :: Type -> Type) (c :: Type -> Type).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Heap w a))
$cdataCast1 :: forall w a (t :: Type -> Type) (c :: Type -> Type).
(Data w, Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Heap w a))
dataTypeOf :: Heap w a -> DataType
$cdataTypeOf :: forall w a. (Data w, Data a) => Heap w a -> DataType
toConstr :: Heap w a -> Constr
$ctoConstr :: forall w a. (Data w, Data a) => Heap w a -> Constr
gunfold :: forall (c :: Type -> Type).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Heap w a)
$cgunfold :: forall w a (c :: Type -> Type).
(Data w, Data a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Heap w a)
gfoldl :: forall (c :: Type -> Type).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Heap w a -> c (Heap w a)
$cgfoldl :: forall w a (c :: Type -> Type).
(Data w, Data a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Heap w a -> c (Heap w a)
Data, Typeable, (forall x. Heap w a -> Rep (Heap w a) x)
-> (forall x. Rep (Heap w a) x -> Heap w a) -> Generic (Heap w a)
forall x. Rep (Heap w a) x -> Heap w a
forall x. Heap w a -> Rep (Heap w a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall w a x. Rep (Heap w a) x -> Heap w a
forall w a x. Heap w a -> Rep (Heap w a) x
$cto :: forall w a x. Rep (Heap w a) x -> Heap w a
$cfrom :: forall w a x. Heap w a -> Rep (Heap w a) x
Generic, (forall a. Heap w a -> Rep1 (Heap w) a)
-> (forall a. Rep1 (Heap w) a -> Heap w a) -> Generic1 (Heap w)
forall a. Rep1 (Heap w) a -> Heap w a
forall a. Heap w a -> Rep1 (Heap w) a
forall w a. Rep1 (Heap w) a -> Heap w a
forall w a. Heap w a -> Rep1 (Heap w) a
forall k (f :: k -> Type).
(forall (a :: k). f a -> Rep1 f a)
-> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
$cto1 :: forall w a. Rep1 (Heap w) a -> Heap w a
$cfrom1 :: forall w a. Heap w a -> Rep1 (Heap w) a
Generic1)

heap :: b -> (Root w a -> b) -> Heap w a -> b
heap :: forall b w a. b -> (Root w a -> b) -> Heap w a -> b
heap b
b Root w a -> b
k = \case
  Heap w a
Leaf -> b
b
  Node Root w a
xs -> Root w a -> b
k Root w a
xs
{-# INLINE heap #-}

node :: Maybe (Root w a) -> Heap w a
node :: forall w a. Maybe (Root w a) -> Heap w a
node = Heap w a -> (Root w a -> Heap w a) -> Maybe (Root w a) -> Heap w a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Heap w a
forall w a. Heap w a
Leaf Root w a -> Heap w a
forall w a. Root w a -> Heap w a
Node
{-# INLINE node #-}

root :: Heap w a -> Maybe (Root w a) 
root :: forall w a. Heap w a -> Maybe (Root w a)
root = Maybe (Root w a)
-> (Root w a -> Maybe (Root w a)) -> Heap w a -> Maybe (Root w a)
forall b w a. b -> (Root w a -> b) -> Heap w a -> b
heap Maybe (Root w a)
forall a. Maybe a
Nothing Root w a -> Maybe (Root w a)
forall a. a -> Maybe a
Just
{-# INLINE root #-}

instance (NFData w, NFData a) => NFData (Heap w a) where
  rnf :: Heap w a -> ()
rnf = () -> (Root w a -> ()) -> Heap w a -> ()
forall b w a. b -> (Root w a -> b) -> Heap w a -> b
heap () Root w a -> ()
forall a. NFData a => a -> ()
rnf

instance Bifunctor Heap where
  bimap :: forall a b c d. (a -> b) -> (c -> d) -> Heap a c -> Heap b d
bimap a -> b
f c -> d
g = Heap b d -> (Root a c -> Heap b d) -> Heap a c -> Heap b d
forall b w a. b -> (Root w a -> b) -> Heap w a -> b
heap Heap b d
forall w a. Heap w a
Leaf (Root b d -> Heap b d
forall w a. Root w a -> Heap w a
Node (Root b d -> Heap b d)
-> (Root a c -> Root b d) -> Root a c -> Heap b d
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> (c -> d) -> Root a c -> Root b d
forall (p :: Type -> Type -> Type) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap a -> b
f c -> d
g)

instance Bifoldable Heap where
  bifold :: forall m. Monoid m => Heap m m -> m
bifold = m -> (Root m m -> m) -> Heap m m -> m
forall b w a. b -> (Root w a -> b) -> Heap w a -> b
heap m
forall a. Monoid a => a
mempty Root m m -> m
forall (p :: Type -> Type -> Type) m.
(Bifoldable p, Monoid m) =>
p m m -> m
bifold
  
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> Heap a b -> m
bifoldMap a -> m
f b -> m
g = m -> (Root a b -> m) -> Heap a b -> m
forall b w a. b -> (Root w a -> b) -> Heap w a -> b
heap m
forall a. Monoid a => a
mempty ((a -> m) -> (b -> m) -> Root a b -> m
forall (p :: Type -> Type -> Type) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap a -> m
f b -> m
g)

  bifoldr :: forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> Heap a b -> c
bifoldr a -> c -> c
f b -> c -> c
g c
b = c -> (Root a b -> c) -> Heap a b -> c
forall b w a. b -> (Root w a -> b) -> Heap w a -> b
heap c
b ((a -> c -> c) -> (b -> c -> c) -> c -> Root a b -> c
forall (p :: Type -> Type -> Type) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr a -> c -> c
f b -> c -> c
g c
b)
  bifoldl :: forall c a b. (c -> a -> c) -> (c -> b -> c) -> c -> Heap a b -> c
bifoldl c -> a -> c
f c -> b -> c
g c
b = c -> (Root a b -> c) -> Heap a b -> c
forall b w a. b -> (Root w a -> b) -> Heap w a -> b
heap c
b ((c -> a -> c) -> (c -> b -> c) -> c -> Root a b -> c
forall (p :: Type -> Type -> Type) c a b.
Bifoldable p =>
(c -> a -> c) -> (c -> b -> c) -> c -> p a b -> c
bifoldl c -> a -> c
f c -> b -> c
g c
b)

instance Bitraversable Heap where
  bitraverse :: forall (f :: Type -> Type) a c b d.
Applicative f =>
(a -> f c) -> (b -> f d) -> Heap a b -> f (Heap c d)
bitraverse a -> f c
f b -> f d
g Heap a b
Leaf = Heap c d -> f (Heap c d)
forall (f :: Type -> Type) a. Applicative f => a -> f a
pure Heap c d
forall w a. Heap w a
Leaf
  bitraverse a -> f c
f b -> f d
g (Node (Root a
w b
x [Heap a b]
xs)) = (c -> d -> [Heap c d] -> Heap c d)
-> f c -> f d -> f [Heap c d] -> f (Heap c d)
forall (f :: Type -> Type) a b c d.
Applicative f =>
(a -> b -> c -> d) -> f a -> f b -> f c -> f d
liftA3 (\c
w' d
x' [Heap c d]
xs' -> Heap c d -> Heap c d
forall w a. Root w a -> Heap w a
Node (c -> d -> [Heap c d] -> Heap c d
forall w a. w -> a -> [Heap w a] -> Heap w a
Root c
w' d
x' [Heap c d]
xs')) (a -> f c
f a
w) (b -> f d
g b
x) ((Heap a b -> f (Heap c d)) -> [Heap a b] -> f [Heap c d]
forall (t :: Type -> Type) (f :: Type -> Type) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((a -> f c) -> (b -> f d) -> Heap a b -> f (Heap c d)
forall (t :: Type -> Type -> Type) (f :: Type -> Type) a c b d.
(Bitraversable t, Applicative f) =>
(a -> f c) -> (b -> f d) -> t a b -> f (t c d)
bitraverse a -> f c
f b -> f d
g) [Heap a b]
xs)

instance Arbitrary2 Heap where
  liftArbitrary2 :: forall a b. Gen a -> Gen b -> Gen (Heap a b)
liftArbitrary2 Gen a
ls Gen b
rs = (Int -> Gen (Heap a b)) -> Gen (Heap a b)
forall a. (Int -> Gen a) -> Gen a
sized (\Int
n -> [(Int, Gen (Heap a b))] -> Gen (Heap a b)
forall a. [(Int, Gen a)] -> Gen a
frequency [(Int
1, Heap a b -> Gen (Heap a b)
forall (f :: Type -> Type) a. Applicative f => a -> f a
pure Heap a b
forall w a. Heap w a
Leaf), (Int
n, (Root a b -> Heap a b) -> Gen (Root a b) -> Gen (Heap a b)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap Root a b -> Heap a b
forall w a. Root w a -> Heap w a
Node (Gen a -> Gen b -> Gen (Root a b)
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
Gen a -> Gen b -> Gen (f a b)
liftArbitrary2 Gen a
ls Gen b
rs))])
  liftShrink2 :: forall a b. (a -> [a]) -> (b -> [b]) -> Heap a b -> [Heap a b]
liftShrink2 a -> [a]
_ b -> [b]
_ Heap a b
Leaf = []
  liftShrink2 a -> [a]
ls b -> [b]
rs (Node Root a b
x) = Heap a b
forall w a. Heap w a
Leaf Heap a b -> [Heap a b] -> [Heap a b]
forall a. a -> [a] -> [a]
: (Root a b -> Heap a b) -> [Root a b] -> [Heap a b]
forall a b. (a -> b) -> [a] -> [b]
map Root a b -> Heap a b
forall w a. Root w a -> Heap w a
Node ((a -> [a]) -> (b -> [b]) -> Root a b -> [Root a b]
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
(a -> [a]) -> (b -> [b]) -> f a b -> [f a b]
liftShrink2 a -> [a]
ls b -> [b]
rs Root a b
x)
  
instance Arbitrary w => Arbitrary1 (Heap w) where
  liftArbitrary :: forall a. Gen a -> Gen (Heap w a)
liftArbitrary = Gen w -> Gen a -> Gen (Heap w a)
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
Gen a -> Gen b -> Gen (f a b)
liftArbitrary2 Gen w
forall a. Arbitrary a => Gen a
arbitrary
  liftShrink :: forall a. (a -> [a]) -> Heap w a -> [Heap w a]
liftShrink = (w -> [w]) -> (a -> [a]) -> Heap w a -> [Heap w a]
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
(a -> [a]) -> (b -> [b]) -> f a b -> [f a b]
liftShrink2 w -> [w]
forall a. Arbitrary a => a -> [a]
shrink
  
instance (Arbitrary w, Arbitrary a) => Arbitrary (Heap w a) where
  arbitrary :: Gen (Heap w a)
arbitrary = Gen w -> Gen a -> Gen (Heap w a)
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
Gen a -> Gen b -> Gen (f a b)
liftArbitrary2 Gen w
forall a. Arbitrary a => Gen a
arbitrary Gen a
forall a. Arbitrary a => Gen a
arbitrary
  shrink :: Heap w a -> [Heap w a]
shrink = (w -> [w]) -> (a -> [a]) -> Heap w a -> [Heap w a]
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
(a -> [a]) -> (b -> [b]) -> f a b -> [f a b]
liftShrink2 w -> [w]
forall a. Arbitrary a => a -> [a]
shrink a -> [a]
forall a. Arbitrary a => a -> [a]
shrink

(<+>) :: Monus w => Heap w a -> Heap w a -> Heap w a
Heap w a
Leaf <+> :: forall w a. Monus w => Heap w a -> Heap w a -> Heap w a
<+> Heap w a
ys = Heap w a
ys
Heap w a
xs <+> Heap w a
Leaf = Heap w a
xs
Node Root w a
xs <+> Node Root w a
ys = Root w a -> Heap w a
forall w a. Root w a -> Heap w a
Node (Root w a
xs Root w a -> Root w a -> Root w a
forall w a. Monus w => Heap w a -> Heap w a -> Heap w a
NonEmpty.<+> Root w a
ys)
{-# INLINE (<+>) #-}

popMin :: Monus w => Heap w a -> Maybe ((w, a), Heap w a)
popMin :: forall w a. Monus w => Heap w a -> Maybe ((w, a), Heap w a)
popMin = (Heap w a -> ((w, a), Heap w a))
-> Maybe (Heap w a) -> Maybe ((w, a), Heap w a)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Maybe (Heap w a) -> Heap w a)
-> ((w, a), Maybe (Heap w a)) -> ((w, a), Heap w a)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap Maybe (Heap w a) -> Heap w a
forall w a. Maybe (Root w a) -> Heap w a
node (((w, a), Maybe (Heap w a)) -> ((w, a), Heap w a))
-> (Heap w a -> ((w, a), Maybe (Heap w a)))
-> Heap w a
-> ((w, a), Heap w a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Heap w a -> ((w, a), Maybe (Heap w a))
forall w a. Monus w => Heap w a -> ((w, a), Maybe (Heap w a))
NonEmpty.popMin) (Maybe (Heap w a) -> Maybe ((w, a), Heap w a))
-> (Heap w a -> Maybe (Heap w a))
-> Heap w a
-> Maybe ((w, a), Heap w a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Heap w a -> Maybe (Heap w a)
forall w a. Heap w a -> Maybe (Root w a)
root
{-# INLINE popMin #-}

(<><) :: Semigroup w => w -> Heap w a -> Heap w a
w
w <>< :: forall w a. Semigroup w => w -> Heap w a -> Heap w a
<>< Heap w a
Leaf = Heap w a
forall w a. Heap w a
Leaf
w
w <>< Node (Root w
w' a
x [Heap w a]
xs) = Heap w a -> Heap w a
forall w a. Root w a -> Heap w a
Node (w -> a -> [Heap w a] -> Heap w a
forall w a. w -> a -> [Heap w a] -> Heap w a
Root (w
w w -> w -> w
forall a. Semigroup a => a -> a -> a
<> w
w') a
x [Heap w a]
xs)
{-# INLINE (<><) #-}

singleton :: w -> a -> Heap w a
singleton :: forall w a. w -> a -> Heap w a
singleton w
w a
x = Root w a -> Heap w a
forall w a. Root w a -> Heap w a
Node (w -> a -> [Root w a] -> Root w a
forall w a. w -> a -> [Heap w a] -> Heap w a
Root w
w a
x [])
{-# INLINE singleton #-}

fromList :: Monus w => [(w, a)] -> Heap w a
fromList :: forall w a. Monus w => [(w, a)] -> Heap w a
fromList = Maybe (Root w a) -> Heap w a
forall w a. Maybe (Root w a) -> Heap w a
node (Maybe (Root w a) -> Heap w a)
-> ([(w, a)] -> Maybe (Root w a)) -> [(w, a)] -> Heap w a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (NonEmpty (w, a) -> Root w a)
-> Maybe (NonEmpty (w, a)) -> Maybe (Root w a)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap (NonEmpty (Root w a) -> Root w a
forall w a. Monus w => NonEmpty (Heap w a) -> Heap w a
NonEmpty.mergeHeaps (NonEmpty (Root w a) -> Root w a)
-> (NonEmpty (w, a) -> NonEmpty (Root w a))
-> NonEmpty (w, a)
-> Root w a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((w, a) -> Root w a) -> NonEmpty (w, a) -> NonEmpty (Root w a)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap ((w -> a -> Root w a) -> (w, a) -> Root w a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry w -> a -> Root w a
forall w a. w -> a -> Heap w a
NonEmpty.singleton)) (Maybe (NonEmpty (w, a)) -> Maybe (Root w a))
-> ([(w, a)] -> Maybe (NonEmpty (w, a)))
-> [(w, a)]
-> Maybe (Root w a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(w, a)] -> Maybe (NonEmpty (w, a))
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty
{-# INLINE fromList #-}

-- | An implementation of Dijkstra's algorithm on 'Graph's.
dijkstra :: Ord a => Graph a -> Graph a
dijkstra :: forall a. Ord a => Graph a -> Graph a
dijkstra Graph a
g a
s = Set a -> Heap Dist a -> [(a, Dist)]
go Set a
forall a. Set a
Set.empty (Dist -> a -> Heap Dist a
forall w a. w -> a -> Heap w a
singleton Dist
forall a. Monoid a => a
mempty a
s)
  where
    go :: Set a -> Heap Dist a -> [(a, Dist)]
go Set a
s Heap Dist a
hp = case Heap Dist a -> Maybe ((Dist, a), Heap Dist a)
forall w a. Monus w => Heap w a -> Maybe ((w, a), Heap w a)
popMin Heap Dist a
hp of
      Maybe ((Dist, a), Heap Dist a)
Nothing -> []
      Just ((Dist
w,a
x),Heap Dist a
xs)
        | a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member a
x Set a
s -> Set a -> Heap Dist a -> [(a, Dist)]
go Set a
s Heap Dist a
xs
        | Bool
otherwise -> (a
x,Dist
w) (a, Dist) -> [(a, Dist)] -> [(a, Dist)]
forall a. a -> [a] -> [a]
: Set a -> Heap Dist a -> [(a, Dist)]
go (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
x Set a
s) (Heap Dist a
xs Heap Dist a -> Heap Dist a -> Heap Dist a
forall w a. Monus w => Heap w a -> Heap w a -> Heap w a
<+> Heap Dist a
xs')
        where
          xs' :: Heap Dist a
xs' = Dist
w Dist -> Heap Dist a -> Heap Dist a
forall w a. Semigroup w => w -> Heap w a -> Heap w a
<>< [(Dist, a)] -> Heap Dist a
forall w a. Monus w => [(w, a)] -> Heap w a
fromList (((a, Dist) -> (Dist, a)) -> [(a, Dist)] -> [(Dist, a)]
forall a b. (a -> b) -> [a] -> [b]
map (a, Dist) -> (Dist, a)
forall a b. (a, b) -> (b, a)
swap (Graph a
g a
x))

-- | Heapsort.
monusSort :: Ord a => [a] -> [a]
monusSort :: forall a. Ord a => [a] -> [a]
monusSort = ((Max a, a) -> a) -> [(Max a, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (Max a, a) -> a
forall a b. (a, b) -> b
snd ([(Max a, a)] -> [a]) -> ([a] -> [(Max a, a)]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Heap (Max a) a -> Maybe ((Max a, a), Heap (Max a) a))
-> Heap (Max a) a -> [(Max a, a)]
forall b a. (b -> Maybe (a, b)) -> b -> [a]
unfoldr Heap (Max a) a -> Maybe ((Max a, a), Heap (Max a) a)
forall w a. Monus w => Heap w a -> Maybe ((w, a), Heap w a)
popMin (Heap (Max a) a -> [(Max a, a)])
-> ([a] -> Heap (Max a) a) -> [a] -> [(Max a, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Max a, a)] -> Heap (Max a) a
forall w a. Monus w => [(w, a)] -> Heap w a
fromList ([(Max a, a)] -> Heap (Max a) a)
-> ([a] -> [(Max a, a)]) -> [a] -> Heap (Max a) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (Max a, a)) -> [a] -> [(Max a, a)]
forall a b. (a -> b) -> [a] -> [b]
map (\a
x -> (a -> Max a
forall a. a -> Max a
In a
x, a
x))