Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

## Synopsis

- data OrdPSQ k p v
- empty :: OrdPSQ k p v
- singleton :: k -> p -> v -> OrdPSQ k p v
- fromList :: (Ord k, Ord p) => [(k, p, v)] -> OrdPSQ k p v
- null :: OrdPSQ k p v -> Bool
- size :: OrdPSQ k p v -> Int
- member :: Ord k => k -> OrdPSQ k p v -> Bool
- lookup :: Ord k => k -> OrdPSQ k p v -> Maybe (p, v)
- findMin :: OrdPSQ k p v -> Maybe (k, p, v)
- minView :: (Ord k, Ord p) => OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v)
- atMostView :: (Ord k, Ord p) => p -> OrdPSQ k p v -> ([(k, p, v)], OrdPSQ k p v)
- insert :: (Ord k, Ord p) => k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
- insertView :: (Ord k, Ord p) => k -> p -> v -> OrdPSQ k p v -> (Maybe (p, v), OrdPSQ k p v)
- delete :: (Ord k, Ord p) => k -> OrdPSQ k p v -> OrdPSQ k p v
- deleteView :: (Ord k, Ord p) => k -> OrdPSQ k p v -> Maybe (p, v, OrdPSQ k p v)
- alter :: (Ord k, Ord p) => (Maybe (p, v) -> (b, Maybe (p, v))) -> k -> OrdPSQ k p v -> (b, OrdPSQ k p v)
- alterMin :: (Ord k, Ord p) => (Maybe (k, p, v) -> (b, Maybe (k, p, v))) -> OrdPSQ k p v -> (b, OrdPSQ k p v)
- map :: (k -> p -> v -> w) -> OrdPSQ k p v -> OrdPSQ k p w
- unsafeMapMonotonic :: (k -> p -> v -> (q, w)) -> OrdPSQ k p v -> OrdPSQ k q w
- toList :: OrdPSQ k p v -> [(k, p, v)]
- toAscList :: OrdPSQ k p v -> [(k, p, v)]
- keys :: OrdPSQ k p v -> [k]
- fold' :: (k -> p -> v -> a -> a) -> a -> OrdPSQ k p v -> a

# OrdPSQ

A mapping from keys `k`

to priorites `p`

and values `v`

. It is strict in
keys, priorities and values.

## Instances

Functor (OrdPSQ k p) | |

Foldable (OrdPSQ k p) | |

Defined in Data.OrdPSQ.Internal fold :: Monoid m => OrdPSQ k p m -> m # foldMap :: Monoid m => (a -> m) -> OrdPSQ k p a -> m # foldr :: (a -> b -> b) -> b -> OrdPSQ k p a -> b # foldr' :: (a -> b -> b) -> b -> OrdPSQ k p a -> b # foldl :: (b -> a -> b) -> b -> OrdPSQ k p a -> b # foldl' :: (b -> a -> b) -> b -> OrdPSQ k p a -> b # foldr1 :: (a -> a -> a) -> OrdPSQ k p a -> a # foldl1 :: (a -> a -> a) -> OrdPSQ k p a -> a # toList :: OrdPSQ k p a -> [a] # null :: OrdPSQ k p a -> Bool # length :: OrdPSQ k p a -> Int # elem :: Eq a => a -> OrdPSQ k p a -> Bool # maximum :: Ord a => OrdPSQ k p a -> a # minimum :: Ord a => OrdPSQ k p a -> a # | |

Traversable (OrdPSQ k p) | |

Defined in Data.OrdPSQ.Internal | |

(Ord k, Ord p, Eq v) => Eq (OrdPSQ k p v) | |

(Show k, Show p, Show v) => Show (OrdPSQ k p v) | |

(NFData k, NFData p, NFData v) => NFData (OrdPSQ k p v) | |

Defined in Data.OrdPSQ.Internal |

# Construction

fromList :: (Ord k, Ord p) => [(k, p, v)] -> OrdPSQ k p v #

*O(n*log n)* Build a queue from a list of (key, priority, value) tuples.
If the list contains more than one priority and value for the same key, the
last priority and value for the key is retained.

# Querying

lookup :: Ord k => k -> OrdPSQ k p v -> Maybe (p, v) #

*O(log n)* The priority and value of a given key, or `Nothing`

if the key
is not bound.

minView :: (Ord k, Ord p) => OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v) #

*O(log n)* Retrieve the binding with the least priority, and the
rest of the queue stripped of that binding.

atMostView :: (Ord k, Ord p) => p -> OrdPSQ k p v -> ([(k, p, v)], OrdPSQ k p v) #

Return a list of elements ordered by key whose priorities are at most `pt`

,
and the rest of the queue stripped of these elements. The returned list of
elements can be in any order: no guarantees there.

# Insertion

insert :: (Ord k, Ord p) => k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v #

*O(log n)* Insert a new key, priority and value into the queue. If the key is
already present in the queue, the associated priority and value are replaced
with the supplied priority and value.

insertView :: (Ord k, Ord p) => k -> p -> v -> OrdPSQ k p v -> (Maybe (p, v), OrdPSQ k p v) #

*O(log n)* Insert a new key, priority and value into the queue. If the key is
already present in the queue, then the evicted priority and value can be
found the first element of the returned tuple.

# Deletion

delete :: (Ord k, Ord p) => k -> OrdPSQ k p v -> OrdPSQ k p v #

*O(log n)* Delete a key and its priority and value from the queue. When the
key is not a member of the queue, the original queue is returned.

deleteView :: (Ord k, Ord p) => k -> OrdPSQ k p v -> Maybe (p, v, OrdPSQ k p v) #

*O(log n)* Delete a key and its priority and value from the queue. If the
key was present, the associated priority and value are returned in addition
to the updated queue.

# Alteration

alter :: (Ord k, Ord p) => (Maybe (p, v) -> (b, Maybe (p, v))) -> k -> OrdPSQ k p v -> (b, OrdPSQ k p v) #

*O(log n)* The expression `alter f k queue`

alters the value `x`

at `k`

, or
absence thereof. `alter`

can be used to insert, delete, or update a value
in a queue. It also allows you to calculate an additional value `b`

.

alterMin :: (Ord k, Ord p) => (Maybe (k, p, v) -> (b, Maybe (k, p, v))) -> OrdPSQ k p v -> (b, OrdPSQ k p v) #

# Mapping

unsafeMapMonotonic :: (k -> p -> v -> (q, w)) -> OrdPSQ k p v -> OrdPSQ k q w #

*O(n)* Maps a function over the values and priorities of the queue.
The function `f`

must be monotonic with respect to the priorities. I.e. if
`x < y`

, then `fst (f k x v) < fst (f k y v)`

.
*The precondition is not checked.* If `f`

is not monotonic, then the result
will be invalid.