Maintainer | brad.larsen@gmail.com |
---|
Data.PurePriorityQueue.Internal
Description
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
- singleton :: Ord p => a -> p -> MinMaxQueue p a
- 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
.
Constructors
MinMaxQueue | |
Fields
|
Instances
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.
singleton :: Ord p => a -> p -> MinMaxQueue p aSource
O(1) A priority queue with a single entry.
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
Arguments
:: 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.
Ties are broken arbitrarily.
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.
Ties are broken arbitrarily.
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 log p) Filter all values that satisfy the predicate.
filterWithPriority :: Ord p => (a -> p -> Bool) -> MinMaxQueue p a -> MinMaxQueue p aSource
O(n log p) 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.
Ties are broken in an arbitrary manner.