landlab.utils.stable_priority_queue module

class StablePriorityQueue

Bases: object

Implements a stable priority queue, that tracks insertion order; i.e., this is used to break ties.

See https://docs.python.org/2/library/heapq.html#priority-queue-implementation-notes & https://www.sciencedirect.com/science/article/pii/S0098300413001337

Examples

>>> q = StablePriorityQueue()
>>> q.add_task("b", priority=2)
>>> q.add_task("a", priority=1)
>>> q.add_task(0, priority=0)
>>> q.add_task("c", priority=2)
>>> q.remove_task(0)
>>> q.pop_task()
'a'
>>> q.peek_at_task()
'b'
>>> np.all(q.tasks_currently_in_queue() == np.array(["b", "c"]))
True
>>> q.pop_task()
'b'
>>> np.all(q.tasks_ever_in_queue() == np.array(["b", "a", "0", "c"]))
True

If only ints or floats are loaded into the array, the _in_queue methods return arrays with the corresponding data types:

>>> q = StablePriorityQueue()
>>> q.add_task(2, priority=2)
>>> q.add_task(1, priority=1)
>>> np.issubdtype(q.tasks_currently_in_queue().dtype, np.integer)
True
>>> q = StablePriorityQueue()
>>> q.add_task(np.pi)
>>> np.issubdtype(q.tasks_currently_in_queue().dtype, np.floating)
True

Popping from (or peeking at) an empty queue will throw a KeyError:

>>> q = StablePriorityQueue()
>>> try:
...     q.pop_task()
... except KeyError:
...     print("No tasks left")
...
No tasks left

add_task(task, priority=0)

Add a new task or update the priority of an existing task.

peek_at_task()

Return the lowest priority task without removal.

Raise KeyError if empty.

pop_task()

Remove and return the lowest priority task.

Raise KeyError if empty.

remove_task(task)

Mark an existing task as _REMOVED.

Raise KeyError if not found.

tasks_currently_in_queue()

Return array of nodes currently in the queue.

tasks_ever_in_queue()

Return array of all nodes ever added to this queue object.

Repeats are permitted.