Data.HashPSQ

Hash Priority Search Queue

Reexports

Definitions

insert : Hashable k => Ord k => Ord p => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v

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

Totality: total
Visibility: export

empty : HashPSQ k p v

  The empty queue. O(1)

Totality: total
Visibility: export

singleton : Hashable k => Ord k => Ord p => k -> p -> v -> HashPSQ k p v

  Build a queue with one element. O(1)

Totality: total
Visibility: export

null : HashPSQ k p v -> Bool

  Is the queue empty? O(1)

Totality: total
Visibility: export

size : HashPSQ k p v -> Nat

  The number of elements in a queue. O(n)

Totality: total
Visibility: export

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

  The priority and value of a given key, or Nothing if the
  key is not bound. O(min(n ,W))

Totality: total
Visibility: export

member : Hashable k => Ord k => Ord p => k -> HashPSQ k p v -> Bool

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

Totality: total
Visibility: export

notMember : Hashable k => Ord k => Ord p => k -> HashPSQ k p v -> Bool

  Is the key not a member of the queue? See also member. O(log n)

Totality: total
Visibility: export

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

  The element with the lowest priority. O(1)

Totality: total
Visibility: export

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

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

Totality: total
Visibility: export

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

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

Totality: total
Visibility: export

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

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

Totality: total
Visibility: export

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

  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.

Totality: total
Visibility: export

delete : Hashable k => Ord k => Ord p => k -> HashPSQ k p v -> HashPSQ k p v

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

Totality: total
Visibility: export

deleteMin : Hashable k => Ord k => Ord p => HashPSQ k p v -> HashPSQ k p v

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

Totality: total
Visibility: export

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

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

Totality: total
Visibility: export

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)

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

Totality: total
Visibility: export

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

  Modify every value in the queue. O(n)

Totality: total
Visibility: export

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

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

Totality: total
Visibility: export

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

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

Totality: total
Visibility: export

keys : Hashable k => Ord k => Ord p => HashPSQ k p v -> List k

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

Totality: total
Visibility: export