{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Data.PQueue.Prio.Max
-- Copyright   :  (c) Louis Wasserman 2010
-- License     :  BSD-style
-- Maintainer  :  libraries@haskell.org
-- Stability   :  experimental
-- Portability :  portable
-----------------------------------------------------------------------------
module Data.PQueue.Prio.Max.Internals (
  MaxPQueue (..),
  -- * Construction
  empty,
  singleton,
  insert,
  insertBehind,
  union,
  unions,
  -- * Query
  null,
  size,
  -- ** Maximum view
  findMax,
  getMax,
  deleteMax,
  deleteFindMax,
  adjustMax,
  adjustMaxA,
  adjustMaxWithKey,
  adjustMaxWithKeyA,
  updateMax,
  updateMaxA,
  updateMaxWithKey,
  updateMaxWithKeyA,
  maxView,
  maxViewWithKey,
  -- * Traversal
  -- ** Map
  map,
  mapWithKey,
  mapKeys,
  mapKeysMonotonic,
  -- ** Fold
  foldrWithKey,
  foldlWithKey,
  -- ** Traverse
  traverseWithKey,
  mapMWithKey,
  -- * Subsets
  -- ** Indexed
  take,
  drop,
  splitAt,
  -- ** Predicates
  takeWhile,
  takeWhileWithKey,
  dropWhile,
  dropWhileWithKey,
  span,
  spanWithKey,
  break,
  breakWithKey,
  -- *** Filter
  filter,
  filterWithKey,
  partition,
  partitionWithKey,
  mapMaybe,
  mapMaybeWithKey,
  mapEither,
  mapEitherWithKey,
  -- * List operations
  -- ** Conversion from lists
  fromList,
  fromAscList,
  fromDescList,
  -- ** Conversion to lists
  keys,
  elems,
  assocs,
  toAscList,
  toDescList,
  toList,
  -- * Unordered operations
  foldrU,
  foldMapWithKeyU,
  foldrWithKeyU,
  foldlU,
  foldlU',
  foldlWithKeyU,
  foldlWithKeyU',
  traverseU,
  traverseWithKeyU,
  keysU,
  elemsU,
  assocsU,
  toListU,
  -- * Helper methods
  seqSpine
  )
  where

import Data.Maybe (fromMaybe)
import Data.PQueue.Internals.Down
import Data.PQueue.Prio.Internals (MinPQueue)
import qualified Data.PQueue.Prio.Internals as PrioInternals
import Control.DeepSeq (NFData(rnf))

#if MIN_VERSION_base(4,9,0)
import Data.Semigroup (Semigroup(..), stimesMonoid)
#endif

import Prelude hiding (map, filter, break, span, takeWhile, dropWhile, splitAt, take, drop, (!!), null)
import qualified Data.Foldable as F

import qualified Data.PQueue.Prio.Min as Q

#ifdef __GLASGOW_HASKELL__
import Data.Data (Data)
import Text.Read (Lexeme(Ident), lexP, parens, prec,
  readPrec, readListPrec, readListPrecDefault)
#endif

import Data.Functor.WithIndex
import Data.Foldable.WithIndex
import Data.Traversable.WithIndex

#ifndef __GLASGOW_HASKELL__
build :: ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
build f = f (:) []
#endif

-- | A priority queue where values of type @a@ are annotated with keys of type @k@.
-- The queue supports extracting the element with maximum key.
newtype MaxPQueue k a = MaxPQ (MinPQueue (Down k) a)
# if __GLASGOW_HASKELL__
  deriving (MaxPQueue k a -> MaxPQueue k a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k a. (Ord k, Eq a) => MaxPQueue k a -> MaxPQueue k a -> Bool
/= :: MaxPQueue k a -> MaxPQueue k a -> Bool
$c/= :: forall k a. (Ord k, Eq a) => MaxPQueue k a -> MaxPQueue k a -> Bool
== :: MaxPQueue k a -> MaxPQueue k a -> Bool
$c== :: forall k a. (Ord k, Eq a) => MaxPQueue k a -> MaxPQueue k a -> Bool
Eq, MaxPQueue k a -> MaxPQueue k a -> Bool
MaxPQueue k a -> MaxPQueue k a -> Ordering
MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k 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 {k} {a}. (Ord k, Ord a) => Eq (MaxPQueue k a)
forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> Bool
forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> Ordering
forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
min :: MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
$cmin :: forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
max :: MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
$cmax :: forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
>= :: MaxPQueue k a -> MaxPQueue k a -> Bool
$c>= :: forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> Bool
> :: MaxPQueue k a -> MaxPQueue k a -> Bool
$c> :: forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> Bool
<= :: MaxPQueue k a -> MaxPQueue k a -> Bool
$c<= :: forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> Bool
< :: MaxPQueue k a -> MaxPQueue k a -> Bool
$c< :: forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> Bool
compare :: MaxPQueue k a -> MaxPQueue k a -> Ordering
$ccompare :: forall k a.
(Ord k, Ord a) =>
MaxPQueue k a -> MaxPQueue k a -> Ordering
Ord, MaxPQueue k a -> DataType
MaxPQueue k a -> Constr
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall {k} {a}. (Data k, Data a, Ord k) => Typeable (MaxPQueue k a)
forall k a. (Data k, Data a, Ord k) => MaxPQueue k a -> DataType
forall k a. (Data k, Data a, Ord k) => MaxPQueue k a -> Constr
forall k a.
(Data k, Data a, Ord k) =>
(forall b. Data b => b -> b) -> MaxPQueue k a -> MaxPQueue k a
forall k a u.
(Data k, Data a, Ord k) =>
Int -> (forall d. Data d => d -> u) -> MaxPQueue k a -> u
forall k a u.
(Data k, Data a, Ord k) =>
(forall d. Data d => d -> u) -> MaxPQueue k a -> [u]
forall k a r r'.
(Data k, Data a, Ord k) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> MaxPQueue k a -> r
forall k a r r'.
(Data k, Data a, Ord k) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> MaxPQueue k a -> r
forall k a (m :: * -> *).
(Data k, Data a, Ord k, Monad m) =>
(forall d. Data d => d -> m d)
-> MaxPQueue k a -> m (MaxPQueue k a)
forall k a (m :: * -> *).
(Data k, Data a, Ord k, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> MaxPQueue k a -> m (MaxPQueue k a)
forall k a (c :: * -> *).
(Data k, Data a, Ord k) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MaxPQueue k a)
forall k a (c :: * -> *).
(Data k, Data a, Ord k) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxPQueue k a -> c (MaxPQueue k a)
forall k a (t :: * -> *) (c :: * -> *).
(Data k, Data a, Ord k, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (MaxPQueue k a))
forall k a (t :: * -> * -> *) (c :: * -> *).
(Data k, Data a, Ord k, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (MaxPQueue k a))
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MaxPQueue k a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxPQueue k a -> c (MaxPQueue k a)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (MaxPQueue k a))
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> MaxPQueue k a -> m (MaxPQueue k a)
$cgmapMo :: forall k a (m :: * -> *).
(Data k, Data a, Ord k, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> MaxPQueue k a -> m (MaxPQueue k a)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> MaxPQueue k a -> m (MaxPQueue k a)
$cgmapMp :: forall k a (m :: * -> *).
(Data k, Data a, Ord k, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> MaxPQueue k a -> m (MaxPQueue k a)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> MaxPQueue k a -> m (MaxPQueue k a)
$cgmapM :: forall k a (m :: * -> *).
(Data k, Data a, Ord k, Monad m) =>
(forall d. Data d => d -> m d)
-> MaxPQueue k a -> m (MaxPQueue k a)
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> MaxPQueue k a -> u
$cgmapQi :: forall k a u.
(Data k, Data a, Ord k) =>
Int -> (forall d. Data d => d -> u) -> MaxPQueue k a -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> MaxPQueue k a -> [u]
$cgmapQ :: forall k a u.
(Data k, Data a, Ord k) =>
(forall d. Data d => d -> u) -> MaxPQueue k a -> [u]
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> MaxPQueue k a -> r
$cgmapQr :: forall k a r r'.
(Data k, Data a, Ord k) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> MaxPQueue k a -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> MaxPQueue k a -> r
$cgmapQl :: forall k a r r'.
(Data k, Data a, Ord k) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> MaxPQueue k a -> r
gmapT :: (forall b. Data b => b -> b) -> MaxPQueue k a -> MaxPQueue k a
$cgmapT :: forall k a.
(Data k, Data a, Ord k) =>
(forall b. Data b => b -> b) -> MaxPQueue k a -> MaxPQueue k a
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (MaxPQueue k a))
$cdataCast2 :: forall k a (t :: * -> * -> *) (c :: * -> *).
(Data k, Data a, Ord k, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (MaxPQueue k a))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (MaxPQueue k a))
$cdataCast1 :: forall k a (t :: * -> *) (c :: * -> *).
(Data k, Data a, Ord k, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (MaxPQueue k a))
dataTypeOf :: MaxPQueue k a -> DataType
$cdataTypeOf :: forall k a. (Data k, Data a, Ord k) => MaxPQueue k a -> DataType
toConstr :: MaxPQueue k a -> Constr
$ctoConstr :: forall k a. (Data k, Data a, Ord k) => MaxPQueue k a -> Constr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MaxPQueue k a)
$cgunfold :: forall k a (c :: * -> *).
(Data k, Data a, Ord k) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MaxPQueue k a)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxPQueue k a -> c (MaxPQueue k a)
$cgfoldl :: forall k a (c :: * -> *).
(Data k, Data a, Ord k) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxPQueue k a -> c (MaxPQueue k a)
Data)
# else
  deriving (Eq, Ord)
# endif

instance (NFData k, NFData a) => NFData (MaxPQueue k a) where
  rnf :: MaxPQueue k a -> ()
rnf (MaxPQ MinPQueue (Down k) a
q) = forall a. NFData a => a -> ()
rnf MinPQueue (Down k) a
q

first' :: (a -> b) -> (a, c) -> (b, c)
first' :: forall a b c. (a -> b) -> (a, c) -> (b, c)
first' a -> b
f (a
a, c
c) = (a -> b
f a
a, c
c)

#if MIN_VERSION_base(4,9,0)
instance Ord k => Semigroup (MaxPQueue k a) where
  <> :: MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
(<>) = forall k a.
Ord k =>
MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
union
  stimes :: forall b. Integral b => b -> MaxPQueue k a -> MaxPQueue k a
stimes = forall b a. (Integral b, Monoid a) => b -> a -> a
stimesMonoid
  {-# INLINABLE stimes #-}
#endif

instance Ord k => Monoid (MaxPQueue k a) where
  mempty :: MaxPQueue k a
mempty = forall k a. MaxPQueue k a
empty
#if !MIN_VERSION_base(4,11,0)
  mappend = union
#endif
  mconcat :: [MaxPQueue k a] -> MaxPQueue k a
mconcat = forall k a. Ord k => [MaxPQueue k a] -> MaxPQueue k a
unions

instance (Ord k, Show k, Show a) => Show (MaxPQueue k a) where
  showsPrec :: Int -> MaxPQueue k a -> ShowS
showsPrec Int
p MaxPQueue k a
xs = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10) forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"fromDescList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => a -> ShowS
shows (forall k a. Ord k => MaxPQueue k a -> [(k, a)]
toDescList MaxPQueue k a
xs)

instance (Read k, Read a) => Read (MaxPQueue k a) where
#ifdef __GLASGOW_HASKELL__
  readPrec :: ReadPrec (MaxPQueue k a)
readPrec = forall a. ReadPrec a -> ReadPrec a
parens forall a b. (a -> b) -> a -> b
$ forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 forall a b. (a -> b) -> a -> b
$ do
    Ident String
"fromDescList" <- ReadPrec Lexeme
lexP
    [(k, a)]
xs <- forall a. Read a => ReadPrec a
readPrec
    forall (m :: * -> *) a. Monad m => a -> m a
return (forall k a. [(k, a)] -> MaxPQueue k a
fromDescList [(k, a)]
xs)

  readListPrec :: ReadPrec [MaxPQueue k a]
readListPrec = forall a. Read a => ReadPrec [a]
readListPrecDefault
#else
  readsPrec p = readParen (p > 10) $ \r -> do
    ("fromDescList",s) <- lex r
    (xs,t) <- reads s
    return (fromDescList xs,t)
#endif

instance Functor (MaxPQueue k) where
  fmap :: forall a b. (a -> b) -> MaxPQueue k a -> MaxPQueue k b
fmap a -> b
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f MinPQueue (Down k) a
q)

instance FunctorWithIndex k (MaxPQueue k) where
  imap :: forall a b. (k -> a -> b) -> MaxPQueue k a -> MaxPQueue k b
imap = forall k a b. (k -> a -> b) -> MaxPQueue k a -> MaxPQueue k b
mapWithKey

instance Ord k => Foldable (MaxPQueue k) where
  foldr :: forall a b. (a -> b -> b) -> b -> MaxPQueue k a -> b
foldr a -> b -> b
f b
z (MaxPQ MinPQueue (Down k) a
q) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z MinPQueue (Down k) a
q
  foldl :: forall b a. (b -> a -> b) -> b -> MaxPQueue k a -> b
foldl b -> a -> b
f b
z (MaxPQ MinPQueue (Down k) a
q) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
f b
z MinPQueue (Down k) a
q
  length :: forall a. MaxPQueue k a -> Int
length = forall k a. MaxPQueue k a -> Int
size
  null :: forall a. MaxPQueue k a -> Bool
null = forall k a. MaxPQueue k a -> Bool
null

instance Ord k => FoldableWithIndex k (MaxPQueue k) where
  ifoldr :: forall a b. (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
ifoldr   = forall k a b.
Ord k =>
(k -> a -> b -> b) -> b -> MaxPQueue k a -> b
foldrWithKey
  ifoldl :: forall b a. (k -> b -> a -> b) -> b -> MaxPQueue k a -> b
ifoldl k -> b -> a -> b
f = forall k b a.
Ord k =>
(b -> k -> a -> b) -> b -> MaxPQueue k a -> b
foldlWithKey (forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> b -> a -> b
f)

-- | Traverses in descending order. 'mapM' is strictly accumulating like
-- 'mapMWithKey'.
instance Ord k => Traversable (MaxPQueue k) where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
traverse a -> f b
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f MinPQueue (Down k) a
q
  mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> MaxPQueue k a -> m (MaxPQueue k b)
mapM = forall k (m :: * -> *) a b.
(Ord k, Monad m) =>
(k -> a -> m b) -> MaxPQueue k a -> m (MaxPQueue k b)
mapMWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const
  sequence :: forall (m :: * -> *) a.
Monad m =>
MaxPQueue k (m a) -> m (MaxPQueue k a)
sequence = forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM forall a. a -> a
id

instance Ord k => TraversableWithIndex k (MaxPQueue k) where
  itraverse :: forall (f :: * -> *) a b.
Applicative f =>
(k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
itraverse = forall k (f :: * -> *) a b.
(Ord k, Applicative f) =>
(k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
traverseWithKey

-- | \(O(1)\). Returns the empty priority queue.
empty :: MaxPQueue k a
empty :: forall k a. MaxPQueue k a
empty = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ forall k a. MinPQueue k a
Q.empty

-- | \(O(1)\). Constructs a singleton priority queue.
singleton :: k -> a -> MaxPQueue k a
singleton :: forall k a. k -> a -> MaxPQueue k a
singleton k
k a
a = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a. k -> a -> MinPQueue k a
Q.singleton (forall a. a -> Down a
Down k
k) a
a)

-- | Amortized \(O(1)\), worst-case \(O(\log n)\). Inserts
-- an element with the specified key into the queue.
insert :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
insert :: forall k a. Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
insert k
k a
a (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
Q.insert (forall a. a -> Down a
Down k
k) a
a MinPQueue (Down k) a
q)

-- | \(O(n)\) (an earlier implementation had \(O(1)\) but was buggy).
-- Insert an element with the specified key into the priority queue,
-- putting it behind elements whose key compares equal to the
-- inserted one.
insertBehind :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
insertBehind :: forall k a. Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
insertBehind k
k a
a (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
Q.insertBehind (forall a. a -> Down a
Down k
k) a
a MinPQueue (Down k) a
q)

-- | Amortized \(O(\log \min(n_1,n_2))\), worst-case \(O(\log \max(n_1,n_2))\). Returns the union
-- of the two specified queues.
union :: Ord k => MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
MaxPQ MinPQueue (Down k) a
q1 union :: forall k a.
Ord k =>
MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
`union` MaxPQ MinPQueue (Down k) a
q2 = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (MinPQueue (Down k) a
q1 forall k a.
Ord k =>
MinPQueue k a -> MinPQueue k a -> MinPQueue k a
`Q.union` MinPQueue (Down k) a
q2)

-- | The union of a list of queues: (@'unions' == 'List.foldl' 'union' 'empty'@).
unions :: Ord k => [MaxPQueue k a] -> MaxPQueue k a
unions :: forall k a. Ord k => [MaxPQueue k a] -> MaxPQueue k a
unions [MaxPQueue k a]
qs = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a. Ord k => [MinPQueue k a] -> MinPQueue k a
Q.unions [MinPQueue (Down k) a
q | MaxPQ MinPQueue (Down k) a
q <- [MaxPQueue k a]
qs])

-- | \(O(1)\). Checks if this priority queue is empty.
null :: MaxPQueue k a -> Bool
null :: forall k a. MaxPQueue k a -> Bool
null (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue k a -> Bool
Q.null MinPQueue (Down k) a
q

-- | \(O(1)\). Returns the size of this priority queue.
size :: MaxPQueue k a -> Int
size :: forall k a. MaxPQueue k a -> Int
size (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue k a -> Int
Q.size MinPQueue (Down k) a
q

-- | \(O(1)\). The maximal (key, element) in the queue. Calls 'error' if empty.
findMax :: MaxPQueue k a -> (k, a)
findMax :: forall k a. MaxPQueue k a -> (k, a)
findMax = forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => String -> a
error String
"Error: findMax called on an empty queue") forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. MaxPQueue k a -> Maybe (k, a)
getMax

-- | \(O(1)\). The maximal (key, element) in the queue, if the queue is nonempty.
getMax :: MaxPQueue k a -> Maybe (k, a)
getMax :: forall k a. MaxPQueue k a -> Maybe (k, a)
getMax (MaxPQ MinPQueue (Down k) a
q) = do
  (Down k
k, a
a) <- forall k a. MinPQueue k a -> Maybe (k, a)
Q.getMin MinPQueue (Down k) a
q
  forall (m :: * -> *) a. Monad m => a -> m a
return (k
k, a
a)

-- | \(O(\log n)\). Delete and find the element with the maximum key. Calls 'error' if empty.
deleteMax :: Ord k => MaxPQueue k a -> MaxPQueue k a
deleteMax :: forall k a. Ord k => MaxPQueue k a -> MaxPQueue k a
deleteMax (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a. Ord k => MinPQueue k a -> MinPQueue k a
Q.deleteMin MinPQueue (Down k) a
q)

-- | \(O(\log n)\). Delete and find the element with the maximum key. Calls 'error' if empty.
deleteFindMax :: Ord k => MaxPQueue k a -> ((k, a), MaxPQueue k a)
deleteFindMax :: forall k a. Ord k => MaxPQueue k a -> ((k, a), MaxPQueue k a)
deleteFindMax = forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => String -> a
error String
"Error: deleteFindMax called on an empty queue") forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => MaxPQueue k a -> Maybe ((k, a), MaxPQueue k a)
maxViewWithKey

-- | \(O(1)\). Alter the value at the maximum key. If the queue is empty, does nothing.
adjustMax :: (a -> a) -> MaxPQueue k a -> MaxPQueue k a
adjustMax :: forall a k. (a -> a) -> MaxPQueue k a -> MaxPQueue k a
adjustMax = forall k a. (k -> a -> a) -> MaxPQueue k a -> MaxPQueue k a
adjustMaxWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(1)\) per operation. Alter the value at the maximum key in an
-- 'Applicative' context. If the queue is empty, does nothing.
--
-- @since 1.4.2
adjustMaxA :: Applicative f => (a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a)
adjustMaxA :: forall (f :: * -> *) a k.
Applicative f =>
(a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a)
adjustMaxA = forall (f :: * -> *) k a.
Applicative f =>
(k -> a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a)
adjustMaxWithKeyA forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(1)\). Alter the value at the maximum key. If the queue is empty, does nothing.
adjustMaxWithKey :: (k -> a -> a) -> MaxPQueue k a -> MaxPQueue k a
adjustMaxWithKey :: forall k a. (k -> a -> a) -> MaxPQueue k a -> MaxPQueue k a
adjustMaxWithKey k -> a -> a
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a. (k -> a -> a) -> MinPQueue k a -> MinPQueue k a
Q.adjustMinWithKey (k -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q)

-- | \(O(1)\) per operation. Alter the value at the maximum key in an
-- 'Applicative' context. If the queue is empty, does nothing.
--
-- @since 1.4.2
adjustMaxWithKeyA :: Applicative f => (k -> a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a)
adjustMaxWithKeyA :: forall (f :: * -> *) k a.
Applicative f =>
(k -> a -> f a) -> MaxPQueue k a -> f (MaxPQueue k a)
adjustMaxWithKeyA k -> a -> f a
f (MaxPQ MinPQueue (Down k) a
q) = forall (f :: * -> *) k a r.
Applicative f =>
(MinPQueue k a -> r) -> (k -> a -> f a) -> MinPQueue k a -> f r
PrioInternals.adjustMinWithKeyA' forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (k -> a -> f a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q

-- | \(O(\log n)\). (Actually \(O(1)\) if there's no deletion.) Update the value at the maximum key.
-- If the queue is empty, does nothing.
updateMax :: Ord k => (a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
updateMax :: forall k a.
Ord k =>
(a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
updateMax = forall k a.
Ord k =>
(k -> a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
updateMaxWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(\log n)\) per operation. (Actually \(O(1)\) if there's no deletion.) Update
-- the value at the maximum key in an 'Applicative' context. If the queue is
-- empty, does nothing.
--
-- @since 1.4.2
updateMaxA :: (Applicative f, Ord k) => (a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a)
updateMaxA :: forall (f :: * -> *) k a.
(Applicative f, Ord k) =>
(a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a)
updateMaxA = forall (f :: * -> *) k a.
(Applicative f, Ord k) =>
(k -> a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a)
updateMaxWithKeyA forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(\log n)\). (Actually \(O(1)\) if there's no deletion.) Update the value at the maximum key.
-- If the queue is empty, does nothing.
updateMaxWithKey :: Ord k => (k -> a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
updateMaxWithKey :: forall k a.
Ord k =>
(k -> a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
updateMaxWithKey k -> a -> Maybe a
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a.
Ord k =>
(k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
Q.updateMinWithKey (k -> a -> Maybe a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q)

-- | \(O(\log n)\) per operation. (Actually \(O(1)\) if there's no deletion.) Update
-- the value at the maximum key in an 'Applicative' context. If the queue is
-- empty, does nothing.
--
-- @since 1.4.2
updateMaxWithKeyA :: (Applicative f, Ord k) => (k -> a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a)
updateMaxWithKeyA :: forall (f :: * -> *) k a.
(Applicative f, Ord k) =>
(k -> a -> f (Maybe a)) -> MaxPQueue k a -> f (MaxPQueue k a)
updateMaxWithKeyA k -> a -> f (Maybe a)
f (MaxPQ MinPQueue (Down k) a
q) = forall (f :: * -> *) k a r.
(Applicative f, Ord k) =>
(MinPQueue k a -> r)
-> (k -> a -> f (Maybe a)) -> MinPQueue k a -> f r
PrioInternals.updateMinWithKeyA' forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (k -> a -> f (Maybe a)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q

-- | \(O(\log n)\). Retrieves the value associated with the maximum key of the queue, and the queue
-- stripped of that element, or 'Nothing' if passed an empty queue.
maxView :: Ord k => MaxPQueue k a -> Maybe (a, MaxPQueue k a)
maxView :: forall k a. Ord k => MaxPQueue k a -> Maybe (a, MaxPQueue k a)
maxView MaxPQueue k a
q = do
  ((k
_, a
a), MaxPQueue k a
q') <- forall k a. Ord k => MaxPQueue k a -> Maybe ((k, a), MaxPQueue k a)
maxViewWithKey MaxPQueue k a
q
  forall (m :: * -> *) a. Monad m => a -> m a
return (a
a, MaxPQueue k a
q')

-- | \(O(\log n)\). Retrieves the maximal (key, value) pair of the map, and the map stripped of that
-- element, or 'Nothing' if passed an empty map.
maxViewWithKey :: Ord k => MaxPQueue k a -> Maybe ((k, a), MaxPQueue k a)
maxViewWithKey :: forall k a. Ord k => MaxPQueue k a -> Maybe ((k, a), MaxPQueue k a)
maxViewWithKey (MaxPQ MinPQueue (Down k) a
q) = do
  ((Down k
k, a
a), MinPQueue (Down k) a
q') <- forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
Q.minViewWithKey MinPQueue (Down k) a
q
  forall (m :: * -> *) a. Monad m => a -> m a
return ((k
k, a
a), forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ MinPQueue (Down k) a
q')

-- | \(O(n)\). Map a function over all values in the queue.
map :: (a -> b) -> MaxPQueue k a -> MaxPQueue k b
map :: forall a b k. (a -> b) -> MaxPQueue k a -> MaxPQueue k b
map = forall k a b. (k -> a -> b) -> MaxPQueue k a -> MaxPQueue k b
mapWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(n)\). Map a function over all values in the queue.
mapWithKey :: (k -> a -> b) -> MaxPQueue k a -> MaxPQueue k b
mapWithKey :: forall k a b. (k -> a -> b) -> MaxPQueue k a -> MaxPQueue k b
mapWithKey k -> a -> b
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a b. (k -> a -> b) -> MinPQueue k a -> MinPQueue k b
Q.mapWithKey (k -> a -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q)

-- | \(O(n)\). Map a function over all values in the queue.
mapKeys :: Ord k' => (k -> k') -> MaxPQueue k a -> MaxPQueue k' a
mapKeys :: forall k' k a.
Ord k' =>
(k -> k') -> MaxPQueue k a -> MaxPQueue k' a
mapKeys k -> k'
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k' k a.
Ord k' =>
(k -> k') -> MinPQueue k a -> MinPQueue k' a
Q.mapKeys (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap k -> k'
f) MinPQueue (Down k) a
q)

-- | \(O(n)\). @'mapKeysMonotonic' f q == 'mapKeys' f q@, but only works when @f@ is strictly
-- monotonic. /The precondition is not checked./ This function has better performance than
-- 'mapKeys'.
mapKeysMonotonic :: (k -> k') -> MaxPQueue k a -> MaxPQueue k' a
mapKeysMonotonic :: forall k k' a. (k -> k') -> MaxPQueue k a -> MaxPQueue k' a
mapKeysMonotonic k -> k'
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k k' a. (k -> k') -> MinPQueue k a -> MinPQueue k' a
Q.mapKeysMonotonic (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap k -> k'
f) MinPQueue (Down k) a
q)

-- | \(O(n \log n)\). Fold the keys and values in the map, such that
-- @'foldrWithKey' f z q == 'List.foldr' ('uncurry' f) z ('toDescList' q)@.
--
-- If you do not care about the traversal order, consider using 'foldrWithKeyU'.
foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
foldrWithKey :: forall k a b.
Ord k =>
(k -> a -> b -> b) -> b -> MaxPQueue k a -> b
foldrWithKey k -> a -> b -> b
f b
z (MaxPQ MinPQueue (Down k) a
q) = forall k a b.
Ord k =>
(k -> a -> b -> b) -> b -> MinPQueue k a -> b
Q.foldrWithKey (k -> a -> b -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) b
z MinPQueue (Down k) a
q

-- | \(O(n \log n)\). Fold the keys and values in the map, such that
-- @'foldlWithKey' f z q == 'List.foldl' ('uncurry' . f) z ('toDescList' q)@.
--
-- If you do not care about the traversal order, consider using 'foldlWithKeyU'.
foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
foldlWithKey :: forall k b a.
Ord k =>
(b -> k -> a -> b) -> b -> MaxPQueue k a -> b
foldlWithKey b -> k -> a -> b
f b
z0 (MaxPQ MinPQueue (Down k) a
q) = forall k b a.
Ord k =>
(b -> k -> a -> b) -> b -> MinPQueue k a -> b
Q.foldlWithKey (\b
z -> b -> k -> a -> b
f b
z forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) b
z0 MinPQueue (Down k) a
q

-- | \(O(n \log n)\). Traverses the elements of the queue in descending order by key.
-- (@'traverseWithKey' f q == 'fromDescList' <$> 'traverse' ('uncurry' f) ('toDescList' q)@)
--
-- If you do not care about the /order/ of the traversal, consider using 'traverseWithKeyU'.
--
-- If you are working in a strict monad, consider using 'mapMWithKey'.
traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
traverseWithKey :: forall k (f :: * -> *) a b.
(Ord k, Applicative f) =>
(k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
traverseWithKey k -> a -> f b
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall k (f :: * -> *) a b.
(Ord k, Applicative f) =>
(k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
Q.traverseWithKey (k -> a -> f b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q

-- | A strictly accumulating version of 'traverseWithKey'. This works well in
-- 'IO' and strict @State@, and is likely what you want for other "strict" monads,
-- where @⊥ >>= pure () = ⊥@.
mapMWithKey :: (Ord k, Monad m) => (k -> a -> m b) -> MaxPQueue k a -> m (MaxPQueue k b)
mapMWithKey :: forall k (m :: * -> *) a b.
(Ord k, Monad m) =>
(k -> a -> m b) -> MaxPQueue k a -> m (MaxPQueue k b)
mapMWithKey k -> a -> m b
f = MaxPQueue k b -> MaxPQueue k a -> m (MaxPQueue k b)
go forall k a. MaxPQueue k a
empty
  where
    go :: MaxPQueue k b -> MaxPQueue k a -> m (MaxPQueue k b)
go !MaxPQueue k b
acc MaxPQueue k a
q =
      case forall k a. Ord k => MaxPQueue k a -> Maybe ((k, a), MaxPQueue k a)
maxViewWithKey MaxPQueue k a
q of
        Maybe ((k, a), MaxPQueue k a)
Nothing           -> forall (f :: * -> *) a. Applicative f => a -> f a
pure MaxPQueue k b
acc
        Just ((k
k, a
a), MaxPQueue k a
q') -> do
          b
b <- k -> a -> m b
f k
k a
a
          let !acc' :: MaxPQueue k b
acc' = forall k a. k -> a -> MaxPQueue k a -> MaxPQueue k a
insertMin' k
k b
b MaxPQueue k b
acc
          MaxPQueue k b -> MaxPQueue k a -> m (MaxPQueue k b)
go MaxPQueue k b
acc' MaxPQueue k a
q'

insertMin' :: k -> a -> MaxPQueue k a -> MaxPQueue k a
insertMin' :: forall k a. k -> a -> MaxPQueue k a -> MaxPQueue k a
insertMin' k
k a
a (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a. k -> a -> MinPQueue k a -> MinPQueue k a
PrioInternals.insertMax' (forall a. a -> Down a
Down k
k) a
a MinPQueue (Down k) a
q)

-- | \(O(k \log n)\)/. Takes the first @k@ (key, value) pairs in the queue, or the first @n@ if @k >= n@.
-- (@'take' k q == 'List.take' k ('toDescList' q)@)
take :: Ord k => Int -> MaxPQueue k a -> [(k, a)]
take :: forall k a. Ord k => Int -> MaxPQueue k a -> [(k, a)]
take Int
k (MaxPQ MinPQueue (Down k) a
q) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. Down a -> a
unDown) (forall k a. Ord k => Int -> MinPQueue k a -> [(k, a)]
Q.take Int
k MinPQueue (Down k) a
q)

-- | \(O(k \log n)\)/. Deletes the first @k@ (key, value) pairs in the queue, or returns an empty queue if @k >= n@.
drop :: Ord k => Int -> MaxPQueue k a -> MaxPQueue k a
drop :: forall k a. Ord k => Int -> MaxPQueue k a -> MaxPQueue k a
drop Int
k (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a. Ord k => Int -> MinPQueue k a -> MinPQueue k a
Q.drop Int
k MinPQueue (Down k) a
q)

-- | \(O(k \log n)\)/. Equivalent to @('take' k q, 'drop' k q)@.
splitAt :: Ord k => Int -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
splitAt :: forall k a.
Ord k =>
Int -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
splitAt Int
k (MaxPQ MinPQueue (Down k) a
q) = case forall k a.
Ord k =>
Int -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
Q.splitAt Int
k MinPQueue (Down k) a
q of
  ([(Down k, a)]
xs, MinPQueue (Down k) a
q') -> (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. Down a -> a
unDown) [(Down k, a)]
xs, forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ MinPQueue (Down k) a
q')

-- | Takes the longest possible prefix of elements satisfying the predicate.
-- (@'takeWhile' p q == 'List.takeWhile' (p . 'snd') ('toDescList' q)@)
takeWhile :: Ord k => (a -> Bool) -> MaxPQueue k a -> [(k, a)]
takeWhile :: forall k a. Ord k => (a -> Bool) -> MaxPQueue k a -> [(k, a)]
takeWhile = forall k a. Ord k => (k -> a -> Bool) -> MaxPQueue k a -> [(k, a)]
takeWhileWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | Takes the longest possible prefix of elements satisfying the predicate.
-- (@'takeWhile' p q == 'List.takeWhile' (uncurry p) ('toDescList' q)@)
takeWhileWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> [(k, a)]
takeWhileWithKey :: forall k a. Ord k => (k -> a -> Bool) -> MaxPQueue k a -> [(k, a)]
takeWhileWithKey k -> a -> Bool
p (MaxPQ MinPQueue (Down k) a
q) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. Down a -> a
unDown) (forall k a. Ord k => (k -> a -> Bool) -> MinPQueue k a -> [(k, a)]
Q.takeWhileWithKey (k -> a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q)

-- | Removes the longest possible prefix of elements satisfying the predicate.
dropWhile :: Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
dropWhile :: forall k a. Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
dropWhile = forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
dropWhileWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | Removes the longest possible prefix of elements satisfying the predicate.
dropWhileWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
dropWhileWithKey :: forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
dropWhileWithKey k -> a -> Bool
p (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a.
Ord k =>
(k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
Q.dropWhileWithKey (k -> a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q)

-- | Equivalent to @('takeWhile' p q, 'dropWhile' p q)@.
span :: Ord k => (a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
span :: forall k a.
Ord k =>
(a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
span = forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
spanWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | Equivalent to @'span' ('not' . p)@.
break :: Ord k => (a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
break :: forall k a.
Ord k =>
(a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
break = forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
breakWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | Equivalent to @'spanWithKey' (\k a -> 'not' (p k a)) q@.
spanWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
spanWithKey :: forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
spanWithKey k -> a -> Bool
p (MaxPQ MinPQueue (Down k) a
q) = case forall k a.
Ord k =>
(k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
Q.spanWithKey (k -> a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q of
  ([(Down k, a)]
xs, MinPQueue (Down k) a
q') -> (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. Down a -> a
unDown) [(Down k, a)]
xs, forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ MinPQueue (Down k) a
q')

-- | Equivalent to @'spanWithKey' (\k a -> 'not' (p k a)) q@.
breakWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
breakWithKey :: forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> ([(k, a)], MaxPQueue k a)
breakWithKey k -> a -> Bool
p (MaxPQ MinPQueue (Down k) a
q) = case forall k a.
Ord k =>
(k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
Q.breakWithKey (k -> a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q of
  ([(Down k, a)]
xs, MinPQueue (Down k) a
q') -> (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. Down a -> a
unDown) [(Down k, a)]
xs, forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ MinPQueue (Down k) a
q')

-- | \(O(n)\). Filter all values that satisfy the predicate.
filter :: Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
filter :: forall k a. Ord k => (a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
filter = forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
filterWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(n)\). Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
filterWithKey :: forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> MaxPQueue k a
filterWithKey k -> a -> Bool
p (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a.
Ord k =>
(k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
Q.filterWithKey (k -> a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q)

-- | \(O(n)\). Partition the queue according to a predicate. The first queue contains all elements
-- which satisfy the predicate, the second all elements that fail the predicate.
partition :: Ord k => (a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a)
partition :: forall k a.
Ord k =>
(a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a)
partition = forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a)
partitionWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(n)\). Partition the queue according to a predicate. The first queue contains all elements
-- which satisfy the predicate, the second all elements that fail the predicate.
partitionWithKey :: Ord k => (k -> a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a)
partitionWithKey :: forall k a.
Ord k =>
(k -> a -> Bool) -> MaxPQueue k a -> (MaxPQueue k a, MaxPQueue k a)
partitionWithKey k -> a -> Bool
p (MaxPQ MinPQueue (Down k) a
q) = case forall k a.
Ord k =>
(k -> a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
Q.partitionWithKey (k -> a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q of
  (MinPQueue (Down k) a
q1, MinPQueue (Down k) a
q0) -> (forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ MinPQueue (Down k) a
q1, forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ MinPQueue (Down k) a
q0)

-- | \(O(n)\). Map values and collect the 'Just' results.
mapMaybe :: Ord k => (a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b
mapMaybe :: forall k a b.
Ord k =>
(a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b
mapMaybe = forall k a b.
Ord k =>
(k -> a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b
mapMaybeWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(n)\). Map values and collect the 'Just' results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b
mapMaybeWithKey :: forall k a b.
Ord k =>
(k -> a -> Maybe b) -> MaxPQueue k a -> MaxPQueue k b
mapMaybeWithKey k -> a -> Maybe b
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ (forall k a b.
Ord k =>
(k -> a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
Q.mapMaybeWithKey (k -> a -> Maybe b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q)

-- | \(O(n)\). Map values and separate the 'Left' and 'Right' results.
mapEither :: Ord k => (a -> Either b c) -> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c)
mapEither :: forall k a b c.
Ord k =>
(a -> Either b c)
-> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c)
mapEither = forall k a b c.
Ord k =>
(k -> a -> Either b c)
-> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c)
mapEitherWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(n)\). Map values and separate the 'Left' and 'Right' results.
mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c)
mapEitherWithKey :: forall k a b c.
Ord k =>
(k -> a -> Either b c)
-> MaxPQueue k a -> (MaxPQueue k b, MaxPQueue k c)
mapEitherWithKey k -> a -> Either b c
f (MaxPQ MinPQueue (Down k) a
q) = case forall k a b c.
Ord k =>
(k -> a -> Either b c)
-> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)
Q.mapEitherWithKey (k -> a -> Either b c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q of
  (MinPQueue (Down k) b
qL, MinPQueue (Down k) c
qR) -> (forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ MinPQueue (Down k) b
qL, forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ MinPQueue (Down k) c
qR)

-- | \(O(n)\). Build a priority queue from the list of (key, value) pairs.
fromList :: Ord k => [(k, a)] -> MaxPQueue k a
fromList :: forall k a. Ord k => [(k, a)] -> MaxPQueue k a
fromList = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => [(k, a)] -> MinPQueue k a
Q.fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. a -> Down a
Down)

-- | \(O(n)\). Build a priority queue from an ascending list of (key, value) pairs. /The precondition is not checked./
fromAscList :: [(k, a)] -> MaxPQueue k a
fromAscList :: forall k a. [(k, a)] -> MaxPQueue k a
fromAscList = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. [(k, a)] -> MinPQueue k a
Q.fromDescList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. a -> Down a
Down)

-- | \(O(n)\). Build a priority queue from a descending list of (key, value) pairs. /The precondition is not checked./
fromDescList :: [(k, a)] -> MaxPQueue k a
fromDescList :: forall k a. [(k, a)] -> MaxPQueue k a
fromDescList = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. [(k, a)] -> MinPQueue k a
Q.fromAscList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. a -> Down a
Down)

-- | \(O(n \log n)\). Return all keys of the queue in descending order.
keys :: Ord k => MaxPQueue k a -> [k]
keys :: forall k a. Ord k => MaxPQueue k a -> [k]
keys = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> a
fst forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => MaxPQueue k a -> [(k, a)]
toDescList

-- | \(O(n \log n)\). Return all elements of the queue in descending order by key.
elems :: Ord k => MaxPQueue k a -> [a]
elems :: forall k a. Ord k => MaxPQueue k a -> [a]
elems = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => MaxPQueue k a -> [(k, a)]
toDescList

-- | \(O(n \log n)\). Equivalent to 'toDescList'.
assocs :: Ord k => MaxPQueue k a -> [(k, a)]
assocs :: forall k a. Ord k => MaxPQueue k a -> [(k, a)]
assocs = forall k a. Ord k => MaxPQueue k a -> [(k, a)]
toDescList

-- | \(O(n \log n)\). Return all (key, value) pairs in ascending order by key.
toAscList :: Ord k => MaxPQueue k a -> [(k, a)]
toAscList :: forall k a. Ord k => MaxPQueue k a -> [(k, a)]
toAscList (MaxPQ MinPQueue (Down k) a
q) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. Down a -> a
unDown) (forall k a. Ord k => MinPQueue k a -> [(k, a)]
Q.toDescList MinPQueue (Down k) a
q)

-- | \(O(n \log n)\). Return all (key, value) pairs in descending order by key.
toDescList :: Ord k => MaxPQueue k a -> [(k, a)]
toDescList :: forall k a. Ord k => MaxPQueue k a -> [(k, a)]
toDescList (MaxPQ MinPQueue (Down k) a
q) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. Down a -> a
unDown) (forall k a. Ord k => MinPQueue k a -> [(k, a)]
Q.toAscList MinPQueue (Down k) a
q)

-- | \(O(n \log n)\). Equivalent to 'toDescList'.
--
-- If the traversal order is irrelevant, consider using 'toListU'.
toList :: Ord k => MaxPQueue k a -> [(k, a)]
toList :: forall k a. Ord k => MaxPQueue k a -> [(k, a)]
toList = forall k a. Ord k => MaxPQueue k a -> [(k, a)]
toDescList

-- | \(O(n)\). An unordered right fold over the elements of the queue, in no particular order.
foldrU :: (a -> b -> b) -> b -> MaxPQueue k a -> b
foldrU :: forall a b k. (a -> b -> b) -> b -> MaxPQueue k a -> b
foldrU = forall k a b. (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
foldrWithKeyU forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(n)\). An unordered right fold over the elements of the queue, in no particular order.
foldrWithKeyU :: (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
foldrWithKeyU :: forall k a b. (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
foldrWithKeyU k -> a -> b -> b
f b
z (MaxPQ MinPQueue (Down k) a
q) = forall k a b. (k -> a -> b -> b) -> b -> MinPQueue k a -> b
Q.foldrWithKeyU (k -> a -> b -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) b
z MinPQueue (Down k) a
q

-- | \(O(n)\). An unordered monoidal fold over the elements of the queue, in no particular order.
--
-- @since 1.4.2
foldMapWithKeyU :: Monoid m => (k -> a -> m) -> MaxPQueue k a -> m
foldMapWithKeyU :: forall m k a. Monoid m => (k -> a -> m) -> MaxPQueue k a -> m
foldMapWithKeyU k -> a -> m
f (MaxPQ MinPQueue (Down k) a
q) = forall m k a. Monoid m => (k -> a -> m) -> MinPQueue k a -> m
Q.foldMapWithKeyU (k -> a -> m
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q

-- | \(O(n)\). An unordered left fold over the elements of the queue, in no
-- particular order. This is rarely what you want; 'foldrU' and 'foldlU'' are
-- more likely to perform well.
foldlU :: (b -> a -> b) -> b -> MaxPQueue k a -> b
foldlU :: forall b a k. (b -> a -> b) -> b -> MaxPQueue k a -> b
foldlU b -> a -> b
f = forall b k a. (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
foldlWithKeyU (forall a b. a -> b -> a
const forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> a -> b
f)

-- | \(O(n)\). An unordered strict left fold over the elements of the queue, in no
-- particular order.
--
-- @since 1.4.2
foldlU' :: (b -> a -> b) -> b -> MaxPQueue k a -> b
foldlU' :: forall b a k. (b -> a -> b) -> b -> MaxPQueue k a -> b
foldlU' b -> a -> b
f = forall b k a. (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
foldlWithKeyU' (forall a b. a -> b -> a
const forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> a -> b
f)

-- | \(O(n)\). An unordered left fold over the elements of the queue, in no
-- particular order. This is rarely what you want; 'foldrWithKeyU' and
-- 'foldlWithKeyU'' are more likely to perform well.
foldlWithKeyU :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
foldlWithKeyU :: forall b k a. (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
foldlWithKeyU b -> k -> a -> b
f b
z0 (MaxPQ MinPQueue (Down k) a
q) = forall b k a. (b -> k -> a -> b) -> b -> MinPQueue k a -> b
Q.foldlWithKeyU (\b
z -> b -> k -> a -> b
f b
z forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) b
z0 MinPQueue (Down k) a
q

-- | \(O(n)\). An unordered left fold over the elements of the queue, in no particular order.
--
-- @since 1.4.2
foldlWithKeyU' :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
foldlWithKeyU' :: forall b k a. (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
foldlWithKeyU' b -> k -> a -> b
f b
z0 (MaxPQ MinPQueue (Down k) a
q) = forall b k a. (b -> k -> a -> b) -> b -> MinPQueue k a -> b
Q.foldlWithKeyU' (\b
z -> b -> k -> a -> b
f b
z forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) b
z0 MinPQueue (Down k) a
q

-- | \(O(n)\). An unordered traversal over a priority queue, in no particular order.
-- While there is no guarantee in which order the elements are traversed, the resulting
-- priority queue will be perfectly valid.
traverseU :: (Applicative f) => (a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
traverseU :: forall (f :: * -> *) a b k.
Applicative f =>
(a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
traverseU = forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
traverseWithKeyU forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const

-- | \(O(n)\). An unordered traversal over a priority queue, in no particular order.
-- While there is no guarantee in which order the elements are traversed, the resulting
-- priority queue will be perfectly valid.
traverseWithKeyU :: (Applicative f) => (k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
traverseWithKeyU :: forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> MaxPQueue k a -> f (MaxPQueue k b)
traverseWithKeyU k -> a -> f b
f (MaxPQ MinPQueue (Down k) a
q) = forall k a. MinPQueue (Down k) a -> MaxPQueue k a
MaxPQ forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
Q.traverseWithKeyU (k -> a -> f b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Down a -> a
unDown) MinPQueue (Down k) a
q

-- | \(O(n)\). Return all keys of the queue in no particular order.
keysU :: MaxPQueue k a -> [k]
keysU :: forall k a. MaxPQueue k a -> [k]
keysU = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> a
fst forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. MaxPQueue k a -> [(k, a)]
toListU

-- | \(O(n)\). Return all elements of the queue in no particular order.
elemsU :: MaxPQueue k a -> [a]
elemsU :: forall k a. MaxPQueue k a -> [a]
elemsU = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. MaxPQueue k a -> [(k, a)]
toListU

-- | \(O(n)\). Equivalent to 'toListU'.
assocsU :: MaxPQueue k a -> [(k, a)]
assocsU :: forall k a. MaxPQueue k a -> [(k, a)]
assocsU = forall k a. MaxPQueue k a -> [(k, a)]
toListU

-- | \(O(n)\). Returns all (key, value) pairs in the queue in no particular order.
toListU :: MaxPQueue k a -> [(k, a)]
toListU :: forall k a. MaxPQueue k a -> [(k, a)]
toListU (MaxPQ MinPQueue (Down k) a
q) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b c. (a -> b) -> (a, c) -> (b, c)
first' forall a. Down a -> a
unDown) (forall k a. MinPQueue k a -> [(k, a)]
Q.toListU MinPQueue (Down k) a
q)

-- | \(O(\log n)\). @seqSpine q r@ forces the spine of @q@ and returns @r@.
--
-- Note: The spine of a 'MaxPQueue' is stored somewhat lazily. Most operations
-- take great care to prevent chains of thunks from accumulating along the
-- spine to the detriment of performance. However, 'mapKeysMonotonic' can leave
-- expensive thunks in the structure and repeated applications of that function
-- can create thunk chains.
seqSpine :: MaxPQueue k a -> b -> b
seqSpine :: forall k a b. MaxPQueue k a -> b -> b
seqSpine (MaxPQ MinPQueue (Down k) a
q) = forall k a b. MinPQueue k a -> b -> b
Q.seqSpine MinPQueue (Down k) a
q