- data Binding k p = k :-> p
- data PSQ k p
- size :: (Ord k, Ord p) => PSQ k p -> Int
- null :: (Ord k, Ord p) => 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
- alter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k p
- delete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p
- adjust :: (Ord k, Ord p) => (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
- toList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
- keys :: (Ord k, Ord p) => PSQ k p -> [k]
- fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
- fromAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
- minView :: (Ord k, Ord p) => PSQ k p -> Maybe (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
- range :: (Ord k, Ord p) => (k, k) -> PSQ k p -> PSQ k p
- atMost :: (Ord k, Ord p) => p -> 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

# Documentation

k :-> p |

lookup :: (Ord k, Ord p) => k -> PSQ k p -> Maybe pSource

O(log n). Determine if a key is in the queue, and its priority.

singleton :: (Ord k, Ord p) => k -> p -> PSQ k pSource

O(1). Construct a queue with a single key/priority binding.

alter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k pSource

O(log n). Alters a priority search queue such that `lookup k (alter f k q) = f (lookup k q)`

. This can be used to insert, delete,
or update a priority in a queue.

adjust :: (Ord k, Ord p) => (p -> p) -> k -> PSQ k p -> PSQ k pSource

O(log n). Adjust the priority of a key in the queue, provided that key exists.

adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k pSource

O(log n). Adjust the priority of a key in the queue, provided that key exists, according to a function which additionally takes the key as a parameter.

update :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k pSource

O(log n). Update or delete a priority in the queue, provided that key exists.

updateWithKey :: (Ord k, Ord p) => (k -> p -> Maybe p) -> k -> PSQ k p -> PSQ k pSource

O(log n). Update or delete a priority in the queue, provided that key exists, according to a function which additionally takes the key as a parameter.

toList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]Source

O(n). Flatten a queue into a list of bindings.

fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k pSource

O(n log n). Construct a queue from a list of bindings.

fromAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k pSource

O(n log n). Contstruct a queue from an already ascending list of bindings. Does not check that the list is sorted.

minView :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p, PSQ k p)Source

O(log n). Split a queue into the element with minimum priority, and the remainder.

findMin :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p)Source

O(1). Find the binding with minimum priority in a queue.

deleteMin :: (Ord k, Ord p) => PSQ k p -> PSQ k pSource

O(log n). Delete the key with minimum priority from a queue.

range :: (Ord k, Ord p) => (k, k) -> PSQ k p -> PSQ k pSource

O(log n). The expression `range (l,u) q`

selects the keys k from q where `l <= k`

and `k <= u`

.

atMost :: (Ord k, Ord p) => p -> PSQ k p -> [Binding k p]Source

O(r (log n)). Finds all the bindings in a queue whose priority is less than the given value.