    {-# LANGUAGE CPP #-}

    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Data.PQueue.Max
    -- Copyright   :  (c) Louis Wasserman 2010
    -- License     :  BSD-style
    -- Maintainer  :  libraries@haskell.org
    -- Stability   :  experimental
    -- Portability :  portable
    --
    -- General purpose priority queue, supporting view-maximum operations.
    --
    -- An amortized running time is given for each operation, with /n/ referring
    -- to the length of the sequence and /k/ being the integral index used by
    -- some operations. These bounds hold even in a persistent (shared) setting.
    --
    -- This implementation is based on a binomial heap augmented with a global root.
    --
    -- This implementation does not guarantee stable behavior.
    --
    -- 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.Max (
      MaxQueue,
      -- * Basic operations
      empty,
      null,
      size,
      -- * Query operations
      findMax,
      getMax,
      deleteMax,
      deleteFindMax,
      delete,
      maxView,
      -- * Construction operations
      singleton,
      insert,
      union,
      unions,
      -- * Subsets
      -- ** Extracting subsets
      (!!),
      take,
      drop,
      splitAt,
      -- ** Predicates
      takeWhile,
      dropWhile,
      span,
      break,
      -- * Filter/Map
      filter,
      partition,
      mapMaybe,
      mapEither,
      -- * Fold\/Functor\/Traversable variations
      map,
      foldrAsc,
      foldlAsc,
      foldrDesc,
      foldlDesc,
      -- * List operations
      toList,
      toAscList,
      toDescList,
      fromList,
      fromAscList,
      fromDescList,
      -- * Unordered operations
      mapU,
      foldrU,
      foldlU,
      foldlU',
      foldMapU,
      elemsU,
      toListU,
      -- * Miscellaneous operations
      keysQueue,
      seqSpine) where

    import Control.DeepSeq (NFData(rnf))

    import Data.Maybe (fromMaybe)

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

    import Data.Foldable (foldl')

    import qualified Data.PQueue.Min as Min
    import qualified Data.PQueue.Prio.Max.Internals as Prio
    import Data.PQueue.Internals.Down (Down(..))

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

    #ifdef __GLASGOW_HASKELL__
    import GHC.Exts (build)
    import Text.Read (Lexeme(Ident), lexP, parens, prec,
      readPrec, readListPrec, readListPrecDefault)
    import Data.Data
    #else
    build :: ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
    build f = f (:) []
    #endif

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

    instance NFData a => NFData (MaxQueue a) where
      rnf :: MaxQueue a -> ()
    rnf (MaxQ MinQueue (Down a)
    q) = MinQueue (Down a) -> ()
    forall a. NFData a => a -> ()
    rnf MinQueue (Down a)
    q

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

    instance Read a => Read (MaxQueue a) where
    #ifdef __GLASGOW_HASKELL__
      readPrec :: ReadPrec (MaxQueue a)
    readPrec = ReadPrec (MaxQueue a) -> ReadPrec (MaxQueue a)
    forall a. ReadPrec a -> ReadPrec a
    parens (ReadPrec (MaxQueue a) -> ReadPrec (MaxQueue a))
    -> ReadPrec (MaxQueue a) -> ReadPrec (MaxQueue a)
    forall a b. (a -> b) -> a -> b
    $ Int -> ReadPrec (MaxQueue a) -> ReadPrec (MaxQueue a)
    forall a. Int -> ReadPrec a -> ReadPrec a
    prec Int
    10 (ReadPrec (MaxQueue a) -> ReadPrec (MaxQueue a))
    -> ReadPrec (MaxQueue a) -> ReadPrec (MaxQueue a)
    forall a b. (a -> b) -> a -> b
    $ do
        Ident "fromDescList" <- ReadPrec Lexeme
    lexP
        xs <- readPrec
        return (fromDescList xs)

      readListPrec :: ReadPrec [MaxQueue a]
    readListPrec = ReadPrec [MaxQueue a]
    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

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

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

    -- | \(O(1)\). The empty priority queue.
    empty :: MaxQueue a
    empty :: forall a. MaxQueue a
    empty = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ MinQueue (Down a)
    forall a. MinQueue a
    Min.empty

    -- | \(O(1)\). Is this the empty priority queue?
    null :: MaxQueue a -> Bool
    null :: forall a. MaxQueue a -> Bool
    null (MaxQ MinQueue (Down a)
    q) = MinQueue (Down a) -> Bool
    forall a. MinQueue a -> Bool
    Min.null MinQueue (Down a)
    q

    -- | \(O(1)\). The number of elements in the queue.
    size :: MaxQueue a -> Int
    size :: forall a. MaxQueue a -> Int
    size (MaxQ MinQueue (Down a)
    q) = MinQueue (Down a) -> Int
    forall a. MinQueue a -> Int
    Min.size MinQueue (Down a)
    q

    -- | \(O(1)\). Returns the maximum element of the queue. Throws an error on an empty queue.
    findMax :: MaxQueue a -> a
    findMax :: forall a. MaxQueue a -> a
    findMax = a -> Maybe a -> a
    forall a. a -> Maybe a -> a
    fromMaybe (String -> a
    forall a. HasCallStack => String -> a
    error String
    "Error: findMax called on empty queue") (Maybe a -> a) -> (MaxQueue a -> Maybe a) -> MaxQueue a -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> Maybe a
    forall a. MaxQueue a -> Maybe a
    getMax

    -- | \(O(1)\). The top (maximum) element of the queue, if there is one.
    getMax :: MaxQueue a -> Maybe a
    getMax :: forall a. MaxQueue a -> Maybe a
    getMax (MaxQ MinQueue (Down a)
    q) = Down a -> a
    forall a. Down a -> a
    unDown (Down a -> a) -> Maybe (Down a) -> Maybe a
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> MinQueue (Down a) -> Maybe (Down a)
    forall a. MinQueue a -> Maybe a
    Min.getMin MinQueue (Down a)
    q

    -- | \(O(\log n)\). Deletes the maximum element of the queue. Does nothing on an empty queue.
    deleteMax :: Ord a => MaxQueue a -> MaxQueue a
    deleteMax :: forall a. Ord a => MaxQueue a -> MaxQueue a
    deleteMax (MaxQ MinQueue (Down a)
    q) = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ (MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => MinQueue a -> MinQueue a
    Min.deleteMin MinQueue (Down a)
    q)

    -- | \(O(\log n)\). Extracts the maximum element of the queue. Throws an error on an empty queue.
    deleteFindMax :: Ord a => MaxQueue a -> (a, MaxQueue a)
    deleteFindMax :: forall a. Ord a => MaxQueue a -> (a, MaxQueue a)
    deleteFindMax = (a, MaxQueue a) -> Maybe (a, MaxQueue a) -> (a, MaxQueue a)
    forall a. a -> Maybe a -> a
    fromMaybe (String -> (a, MaxQueue a)
    forall a. HasCallStack => String -> a
    error String
    "Error: deleteFindMax called on empty queue") (Maybe (a, MaxQueue a) -> (a, MaxQueue a))
    -> (MaxQueue a -> Maybe (a, MaxQueue a))
    -> MaxQueue a
    -> (a, MaxQueue a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> Maybe (a, MaxQueue a)
    forall a. Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
    maxView

    -- | \(O(\log n)\). Extract the top (maximum) element of the sequence, if there is one.
    maxView :: Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
    maxView :: forall a. Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
    maxView (MaxQ MinQueue (Down a)
    q) = case MinQueue (Down a) -> Maybe (Down a, MinQueue (Down a))
    forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
    Min.minView MinQueue (Down a)
    q of
      Maybe (Down a, MinQueue (Down a))
    Nothing -> Maybe (a, MaxQueue a)
    forall a. Maybe a
    Nothing
      Just (Down a
    x, MinQueue (Down a)
    q')
              -> (a, MaxQueue a) -> Maybe (a, MaxQueue a)
    forall a. a -> Maybe a
    Just (a
    x, MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ MinQueue (Down a)
    q')

    -- | \(O(\log n)\). Delete the top (maximum) element of the sequence, if there is one.
    delete :: Ord a => MaxQueue a -> Maybe (MaxQueue a)
    delete :: forall a. Ord a => MaxQueue a -> Maybe (MaxQueue a)
    delete = ((a, MaxQueue a) -> MaxQueue a)
    -> Maybe (a, MaxQueue a) -> Maybe (MaxQueue a)
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (a, MaxQueue a) -> MaxQueue a
    forall a b. (a, b) -> b
    snd (Maybe (a, MaxQueue a) -> Maybe (MaxQueue a))
    -> (MaxQueue a -> Maybe (a, MaxQueue a))
    -> MaxQueue a
    -> Maybe (MaxQueue a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> Maybe (a, MaxQueue a)
    forall a. Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
    maxView

    -- | \(O(1)\). Construct a priority queue with a single element.
    singleton :: a -> MaxQueue a
    singleton :: forall a. a -> MaxQueue a
    singleton = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ (MinQueue (Down a) -> MaxQueue a)
    -> (a -> MinQueue (Down a)) -> a -> MaxQueue a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> MinQueue (Down a)
    forall a. a -> MinQueue a
    Min.singleton (Down a -> MinQueue (Down a))
    -> (a -> Down a) -> a -> MinQueue (Down a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Down a
    forall a. a -> Down a
    Down

    -- | \(O(1)\). Insert an element into the priority queue.
    insert :: Ord a => a -> MaxQueue a -> MaxQueue a
    a
    x insert :: forall a. Ord a => a -> MaxQueue a -> MaxQueue a
    `insert` MaxQ MinQueue (Down a)
    q = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ (a -> Down a
    forall a. a -> Down a
    Down a
    x Down a -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => a -> MinQueue a -> MinQueue a
    `Min.insert` MinQueue (Down a)
    q)

    -- | \(O(\log min(n_1,n_2))\). Take the union of two priority queues.
    union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
    MaxQ MinQueue (Down a)
    q1 union :: forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
    `union` MaxQ MinQueue (Down a)
    q2 = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ (MinQueue (Down a)
    q1 MinQueue (Down a) -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => MinQueue a -> MinQueue a -> MinQueue a
    `Min.union` MinQueue (Down a)
    q2)

    -- | Takes the union of a list of priority queues. Equivalent to @'foldl' 'union' 'empty'@.
    unions :: Ord a => [MaxQueue a] -> MaxQueue a
    unions :: forall a. Ord a => [MaxQueue a] -> MaxQueue a
    unions [MaxQueue a]
    qs = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ ([MinQueue (Down a)] -> MinQueue (Down a)
    forall a. Ord a => [MinQueue a] -> MinQueue a
    Min.unions [MinQueue (Down a)
    q | MaxQ MinQueue (Down a)
    q <- [MaxQueue a]
    qs])

    -- | \(O(k \log n)\)/. Returns the @(k+1)@th largest element of the queue.
    (!!) :: Ord a => MaxQueue a -> Int -> a
    MaxQ MinQueue (Down a)
    q !! :: forall a. Ord a => MaxQueue a -> Int -> a
    !! Int
    n = Down a -> a
    forall a. Down a -> a
    unDown (MinQueue (Down a) -> Int -> Down a
    forall a. Ord a => MinQueue a -> Int -> a
    (Min.!!) MinQueue (Down a)
    q Int
    n)

    {-# INLINE take #-}
    -- | \(O(k \log n)\)/. Returns the list of the @k@ largest elements of the queue, in descending order, or
    -- all elements of the queue, if @k >= n@.
    take :: Ord a => Int -> MaxQueue a -> [a]
    take :: forall a. Ord a => Int -> MaxQueue a -> [a]
    take Int
    k (MaxQ MinQueue (Down a)
    q) = [a
    a | Down a
    a <- Int -> MinQueue (Down a) -> [Down a]
    forall a. Ord a => Int -> MinQueue a -> [a]
    Min.take Int
    k MinQueue (Down a)
    q]

    -- | \(O(k \log n)\)/. Returns the queue with the @k@ largest elements deleted, or the empty queue if @k >= n@.
    drop :: Ord a => Int -> MaxQueue a -> MaxQueue a
    drop :: forall a. Ord a => Int -> MaxQueue a -> MaxQueue a
    drop Int
    k (MaxQ MinQueue (Down a)
    q) = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ (Int -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => Int -> MinQueue a -> MinQueue a
    Min.drop Int
    k MinQueue (Down a)
    q)

    -- | \(O(k \log n)\)/. Equivalent to @(take k queue, drop k queue)@.
    splitAt :: Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)
    splitAt :: forall a. Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)
    splitAt Int
    k (MaxQ MinQueue (Down a)
    q) = ((Down a -> a) -> [Down a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Down a -> a
    forall a. Down a -> a
    unDown [Down a]
    xs, MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ MinQueue (Down a)
    q') where
      ([Down a]
    xs, MinQueue (Down a)
    q') = Int -> MinQueue (Down a) -> ([Down a], MinQueue (Down a))
    forall a. Ord a => Int -> MinQueue a -> ([a], MinQueue a)
    Min.splitAt Int
    k MinQueue (Down a)
    q

    -- | 'takeWhile', applied to a predicate @p@ and a queue @queue@, returns the
    -- longest prefix (possibly empty) of @queue@ of elements that satisfy @p@.
    takeWhile :: Ord a => (a -> Bool) -> MaxQueue a -> [a]
    takeWhile :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> [a]
    takeWhile a -> Bool
    p (MaxQ MinQueue (Down a)
    q) = (Down a -> a) -> [Down a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Down a -> a
    forall a. Down a -> a
    unDown ((Down a -> Bool) -> MinQueue (Down a) -> [Down a]
    forall a. Ord a => (a -> Bool) -> MinQueue a -> [a]
    Min.takeWhile (a -> Bool
    p (a -> Bool) -> (Down a -> a) -> Down a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> a
    forall a. Down a -> a
    unDown) MinQueue (Down a)
    q)

    -- | 'dropWhile' @p queue@ returns the queue remaining after 'takeWhile' @p queue@.
    dropWhile :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
    dropWhile :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
    dropWhile a -> Bool
    p (MaxQ MinQueue (Down a)
    q) = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ ((Down a -> Bool) -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
    Min.dropWhile (a -> Bool
    p (a -> Bool) -> (Down a -> a) -> Down a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> a
    forall a. Down a -> a
    unDown) MinQueue (Down a)
    q)

    -- | 'span', applied to a predicate @p@ and a queue @queue@, returns a tuple where
    -- first element is longest prefix (possibly empty) of @queue@ of elements that
    -- satisfy @p@ and second element is the remainder of the queue.
    --
    span :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
    span :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
    span a -> Bool
    p (MaxQ MinQueue (Down a)
    q) = ((Down a -> a) -> [Down a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Down a -> a
    forall a. Down a -> a
    unDown [Down a]
    xs, MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ MinQueue (Down a)
    q') where
      ([Down a]
    xs, MinQueue (Down a)
    q') = (Down a -> Bool)
    -> MinQueue (Down a) -> ([Down a], MinQueue (Down a))
    forall a. Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
    Min.span (a -> Bool
    p (a -> Bool) -> (Down a -> a) -> Down a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> a
    forall a. Down a -> a
    unDown) MinQueue (Down a)
    q

    -- | 'break', applied to a predicate @p@ and a queue @queue@, returns a tuple where
    -- first element is longest prefix (possibly empty) of @queue@ of elements that
    -- /do not satisfy/ @p@ and second element is the remainder of the queue.
    break :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
    break :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
    break a -> Bool
    p = (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
    forall a. Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
    span (Bool -> Bool
    not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Bool
    p)

    -- | \(O(n)\). Returns a queue of those elements which satisfy the predicate.
    filter :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
    filter :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
    filter a -> Bool
    p (MaxQ MinQueue (Down a)
    q) = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ ((Down a -> Bool) -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
    Min.filter (a -> Bool
    p (a -> Bool) -> (Down a -> a) -> Down a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> a
    forall a. Down a -> a
    unDown) MinQueue (Down a)
    q)

    -- | \(O(n)\). Returns a pair of queues, where the left queue contains those elements that satisfy the predicate,
    -- and the right queue contains those that do not.
    partition :: Ord a => (a -> Bool) -> MaxQueue a -> (MaxQueue a, MaxQueue a)
    partition :: forall a.
    Ord a =>
    (a -> Bool) -> MaxQueue a -> (MaxQueue a, MaxQueue a)
    partition a -> Bool
    p (MaxQ MinQueue (Down a)
    q) = (MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ MinQueue (Down a)
    q0, MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ MinQueue (Down a)
    q1)
      where  (MinQueue (Down a)
    q0, MinQueue (Down a)
    q1) = (Down a -> Bool)
    -> MinQueue (Down a) -> (MinQueue (Down a), MinQueue (Down a))
    forall a.
    Ord a =>
    (a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)
    Min.partition (a -> Bool
    p (a -> Bool) -> (Down a -> a) -> Down a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> a
    forall a. Down a -> a
    unDown) MinQueue (Down a)
    q

    -- | \(O(n)\). Maps a function over the elements of the queue, and collects the 'Just' values.
    mapMaybe :: Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue b
    mapMaybe :: forall b a. Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue b
    mapMaybe a -> Maybe b
    f (MaxQ MinQueue (Down a)
    q) = MinQueue (Down b) -> MaxQueue b
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ ((Down a -> Maybe (Down b))
    -> MinQueue (Down a) -> MinQueue (Down b)
    forall b a. Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b
    Min.mapMaybe (\(Down a
    x) -> b -> Down b
    forall a. a -> Down a
    Down (b -> Down b) -> Maybe b -> Maybe (Down b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> a -> Maybe b
    f a
    x) MinQueue (Down a)
    q)

    -- | \(O(n)\). Maps a function over the elements of the queue, and separates the 'Left' and 'Right' values.
    mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MaxQueue a -> (MaxQueue b, MaxQueue c)
    mapEither :: forall b c a.
    (Ord b, Ord c) =>
    (a -> Either b c) -> MaxQueue a -> (MaxQueue b, MaxQueue c)
    mapEither a -> Either b c
    f (MaxQ MinQueue (Down a)
    q) = (MinQueue (Down b) -> MaxQueue b
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ MinQueue (Down b)
    q0, MinQueue (Down c) -> MaxQueue c
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ MinQueue (Down c)
    q1)
      where  (MinQueue (Down b)
    q0, MinQueue (Down c)
    q1) = (Down a -> Either (Down b) (Down c))
    -> MinQueue (Down a) -> (MinQueue (Down b), MinQueue (Down c))
    forall b c a.
    (Ord b, Ord c) =>
    (a -> Either b c) -> MinQueue a -> (MinQueue b, MinQueue c)
    Min.mapEither ((b -> Either (Down b) (Down c))
    -> (c -> Either (Down b) (Down c))
    -> Either b c
    -> Either (Down b) (Down c)
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either (Down b -> Either (Down b) (Down c)
    forall a b. a -> Either a b
    Left (Down b -> Either (Down b) (Down c))
    -> (b -> Down b) -> b -> Either (Down b) (Down c)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . b -> Down b
    forall a. a -> Down a
    Down) (Down c -> Either (Down b) (Down c)
    forall a b. b -> Either a b
    Right (Down c -> Either (Down b) (Down c))
    -> (c -> Down c) -> c -> Either (Down b) (Down c)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . c -> Down c
    forall a. a -> Down a
    Down) (Either b c -> Either (Down b) (Down c))
    -> (Down a -> Either b c) -> Down a -> Either (Down b) (Down c)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Either b c
    f (a -> Either b c) -> (Down a -> a) -> Down a -> Either b c
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> a
    forall a. Down a -> a
    unDown) MinQueue (Down a)
    q

    -- | \(O(n)\). Creates a new priority queue containing the images of the elements of this queue.
    -- Equivalent to @'fromList' . 'Data.List.map' f . toList@.
    map :: Ord b => (a -> b) -> MaxQueue a -> MaxQueue b
    map :: forall b a. Ord b => (a -> b) -> MaxQueue a -> MaxQueue b
    map a -> b
    f (MaxQ MinQueue (Down a)
    q) = MinQueue (Down b) -> MaxQueue b
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ ((Down a -> Down b) -> MinQueue (Down a) -> MinQueue (Down b)
    forall b a. Ord b => (a -> b) -> MinQueue a -> MinQueue b
    Min.map (\(Down a
    x) -> b -> Down b
    forall a. a -> Down a
    Down (a -> b
    f a
    x)) MinQueue (Down a)
    q)

    -- | \(O(n)\). Assumes that the function it is given is monotonic, and applies this function to every element of the priority queue.
    -- /Does not check the precondition/.
    mapU :: (a -> b) -> MaxQueue a -> MaxQueue b
    mapU :: forall a b. (a -> b) -> MaxQueue a -> MaxQueue b
    mapU a -> b
    f (MaxQ MinQueue (Down a)
    q) = MinQueue (Down b) -> MaxQueue b
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ ((Down a -> Down b) -> MinQueue (Down a) -> MinQueue (Down b)
    forall a b. (a -> b) -> MinQueue a -> MinQueue b
    Min.mapU (\(Down a
    a) -> b -> Down b
    forall a. a -> Down a
    Down (a -> b
    f a
    a)) MinQueue (Down a)
    q)

    -- | \(O(n)\). Unordered right fold on a priority queue.
    foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b
    foldrU :: forall a b. (a -> b -> b) -> b -> MaxQueue a -> b
    foldrU a -> b -> b
    f b
    z (MaxQ MinQueue (Down a)
    q) = (Down a -> b -> b) -> b -> MinQueue (Down a) -> b
    forall a b. (a -> b -> b) -> b -> MinQueue a -> b
    Min.foldrU ((b -> Down a -> b) -> Down a -> b -> b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip ((a -> b -> b) -> b -> Down a -> b
    forall a b. (a -> b -> b) -> b -> Down a -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr a -> b -> b
    f)) b
    z MinQueue (Down a)
    q

    -- | \(O(n)\). Unordered monoidal fold on a priority queue.
    --
    -- @since 1.4.2
    foldMapU :: Monoid m => (a -> m) -> MaxQueue a -> m
    foldMapU :: forall m a. Monoid m => (a -> m) -> MaxQueue a -> m
    foldMapU a -> m
    f (MaxQ MinQueue (Down a)
    q) = (Down a -> m) -> MinQueue (Down a) -> m
    forall m a. Monoid m => (a -> m) -> MinQueue a -> m
    Min.foldMapU (a -> m
    f (a -> m) -> (Down a -> a) -> Down a -> m
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> a
    forall a. Down a -> a
    unDown) MinQueue (Down a)
    q

    -- | \(O(n)\). Unordered left fold on a priority queue. This is rarely
    -- what you want; 'foldrU' and 'foldlU'' are more likely to perform
    -- well.
    foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b
    foldlU :: forall b a. (b -> a -> b) -> b -> MaxQueue a -> b
    foldlU b -> a -> b
    f b
    z (MaxQ MinQueue (Down a)
    q) = (b -> Down a -> b) -> b -> MinQueue (Down a) -> b
    forall b a. (b -> a -> b) -> b -> MinQueue a -> b
    Min.foldlU ((b -> a -> b) -> b -> Down a -> b
    forall b a. (b -> a -> b) -> b -> Down a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl b -> a -> b
    f) b
    z MinQueue (Down a)
    q

    -- | \(O(n)\). Unordered strict left fold on a priority queue.
    --
    -- @since 1.4.2
    foldlU' :: (b -> a -> b) -> b -> MaxQueue a -> b
    foldlU' :: forall b a. (b -> a -> b) -> b -> MaxQueue a -> b
    foldlU' b -> a -> b
    f b
    z (MaxQ MinQueue (Down a)
    q) = (b -> Down a -> b) -> b -> MinQueue (Down a) -> b
    forall b a. (b -> a -> b) -> b -> MinQueue a -> b
    Min.foldlU' ((b -> a -> b) -> b -> Down a -> b
    forall b a. (b -> a -> b) -> b -> Down a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' b -> a -> b
    f) b
    z MinQueue (Down a)
    q

    {-# INLINE elemsU #-}
    -- | Equivalent to 'toListU'.
    elemsU :: MaxQueue a -> [a]
    elemsU :: forall a. MaxQueue a -> [a]
    elemsU = MaxQueue a -> [a]
    forall a. MaxQueue a -> [a]
    toListU

    {-# INLINE toListU #-}
    -- | \(O(n)\). Returns a list of the elements of the priority queue, in no particular order.
    toListU :: MaxQueue a -> [a]
    toListU :: forall a. MaxQueue a -> [a]
    toListU (MaxQ MinQueue (Down a)
    q) = (Down a -> a) -> [Down a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Down a -> a
    forall a. Down a -> a
    unDown (MinQueue (Down a) -> [Down a]
    forall a. MinQueue a -> [a]
    Min.toListU MinQueue (Down a)
    q)

    -- | \(O(n \log n)\). Performs a right-fold on the elements of a priority queue in ascending order.
    -- @'foldrAsc' f z q == 'foldlDesc' (flip f) z q@.
    foldrAsc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
    foldrAsc :: forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
    foldrAsc = (b -> a -> b) -> b -> MaxQueue a -> b
    forall a b. Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
    foldlDesc ((b -> a -> b) -> b -> MaxQueue a -> b)
    -> ((a -> b -> b) -> b -> a -> b)
    -> (a -> b -> b)
    -> b
    -> MaxQueue a
    -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> b -> b) -> b -> a -> b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip

    -- | \(O(n \log n)\). Performs a left-fold on the elements of a priority queue in descending order.
    -- @'foldlAsc' f z q == 'foldrDesc' (flip f) z q@.
    foldlAsc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
    foldlAsc :: forall a b. Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
    foldlAsc = (a -> b -> b) -> b -> MaxQueue a -> b
    forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
    foldrDesc ((a -> b -> b) -> b -> MaxQueue a -> b)
    -> ((b -> a -> b) -> a -> b -> b)
    -> (b -> a -> b)
    -> b
    -> MaxQueue a
    -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> a -> b) -> a -> b -> b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip

    -- | \(O(n \log n)\). Performs a right-fold on the elements of a priority queue in descending order.
    foldrDesc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
    foldrDesc :: forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
    foldrDesc a -> b -> b
    f b
    z (MaxQ MinQueue (Down a)
    q) = (Down a -> b -> b) -> b -> MinQueue (Down a) -> b
    forall a b. Ord a => (a -> b -> b) -> b -> MinQueue a -> b
    Min.foldrAsc ((b -> Down a -> b) -> Down a -> b -> b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip ((a -> b -> b) -> b -> Down a -> b
    forall a b. (a -> b -> b) -> b -> Down a -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr a -> b -> b
    f)) b
    z MinQueue (Down a)
    q

    -- | \(O(n \log n)\). Performs a left-fold on the elements of a priority queue in descending order.
    foldlDesc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
    foldlDesc :: forall a b. Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
    foldlDesc b -> a -> b
    f b
    z (MaxQ MinQueue (Down a)
    q) = (b -> Down a -> b) -> b -> MinQueue (Down a) -> b
    forall a b. Ord a => (b -> a -> b) -> b -> MinQueue a -> b
    Min.foldlAsc ((b -> a -> b) -> b -> Down a -> b
    forall b a. (b -> a -> b) -> b -> Down a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl b -> a -> b
    f) b
    z MinQueue (Down a)
    q

    {-# INLINE toAscList #-}
    -- | \(O(n \log n)\). Extracts the elements of the priority queue in ascending order.
    toAscList :: Ord a => MaxQueue a -> [a]
    toAscList :: forall a. Ord a => MaxQueue a -> [a]
    toAscList MaxQueue a
    q = (forall b. (a -> b -> b) -> b -> b) -> [a]
    forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
    build (\a -> b -> b
    c b
    nil -> (a -> b -> b) -> b -> MaxQueue a -> b
    forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
    foldrAsc a -> b -> b
    c b
    nil MaxQueue a
    q)
    -- I can see no particular reason this does not simply forward to Min.toDescList. (lsp, 2016)

    {-# INLINE toDescList #-}
    -- | \(O(n \log n)\). Extracts the elements of the priority queue in descending order.
    toDescList :: Ord a => MaxQueue a -> [a]
    toDescList :: forall a. Ord a => MaxQueue a -> [a]
    toDescList MaxQueue a
    q = (forall b. (a -> b -> b) -> b -> b) -> [a]
    forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
    build (\a -> b -> b
    c b
    nil -> (a -> b -> b) -> b -> MaxQueue a -> b
    forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
    foldrDesc a -> b -> b
    c b
    nil MaxQueue a
    q)
    -- I can see no particular reason this does not simply forward to Min.toAscList. (lsp, 2016)

    {-# INLINE toList #-}
    -- | \(O(n \log n)\). Returns the elements of the priority queue in ascending order. Equivalent to 'toDescList'.
    --
    -- If the order of the elements is irrelevant, consider using 'toListU'.
    toList :: Ord a => MaxQueue a -> [a]
    toList :: forall a. Ord a => MaxQueue a -> [a]
    toList (MaxQ MinQueue (Down a)
    q) = (Down a -> a) -> [Down a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Down a -> a
    forall a. Down a -> a
    unDown (MinQueue (Down a) -> [Down a]
    forall a. Ord a => MinQueue a -> [a]
    Min.toList MinQueue (Down a)
    q)

    {-# INLINE fromAscList #-}
    -- | \(O(n)\). Constructs a priority queue from an ascending list. /Warning/: Does not check the precondition.
    fromAscList :: [a] -> MaxQueue a
    fromAscList :: forall a. [a] -> MaxQueue a
    fromAscList = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ (MinQueue (Down a) -> MaxQueue a)
    -> ([a] -> MinQueue (Down a)) -> [a] -> MaxQueue a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Down a] -> MinQueue (Down a)
    forall a. [a] -> MinQueue a
    Min.fromDescList ([Down a] -> MinQueue (Down a))
    -> ([a] -> [Down a]) -> [a] -> MinQueue (Down a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Down a) -> [a] -> [Down a]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Down a
    forall a. a -> Down a
    Down

    {-# INLINE fromDescList #-}
    -- | \(O(n)\). Constructs a priority queue from a descending list. /Warning/: Does not check the precondition.
    fromDescList :: [a] -> MaxQueue a
    fromDescList :: forall a. [a] -> MaxQueue a
    fromDescList = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ (MinQueue (Down a) -> MaxQueue a)
    -> ([a] -> MinQueue (Down a)) -> [a] -> MaxQueue a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Down a] -> MinQueue (Down a)
    forall a. [a] -> MinQueue a
    Min.fromAscList ([Down a] -> MinQueue (Down a))
    -> ([a] -> [Down a]) -> [a] -> MinQueue (Down a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Down a) -> [a] -> [Down a]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Down a
    forall a. a -> Down a
    Down

    {-# INLINE fromList #-}
    -- | \(O(n \log n)\). Constructs a priority queue from an unordered list.
    fromList :: Ord a => [a] -> MaxQueue a
    fromList :: forall a. Ord a => [a] -> MaxQueue a
    fromList = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ (MinQueue (Down a) -> MaxQueue a)
    -> ([a] -> MinQueue (Down a)) -> [a] -> MaxQueue a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Down a] -> MinQueue (Down a)
    forall a. Ord a => [a] -> MinQueue a
    Min.fromList ([Down a] -> MinQueue (Down a))
    -> ([a] -> [Down a]) -> [a] -> MinQueue (Down a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Down a) -> [a] -> [Down a]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Down a
    forall a. a -> Down a
    Down

    -- | \(O(n)\). Constructs a priority queue from the keys of a 'Prio.MaxPQueue'.
    keysQueue :: Prio.MaxPQueue k a -> MaxQueue k
    keysQueue :: forall k a. MaxPQueue k a -> MaxQueue k
    keysQueue (Prio.MaxPQ MinPQueue (Down k) a
    q) = MinQueue (Down k) -> MaxQueue k
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQ (MinPQueue (Down k) a -> MinQueue (Down k)
    forall k a. MinPQueue k a -> MinQueue k
    Min.keysQueue MinPQueue (Down k) a
    q)

    -- | \(O(\log n)\). @seqSpine q r@ forces the spine of @q@ and returns @r@.
    --
    -- Note: The spine of a 'MaxQueue' is stored somewhat lazily. In earlier
    -- versions of this package, some operations could produce chains of thunks
    -- along the spine, occasionally necessitating manual forcing. Now, all
    -- operations are careful to force enough to avoid this problem.
    {-# DEPRECATED seqSpine "This function is no longer necessary or useful." #-}
    seqSpine :: MaxQueue a -> b -> b
    seqSpine :: forall a b. MaxQueue a -> b -> b
    seqSpine (MaxQ MinQueue (Down a)
    q) = MinQueue (Down a) -> b -> b
    forall a b. MinQueue a -> b -> b
    Min.seqSpine MinQueue (Down a)
    q