Data.OrdPSQ

Ordered Priority Search Queue

Reexports

Definitions

empty : OrdPSQ k p v

  The empty queue. O(1)

Totality: total
Visibility: export

singleton : k -> p -> v -> OrdPSQ k p v

  Build a queue with one element. O(1)

Totality: total
Visibility: export

null : OrdPSQ k p v -> Bool

  Is the queue empty? O(1)

Totality: total
Visibility: export

size : OrdPSQ k p v -> Nat

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

Totality: total
Visibility: export

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

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

Totality: total
Visibility: export

member : Ord k => k -> OrdPSQ k p v -> Bool

  Check if a key is present in the queue. O(log n)

Totality: total
Visibility: export

notMember : Ord k => k -> OrdPSQ k p v -> Bool

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

Totality: total
Visibility: export

findMin : OrdPSQ k p v -> Maybe (k, (p, v))

  The element with the lowest priority. O(1)

Totality: total
Visibility: export

insert : Ord k => Ord p => k -> p -> v -> OrdPSQ k p v -> OrdPSQ 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(log n)

Totality: total
Visibility: export

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

  Modify every value in the queue. O(n)

Totality: total
Visibility: export

unsafeMapMonotonic : (k -> p -> v -> (q, w)) -> OrdPSQ k p v -> OrdPSQ k q w

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

Totality: total
Visibility: export

fold : (k -> p -> v -> a -> a) -> a -> OrdPSQ k p v -> a

  Fold over every key, priority and value in the queue. O(n)

Totality: total
Visibility: export

foldr : (a -> b -> b) -> b -> OrdPSQ k p a -> b

Totality: total
Visibility: export

foldl : (b -> a -> b) -> b -> OrdPSQ k p a -> b

Totality: total
Visibility: export

deleteView : Ord k => Ord p => k -> OrdPSQ k p v -> Maybe (p, (v, OrdPSQ 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(log n)

Totality: total
Visibility: export

insertView : Ord k => Ord p => k -> p -> v -> OrdPSQ k p v -> (Maybe (p, v), OrdPSQ 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(log n)

Totality: total
Visibility: export

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

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

Totality: total
Visibility: export

atMostView : Ord k => Ord p => p -> OrdPSQ k p v -> (List (k, (p, v)), OrdPSQ 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 : Ord k => Ord p => k -> OrdPSQ k p v -> OrdPSQ k p v

  Delete a key, its priority, and its value from the queue.
  When the key is not a member of the queue,
  the original queue is returned. O(log n)

Totality: total
Visibility: export

deleteMin : Ord k => Ord p => OrdPSQ k p v -> OrdPSQ 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(log n)

Totality: total
Visibility: export

alter : Ord k => Ord p => (Maybe (p, v) -> (b, Maybe (p, v))) -> k -> OrdPSQ k p v -> (b, OrdPSQ 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(log n)

Totality: total
Visibility: export

alterMin : Ord k => Ord p => (Maybe (k, (p, v)) -> (b, Maybe (k, (p, v)))) -> OrdPSQ k p v -> (b, OrdPSQ 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(log n)

Totality: total
Visibility: export

fromList : Ord k => Ord p => List (k, (p, v)) -> OrdPSQ 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(n * log n)

Totality: total
Visibility: export

toList : OrdPSQ k p v -> List (k, (p, v))

  Convert a queue to a list of (key, priority, value) tuples. O(n)

Totality: total
Visibility: export

keys : OrdPSQ k p v -> List k

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

Totality: total
Visibility: export