-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A pure priority queue.
--
-- A pure priority queue.
@package pure-priority-queue
@version 0.14
-- | This module exposes the internals of a pure priority queue,
-- implemented on top of Data.Map.
--
-- Estimates of worst-case time complexity are given. The value n
-- is the number of elements in the queue. The value p is the
-- cardinality of the set of priorities of the elements in the queue.
-- p is never greater than n.
module Data.PurePriorityQueue.Internal
-- | A queue of values of type a with priority of type p.
newtype MinMaxQueue p a
MinMaxQueue :: Map p [a] -> MinMaxQueue p a
unMinMaxQueue :: MinMaxQueue p a -> Map p [a]
-- | O(1) An empty priority queue.
empty :: MinMaxQueue p a
-- | O(1) Test whether a priority queue is empty.
null :: MinMaxQueue p a -> Bool
-- | O(1) A priority queue with a single entry.
singleton :: (Ord p) => a -> p -> MinMaxQueue p a
-- | O(log p) Insert a value with given priority into a priority
-- queue.
insert :: (Ord p) => a -> p -> MinMaxQueue p a -> MinMaxQueue p a
-- | O(log p) Remove the value with the minimum priority from the
-- queue.
--
-- If the queue is empty, deleteMin returns empty. Ties are
-- broken arbitrarily.
deleteMin :: (Ord p) => MinMaxQueue p a -> MinMaxQueue p a
-- | O(log p) Remove the value with the maximum priority from the
-- queue.
--
-- If the queue is empty, deleteMax returns empty. Ties are
-- broken arbitrarily.
deleteMax :: (Ord p) => MinMaxQueue p a -> MinMaxQueue p a
-- | Applies a Data.Map.Map view function to a given priority
-- queue.
viewWith :: (Ord p) => (Map p [a] -> Maybe ((p, [a]), Map p [a])) -> MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)
-- | O(log p) View a priority queue to get the (value, priority)
-- pair with the lowest priority and the remainder of the queue.
--
-- Ties are broken arbitrarily.
minView :: (Ord p) => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)
-- | O(log p) View a priority queue to get the (value, priority)
-- pair with the highest priority and the remainder of the queue.
--
-- Ties are broken arbitrarily.
maxView :: (Ord p) => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)
-- | O(log p) Get the minimum priority of the elements in the queue.
minPriority :: (Ord p) => MinMaxQueue p a -> Maybe p
-- | O(log p) Get the maximum priority of the elements in the queue.
maxPriority :: (Ord p) => MinMaxQueue p a -> Maybe p
-- | O(n) Fold the priorities and values of a priority queue.
foldWithPriority :: (Ord p) => (p -> a -> b -> b) -> b -> MinMaxQueue p a -> b
-- | O(log p) Split a priority queue q into two queues
-- (q1, q2) by the given priority p, such that
-- q1 contains exactly the entries with priority less than
-- p, and q2 containes exactly the entries with
-- priority greater than or equal to p.
splitByPriority :: (Ord p) => p -> MinMaxQueue p a -> (MinMaxQueue p a, MinMaxQueue p a)
-- | O(n) The number of entries in a priority queue.
size :: (Ord p) => MinMaxQueue p a -> Int
-- | O(n log p) Filter all values that satisfy the predicate.
filter :: (Ord p) => (a -> Bool) -> MinMaxQueue p a -> MinMaxQueue p a
-- | O(n log p) Filter all entries that satisfy the predicate.
filterWithPriority :: (Ord p) => (a -> p -> Bool) -> MinMaxQueue p a -> MinMaxQueue p a
-- | O(n) Convert the priority queue into a list of (value,
-- priority) pairs in ascending priority.
--
-- Ties are broken in an arbitrary manner.
toAscList :: (Ord p) => MinMaxQueue p a -> [(a, p)]
instance (Eq p, Eq a) => Eq (MinMaxQueue p a)
instance (Ord p, Ord a) => Ord (MinMaxQueue p a)
instance (Ord p) => Monoid (MinMaxQueue p a)
instance Foldable (MinMaxQueue p)
instance Functor (MinMaxQueue p)
-- | A pure priority queue.
--
-- Because many function names clash with Prelude names, this
-- module is usually imported qualified, e.g.,
--
--
-- import qualified Data.PurePriorityQueue as PQ
--
--
-- This implementation is built on top of Data.Map.
--
-- Estimates of worst-case time complexity are given. The value n
-- is the number of elements in the queue. The value p is the
-- cardinality of the set of priorities of the elements in the queue.
-- p is never greater than n.
module Data.PurePriorityQueue
-- | A queue of values of type a with priority of type p.
data MinMaxQueue p a
-- | O(1) An empty priority queue.
empty :: MinMaxQueue p a
-- | O(1) Test whether a priority queue is empty.
null :: MinMaxQueue p a -> Bool
-- | O(1) A priority queue with a single entry.
singleton :: (Ord p) => a -> p -> MinMaxQueue p a
-- | O(log p) Insert a value with given priority into a priority
-- queue.
insert :: (Ord p) => a -> p -> MinMaxQueue p a -> MinMaxQueue p a
-- | O(log p) Remove the value with the minimum priority from the
-- queue.
--
-- If the queue is empty, deleteMin returns empty. Ties are
-- broken arbitrarily.
deleteMin :: (Ord p) => MinMaxQueue p a -> MinMaxQueue p a
-- | O(log p) Remove the value with the maximum priority from the
-- queue.
--
-- If the queue is empty, deleteMax returns empty. Ties are
-- broken arbitrarily.
deleteMax :: (Ord p) => MinMaxQueue p a -> MinMaxQueue p a
-- | O(log p) View a priority queue to get the (value, priority)
-- pair with the lowest priority and the remainder of the queue.
--
-- Ties are broken arbitrarily.
minView :: (Ord p) => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)
-- | O(log p) View a priority queue to get the (value, priority)
-- pair with the highest priority and the remainder of the queue.
--
-- Ties are broken arbitrarily.
maxView :: (Ord p) => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)
-- | O(log p) Get the minimum priority of the elements in the queue.
minPriority :: (Ord p) => MinMaxQueue p a -> Maybe p
-- | O(log p) Get the maximum priority of the elements in the queue.
maxPriority :: (Ord p) => MinMaxQueue p a -> Maybe p
-- | O(n) Fold the priorities and values of a priority queue.
foldWithPriority :: (Ord p) => (p -> a -> b -> b) -> b -> MinMaxQueue p a -> b
-- | O(log p) Split a priority queue q into two queues
-- (q1, q2) by the given priority p, such that
-- q1 contains exactly the entries with priority less than
-- p, and q2 containes exactly the entries with
-- priority greater than or equal to p.
splitByPriority :: (Ord p) => p -> MinMaxQueue p a -> (MinMaxQueue p a, MinMaxQueue p a)
-- | O(n) The number of entries in a priority queue.
size :: (Ord p) => MinMaxQueue p a -> Int
-- | O(n log p) Filter all values that satisfy the predicate.
filter :: (Ord p) => (a -> Bool) -> MinMaxQueue p a -> MinMaxQueue p a
-- | O(n log p) Filter all entries that satisfy the predicate.
filterWithPriority :: (Ord p) => (a -> p -> Bool) -> MinMaxQueue p a -> MinMaxQueue p a
-- | O(n) Convert the priority queue into a list of (value,
-- priority) pairs in ascending priority.
--
-- Ties are broken in an arbitrary manner.
toAscList :: (Ord p) => MinMaxQueue p a -> [(a, p)]