    {-# LANGUAGE CPP #-}

    -----------------------------------------------------------------------------
    -- |
    -- Module      :  BinomialQueue.Max
    -- Copyright   :  (c) Louis Wasserman 2010
    -- License     :  BSD-style
    -- Maintainer  :  libraries@haskell.org
    -- Stability   :  experimental
    -- Portability :  portable
    --
    -- General purpose priority queue. Unlike the queues in "Data.PQueue.Max",
    -- these are /not/ augmented with a global root or their size, so 'getMax'
    -- and 'size' take logarithmic, rather than constant, time. When those
    -- operations are not (often) needed, these queues are generally faster than
    -- those in "Data.PQueue.Max".
    --
    -- 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.
    --
    -- 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 BinomialQueue.Max (
      MaxQueue,
      -- * Basic operations
      empty,
      null,
      size,
      -- * Query operations
      findMax,
      getMax,
      deleteMax,
      deleteFindMax,
      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
      foldrU,
      foldlU,
      foldlU',
      foldMapU,
      elemsU,
      toListU,
      -- * Miscellaneous operations
    --  keysQueue,  -- We want bare Prio queues for this.
      seqSpine
      ) where

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

    import Data.Foldable (foldl')
    import Data.Maybe (fromMaybe)
    import Data.Bifunctor (bimap)

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

    import qualified Data.List as List

    import qualified BinomialQueue.Min as MinQ
    import Data.PQueue.Internals.Down

    #ifdef __GLASGOW_HASKELL__
    import GHC.Exts (build)
    #else
    build :: ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
    build f = f (:) []
    #endif

    newtype MaxQueue a = MaxQueue { forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue :: MinQ.MinQueue (Down a) }

    -- | \(O(\log n)\). Returns the minimum element. Throws an error on an empty queue.
    findMax :: Ord a => MaxQueue a -> a
    findMax :: forall a. Ord a => MaxQueue a -> a
    findMax = a -> Maybe a -> a
    forall a. a -> Maybe a -> a
    fromMaybe ([Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "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. Ord a => MaxQueue a -> Maybe a
    getMax

    -- | \(O(1)\). The top (maximum) element of the queue, if there is one.
    getMax :: Ord a => MaxQueue a -> Maybe a
    getMax :: forall a. Ord a => MaxQueue a -> Maybe a
    getMax (MaxQueue 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. Ord a => MinQueue a -> Maybe a
    MinQ.getMin MinQueue (Down a)
    q

    -- | \(O(\log n)\). Deletes the maximum element. If the queue is empty, does nothing.
    deleteMax :: Ord a => MaxQueue a -> MaxQueue a
    deleteMax :: forall a. Ord a => MaxQueue a -> MaxQueue a
    deleteMax = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (MinQueue (Down a) -> MaxQueue a)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> MaxQueue a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => MinQueue a -> MinQueue a
    MinQ.deleteMin (MinQueue (Down a) -> MinQueue (Down a))
    -> (MaxQueue a -> MinQueue (Down a))
    -> MaxQueue a
    -> MinQueue (Down a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    -- | \(O(\log n)\). Extracts the maximum element. 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 ([Char] -> (a, MaxQueue a)
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "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 (MaxQueue MinQueue (Down a)
    q) = case MinQueue (Down a) -> Maybe (Down a, MinQueue (Down a))
    forall a. Ord a => MinQueue a -> Maybe (a, MinQueue a)
    MinQ.minView MinQueue (Down a)
    q of
      Just (Down a
    a, MinQueue (Down a)
    q') -> (a, MaxQueue a) -> Maybe (a, MaxQueue a)
    forall a. a -> Maybe a
    Just (a
    a, MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue MinQueue (Down a)
    q')
      Maybe (Down a, MinQueue (Down a))
    Nothing -> Maybe (a, MaxQueue a)
    forall a. Maybe a
    Nothing

    -- | \(O(k \log n)\)/. Index (subscript) operator, starting from 0. @queue !! k@ returns the @(k+1)@th largest
    -- element in the queue. Equivalent to @toDescList queue !! k@.
    (!!) :: Ord a => MaxQueue a -> Int -> a
    MaxQueue a
    q !! :: forall a. Ord a => MaxQueue a -> Int -> a
    !! Int
    n  | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= MaxQueue a -> Int
    forall a. MaxQueue a -> Int
    size MaxQueue a
    q
        = [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "BinomialQueue.Max.!!: index too large"
    MaxQueue a
    q !! Int
    n = MaxQueue a -> [a]
    forall a. Ord a => MaxQueue a -> [a]
    toDescList MaxQueue a
    q [a] -> Int -> a
    forall a. HasCallStack => [a] -> Int -> a
    List.!! Int
    n

    {-# INLINE takeWhile #-}
    -- | '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 = (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] -> [a]) -> (MaxQueue a -> [Down a]) -> MaxQueue a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Down a -> Bool) -> MinQueue (Down a) -> [Down a]
    forall a. Ord a => (a -> Bool) -> MinQueue a -> [a]
    MinQ.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) -> [Down a])
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> [Down a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    -- | '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 = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (MinQueue (Down a) -> MaxQueue a)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> MaxQueue a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Down a -> Bool) -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
    MinQ.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) -> MinQueue (Down a))
    -> (MaxQueue a -> MinQueue (Down a))
    -> MaxQueue a
    -> MinQueue (Down a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    -- | '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 (MaxQueue MinQueue (Down a)
    queue)
      | ([Down a]
    front, MinQueue (Down a)
    rear) <- (Down a -> Bool)
    -> MinQueue (Down a) -> ([Down a], MinQueue (Down a))
    forall a. Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
    MinQ.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)
    queue
      = ((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]
    front, MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue MinQueue (Down a)
    rear)

    -- | '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)

    {-# INLINE take #-}
    -- | \(O(k \log n)\)/. 'take' @k@, applied to a queue @queue@, returns a list of the greatest @k@ elements of @queue@,
    -- or all elements of @queue@ itself if @k >= 'size' queue@.
    take :: Ord a => Int -> MaxQueue a -> [a]
    take :: forall a. Ord a => Int -> MaxQueue a -> [a]
    take Int
    n = Int -> [a] -> [a]
    forall a. Int -> [a] -> [a]
    List.take Int
    n ([a] -> [a]) -> (MaxQueue a -> [a]) -> MaxQueue a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> [a]
    forall a. Ord a => MaxQueue a -> [a]
    toDescList

    -- | \(O(k \log n)\)/. 'drop' @k@, applied to a queue @queue@, returns @queue@ with the greatest @k@ elements deleted,
    -- or an empty queue if @k >= size 'queue'@.
    drop :: Ord a => Int -> MaxQueue a -> MaxQueue a
    drop :: forall a. Ord a => Int -> MaxQueue a -> MaxQueue a
    drop Int
    n (MaxQueue MinQueue (Down a)
    queue) = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (Int -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => Int -> MinQueue a -> MinQueue a
    MinQ.drop Int
    n MinQueue (Down a)
    queue)

    -- | \(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
    n (MaxQueue MinQueue (Down a)
    queue)
      | ([Down a]
    l, MinQueue (Down a)
    r) <- Int -> MinQueue (Down a) -> ([Down a], MinQueue (Down a))
    forall a. Ord a => Int -> MinQueue a -> ([a], MinQueue a)
    MinQ.splitAt Int
    n MinQueue (Down a)
    queue
      = ((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]
    l, MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue MinQueue (Down a)
    r)

    -- | \(O(n)\). Returns the queue with all elements not satisfying @p@ removed.
    filter :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
    filter :: forall a. Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
    filter a -> Bool
    p = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (MinQueue (Down a) -> MaxQueue a)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> MaxQueue a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Down a -> Bool) -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
    MinQ.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) -> MinQueue (Down a))
    -> (MaxQueue a -> MinQueue (Down a))
    -> MaxQueue a
    -> MinQueue (Down a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    -- | \(O(n)\). Returns a pair where the first queue contains all elements satisfying @p@, and the second queue
    -- contains all elements not satisfying @p@.
    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 = MinQueue (Down a) -> (MaxQueue a, MaxQueue a)
    go (MinQueue (Down a) -> (MaxQueue a, MaxQueue a))
    -> (MaxQueue a -> MinQueue (Down a))
    -> MaxQueue a
    -> (MaxQueue a, MaxQueue a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue
      where
        go :: MinQueue (Down a) -> (MaxQueue a, MaxQueue a)
    go MinQueue (Down a)
    queue
          | (MinQueue (Down a)
    l, MinQueue (Down a)
    r) <- (Down a -> Bool)
    -> MinQueue (Down a) -> (MinQueue (Down a), MinQueue (Down a))
    forall a.
    Ord a =>
    (a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)
    MinQ.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)
    queue
          = (MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue MinQueue (Down a)
    l, MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue MinQueue (Down a)
    r)

    -- | \(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 = MinQueue (Down b) -> MaxQueue b
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (MinQueue (Down b) -> MaxQueue b)
    -> (MaxQueue a -> MinQueue (Down b)) -> MaxQueue a -> MaxQueue b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Down a -> Down b) -> MinQueue (Down a) -> MinQueue (Down b)
    forall b a. Ord b => (a -> b) -> MinQueue a -> MinQueue b
    MinQ.map ((a -> b) -> Down a -> Down b
    forall a b. (a -> b) -> Down a -> Down b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    f) (MinQueue (Down a) -> MinQueue (Down b))
    -> (MaxQueue a -> MinQueue (Down a))
    -> MaxQueue a
    -> MinQueue (Down b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    {-# INLINE toList #-}
    -- | \(O(n \log n)\). Returns the elements of the priority queue in descending 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 = (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] -> [a]) -> (MaxQueue a -> [Down a]) -> MaxQueue a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinQueue (Down a) -> [Down a]
    forall a. Ord a => MinQueue a -> [a]
    MinQ.toAscList (MinQueue (Down a) -> [Down a])
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> [Down a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    toAscList :: Ord a => MaxQueue a -> [a]
    toAscList :: forall a. Ord a => MaxQueue a -> [a]
    toAscList = (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] -> [a]) -> (MaxQueue a -> [Down a]) -> MaxQueue a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinQueue (Down a) -> [Down a]
    forall a. Ord a => MinQueue a -> [a]
    MinQ.toDescList (MinQueue (Down a) -> [Down a])
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> [Down a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    toDescList :: Ord a => MaxQueue a -> [a]
    toDescList :: forall a. Ord a => MaxQueue a -> [a]
    toDescList = (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] -> [a]) -> (MaxQueue a -> [Down a]) -> MaxQueue a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinQueue (Down a) -> [Down a]
    forall a. Ord a => MinQueue a -> [a]
    MinQ.toAscList (MinQueue (Down a) -> [Down a])
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> [Down a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    -- | \(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 (MaxQueue 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
    MinQ.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 right fold on the elements of a priority queue in ascending order.
    foldrAsc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
    foldrAsc :: forall a b. Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
    foldrAsc a -> b -> b
    f b
    z (MaxQueue 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
    MinQ.foldrDesc ((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 ascending order.
    foldlAsc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
    foldlAsc :: forall a b. Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
    foldlAsc b -> a -> b
    f b
    z (MaxQueue 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
    MinQ.foldlDesc ((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 \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 (MaxQueue 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
    MinQ.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 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
    MaxQueue (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
    MinQ.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
    MaxQueue (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
    MinQ.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

    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
    MaxQueue (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
    MinQ.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

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

    -- | Convert to a list in an arbitrary order.
    toListU :: MaxQueue a -> [a]
    toListU :: forall a. MaxQueue a -> [a]
    toListU = (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] -> [a]) -> (MaxQueue a -> [Down a]) -> MaxQueue a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MinQueue (Down a) -> [Down a]
    forall a. MinQueue a -> [a]
    MinQ.toListU (MinQueue (Down a) -> [Down a])
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> [Down a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    -- | Get the number of elements in a 'MaxQueue'.
    size :: MaxQueue a -> Int
    size :: forall a. MaxQueue a -> Int
    size = MinQueue (Down a) -> Int
    forall a. MinQueue a -> Int
    MinQ.size (MinQueue (Down a) -> Int)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    empty :: MaxQueue a
    empty :: forall a. MaxQueue a
    empty = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue MinQueue (Down a)
    forall a. MinQueue a
    MinQ.empty

    foldMapU :: Monoid m => (a -> m) -> MaxQueue a -> m
    foldMapU :: forall m a. Monoid m => (a -> m) -> MaxQueue a -> m
    foldMapU a -> m
    f = (Down a -> m) -> MinQueue (Down a) -> m
    forall m a. Monoid m => (a -> m) -> MinQueue a -> m
    MinQ.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) -> m)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> m
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    seqSpine :: MaxQueue a -> b -> b
    seqSpine :: forall a b. MaxQueue a -> b -> b
    seqSpine = MinQueue (Down a) -> b -> b
    forall a b. MinQueue a -> b -> b
    MinQ.seqSpine (MinQueue (Down a) -> b -> b)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> b -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    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
    b = (b -> Down a -> b) -> b -> MinQueue (Down a) -> b
    forall b a. (b -> a -> b) -> b -> MinQueue a -> b
    MinQ.foldlU (\b
    acc (Down a
    a) -> b -> a -> b
    f b
    acc a
    a) b
    b (MinQueue (Down a) -> b)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    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
    b = (b -> Down a -> b) -> b -> MinQueue (Down a) -> b
    forall b a. (b -> a -> b) -> b -> MinQueue a -> b
    MinQ.foldlU' (\b
    acc (Down a
    a) -> b -> a -> b
    f b
    acc a
    a) b
    b (MinQueue (Down a) -> b)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b
    foldrU :: forall a b. (a -> b -> b) -> b -> MaxQueue a -> b
    foldrU a -> b -> b
    c b
    n = (Down a -> b -> b) -> b -> MinQueue (Down a) -> b
    forall a b. (a -> b -> b) -> b -> MinQueue a -> b
    MinQ.foldrU (a -> b -> b
    c (a -> b -> b) -> (Down a -> a) -> Down a -> b -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> a
    forall a. Down a -> a
    unDown) b
    n (MinQueue (Down a) -> b)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    null :: MaxQueue a -> Bool
    null :: forall a. MaxQueue a -> Bool
    null = MinQueue (Down a) -> Bool
    forall a. MinQueue a -> Bool
    MinQ.null (MinQueue (Down a) -> Bool)
    -> (MaxQueue a -> MinQueue (Down a)) -> MaxQueue a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    singleton :: a -> MaxQueue a
    singleton :: forall a. a -> MaxQueue a
    singleton = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (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
    MinQ.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

    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 = MinQueue (Down b) -> MaxQueue b
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (MinQueue (Down b) -> MaxQueue b)
    -> (MaxQueue a -> MinQueue (Down b)) -> MaxQueue a -> MaxQueue b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Down a -> Maybe (Down b))
    -> MinQueue (Down a) -> MinQueue (Down b)
    forall b a. Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b
    MinQ.mapMaybe ((b -> Down b) -> Maybe b -> Maybe (Down b)
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap b -> Down b
    forall a. a -> Down a
    Down (Maybe b -> Maybe (Down b))
    -> (Down a -> Maybe b) -> Down a -> Maybe (Down b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Maybe b
    f (a -> Maybe b) -> (Down a -> a) -> Down a -> Maybe b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Down a -> a
    forall a. Down a -> a
    unDown) (MinQueue (Down a) -> MinQueue (Down b))
    -> (MaxQueue a -> MinQueue (Down a))
    -> MaxQueue a
    -> MinQueue (Down b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue

    insert :: Ord a => a -> MaxQueue a -> MaxQueue a
    insert :: forall a. Ord a => a -> MaxQueue a -> MaxQueue a
    insert a
    a (MaxQueue MinQueue (Down a)
    q) = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (Down a -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => a -> MinQueue a -> MinQueue a
    MinQ.insert (a -> Down a
    forall a. a -> Down a
    Down a
    a) MinQueue (Down a)
    q)

    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 (MaxQueue MinQueue (Down a)
    q) = case (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)
    MinQ.mapEither ((b -> Down b)
    -> (c -> Down c) -> Either b c -> Either (Down b) (Down c)
    forall a b c d. (a -> b) -> (c -> d) -> Either a c -> Either b d
    forall (p :: * -> * -> *) a b c d.
    Bifunctor p =>
    (a -> b) -> (c -> d) -> p a c -> p b d
    bimap b -> Down b
    forall a. a -> Down a
    Down 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 of
      (MinQueue (Down b)
    l, MinQueue (Down c)
    r) -> (MinQueue (Down b) -> MaxQueue b
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue MinQueue (Down b)
    l, MinQueue (Down c) -> MaxQueue c
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue MinQueue (Down c)
    r)

    union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
    union :: forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
    union (MaxQueue MinQueue (Down a)
    a) (MaxQueue MinQueue (Down a)
    b) = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (MinQueue (Down a) -> MinQueue (Down a) -> MinQueue (Down a)
    forall a. Ord a => MinQueue a -> MinQueue a -> MinQueue a
    MinQ.union MinQueue (Down a)
    a MinQueue (Down a)
    b)

    unions :: Ord a => [MaxQueue a] -> MaxQueue a
    unions :: forall a. Ord a => [MaxQueue a] -> MaxQueue a
    unions = MinQueue (Down a) -> MaxQueue a
    forall a. MinQueue (Down a) -> MaxQueue a
    MaxQueue (MinQueue (Down a) -> MaxQueue a)
    -> ([MaxQueue a] -> MinQueue (Down a))
    -> [MaxQueue a]
    -> MaxQueue a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [MinQueue (Down a)] -> MinQueue (Down a)
    forall a. Ord a => [MinQueue a] -> MinQueue a
    MinQ.unions ([MinQueue (Down a)] -> MinQueue (Down a))
    -> ([MaxQueue a] -> [MinQueue (Down a)])
    -> [MaxQueue a]
    -> MinQueue (Down a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (MaxQueue a -> MinQueue (Down a))
    -> [MaxQueue a] -> [MinQueue (Down a)]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap MaxQueue a -> MinQueue (Down a)
    forall a. MaxQueue a -> MinQueue (Down a)
    unMaxQueue