{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeFamilies #-}
{-# OPTIONS_HADDOCK not-home #-}

-- |
-- This is an internal module. You probably don't need to import this. Use
-- "Data.Seqn.PQueue" instead.
--
-- = WARNING
--
-- Definitions in this module allow violating invariants that would otherwise be
-- guaranteed by "Data.Seqn.PQueue". Use at your own risk!
--
module Data.Seqn.Internal.PQueue
  (
    -- * PQueue
    PQueue(..)
  , Elem(..)
  , Min(..)
  , empty
  , singleton
  , fromList
  , concatMap
  , insert
  , min
  , minView
  , toSortedList

    -- * Entry
  , Entry(..)
  , entryPrio
  , entryValue
  ) where

import Prelude hiding (concatMap, min)
import Data.Coerce (coerce)
import Control.DeepSeq (NFData(..), NFData1(..))
import qualified Data.Foldable as F
import qualified Data.Foldable.WithIndex as IFo
import Data.Functor.Classes (Eq1(..), Ord1(..), Show1(..))
import qualified GHC.Exts as X

import Data.Seqn.MSeq (Measured(..))
import Data.Seqn.Internal.MSeq (MSeq(..))
import qualified Data.Seqn.Internal.MSeq as MSeq
import Data.Seqn.Internal.MTree (MTree(..))
import qualified Data.Seqn.Internal.MTree as T
import qualified Data.Seqn.Internal.Util as U

newtype Min a = Min a

-- Note: We do not use Data.Semigroup.Min because we need a left-biased (<>)
-- for the FIFO property. Data.Semigroup.Min simply delegates to the min
-- function of the underlying type, which is not required to be left-biased.

instance Ord a => Semigroup (Min a) where
  x :: Min a
x@(Min a
x') <> :: Min a -> Min a -> Min a
<> y :: Min a
y@(Min a
y') = if a
x' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y' then Min a
x else Min a
y
  {-# INLINE (<>) #-}

instance NFData a => NFData (Min a) where
  rnf :: Min a -> ()
rnf = ((a -> ()) -> Min a -> ()
forall {a}. (a -> ()) -> Min a -> ()
forall a b. Coercible a b => a -> b
coerce :: (a -> ()) -> Min a -> ()) a -> ()
forall a. NFData a => a -> ()
rnf
  {-# INLINABLE rnf #-}

instance NFData1 Min where
  liftRnf :: forall {a}. (a -> ()) -> Min a -> ()
liftRnf = (a -> ()) -> Min a -> ()
forall a b. Coercible a b => a -> b
coerce

newtype Elem a = Elem a
  deriving newtype (Elem a -> Elem a -> Bool
(Elem a -> Elem a -> Bool)
-> (Elem a -> Elem a -> Bool) -> Eq (Elem a)
forall a. Eq a => Elem a -> Elem a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Elem a -> Elem a -> Bool
== :: Elem a -> Elem a -> Bool
$c/= :: forall a. Eq a => Elem a -> Elem a -> Bool
/= :: Elem a -> Elem a -> Bool
Eq, Eq (Elem a)
Eq (Elem a) =>
(Elem a -> Elem a -> Ordering)
-> (Elem a -> Elem a -> Bool)
-> (Elem a -> Elem a -> Bool)
-> (Elem a -> Elem a -> Bool)
-> (Elem a -> Elem a -> Bool)
-> (Elem a -> Elem a -> Elem a)
-> (Elem a -> Elem a -> Elem a)
-> Ord (Elem a)
Elem a -> Elem a -> Bool
Elem a -> Elem a -> Ordering
Elem a -> Elem a -> Elem 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 a. Ord a => Eq (Elem a)
forall a. Ord a => Elem a -> Elem a -> Bool
forall a. Ord a => Elem a -> Elem a -> Ordering
forall a. Ord a => Elem a -> Elem a -> Elem a
$ccompare :: forall a. Ord a => Elem a -> Elem a -> Ordering
compare :: Elem a -> Elem a -> Ordering
$c< :: forall a. Ord a => Elem a -> Elem a -> Bool
< :: Elem a -> Elem a -> Bool
$c<= :: forall a. Ord a => Elem a -> Elem a -> Bool
<= :: Elem a -> Elem a -> Bool
$c> :: forall a. Ord a => Elem a -> Elem a -> Bool
> :: Elem a -> Elem a -> Bool
$c>= :: forall a. Ord a => Elem a -> Elem a -> Bool
>= :: Elem a -> Elem a -> Bool
$cmax :: forall a. Ord a => Elem a -> Elem a -> Elem a
max :: Elem a -> Elem a -> Elem a
$cmin :: forall a. Ord a => Elem a -> Elem a -> Elem a
min :: Elem a -> Elem a -> Elem a
Ord, Int -> Elem a -> ShowS
[Elem a] -> ShowS
Elem a -> String
(Int -> Elem a -> ShowS)
-> (Elem a -> String) -> ([Elem a] -> ShowS) -> Show (Elem a)
forall a. Show a => Int -> Elem a -> ShowS
forall a. Show a => [Elem a] -> ShowS
forall a. Show a => Elem a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> Elem a -> ShowS
showsPrec :: Int -> Elem a -> ShowS
$cshow :: forall a. Show a => Elem a -> String
show :: Elem a -> String
$cshowList :: forall a. Show a => [Elem a] -> ShowS
showList :: [Elem a] -> ShowS
Show, ReadPrec [Elem a]
ReadPrec (Elem a)
Int -> ReadS (Elem a)
ReadS [Elem a]
(Int -> ReadS (Elem a))
-> ReadS [Elem a]
-> ReadPrec (Elem a)
-> ReadPrec [Elem a]
-> Read (Elem a)
forall a. Read a => ReadPrec [Elem a]
forall a. Read a => ReadPrec (Elem a)
forall a. Read a => Int -> ReadS (Elem a)
forall a. Read a => ReadS [Elem a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: forall a. Read a => Int -> ReadS (Elem a)
readsPrec :: Int -> ReadS (Elem a)
$creadList :: forall a. Read a => ReadS [Elem a]
readList :: ReadS [Elem a]
$creadPrec :: forall a. Read a => ReadPrec (Elem a)
readPrec :: ReadPrec (Elem a)
$creadListPrec :: forall a. Read a => ReadPrec [Elem a]
readListPrec :: ReadPrec [Elem a]
Read, Elem a -> ()
(Elem a -> ()) -> NFData (Elem a)
forall a. NFData a => Elem a -> ()
forall a. (a -> ()) -> NFData a
$crnf :: forall a. NFData a => Elem a -> ()
rnf :: Elem a -> ()
NFData)

instance Ord a => Measured (Elem a) where
  type Measure (Elem a) = Min a
  measure :: Elem a -> Measure (Elem a)
measure = Elem a -> Measure (Elem a)
Elem a -> Min a
forall a b. Coercible a b => a -> b
coerce

-- | A minimum priority queue.
--
-- @PQueue@ can be used as a maximum priority queue by wrapping its elements
-- with t'Data.Ord.Down'.
newtype PQueue a = PQueue (MSeq (Elem a))
  deriving newtype
    (
      -- | Insertion order.
      PQueue a -> PQueue a -> Bool
(PQueue a -> PQueue a -> Bool)
-> (PQueue a -> PQueue a -> Bool) -> Eq (PQueue a)
forall a. Eq a => PQueue a -> PQueue a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => PQueue a -> PQueue a -> Bool
== :: PQueue a -> PQueue a -> Bool
$c/= :: forall a. Eq a => PQueue a -> PQueue a -> Bool
/= :: PQueue a -> PQueue a -> Bool
Eq

      -- | Lexicographical ordering, in insertion order.
    , Eq (PQueue a)
Eq (PQueue a) =>
(PQueue a -> PQueue a -> Ordering)
-> (PQueue a -> PQueue a -> Bool)
-> (PQueue a -> PQueue a -> Bool)
-> (PQueue a -> PQueue a -> Bool)
-> (PQueue a -> PQueue a -> Bool)
-> (PQueue a -> PQueue a -> PQueue a)
-> (PQueue a -> PQueue a -> PQueue a)
-> Ord (PQueue a)
PQueue a -> PQueue a -> Bool
PQueue a -> PQueue a -> Ordering
PQueue a -> PQueue a -> PQueue 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 a. Ord a => Eq (PQueue a)
forall a. Ord a => PQueue a -> PQueue a -> Bool
forall a. Ord a => PQueue a -> PQueue a -> Ordering
forall a. Ord a => PQueue a -> PQueue a -> PQueue a
$ccompare :: forall a. Ord a => PQueue a -> PQueue a -> Ordering
compare :: PQueue a -> PQueue a -> Ordering
$c< :: forall a. Ord a => PQueue a -> PQueue a -> Bool
< :: PQueue a -> PQueue a -> Bool
$c<= :: forall a. Ord a => PQueue a -> PQueue a -> Bool
<= :: PQueue a -> PQueue a -> Bool
$c> :: forall a. Ord a => PQueue a -> PQueue a -> Bool
> :: PQueue a -> PQueue a -> Bool
$c>= :: forall a. Ord a => PQueue a -> PQueue a -> Bool
>= :: PQueue a -> PQueue a -> Bool
$cmax :: forall a. Ord a => PQueue a -> PQueue a -> PQueue a
max :: PQueue a -> PQueue a -> PQueue a
$cmin :: forall a. Ord a => PQueue a -> PQueue a -> PQueue a
min :: PQueue a -> PQueue a -> PQueue a
Ord

      -- |
      -- [@(<>)@]: \(O(\left| \log n_1 - \log n_2 \right|)\). Concatenate
      -- two @PQueue@s.
    , NonEmpty (PQueue a) -> PQueue a
PQueue a -> PQueue a -> PQueue a
(PQueue a -> PQueue a -> PQueue a)
-> (NonEmpty (PQueue a) -> PQueue a)
-> (forall b. Integral b => b -> PQueue a -> PQueue a)
-> Semigroup (PQueue a)
forall b. Integral b => b -> PQueue a -> PQueue a
forall a. Ord a => NonEmpty (PQueue a) -> PQueue a
forall a. Ord a => PQueue a -> PQueue a -> PQueue a
forall a b. (Ord a, Integral b) => b -> PQueue a -> PQueue a
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
$c<> :: forall a. Ord a => PQueue a -> PQueue a -> PQueue a
<> :: PQueue a -> PQueue a -> PQueue a
$csconcat :: forall a. Ord a => NonEmpty (PQueue a) -> PQueue a
sconcat :: NonEmpty (PQueue a) -> PQueue a
$cstimes :: forall a b. (Ord a, Integral b) => b -> PQueue a -> PQueue a
stimes :: forall b. Integral b => b -> PQueue a -> PQueue a
Semigroup

      -- |
      -- [@mempty@]: The empty queue.
    , Semigroup (PQueue a)
PQueue a
Semigroup (PQueue a) =>
PQueue a
-> (PQueue a -> PQueue a -> PQueue a)
-> ([PQueue a] -> PQueue a)
-> Monoid (PQueue a)
[PQueue a] -> PQueue a
PQueue a -> PQueue a -> PQueue a
forall a. Ord a => Semigroup (PQueue a)
forall a. Ord a => PQueue a
forall a. Ord a => [PQueue a] -> PQueue a
forall a. Ord a => PQueue a -> PQueue a -> PQueue a
forall a.
Semigroup a =>
a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
$cmempty :: forall a. Ord a => PQueue a
mempty :: PQueue a
$cmappend :: forall a. Ord a => PQueue a -> PQueue a -> PQueue a
mappend :: PQueue a -> PQueue a -> PQueue a
$cmconcat :: forall a. Ord a => [PQueue a] -> PQueue a
mconcat :: [PQueue a] -> PQueue a
Monoid

    , Int -> PQueue a -> ShowS
[PQueue a] -> ShowS
PQueue a -> String
(Int -> PQueue a -> ShowS)
-> (PQueue a -> String) -> ([PQueue a] -> ShowS) -> Show (PQueue a)
forall a. Show a => Int -> PQueue a -> ShowS
forall a. Show a => [PQueue a] -> ShowS
forall a. Show a => PQueue a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> PQueue a -> ShowS
showsPrec :: Int -> PQueue a -> ShowS
$cshow :: forall a. Show a => PQueue a -> String
show :: PQueue a -> String
$cshowList :: forall a. Show a => [PQueue a] -> ShowS
showList :: [PQueue a] -> ShowS
Show
    , ReadPrec [PQueue a]
ReadPrec (PQueue a)
Int -> ReadS (PQueue a)
ReadS [PQueue a]
(Int -> ReadS (PQueue a))
-> ReadS [PQueue a]
-> ReadPrec (PQueue a)
-> ReadPrec [PQueue a]
-> Read (PQueue a)
forall a. (Ord a, Read a) => ReadPrec [PQueue a]
forall a. (Ord a, Read a) => ReadPrec (PQueue a)
forall a. (Ord a, Read a) => Int -> ReadS (PQueue a)
forall a. (Ord a, Read a) => ReadS [PQueue a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: forall a. (Ord a, Read a) => Int -> ReadS (PQueue a)
readsPrec :: Int -> ReadS (PQueue a)
$creadList :: forall a. (Ord a, Read a) => ReadS [PQueue a]
readList :: ReadS [PQueue a]
$creadPrec :: forall a. (Ord a, Read a) => ReadPrec (PQueue a)
readPrec :: ReadPrec (PQueue a)
$creadListPrec :: forall a. (Ord a, Read a) => ReadPrec [PQueue a]
readListPrec :: ReadPrec [PQueue a]
Read
    )

instance Eq1 PQueue where
  liftEq :: forall a b. (a -> b -> Bool) -> PQueue a -> PQueue b -> Bool
liftEq =
    (((Elem a -> Elem b -> Bool)
 -> MSeq (Elem a) -> MSeq (Elem b) -> Bool)
-> (a -> b -> Bool) -> PQueue a -> PQueue b -> Bool
forall {a} {b}.
((Elem a -> Elem b -> Bool)
 -> MSeq (Elem a) -> MSeq (Elem b) -> Bool)
-> (a -> b -> Bool) -> PQueue a -> PQueue b -> Bool
forall a b. Coercible a b => a -> b
coerce :: ((Elem a -> Elem b -> Bool) -> MSeq (Elem a) -> MSeq (Elem b) -> Bool)
            -> (a -> b -> Bool) -> PQueue a -> PQueue b -> Bool)
    (Elem a -> Elem b -> Bool)
-> MSeq (Elem a) -> MSeq (Elem b) -> Bool
forall a b. (a -> b -> Bool) -> MSeq a -> MSeq b -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq
  {-# INLINE liftEq #-}

instance Ord1 PQueue where
  liftCompare :: forall a b.
(a -> b -> Ordering) -> PQueue a -> PQueue b -> Ordering
liftCompare =
    (((Elem a -> Elem b -> Ordering)
 -> MSeq (Elem a) -> MSeq (Elem b) -> Ordering)
-> (a -> b -> Ordering) -> PQueue a -> PQueue b -> Ordering
forall {a} {b}.
((Elem a -> Elem b -> Ordering)
 -> MSeq (Elem a) -> MSeq (Elem b) -> Ordering)
-> (a -> b -> Ordering) -> PQueue a -> PQueue b -> Ordering
forall a b. Coercible a b => a -> b
coerce :: ((Elem a -> Elem b -> Ordering) -> MSeq (Elem a) -> MSeq (Elem b) -> Ordering)
            -> (a -> b -> Ordering) -> PQueue a -> PQueue b -> Ordering)
    (Elem a -> Elem b -> Ordering)
-> MSeq (Elem a) -> MSeq (Elem b) -> Ordering
forall a b. (a -> b -> Ordering) -> MSeq a -> MSeq b -> Ordering
forall (f :: * -> *) a b.
Ord1 f =>
(a -> b -> Ordering) -> f a -> f b -> Ordering
liftCompare
  {-# INLINE liftCompare #-}

instance Show1 PQueue where
  liftShowsPrec :: forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> PQueue a -> ShowS
liftShowsPrec Int -> a -> ShowS
_ [a] -> ShowS
sl Int
_ PQueue a
s = [a] -> ShowS
sl (PQueue a -> [a]
forall a. PQueue a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList PQueue a
s)
  {-# INLINE liftShowsPrec #-}

-- |
-- [length]: \(O(1)\).
--
-- Folds in insertion order.
instance Foldable PQueue where
  foldMap :: forall m a. Monoid m => (a -> m) -> PQueue a -> m
foldMap =
    (((Elem a -> m) -> MSeq (Elem a) -> m) -> (a -> m) -> PQueue a -> m
forall {a} {m}.
((Elem a -> m) -> MSeq (Elem a) -> m) -> (a -> m) -> PQueue a -> m
forall a b. Coercible a b => a -> b
coerce :: ((Elem a -> m) -> MSeq (Elem a) -> m)
            -> (a -> m) -> PQueue a -> m)
    (Elem a -> m) -> MSeq (Elem a) -> m
forall m a. Monoid m => (a -> m) -> MSeq a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap
  {-# INLINE foldMap #-}

  foldr :: forall a b. (a -> b -> b) -> b -> PQueue a -> b
foldr =
    (((Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
-> (a -> b -> b) -> b -> PQueue a -> b
forall {a} {b}.
((Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
-> (a -> b -> b) -> b -> PQueue a -> b
forall a b. Coercible a b => a -> b
coerce :: ((Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
            -> (a -> b -> b) -> b -> PQueue a -> b)
    (Elem a -> b -> b) -> b -> MSeq (Elem a) -> b
forall a b. (a -> b -> b) -> b -> MSeq a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
  {-# INLINE foldr #-}

  foldl' :: forall b a. (b -> a -> b) -> b -> PQueue a -> b
foldl' =
    (((b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
-> (b -> a -> b) -> b -> PQueue a -> b
forall {b} {a}.
((b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
-> (b -> a -> b) -> b -> PQueue a -> b
forall a b. Coercible a b => a -> b
coerce :: ((b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
            -> (b -> a -> b) -> b -> PQueue a -> b)
    (b -> Elem a -> b) -> b -> MSeq (Elem a) -> b
forall b a. (b -> a -> b) -> b -> MSeq a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl'
  {-# INLINE foldl' #-}

  foldl :: forall b a. (b -> a -> b) -> b -> PQueue a -> b
foldl =
    (((b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
-> (b -> a -> b) -> b -> PQueue a -> b
forall {b} {a}.
((b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
-> (b -> a -> b) -> b -> PQueue a -> b
forall a b. Coercible a b => a -> b
coerce :: ((b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
            -> (b -> a -> b) -> b -> PQueue a -> b)
    (b -> Elem a -> b) -> b -> MSeq (Elem a) -> b
forall b a. (b -> a -> b) -> b -> MSeq a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl
  {-# INLINE foldl #-}

  foldr' :: forall a b. (a -> b -> b) -> b -> PQueue a -> b
foldr' =
    (((Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
-> (a -> b -> b) -> b -> PQueue a -> b
forall {a} {b}.
((Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
-> (a -> b -> b) -> b -> PQueue a -> b
forall a b. Coercible a b => a -> b
coerce :: ((Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
            -> (a -> b -> b) -> b -> PQueue a -> b)
    (Elem a -> b -> b) -> b -> MSeq (Elem a) -> b
forall a b. (a -> b -> b) -> b -> MSeq a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.foldr'
  {-# INLINE foldr' #-}

  null :: forall a. PQueue a -> Bool
null = (MSeq (Elem a) -> Bool) -> PQueue a -> Bool
forall a b. Coercible a b => a -> b
coerce (forall (t :: * -> *) a. Foldable t => t a -> Bool
null @MSeq)
  length :: forall a. PQueue a -> Int
length = (MSeq (Elem a) -> Int) -> PQueue a -> Int
forall a b. Coercible a b => a -> b
coerce (forall (t :: * -> *) a. Foldable t => t a -> Int
length @MSeq)

-- | Folds in insertion order.
instance IFo.FoldableWithIndex Int PQueue where
  ifoldMap :: forall m a. Monoid m => (Int -> a -> m) -> PQueue a -> m
ifoldMap =
    (((Int -> Elem a -> m) -> MSeq (Elem a) -> m)
-> (Int -> a -> m) -> PQueue a -> m
forall {a} {m}.
((Int -> Elem a -> m) -> MSeq (Elem a) -> m)
-> (Int -> a -> m) -> PQueue a -> m
forall a b. Coercible a b => a -> b
coerce :: ((Int -> Elem a -> m) -> MSeq (Elem a) -> m)
            -> (Int -> a -> m) -> PQueue a -> m)
    (Int -> Elem a -> m) -> MSeq (Elem a) -> m
forall m a. Monoid m => (Int -> a -> m) -> MSeq a -> m
forall i (f :: * -> *) m a.
(FoldableWithIndex i f, Monoid m) =>
(i -> a -> m) -> f a -> m
IFo.ifoldMap
  {-# INLINE ifoldMap #-}

  ifoldr :: forall a b. (Int -> a -> b -> b) -> b -> PQueue a -> b
ifoldr =
    (((Int -> Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
-> (Int -> a -> b -> b) -> b -> PQueue a -> b
forall {a} {b}.
((Int -> Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
-> (Int -> a -> b -> b) -> b -> PQueue a -> b
forall a b. Coercible a b => a -> b
coerce :: ((Int -> Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
            -> (Int -> a -> b -> b) -> b -> PQueue a -> b)
    (Int -> Elem a -> b -> b) -> b -> MSeq (Elem a) -> b
forall a b. (Int -> a -> b -> b) -> b -> MSeq a -> b
forall i (f :: * -> *) a b.
FoldableWithIndex i f =>
(i -> a -> b -> b) -> b -> f a -> b
IFo.ifoldr
  {-# INLINE ifoldr #-}

  ifoldr' :: forall a b. (Int -> a -> b -> b) -> b -> PQueue a -> b
ifoldr' =
    (((Int -> Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
-> (Int -> a -> b -> b) -> b -> PQueue a -> b
forall {a} {b}.
((Int -> Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
-> (Int -> a -> b -> b) -> b -> PQueue a -> b
forall a b. Coercible a b => a -> b
coerce :: ((Int -> Elem a -> b -> b) -> b -> MSeq (Elem a) -> b)
            -> (Int -> a -> b -> b) -> b -> PQueue a -> b)
    (Int -> Elem a -> b -> b) -> b -> MSeq (Elem a) -> b
forall a b. (Int -> a -> b -> b) -> b -> MSeq a -> b
forall i (f :: * -> *) a b.
FoldableWithIndex i f =>
(i -> a -> b -> b) -> b -> f a -> b
IFo.ifoldr'
  {-# INLINE ifoldr' #-}

  ifoldl' :: forall b a. (Int -> b -> a -> b) -> b -> PQueue a -> b
ifoldl' =
    (((Int -> b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
-> (Int -> b -> a -> b) -> b -> PQueue a -> b
forall {b} {a}.
((Int -> b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
-> (Int -> b -> a -> b) -> b -> PQueue a -> b
forall a b. Coercible a b => a -> b
coerce :: ((Int -> b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
            -> (Int -> b -> a -> b) -> b -> PQueue a -> b)
    (Int -> b -> Elem a -> b) -> b -> MSeq (Elem a) -> b
forall b a. (Int -> b -> a -> b) -> b -> MSeq a -> b
forall i (f :: * -> *) b a.
FoldableWithIndex i f =>
(i -> b -> a -> b) -> b -> f a -> b
IFo.ifoldl'
  {-# INLINE ifoldl' #-}

  ifoldl :: forall b a. (Int -> b -> a -> b) -> b -> PQueue a -> b
ifoldl =
    (((Int -> b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
-> (Int -> b -> a -> b) -> b -> PQueue a -> b
forall {b} {a}.
((Int -> b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
-> (Int -> b -> a -> b) -> b -> PQueue a -> b
forall a b. Coercible a b => a -> b
coerce :: ((Int -> b -> Elem a -> b) -> b -> MSeq (Elem a) -> b)
            -> (Int -> b -> a -> b) -> b -> PQueue a -> b)
    (Int -> b -> Elem a -> b) -> b -> MSeq (Elem a) -> b
forall b a. (Int -> b -> a -> b) -> b -> MSeq a -> b
forall i (f :: * -> *) b a.
FoldableWithIndex i f =>
(i -> b -> a -> b) -> b -> f a -> b
IFo.ifoldl
  {-# INLINE ifoldl #-}

instance Ord a => X.IsList (PQueue a) where
  type Item (PQueue a) = a

  fromList :: [Item (PQueue a)] -> PQueue a
fromList = [a] -> PQueue a
[Item (PQueue a)] -> PQueue a
forall a. Ord a => [a] -> PQueue a
fromList
  {-# INLINE fromList #-}

  toList :: PQueue a -> [Item (PQueue a)]
toList = PQueue a -> [a]
PQueue a -> [Item (PQueue a)]
forall a. PQueue a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList
  {-# INLINE toList #-}

instance NFData a => NFData (PQueue a) where
  rnf :: PQueue a -> ()
rnf = ((MSeq (Elem a) -> ()) -> PQueue a -> ()
forall {a}. (MSeq (Elem a) -> ()) -> PQueue a -> ()
forall a b. Coercible a b => a -> b
coerce :: (MSeq (Elem a) -> ()) -> PQueue a -> ()) MSeq (Elem a) -> ()
forall a. NFData a => a -> ()
rnf
  {-# INLINABLE rnf #-}

instance NFData1 PQueue where
  liftRnf :: forall a. (a -> ()) -> PQueue a -> ()
liftRnf a -> ()
f (PQueue MSeq (Elem a)
t) = (Measure (Elem a) -> ()) -> (Elem a -> ()) -> MSeq (Elem a) -> ()
forall a. (Measure a -> ()) -> (a -> ()) -> MSeq a -> ()
MSeq.liftRnf2 ((a -> ()) -> Min a -> ()
forall {a}. (a -> ()) -> Min a -> ()
forall (f :: * -> *) a. NFData1 f => (a -> ()) -> f a -> ()
liftRnf a -> ()
f) ((a -> ()) -> Elem a -> ()
forall a b. Coercible a b => a -> b
coerce a -> ()
f) MSeq (Elem a)
t
  {-# INLINE liftRnf #-}

---------------
-- Operations
---------------

-- | The empty queue.
empty :: PQueue a
empty :: forall a. PQueue a
empty = MSeq (Elem a) -> PQueue a
forall a. MSeq (Elem a) -> PQueue a
PQueue MSeq (Elem a)
forall a. MSeq a
MSeq.empty

-- | A singleton queue.
singleton :: a -> PQueue a
singleton :: forall a. a -> PQueue a
singleton = (Elem a -> MSeq (Elem a)) -> a -> PQueue a
forall a b. Coercible a b => a -> b
coerce Elem a -> MSeq (Elem a)
forall a. a -> MSeq a
MSeq.singleton

-- | \(O(n)\). Create a queue from a list.
fromList :: Ord a => [a] -> PQueue a
fromList :: forall a. Ord a => [a] -> PQueue a
fromList = ([Elem a] -> MSeq (Elem a)) -> [a] -> PQueue a
forall a b. Coercible a b => a -> b
coerce [Elem a] -> MSeq (Elem a)
forall a. Measured a => [a] -> MSeq a
MSeq.fromList
{-# INLINE fromList #-}

-- | \(O \left(\sum_i \log n_i \right)\).
-- Map over a @Foldable@ and concatenate the results.
concatMap :: (Ord b, Foldable f) => (a -> PQueue b) -> f a -> PQueue b
concatMap :: forall b (f :: * -> *) a.
(Ord b, Foldable f) =>
(a -> PQueue b) -> f a -> PQueue b
concatMap =
  (((a -> MSeq (Elem b)) -> f a -> MSeq (Elem b))
-> (a -> PQueue b) -> f a -> PQueue b
forall {a} {b} {f :: * -> *}.
((a -> MSeq (Elem b)) -> f a -> MSeq (Elem b))
-> (a -> PQueue b) -> f a -> PQueue b
forall a b. Coercible a b => a -> b
coerce :: ((a -> MSeq (Elem b)) -> f a -> MSeq (Elem b))
          -> (a -> PQueue b) -> f a -> PQueue b)
  (a -> MSeq (Elem b)) -> f a -> MSeq (Elem b)
forall b (f :: * -> *) a.
(Measured b, Foldable f) =>
(a -> MSeq b) -> f a -> MSeq b
MSeq.concatMap
{-# INLINE concatMap #-}

-- | \(O(\log n)\). Insert an element into the queue.
--
-- Note: When inserting multiple elements, it is more efficient to concatenate
-- a fresh queue rather than repeatedly insert elements.
--
-- @
-- q <> fromList xs          -- Good
-- foldl' (flip insert) q xs -- Worse
-- @
insert :: Ord a => a -> PQueue a -> PQueue a
insert :: forall a. Ord a => a -> PQueue a -> PQueue a
insert = (Elem a -> MSeq (Elem a) -> MSeq (Elem a))
-> a -> PQueue a -> PQueue a
forall a b. Coercible a b => a -> b
coerce ((MSeq (Elem a) -> Elem a -> MSeq (Elem a))
-> Elem a -> MSeq (Elem a) -> MSeq (Elem a)
forall a b c. (a -> b -> c) -> b -> a -> c
flip MSeq (Elem a) -> Elem a -> MSeq (Elem a)
forall a. Measured a => MSeq a -> a -> MSeq a
MSeq.snoc)
{-# INLINABLE insert #-}

-- | \(O(1)\). The minimum element in the queue.
min :: Ord a => PQueue a -> Maybe a
min :: forall a. Ord a => PQueue a -> Maybe a
min =
  ((MSeq (Elem a) -> Maybe (Min a)) -> PQueue a -> Maybe a
forall {a}. (MSeq (Elem a) -> Maybe (Min a)) -> PQueue a -> Maybe a
forall a b. Coercible a b => a -> b
coerce :: (MSeq (Elem a) -> Maybe (Min a)) -> PQueue a -> Maybe a)
  MSeq (Elem a) -> Maybe (Measure (Elem a))
MSeq (Elem a) -> Maybe (Min a)
forall a. Measured a => MSeq a -> Maybe (Measure a)
MSeq.summaryMay
{-# INLINE min #-}

-- | \(O(\log n)\). The minimum element in the queue, with the rest of the
-- queue.
minView :: Ord a => PQueue a -> Maybe (a, PQueue a)
minView :: forall a. Ord a => PQueue a -> Maybe (a, PQueue a)
minView (PQueue MSeq (Elem a)
t) = case MSeq (Elem a)
t of
  MSeq (Elem a)
MEmpty -> Maybe (a, PQueue a)
forall a. Maybe a
Nothing
  MTree Elem a
x MTree (Elem a)
xs -> case Elem a -> MTree (Elem a) -> S2 a (MSeq (Elem a))
forall a. Ord a => Elem a -> MTree (Elem a) -> S2 a (MSeq (Elem a))
minViewSure Elem a
x MTree (Elem a)
xs of
    U.S2 a
y MSeq (Elem a)
t' -> (a, PQueue a) -> Maybe (a, PQueue a)
forall a. a -> Maybe a
Just (a
y, MSeq (Elem a) -> PQueue a
forall a. MSeq (Elem a) -> PQueue a
PQueue MSeq (Elem a)
t')
{-# INLINE minView #-}

minViewSure :: Ord a => Elem a -> MTree (Elem a) -> U.S2 a (MSeq (Elem a))
minViewSure :: forall a. Ord a => Elem a -> MTree (Elem a) -> S2 a (MSeq (Elem a))
minViewSure x :: Elem a
x@(Elem !a
x1) MTree (Elem a)
xs = case MTree (Elem a)
xs of
  MTree (Elem a)
MTip -> a -> MSeq (Elem a) -> S2 a (MSeq (Elem a))
forall a b. a -> b -> S2 a b
U.S2 a
x1 MSeq (Elem a)
forall a. MSeq a
MSeq.empty
  MBin Int
_ (Min a
v) Elem a
_ MTree (Elem a)
_ MTree (Elem a)
_
    | a
x1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
v -> a -> MSeq (Elem a) -> S2 a (MSeq (Elem a))
forall a b. a -> b -> S2 a b
U.S2 a
x1 (MTree (Elem a) -> MSeq (Elem a)
forall a. Measured a => MTree a -> MSeq a
MSeq.fromMTree MTree (Elem a)
xs)
    | Bool
otherwise -> a -> MSeq (Elem a) -> S2 a (MSeq (Elem a))
forall a b. a -> b -> S2 a b
U.S2 a
v (Elem a -> MTree (Elem a) -> MSeq (Elem a)
forall a. a -> MTree a -> MSeq a
MTree Elem a
x (a -> MTree (Elem a) -> MTree (Elem a)
forall a. Ord a => a -> MTree (Elem a) -> MTree (Elem a)
deleteSure a
v MTree (Elem a)
xs))
{-# INLINABLE minViewSure #-}

deleteSure :: Ord a => a -> MTree (Elem a) -> MTree (Elem a)
deleteSure :: forall a. Ord a => a -> MTree (Elem a) -> MTree (Elem a)
deleteSure !a
k = \case
  MBin Int
_ Measure (Elem a)
_ x :: Elem a
x@(Elem a
x1) MTree (Elem a)
l MTree (Elem a)
r -> case MTree (Elem a)
l of
    MTree (Elem a)
MTip
      | a
x1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
k -> MTree (Elem a)
r
      | Bool
otherwise -> Elem a -> MTree (Elem a) -> MTree (Elem a)
forall a. Measured a => a -> MTree a -> MTree a
T.cons Elem a
x (a -> MTree (Elem a) -> MTree (Elem a)
forall a. Ord a => a -> MTree (Elem a) -> MTree (Elem a)
deleteSure a
k MTree (Elem a)
r)
    MBin Int
_ (Min a
v) Elem a
_ MTree (Elem a)
_ MTree (Elem a)
_
      | a
v a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
k -> Elem a -> MTree (Elem a) -> MTree (Elem a) -> MTree (Elem a)
forall a. Measured a => a -> MTree a -> MTree a -> MTree a
T.balanceR Elem a
x (a -> MTree (Elem a) -> MTree (Elem a)
forall a. Ord a => a -> MTree (Elem a) -> MTree (Elem a)
deleteSure a
k MTree (Elem a)
l) MTree (Elem a)
r
      | a
x1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
k -> MTree (Elem a) -> MTree (Elem a) -> MTree (Elem a)
forall a. Measured a => MTree a -> MTree a -> MTree a
T.glue MTree (Elem a)
l MTree (Elem a)
r
      | Bool
otherwise -> Elem a -> MTree (Elem a) -> MTree (Elem a) -> MTree (Elem a)
forall a. Measured a => a -> MTree a -> MTree a -> MTree a
T.balanceL Elem a
x MTree (Elem a)
l (a -> MTree (Elem a) -> MTree (Elem a)
forall a. Ord a => a -> MTree (Elem a) -> MTree (Elem a)
deleteSure a
k MTree (Elem a)
r)
  MTree (Elem a)
MTip -> String -> MTree (Elem a)
forall a. HasCallStack => String -> a
error String
"PQueue.deleteSure: impossible"
{-# INLINABLE deleteSure #-}

-- | \(O(n \log n)\). Convert to a sorted list.
toSortedList :: Ord a => PQueue a -> [a]
toSortedList :: forall a. Ord a => PQueue a -> [a]
toSortedList PQueue a
q0 = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
X.build ((forall b. (a -> b -> b) -> b -> b) -> [a])
-> (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a b. (a -> b) -> a -> b
$ \a -> b -> b
lcons b
lnil ->
  let go :: PQueue a -> b
go PQueue a
q = case PQueue a -> Maybe (a, PQueue a)
forall a. Ord a => PQueue a -> Maybe (a, PQueue a)
minView PQueue a
q of
        Maybe (a, PQueue a)
Nothing -> b
lnil
        Just (a
x,PQueue a
q') -> a -> b -> b
lcons a
x (PQueue a -> b
go PQueue a
q')
  in PQueue a -> b
go PQueue a
q0
{-# INLINE toSortedList #-}

----------
-- Entry
----------

-- | A priority associated with a value. A @PQueue (Entry k a)@ may be used
-- when the priority is separate from the value.
data Entry k a = Entry !k a
  deriving (Int -> Entry k a -> ShowS
[Entry k a] -> ShowS
Entry k a -> String
(Int -> Entry k a -> ShowS)
-> (Entry k a -> String)
-> ([Entry k a] -> ShowS)
-> Show (Entry k a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k a. (Show k, Show a) => Int -> Entry k a -> ShowS
forall k a. (Show k, Show a) => [Entry k a] -> ShowS
forall k a. (Show k, Show a) => Entry k a -> String
$cshowsPrec :: forall k a. (Show k, Show a) => Int -> Entry k a -> ShowS
showsPrec :: Int -> Entry k a -> ShowS
$cshow :: forall k a. (Show k, Show a) => Entry k a -> String
show :: Entry k a -> String
$cshowList :: forall k a. (Show k, Show a) => [Entry k a] -> ShowS
showList :: [Entry k a] -> ShowS
Show, ReadPrec [Entry k a]
ReadPrec (Entry k a)
Int -> ReadS (Entry k a)
ReadS [Entry k a]
(Int -> ReadS (Entry k a))
-> ReadS [Entry k a]
-> ReadPrec (Entry k a)
-> ReadPrec [Entry k a]
-> Read (Entry k a)
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
forall k a. (Read k, Read a) => ReadPrec [Entry k a]
forall k a. (Read k, Read a) => ReadPrec (Entry k a)
forall k a. (Read k, Read a) => Int -> ReadS (Entry k a)
forall k a. (Read k, Read a) => ReadS [Entry k a]
$creadsPrec :: forall k a. (Read k, Read a) => Int -> ReadS (Entry k a)
readsPrec :: Int -> ReadS (Entry k a)
$creadList :: forall k a. (Read k, Read a) => ReadS [Entry k a]
readList :: ReadS [Entry k a]
$creadPrec :: forall k a. (Read k, Read a) => ReadPrec (Entry k a)
readPrec :: ReadPrec (Entry k a)
$creadListPrec :: forall k a. (Read k, Read a) => ReadPrec [Entry k a]
readListPrec :: ReadPrec [Entry k a]
Read, (forall a b. (a -> b) -> Entry k a -> Entry k b)
-> (forall a b. a -> Entry k b -> Entry k a) -> Functor (Entry k)
forall a b. a -> Entry k b -> Entry k a
forall a b. (a -> b) -> Entry k a -> Entry k b
forall k a b. a -> Entry k b -> Entry k a
forall k a b. (a -> b) -> Entry k a -> Entry k b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall k a b. (a -> b) -> Entry k a -> Entry k b
fmap :: forall a b. (a -> b) -> Entry k a -> Entry k b
$c<$ :: forall k a b. a -> Entry k b -> Entry k a
<$ :: forall a b. a -> Entry k b -> Entry k a
Functor)

-- | Compares by @k@ only.
instance Eq k => Eq (Entry k a) where
  Entry k
k1 a
_ == :: Entry k a -> Entry k a -> Bool
== Entry k
k2 a
_ = k
k1 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k2
  {-# INLINABLE (==) #-}

-- | Compares by @k@ only.
instance Ord k => Ord (Entry k a) where
  compare :: Entry k a -> Entry k a -> Ordering
compare (Entry k
k1 a
_) (Entry k
k2 a
_) = k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k1 k
k2
  {-# INLINABLE compare #-}

  Entry k
k1 a
_ <= :: Entry k a -> Entry k a -> Bool
<= Entry k
k2 a
_ = k
k1 k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<= k
k2
  {-# INLINABLE (<=) #-}

instance (NFData k, NFData a) => NFData (Entry k a) where
  rnf :: Entry k a -> ()
rnf (Entry k
k a
x) = k -> ()
forall a. NFData a => a -> ()
rnf k
k () -> () -> ()
forall a b. a -> b -> b
`seq` a -> ()
forall a. NFData a => a -> ()
rnf a
x
  {-# INLINABLE rnf #-}

-- | The priority.
entryPrio :: Entry k a -> k
entryPrio :: forall k a. Entry k a -> k
entryPrio (Entry k
k a
_) = k
k

-- | The value.
entryValue :: Entry k a -> a
entryValue :: forall k a. Entry k a -> a
entryValue (Entry k
_ a
x) = a
x