PSQueue-1.1: Priority Search Queue

Data.PSQueue

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

Synopsis

# Binding Type

data Binding k p Source

`k :-> p` binds the key `k` with the priority `p`.

Constructors

 k :-> p

Instances

 (Eq k, Eq p) => Eq (Binding k p) (Ord k, Ord p) => Ord (Binding k p) (Read k, Read p) => Read (Binding k p) (Show k, Show p) => Show (Binding k p)

key :: Binding k p -> kSource

The key of a binding

prio :: Binding k p -> pSource

The priority of a binding

# Priority Search Queue Type

data PSQ k p Source

A mapping from keys `k` to priorites `p`.

Instances

 (Show k, Show p, Ord k, Ord p) => Show (PSQ k p)

# Query

size :: PSQ k p -> IntSource

O(1) The number of bindings in a queue.

null :: PSQ k p -> BoolSource

O(1) True if the queue is empty.

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

empty :: (Ord k, Ord p) => PSQ k pSource

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

O(1) Build a queue with one binding.

# 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

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

O(log n) Remove a binding from the queue.

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.

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

O(log n) The expression (`update f k q`) updates the priority `p` bound `k` (if it is in the queue). If (`f p`) is `Nothing`, the binding is deleted. If it is (`Just z`), the key `k` is bound to the new priority `z`.

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

O(log n). The expression (`updateWithKey f k q`) updates the priority `p` bound `k` (if it is in the queue). If (`f k p`) is `Nothing`, the binding is deleted. If it is (`Just z`), the key `k` is bound to the new priority `z`.

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

O(log n). The expression (`alter f k q`) alters the priority `p` bound to `k`, or absence thereof. alter can be used to insert, delete, or update a priority in a queue.

# Conversion

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

O(n) The keys of a priority queue

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

O(n) Convert a queue to a list.

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'
```

# Fold

foldr :: (Ord k, Ord p) => (Binding k p -> b -> b) -> b -> PSQ k p -> bSource

Right fold over the bindings in the queue, in key order.

foldl :: (Ord k, Ord p) => (b -> Binding k p -> b) -> b -> PSQ k p -> bSource

Left fold over the bindings in the queue, in key order.