Maintainer | brad.larsen@gmail.com |
---|
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.
- newtype MinMaxQueue p a = MinMaxQueue {
- unMinMaxQueue :: Map p [a]
- empty :: MinMaxQueue p a
- null :: MinMaxQueue p a -> Bool
- insert :: Ord p => a -> p -> MinMaxQueue p a -> MinMaxQueue p a
- deleteMin :: Ord p => MinMaxQueue p a -> MinMaxQueue p a
- deleteMax :: Ord p => MinMaxQueue p a -> MinMaxQueue p a
- viewWith :: Ord p => (Map p [a] -> Maybe ((p, [a]), Map p [a])) -> MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)
- minView :: Ord p => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)
- maxView :: Ord p => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)
- minPriority :: Ord p => MinMaxQueue p a -> Maybe p
- maxPriority :: Ord p => MinMaxQueue p a -> Maybe p
- foldWithPriority :: Ord p => (p -> a -> b -> b) -> b -> MinMaxQueue p a -> b
- splitByPriority :: Ord p => p -> MinMaxQueue p a -> (MinMaxQueue p a, MinMaxQueue p a)
- size :: Ord p => MinMaxQueue p a -> Int
- filter :: Ord p => (a -> Bool) -> MinMaxQueue p a -> MinMaxQueue p a
- filterWithPriority :: Ord p => (a -> p -> Bool) -> MinMaxQueue p a -> MinMaxQueue p a
- toAscList :: Ord p => MinMaxQueue p a -> [(a, p)]
Documentation
newtype MinMaxQueue p a Source
A queue of values of type a
with priority of type p
.
MinMaxQueue | |
|
Functor (MinMaxQueue p) | |
Foldable (MinMaxQueue p) | |
(Eq p, Eq a) => Eq (MinMaxQueue p a) | |
(Ord p, Ord a) => Ord (MinMaxQueue p a) | |
Ord p => Monoid (MinMaxQueue p a) |
empty :: MinMaxQueue p aSource
O(1) An empty priority queue.
null :: MinMaxQueue p a -> BoolSource
O(1) Test whether a priority queue is empty.
insert :: Ord p => a -> p -> MinMaxQueue p a -> MinMaxQueue p aSource
O(log p) Insert a value with given priority into a priority queue.
deleteMin :: Ord p => MinMaxQueue p a -> MinMaxQueue p aSource
deleteMax :: Ord p => MinMaxQueue p a -> MinMaxQueue p aSource
:: Ord p | |
=> (Map p [a] -> Maybe ((p, [a]), Map p [a])) | The view function |
-> MinMaxQueue p a | The priority queue |
-> Maybe ((a, p), MinMaxQueue p a) |
Applies a Data.Map.Map
view function to a given priority queue.
minView :: Ord p => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)Source
O(log p) View a priority queue to get the (value, priority) pair with the lowest priority and the remainder of the queue.
If multiple values share the lowest priority, the most recently added will be returned.
maxView :: Ord p => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)Source
O(log p) View a priority queue to get the (value, priority) pair with the highest priority and the remainder of the queue.
If multiple values share the highest priority, the most recently added will be returned.
minPriority :: Ord p => MinMaxQueue p a -> Maybe pSource
O(log p) Get the minimum priority of the elements in the queue.
maxPriority :: Ord p => MinMaxQueue p a -> Maybe pSource
O(log p) Get the maximum priority of the elements in the queue.
foldWithPriority :: Ord p => (p -> a -> b -> b) -> b -> MinMaxQueue p a -> bSource
O(n) Fold the priorities and values of a priority queue.
splitByPriority :: Ord p => p -> MinMaxQueue p a -> (MinMaxQueue p a, MinMaxQueue p a)Source
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
.
size :: Ord p => MinMaxQueue p a -> IntSource
O(n) The number of entries in a priority queue.
filter :: Ord p => (a -> Bool) -> MinMaxQueue p a -> MinMaxQueue p aSource
O(n) Filter all values that satisfy the predicate.
filterWithPriority :: Ord p => (a -> p -> Bool) -> MinMaxQueue p a -> MinMaxQueue p aSource
O(n) Filter all entries that satisfy the predicate.
toAscList :: Ord p => MinMaxQueue p a -> [(a, p)]Source
O(n) Convert the priority queue into a list of (value, priority) pairs in ascending priority.
If multiple values share the same priority, the most recently added entries will come first.