Module pqueue3

A Large Priority Queue.

This priority queue implementation depends on layered tuples, so that tuple access times can be exploited for quick in/out priority queue operations when using 64 or more total priorities.

Copyright © 2011-2020 Michael Truog

Version: 2.0.1 Nov 26 2020 14:55:32 ------------------------------------------------------------------------

Authors: Michael Truog (mjtruog at protonmail dot com).

Description

A Large Priority Queue.

This priority queue implementation depends on layered tuples, so that tuple access times can be exploited for quick in/out priority queue operations when using 64 or more total priorities. This implementation was created to avoid the slowness within the priority queue used by both RabbitMQ and Riak (https://github.com/basho/riak_core/blob/master/src/priority_queue.erl).

Data Types

pqueue3()

pqueue3() = {integer(), integer(), empty | integer(), tuple()}

pqueue3_empty()

pqueue3_empty() = {integer(), integer(), empty, tuple()}

Function Index

in/2

Append an item to the tail of the 0 priority queue.

O(1).
in/3

Append an item to the tail of a specific priority queue.

O(1).
is_empty/1

Check if the priority queue is empty.

O(1).
is_queue/1

Check if the priority queue type is as expected.

O(1).
len/1

Determine the length of a priority queue.

O(N).
new/0

Create a new priority queue.

O(1).
new/1

Create a new priority queue with customization options.

O(1).
out/1

Take an item from the head of the priority queue.

O(1) amortized, O(N) worst case.
out/2

Take an item of a specific priority from the head of the queue.

O(1) amortized, O(N) worst case.
pout/1

Take an item from the head of the priority queue.

Includes the priority in the return value.
to_list/1

Convert the priority queue to a list.

O(N).

Function Details

in/2

in(Value::term(), Q::pqueue3()) -> pqueue3()

Append an item to the tail of the 0 priority queue.

O(1)

in/3

in(Value::term(), P::integer(), X3::pqueue3()) -> pqueue3()

Append an item to the tail of a specific priority queue.

O(1)

is_empty/1

is_empty(Q::pqueue3()) -> true | false

Check if the priority queue is empty.

O(1)

is_queue/1

is_queue(X1::pqueue3()) -> true | false

Check if the priority queue type is as expected.

O(1)

len/1

len(Q::pqueue3()) -> non_neg_integer()

Determine the length of a priority queue.

O(N)

new/0

new() -> pqueue3_empty()

Create a new priority queue.

O(1)

new/1

new(Options::[{atom(), term()}]) -> pqueue3()

Create a new priority queue with customization options.

O(1)

out/1

out(Q::pqueue3()) -> {{value, term()}, pqueue3()} | {empty, pqueue3()}

Take an item from the head of the priority queue.

O(1) amortized, O(N) worst case

out/2

out(P::integer(), Q::pqueue3()) -> {{value, term()}, pqueue3()} | {empty, pqueue3()}

Take an item of a specific priority from the head of the queue.

O(1) amortized, O(N) worst case

pout/1

pout(Q::pqueue3()) -> {{value, term(), integer()}, pqueue3()} | {empty, pqueue3()}

Take an item from the head of the priority queue.

Includes the priority in the return value. O(1) amortized, O(N) worst case

to_list/1

to_list(Q::pqueue3()) -> [term()]

Convert the priority queue to a list.

O(N)


Generated by EDoc