{-# 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.
-- The spine of the heap is maintained lazily. To force the spine of the heap,
-- use 'seqSpine'.
--
-- 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,
  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((<>)))
#endif

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

import Prelude hiding (null, 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
/= :: 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
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
min :: MaxQueue a -> MaxQueue a -> MaxQueue a
$cmin :: forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
max :: MaxQueue a -> MaxQueue a -> MaxQueue a
$cmax :: forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
>= :: 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
$c< :: forall a. Ord a => MaxQueue a -> MaxQueue a -> Bool
compare :: MaxQueue a -> MaxQueue a -> Ordering
$ccompare :: forall a. Ord a => MaxQueue a -> MaxQueue a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (MaxQueue a)
Ord, Typeable (MaxQueue a)
DataType
Constr
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 -> DataType
MaxQueue a -> Constr
(forall d. Data d => c (t d)) -> Maybe (c (MaxQueue a))
(forall b. Data b => b -> b) -> MaxQueue a -> MaxQueue a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxQueue a -> c (MaxQueue a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (MaxQueue a)
forall a. (Data a, Ord a) => Typeable (MaxQueue a)
forall a. (Data a, Ord a) => MaxQueue a -> DataType
forall a. (Data a, Ord a) => MaxQueue a -> Constr
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))
$cMaxQ :: Constr
$tMaxQueue :: DataType
gmapMo :: (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)
gmapMp :: (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)
gmapM :: (forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Ord a, Monad m) =>
(forall d. Data d => d -> m d) -> MaxQueue a -> m (MaxQueue a)
gmapQi :: Int -> (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
gmapQ :: (forall d. Data d => d -> u) -> MaxQueue a -> [u]
$cgmapQ :: forall a u.
(Data a, Ord a) =>
(forall d. Data d => d -> u) -> MaxQueue a -> [u]
gmapQr :: (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
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> MaxQueue a -> r
$cgmapQl :: forall a r r'.
(Data a, Ord a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> MaxQueue a -> r
gmapT :: (forall b. Data b => b -> b) -> MaxQueue a -> MaxQueue a
$cgmapT :: forall a.
(Data a, Ord a) =>
(forall b. Data b => b -> b) -> MaxQueue a -> MaxQueue a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> 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))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (MaxQueue a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (MaxQueue a))
dataTypeOf :: MaxQueue a -> DataType
$cdataTypeOf :: forall a. (Data a, Ord a) => MaxQueue a -> DataType
toConstr :: MaxQueue a -> Constr
$ctoConstr :: forall a. (Data a, Ord a) => MaxQueue a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> 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)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> MaxQueue a -> 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)
$cp1Data :: forall a. (Data a, Ord a) => Typeable (MaxQueue a)
Data, Typeable)
# 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 String
"fromDescList" <- ReadPrec Lexeme
lexP
    [a]
xs <- ReadPrec [a]
forall a. Read a => ReadPrec a
readPrec
    MaxQueue a -> ReadPrec (MaxQueue a)
forall (m :: * -> *) a. Monad m => a -> m a
return ([a] -> MaxQueue a
forall a. [a] -> MaxQueue a
fromDescList [a]
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
#endif

instance Ord a => Monoid (MaxQueue a) where
  mempty :: MaxQueue a
mempty = MaxQueue a
forall a. MaxQueue a
empty
  mappend :: MaxQueue a -> MaxQueue a -> MaxQueue a
mappend = MaxQueue a -> MaxQueue a -> MaxQueue a
forall a. Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
union

-- | /O(1)/. The empty priority queue.
empty :: MaxQueue a
empty :: 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 :: 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 :: 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 :: 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 :: 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 :: 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 :: 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 :: 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 :: MaxQueue a -> Maybe (MaxQueue a)
delete = ((a, MaxQueue a) -> MaxQueue a)
-> Maybe (a, MaxQueue a) -> Maybe (MaxQueue a)
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 :: 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 :: 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(n1,n2)))/. Take the union of two priority queues.
union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
MaxQ MinQueue (Down a)
q1 union :: 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 :: [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 !! :: 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 :: 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 :: 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 :: 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]
map 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 :: (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]
map 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 :: (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 :: (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]
map 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 :: (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 :: (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 :: (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 :: (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 :: (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)/. 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 :: (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 :: (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 (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 left fold on a priority queue.
foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b
foldlU :: (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 (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 :: 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 :: MaxQueue a -> [a]
toListU (MaxQ MinQueue (Down a)
q) = (Down a -> a) -> [Down a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map 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 :: (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 :: (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 :: (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 (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 :: (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 (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 :: 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 :: 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 :: MaxQueue a -> [a]
toList (MaxQ MinQueue (Down a)
q) = (Down a -> a) -> [Down a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map 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 :: [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]
map 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 :: [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]
map 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 :: [a] -> MaxQueue a
fromList = (a -> MaxQueue a -> MaxQueue a) -> MaxQueue a -> [a] -> MaxQueue a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> MaxQueue a -> MaxQueue a
forall a. Ord a => a -> MaxQueue a -> MaxQueue a
insert MaxQueue a
forall a. MaxQueue a
empty

-- | /O(n)/. Constructs a priority queue from the keys of a 'Prio.MaxPQueue'.
keysQueue :: Prio.MaxPQueue k a -> MaxQueue k
keysQueue :: 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)/. Forces the spine of the heap.
seqSpine :: MaxQueue a -> b -> b
seqSpine :: 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