| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.HashPSQ
Description
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.
Synopsis
- data HashPSQ k p v
- null :: HashPSQ k p v -> Bool
- size :: HashPSQ k p v -> Int
- member :: ( Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Bool
- lookup :: ( Ord k, Hashable k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v)
- findMin :: ( Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v)
- empty :: HashPSQ k p v
- singleton :: ( Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v
- insert :: ( Ord k, Hashable k, Ord p) => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
- delete :: ( Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> HashPSQ k p v
- deleteMin :: ( Hashable k, Ord k, Ord p) => HashPSQ k p v -> HashPSQ k p v
- alter :: ( Hashable k, Ord k, Ord p) => ( Maybe (p, v) -> (b, Maybe (p, v))) -> k -> HashPSQ k p v -> (b, HashPSQ k p v)
- alterMin :: ( Hashable k, Ord k, Ord p) => ( Maybe (k, p, v) -> (b, Maybe (k, p, v))) -> HashPSQ k p v -> (b, HashPSQ k p v)
- fromList :: ( Hashable k, Ord k, Ord p) => [(k, p, v)] -> HashPSQ k p v
- toList :: ( Hashable k, Ord k, Ord p) => HashPSQ k p v -> [(k, p, v)]
- keys :: ( Hashable k, Ord k, Ord p) => HashPSQ k p v -> [k]
- insertView :: ( Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> ( Maybe (p, v), HashPSQ k p v)
- deleteView :: forall k p v. ( Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v)
- minView :: ( Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)
- atMostView :: ( Hashable k, Ord k, Ord p) => p -> HashPSQ k p v -> ([(k, p, v)], HashPSQ k p v)
- map :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w
- unsafeMapMonotonic :: (k -> p -> v -> (q, w)) -> HashPSQ k p v -> HashPSQ k q w
- fold' :: (k -> p -> v -> a -> a) -> a -> HashPSQ k p v -> a
- unsafeLookupIncreasePriority :: ( Hashable k, Ord k, Ord p) => k -> p -> HashPSQ k p v -> ( Maybe (p, v), HashPSQ k p v)
- unsafeInsertIncreasePriority :: ( Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
- unsafeInsertIncreasePriorityView :: ( Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> ( Maybe (p, v), HashPSQ k p v)
- valid :: ( Hashable k, Ord k, Ord p) => HashPSQ k p v -> Bool
Type
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.
Instances
| Functor ( HashPSQ k p) Source # | |
| Foldable ( HashPSQ k p) Source # | |
|
Defined in Data.HashPSQ.Internal Methods fold :: Monoid m => HashPSQ k p m -> m Source # foldMap :: Monoid m => (a -> m) -> HashPSQ k p a -> m Source # foldMap' :: Monoid m => (a -> m) -> HashPSQ k p a -> m Source # foldr :: (a -> b -> b) -> b -> HashPSQ k p a -> b Source # foldr' :: (a -> b -> b) -> b -> HashPSQ k p a -> b Source # foldl :: (b -> a -> b) -> b -> HashPSQ k p a -> b Source # foldl' :: (b -> a -> b) -> b -> HashPSQ k p a -> b Source # foldr1 :: (a -> a -> a) -> HashPSQ k p a -> a Source # foldl1 :: (a -> a -> a) -> HashPSQ k p a -> a Source # toList :: HashPSQ k p a -> [a] Source # null :: HashPSQ k p a -> Bool Source # length :: HashPSQ k p a -> Int Source # elem :: Eq a => a -> HashPSQ k p a -> Bool Source # maximum :: Ord a => HashPSQ k p a -> a Source # minimum :: Ord a => HashPSQ k p a -> a Source # |
|
| Traversable ( HashPSQ k p) Source # | |
|
Defined in Data.HashPSQ.Internal Methods traverse :: Applicative f => (a -> f b) -> HashPSQ k p a -> f ( HashPSQ k p b) Source # sequenceA :: Applicative f => HashPSQ k p (f a) -> f ( HashPSQ k p a) Source # mapM :: Monad m => (a -> m b) -> HashPSQ k p a -> m ( HashPSQ k p b) Source # sequence :: Monad m => HashPSQ k p (m a) -> m ( HashPSQ k p a) Source # |
|
| ( Eq k, Eq p, Eq v, Hashable k, Ord k, Ord p) => Eq ( HashPSQ k p v) Source # | |
| ( Show p, Show k, Show v) => Show ( HashPSQ k p v) Source # | |
| ( NFData p, NFData k, NFData v) => NFData ( HashPSQ k p v) Source # | |
|
Defined in Data.HashPSQ.Internal |
|
Query
member :: ( 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.
lookup :: ( 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.
findMin :: ( Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v) Source #
O(1) The element with the lowest priority.
Construction
singleton :: ( Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v Source #
O(1) Build a queue with one element.
Insertion
insert :: ( 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
delete :: ( 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.
deleteMin :: ( 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.
alter :: ( 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
.
alterMin :: ( 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 #
Lists
fromList :: ( 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.
toList :: ( 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.
keys :: ( Hashable k, Ord k, Ord p) => HashPSQ k p v -> [k] Source #
O(n) Obtain the list of present keys in the queue.
Views
insertView :: ( 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.
deleteView :: forall k p v. ( 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.
minView :: ( 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.
atMostView :: ( 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
map :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w Source #
O(n) Modify every value in the queue.
unsafeMapMonotonic :: (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.
fold' :: (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
unsafeLookupIncreasePriority :: ( Hashable k, Ord k, Ord p) => k -> p -> HashPSQ k p v -> ( Maybe (p, v), HashPSQ k p v) Source #
unsafeInsertIncreasePriority :: ( Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v Source #
unsafeInsertIncreasePriorityView :: ( Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> ( Maybe (p, v), HashPSQ k p v) Source #