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

Language | Haskell98 |

## Synopsis

- data IntPSQ p v
- null :: IntPSQ p v -> Bool
- size :: IntPSQ p v -> Int
- member :: Int -> IntPSQ p v -> Bool
- lookup :: Int -> IntPSQ p v -> Maybe (p, v)
- findMin :: Ord p => IntPSQ p v -> Maybe (Int, p, v)
- empty :: IntPSQ p v
- singleton :: Ord p => Int -> p -> v -> IntPSQ p v
- insert :: Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v
- delete :: Ord p => Int -> IntPSQ p v -> IntPSQ p v
- deleteMin :: Ord p => IntPSQ p v -> IntPSQ p v
- alter :: Ord p => (Maybe (p, v) -> (b, Maybe (p, v))) -> Int -> IntPSQ p v -> (b, IntPSQ p v)
- alterMin :: Ord p => (Maybe (Int, p, v) -> (b, Maybe (Int, p, v))) -> IntPSQ p v -> (b, IntPSQ p v)
- fromList :: Ord p => [(Int, p, v)] -> IntPSQ p v
- toList :: IntPSQ p v -> [(Int, p, v)]
- keys :: IntPSQ p v -> [Int]
- insertView :: Ord p => Int -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v)
- deleteView :: Ord p => Int -> IntPSQ p v -> Maybe (p, v, IntPSQ p v)
- minView :: Ord p => IntPSQ p v -> Maybe (Int, p, v, IntPSQ p v)
- atMostView :: Ord p => p -> IntPSQ p v -> ([(Int, p, v)], IntPSQ p v)
- map :: (Int -> p -> v -> w) -> IntPSQ p v -> IntPSQ p w
- unsafeMapMonotonic :: (Key -> p -> v -> (q, w)) -> IntPSQ p v -> IntPSQ q w
- fold' :: (Int -> p -> v -> a -> a) -> a -> IntPSQ p v -> a
- unsafeInsertNew :: Ord p => Key -> p -> v -> IntPSQ p v -> IntPSQ p v
- unsafeInsertIncreasePriority :: Ord p => Key -> p -> v -> IntPSQ p v -> IntPSQ p v
- unsafeInsertIncreasePriorityView :: Ord p => Key -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v)
- unsafeInsertWithIncreasePriority :: Ord p => (p -> v -> p -> v -> (p, v)) -> Key -> p -> v -> IntPSQ p v -> IntPSQ p v
- unsafeInsertWithIncreasePriorityView :: Ord p => (p -> v -> p -> v -> (p, v)) -> Key -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v)
- unsafeLookupIncreasePriority :: Ord p => (p -> v -> (Maybe b, p, v)) -> Key -> IntPSQ p v -> (Maybe b, IntPSQ p v)
- valid :: Ord p => IntPSQ p v -> Bool

# Type

A priority search queue with `Int`

keys and priorities of type `p`

and
values of type `v`

. It is strict in keys, priorities and values.

## Instances

Functor (IntPSQ p) Source # | |

Foldable (IntPSQ p) Source # | |

Defined in Data.IntPSQ.Internal fold :: Monoid m => IntPSQ p m -> m # foldMap :: Monoid m => (a -> m) -> IntPSQ p a -> m # foldr :: (a -> b -> b) -> b -> IntPSQ p a -> b # foldr' :: (a -> b -> b) -> b -> IntPSQ p a -> b # foldl :: (b -> a -> b) -> b -> IntPSQ p a -> b # foldl' :: (b -> a -> b) -> b -> IntPSQ p a -> b # foldr1 :: (a -> a -> a) -> IntPSQ p a -> a # foldl1 :: (a -> a -> a) -> IntPSQ p a -> a # elem :: Eq a => a -> IntPSQ p a -> Bool # maximum :: Ord a => IntPSQ p a -> a # minimum :: Ord a => IntPSQ p a -> a # | |

Traversable (IntPSQ p) Source # | |

(Ord p, Eq v) => Eq (IntPSQ p v) Source # | |

(Show p, Show v) => Show (IntPSQ p v) Source # | |

(NFData p, NFData v) => NFData (IntPSQ p v) Source # | |

Defined in Data.IntPSQ.Internal |

# Query

lookup :: Int -> IntPSQ p v -> Maybe (p, v) Source #

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

if the
key is not bound.

findMin :: Ord p => IntPSQ p v -> Maybe (Int, p, v) Source #

*O(1)* The element with the lowest priority.

# Construction

# Insertion

insert :: Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v Source #

*O(min(n,W))* 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.

# Delete/update

delete :: Ord p => Int -> IntPSQ p v -> IntPSQ p v Source #

*O(min(n,W))* 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.

deleteMin :: Ord p => IntPSQ p v -> IntPSQ p v Source #

*O(min(n,W))* Delete the binding with the least priority, and return the
rest of the queue stripped of that binding. In case the queue is empty, the
empty queue is returned again.

alter :: Ord p => (Maybe (p, v) -> (b, Maybe (p, v))) -> Int -> IntPSQ p v -> (b, IntPSQ p v) Source #

*O(min(n,W))* 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 p => (Maybe (Int, p, v) -> (b, Maybe (Int, p, v))) -> IntPSQ p v -> (b, IntPSQ p v) Source #

# Lists

fromList :: Ord p => [(Int, p, v)] -> IntPSQ p v Source #

*O(n*min(n,W))* 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.

toList :: IntPSQ p v -> [(Int, p, v)] Source #

*O(n)* Convert a queue to a list of (key, priority, value) tuples. The
order of the list is not specified.

# Views

insertView :: Ord p => Int -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v) Source #

*O(min(n,W))* 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.

deleteView :: Ord p => Int -> IntPSQ p v -> Maybe (p, v, IntPSQ p v) Source #

*O(min(n,W))* 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.

minView :: Ord p => IntPSQ p v -> Maybe (Int, p, v, IntPSQ p v) Source #

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

atMostView :: Ord p => p -> IntPSQ p v -> ([(Int, p, v)], IntPSQ p v) Source #

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.

# Traversal

map :: (Int -> p -> v -> w) -> IntPSQ p v -> IntPSQ p w Source #

*O(n)* Modify every value in the queue.

unsafeMapMonotonic :: (Key -> p -> v -> (q, w)) -> IntPSQ p v -> IntPSQ q w Source #

*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.

fold' :: (Int -> p -> v -> a -> a) -> a -> IntPSQ p v -> a Source #

*O(n)* Strict fold over every key, priority and value in the queue. The order
in which the fold is performed is not specified.

# Unsafe operations

unsafeInsertNew :: Ord p => Key -> p -> v -> IntPSQ p v -> IntPSQ p v Source #

Internal function to insert a key that is *not* present in the priority queue.

unsafeInsertIncreasePriority :: Ord p => Key -> p -> v -> IntPSQ p v -> IntPSQ p v Source #

Internal function to insert a key with priority larger than the maximal priority in the heap. This is always the case when using the PSQ as the basis to implement a LRU cache, which associates a access-tick-number with every element.

unsafeInsertIncreasePriorityView :: Ord p => Key -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v) Source #

unsafeInsertWithIncreasePriority :: Ord p => (p -> v -> p -> v -> (p, v)) -> Key -> p -> v -> IntPSQ p v -> IntPSQ p v Source #

This name is not chosen well anymore. This function:

- Either inserts a value at a new key with a prio higher than the max of the entire PSQ.
- Or, overrides the value at the key with a prio strictly higher than the original prio at that key (but not necessarily the max of the entire PSQ).

unsafeInsertWithIncreasePriorityView :: Ord p => (p -> v -> p -> v -> (p, v)) -> Key -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v) Source #

unsafeLookupIncreasePriority :: Ord p => (p -> v -> (Maybe b, p, v)) -> Key -> IntPSQ p v -> (Maybe b, IntPSQ p v) Source #

This can NOT be used to delete elements.