Trait orx_priority_queue::PriorityQueue

pub trait PriorityQueue<N, K>
where
    K: PartialOrd,
{
    type NodeKey<'a>: NodeKeyRef<'a, N, K>
       where Self: 'a,
             N: 'a,
             K: 'a;
    type Iter<'a>: Iterator<Item = Self::NodeKey<'a>>
       where Self: 'a,
             N: 'a,
             K: 'a;

    // Required methods
    fn len(&self) -> usize;
    fn capacity(&self) -> usize;
    fn peek(&self) -> Option<Self::NodeKey<'_>>;
    fn clear(&mut self);
    fn pop(&mut self) -> Option<(N, K)>;
    fn pop_node(&mut self) -> Option<N>;
    fn pop_key(&mut self) -> Option<K>;
    fn push(&mut self, node: N, key: K);
    fn push_then_pop(&mut self, node: N, key: K) -> (N, K);
    fn iter(&self) -> Self::Iter<'_>;

    // Provided method
    fn is_empty(&self) -> bool { ... }
}

A priority queue which allows pushing (N, K)=(node, key) pairs to the collection, and popping the foremost element having the lowest key.

Required Associated Types

type NodeKey<'a>: NodeKeyRef<'a, N, K> where Self: 'a, N: 'a, K: 'a

Item providing references to node & key pairs which are yielded by the iterator.

type Iter<'a>: Iterator<Item = Self::NodeKey<'a>> where Self: 'a, N: 'a, K: 'a

An iterator over the (node, key) pairs on the priority queue in an arbitrary order.

Required Methods

fn len(&self) -> usize

Number of elements in the queue.

Examples

use orx_priority_queue::*;

let mut queue = DaryHeap::<_, _, 16>::default();

queue.push('a', 42);
queue.push('b', 7);
assert_eq!(2, queue.len());

_ = queue.pop();
assert_eq!(1, queue.len());

fn capacity(&self) -> usize

Capacity of the heap.

fn peek(&self) -> Option<Self::NodeKey<'_>>

Returns, without popping, a reference to the foremost element of the queue; returns None if the queue is empty.

Examples

use orx_priority_queue::*;

let mut queue = BinaryHeap::default();
assert_eq!(None, queue.peek());

queue.push(0, 12.0);
queue.push(42, 1.0);
queue.push(21, 5.0);
assert_eq!(Some(&(42, 1.0)), queue.peek());

fn clear(&mut self)

Clears the queue.

Examples

use orx_priority_queue::*;

let mut queue = QuarternaryHeap::default();
assert!(queue.is_empty());

queue.push(0, 12.0);
queue.push(42, 1.0);
queue.push(21, 5.0);
assert!(!queue.is_empty());

queue.clear();
assert!(queue.is_empty());

fn pop(&mut self) -> Option<(N, K)>

Removes and returns the (node, key) pair with the lowest key in the queue; returns None if the queue is empty.

Examples

use orx_priority_queue::*;

let mut queue = BinaryHeap::default();
assert_eq!(None, queue.pop());

queue.push(0, 12.0);
queue.push(42, 1.0);
queue.push(21, 5.0);
assert_eq!(3, queue.len());

assert_eq!(Some((42, 1.0)), queue.pop());
assert_eq!(2, queue.len());

assert_eq!(Some((21, 5.0)), queue.pop());
assert_eq!(1, queue.len());

assert_eq!(Some((0, 12.0)), queue.pop());
assert!(queue.is_empty());

assert_eq!(None, queue.pop());

fn pop_node(&mut self) -> Option<N>

Removes and returns the node with the lowest key in the queue; returns None if the queue is empty.

Examples

use orx_priority_queue::*;

let mut queue = BinaryHeap::default();
assert_eq!(None, queue.pop_node());

queue.push(0, 12.0);
queue.push(42, 1.0);
queue.push(21, 5.0);
assert_eq!(3, queue.len());

assert_eq!(Some(42), queue.pop_node());
assert_eq!(2, queue.len());

assert_eq!(Some(21), queue.pop_node());
assert_eq!(1, queue.len());

assert_eq!(Some(0), queue.pop_node());
assert!(queue.is_empty());

assert_eq!(None, queue.pop_node());

fn pop_key(&mut self) -> Option<K>

Removes and returns the key of the node with the lowest key in the queue; returns None if the queue is empty.

Examples

use orx_priority_queue::*;

let mut queue = BinaryHeap::default();
assert_eq!(None, queue.pop_key());

queue.push(0, 12.0);
queue.push(42, 1.0);
queue.push(21, 5.0);
assert_eq!(3, queue.len());

assert_eq!(Some(1.0), queue.pop_key());
assert_eq!(2, queue.len());

assert_eq!(Some(5.0), queue.pop_key());
assert_eq!(1, queue.len());

assert_eq!(Some(12.0), queue.pop_key());
assert!(queue.is_empty());

assert_eq!(None, queue.pop_key());

fn push(&mut self, node: N, key: K)

Pushes the given (node, key) pair to the queue.

Examples

use orx_priority_queue::*;

let mut queue = BinaryHeap::default();
assert!(queue.is_empty());

queue.push(0, 12.0);
queue.push(42, 1.0);
queue.push(21, 5.0);
assert_eq!(3, queue.len());

fn push_then_pop(&mut self, node: N, key: K) -> (N, K)

Performs the push with given (node, key) followed by the pop operation.

Since the queue cannot be empty after the push, the return type is not optional.

The reason of merging the calls is that handling two instructions at once is more efficient for certain implementations, such as for the binary heap.

According to benchmark defined in “benches/push_then_pop.rs”, replacing the consequent push and pop calls with a push_then_pop call increases the performance by a factor 2 or 3 when the underlying struct takes benefit of this such as the DaryHeap and its variants.

Examples

use orx_priority_queue::*;

let mut queue = BinaryHeap::default();
assert!(queue.is_empty());

// returns the (node, key) back qhen the queue is empty
let popped = queue.push_then_pop(3, 33.3);
assert_eq!((3, 33.3), popped);
assert!(queue.is_empty());

queue.push(0, 12.0);
queue.push(42, 1.0);
queue.push(21, 5.0);
assert_eq!(3, queue.len()); // sorted-nodes: 42 (1.0) << 21 (5.0) << 0 (12.0)

let popped = queue.push_then_pop(100, 100.0);
assert_eq!((42, 1.0), popped);
assert_eq!(3, queue.len()); // sorted-nodes: 21 (5.0) << 0 (12.0) << 100 (100.0)

let popped = queue.push_then_pop(6, 6.0);
assert_eq!((21, 5.0), popped);
assert_eq!(3, queue.len()); // sorted-nodes: 6 (6.0) << 0 (12.0) << 100 (100.0)

let popped = queue.push_then_pop(13, 13.0);
assert_eq!((6, 6.0), popped);
assert_eq!(3, queue.len()); // sorted-nodes: 0 (12.0) << 13 (13.0) << 100 (100.0)

assert_eq!(Some((0, 12.0)), queue.pop());
assert_eq!(Some((13, 13.0)), queue.pop());
assert_eq!(Some((100, 100.0)), queue.pop());
assert!(queue.is_empty());

fn iter(&self) -> Self::Iter<'_>

Returns an iterator visiting all values on the heap in arbitrary order.

Provided Methods

fn is_empty(&self) -> bool

Returns whether he queue is empty or not.

Examples

use orx_priority_queue::*;

let mut queue = QuarternaryHeap::default();
assert!(queue.is_empty());

queue.push("wisdom", 42);
assert!(!queue.is_empty());

Object Safety

This trait is not object safe.

Implementations on Foreign Types

impl<N, K> PriorityQueue<N, K> for BinaryHeap<(N, K)>

where K: PartialOrd + Ord, N: Ord,

type NodeKey<'a> = &'a (N, K) where Self: 'a, N: 'a, K: 'a

type Iter<'a> = Iter<'a, (N, K)> where Self: 'a, N: 'a, K: 'a

fn len(&self) -> usize

fn capacity(&self) -> usize

fn peek(&self) -> Option<&(N, K)>

fn clear(&mut self)

fn pop(&mut self) -> Option<(N, K)>

fn pop_node(&mut self) -> Option<N>

fn pop_key(&mut self) -> Option<K>

fn push(&mut self, node: N, key: K)

fn push_then_pop(&mut self, node: N, key: K) -> (N, K)

fn iter(&self) -> Self::Iter<'_>

Implementors

impl<N, K, const D: usize> PriorityQueue<N, K> for DaryHeap<N, K, D>

where N: Clone, K: PartialOrd + Clone,

type NodeKey<'a> = &'a (N, K) where Self: 'a, N: 'a, K: 'a

type Iter<'a> = Iter<'a, (N, K)> where Self: 'a, N: 'a, K: 'a

impl<N, K, const D: usize> PriorityQueue<N, K> for DaryHeapOfIndices<N, K, D>

where N: HasIndex, K: PartialOrd + Clone,

type NodeKey<'a> = &'a (N, K) where Self: 'a, N: 'a, K: 'a

type Iter<'a> = Iter<'a, (N, K)> where Self: 'a, N: 'a, K: 'a

impl<N, K, const D: usize> PriorityQueue<N, K> for DaryHeapWithMap<N, K, D>

where N: Index, K: PartialOrd + Clone,

type NodeKey<'a> = &'a (N, K) where Self: 'a, N: 'a, K: 'a

type Iter<'a> = Iter<'a, (N, K)> where Self: 'a, N: 'a, K: 'a