Modulepsqueues-0.2.8.3Haskell2010

Data.HashPSQ

A HashPSQ offers very similar performance to IntPSQ. In case of collisions, it uses an OrdPSQ locally to solve those.

This means worst case complexity is usually given by O(min(n,W), log n), where W is the number of bits in an Int. This simplifies to O(min(n,W)) since log n is always smaller than W on current machines.

Contents

Type
Query
Construction
Insertion
Delete/update
Lists
Views
Traversal
Unsafe operations
Validity check

Synopsis

newtype HashPSQ
value null
value size
value member
value lookup
value findMin
value empty
value singleton
value insert
value delete
value deleteMin
value alter
value alterMin
value fromList
value toList
value keys
value insertView
value deleteView
value minView
value atMostView
value map
value unsafeMapMonotonic
value fold'
value unsafeLookupIncreasePriority
value unsafeInsertIncreasePriority
value unsafeInsertIncreasePriorityView
value valid

Packagepsqueues-0.2.8.3
Exports27
LanguageHaskell2010
LicenceBSD-3-Clause
SourceHashPSQ.hs

Type

newtypenewtype HashPSQ k p v

Source#

A priority search queue with keys of type k and priorities of type p and values of type v. It is strict in keys, priorities and values.

Instances6Functor, Foldable, Traversable, Eq, Show, NFData

Functor (HashPSQ k p)Defined in psqueues-0.2.8.3 · Data.HashPSQ.Internal
Foldable (HashPSQ k p)Defined in psqueues-0.2.8.3 · Data.HashPSQ.Internal
Traversable (HashPSQ k p)Defined in psqueues-0.2.8.3 · Data.HashPSQ.Internal
(Eq k, Eq p, Eq v, Hashable k, Ord k, Ord p) => Eq (HashPSQ k p v)Defined in psqueues-0.2.8.3 · Data.HashPSQ.Internal
(Show p, Show k, Show v) => Show (HashPSQ k p v)Defined in psqueues-0.2.8.3 · Data.HashPSQ.Internal
(NFData p, NFData k, NFData v) => NFData (HashPSQ k p v)Defined in psqueues-0.2.8.3 · Data.HashPSQ.Internal

Query

valuenull :: HashPSQ k p v -> Bool

Source#

O(1) True if the queue is empty.

valuesize :: HashPSQ k p v -> Int

Source#

O(n) The number of elements stored in the PSQ.

valuemember :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Bool

Source#

O(min(n,W)) Check if a key is present in the the queue.

valuelookup :: (Ord k, Hashable k, Ord p) => k -> HashPSQ k 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.

valuefindMin :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v)

Source#

O(1) The element with the lowest priority.

Construction

valueempty :: HashPSQ k p v

Source#

O(1) The empty queue.

valuesingleton :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v

Source#

O(1) Build a queue with one element.

Insertion

valueinsert

:: (Ord k, Hashable k, Ord p)
=> k
-> p
-> v
-> HashPSQ k p v
-> HashPSQ k 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

valuedelete :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> HashPSQ k 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.

valuedeleteMin :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> HashPSQ k 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.

valuealter

:: (Hashable k, Ord k, Ord p)
=> Maybe (p, v) -> (b, Maybe (p, v))
-> k
-> HashPSQ k p v
-> (b, HashPSQ k 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.

valuealterMin

:: (Hashable k, Ord k, Ord p)
=> Maybe (k, p, v) -> (b, Maybe (k, p, v))
-> HashPSQ k p v
-> (b, HashPSQ k p v)

Source#

O(min(n,W)) A variant of alter which works on the element with the minimum priority. Unlike alter, this variant also allows you to change the key of the element.

Lists

valuefromList :: (Hashable k, Ord k, Ord p) => [(k, p, v)] -> HashPSQ k 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.

valuetoList :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [(k, p, v)]

Source#

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

valuekeys :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [k]

Source#

O(n) Obtain the list of present keys in the queue.

Views

valueinsertView

:: (Hashable k, Ord k, Ord p)
=> k
-> p
-> v
-> HashPSQ k p v
-> (Maybe (p, v), HashPSQ k 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.

valuedeleteView

:: (Hashable k, Ord k, Ord p)
=> k
-> HashPSQ k p v
-> Maybe (p, v, HashPSQ k 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.

valueminView

:: (Hashable k, Ord k, Ord p)
=> HashPSQ k p v
-> Maybe (k, p, v, HashPSQ k p v)

Source#

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

valueatMostView

:: (Hashable k, Ord k, Ord p)
=> p
-> HashPSQ k p v
-> ([(k, p, v)], HashPSQ k 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

valuemap :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w

Source#

O(n) Modify every value in the queue.

valueunsafeMapMonotonic

:: k -> p -> v -> (q, w)
-> HashPSQ k p v
-> HashPSQ k 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.

valuefold' :: (k -> p -> v -> a -> a) -> a -> HashPSQ k 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

valueunsafeLookupIncreasePriority

:: (Hashable k, Ord k, Ord p)
=> k
-> p
-> HashPSQ k p v
-> (Maybe (p, v), HashPSQ k p v)

valueunsafeInsertIncreasePriority

:: (Hashable k, Ord k, Ord p)
=> k
-> p
-> v
-> HashPSQ k p v
-> HashPSQ k p v

valueunsafeInsertIncreasePriorityView

:: (Hashable k, Ord k, Ord p)
=> k
-> p
-> v
-> HashPSQ k p v
-> (Maybe (p, v), HashPSQ k p v)

Validity check

valuevalid :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Bool

Source#

O(n^2) Internal function to check if the HashPSQ is valid, i.e. if all invariants hold. This should always be the case.