sc_priority_queue.md

Module sc_priority_queue

• Description
• Data Types
• Function Index
• Function Details

Priority queues have essentially the same interface as ordinary queues, except that a) there is an in/3 that takes a priority, and b) we have only implemented the core API we need.

Description

Priorities should be integers - the higher the value the higher the priority - but we don't actually check that.

in/2 inserts items with priority 0.

We optimise the case where a priority queue is being used just like an ordinary queue. When that is the case we represent the priority queue as an ordinary queue. We could just call into the queue module for that, but for efficiency we implement the relevant functions directly in here, thus saving on inter-module calls and eliminating a level of boxing.

When the queue contains items with non-zero priorities, it is represented as a sorted kv list with the inverted priority as the key and an ordinary queue as the value. Here again we use our own ordinary queue implemention for efficiency, often making recursive calls into the same function knowing that ordinary queues represent a base case.

Data Types

pqueue()

pqueue() = squeue() | {pqueue, [{priority(), squeue()}]}

priority()

priority() = integer() | infinity

q()

q() = pqueue()

squeue()

squeue() = {queue, [any()], [any()], non_neg_integer()}

Function Index

filter/2
fold/3
from_list/1
highest/1
in/2
in/3
is_empty/1
is_queue/1
join/2
len/1
new/0
out/1
out_p/1
to_list/1

Function Details

filter/2

filter(Pred::fun((any()) -> boolean()), Q::pqueue()) -> pqueue()

fold/3

fold(Fun::fun((any(), priority(), A) -> A), A, Q::pqueue()) -> A

from_list/1

from_list(L::[{priority(), any()}]) -> pqueue()

highest/1

highest(X1::pqueue()) -> priority() | empty

in/2

in(Item::any(), Q::pqueue()) -> pqueue()

in/3

in(X::any(), Priority::priority(), Q::pqueue()) -> pqueue()

is_empty/1

is_empty(X1::pqueue()) -> boolean()

is_queue/1

is_queue(X1::any()) -> boolean()

join/2

join(A::pqueue(), B::pqueue()) -> pqueue()

len/1

len(X1::pqueue()) -> non_neg_integer()

new/0

new() -> pqueue()

out/1

out(Q::pqueue()) -> {empty | {value, any()}, pqueue()}

out_p/1

out_p(Q::pqueue()) -> {empty | {value, any(), priority()}, pqueue()}

to_list/1

to_list(X1::pqueue()) -> [{priority(), any()}]