Struct DynamicPriorityQueue 

pub struct DynamicPriorityQueue<T: HasDynamicPriority> { /* private fields */ }

Priority queue using dynamic priorities.

Trait Implementations

impl<T: HasDynamicPriority> Default for DynamicPriorityQueue<T>

where Vec<T>: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<T: HasDynamicPriority> From<Vec<T>> for DynamicPriorityQueue<T>

fn from(value: Vec<T>) -> Self

Converts to this type from the input type.

impl<T: HasDynamicPriority, const N: usize> From<[T; N]> for DynamicPriorityQueue<T>

fn from(value: [T; N]) -> Self

Converts to this type from the input type.

impl<T: HasDynamicPriority> FromIterator<T> for DynamicPriorityQueue<T>

fn from_iter<II: IntoIterator<Item = T>>(iter: II) -> Self

Creates a value from an iterator.

impl<T: HasDynamicPriority> PriorityQueue<T> for DynamicPriorityQueue<T>

fn len(&self) -> usize

Returns the length of the queue.

use gtether::util::priority::{PriorityQueue, DynamicPriorityQueue};
use std::sync::atomic::AtomicIsize;
let queue = DynamicPriorityQueue::<AtomicIsize>::from([AtomicIsize::new(-2), AtomicIsize::new(3)]);
assert_eq!(queue.len(), 2);

fn is_empty(&self) -> bool

Checks if the queue is empty.

use gtether::util::priority::{PriorityQueue, DynamicPriorityQueue};
use std::sync::atomic::AtomicIsize;
let mut queue = DynamicPriorityQueue::<AtomicIsize>::default();
assert!(queue.is_empty());

queue.push(AtomicIsize::new(0));
queue.push(AtomicIsize::new(-2));
queue.push(AtomicIsize::new(3));
assert!(!queue.is_empty());

fn peek(&self) -> Option<&T>

Returns the item in the queue with the highest priority, or None if the queue is empty.

use gtether::util::priority::{PriorityQueue, DynamicPriorityQueue};
use std::sync::{Arc, atomic::{AtomicIsize, Ordering}};
let mut queue = DynamicPriorityQueue::<Arc<AtomicIsize>>::default();
assert!(queue.peek().is_none());

let val_a = Arc::new(AtomicIsize::new(-2));
let val_b = Arc::new(AtomicIsize::new(3));
queue.push(val_a.clone());
queue.push(val_b.clone());

{
    let val = queue.peek().expect("should be Some()");
    assert_eq!(val.load(Ordering::Relaxed), 3);
}

{
    val_a.store(10, Ordering::Relaxed);
    let val = queue.peek().expect("should be Some()");
    assert_eq!(val.load(Ordering::Relaxed), 10);
}

Time complexity

Because priorities are dynamic, the entire queue must be iterated to find the highest priority every time, making the cost O(n).

fn push(&mut self, value: T)

Push an item onto the queue.

use gtether::util::priority::{PriorityQueue, DynamicPriorityQueue};
use std::sync::atomic::{AtomicIsize, Ordering};
let mut queue = DynamicPriorityQueue::<AtomicIsize>::default();
queue.push(AtomicIsize::new(0));
queue.push(AtomicIsize::new(-2));
queue.push(AtomicIsize::new(3));

assert_eq!(queue.len(), 3);
let val = queue.peek().expect("should be Some()");
assert_eq!(val.load(Ordering::Relaxed), 3);

Time complexity

Takes amortized O(1) time. See Vec::push() for more.

fn pop(&mut self) -> Option<T>

Removes the item with the highest priority and returns it, or None if the queue is empty.

use gtether::util::priority::{PriorityQueue, DynamicPriorityQueue};
use std::sync::{Arc, atomic::{AtomicIsize, Ordering}};

let val_a = Arc::new(AtomicIsize::new(0));
let val_b = Arc::new(AtomicIsize::new(-2));
let val_c = Arc::new(AtomicIsize::new(3));

let mut queue = DynamicPriorityQueue::<Arc<AtomicIsize>>::from([
    val_a.clone(),
    val_b.clone(),
    val_c.clone(),
]);

{
    let val = queue.pop().expect("should be Some()");
    assert_eq!(val.load(Ordering::Relaxed), 3);
}

{
    val_b.store(10, Ordering::Relaxed);
    let val = queue.pop().expect("should be Some()");
    assert_eq!(val.load(Ordering::Relaxed), 10);
}

{
    let val = queue.pop().expect("should be Some()");
    assert_eq!(val.load(Ordering::Relaxed), 0);
}

assert!(queue.pop().is_none());

Time complexity

Because priorities are dynamic, the entire queue must be iterated to find the highest priority every time, making the cost O(n).

fn swap_if_higher(&mut self, value: T) -> T

Compares value to the highest priority in the queue, and swaps with it if it is higher.

use gtether::util::priority::{PriorityQueue, DynamicPriorityQueue};
use std::sync::{Arc, atomic::{AtomicIsize, Ordering}};

let val_a = Arc::new(AtomicIsize::new(5));
let mut queue = DynamicPriorityQueue::<Arc<AtomicIsize>>::from([val_a.clone()]);

let val_b = Arc::new(AtomicIsize::new(10));
{
    let val = queue.swap_if_higher(val_b.clone());
    assert_eq!(val.load(Ordering::Relaxed), 10);
}

val_a.store(20, Ordering::Relaxed);
{
    let val = queue.swap_if_higher(val_b.clone());
    assert_eq!(val.load(Ordering::Relaxed), 20);
}

Time complexity

Because priorities are dynamic, the entire queue must be iterated to find the highest priority every time, making the cost O(n).

This method only searches for the highest priority once before comparing and swapping, so it is faster than manually comparing with peek() and then calling pop() and push().