{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE DeriveFoldable             #-}
{-# LANGUAGE DeriveFunctor              #-}
{-# LANGUAGE DeriveTraversable          #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE ScopedTypeVariables        #-}
module Data.HashPSQ.Internal
    ( -- * Type
      Bucket (..)
    , mkBucket
    , HashPSQ (..)

      -- * Query
    , null
    , size
    , member
    , lookup
    , findMin

      -- * Construction
    , empty
    , singleton

      -- * Insertion
    , insert

      -- * Delete/update
    , delete
    , deleteMin
    , alter
    , alterMin

      -- * Lists
    , fromList
    , toList
    , keys

      -- * Views
    , insertView
    , deleteView
    , minView
    , atMostView

      -- * Traversal
    , map
    , unsafeMapMonotonic
    , fold'

      -- * Unsafe operations
    , unsafeLookupIncreasePriority
    , unsafeInsertIncreasePriority
    , unsafeInsertIncreasePriorityView

      -- * Validity check
    , valid
    ) where

import           Control.DeepSeq      (NFData (..))
import           Data.Foldable        (Foldable)
import           Data.Hashable
import qualified Data.List            as List
import           Data.Maybe           (isJust)
import           Data.Traversable
import           Prelude              hiding (foldr, lookup, map, null)

import qualified Data.IntPSQ.Internal as IntPSQ
import qualified Data.OrdPSQ          as OrdPSQ

------------------------------------------------------------------------------
-- Types
------------------------------------------------------------------------------

data Bucket k p v = B !k !v !(OrdPSQ.OrdPSQ k p v)
    deriving (Bucket k p a -> Bool
(a -> m) -> Bucket k p a -> m
(a -> b -> b) -> b -> Bucket k p a -> b
(forall m. Monoid m => Bucket k p m -> m)
-> (forall m a. Monoid m => (a -> m) -> Bucket k p a -> m)
-> (forall m a. Monoid m => (a -> m) -> Bucket k p a -> m)
-> (forall a b. (a -> b -> b) -> b -> Bucket k p a -> b)
-> (forall a b. (a -> b -> b) -> b -> Bucket k p a -> b)
-> (forall b a. (b -> a -> b) -> b -> Bucket k p a -> b)
-> (forall b a. (b -> a -> b) -> b -> Bucket k p a -> b)
-> (forall a. (a -> a -> a) -> Bucket k p a -> a)
-> (forall a. (a -> a -> a) -> Bucket k p a -> a)
-> (forall a. Bucket k p a -> [a])
-> (forall a. Bucket k p a -> Bool)
-> (forall a. Bucket k p a -> Int)
-> (forall a. Eq a => a -> Bucket k p a -> Bool)
-> (forall a. Ord a => Bucket k p a -> a)
-> (forall a. Ord a => Bucket k p a -> a)
-> (forall a. Num a => Bucket k p a -> a)
-> (forall a. Num a => Bucket k p a -> a)
-> Foldable (Bucket k p)
forall a. Eq a => a -> Bucket k p a -> Bool
forall a. Num a => Bucket k p a -> a
forall a. Ord a => Bucket k p a -> a
forall m. Monoid m => Bucket k p m -> m
forall a. Bucket k p a -> Bool
forall a. Bucket k p a -> Int
forall a. Bucket k p a -> [a]
forall a. (a -> a -> a) -> Bucket k p a -> a
forall m a. Monoid m => (a -> m) -> Bucket k p a -> m
forall b a. (b -> a -> b) -> b -> Bucket k p a -> b
forall a b. (a -> b -> b) -> b -> Bucket k p a -> b
forall k p a. Eq a => a -> Bucket k p a -> Bool
forall k p a. Num a => Bucket k p a -> a
forall k p a. Ord a => Bucket k p a -> a
forall k p m. Monoid m => Bucket k p m -> m
forall k p a. Bucket k p a -> Bool
forall k p a. Bucket k p a -> Int
forall k p a. Bucket k p a -> [a]
forall k p a. (a -> a -> a) -> Bucket k p a -> a
forall k p m a. Monoid m => (a -> m) -> Bucket k p a -> m
forall k p b a. (b -> a -> b) -> b -> Bucket k p a -> b
forall k p a b. (a -> b -> b) -> b -> Bucket k p a -> b
forall (t :: * -> *).
(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 :: Bucket k p a -> a
$cproduct :: forall k p a. Num a => Bucket k p a -> a
sum :: Bucket k p a -> a
$csum :: forall k p a. Num a => Bucket k p a -> a
minimum :: Bucket k p a -> a
$cminimum :: forall k p a. Ord a => Bucket k p a -> a
maximum :: Bucket k p a -> a
$cmaximum :: forall k p a. Ord a => Bucket k p a -> a
elem :: a -> Bucket k p a -> Bool
$celem :: forall k p a. Eq a => a -> Bucket k p a -> Bool
length :: Bucket k p a -> Int
$clength :: forall k p a. Bucket k p a -> Int
null :: Bucket k p a -> Bool
$cnull :: forall k p a. Bucket k p a -> Bool
toList :: Bucket k p a -> [a]
$ctoList :: forall k p a. Bucket k p a -> [a]
foldl1 :: (a -> a -> a) -> Bucket k p a -> a
$cfoldl1 :: forall k p a. (a -> a -> a) -> Bucket k p a -> a
foldr1 :: (a -> a -> a) -> Bucket k p a -> a
$cfoldr1 :: forall k p a. (a -> a -> a) -> Bucket k p a -> a
foldl' :: (b -> a -> b) -> b -> Bucket k p a -> b
$cfoldl' :: forall k p b a. (b -> a -> b) -> b -> Bucket k p a -> b
foldl :: (b -> a -> b) -> b -> Bucket k p a -> b
$cfoldl :: forall k p b a. (b -> a -> b) -> b -> Bucket k p a -> b
foldr' :: (a -> b -> b) -> b -> Bucket k p a -> b
$cfoldr' :: forall k p a b. (a -> b -> b) -> b -> Bucket k p a -> b
foldr :: (a -> b -> b) -> b -> Bucket k p a -> b
$cfoldr :: forall k p a b. (a -> b -> b) -> b -> Bucket k p a -> b
foldMap' :: (a -> m) -> Bucket k p a -> m
$cfoldMap' :: forall k p m a. Monoid m => (a -> m) -> Bucket k p a -> m
foldMap :: (a -> m) -> Bucket k p a -> m
$cfoldMap :: forall k p m a. Monoid m => (a -> m) -> Bucket k p a -> m
fold :: Bucket k p m -> m
$cfold :: forall k p m. Monoid m => Bucket k p m -> m
Foldable, a -> Bucket k p b -> Bucket k p a
(a -> b) -> Bucket k p a -> Bucket k p b
(forall a b. (a -> b) -> Bucket k p a -> Bucket k p b)
-> (forall a b. a -> Bucket k p b -> Bucket k p a)
-> Functor (Bucket k p)
forall a b. a -> Bucket k p b -> Bucket k p a
forall a b. (a -> b) -> Bucket k p a -> Bucket k p b
forall k p a b. a -> Bucket k p b -> Bucket k p a
forall k p a b. (a -> b) -> Bucket k p a -> Bucket k p b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Bucket k p b -> Bucket k p a
$c<$ :: forall k p a b. a -> Bucket k p b -> Bucket k p a
fmap :: (a -> b) -> Bucket k p a -> Bucket k p b
$cfmap :: forall k p a b. (a -> b) -> Bucket k p a -> Bucket k p b
Functor, Int -> Bucket k p v -> ShowS
[Bucket k p v] -> ShowS
Bucket k p v -> String
(Int -> Bucket k p v -> ShowS)
-> (Bucket k p v -> String)
-> ([Bucket k p v] -> ShowS)
-> Show (Bucket k p v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k p v.
(Show k, Show v, Show p) =>
Int -> Bucket k p v -> ShowS
forall k p v. (Show k, Show v, Show p) => [Bucket k p v] -> ShowS
forall k p v. (Show k, Show v, Show p) => Bucket k p v -> String
showList :: [Bucket k p v] -> ShowS
$cshowList :: forall k p v. (Show k, Show v, Show p) => [Bucket k p v] -> ShowS
show :: Bucket k p v -> String
$cshow :: forall k p v. (Show k, Show v, Show p) => Bucket k p v -> String
showsPrec :: Int -> Bucket k p v -> ShowS
$cshowsPrec :: forall k p v.
(Show k, Show v, Show p) =>
Int -> Bucket k p v -> ShowS
Show, Functor (Bucket k p)
Foldable (Bucket k p)
Functor (Bucket k p)
-> Foldable (Bucket k p)
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Bucket k p a -> f (Bucket k p b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Bucket k p (f a) -> f (Bucket k p a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Bucket k p a -> m (Bucket k p b))
-> (forall (m :: * -> *) a.
    Monad m =>
    Bucket k p (m a) -> m (Bucket k p a))
-> Traversable (Bucket k p)
(a -> f b) -> Bucket k p a -> f (Bucket k p b)
forall k p. Functor (Bucket k p)
forall k p. Foldable (Bucket k p)
forall k p (m :: * -> *) a.
Monad m =>
Bucket k p (m a) -> m (Bucket k p a)
forall k p (f :: * -> *) a.
Applicative f =>
Bucket k p (f a) -> f (Bucket k p a)
forall k p (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Bucket k p a -> m (Bucket k p b)
forall k p (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Bucket k p a -> f (Bucket k p b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
Bucket k p (m a) -> m (Bucket k p a)
forall (f :: * -> *) a.
Applicative f =>
Bucket k p (f a) -> f (Bucket k p a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Bucket k p a -> m (Bucket k p b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Bucket k p a -> f (Bucket k p b)
sequence :: Bucket k p (m a) -> m (Bucket k p a)
$csequence :: forall k p (m :: * -> *) a.
Monad m =>
Bucket k p (m a) -> m (Bucket k p a)
mapM :: (a -> m b) -> Bucket k p a -> m (Bucket k p b)
$cmapM :: forall k p (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Bucket k p a -> m (Bucket k p b)
sequenceA :: Bucket k p (f a) -> f (Bucket k p a)
$csequenceA :: forall k p (f :: * -> *) a.
Applicative f =>
Bucket k p (f a) -> f (Bucket k p a)
traverse :: (a -> f b) -> Bucket k p a -> f (Bucket k p b)
$ctraverse :: forall k p (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Bucket k p a -> f (Bucket k p b)
$cp2Traversable :: forall k p. Foldable (Bucket k p)
$cp1Traversable :: forall k p. Functor (Bucket k p)
Traversable)

-- | Smart constructor which takes care of placing the minimum element directly
-- in the 'Bucket'.
{-# INLINABLE mkBucket #-}
mkBucket
    :: (Ord k, Ord p)
    => k -> p -> v -> OrdPSQ.OrdPSQ k p v -> (p, Bucket k p v)
mkBucket :: k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
mkBucket k
k p
p v
x OrdPSQ k p v
opsq =
    -- TODO (jaspervdj): We could do an 'unsafeInsertNew' here for all call
    -- sites.
    case OrdPSQ k p v -> Maybe (p, Bucket k p v)
forall k p v.
(Ord k, Ord p) =>
OrdPSQ k p v -> Maybe (p, Bucket k p v)
toBucket (k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
OrdPSQ.insert k
k p
p v
x OrdPSQ k p v
opsq) of
        Just (p, Bucket k p v)
bucket -> (p, Bucket k p v)
bucket
        Maybe (p, Bucket k p v)
Nothing     -> String -> (p, Bucket k p v)
forall a. HasCallStack => String -> a
error (String -> (p, Bucket k p v)) -> String -> (p, Bucket k p v)
forall a b. (a -> b) -> a -> b
$ String
"mkBucket: internal error"

toBucket :: (Ord k, Ord p) => OrdPSQ.OrdPSQ k p v -> Maybe (p, Bucket k p v)
toBucket :: OrdPSQ k p v -> Maybe (p, Bucket k p v)
toBucket OrdPSQ k p v
opsq = case OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v)
forall k p v.
(Ord k, Ord p) =>
OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v)
OrdPSQ.minView OrdPSQ k p v
opsq of
    Just (k
k, p
p, v
x, OrdPSQ k p v
opsq') -> (p, Bucket k p v) -> Maybe (p, Bucket k p v)
forall a. a -> Maybe a
Just (p
p, k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k v
x OrdPSQ k p v
opsq')
    Maybe (k, p, v, OrdPSQ k p v)
Nothing               -> Maybe (p, Bucket k p v)
forall a. Maybe a
Nothing

instance (NFData k, NFData p, NFData v) => NFData (Bucket k p v) where
    rnf :: Bucket k p v -> ()
rnf (B k
k v
v OrdPSQ k p v
x) = k -> ()
forall a. NFData a => a -> ()
rnf k
k () -> () -> ()
`seq` v -> ()
forall a. NFData a => a -> ()
rnf v
v () -> () -> ()
`seq` OrdPSQ k p v -> ()
forall a. NFData a => a -> ()
rnf OrdPSQ k p v
x

-- | A priority search queue with keys of type @k@ and priorities of type @p@
-- and values of type @v@. It is strict in keys, priorities and values.
newtype HashPSQ k p v = HashPSQ (IntPSQ.IntPSQ p (Bucket k p v))
    deriving (HashPSQ k p a -> Bool
(a -> m) -> HashPSQ k p a -> m
(a -> b -> b) -> b -> HashPSQ k p a -> b
(forall m. Monoid m => HashPSQ k p m -> m)
-> (forall m a. Monoid m => (a -> m) -> HashPSQ k p a -> m)
-> (forall m a. Monoid m => (a -> m) -> HashPSQ k p a -> m)
-> (forall a b. (a -> b -> b) -> b -> HashPSQ k p a -> b)
-> (forall a b. (a -> b -> b) -> b -> HashPSQ k p a -> b)
-> (forall b a. (b -> a -> b) -> b -> HashPSQ k p a -> b)
-> (forall b a. (b -> a -> b) -> b -> HashPSQ k p a -> b)
-> (forall a. (a -> a -> a) -> HashPSQ k p a -> a)
-> (forall a. (a -> a -> a) -> HashPSQ k p a -> a)
-> (forall a. HashPSQ k p a -> [a])
-> (forall a. HashPSQ k p a -> Bool)
-> (forall a. HashPSQ k p a -> Int)
-> (forall a. Eq a => a -> HashPSQ k p a -> Bool)
-> (forall a. Ord a => HashPSQ k p a -> a)
-> (forall a. Ord a => HashPSQ k p a -> a)
-> (forall a. Num a => HashPSQ k p a -> a)
-> (forall a. Num a => HashPSQ k p a -> a)
-> Foldable (HashPSQ k p)
forall a. Eq a => a -> HashPSQ k p a -> Bool
forall a. Num a => HashPSQ k p a -> a
forall a. Ord a => HashPSQ k p a -> a
forall m. Monoid m => HashPSQ k p m -> m
forall a. HashPSQ k p a -> Bool
forall a. HashPSQ k p a -> Int
forall a. HashPSQ k p a -> [a]
forall a. (a -> a -> a) -> HashPSQ k p a -> a
forall m a. Monoid m => (a -> m) -> HashPSQ k p a -> m
forall b a. (b -> a -> b) -> b -> HashPSQ k p a -> b
forall a b. (a -> b -> b) -> b -> HashPSQ k p a -> b
forall k p a. Eq a => a -> HashPSQ k p a -> Bool
forall k p a. Num a => HashPSQ k p a -> a
forall k p a. Ord a => HashPSQ k p a -> a
forall k p m. Monoid m => HashPSQ k p m -> m
forall k p a. HashPSQ k p a -> Bool
forall k p a. HashPSQ k p a -> Int
forall k p a. HashPSQ k p a -> [a]
forall k p a. (a -> a -> a) -> HashPSQ k p a -> a
forall k p m a. Monoid m => (a -> m) -> HashPSQ k p a -> m
forall k p b a. (b -> a -> b) -> b -> HashPSQ k p a -> b
forall k p a b. (a -> b -> b) -> b -> HashPSQ k p a -> b
forall (t :: * -> *).
(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 :: HashPSQ k p a -> a
$cproduct :: forall k p a. Num a => HashPSQ k p a -> a
sum :: HashPSQ k p a -> a
$csum :: forall k p a. Num a => HashPSQ k p a -> a
minimum :: HashPSQ k p a -> a
$cminimum :: forall k p a. Ord a => HashPSQ k p a -> a
maximum :: HashPSQ k p a -> a
$cmaximum :: forall k p a. Ord a => HashPSQ k p a -> a
elem :: a -> HashPSQ k p a -> Bool
$celem :: forall k p a. Eq a => a -> HashPSQ k p a -> Bool
length :: HashPSQ k p a -> Int
$clength :: forall k p a. HashPSQ k p a -> Int
null :: HashPSQ k p a -> Bool
$cnull :: forall k p a. HashPSQ k p a -> Bool
toList :: HashPSQ k p a -> [a]
$ctoList :: forall k p a. HashPSQ k p a -> [a]
foldl1 :: (a -> a -> a) -> HashPSQ k p a -> a
$cfoldl1 :: forall k p a. (a -> a -> a) -> HashPSQ k p a -> a
foldr1 :: (a -> a -> a) -> HashPSQ k p a -> a
$cfoldr1 :: forall k p a. (a -> a -> a) -> HashPSQ k p a -> a
foldl' :: (b -> a -> b) -> b -> HashPSQ k p a -> b
$cfoldl' :: forall k p b a. (b -> a -> b) -> b -> HashPSQ k p a -> b
foldl :: (b -> a -> b) -> b -> HashPSQ k p a -> b
$cfoldl :: forall k p b a. (b -> a -> b) -> b -> HashPSQ k p a -> b
foldr' :: (a -> b -> b) -> b -> HashPSQ k p a -> b
$cfoldr' :: forall k p a b. (a -> b -> b) -> b -> HashPSQ k p a -> b
foldr :: (a -> b -> b) -> b -> HashPSQ k p a -> b
$cfoldr :: forall k p a b. (a -> b -> b) -> b -> HashPSQ k p a -> b
foldMap' :: (a -> m) -> HashPSQ k p a -> m
$cfoldMap' :: forall k p m a. Monoid m => (a -> m) -> HashPSQ k p a -> m
foldMap :: (a -> m) -> HashPSQ k p a -> m
$cfoldMap :: forall k p m a. Monoid m => (a -> m) -> HashPSQ k p a -> m
fold :: HashPSQ k p m -> m
$cfold :: forall k p m. Monoid m => HashPSQ k p m -> m
Foldable, a -> HashPSQ k p b -> HashPSQ k p a
(a -> b) -> HashPSQ k p a -> HashPSQ k p b
(forall a b. (a -> b) -> HashPSQ k p a -> HashPSQ k p b)
-> (forall a b. a -> HashPSQ k p b -> HashPSQ k p a)
-> Functor (HashPSQ k p)
forall a b. a -> HashPSQ k p b -> HashPSQ k p a
forall a b. (a -> b) -> HashPSQ k p a -> HashPSQ k p b
forall k p a b. a -> HashPSQ k p b -> HashPSQ k p a
forall k p a b. (a -> b) -> HashPSQ k p a -> HashPSQ k p b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> HashPSQ k p b -> HashPSQ k p a
$c<$ :: forall k p a b. a -> HashPSQ k p b -> HashPSQ k p a
fmap :: (a -> b) -> HashPSQ k p a -> HashPSQ k p b
$cfmap :: forall k p a b. (a -> b) -> HashPSQ k p a -> HashPSQ k p b
Functor, HashPSQ k p v -> ()
(HashPSQ k p v -> ()) -> NFData (HashPSQ k p v)
forall a. (a -> ()) -> NFData a
forall k p v. (NFData p, NFData k, NFData v) => HashPSQ k p v -> ()
rnf :: HashPSQ k p v -> ()
$crnf :: forall k p v. (NFData p, NFData k, NFData v) => HashPSQ k p v -> ()
NFData, Int -> HashPSQ k p v -> ShowS
[HashPSQ k p v] -> ShowS
HashPSQ k p v -> String
(Int -> HashPSQ k p v -> ShowS)
-> (HashPSQ k p v -> String)
-> ([HashPSQ k p v] -> ShowS)
-> Show (HashPSQ k p v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k p v.
(Show p, Show k, Show v) =>
Int -> HashPSQ k p v -> ShowS
forall k p v. (Show p, Show k, Show v) => [HashPSQ k p v] -> ShowS
forall k p v. (Show p, Show k, Show v) => HashPSQ k p v -> String
showList :: [HashPSQ k p v] -> ShowS
$cshowList :: forall k p v. (Show p, Show k, Show v) => [HashPSQ k p v] -> ShowS
show :: HashPSQ k p v -> String
$cshow :: forall k p v. (Show p, Show k, Show v) => HashPSQ k p v -> String
showsPrec :: Int -> HashPSQ k p v -> ShowS
$cshowsPrec :: forall k p v.
(Show p, Show k, Show v) =>
Int -> HashPSQ k p v -> ShowS
Show, Functor (HashPSQ k p)
Foldable (HashPSQ k p)
Functor (HashPSQ k p)
-> Foldable (HashPSQ k p)
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> HashPSQ k p a -> f (HashPSQ k p b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    HashPSQ k p (f a) -> f (HashPSQ k p a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> HashPSQ k p a -> m (HashPSQ k p b))
-> (forall (m :: * -> *) a.
    Monad m =>
    HashPSQ k p (m a) -> m (HashPSQ k p a))
-> Traversable (HashPSQ k p)
(a -> f b) -> HashPSQ k p a -> f (HashPSQ k p b)
forall k p. Functor (HashPSQ k p)
forall k p. Foldable (HashPSQ k p)
forall k p (m :: * -> *) a.
Monad m =>
HashPSQ k p (m a) -> m (HashPSQ k p a)
forall k p (f :: * -> *) a.
Applicative f =>
HashPSQ k p (f a) -> f (HashPSQ k p a)
forall k p (m :: * -> *) a b.
Monad m =>
(a -> m b) -> HashPSQ k p a -> m (HashPSQ k p b)
forall k p (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> HashPSQ k p a -> f (HashPSQ k p b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
HashPSQ k p (m a) -> m (HashPSQ k p a)
forall (f :: * -> *) a.
Applicative f =>
HashPSQ k p (f a) -> f (HashPSQ k p a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> HashPSQ k p a -> m (HashPSQ k p b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> HashPSQ k p a -> f (HashPSQ k p b)
sequence :: HashPSQ k p (m a) -> m (HashPSQ k p a)
$csequence :: forall k p (m :: * -> *) a.
Monad m =>
HashPSQ k p (m a) -> m (HashPSQ k p a)
mapM :: (a -> m b) -> HashPSQ k p a -> m (HashPSQ k p b)
$cmapM :: forall k p (m :: * -> *) a b.
Monad m =>
(a -> m b) -> HashPSQ k p a -> m (HashPSQ k p b)
sequenceA :: HashPSQ k p (f a) -> f (HashPSQ k p a)
$csequenceA :: forall k p (f :: * -> *) a.
Applicative f =>
HashPSQ k p (f a) -> f (HashPSQ k p a)
traverse :: (a -> f b) -> HashPSQ k p a -> f (HashPSQ k p b)
$ctraverse :: forall k p (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> HashPSQ k p a -> f (HashPSQ k p b)
$cp2Traversable :: forall k p. Foldable (HashPSQ k p)
$cp1Traversable :: forall k p. Functor (HashPSQ k p)
Traversable)

instance (Eq k, Eq p, Eq v, Hashable k, Ord k, Ord p) =>
            Eq (HashPSQ k p v) where
    HashPSQ k p v
x == :: HashPSQ k p v -> HashPSQ k p v -> Bool
== HashPSQ k p v
y = case (HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
forall k p v.
(Hashable k, Ord k, Ord p) =>
HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
minView HashPSQ k p v
x, HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
forall k p v.
(Hashable k, Ord k, Ord p) =>
HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
minView HashPSQ k p v
y) of
        (Maybe (k, p, v, HashPSQ k p v)
Nothing              , Maybe (k, p, v, HashPSQ k p v)
Nothing                ) -> Bool
True
        (Just (k
xk, p
xp, v
xv, HashPSQ k p v
x'), (Just (k
yk, p
yp, v
yv, HashPSQ k p v
y'))) ->
            k
xk k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
yk Bool -> Bool -> Bool
&& p
xp p -> p -> Bool
forall a. Eq a => a -> a -> Bool
== p
yp Bool -> Bool -> Bool
&& v
xv v -> v -> Bool
forall a. Eq a => a -> a -> Bool
== v
yv Bool -> Bool -> Bool
&& HashPSQ k p v
x' HashPSQ k p v -> HashPSQ k p v -> Bool
forall a. Eq a => a -> a -> Bool
== HashPSQ k p v
y'
        (Just (k, p, v, HashPSQ k p v)
_               , Maybe (k, p, v, HashPSQ k p v)
Nothing                ) -> Bool
False
        (Maybe (k, p, v, HashPSQ k p v)
Nothing              , Just (k, p, v, HashPSQ k p v)
_                 ) -> Bool
False


------------------------------------------------------------------------------
-- Query
------------------------------------------------------------------------------

-- | /O(1)/ True if the queue is empty.
{-# INLINABLE null #-}
null :: HashPSQ k p v -> Bool
null :: HashPSQ k p v -> Bool
null (HashPSQ IntPSQ p (Bucket k p v)
ipsq) = IntPSQ p (Bucket k p v) -> Bool
forall p v. IntPSQ p v -> Bool
IntPSQ.null IntPSQ p (Bucket k p v)
ipsq

-- | /O(n)/ The number of elements stored in the PSQ.
{-# INLINABLE size #-}
size :: HashPSQ k p v -> Int
size :: HashPSQ k p v -> Int
size (HashPSQ IntPSQ p (Bucket k p v)
ipsq) = (Int -> p -> Bucket k p v -> Int -> Int)
-> Int -> IntPSQ p (Bucket k p v) -> Int
forall p v a. (Int -> p -> v -> a -> a) -> a -> IntPSQ p v -> a
IntPSQ.fold'
    (\Int
_ p
_ (B k
_ v
_ OrdPSQ k p v
opsq) Int
acc -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ OrdPSQ k p v -> Int
forall k p v. OrdPSQ k p v -> Int
OrdPSQ.size OrdPSQ k p v
opsq Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
acc)
    Int
0
    IntPSQ p (Bucket k p v)
ipsq

-- | /O(min(n,W))/ Check if a key is present in the the queue.
{-# INLINABLE member #-}
member :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Bool
member :: k -> HashPSQ k p v -> Bool
member k
k = Maybe (p, v) -> Bool
forall a. Maybe a -> Bool
isJust (Maybe (p, v) -> Bool)
-> (HashPSQ k p v -> Maybe (p, v)) -> HashPSQ k p v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> HashPSQ k p v -> Maybe (p, v)
forall k p v.
(Ord k, Hashable k, Ord p) =>
k -> HashPSQ k p v -> Maybe (p, v)
lookup k
k

-- | /O(min(n,W))/ The priority and value of a given key, or 'Nothing' if the
-- key is not bound.
{-# INLINABLE lookup #-}
lookup :: (Ord k, Hashable k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v)
lookup :: k -> HashPSQ k p v -> Maybe (p, v)
lookup k
k (HashPSQ IntPSQ p (Bucket k p v)
ipsq) = do
    (p
p0, B k
k0 v
v0 OrdPSQ k p v
os) <- Int -> IntPSQ p (Bucket k p v) -> Maybe (p, Bucket k p v)
forall p v. Int -> IntPSQ p v -> Maybe (p, v)
IntPSQ.lookup (k -> Int
forall a. Hashable a => a -> Int
hash k
k) IntPSQ p (Bucket k p v)
ipsq
    if k
k0 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k
        then (p, v) -> Maybe (p, v)
forall (m :: * -> *) a. Monad m => a -> m a
return (p
p0, v
v0)
        else k -> OrdPSQ k p v -> Maybe (p, v)
forall k p v. Ord k => k -> OrdPSQ k p v -> Maybe (p, v)
OrdPSQ.lookup k
k OrdPSQ k p v
os

-- | /O(1)/ The element with the lowest priority.
findMin :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v)
findMin :: HashPSQ k p v -> Maybe (k, p, v)
findMin (HashPSQ IntPSQ p (Bucket k p v)
ipsq) = case IntPSQ p (Bucket k p v) -> Maybe (Int, p, Bucket k p v)
forall p v. Ord p => IntPSQ p v -> Maybe (Int, p, v)
IntPSQ.findMin IntPSQ p (Bucket k p v)
ipsq of
    Maybe (Int, p, Bucket k p v)
Nothing              -> Maybe (k, p, v)
forall a. Maybe a
Nothing
    Just (Int
_, p
p, B k
k v
x OrdPSQ k p v
_) -> (k, p, v) -> Maybe (k, p, v)
forall a. a -> Maybe a
Just (k
k, p
p, v
x)


--------------------------------------------------------------------------------
-- Construction
--------------------------------------------------------------------------------

-- | /O(1)/ The empty queue.
empty :: HashPSQ k p v
empty :: HashPSQ k p v
empty = IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ IntPSQ p (Bucket k p v)
forall p v. IntPSQ p v
IntPSQ.empty

-- | /O(1)/ Build a queue with one element.
singleton :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v
singleton :: k -> p -> v -> HashPSQ k p v
singleton k
k p
p v
v = k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
forall k p v.
(Ord k, Hashable k, Ord p) =>
k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
insert k
k p
p v
v HashPSQ k p v
forall k p v. HashPSQ k p v
empty


--------------------------------------------------------------------------------
-- Insertion
--------------------------------------------------------------------------------

-- | /O(min(n,W))/ Insert a new key, priority and value into the queue. If the key
-- is already present in the queue, the associated priority and value are
-- replaced with the supplied priority and value.
{-# INLINABLE insert #-}
insert
    :: (Ord k, Hashable k, Ord p)
    => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
insert :: k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
insert k
k p
p v
v (HashPSQ IntPSQ p (Bucket k p v)
ipsq) =
    case (Maybe (p, Bucket k p v) -> ((), Maybe (p, Bucket k p v)))
-> Int -> IntPSQ p (Bucket k p v) -> ((), IntPSQ p (Bucket k p v))
forall p v b.
Ord p =>
(Maybe (p, v) -> (b, Maybe (p, v)))
-> Int -> IntPSQ p v -> (b, IntPSQ p v)
IntPSQ.alter (\Maybe (p, Bucket k p v)
x -> ((), Maybe (p, Bucket k p v) -> Maybe (p, Bucket k p v)
ins Maybe (p, Bucket k p v)
x)) (k -> Int
forall a. Hashable a => a -> Int
hash k
k) IntPSQ p (Bucket k p v)
ipsq of
        ((), IntPSQ p (Bucket k p v)
ipsq') -> IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ IntPSQ p (Bucket k p v)
ipsq'
  where
    ins :: Maybe (p, Bucket k p v) -> Maybe (p, Bucket k p v)
ins Maybe (p, Bucket k p v)
Nothing                         = (p, Bucket k p v) -> Maybe (p, Bucket k p v)
forall a. a -> Maybe a
Just (p
p,  k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k  v
v  (OrdPSQ k p v
forall k p v. OrdPSQ k p v
OrdPSQ.empty))
    ins (Just (p
p', B k
k' v
v' OrdPSQ k p v
os))
        | k
k' k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k                       =
            -- Tricky: p might have less priority than an item in 'os'.
            (p, Bucket k p v) -> Maybe (p, Bucket k p v)
forall a. a -> Maybe a
Just (k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
mkBucket k
k p
p v
v OrdPSQ k p v
os)
        | p
p' p -> p -> Bool
forall a. Ord a => a -> a -> Bool
< p
p Bool -> Bool -> Bool
|| (p
p p -> p -> Bool
forall a. Eq a => a -> a -> Bool
== p
p' Bool -> Bool -> Bool
&& k
k' k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k) =
            (p, Bucket k p v) -> Maybe (p, Bucket k p v)
forall a. a -> Maybe a
Just (p
p', k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k' v
v' (k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
OrdPSQ.insert k
k  p
p  v
v  OrdPSQ k p v
os))
        | k -> OrdPSQ k p v -> Bool
forall k p v. Ord k => k -> OrdPSQ k p v -> Bool
OrdPSQ.member k
k OrdPSQ k p v
os            =
            -- This is a bit tricky: k might already be present in 'os' and we
            -- don't want to end up with duplicate keys.
            (p, Bucket k p v) -> Maybe (p, Bucket k p v)
forall a. a -> Maybe a
Just (p
p,  k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k  v
v  (k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
OrdPSQ.insert k
k' p
p' v
v' (k -> OrdPSQ k p v -> OrdPSQ k p v
forall k p v. (Ord k, Ord p) => k -> OrdPSQ k p v -> OrdPSQ k p v
OrdPSQ.delete k
k OrdPSQ k p v
os)))
        | Bool
otherwise                     =
            (p, Bucket k p v) -> Maybe (p, Bucket k p v)
forall a. a -> Maybe a
Just (p
p , k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k  v
v  (k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
OrdPSQ.insert k
k' p
p' v
v' OrdPSQ k p v
os))


--------------------------------------------------------------------------------
-- Delete/update
--------------------------------------------------------------------------------

-- | /O(min(n,W))/ Delete a key and its priority and value from the queue. When
-- the key is not a member of the queue, the original queue is returned.
{-# INLINE delete #-}
delete
    :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> HashPSQ k p v
delete :: k -> HashPSQ k p v -> HashPSQ k p v
delete k
k HashPSQ k p v
t = case k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v)
forall k p v.
(Hashable k, Ord k, Ord p) =>
k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v)
deleteView k
k HashPSQ k p v
t of
    Maybe (p, v, HashPSQ k p v)
Nothing         -> HashPSQ k p v
t
    Just (p
_, v
_, HashPSQ k p v
t') -> HashPSQ k p v
t'

-- | /O(min(n,W))/ Delete the binding with the least priority, and return the
-- rest of the queue stripped of that binding. In case the queue is empty, the
-- empty queue is returned again.
{-# INLINE deleteMin #-}
deleteMin
    :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> HashPSQ k p v
deleteMin :: HashPSQ k p v -> HashPSQ k p v
deleteMin HashPSQ k p v
t = case HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
forall k p v.
(Hashable k, Ord k, Ord p) =>
HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
minView HashPSQ k p v
t of
    Maybe (k, p, v, HashPSQ k p v)
Nothing            -> HashPSQ k p v
t
    Just (k
_, p
_, v
_, HashPSQ k p v
t') -> HashPSQ k p v
t'

-- | /O(min(n,W))/ The expression @alter f k queue@ alters the value @x@ at @k@,
-- or absence thereof. 'alter' can be used to insert, delete, or update a value
-- in a queue. It also allows you to calculate an additional value @b@.
{-# INLINABLE alter #-}
alter :: (Hashable k, Ord k, Ord p)
      => (Maybe (p, v) -> (b, Maybe (p, v)))
      -> k -> HashPSQ k p v -> (b, HashPSQ k p v)
alter :: (Maybe (p, v) -> (b, Maybe (p, v)))
-> k -> HashPSQ k p v -> (b, HashPSQ k p v)
alter Maybe (p, v) -> (b, Maybe (p, v))
f k
k (HashPSQ IntPSQ p (Bucket k p v)
ipsq) = case Int
-> IntPSQ p (Bucket k p v)
-> Maybe (p, Bucket k p v, IntPSQ p (Bucket k p v))
forall p v. Ord p => Int -> IntPSQ p v -> Maybe (p, v, IntPSQ p v)
IntPSQ.deleteView Int
h IntPSQ p (Bucket k p v)
ipsq of
    Maybe (p, Bucket k p v, IntPSQ p (Bucket k p v))
Nothing -> case Maybe (p, v) -> (b, Maybe (p, v))
f Maybe (p, v)
forall a. Maybe a
Nothing of
        (b
b, Maybe (p, v)
Nothing)     -> (b
b, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ IntPSQ p (Bucket k p v)
ipsq)
        (b
b, Just (p
p, v
x)) ->
            (b
b, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ (IntPSQ p (Bucket k p v) -> HashPSQ k p v)
-> IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall a b. (a -> b) -> a -> b
$ Int
-> p
-> Bucket k p v
-> IntPSQ p (Bucket k p v)
-> IntPSQ p (Bucket k p v)
forall p v. Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v
IntPSQ.unsafeInsertNew Int
h p
p (k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k v
x OrdPSQ k p v
forall k p v. OrdPSQ k p v
OrdPSQ.empty) IntPSQ p (Bucket k p v)
ipsq)
    Just (p
bp, B k
bk v
bx OrdPSQ k p v
opsq, IntPSQ p (Bucket k p v)
ipsq')
        | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
bk   -> case Maybe (p, v) -> (b, Maybe (p, v))
f ((p, v) -> Maybe (p, v)
forall a. a -> Maybe a
Just (p
bp, v
bx)) of
            (b
b, Maybe (p, v)
Nothing) -> case OrdPSQ k p v -> Maybe (p, Bucket k p v)
forall k p v.
(Ord k, Ord p) =>
OrdPSQ k p v -> Maybe (p, Bucket k p v)
toBucket OrdPSQ k p v
opsq of
                Maybe (p, Bucket k p v)
Nothing             -> (b
b, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ IntPSQ p (Bucket k p v)
ipsq')
                Just (p
bp', Bucket k p v
bucket') ->
                    (b
b, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ (IntPSQ p (Bucket k p v) -> HashPSQ k p v)
-> IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall a b. (a -> b) -> a -> b
$ Int
-> p
-> Bucket k p v
-> IntPSQ p (Bucket k p v)
-> IntPSQ p (Bucket k p v)
forall p v. Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v
IntPSQ.unsafeInsertNew Int
h p
bp' Bucket k p v
bucket' IntPSQ p (Bucket k p v)
ipsq')
            (b
b, Just (p
p, v
x)) -> case k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
mkBucket k
k p
p v
x OrdPSQ k p v
opsq of
                (p
bp', Bucket k p v
bucket') ->
                    (b
b, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ (IntPSQ p (Bucket k p v) -> HashPSQ k p v)
-> IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall a b. (a -> b) -> a -> b
$ Int
-> p
-> Bucket k p v
-> IntPSQ p (Bucket k p v)
-> IntPSQ p (Bucket k p v)
forall p v. Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v
IntPSQ.unsafeInsertNew Int
h p
bp' Bucket k p v
bucket' IntPSQ p (Bucket k p v)
ipsq')
        | Bool
otherwise -> case (Maybe (p, v) -> (b, Maybe (p, v)))
-> k -> OrdPSQ k p v -> (b, OrdPSQ k p v)
forall k p v b.
(Ord k, Ord p) =>
(Maybe (p, v) -> (b, Maybe (p, v)))
-> k -> OrdPSQ k p v -> (b, OrdPSQ k p v)
OrdPSQ.alter Maybe (p, v) -> (b, Maybe (p, v))
f k
k OrdPSQ k p v
opsq of
            (b
b, OrdPSQ k p v
opsq') -> case k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
mkBucket k
bk p
bp v
bx OrdPSQ k p v
opsq' of
                (p
bp', Bucket k p v
bucket') ->
                    (b
b, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ (IntPSQ p (Bucket k p v) -> HashPSQ k p v)
-> IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall a b. (a -> b) -> a -> b
$ Int
-> p
-> Bucket k p v
-> IntPSQ p (Bucket k p v)
-> IntPSQ p (Bucket k p v)
forall p v. Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v
IntPSQ.unsafeInsertNew Int
h p
bp' Bucket k p v
bucket' IntPSQ p (Bucket k p v)
ipsq')
  where
    h :: Int
h = k -> Int
forall a. Hashable a => a -> Int
hash k
k

-- | /O(min(n,W))/ A variant of 'alter' which works on the element with the
-- minimum priority. Unlike 'alter', this variant also allows you to change the
-- key of the element.
{-# INLINABLE alterMin #-}
alterMin
    :: (Hashable k, Ord k, Ord p)
     => (Maybe (k, p, v) -> (b, Maybe (k, p, v)))
     -> HashPSQ k p v
     -> (b, HashPSQ k p v)
alterMin :: (Maybe (k, p, v) -> (b, Maybe (k, p, v)))
-> HashPSQ k p v -> (b, HashPSQ k p v)
alterMin Maybe (k, p, v) -> (b, Maybe (k, p, v))
f HashPSQ k p v
t0 =
    let (HashPSQ k p v
t, Maybe (k, p, v)
mbX) = case HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
forall k p v.
(Hashable k, Ord k, Ord p) =>
HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
minView HashPSQ k p v
t0 of
                    Maybe (k, p, v, HashPSQ k p v)
Nothing             -> (HashPSQ k p v
t0, Maybe (k, p, v)
forall a. Maybe a
Nothing)
                    Just (k
k, p
p, v
x, HashPSQ k p v
t0') -> (HashPSQ k p v
t0', (k, p, v) -> Maybe (k, p, v)
forall a. a -> Maybe a
Just (k
k, p
p, v
x))
    in case Maybe (k, p, v) -> (b, Maybe (k, p, v))
f Maybe (k, p, v)
mbX of
        (b
b, Maybe (k, p, v)
mbX') ->
            (b
b, HashPSQ k p v
-> ((k, p, v) -> HashPSQ k p v) -> Maybe (k, p, v) -> HashPSQ k p v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe HashPSQ k p v
t (\(k
k, p
p, v
x) -> k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
forall k p v.
(Ord k, Hashable k, Ord p) =>
k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
insert k
k p
p v
x HashPSQ k p v
t) Maybe (k, p, v)
mbX')


--------------------------------------------------------------------------------
-- Lists
--------------------------------------------------------------------------------

-- | /O(n*min(n,W))/ Build a queue from a list of (key, priority, value) tuples.
-- If the list contains more than one priority and value for the same key, the
-- last priority and value for the key is retained.
{-# INLINABLE fromList #-}
fromList :: (Hashable k, Ord k, Ord p) => [(k, p, v)] -> HashPSQ k p v
fromList :: [(k, p, v)] -> HashPSQ k p v
fromList = (HashPSQ k p v -> (k, p, v) -> HashPSQ k p v)
-> HashPSQ k p v -> [(k, p, v)] -> HashPSQ k p v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\HashPSQ k p v
psq (k
k, p
p, v
x) -> k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
forall k p v.
(Ord k, Hashable k, Ord p) =>
k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
insert k
k p
p v
x HashPSQ k p v
psq) HashPSQ k p v
forall k p v. HashPSQ k p v
empty

-- | /O(n)/ Convert a queue to a list of (key, priority, value) tuples. The
-- order of the list is not specified.
{-# INLINABLE toList #-}
toList :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [(k, p, v)]
toList :: HashPSQ k p v -> [(k, p, v)]
toList (HashPSQ IntPSQ p (Bucket k p v)
ipsq) =
    [ (k
k', p
p', v
x')
    | (Int
_, p
p, (B k
k v
x OrdPSQ k p v
opsq)) <- IntPSQ p (Bucket k p v) -> [(Int, p, Bucket k p v)]
forall p v. IntPSQ p v -> [(Int, p, v)]
IntPSQ.toList IntPSQ p (Bucket k p v)
ipsq
    , (k
k', p
p', v
x')         <- (k
k, p
p, v
x) (k, p, v) -> [(k, p, v)] -> [(k, p, v)]
forall a. a -> [a] -> [a]
: OrdPSQ k p v -> [(k, p, v)]
forall k p v. OrdPSQ k p v -> [(k, p, v)]
OrdPSQ.toList OrdPSQ k p v
opsq
    ]

-- | /O(n)/ Obtain the list of present keys in the queue.
{-# INLINABLE keys #-}
keys :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [k]
keys :: HashPSQ k p v -> [k]
keys HashPSQ k p v
t = [k
k | (k
k, p
_, v
_) <- HashPSQ k p v -> [(k, p, v)]
forall k p v.
(Hashable k, Ord k, Ord p) =>
HashPSQ k p v -> [(k, p, v)]
toList HashPSQ k p v
t]


--------------------------------------------------------------------------------
-- Views
--------------------------------------------------------------------------------

-- | /O(min(n,W))/ Insert a new key, priority and value into the queue. If the key
-- is already present in the queue, then the evicted priority and value can be
-- found the first element of the returned tuple.
{-# INLINABLE insertView #-}
insertView
    :: (Hashable k, Ord k, Ord p)
    => k -> p -> v -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)
insertView :: k -> p -> v -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)
insertView k
k p
p v
x HashPSQ k p v
t =
    -- TODO (jaspervdj): Can be optimized easily
    case k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v)
forall k p v.
(Hashable k, Ord k, Ord p) =>
k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v)
deleteView k
k HashPSQ k p v
t of
        Maybe (p, v, HashPSQ k p v)
Nothing          -> (Maybe (p, v)
forall a. Maybe a
Nothing,       k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
forall k p v.
(Ord k, Hashable k, Ord p) =>
k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
insert k
k p
p v
x HashPSQ k p v
t)
        Just (p
p', v
x', HashPSQ k p v
_) -> ((p, v) -> Maybe (p, v)
forall a. a -> Maybe a
Just (p
p', v
x'), k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
forall k p v.
(Ord k, Hashable k, Ord p) =>
k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
insert k
k p
p v
x HashPSQ k p v
t)

-- | /O(min(n,W))/ Delete a key and its priority and value from the queue. If
-- the key was present, the associated priority and value are returned in
-- addition to the updated queue.
{-# INLINABLE deleteView #-}
deleteView
    :: forall k p v. (Hashable k, Ord k, Ord p)
    => k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v)
deleteView :: k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v)
deleteView k
k (HashPSQ IntPSQ p (Bucket k p v)
ipsq) = case (Maybe (p, Bucket k p v)
 -> (Maybe (p, v), Maybe (p, Bucket k p v)))
-> Int
-> IntPSQ p (Bucket k p v)
-> (Maybe (p, v), IntPSQ p (Bucket k p v))
forall p v b.
Ord p =>
(Maybe (p, v) -> (b, Maybe (p, v)))
-> Int -> IntPSQ p v -> (b, IntPSQ p v)
IntPSQ.alter Maybe (p, Bucket k p v) -> (Maybe (p, v), Maybe (p, Bucket k p v))
f (k -> Int
forall a. Hashable a => a -> Int
hash k
k) IntPSQ p (Bucket k p v)
ipsq of
    (Maybe (p, v)
Nothing,     IntPSQ p (Bucket k p v)
_    ) -> Maybe (p, v, HashPSQ k p v)
forall a. Maybe a
Nothing
    (Just (p
p, v
x), IntPSQ p (Bucket k p v)
ipsq') -> (p, v, HashPSQ k p v) -> Maybe (p, v, HashPSQ k p v)
forall a. a -> Maybe a
Just (p
p, v
x, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ IntPSQ p (Bucket k p v)
ipsq')
  where
    f :: Maybe (p, Bucket k p v) -> (Maybe (p, v), Maybe (p, Bucket k p v))
    f :: Maybe (p, Bucket k p v) -> (Maybe (p, v), Maybe (p, Bucket k p v))
f Maybe (p, Bucket k p v)
Nothing       = (Maybe (p, v)
forall a. Maybe a
Nothing, Maybe (p, Bucket k p v)
forall a. Maybe a
Nothing)
    f (Just (p
p, B k
bk v
bx OrdPSQ k p v
opsq))
        | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
bk   = case OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v)
forall k p v.
(Ord k, Ord p) =>
OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v)
OrdPSQ.minView OrdPSQ k p v
opsq of
            Maybe (k, p, v, OrdPSQ k p v)
Nothing                  -> ((p, v) -> Maybe (p, v)
forall a. a -> Maybe a
Just (p
p, v
bx), Maybe (p, Bucket k p v)
forall a. Maybe a
Nothing)
            Just (k
k', p
p', v
x', OrdPSQ k p v
opsq') -> ((p, v) -> Maybe (p, v)
forall a. a -> Maybe a
Just (p
p, v
bx), (p, Bucket k p v) -> Maybe (p, Bucket k p v)
forall a. a -> Maybe a
Just (p
p', k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k' v
x' OrdPSQ k p v
opsq'))
        | Bool
otherwise = case k -> OrdPSQ k p v -> Maybe (p, v, OrdPSQ k p v)
forall k p v.
(Ord k, Ord p) =>
k -> OrdPSQ k p v -> Maybe (p, v, OrdPSQ k p v)
OrdPSQ.deleteView k
k OrdPSQ k p v
opsq of
            Maybe (p, v, OrdPSQ k p v)
Nothing              -> (Maybe (p, v)
forall a. Maybe a
Nothing,       Maybe (p, Bucket k p v)
forall a. Maybe a
Nothing)
            Just (p
p', v
x', OrdPSQ k p v
opsq') -> ((p, v) -> Maybe (p, v)
forall a. a -> Maybe a
Just (p
p', v
x'), (p, Bucket k p v) -> Maybe (p, Bucket k p v)
forall a. a -> Maybe a
Just (p
p, k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
bk v
bx OrdPSQ k p v
opsq'))

-- | /O(min(n,W))/ Retrieve the binding with the least priority, and the
-- rest of the queue stripped of that binding.
{-# INLINABLE minView #-}
minView
    :: (Hashable k, Ord k, Ord p)
    => HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
minView :: HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
minView (HashPSQ IntPSQ p (Bucket k p v)
ipsq ) =
    case (Maybe (Int, p, Bucket k p v)
 -> (Maybe (k, p, v), Maybe (Int, p, Bucket k p v)))
-> IntPSQ p (Bucket k p v)
-> (Maybe (k, p, v), IntPSQ p (Bucket k p v))
forall p v b.
Ord p =>
(Maybe (Int, p, v) -> (b, Maybe (Int, p, v)))
-> IntPSQ p v -> (b, IntPSQ p v)
IntPSQ.alterMin Maybe (Int, p, Bucket k p v)
-> (Maybe (k, p, v), Maybe (Int, p, Bucket k p v))
forall k p a b v.
(Ord k, Ord p) =>
Maybe (a, b, Bucket k p v)
-> (Maybe (k, b, v), Maybe (a, p, Bucket k p v))
f IntPSQ p (Bucket k p v)
ipsq of
        (Maybe (k, p, v)
Nothing       , IntPSQ p (Bucket k p v)
_    ) -> Maybe (k, p, v, HashPSQ k p v)
forall a. Maybe a
Nothing
        (Just (k
k, p
p, v
x), IntPSQ p (Bucket k p v)
ipsq') -> (k, p, v, HashPSQ k p v) -> Maybe (k, p, v, HashPSQ k p v)
forall a. a -> Maybe a
Just (k
k, p
p, v
x, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ IntPSQ p (Bucket k p v)
ipsq')
  where
    f :: Maybe (a, b, Bucket k p v)
-> (Maybe (k, b, v), Maybe (a, p, Bucket k p v))
f Maybe (a, b, Bucket k p v)
Nothing                 = (Maybe (k, b, v)
forall a. Maybe a
Nothing, Maybe (a, p, Bucket k p v)
forall a. Maybe a
Nothing)
    f (Just (a
h, b
p, B k
k v
x OrdPSQ k p v
os)) = case OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v)
forall k p v.
(Ord k, Ord p) =>
OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v)
OrdPSQ.minView OrdPSQ k p v
os of
        Maybe (k, p, v, OrdPSQ k p v)
Nothing                ->
            ((k, b, v) -> Maybe (k, b, v)
forall a. a -> Maybe a
Just (k
k, b
p, v
x), Maybe (a, p, Bucket k p v)
forall a. Maybe a
Nothing)
        Just (k
k', p
p', v
x', OrdPSQ k p v
os') ->
            ((k, b, v) -> Maybe (k, b, v)
forall a. a -> Maybe a
Just (k
k, b
p, v
x), (a, p, Bucket k p v) -> Maybe (a, p, Bucket k p v)
forall a. a -> Maybe a
Just (a
h, p
p', k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k' v
x' OrdPSQ k p v
os'))

-- | Return a list of elements ordered by key whose priorities are at most @pt@,
-- and the rest of the queue stripped of these elements.  The returned list of
-- elements can be in any order: no guarantees there.
{-# INLINABLE atMostView #-}
atMostView
    :: (Hashable k, Ord k, Ord p)
    => p -> HashPSQ k p v -> ([(k, p, v)], HashPSQ k p v)
atMostView :: p -> HashPSQ k p v -> ([(k, p, v)], HashPSQ k p v)
atMostView p
pt (HashPSQ IntPSQ p (Bucket k p v)
t0) =
    ([(k, p, v)]
returns, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ IntPSQ p (Bucket k p v)
t2)
  where
    -- First we use 'IntPSQ.atMostView' to get a collection of buckets that have
    -- /AT LEAST/ one element with a low priority.  Buckets will usually only
    -- contain a single element.
    ([(Int, p, Bucket k p v)]
buckets, IntPSQ p (Bucket k p v)
t1) = p
-> IntPSQ p (Bucket k p v)
-> ([(Int, p, Bucket k p v)], IntPSQ p (Bucket k p v))
forall p v. Ord p => p -> IntPSQ p v -> ([(Int, p, v)], IntPSQ p v)
IntPSQ.atMostView p
pt IntPSQ p (Bucket k p v)
t0

    -- We now need to run through the buckets.  This will give us a list of
    -- elements to return and a bunch of buckets to re-insert.
    ([(k, p, v)]
returns, [(p, Bucket k p v)]
reinserts) = [(k, p, v)]
-> [(p, Bucket k p v)]
-> [(Int, p, Bucket k p v)]
-> ([(k, p, v)], [(p, Bucket k p v)])
forall k v a.
Ord k =>
[(k, p, v)]
-> [(p, Bucket k p v)]
-> [(a, p, Bucket k p v)]
-> ([(k, p, v)], [(p, Bucket k p v)])
go [] [] [(Int, p, Bucket k p v)]
buckets
      where
        -- We use two accumulators, for returns and re-inserts.
        go :: [(k, p, v)]
-> [(p, Bucket k p v)]
-> [(a, p, Bucket k p v)]
-> ([(k, p, v)], [(p, Bucket k p v)])
go [(k, p, v)]
rets [(p, Bucket k p v)]
reins []                        = ([(k, p, v)]
rets, [(p, Bucket k p v)]
reins)
        go [(k, p, v)]
rets [(p, Bucket k p v)]
reins ((a
_, p
p, B k
k v
v OrdPSQ k p v
opsq) : [(a, p, Bucket k p v)]
bs) =
            -- Note that 'elems' should be very small, ideally a null list.
            let ([(k, p, v)]
elems, OrdPSQ k p v
opsq') = p -> OrdPSQ k p v -> ([(k, p, v)], OrdPSQ k p v)
forall k p v.
(Ord k, Ord p) =>
p -> OrdPSQ k p v -> ([(k, p, v)], OrdPSQ k p v)
OrdPSQ.atMostView p
pt OrdPSQ k p v
opsq
                rets' :: [(k, p, v)]
rets'          = (k
k, p
p, v
v) (k, p, v) -> [(k, p, v)] -> [(k, p, v)]
forall a. a -> [a] -> [a]
: [(k, p, v)]
elems [(k, p, v)] -> [(k, p, v)] -> [(k, p, v)]
forall a. [a] -> [a] -> [a]
++ [(k, p, v)]
rets
                reins' :: [(p, Bucket k p v)]
reins'         = case OrdPSQ k p v -> Maybe (p, Bucket k p v)
forall k p v.
(Ord k, Ord p) =>
OrdPSQ k p v -> Maybe (p, Bucket k p v)
toBucket OrdPSQ k p v
opsq' of
                    Maybe (p, Bucket k p v)
Nothing      -> [(p, Bucket k p v)]
reins
                    Just (p
p', Bucket k p v
b) -> ((p
p', Bucket k p v
b) (p, Bucket k p v) -> [(p, Bucket k p v)] -> [(p, Bucket k p v)]
forall a. a -> [a] -> [a]
: [(p, Bucket k p v)]
reins)
            in  [(k, p, v)]
-> [(p, Bucket k p v)]
-> [(a, p, Bucket k p v)]
-> ([(k, p, v)], [(p, Bucket k p v)])
go [(k, p, v)]
rets' [(p, Bucket k p v)]
reins' [(a, p, Bucket k p v)]
bs

    -- Now we can do the re-insertion pass.
    t2 :: IntPSQ p (Bucket k p v)
t2 = (IntPSQ p (Bucket k p v)
 -> (p, Bucket k p v) -> IntPSQ p (Bucket k p v))
-> IntPSQ p (Bucket k p v)
-> [(p, Bucket k p v)]
-> IntPSQ p (Bucket k p v)
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl'
        (\IntPSQ p (Bucket k p v)
t (p
p, b :: Bucket k p v
b@(B k
k v
_ OrdPSQ k p v
_)) -> Int
-> p
-> Bucket k p v
-> IntPSQ p (Bucket k p v)
-> IntPSQ p (Bucket k p v)
forall p v. Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v
IntPSQ.unsafeInsertNew (k -> Int
forall a. Hashable a => a -> Int
hash k
k) p
p Bucket k p v
b IntPSQ p (Bucket k p v)
t)
        IntPSQ p (Bucket k p v)
t1
        [(p, Bucket k p v)]
reinserts


--------------------------------------------------------------------------------
-- Traversals
--------------------------------------------------------------------------------

-- | /O(n)/ Modify every value in the queue.
{-# INLINABLE map #-}
map :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w
map :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w
map k -> p -> v -> w
f (HashPSQ IntPSQ p (Bucket k p v)
ipsq) = IntPSQ p (Bucket k p w) -> HashPSQ k p w
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ ((Int -> p -> Bucket k p v -> Bucket k p w)
-> IntPSQ p (Bucket k p v) -> IntPSQ p (Bucket k p w)
forall p v w. (Int -> p -> v -> w) -> IntPSQ p v -> IntPSQ p w
IntPSQ.map (\Int
_ p
p Bucket k p v
v -> p -> Bucket k p v -> Bucket k p w
mapBucket p
p Bucket k p v
v) IntPSQ p (Bucket k p v)
ipsq)
  where
    mapBucket :: p -> Bucket k p v -> Bucket k p w
mapBucket p
p (B k
k v
v OrdPSQ k p v
opsq) = k -> w -> OrdPSQ k p w -> Bucket k p w
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k (k -> p -> v -> w
f k
k p
p v
v) ((k -> p -> v -> w) -> OrdPSQ k p v -> OrdPSQ k p w
forall k p v w. (k -> p -> v -> w) -> OrdPSQ k p v -> OrdPSQ k p w
OrdPSQ.map k -> p -> v -> w
f OrdPSQ k p v
opsq)

-- | /O(n)/ Maps a function over the values and priorities of the queue.
-- The function @f@ must be monotonic with respect to the priorities. I.e. if
-- @x < y@, then @fst (f k x v) < fst (f k y v)@.
-- /The precondition is not checked./ If @f@ is not monotonic, then the result
-- will be invalid.
{-# INLINABLE unsafeMapMonotonic #-}
unsafeMapMonotonic
    :: (k -> p -> v -> (q, w))
    -> HashPSQ k p v
    -> HashPSQ k q w
unsafeMapMonotonic :: (k -> p -> v -> (q, w)) -> HashPSQ k p v -> HashPSQ k q w
unsafeMapMonotonic k -> p -> v -> (q, w)
f (HashPSQ IntPSQ p (Bucket k p v)
ipsq) =
  IntPSQ q (Bucket k q w) -> HashPSQ k q w
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ ((Int -> p -> Bucket k p v -> (q, Bucket k q w))
-> IntPSQ p (Bucket k p v) -> IntPSQ q (Bucket k q w)
forall p v q w.
(Int -> p -> v -> (q, w)) -> IntPSQ p v -> IntPSQ q w
IntPSQ.unsafeMapMonotonic (\Int
_ p
p Bucket k p v
v -> p -> Bucket k p v -> (q, Bucket k q w)
mapBucket p
p Bucket k p v
v) IntPSQ p (Bucket k p v)
ipsq)
  where
    mapBucket :: p -> Bucket k p v -> (q, Bucket k q w)
mapBucket p
p (B k
k v
v OrdPSQ k p v
opsq) =
        let (q
p', w
v') = k -> p -> v -> (q, w)
f k
k p
p v
v
        in  (q
p', k -> w -> OrdPSQ k q w -> Bucket k q w
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k w
v' ((k -> p -> v -> (q, w)) -> OrdPSQ k p v -> OrdPSQ k q w
forall k p q v w.
(k -> p -> v -> (q, w)) -> OrdPSQ k p v -> OrdPSQ k q w
OrdPSQ.unsafeMapMonotonic k -> p -> v -> (q, w)
f OrdPSQ k p v
opsq))

-- | /O(n)/ Strict fold over every key, priority and value in the queue. The order
-- in which the fold is performed is not specified.
{-# INLINABLE fold' #-}
fold' :: (k -> p -> v -> a -> a) -> a -> HashPSQ k p v -> a
fold' :: (k -> p -> v -> a -> a) -> a -> HashPSQ k p v -> a
fold' k -> p -> v -> a -> a
f a
acc0 (HashPSQ IntPSQ p (Bucket k p v)
ipsq) = (Int -> p -> Bucket k p v -> a -> a)
-> a -> IntPSQ p (Bucket k p v) -> a
forall p v a. (Int -> p -> v -> a -> a) -> a -> IntPSQ p v -> a
IntPSQ.fold' Int -> p -> Bucket k p v -> a -> a
forall p. p -> p -> Bucket k p v -> a -> a
goBucket a
acc0 IntPSQ p (Bucket k p v)
ipsq
  where
    goBucket :: p -> p -> Bucket k p v -> a -> a
goBucket p
_ p
p (B k
k v
v OrdPSQ k p v
opsq) a
acc =
        let !acc1 :: a
acc1 = k -> p -> v -> a -> a
f k
k p
p v
v a
acc
            !acc2 :: a
acc2 = (k -> p -> v -> a -> a) -> a -> OrdPSQ k p v -> a
forall k p v a. (k -> p -> v -> a -> a) -> a -> OrdPSQ k p v -> a
OrdPSQ.fold' k -> p -> v -> a -> a
f a
acc1 OrdPSQ k p v
opsq
        in a
acc2


--------------------------------------------------------------------------------
-- Unsafe operations
--------------------------------------------------------------------------------

{-# INLINABLE unsafeLookupIncreasePriority #-}
unsafeLookupIncreasePriority
    :: (Hashable k, Ord k, Ord p)
    => k -> p -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)
unsafeLookupIncreasePriority :: k -> p -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)
unsafeLookupIncreasePriority k
k p
p (HashPSQ IntPSQ p (Bucket k p v)
ipsq) =
    (Maybe (p, v)
mbPV, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ IntPSQ p (Bucket k p v)
ipsq')
  where
    (!Maybe (p, v)
mbPV, !IntPSQ p (Bucket k p v)
ipsq') = (p -> Bucket k p v -> (Maybe (p, v), p, Bucket k p v))
-> Int
-> IntPSQ p (Bucket k p v)
-> (Maybe (p, v), IntPSQ p (Bucket k p v))
forall p v b.
Ord p =>
(p -> v -> (Maybe b, p, v))
-> Int -> IntPSQ p v -> (Maybe b, IntPSQ p v)
IntPSQ.unsafeLookupIncreasePriority
        (\p
bp b :: Bucket k p v
b@(B k
bk v
bx OrdPSQ k p v
opsq) ->
            if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
bk
                then let (p
bp', Bucket k p v
b') = k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
mkBucket k
k p
p v
bx OrdPSQ k p v
opsq
                     in ((p, v) -> Maybe (p, v)
forall a. a -> Maybe a
Just (p
bp, v
bx), p
bp', Bucket k p v
b')
                -- TODO (jaspervdj): Still a lookup-insert here: 3 traversals?
                else case k -> OrdPSQ k p v -> Maybe (p, v)
forall k p v. Ord k => k -> OrdPSQ k p v -> Maybe (p, v)
OrdPSQ.lookup k
k OrdPSQ k p v
opsq of
                        Maybe (p, v)
Nothing      -> (Maybe (p, v)
forall a. Maybe a
Nothing,     p
bp, Bucket k p v
b)
                        Just (p
p', v
x) ->
                            let b' :: Bucket k p v
b' = k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
bk v
bx (k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
OrdPSQ.insert k
k p
p v
x OrdPSQ k p v
opsq)
                            in ((p, v) -> Maybe (p, v)
forall a. a -> Maybe a
Just (p
p', v
x), p
bp, Bucket k p v
b'))
        (k -> Int
forall a. Hashable a => a -> Int
hash k
k)
        IntPSQ p (Bucket k p v)
ipsq

{-# INLINABLE unsafeInsertIncreasePriority #-}
unsafeInsertIncreasePriority
    :: (Hashable k, Ord k, Ord p)
    => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
unsafeInsertIncreasePriority :: k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
unsafeInsertIncreasePriority k
k p
p v
x (HashPSQ IntPSQ p (Bucket k p v)
ipsq) = IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ (IntPSQ p (Bucket k p v) -> HashPSQ k p v)
-> IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall a b. (a -> b) -> a -> b
$
    (p -> Bucket k p v -> p -> Bucket k p v -> (p, Bucket k p v))
-> Int
-> p
-> Bucket k p v
-> IntPSQ p (Bucket k p v)
-> IntPSQ p (Bucket k p v)
forall p v.
Ord p =>
(p -> v -> p -> v -> (p, v))
-> Int -> p -> v -> IntPSQ p v -> IntPSQ p v
IntPSQ.unsafeInsertWithIncreasePriority
        (\p
_ Bucket k p v
_ p
bp (B k
bk v
bx OrdPSQ k p v
opsq) ->
            if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
bk
                then k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
mkBucket k
k p
p v
x OrdPSQ k p v
opsq
                else (p
bp, k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
bk v
bx (k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
OrdPSQ.insert k
k p
p v
x OrdPSQ k p v
opsq)))
        (k -> Int
forall a. Hashable a => a -> Int
hash k
k)
        p
p
        (k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k v
x OrdPSQ k p v
forall k p v. OrdPSQ k p v
OrdPSQ.empty)
        IntPSQ p (Bucket k p v)
ipsq

{-# INLINABLE unsafeInsertIncreasePriorityView #-}
unsafeInsertIncreasePriorityView
    :: (Hashable k, Ord k, Ord p)
    => k -> p -> v -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)
unsafeInsertIncreasePriorityView :: k -> p -> v -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)
unsafeInsertIncreasePriorityView k
k p
p v
x (HashPSQ IntPSQ p (Bucket k p v)
ipsq) =
    (Maybe (p, v)
mbEvicted, IntPSQ p (Bucket k p v) -> HashPSQ k p v
forall k p v. IntPSQ p (Bucket k p v) -> HashPSQ k p v
HashPSQ IntPSQ p (Bucket k p v)
ipsq')
  where
    (Maybe (p, Bucket k p v)
mbBucket, IntPSQ p (Bucket k p v)
ipsq') = (p -> Bucket k p v -> p -> Bucket k p v -> (p, Bucket k p v))
-> Int
-> p
-> Bucket k p v
-> IntPSQ p (Bucket k p v)
-> (Maybe (p, Bucket k p v), IntPSQ p (Bucket k p v))
forall p v.
Ord p =>
(p -> v -> p -> v -> (p, v))
-> Int -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v)
IntPSQ.unsafeInsertWithIncreasePriorityView
        (\p
_ Bucket k p v
_ p
bp (B k
bk v
bx OrdPSQ k p v
opsq) ->
            if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
bk
                then k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> (p, Bucket k p v)
mkBucket k
k p
p v
x OrdPSQ k p v
opsq
                else (p
bp, k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
bk v
bx (k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
OrdPSQ.insert k
k p
p v
x OrdPSQ k p v
opsq)))
        (k -> Int
forall a. Hashable a => a -> Int
hash k
k)
        p
p
        (k -> v -> OrdPSQ k p v -> Bucket k p v
forall k p v. k -> v -> OrdPSQ k p v -> Bucket k p v
B k
k v
x OrdPSQ k p v
forall k p v. OrdPSQ k p v
OrdPSQ.empty)
        IntPSQ p (Bucket k p v)
ipsq

    mbEvicted :: Maybe (p, v)
mbEvicted = case Maybe (p, Bucket k p v)
mbBucket of
        Maybe (p, Bucket k p v)
Nothing         -> Maybe (p, v)
forall a. Maybe a
Nothing
        Just (p
bp, B k
bk v
bv OrdPSQ k p v
opsq)
            | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
bk   -> (p, v) -> Maybe (p, v)
forall a. a -> Maybe a
Just (p
bp, v
bv)
            | Bool
otherwise -> k -> OrdPSQ k p v -> Maybe (p, v)
forall k p v. Ord k => k -> OrdPSQ k p v -> Maybe (p, v)
OrdPSQ.lookup k
k OrdPSQ k p v
opsq


--------------------------------------------------------------------------------
-- Validity check
--------------------------------------------------------------------------------

-- | /O(n^2)/ Internal function to check if the 'HashPSQ' is valid, i.e. if all
-- invariants hold. This should always be the case.
valid :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Bool
valid :: HashPSQ k p v -> Bool
valid t :: HashPSQ k p v
t@(HashPSQ IntPSQ p (Bucket k p v)
ipsq) =
    Bool -> Bool
not (HashPSQ k p v -> Bool
forall k p v. (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Bool
hasDuplicateKeys HashPSQ k p v
t) Bool -> Bool -> Bool
&&
    [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [Int -> p -> Bucket k p v -> Bool
forall k p v.
(Hashable k, Ord k, Ord p) =>
Int -> p -> Bucket k p v -> Bool
validBucket Int
k p
p Bucket k p v
bucket | (Int
k, p
p, Bucket k p v
bucket) <- IntPSQ p (Bucket k p v) -> [(Int, p, Bucket k p v)]
forall p v. IntPSQ p v -> [(Int, p, v)]
IntPSQ.toList IntPSQ p (Bucket k p v)
ipsq]

hasDuplicateKeys :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Bool
hasDuplicateKeys :: HashPSQ k p v -> Bool
hasDuplicateKeys = (Int -> Bool) -> [Int] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
1) ([Int] -> Bool)
-> (HashPSQ k p v -> [Int]) -> HashPSQ k p v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([k] -> Int) -> [[k]] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
List.map [k] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([[k]] -> [Int])
-> (HashPSQ k p v -> [[k]]) -> HashPSQ k p v -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> [[k]]
forall a. Eq a => [a] -> [[a]]
List.group ([k] -> [[k]]) -> (HashPSQ k p v -> [k]) -> HashPSQ k p v -> [[k]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> [k]
forall a. Ord a => [a] -> [a]
List.sort ([k] -> [k]) -> (HashPSQ k p v -> [k]) -> HashPSQ k p v -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashPSQ k p v -> [k]
forall k p v. (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [k]
keys

validBucket :: (Hashable k, Ord k, Ord p) => Int -> p -> Bucket k p v -> Bool
validBucket :: Int -> p -> Bucket k p v -> Bool
validBucket Int
h p
p (B k
k v
_ OrdPSQ k p v
opsq) =
    OrdPSQ k p v -> Bool
forall k p v. (Ord k, Ord p) => OrdPSQ k p v -> Bool
OrdPSQ.valid OrdPSQ k p v
opsq Bool -> Bool -> Bool
&&
    -- Check that the first element of the bucket has lower priority than all
    -- the other elements.
    [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [(p
p, k
k) (p, k) -> (p, k) -> Bool
forall a. Ord a => a -> a -> Bool
< (p
p', k
k') Bool -> Bool -> Bool
&& k -> Int
forall a. Hashable a => a -> Int
hash k
k' Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
h | (k
k', p
p', v
_) <- OrdPSQ k p v -> [(k, p, v)]
forall k p v. OrdPSQ k p v -> [(k, p, v)]
OrdPSQ.toList OrdPSQ k p v
opsq]