{-# LANGUAGE CPP #-}
{-# LANGUAGE MultiParamTypeClasses #-}
#if __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Safe #-}
#endif
#if __GLASGOW_HASKELL__ >= 706
{-# LANGUAGE DeriveGeneric #-}
#endif
#if __GLASGOW_HASKELL__ >= 710 && __GLASGOW_HASKELL__ < 802
{-# LANGUAGE AutoDeriveTypeable #-}
#endif
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.PriorityQueue.FingerTree
-- Copyright   :  (c) Ross Paterson 2008
-- License     :  BSD-style
-- Maintainer  :  R.Paterson@city.ac.uk
-- Stability   :  experimental
-- Portability :  non-portable (MPTCs and functional dependencies)
--
-- Min-priority queues implemented using the 'FingerTree' type,
-- following section 4.6 of
--
--  * Ralf Hinze and Ross Paterson,
--    \"Finger trees: a simple general-purpose data structure\",
--    /Journal of Functional Programming/ 16:2 (2006) pp 197-217.
--    <http://staff.city.ac.uk/~ross/papers/FingerTree.html>
--
-- These have the same big-O complexity as skew heap implementations,
-- but are approximately an order of magnitude slower.
-- On the other hand, they are stable, so they can be used for fair
-- queueing.  They are also shallower, so that 'fmap' consumes less
-- space.
--
-- An amortized running time is given for each operation, with /n/
-- referring to the size of the priority queue.  These bounds hold even
-- in a persistent (shared) setting.
--
-- /Note/: Many of these operations have the same names as similar
-- operations on lists in the "Prelude".  The ambiguity may be resolved
-- using either qualification or the @hiding@ clause.
--
-----------------------------------------------------------------------------

module Data.PriorityQueue.FingerTree (
    PQueue,
    -- * Construction
    empty,
    singleton,
    union,
    insert,
    add,
    fromList,
    -- * Deconstruction
    null,
    minView,
    minViewWithKey
    ) where

import qualified Data.FingerTree as FT
import Data.FingerTree (FingerTree, (<|), (|>), (><), ViewL(..), Measured(..))

import Prelude hiding (null)
#if MIN_VERSION_base(4,6,0)
import GHC.Generics
#endif
#if MIN_VERSION_base(4,8,0)
import qualified Prelude (null)
#else
import Data.Foldable (Foldable(foldMap))
import Data.Monoid
#endif
#if (MIN_VERSION_base(4,9,0)) && !(MIN_VERSION_base(4,11,0))
import Data.Semigroup
#endif
import Control.Arrow ((***))
import Data.List (unfoldr)

data Entry k v = Entry k v
#if __GLASGOW_HASKELL__ >= 706
    deriving ((forall x. Entry k v -> Rep (Entry k v) x)
-> (forall x. Rep (Entry k v) x -> Entry k v)
-> Generic (Entry k v)
forall x. Rep (Entry k v) x -> Entry k v
forall x. Entry k v -> Rep (Entry k v) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k v x. Rep (Entry k v) x -> Entry k v
forall k v x. Entry k v -> Rep (Entry k v) x
$cto :: forall k v x. Rep (Entry k v) x -> Entry k v
$cfrom :: forall k v x. Entry k v -> Rep (Entry k v) x
Generic)
#endif

instance Functor (Entry k) where
    fmap :: (a -> b) -> Entry k a -> Entry k b
fmap a -> b
f (Entry k
k a
v) = k -> b -> Entry k b
forall k v. k -> v -> Entry k v
Entry k
k (a -> b
f a
v)

instance Foldable (Entry k) where
    foldMap :: (a -> m) -> Entry k a -> m
foldMap a -> m
f (Entry k
_ a
v) = a -> m
f a
v

data Prio k v = NoPrio | Prio k v
#if __GLASGOW_HASKELL__ >= 706
    deriving ((forall x. Prio k v -> Rep (Prio k v) x)
-> (forall x. Rep (Prio k v) x -> Prio k v) -> Generic (Prio k v)
forall x. Rep (Prio k v) x -> Prio k v
forall x. Prio k v -> Rep (Prio k v) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k v x. Rep (Prio k v) x -> Prio k v
forall k v x. Prio k v -> Rep (Prio k v) x
$cto :: forall k v x. Rep (Prio k v) x -> Prio k v
$cfrom :: forall k v x. Prio k v -> Rep (Prio k v) x
Generic)
#endif

#if MIN_VERSION_base(4,9,0)
instance Ord k => Semigroup (Prio k v) where
    <> :: Prio k v -> Prio k v -> Prio k v
(<>) = Prio k v -> Prio k v -> Prio k v
forall k v. Ord k => Prio k v -> Prio k v -> Prio k v
unionPrio
#endif

instance Ord k => Monoid (Prio k v) where
    mempty :: Prio k v
mempty  = Prio k v
forall k v. Prio k v
NoPrio
#if !(MIN_VERSION_base(4,11,0))
    mappend = unionPrio
#endif

unionPrio :: Ord k => Prio k v -> Prio k v -> Prio k v
Prio k v
x unionPrio :: Prio k v -> Prio k v -> Prio k v
`unionPrio` Prio k v
NoPrio      = Prio k v
x
Prio k v
NoPrio `unionPrio` Prio k v
y      = Prio k v
y
x :: Prio k v
x@(Prio k
kx v
_) `unionPrio` y :: Prio k v
y@(Prio k
ky v
_)
  | k
kx k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<= k
ky            = Prio k v
x
  | Bool
otherwise           = Prio k v
y

instance Ord k => Measured (Prio k v) (Entry k v) where
    measure :: Entry k v -> Prio k v
measure (Entry k
k v
v) = k -> v -> Prio k v
forall k v. k -> v -> Prio k v
Prio k
k v
v

-- | Priority queues.
newtype PQueue k v = PQueue (FingerTree (Prio k v) (Entry k v))
#if __GLASGOW_HASKELL__ >= 706
    deriving ((forall x. PQueue k v -> Rep (PQueue k v) x)
-> (forall x. Rep (PQueue k v) x -> PQueue k v)
-> Generic (PQueue k v)
forall x. Rep (PQueue k v) x -> PQueue k v
forall x. PQueue k v -> Rep (PQueue k v) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k v x. Rep (PQueue k v) x -> PQueue k v
forall k v x. PQueue k v -> Rep (PQueue k v) x
$cto :: forall k v x. Rep (PQueue k v) x -> PQueue k v
$cfrom :: forall k v x. PQueue k v -> Rep (PQueue k v) x
Generic)
#endif

instance Ord k => Functor (PQueue k) where
    fmap :: (a -> b) -> PQueue k a -> PQueue k b
fmap a -> b
f (PQueue FingerTree (Prio k a) (Entry k a)
xs) = FingerTree (Prio k b) (Entry k b) -> PQueue k b
forall k v. FingerTree (Prio k v) (Entry k v) -> PQueue k v
PQueue ((Entry k a -> Entry k b)
-> FingerTree (Prio k a) (Entry k a)
-> FingerTree (Prio k b) (Entry k b)
forall v1 a1 v2 a2.
(Measured v1 a1, Measured v2 a2) =>
(a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2
FT.fmap' ((a -> b) -> Entry k a -> Entry k b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f) FingerTree (Prio k a) (Entry k a)
xs)

-- | In ascending order of keys.
instance Ord k => Foldable (PQueue k) where
    foldMap :: (a -> m) -> PQueue k a -> m
foldMap a -> m
f PQueue k a
q = case PQueue k a -> Maybe (a, PQueue k a)
forall k v. Ord k => PQueue k v -> Maybe (v, PQueue k v)
minView PQueue k a
q of
        Maybe (a, PQueue k a)
Nothing -> m
forall a. Monoid a => a
mempty
        Just (a
v, PQueue k a
q') -> a -> m
f a
v m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` (a -> m) -> PQueue k a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f PQueue k a
q'
#if MIN_VERSION_base(4,8,0)
    null :: PQueue k a -> Bool
null (PQueue FingerTree (Prio k a) (Entry k a)
q) = FingerTree (Prio k a) (Entry k a) -> Bool
forall v a. FingerTree v a -> Bool
FT.null FingerTree (Prio k a) (Entry k a)
q
#endif

#if MIN_VERSION_base(4,9,0)
instance Ord k => Semigroup (PQueue k v) where
    <> :: PQueue k v -> PQueue k v -> PQueue k v
(<>) = PQueue k v -> PQueue k v -> PQueue k v
forall k v. Ord k => PQueue k v -> PQueue k v -> PQueue k v
union
#endif

-- | 'empty' and 'union'
instance Ord k => Monoid (PQueue k v) where
    mempty :: PQueue k v
mempty = PQueue k v
forall k v. Ord k => PQueue k v
empty
#if !(MIN_VERSION_base(4,11,0))
    mappend = union
#endif

instance (Ord k, Eq v) => Eq (PQueue k v) where
    PQueue k v
xs == :: PQueue k v -> PQueue k v -> Bool
== PQueue k v
ys = PQueue k v -> [(k, v)]
forall k v. Ord k => PQueue k v -> [(k, v)]
assocs PQueue k v
xs [(k, v)] -> [(k, v)] -> Bool
forall a. Eq a => a -> a -> Bool
== PQueue k v -> [(k, v)]
forall k v. Ord k => PQueue k v -> [(k, v)]
assocs PQueue k v
ys

-- | Lexicographical ordering
instance (Ord k, Ord v) => Ord (PQueue k v) where
    compare :: PQueue k v -> PQueue k v -> Ordering
compare PQueue k v
xs PQueue k v
ys = [(k, v)] -> [(k, v)] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (PQueue k v -> [(k, v)]
forall k v. Ord k => PQueue k v -> [(k, v)]
assocs PQueue k v
xs) (PQueue k v -> [(k, v)]
forall k v. Ord k => PQueue k v -> [(k, v)]
assocs PQueue k v
ys)

-- | In ascending key order
instance (Ord k, Show k, Show v) => Show (PQueue k v) where
    showsPrec :: Int -> PQueue k v -> ShowS
showsPrec Int
p PQueue k v
xs = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
        String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, v)] -> ShowS
forall a. Show a => a -> ShowS
shows (PQueue k v -> [(k, v)]
forall k v. Ord k => PQueue k v -> [(k, v)]
assocs PQueue k v
xs)

-- | /O(1)/. The empty priority queue.
empty :: Ord k => PQueue k v
empty :: PQueue k v
empty = FingerTree (Prio k v) (Entry k v) -> PQueue k v
forall k v. FingerTree (Prio k v) (Entry k v) -> PQueue k v
PQueue FingerTree (Prio k v) (Entry k v)
forall v a. Measured v a => FingerTree v a
FT.empty

-- | /O(1)/. A singleton priority queue.
singleton :: Ord k => k -> v -> PQueue k v
singleton :: k -> v -> PQueue k v
singleton k
k v
v = FingerTree (Prio k v) (Entry k v) -> PQueue k v
forall k v. FingerTree (Prio k v) (Entry k v) -> PQueue k v
PQueue (Entry k v -> FingerTree (Prio k v) (Entry k v)
forall v a. Measured v a => a -> FingerTree v a
FT.singleton (k -> v -> Entry k v
forall k v. k -> v -> Entry k v
Entry k
k v
v))

-- | /O(1)/. Add a (priority, value) pair to the front of a priority queue.
--
-- * @'insert' k v q = 'union' ('singleton' k v) q@
--
-- If @q@ contains entries with the same priority @k@, 'minView' of
-- @'insert' k v q@ will return them after this one.
insert :: Ord k => k -> v -> PQueue k v -> PQueue k v
insert :: k -> v -> PQueue k v -> PQueue k v
insert k
k v
v (PQueue FingerTree (Prio k v) (Entry k v)
q) = FingerTree (Prio k v) (Entry k v) -> PQueue k v
forall k v. FingerTree (Prio k v) (Entry k v) -> PQueue k v
PQueue (k -> v -> Entry k v
forall k v. k -> v -> Entry k v
Entry k
k v
v Entry k v
-> FingerTree (Prio k v) (Entry k v)
-> FingerTree (Prio k v) (Entry k v)
forall v a. Measured v a => a -> FingerTree v a -> FingerTree v a
<| FingerTree (Prio k v) (Entry k v)
q)

-- | /O(log n)/. Add a (priority, value) pair to the back of a priority queue.
--
-- * @'add' k v q = 'union' q ('singleton' k v)@
--
-- If @q@ contains entries with the same priority @k@, 'minView' of
-- @'add' k v q@ will return them before this one.
add :: Ord k => k -> v -> PQueue k v -> PQueue k v
add :: k -> v -> PQueue k v -> PQueue k v
add k
k v
v (PQueue FingerTree (Prio k v) (Entry k v)
q) = FingerTree (Prio k v) (Entry k v) -> PQueue k v
forall k v. FingerTree (Prio k v) (Entry k v) -> PQueue k v
PQueue (FingerTree (Prio k v) (Entry k v)
q FingerTree (Prio k v) (Entry k v)
-> Entry k v -> FingerTree (Prio k v) (Entry k v)
forall v a. Measured v a => FingerTree v a -> a -> FingerTree v a
|> k -> v -> Entry k v
forall k v. k -> v -> Entry k v
Entry k
k v
v)

-- | /O(log(min(n1,n2)))/. Concatenate two priority queues.
-- 'union' is associative, with identity 'empty'.
--
-- If there are entries with the same priority in both arguments, 'minView'
-- of @'union' xs ys@ will return those from @xs@ before those from @ys@.
union :: Ord k => PQueue k v -> PQueue k v -> PQueue k v
union :: PQueue k v -> PQueue k v -> PQueue k v
union (PQueue FingerTree (Prio k v) (Entry k v)
xs) (PQueue FingerTree (Prio k v) (Entry k v)
ys) = FingerTree (Prio k v) (Entry k v) -> PQueue k v
forall k v. FingerTree (Prio k v) (Entry k v) -> PQueue k v
PQueue (FingerTree (Prio k v) (Entry k v)
xs FingerTree (Prio k v) (Entry k v)
-> FingerTree (Prio k v) (Entry k v)
-> FingerTree (Prio k v) (Entry k v)
forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< FingerTree (Prio k v) (Entry k v)
ys)

-- | /O(n)/. Create a priority queue from a finite list of priorities
-- and values.
fromList :: Ord k => [(k, v)] -> PQueue k v
fromList :: [(k, v)] -> PQueue k v
fromList = ((k, v) -> PQueue k v -> PQueue k v)
-> PQueue k v -> [(k, v)] -> PQueue k v
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((k -> v -> PQueue k v -> PQueue k v)
-> (k, v) -> PQueue k v -> PQueue k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> PQueue k v -> PQueue k v
forall k v. Ord k => k -> v -> PQueue k v -> PQueue k v
insert) PQueue k v
forall k v. Ord k => PQueue k v
empty

-- | /O(1)/. Is this the empty priority queue?
null :: Ord k => PQueue k v -> Bool
null :: PQueue k v -> Bool
null (PQueue FingerTree (Prio k v) (Entry k v)
q) = FingerTree (Prio k v) (Entry k v) -> Bool
forall v a. FingerTree v a -> Bool
FT.null FingerTree (Prio k v) (Entry k v)
q

-- | /O(1)/ for the element, /O(log(n))/ for the reduced queue.
-- Returns 'Nothing' for an empty map, or the value associated with the
-- minimal priority together with the rest of the priority queue.
--
--  * @'minView' 'empty' = 'Nothing'@
--
--  * @'minView' ('singleton' k v) = 'Just' (v, 'empty')@
--
minView :: Ord k => PQueue k v -> Maybe (v, PQueue k v)
minView :: PQueue k v -> Maybe (v, PQueue k v)
minView PQueue k v
q = (((k, v), PQueue k v) -> (v, PQueue k v))
-> Maybe ((k, v), PQueue k v) -> Maybe (v, PQueue k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k, v) -> v
forall a b. (a, b) -> b
snd ((k, v) -> v)
-> (PQueue k v -> PQueue k v)
-> ((k, v), PQueue k v)
-> (v, PQueue k v)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** PQueue k v -> PQueue k v
forall a. a -> a
id) (PQueue k v -> Maybe ((k, v), PQueue k v)
forall k v. Ord k => PQueue k v -> Maybe ((k, v), PQueue k v)
minViewWithKey PQueue k v
q)

-- | /O(1)/ for the element, /O(log(n))/ for the reduced queue.
-- Returns 'Nothing' for an empty map, or the minimal (priority, value)
-- pair together with the rest of the priority queue.
--
--  * @'minViewWithKey' 'empty' = 'Nothing'@
--
--  * @'minViewWithKey' ('singleton' k v) = 'Just' ((k, v), 'empty')@
--
--  * If @'minViewWithKey' qi = 'Just' ((ki, vi), qi')@ and @k1 <= k2@,
--    then @'minViewWithKey' ('union' q1 q2) = 'Just' ((k1, v1), 'union' q1' q2)@
--
--  * If @'minViewWithKey' qi = 'Just' ((ki, vi), qi')@ and @k2 < k1@,
--    then @'minViewWithKey' ('union' q1 q2) = 'Just' ((k2, v2), 'union' q1 q2')@
--
minViewWithKey :: Ord k => PQueue k v -> Maybe ((k, v), PQueue k v)
minViewWithKey :: PQueue k v -> Maybe ((k, v), PQueue k v)
minViewWithKey (PQueue FingerTree (Prio k v) (Entry k v)
q)
  | FingerTree (Prio k v) (Entry k v) -> Bool
forall v a. FingerTree v a -> Bool
FT.null FingerTree (Prio k v) (Entry k v)
q = Maybe ((k, v), PQueue k v)
forall a. Maybe a
Nothing
  | Bool
otherwise = ((k, v), PQueue k v) -> Maybe ((k, v), PQueue k v)
forall a. a -> Maybe a
Just ((k
k, v
v), case FingerTree (Prio k v) (Entry k v)
-> ViewL (FingerTree (Prio k v)) (Entry k v)
forall v a.
Measured v a =>
FingerTree v a -> ViewL (FingerTree v) a
FT.viewl FingerTree (Prio k v) (Entry k v)
r of
    Entry k v
_ :< FingerTree (Prio k v) (Entry k v)
r' -> FingerTree (Prio k v) (Entry k v) -> PQueue k v
forall k v. FingerTree (Prio k v) (Entry k v) -> PQueue k v
PQueue (FingerTree (Prio k v) (Entry k v)
l FingerTree (Prio k v) (Entry k v)
-> FingerTree (Prio k v) (Entry k v)
-> FingerTree (Prio k v) (Entry k v)
forall v a.
Measured v a =>
FingerTree v a -> FingerTree v a -> FingerTree v a
>< FingerTree (Prio k v) (Entry k v)
r')
    ViewL (FingerTree (Prio k v)) (Entry k v)
_ -> String -> PQueue k v
forall a. HasCallStack => String -> a
error String
"can't happen")
  where
    Prio k
k v
v = FingerTree (Prio k v) (Entry k v) -> Prio k v
forall v a. Measured v a => a -> v
measure FingerTree (Prio k v) (Entry k v)
q
    (FingerTree (Prio k v) (Entry k v)
l, FingerTree (Prio k v) (Entry k v)
r) = (Prio k v -> Bool)
-> FingerTree (Prio k v) (Entry k v)
-> (FingerTree (Prio k v) (Entry k v),
    FingerTree (Prio k v) (Entry k v))
forall v a.
Measured v a =>
(v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a)
FT.split (k -> Prio k v -> Bool
forall k v. Ord k => k -> Prio k v -> Bool
below k
k) FingerTree (Prio k v) (Entry k v)
q

below :: Ord k => k -> Prio k v -> Bool
below :: k -> Prio k v -> Bool
below k
_ Prio k v
NoPrio = Bool
False
below k
k (Prio k
k' v
_) = k
k' k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<= k
k

-- | /O(n)/. Key-value pairs in ascending key order.
assocs :: Ord k => PQueue k v -> [(k, v)]
assocs :: PQueue k v -> [(k, v)]
assocs = (PQueue k v -> Maybe ((k, v), PQueue k v))
-> PQueue k v -> [(k, v)]
forall b a. (b -> Maybe (a, b)) -> b -> [a]
unfoldr PQueue k v -> Maybe ((k, v), PQueue k v)
forall k v. Ord k => PQueue k v -> Maybe ((k, v), PQueue k v)
minViewWithKey