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.