Struct Priority 

pub struct Priority { /* private fields */ }

A totally-ordered priority.

These priorities implement Dietz & Sleator (1987)’s solution to the order maintenance problem, which require a data structure T that supports insertion and comparison operations such that insertion constructs an element of the next greatest priority:

forall t: T, t < t.insert()

but is still lower priority than all other greater priorities:

forall t t': T s.t. t < t', t.insert() < t'

Amongst a collection of n priorities, comparison takes constant time, while insertion takes amortized log(n) time.

Usage

let p0 = Priority::new();
let p2 = p0.insert();
let p1 = p0.insert();
let p3 = p2.insert();

assert!(p0 < p1);
assert!(p0 < p2);
assert!(p0 < p3);
assert!(p1 < p2);
assert!(p1 < p3);
assert!(p2 < p3);

Memory management

Under the hood, these priorities are actually references to nodes of a circular linked list, allocated from an arena. Those nodes are reference-counted, which allows these priorities to be cloned. The node’s reference count is decremented when this priority is dropped, and if it reaches zero, the node is deallocated.

Priorities from different arenas cannot be compared with one another.

Algorithm

This implementation uses Dietz & Sleator (1987)’s algorithm, also called tag-range relabeling (as opposed to Bender et al.’s list-range relabeling algorithm).

While Dietz & Sleator also propose a data structure that supports constant-time insertion, that data structure is so overwhelmingly complex that the overhead of maintaining such a data structure will overwhelm any theoretical efficiency for any reasonable number of priorities.

More recently, Bender et al. proposed an alternative solution, using a list-range relabling approach. That approach is likely more efficient on real hardware, since it favors bit-wise operations over multiplication and division. For now, this crate uses the possibly slower tag-range relabeling approach, because it was ported from a scripting language that is better suited toward floating operations. It remains to be seen which implementation is better under which circumstances.

References

• Paul F. Dietz and Daniel D. Sleator. Two Algorithms for Maintaining Order in a List. 1987.

• Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito. Two simplified algorithms for maintaining order in a list. 2002.

Implementations

impl Priority

pub fn new() -> Self

Allocate a new priority in a fresh arena.

Note that priorities allocated in separate arenas cannot be compared; to construct a Priority that can be compared to some existing priority, use Priority::insert().

pub fn insert(&self) -> Self

Allocate the next greatest priority after the given self.

Trait Implementations

impl Clone for Priority

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Priority

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Drop for Priority

fn drop(&mut self)

Executes the destructor for this type.

impl PartialEq for Priority

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for Priority

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Eq for Priority