-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Double-ended priority queues.
--
-- Min-max priority queues, also known as double-ended priority queues.
@package min-max-pqueue
@version 0.1.0.2
-- | Double-ended priority queues where priority values are integers,
-- allowing efficient retrieval and removel from both ends of the queue.
--
-- A queue can be configured with a maximum size. Each time an insertion
-- causes the queue to grow beyond the size limit, the greatest element
-- will be automatically removed (rather than rejecting the insertion).
--
-- The implementation is backed by an IntMap (NonEmpty
-- a). This means that certain operations, including peekMin,
-- peekMax and fromList, are asymptotically more expensive
-- than a mutable array based implementation. In a pure language like
-- Haskell, a mutable array based implementation would be impure and need
-- to operate inside monads. And in many applications, regardless of
-- language, the additional time complexity would be a small or
-- negligible price to pay to avoid destructive updates anyway.
--
-- If you only access one end of the queue (i.e., you need a regular
-- priority queue), an implementation based on a kind of heap that is
-- more amenable to purely functional implementations, such as binomial
-- heap and pairing heap, is potentially more efficient. But
-- always benchmark if performance is important; in my experience
-- Map always wins, even for regular priority queues.
--
-- See README.md for more information.
module Data.IntMinMaxQueue
-- | A double-ended priority queue whose elements are compared on an
-- Int field.
data IntMinMaxQueue a
type Prio = Int
-- | O(1). The empty queue.
empty :: IntMinMaxQueue a
-- | O(1). A queue with a single element.
singleton :: (a -> Prio) -> a -> IntMinMaxQueue a
-- | O(n * log n). Build a queue from a list of (priority, element)
-- pairs.
fromList :: [(Prio, a)] -> IntMinMaxQueue a
-- | O(n * log n). Build a queue from a list of elements and a
-- function from elements to priorities.
fromListWith :: (a -> Prio) -> [a] -> IntMinMaxQueue a
-- | O(n) (due to calculating the queue size).
fromMap :: IntMap (NonEmpty a) -> IntMinMaxQueue a
-- | O(1). Is the queue empty?
null :: IntMinMaxQueue a -> Bool
-- | O(1). Is the queue non-empty?
notNull :: IntMinMaxQueue a -> Bool
-- | O(1). The total number of elements in the queue.
size :: IntMinMaxQueue a -> Int
-- | Return a queue that is limited to the given number of elements. If the
-- original queue has more elements than the size limit, the greatest
-- elements will be dropped until the size limit is satisfied.
withMaxSize :: IntMinMaxQueue a -> Int -> IntMinMaxQueue a
-- | O(1). The size limit of the queue. It returns either
-- Nothing (if the queue does not have a size limit) or Just
-- n where n >= 0.
maxSize :: IntMinMaxQueue a -> Maybe Int
-- | O(log n). Add the given element to the queue. If the queue has
-- a size limit, and the insertion causes the queue to grow beyond its
-- size limit, the greatest element will be removed from the queue, which
-- may be the element just added.
insert :: (a -> Prio) -> a -> IntMinMaxQueue a -> IntMinMaxQueue a
-- | O(log n). Retrieve the least element of the queue, if exists.
peekMin :: IntMinMaxQueue a -> Maybe a
-- | O(log n). Retrieve the greatest element of the queue, if
-- exists.
peekMax :: IntMinMaxQueue a -> Maybe a
-- | O(log n). Remove the least element of the queue, if exists.
deleteMin :: IntMinMaxQueue a -> IntMinMaxQueue a
-- | O(log n). Remove the greatest element of the queue, if exists.
deleteMax :: IntMinMaxQueue a -> IntMinMaxQueue a
-- | O(log n). Remove and return the least element of the queue, if
-- exists.
pollMin :: IntMinMaxQueue a -> Maybe (a, IntMinMaxQueue a)
-- | O(log n). Remove and return the greatest element of the queue,
-- if exists.
pollMax :: IntMinMaxQueue a -> Maybe (a, IntMinMaxQueue a)
-- | takeMin n q returns a queue with the n least
-- elements in q, or q itself if n >=
-- size q.
takeMin :: Int -> IntMinMaxQueue a -> IntMinMaxQueue a
-- | takeMin n q returns a queue with the n
-- greatest elements in q, or q itself if n >=
-- size q.
takeMax :: Int -> IntMinMaxQueue a -> IntMinMaxQueue a
-- | dropMin n q returns a queue with the n least
-- elements dropped from q, or empty if n >=
-- size q.
dropMin :: Int -> IntMinMaxQueue a -> IntMinMaxQueue a
-- | dropMax n q returns a queue with the n
-- greatest elements dropped from q, or empty if n
-- >= size q.
dropMax :: Int -> IntMinMaxQueue a -> IntMinMaxQueue a
-- | Map a function over all elements in the queue.
map :: (a -> b) -> IntMinMaxQueue a -> IntMinMaxQueue b
-- | Map a function over all elements in the queue.
mapWithPriority :: (Prio -> a -> b) -> IntMinMaxQueue a -> IntMinMaxQueue b
-- | Fold the elements in the queue using the given right-associative
-- binary operator, such that foldr f z == foldr f z .
-- elems.
foldr :: (a -> b -> b) -> b -> IntMinMaxQueue a -> b
-- | Fold the elements in the queue using the given left-associative binary
-- operator, such that foldl f z == foldl f z .
-- elems.
foldl :: (a -> b -> a) -> a -> IntMinMaxQueue b -> a
-- | Fold the elements in the queue using the given right-associative
-- binary operator, such that foldrWithPriority f z ==
-- foldr (uncurry f) z . toAscList.
foldrWithPriority :: (Prio -> a -> b -> b) -> b -> IntMinMaxQueue a -> b
-- | Fold the elements in the queue using the given left-associative binary
-- operator, such that foldlWithPriority f z == foldr
-- (uncurry . f) z . toAscList.
foldlWithPriority :: (a -> Prio -> b -> a) -> a -> IntMinMaxQueue b -> a
-- | Fold the elements in the queue using the given monoid, such that
-- foldMapWithPriority f == foldMap (uncurry f) .
-- elems.
foldMapWithPriority :: Monoid m => (Prio -> a -> m) -> IntMinMaxQueue a -> m
-- | A strict version of foldr. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> IntMinMaxQueue a -> b
-- | A strict version of foldl. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> IntMinMaxQueue b -> a
-- | A strict version of foldrWithPriority. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldrWithPriority' :: (Prio -> a -> b -> b) -> b -> IntMinMaxQueue a -> b
-- | A strict version of foldlWithPriority. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldlWithPriority' :: (a -> Prio -> b -> a) -> a -> IntMinMaxQueue b -> a
-- | Elements in the queue in ascending order of priority. Elements with
-- the same priority are returned in no particular order.
elems :: IntMinMaxQueue a -> [a]
-- | An alias for toAscList.
toList :: IntMinMaxQueue a -> [(Prio, a)]
-- | Convert the queue to a list in ascending order of priority. Elements
-- with the same priority are returned in no particular order.
toAscList :: IntMinMaxQueue a -> [(Prio, a)]
-- | Convert the queue to a list in descending order of priority. Elements
-- with the same priority are returned in no particular order.
toDescList :: IntMinMaxQueue a -> [(Prio, a)]
-- | O(n). Convert the queue to an IntMap.
toMap :: IntMinMaxQueue a -> IntMap (NonEmpty a)
instance Data.Data.Data a => Data.Data.Data (Data.IntMinMaxQueue.IntMinMaxQueue a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.IntMinMaxQueue.IntMinMaxQueue a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.IntMinMaxQueue.IntMinMaxQueue a)
instance Data.Functor.Classes.Eq1 Data.IntMinMaxQueue.IntMinMaxQueue
instance Data.Functor.Classes.Ord1 Data.IntMinMaxQueue.IntMinMaxQueue
instance GHC.Show.Show a => GHC.Show.Show (Data.IntMinMaxQueue.IntMinMaxQueue a)
instance Data.Functor.Classes.Show1 Data.IntMinMaxQueue.IntMinMaxQueue
instance GHC.Read.Read a => GHC.Read.Read (Data.IntMinMaxQueue.IntMinMaxQueue a)
instance Data.Functor.Classes.Read1 Data.IntMinMaxQueue.IntMinMaxQueue
instance GHC.Base.Functor Data.IntMinMaxQueue.IntMinMaxQueue
instance Data.Foldable.Foldable Data.IntMinMaxQueue.IntMinMaxQueue
-- | Double-ended priority queues, allowing efficient retrieval and removel
-- from both ends of the queue.
--
-- A queue can be configured with a maximum size. Each time an insertion
-- causes the queue to grow beyond the size limit, the greatest element
-- will be automatically removed (rather than rejecting the insertion).
--
-- If the priority values are Ints, use
-- Data.IntMinMaxQueue.
--
-- The implementation is backed by a Map prio (NonEmpty
-- a). This means that certain operations, including peekMin,
-- peekMax and fromList, are asymptotically more expensive
-- than a mutable array based implementation. In a pure language like
-- Haskell, a mutable array based implementation would be impure and need
-- to operate inside monads. And in many applications, regardless of
-- language, the additional time complexity would be a small or
-- negligible price to pay to avoid destructive updates anyway.
--
-- If you only access one end of the queue (i.e., you need a regular
-- priority queue), an implementation based on a kind of heap that is
-- more amenable to purely functional implementations, such as binomial
-- heap and pairing heap, is potentially more efficient. But
-- always benchmark if performance is important; in my experience
-- Map always wins, even for regular priority queues.
--
-- See README.md for more information.
module Data.MinMaxQueue
-- | A double-ended priority queue whose elements are of type a
-- and are compared on prio.
data MinMaxQueue prio a
-- | O(1). The empty queue.
empty :: MinMaxQueue prio a
-- | O(1). A queue with a single element.
singleton :: (a -> prio) -> a -> MinMaxQueue prio a
-- | O(n * log n). Build a queue from a list of (priority, element)
-- pairs.
fromList :: Ord prio => [(prio, a)] -> MinMaxQueue prio a
-- | O(n * log n). Build a queue from a list of elements and a
-- function from elements to priorities.
fromListWith :: Ord prio => (a -> prio) -> [a] -> MinMaxQueue prio a
-- | O(n) (due to calculating the queue size).
fromMap :: Map prio (NonEmpty a) -> MinMaxQueue prio a
-- | O(1). Is the queue empty?
null :: MinMaxQueue prio a -> Bool
-- | O(1). Is the queue non-empty?
notNull :: MinMaxQueue prio a -> Bool
-- | O(1). The total number of elements in the queue.
size :: MinMaxQueue prio a -> Int
-- | Return a queue that is limited to the given number of elements. If the
-- original queue has more elements than the size limit, the greatest
-- elements will be dropped until the size limit is satisfied.
withMaxSize :: Ord prio => MinMaxQueue prio a -> Int -> MinMaxQueue prio a
-- | O(1). The size limit of the queue. It returns either
-- Nothing (if the queue does not have a size limit) or Just
-- n where n >= 0.
maxSize :: MinMaxQueue prio a -> Maybe Int
-- | O(log n). Add the given element to the queue. If the queue has
-- a size limit, and the insertion causes the queue to grow beyond its
-- size limit, the greatest element will be removed from the queue, which
-- may be the element just added.
insert :: Ord prio => (a -> prio) -> a -> MinMaxQueue prio a -> MinMaxQueue prio a
-- | O(log n). Retrieve the least element of the queue, if exists.
peekMin :: Ord prio => MinMaxQueue prio a -> Maybe a
-- | O(log n). Retrieve the greatest element of the queue, if
-- exists.
peekMax :: Ord prio => MinMaxQueue prio a -> Maybe a
-- | O(log n). Remove the least element of the queue, if exists.
deleteMin :: Ord prio => MinMaxQueue prio a -> MinMaxQueue prio a
-- | O(log n). Remove the greatest element of the queue, if exists.
deleteMax :: Ord prio => MinMaxQueue prio a -> MinMaxQueue prio a
-- | O(log n). Remove and return the least element of the queue, if
-- exists.
pollMin :: Ord prio => MinMaxQueue prio a -> Maybe (a, MinMaxQueue prio a)
-- | O(log n). Remove and return the greatest element of the queue,
-- if exists.
pollMax :: Ord prio => MinMaxQueue prio a -> Maybe (a, MinMaxQueue prio a)
-- | takeMin n q returns a queue with the n least
-- elements in q, or q itself if n >=
-- size q.
takeMin :: Ord prio => Int -> MinMaxQueue prio a -> MinMaxQueue prio a
-- | takeMin n q returns a queue with the n
-- greatest elements in q, or q itself if n >=
-- size q.
takeMax :: Ord prio => Int -> MinMaxQueue prio a -> MinMaxQueue prio a
-- | dropMin n q returns a queue with the n least
-- elements dropped from q, or empty if n >=
-- size q.
dropMin :: Ord prio => Int -> MinMaxQueue prio a -> MinMaxQueue prio a
-- | dropMax n q returns a queue with the n
-- greatest elements dropped from q, or empty if n
-- >= size q.
dropMax :: Ord prio => Int -> MinMaxQueue prio a -> MinMaxQueue prio a
-- | Map a function over all elements in the queue.
map :: (a -> b) -> MinMaxQueue prio a -> MinMaxQueue prio b
-- | Map a function over all elements in the queue.
mapWithPriority :: (prio -> a -> b) -> MinMaxQueue prio a -> MinMaxQueue prio b
-- | Fold the elements in the queue using the given right-associative
-- binary operator, such that foldr f z == foldr f z .
-- elems.
foldr :: (a -> b -> b) -> b -> MinMaxQueue prio a -> b
-- | Fold the elements in the queue using the given left-associative binary
-- operator, such that foldl f z == foldl f z .
-- elems.
foldl :: (a -> b -> a) -> a -> MinMaxQueue prio b -> a
-- | Fold the elements in the queue using the given right-associative
-- binary operator, such that foldrWithPriority f z ==
-- foldr (uncurry f) z . toAscList.
foldrWithPriority :: (prio -> a -> b -> b) -> b -> MinMaxQueue prio a -> b
-- | Fold the elements in the queue using the given left-associative binary
-- operator, such that foldlWithPriority f z == foldr
-- (uncurry . f) z . toAscList.
foldlWithPriority :: (a -> prio -> b -> a) -> a -> MinMaxQueue prio b -> a
-- | Fold the elements in the queue using the given monoid, such that
-- foldMapWithPriority f == foldMap (uncurry f) .
-- elems.
foldMapWithPriority :: Monoid m => (prio -> a -> m) -> MinMaxQueue prio a -> m
-- | A strict version of foldr. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> MinMaxQueue prio a -> b
-- | A strict version of foldl. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> MinMaxQueue prio b -> a
-- | A strict version of foldrWithPriority. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldrWithPriority' :: (prio -> a -> b -> b) -> b -> MinMaxQueue prio a -> b
-- | A strict version of foldlWithPriority. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldlWithPriority' :: (a -> prio -> b -> a) -> a -> MinMaxQueue prio b -> a
-- | Elements in the queue in ascending order of priority. Elements with
-- the same priority are returned in no particular order.
elems :: MinMaxQueue prio a -> [a]
-- | An alias for toAscList.
toList :: MinMaxQueue prio a -> [(prio, a)]
-- | Convert the queue to a list in ascending order of priority. Elements
-- with the same priority are returned in no particular order.
toAscList :: MinMaxQueue prio a -> [(prio, a)]
-- | Convert the queue to a list in descending order of priority. Elements
-- with the same priority are returned in no particular order.
toDescList :: MinMaxQueue prio a -> [(prio, a)]
-- | O(n). Convert the queue to a Map.
toMap :: MinMaxQueue prio a -> Map prio (NonEmpty a)
instance (Data.Data.Data prio, Data.Data.Data a, GHC.Classes.Ord prio) => Data.Data.Data (Data.MinMaxQueue.MinMaxQueue prio a)
instance (GHC.Classes.Ord prio, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.MinMaxQueue.MinMaxQueue prio a)
instance (GHC.Classes.Eq prio, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.MinMaxQueue.MinMaxQueue prio a)
instance GHC.Classes.Eq prio => Data.Functor.Classes.Eq1 (Data.MinMaxQueue.MinMaxQueue prio)
instance Data.Functor.Classes.Eq2 Data.MinMaxQueue.MinMaxQueue
instance GHC.Classes.Ord prio => Data.Functor.Classes.Ord1 (Data.MinMaxQueue.MinMaxQueue prio)
instance Data.Functor.Classes.Ord2 Data.MinMaxQueue.MinMaxQueue
instance (GHC.Show.Show prio, GHC.Show.Show a) => GHC.Show.Show (Data.MinMaxQueue.MinMaxQueue prio a)
instance GHC.Show.Show prio => Data.Functor.Classes.Show1 (Data.MinMaxQueue.MinMaxQueue prio)
instance Data.Functor.Classes.Show2 Data.MinMaxQueue.MinMaxQueue
instance (GHC.Classes.Ord prio, GHC.Read.Read prio, GHC.Read.Read a) => GHC.Read.Read (Data.MinMaxQueue.MinMaxQueue prio a)
instance (GHC.Classes.Ord prio, GHC.Read.Read prio) => Data.Functor.Classes.Read1 (Data.MinMaxQueue.MinMaxQueue prio)
instance GHC.Base.Functor (Data.MinMaxQueue.MinMaxQueue prio)
instance Data.Foldable.Foldable (Data.MinMaxQueue.MinMaxQueue prio)