Data.NatPSQ

(source)

Ordered Nat Priority Search Queue

Reexports

import public Data.NatPSQ.Internal

Definitions

unsafeInsertNew : Ord p => Key -> p -> v -> NatPSQ p v -> NatPSQ p v

  Internal function to insert a key that is *not* present in the priority queue.

Totality: total
Visibility: export

empty : NatPSQ p v

  The empty queue. O(1)

Totality: total
Visibility: export

singleton : Ord p => Nat -> p -> v -> NatPSQ p v

  Build a queue with one element. O(1)

Totality: total
Visibility: export

null : NatPSQ p v -> Bool

  Is the queue empty? O(1)

Totality: total
Visibility: export

size : NatPSQ p v -> Nat

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

Totality: total
Visibility: export

lookup : Nat -> NatPSQ 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 : Nat -> NatPSQ p v -> Bool

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

Totality: total
Visibility: export

notMember : Nat -> NatPSQ p v -> Bool

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

Totality: total
Visibility: export

findMin : NatPSQ p v -> Maybe (Nat, (p, v))

  The element with the lowest priority. O(1)

Totality: total
Visibility: export

deleteView : Ord p => Nat -> NatPSQ p v -> Maybe (p, (v, NatPSQ 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 : Ord p => Nat -> p -> v -> NatPSQ p v -> (Maybe (p, v), NatPSQ 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 : Ord p => NatPSQ p v -> Maybe (Nat, (p, (v, NatPSQ 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 : Ord p => p -> NatPSQ p v -> (List (Nat, (p, v)), NatPSQ 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 p => Nat -> NatPSQ p v -> NatPSQ 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 : Ord p => NatPSQ p v -> NatPSQ 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

insert : Ord p => Nat -> p -> v -> NatPSQ p v -> NatPSQ 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

alter : Ord p => (Maybe (p, v) -> (b, Maybe (p, v))) -> Nat -> NatPSQ p v -> (b, NatPSQ 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 : Ord p => (Maybe (Nat, (p, v)) -> (b, Maybe (Nat, (p, v)))) -> NatPSQ p v -> (b, NatPSQ 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) -> NatPSQ p v -> NatPSQ p w

  Modify every value in the queue. O(n)

Totality: total
Visibility: export

unsafeMapMonotonic : (Key -> p -> v -> (q, w)) -> NatPSQ p v -> NatPSQ q w

  Maps a function over the values and priorities of the queue.
  The function f must be monotonic with respect to the priorities.
  This means that 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 : (Nat -> p -> v -> a -> a) -> a -> NatPSQ p v -> a

  Fold over every key, priority and value in the queue.
  The order in which the fold is performed is not specified. O(n)

Totality: total
Visibility: export

foldl : (acc -> v -> acc) -> acc -> NatPSQ p v -> acc

Totality: total
Visibility: export

foldr : (v -> acc -> acc) -> acc -> NatPSQ p v -> acc

Totality: total
Visibility: export

fromList : Ord p => List (Nat, (p, v)) -> NatPSQ 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 * min(n, W))

Totality: total
Visibility: export

toList : NatPSQ p v -> List (Nat, (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 : NatPSQ p v -> List Nat

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

Totality: total
Visibility: export