Safe Haskell | Safe-Infered |
---|
Data.PSQueue
Contents
Description
A priority search queue (henceforth queue) efficiently supports the
opperations of both a search tree and a priority queue. A Binding
is a
product of a key and a priority. Bindings can be inserted, deleted, modified
and queried in logarithmic time, and the binding with the least priority can be
retrieved in constant time. A queue can be built from a list of bindings,
sorted by keys, in linear time.
This implementation is due to Ralf Hinze.
- Hinze, R., A Simple Implementation Technique for Priority Search Queues, ICFP 2001, pp. 110-121
- data Binding k p = k :-> p
- key :: Binding k p -> k
- prio :: Binding k p -> p
- data PSQ k p
- size :: PSQ k p -> Int
- null :: PSQ k p -> Bool
- lookup :: (Ord k, Ord p) => k -> PSQ k p -> Maybe p
- empty :: (Ord k, Ord p) => PSQ k p
- singleton :: (Ord k, Ord p) => k -> p -> PSQ k p
- insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p
- insertWith :: (Ord k, Ord p) => (p -> p -> p) -> k -> p -> PSQ k p -> PSQ k p
- delete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p
- adjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k p
- adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k p
- update :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k p
- updateWithKey :: (Ord k, Ord p) => (k -> p -> Maybe p) -> k -> PSQ k p -> PSQ k p
- alter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k p
- keys :: (Ord k, Ord p) => PSQ k p -> [k]
- toList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
- toAscList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
- toDescList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
- fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
- fromAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
- fromDistinctAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
- findMin :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p)
- deleteMin :: (Ord k, Ord p) => PSQ k p -> PSQ k p
- minView :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p, PSQ k p)
- atMost :: (Ord k, Ord p) => p -> PSQ k p -> [Binding k p]
- atMostRange :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> [Binding k p]
- foldr :: (Ord k, Ord p) => (Binding k p -> b -> b) -> b -> PSQ k p -> b
- foldl :: (Ord k, Ord p) => (b -> Binding k p -> b) -> b -> PSQ k p -> b
Binding Type
k :-> p
binds the key k
with the priority p
.
Constructors
k :-> p |
Priority Search Queue Type
A mapping from keys k
to priorites p
.
Query
lookup :: (Ord k, Ord p) => k -> PSQ k p -> Maybe pSource
O(log n) The priority of a given key, or Nothing if the key is not bound.
Construction
Insertion
insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k pSource
O(log n) Insert a binding into the queue.
insertWith :: (Ord k, Ord p) => (p -> p -> p) -> k -> p -> PSQ k p -> PSQ k pSource
O(log n) Insert a binding with a combining function.
Delete/Update
adjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k pSource
O(log n) Adjust the priority of a key.
adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k pSource
O(log n) Adjust the priority of a key.
alter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k pSource
O(log n). The expression (
) alters the priority alter
f k qp
bound to k
, or absence thereof.
alter can be used to insert, delete, or update a priority in a queue.
Conversion
toAscList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]Source
O(n) Convert a queue to a list in ascending order of keys.
toDescList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]Source
O(n) Convert a queue to a list in descending order of keys.
fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k pSource
O(n log n) Build a queue from a list of bindings.
fromAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k pSource
O(n) Build a queue from a list of bindings in order of ascending keys. The precondition that the keys are ascending is not checked.
fromDistinctAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k pSource
O(n) Build a queue from a list of distinct bindings in order of ascending keys. The precondition that keys are distinct and ascending is not checked.
Priority Queue
findMin :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p)Source
O(1) The binding with the lowest priority.
deleteMin :: (Ord k, Ord p) => PSQ k p -> PSQ k pSource
O(log n) Remove the binding with the lowest priority.
minView :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p, PSQ k p)Source
O(log n) Retrieve the binding with the least priority, and the rest of the queue stripped of that binding.
atMost :: (Ord k, Ord p) => p -> PSQ k p -> [Binding k p]Source
O(r(log n - log r) atMost p q
is a list of all the bindings in q
with
priority less than p
, in order of ascending keys.
Effectively,
atMost p' q = filter (\(k:->p) -> p<=p') . toList
atMostRange :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> [Binding k p]Source
O(r(log n - log r)) atMostRange p (l,u) q
is a list of all the bindings in
q
with a priority less than p
and a key in the range (l,u)
inclusive.
Effectively,
atMostRange p' (l,u) q = filter (\(k:->p) -> l<=k && k<=u ) . atMost
p'