    {-# LANGUAGE CPP #-}
    {-# LANGUAGE PatternSynonyms #-}
    {-# LANGUAGE ViewPatterns #-}

    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Data.PQueue.Prio.Min
    -- Copyright   :  (c) Louis Wasserman 2010
    -- License     :  BSD-style
    -- Maintainer  :  libraries@haskell.org
    -- Stability   :  experimental
    -- Portability :  portable
    --
    -- General purpose priority queue.
    -- Each element is associated with a /key/, and the priority queue supports
    -- viewing and extracting the element with the minimum key.
    --
    -- A worst-case bound is given for each operation. In some cases, an amortized
    -- bound is also specified; these bounds hold even in a persistent context.
    --
    -- This implementation is based on a binomial heap augmented with a global root.
    --
    -- We do not guarantee stable behavior.
    -- Ties are broken arbitrarily -- that is, if @k1 <= k2@ and @k2 <= k1@, then there
    -- are no guarantees about the relative order in which @k1@, @k2@, and their associated
    -- elements are returned. (Unlike Data.Map, we allow multiple elements with the
    -- same key.)
    --
    -- This implementation offers a number of methods of the form @xxxU@, where @U@ stands for
    -- unordered. No guarantees whatsoever are made on the execution or traversal order of
    -- these functions.
    -----------------------------------------------------------------------------
    module Data.PQueue.Prio.Min (
    #if __GLASGOW_HASKELL__ >= 802
      MinPQueue (Data.PQueue.Prio.Min.Empty, (:<)),
    #elif defined (__GLASGOW_HASKELL__)
      MinPQueue,
      pattern Data.PQueue.Prio.Min.Empty,
      pattern (:<),
    #endif
      -- * Construction
      empty,
      singleton,
      insert,
      insertBehind,
      union,
      unions,
      -- * Query
      null,
      size,
      -- ** Minimum view
      findMin,
      getMin,
      deleteMin,
      deleteFindMin,
      adjustMin,
      adjustMinA,
      adjustMinWithKey,
      adjustMinWithKeyA,
      updateMin,
      updateMinA,
      updateMinWithKey,
      updateMinWithKeyA,
      minView,
      minViewWithKey,
      -- * 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 qualified Data.List as List
    import Data.Maybe (fromMaybe)

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

    import Data.PQueue.Prio.Internals hiding (MinPQueue (..))
    import Data.PQueue.Prio.Internals (MinPQueue)
    import qualified Data.PQueue.Prio.Internals as Internals

    import Prelude hiding (map, filter, break, span, takeWhile, dropWhile, splitAt, take, drop, (!!), null)

    #ifdef __GLASGOW_HASKELL__
    -- | A bidirectional pattern synonym for an empty priority queue.
    --
    -- @since 1.5.0
    pattern Empty :: MinPQueue k a
    pattern $mEmpty :: forall {r} {k} {a}.
    MinPQueue k a -> ((# #) -> r) -> ((# #) -> r) -> r
    $bEmpty :: forall k a. MinPQueue k a
    Empty = Internals.Empty
    # if __GLASGOW_HASKELL__ >= 902
    {-# INLINE CONLIKE Empty #-}
    # endif

    infixr 5 :<

    -- | A bidirectional pattern synonym for working with the minimum view of a
    -- 'MinPQueue'. Using @:<@ to construct a queue performs an insertion in
    -- \(O(1)\) amortized time. When matching on @(k, a) :< q@, forcing @q@ takes
    -- \(O(\log n)\) time.
    --
    -- @since 1.5.0
    # if __GLASGOW_HASKELL__ >= 800
    pattern (:<) :: Ord k => (k, a) -> MinPQueue k a -> MinPQueue k a
    # else
    pattern (:<) :: () => Ord k => (k, a) -> MinPQueue k a -> MinPQueue k a
    # endif
    pattern ka $m:< :: forall {r} {k} {a}.
    Ord k =>
    MinPQueue k a
    -> ((k, a) -> MinPQueue k a -> r) -> ((# #) -> r) -> r
    $b:< :: forall k a. Ord k => (k, a) -> MinPQueue k a -> MinPQueue k a
    :< q <- (minViewWithKey -> Just (ka, q))
      where
        (k
    k, a
    a) :< MinPQueue k a
    q = k -> a -> MinPQueue k a -> MinPQueue k a
    forall k a. Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
    insert k
    k a
    a MinPQueue k a
    q
    # if __GLASGOW_HASKELL__ >= 902
    {-# INLINE (:<) #-}
    # endif

    {-# COMPLETE Empty, (:<) #-}
    #endif

    (.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
    (c -> d
    f .: :: forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
    .: a -> b -> c
    g) a
    x b
    y = c -> d
    f (a -> b -> c
    g a
    x b
    y)

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

    infixr 8 .:

    -- | \(O(1)\). The minimal (key, element) in the queue. Calls 'error' if empty.
    findMin :: MinPQueue k a -> (k, a)
    findMin :: forall k a. MinPQueue k a -> (k, a)
    findMin = (k, a) -> Maybe (k, a) -> (k, a)
    forall a. a -> Maybe a -> a
    fromMaybe ([Char] -> (k, a)
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Error: findMin called on an empty queue") (Maybe (k, a) -> (k, a))
    -> (MinPQueue k a -> Maybe (k, a)) -> MinPQueue k a -> (k, a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinPQueue k a -> Maybe (k, a)
    forall k a. MinPQueue k a -> Maybe (k, a)
    getMin

    -- | \(O(\log n)\). Deletes the minimal (key, element) in the queue. Returns an empty queue
    -- if the queue is empty.
    deleteMin :: Ord k => MinPQueue k a -> MinPQueue k a
    deleteMin :: forall k a. Ord k => MinPQueue k a -> MinPQueue k a
    deleteMin = (a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
    forall k a.
    Ord k =>
    (a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
    updateMin (Maybe a -> a -> Maybe a
    forall a b. a -> b -> a
    const Maybe a
    forall a. Maybe a
    Nothing)

    -- | \(O(\log n)\). Delete and find the element with the minimum key. Calls 'error' if empty.
    deleteFindMin :: Ord k => MinPQueue k a -> ((k, a), MinPQueue k a)
    deleteFindMin :: forall k a. Ord k => MinPQueue k a -> ((k, a), MinPQueue k a)
    deleteFindMin = ((k, a), MinPQueue k a)
    -> Maybe ((k, a), MinPQueue k a) -> ((k, a), MinPQueue k a)
    forall a. a -> Maybe a -> a
    fromMaybe ([Char] -> ((k, a), MinPQueue k a)
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Error: deleteFindMin called on an empty queue") (Maybe ((k, a), MinPQueue k a) -> ((k, a), MinPQueue k a))
    -> (MinPQueue k a -> Maybe ((k, a), MinPQueue k a))
    -> MinPQueue k a
    -> ((k, a), MinPQueue k a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    minViewWithKey

    -- | \(O(1)\). Alter the value at the minimum key. If the queue is empty, does nothing.
    adjustMin :: (a -> a) -> MinPQueue k a -> MinPQueue k a
    adjustMin :: forall a k. (a -> a) -> MinPQueue k a -> MinPQueue k a
    adjustMin = (k -> a -> a) -> MinPQueue k a -> MinPQueue k a
    forall k a. (k -> a -> a) -> MinPQueue k a -> MinPQueue k a
    adjustMinWithKey ((k -> a -> a) -> MinPQueue k a -> MinPQueue k a)
    -> ((a -> a) -> k -> a -> a)
    -> (a -> a)
    -> MinPQueue k a
    -> MinPQueue k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a) -> k -> a -> a
    forall a b. a -> b -> a
    const

    -- | \(O(1)\). Alter the value at the minimum key in an 'Applicative' context. If
    -- the queue is empty, does nothing.
    --
    -- @since 1.4.2
    adjustMinA :: Applicative f => (a -> f a) -> MinPQueue k a -> f (MinPQueue k a)
    adjustMinA :: forall (f :: * -> *) a k.
    Applicative f =>
    (a -> f a) -> MinPQueue k a -> f (MinPQueue k a)
    adjustMinA = (k -> a -> f a) -> MinPQueue k a -> f (MinPQueue k a)
    forall (f :: * -> *) k a.
    Applicative f =>
    (k -> a -> f a) -> MinPQueue k a -> f (MinPQueue k a)
    adjustMinWithKeyA ((k -> a -> f a) -> MinPQueue k a -> f (MinPQueue k a))
    -> ((a -> f a) -> k -> a -> f a)
    -> (a -> f a)
    -> MinPQueue k a
    -> f (MinPQueue k a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> f a) -> k -> a -> f a
    forall a b. a -> b -> a
    const

    -- | \(O(1)\) per operation. Alter the value at the minimum key in an 'Applicative' context. If the
    -- queue is empty, does nothing.
    --
    -- @since 1.4.2
    adjustMinWithKeyA :: Applicative f => (k -> a -> f a) -> MinPQueue k a -> f (MinPQueue k a)
    adjustMinWithKeyA :: forall (f :: * -> *) k a.
    Applicative f =>
    (k -> a -> f a) -> MinPQueue k a -> f (MinPQueue k a)
    adjustMinWithKeyA = (MinPQueue k a -> MinPQueue k a)
    -> (k -> a -> f a) -> MinPQueue k a -> f (MinPQueue k a)
    forall (f :: * -> *) k a r.
    Applicative f =>
    (MinPQueue k a -> r) -> (k -> a -> f a) -> MinPQueue k a -> f r
    adjustMinWithKeyA' MinPQueue k a -> MinPQueue k a
    forall a. a -> a
    id

    -- | \(O(\log n)\). (Actually \(O(1)\) if there's no deletion.) Update the value at the minimum key.
    -- If the queue is empty, does nothing.
    updateMin :: Ord k => (a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
    updateMin :: forall k a.
    Ord k =>
    (a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
    updateMin = (k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
    forall k a.
    Ord k =>
    (k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
    updateMinWithKey ((k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a)
    -> ((a -> Maybe a) -> k -> a -> Maybe a)
    -> (a -> Maybe a)
    -> MinPQueue k a
    -> MinPQueue k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Maybe a) -> k -> a -> Maybe a
    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 minimum key.  If the queue is empty, does nothing.
    --
    -- @since 1.4.2
    updateMinA :: (Applicative f, Ord k) => (a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a)
    updateMinA :: forall (f :: * -> *) k a.
    (Applicative f, Ord k) =>
    (a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a)
    updateMinA = (k -> a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a)
    forall (f :: * -> *) k a.
    (Applicative f, Ord k) =>
    (k -> a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a)
    updateMinWithKeyA ((k -> a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a))
    -> ((a -> f (Maybe a)) -> k -> a -> f (Maybe a))
    -> (a -> f (Maybe a))
    -> MinPQueue k a
    -> f (MinPQueue k a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> f (Maybe a)) -> k -> a -> f (Maybe a)
    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 minimum key in an 'Applicative' context. If the queue is
    -- empty, does nothing.
    --
    -- @since 1.4.2
    updateMinWithKeyA :: (Applicative f, Ord k) => (k -> a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a)
    updateMinWithKeyA :: forall (f :: * -> *) k a.
    (Applicative f, Ord k) =>
    (k -> a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a)
    updateMinWithKeyA = (MinPQueue k a -> MinPQueue k a)
    -> (k -> a -> f (Maybe a)) -> MinPQueue k a -> f (MinPQueue k a)
    forall (f :: * -> *) k a r.
    (Applicative f, Ord k) =>
    (MinPQueue k a -> r)
    -> (k -> a -> f (Maybe a)) -> MinPQueue k a -> f r
    updateMinWithKeyA' MinPQueue k a -> MinPQueue k a
    forall a. a -> a
    id

    -- | \(O(\log n)\). Retrieves the value associated with the minimal key of the queue, and the queue
    -- stripped of that element, or 'Nothing' if passed an empty queue.
    minView :: Ord k => MinPQueue k a -> Maybe (a, MinPQueue k a)
    minView :: forall k a. Ord k => MinPQueue k a -> Maybe (a, MinPQueue k a)
    minView MinPQueue k a
    q = do  ((_, a), q') <- MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    minViewWithKey MinPQueue k a
    q
                    return (a, q')

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

    -- | \(O(n)\). @'mapKeys' f q@ is the queue obtained by applying @f@ to each key of @q@.
    mapKeys :: Ord k' => (k -> k') -> MinPQueue k a -> MinPQueue k' a
    mapKeys :: forall k' k a.
    Ord k' =>
    (k -> k') -> MinPQueue k a -> MinPQueue k' a
    mapKeys k -> k'
    f MinPQueue k a
    q = [(k', a)] -> MinPQueue k' a
    forall k a. Ord k => [(k, a)] -> MinPQueue k a
    fromList [(k -> k'
    f k
    k, a
    a) | (k
    k, a
    a) <- MinPQueue k a -> [(k, a)]
    forall k a. MinPQueue k a -> [(k, a)]
    toListU MinPQueue k a
    q]

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

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

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

    -- | \(O(n)\). Filter all values that satisfy the predicate.
    filterWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
    filterWithKey :: forall k a.
    Ord k =>
    (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
    filterWithKey k -> a -> Bool
    p = (k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
    forall k a b.
    Ord k =>
    (k -> a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
    mapMaybeWithKey (\k
    k a
    a -> if k -> a -> Bool
    p k
    k a
    a then a -> Maybe a
    forall a. a -> Maybe a
    Just a
    a else Maybe a
    forall a. Maybe a
    Nothing)

    -- | \(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) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
    partition :: forall k a.
    Ord k =>
    (a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
    partition = (k -> a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
    forall k a.
    Ord k =>
    (k -> a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
    partitionWithKey ((k -> a -> Bool)
     -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a))
    -> ((a -> Bool) -> k -> a -> Bool)
    -> (a -> Bool)
    -> MinPQueue k a
    -> (MinPQueue k a, MinPQueue k a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Bool) -> k -> a -> Bool
    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) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
    partitionWithKey :: forall k a.
    Ord k =>
    (k -> a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
    partitionWithKey k -> a -> Bool
    p = (k -> a -> Either a a)
    -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
    forall k a b c.
    Ord k =>
    (k -> a -> Either b c)
    -> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)
    mapEitherWithKey (\k
    k a
    a -> if k -> a -> Bool
    p k
    k a
    a then a -> Either a a
    forall a b. a -> Either a b
    Left a
    a else a -> Either a a
    forall a b. b -> Either a b
    Right a
    a)

    {-# INLINE take #-}
    -- | \(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 ('toAscList' q)@)
    take :: Ord k => Int -> MinPQueue k a -> [(k, a)]
    take :: forall k a. Ord k => Int -> MinPQueue k a -> [(k, a)]
    take Int
    n = Int -> [(k, a)] -> [(k, a)]
    forall a. Int -> [a] -> [a]
    List.take Int
    n ([(k, a)] -> [(k, a)])
    -> (MinPQueue k a -> [(k, a)]) -> MinPQueue k a -> [(k, a)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinPQueue k a -> [(k, a)]
    forall k a. Ord k => MinPQueue k a -> [(k, a)]
    toAscList

    -- | \(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 -> MinPQueue k a -> MinPQueue k a
    drop :: forall k a. Ord k => Int -> MinPQueue k a -> MinPQueue k a
    drop Int
    n0 MinPQueue k a
    q0
      | Int
    n0 Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0  = MinPQueue k a
    q0
      | Int
    n0 Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= MinPQueue k a -> Int
    forall k a. MinPQueue k a -> Int
    size MinPQueue k a
    q0  = MinPQueue k a
    forall k a. MinPQueue k a
    empty
      | Bool
    otherwise  = Int -> MinPQueue k a -> MinPQueue k a
    forall {t} {k} {a}.
    (Num t, Ord k, Eq t) =>
    t -> MinPQueue k a -> MinPQueue k a
    drop' Int
    n0 MinPQueue k a
    q0
      where
        drop' :: t -> MinPQueue k a -> MinPQueue k a
    drop' t
    n MinPQueue k a
    q
          | t
    n t -> t -> Bool
    forall a. Eq a => a -> a -> Bool
    == t
    0    = MinPQueue k a
    q
          | Bool
    otherwise = t -> MinPQueue k a -> MinPQueue k a
    drop' (t
    n t -> t -> t
    forall a. Num a => a -> a -> a
    - t
    1) (MinPQueue k a -> MinPQueue k a
    forall k a. Ord k => MinPQueue k a -> MinPQueue k a
    deleteMin MinPQueue k a
    q)

    -- | \(O(k \log n)\)/. Equivalent to @('take' k q, 'drop' k q)@.
    splitAt :: Ord k => Int -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    splitAt :: forall k a.
    Ord k =>
    Int -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    splitAt Int
    n MinPQueue k a
    q
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0     = ([], MinPQueue k a
    q)
      | Bool
    otherwise  = Int
    n Int -> ([(k, a)], MinPQueue k a) -> ([(k, a)], MinPQueue k a)
    forall a b. a -> b -> b
    `seq` case MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    minViewWithKey MinPQueue k a
    q of
          Just ((k, a)
    ka, MinPQueue k a
    q') -> let ([(k, a)]
    kas, MinPQueue k a
    q'') = Int -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    forall k a.
    Ord k =>
    Int -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    splitAt (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) MinPQueue k a
    q' in ((k, a)
    ka (k, a) -> [(k, a)] -> [(k, a)]
    forall a. a -> [a] -> [a]
    : [(k, a)]
    kas, MinPQueue k a
    q'')
          Maybe ((k, a), MinPQueue k a)
    _             -> ([], MinPQueue k a
    q)

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

    {-# INLINE takeWhileWithKey #-}
    -- | Takes the longest possible prefix of elements satisfying the predicate.
    -- (@'takeWhile' p q == 'List.takeWhile' (uncurry p) ('toAscList' q)@)
    takeWhileWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> [(k, a)]
    takeWhileWithKey :: forall k a. Ord k => (k -> a -> Bool) -> MinPQueue k a -> [(k, a)]
    takeWhileWithKey k -> a -> Bool
    p0 = ((k, a) -> Bool) -> [(k, a)] -> [(k, a)]
    forall a. (a -> Bool) -> [a] -> [a]
    List.takeWhile ((k -> a -> Bool) -> (k, a) -> Bool
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry' k -> a -> Bool
    p0) ([(k, a)] -> [(k, a)])
    -> (MinPQueue k a -> [(k, a)]) -> MinPQueue k a -> [(k, a)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinPQueue k a -> [(k, a)]
    forall k a. Ord k => MinPQueue k a -> [(k, a)]
    toAscList

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

    -- | Removes the longest possible prefix of elements satisfying the predicate.
    dropWhileWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
    dropWhileWithKey :: forall k a.
    Ord k =>
    (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
    dropWhileWithKey k -> a -> Bool
    p MinPQueue k a
    q = case MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    minViewWithKey MinPQueue k a
    q of
      Just ((k
    k, a
    a), MinPQueue k a
    q')
        | k -> a -> Bool
    p k
    k a
    a -> (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
    forall k a.
    Ord k =>
    (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
    dropWhileWithKey k -> a -> Bool
    p MinPQueue k a
    q'
      Maybe ((k, a), MinPQueue k a)
    _         -> MinPQueue k a
    q

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

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

    -- | Equivalent to @('takeWhileWithKey' p q, 'dropWhileWithKey' p q)@.
    spanWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    spanWithKey :: forall k a.
    Ord k =>
    (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    spanWithKey k -> a -> Bool
    p MinPQueue k a
    q = case MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    forall k a. Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
    minViewWithKey MinPQueue k a
    q of
      Just (t :: (k, a)
    t@(k
    k, a
    a), MinPQueue k a
    q')
        | k -> a -> Bool
    p k
    k a
    a -> let ([(k, a)]
    kas, MinPQueue k a
    q'') = (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    forall k a.
    Ord k =>
    (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    spanWithKey k -> a -> Bool
    p MinPQueue k a
    q' in ((k, a)
    t (k, a) -> [(k, a)] -> [(k, a)]
    forall a. a -> [a] -> [a]
    : [(k, a)]
    kas, MinPQueue k a
    q'')
      Maybe ((k, a), MinPQueue k a)
    _         -> ([], MinPQueue k a
    q)

    -- | Equivalent to @'spanWithKey' (\ k a -> 'not' (p k a)) q@.
    breakWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    breakWithKey :: forall k a.
    Ord k =>
    (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    breakWithKey k -> a -> Bool
    p = (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    forall k a.
    Ord k =>
    (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
    spanWithKey (Bool -> Bool
    not (Bool -> Bool) -> (k -> a -> Bool) -> k -> a -> Bool
    forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
    .: k -> a -> Bool
    p)

    -- | \(O(n)\). Build a priority queue from a descending list of (key, value) pairs. /The precondition is not checked./
    fromDescList :: [(k, a)] -> MinPQueue k a
    {-# INLINE fromDescList #-}
    fromDescList :: forall k a. [(k, a)] -> MinPQueue k a
    fromDescList [(k, a)]
    xs = (MinPQueue k a -> (k, a) -> MinPQueue k a)
    -> MinPQueue k a -> [(k, a)] -> MinPQueue k a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    List.foldl' (\MinPQueue k a
    q (k
    k, a
    a) -> k -> a -> MinPQueue k a -> MinPQueue k a
    forall k a. k -> a -> MinPQueue k a -> MinPQueue k a
    insertMin' k
    k a
    a MinPQueue k a
    q) MinPQueue k a
    forall k a. MinPQueue k a
    empty [(k, a)]
    xs

    {-# INLINE keys #-}
    -- | \(O(n \log n)\). Return all keys of the queue in ascending order.
    keys :: Ord k => MinPQueue k a -> [k]
    keys :: forall k a. Ord k => MinPQueue k a -> [k]
    keys = ((k, a) -> k) -> [(k, a)] -> [k]
    forall a b. (a -> b) -> [a] -> [b]
    List.map (k, a) -> k
    forall a b. (a, b) -> a
    fst ([(k, a)] -> [k])
    -> (MinPQueue k a -> [(k, a)]) -> MinPQueue k a -> [k]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinPQueue k a -> [(k, a)]
    forall k a. Ord k => MinPQueue k a -> [(k, a)]
    toAscList

    {-# INLINE elems #-}
    -- | \(O(n \log n)\). Return all elements of the queue in ascending order by key.
    elems :: Ord k => MinPQueue k a -> [a]
    elems :: forall k a. Ord k => MinPQueue k a -> [a]
    elems = ((k, a) -> a) -> [(k, a)] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    List.map (k, a) -> a
    forall a b. (a, b) -> b
    snd ([(k, a)] -> [a])
    -> (MinPQueue k a -> [(k, a)]) -> MinPQueue k a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinPQueue k a -> [(k, a)]
    forall k a. Ord k => MinPQueue k a -> [(k, a)]
    toAscList

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

    {-# INLINE assocs #-}
    -- | \(O(n \log n)\). Equivalent to 'toAscList'.
    assocs :: Ord k => MinPQueue k a -> [(k, a)]
    assocs :: forall k a. Ord k => MinPQueue k a -> [(k, a)]
    assocs = MinPQueue k a -> [(k, a)]
    forall k a. Ord k => MinPQueue k a -> [(k, a)]
    toAscList

    {-# INLINE keysU #-}
    -- | \(O(n)\). Return all keys of the queue in no particular order.
    keysU :: MinPQueue k a -> [k]
    keysU :: forall k a. MinPQueue k a -> [k]
    keysU = ((k, a) -> k) -> [(k, a)] -> [k]
    forall a b. (a -> b) -> [a] -> [b]
    List.map (k, a) -> k
    forall a b. (a, b) -> a
    fst ([(k, a)] -> [k])
    -> (MinPQueue k a -> [(k, a)]) -> MinPQueue k a -> [k]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinPQueue k a -> [(k, a)]
    forall k a. MinPQueue k a -> [(k, a)]
    toListU

    {-# INLINE elemsU #-}
    -- | \(O(n)\). Return all elements of the queue in no particular order.
    elemsU :: MinPQueue k a -> [a]
    elemsU :: forall k a. MinPQueue k a -> [a]
    elemsU = ((k, a) -> a) -> [(k, a)] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    List.map (k, a) -> a
    forall a b. (a, b) -> b
    snd ([(k, a)] -> [a])
    -> (MinPQueue k a -> [(k, a)]) -> MinPQueue k a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinPQueue k a -> [(k, a)]
    forall k a. MinPQueue k a -> [(k, a)]
    toListU

    {-# INLINE assocsU #-}
    -- | \(O(n)\). Equivalent to 'toListU'.
    assocsU :: MinPQueue k a -> [(k, a)]
    assocsU :: forall k a. MinPQueue k a -> [(k, a)]
    assocsU = MinPQueue k a -> [(k, a)]
    forall k a. MinPQueue k a -> [(k, a)]
    toListU

    -- | \(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 -> MinPQueue k a -> b
    foldlU :: forall b a k. (b -> a -> b) -> b -> MinPQueue k a -> b
    foldlU b -> a -> b
    f = (b -> k -> a -> b) -> b -> MinPQueue k a -> b
    forall b k a. (b -> k -> a -> b) -> b -> MinPQueue k a -> b
    foldlWithKeyU ((a -> b) -> k -> a -> b
    forall a b. a -> b -> a
    const ((a -> b) -> k -> a -> b) -> (b -> a -> b) -> b -> k -> a -> b
    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 -> MinPQueue k a -> b
    foldlU' :: forall b a k. (b -> a -> b) -> b -> MinPQueue k a -> b
    foldlU' b -> a -> b
    f = (b -> k -> a -> b) -> b -> MinPQueue k a -> b
    forall b k a. (b -> k -> a -> b) -> b -> MinPQueue k a -> b
    foldlWithKeyU' ((a -> b) -> k -> a -> b
    forall a b. a -> b -> a
    const ((a -> b) -> k -> a -> b) -> (b -> a -> b) -> b -> k -> a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . b -> a -> b
    f)

    -- | \(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) -> MinPQueue k a -> f (MinPQueue k b)
    traverseU :: forall (f :: * -> *) a b k.
    Applicative f =>
    (a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
    traverseU = (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
    forall (f :: * -> *) k a b.
    Applicative f =>
    (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
    traverseWithKeyU ((k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b))
    -> ((a -> f b) -> k -> a -> f b)
    -> (a -> f b)
    -> MinPQueue k a
    -> f (MinPQueue k b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> f b) -> k -> a -> f b
    forall a b. a -> b -> a
    const