Module pqueue4

Description
Data Types
Function Index
Function Details

Static Priority Queue.

This priority queue implementation depends on a static number of priorities (-128 (high) to 128 (low)) so that tuple access times can be exploited for quick in/out priority queue operations.

Copyright © 2011-2020 Michael Truog

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

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

Description

Static Priority Queue.

This priority queue implementation depends on a static number of priorities (-128 (high) to 128 (low)) so that tuple access times can be exploited for quick in/out priority queue operations. 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

pqueue4()

pqueue4() = pqueue4(any())

pqueue4()

pqueue4(T) = {priority() | empty, non_neg_integer(), {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, queue:queue(T), {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}, {queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T), queue:queue(T)}}

priority()

priority() = -128..128

Function Index

filter/2	Filter the priority queue. O(N).
filter/3	Filter a specific priority within the priority queue. O(N).
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(1).
new/0	Create a new priority queue. 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.
remove_unique/2	Remove a unique value from the priority queue with a binary predicate. O(N) but smaller constant than filter/2.
remove_unique/3	Remove a unique value in a specific priority within the priority queue with a binary predicate. O(N) but smaller constant than filter/3.
to_list/1	Convert the priority queue to a list. O(N).
to_plist/1	Convert the priority queue to a list with priorities. O(N).

Function Details

filter/2

filter(F::fun((any()) -> boolean()), Q::pqueue4()) -> pqueue4()

Filter the priority queue.

O(N)

filter/3

filter(F::fun((any()) -> boolean()), P::integer(), Q::pqueue4()) -> pqueue4()

Filter a specific priority within the priority queue.

O(N)

in/2

in(X::any(), Q::pqueue4()) -> pqueue4()

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

O(1)

in/3

in(X::any(), P::integer(), Q::pqueue4()) -> pqueue4()

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

O(1)

is_empty/1

is_empty(X1::pqueue4()) -> true | false

Check if the priority queue is empty.

O(1)

is_queue/1

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

Check if the priority queue type is as expected.

O(1)

len/1

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

Determine the length of a priority queue.

O(1)

new/0

new() -> pqueue4()

Create a new priority queue.

O(1)

out/1

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

Take an item from the head of the priority queue.

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

out/2

out(P::integer(), Q::pqueue4()) -> {{value, any()}, pqueue4()} | {empty, pqueue4()}

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

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

pout/1

pout(Q::pqueue4()) -> {{value, any(), integer()}, pqueue4()} | {empty, pqueue4()}

Take an item from the head of the priority queue.

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

remove_unique/2

remove_unique(F::fun((any()) -> boolean()), Q::pqueue4()) -> {boolean(), pqueue4()}

Remove a unique value from the priority queue with a binary predicate.

O(N) but smaller constant than filter/2

remove_unique/3

remove_unique(F::fun((any()) -> boolean()), P::integer(), Q::pqueue4()) -> {boolean(), pqueue4()}

Remove a unique value in a specific priority within the priority queue with a binary predicate.

O(N) but smaller constant than filter/3

to_list/1

to_list(Q::pqueue4()) -> list()

Convert the priority queue to a list.

O(N)

to_plist/1

to_plist(Q::pqueue4()) -> [{priority(), list()}]

Convert the priority queue to a list with priorities.

O(N)

Generated by EDoc