priority-map-0.1.0.0: The priority map data structure is a map combined with a heap

Safe HaskellNone
LanguageHaskell2010

Data.PriorityMap

Contents

Description

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.

Synopsis

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.

Constructors

PriorityMap 

Fields

pmmap :: m s km (STRef s (Info km v))

the map

pmheap :: Heap s kh (STRef s (Info km v))

the heap

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)

O(log n). Checks whether there is an element in the priority map with the given map key; if there is not, returns Nothing, and if there is, returns Just the value associated with that key.

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!

pop :: (STMap m, Ord kh, Ord km) => PriorityMap s m km kh v -> ST s (Maybe (km, kh, v))

O(log n). If the priority map is empty, returns Nothing. If the priority map is not empty, removes the entry with the lowest score from the heap and returns Just that entry.

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.

data Info km v

Constructors

Info Int km v 

Instances

(Show km, Show v) => Show (Info km v) 

updateCallback :: OnUpdate s (k, STRef s (Info km v))