Safe Haskell | None |
---|---|
Language | Haskell2010 |
A priority map is a heap fused with a map. It is a mutable data structure. Its primary advantage is that it allows quick access to the heap, allowing for quick modification or deletion of elements from the heap.
Complexities mentioned in the documentation are valid if the map that is used is a tree map.
Values with the lowest score are placed at the top of the heap.
- data PriorityMap s m km kh v = PriorityMap {}
- type PrioMap s = PriorityMap s MapST
- null :: STMap m => PriorityMap s m km kh v -> ST s Bool
- lookupValue :: (STMap m, Ord km) => PriorityMap s m km kh v -> km -> ST s (Maybe v)
- toList :: STMap m => PriorityMap s m km kh v -> ST s [(km, v)]
- empty :: STMap m => ST s (PriorityMap s m km kh v)
- fromList :: (STMap m, Ord km, Ord kh) => [(km, kh, v)] -> ST s (PriorityMap s m km kh v)
- insert :: (STMap m, Ord kh, Ord km) => PriorityMap s m km kh v -> (km, kh, v) -> ST s ()
- pop :: (STMap m, Ord kh, Ord km) => PriorityMap s m km kh v -> ST s (Maybe (km, kh, v))
- updateValue :: (STMap m, Ord km) => PriorityMap s m km kh v -> km -> (v -> ST s v) -> ST s ()
- updateMapKey :: (STMap m, Ord km) => PriorityMap s m km kh v -> km -> km -> ST s ()
- updatePriority :: (STMap m, Ord km, Ord kh) => PriorityMap s m km kh v -> km -> (v -> kh) -> ST s ()
- delete :: (STMap m, Ord km, Ord kh) => PriorityMap s m km kh v -> km -> ST s ()
- data Info km v = Info Int km v
- updateCallback :: OnUpdate s (k, STRef s (Info km v))
Priority map type
data PriorityMap s m km kh v
A general priority map structure. s
is the state thread in the ST monad,
m
is the map type, km
is the keys for the map, kh
is the keys for
the heap, and v
is the value type.
type PrioMap s = PriorityMap s MapST
The default priority map, which uses an STRef to a Data.Map as its map structure.
Query
null :: STMap m => PriorityMap s m km kh v -> ST s Bool
O(1). Returns true iff the priority map is null.
lookupValue :: (STMap m, Ord km) => PriorityMap s m km kh v -> km -> ST s (Maybe v)
toList :: STMap m => PriorityMap s m km kh v -> ST s [(km, v)]
O(n). Return a list of the map keys and values of all entries currently in the priority map.
Construction
empty :: STMap m => ST s (PriorityMap s m km kh v)
Create a new empty priority map.
fromList :: (STMap m, Ord km, Ord kh) => [(km, kh, v)] -> ST s (PriorityMap s m km kh v)
O(n log n). Create a new priority map from a list of map keys, heap scores, and values. Could be improved in the future to be O(n).
Modification
insert :: (STMap m, Ord kh, Ord km) => PriorityMap s m km kh v -> (km, kh, v) -> ST s ()
O(log n). Insert a value into the priority map. There should not already be an entry with the given map key. If there is, behavior is undefined, and it is likely that bad things will happen!
updateValue :: (STMap m, Ord km) => PriorityMap s m km kh v -> km -> (v -> ST s v) -> ST s ()
O(log n). Modifies the value associated to a given map key. If no entry currently exists for that key, behavior is undefined. Currently, an exception should be raised.
updateMapKey :: (STMap m, Ord km) => PriorityMap s m km kh v -> km -> km -> ST s ()
O(log n). Modifies the map key of an entry. If no entry currently exists for that key, behavior is undefined. Currently, an exception should be raised.
updatePriority :: (STMap m, Ord km, Ord kh) => PriorityMap s m km kh v -> km -> (v -> kh) -> ST s ()
O(log n). Update the priority for a given entry. If no entry currently exists for that key, behavior is undefined. Currently, an exception should be raised.
delete :: (STMap m, Ord km, Ord kh) => PriorityMap s m km kh v -> km -> ST s ()
O(log n). Delete an entry. If no entry currently exists for that key, behavior is undefined. Currently, an exception should be raised.
Internals
These are not part of the API, and may change from version to version.
updateCallback :: OnUpdate s (k, STRef s (Info km v))