Struct rb_tree::RBQueue

pub struct RBQueue<T, P> where
    P: Fn(&T, &T) -> Ordering,  { /* fields omitted */ }

A priority queue implemented using a red black tree. The ordering supplied must satisfy the assymetry and transitivity rules as outlined by the dorumentation of std::cmp::PartialOrd.

Implementations

impl<T, P> RBQueue<T, P> where
    P: Fn(&T, &T) -> Ordering, 

pub fn new(cmp: P) -> RBQueue<T, P>

Creates and returns a new RBQueue that will order entries based on cmp.

It is a logic error to use a closure where two non-identical items map to the same value. If cmp returns Equal, then the two keys are considered the same.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<(i8, i8), _>::new(|l, r| {
    let l_sum = l.0 + l.1;
    let r_sum = r.0 + r.1;
    if l_sum == r_sum {
        if l.0 == r.0 {
            std::cmp::Ordering::Equal
        } else if l.0 < r.0 {
            std::cmp::Ordering::Less
        } else {
            std::cmp::Ordering::Greater
        }
    } else if l_sum < r_sum {
        std::cmp::Ordering::Less
    } else {
        std::cmp::Ordering::Greater
    }
});

t.insert((1, 1));
t.insert((1, 2));
t.insert((1, -1));
assert_eq!(t.peek().unwrap(), &(1, -1));

pub fn clear(&mut self)

Clears all entries from the queue.

Example:

use rb_tree::RBQueue;

let mut q = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
q.insert(2);
q.insert(5);
q.clear();
assert_eq!(q.len(), 0);
assert!(!q.contains(&2));

pub fn drain(&mut self) -> Drain<T>

Clears the queue and returns all values as an iterator in their order.

Example:

use rb_tree::RBQueue;

let mut q = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
q.insert(2);
q.insert(5);
assert_eq!(q.len(), 2);
let mut drain = q.drain();
assert_eq!(drain.next().unwrap(), 2);
assert_eq!(drain.next().unwrap(), 5);
assert!(drain.next().is_none());
assert_eq!(q.len(), 0);

pub fn ordered(&self) -> Vec<&T>

Returns a vector presenting the contained elements of the RBQueue in the order by which they are prioritised (that is, in the in-order tree traversal order).

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(3);
t.insert(1);
t.insert(2);
let order = t.ordered();
assert_eq!(*order[1], 2);

pub fn len(&self) -> usize

Returns the number of elements contained in the tree.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(3);
t.insert(1);
t.insert(2);
assert_eq!(t.len(), 3);
t.remove(&2);
assert_eq!(t.len(), 2);

pub fn is_empty(&self) -> bool

Returns true if there are no items present in the tree, false otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
assert!(t.is_empty());
t.insert(3);
assert!(!t.is_empty());

pub fn insert(&mut self, val: T) -> bool

Inserts a new element into the RBQueue. Returns true if this item was not already in the tree, and false otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<String, _>::new(|l, r| l.partial_cmp(r).unwrap());
assert_eq!(t.insert("Hello".to_string()), true);
assert_eq!(t.insert("Hello".to_string()), false);

pub fn replace(&mut self, val: T) -> Option<T>

Inserts a new element into the RBQueue. Returns None if this item was not already in the tree, and the previously contained item otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<String, _>::new(|l, r| l.partial_cmp(r).unwrap());
assert_eq!(t.replace("Hello".to_string()), None);
assert_eq!(t.replace("Hello".to_string()), Some("Hello".to_string()));

pub fn contains(&self, val: &T) -> bool

Returns true if the tree contains the specified item, false otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(2);
assert!(!t.contains(&3));
assert!(t.contains(&2));

pub fn get(&self, val: &T) -> Option<&T>

Returns the item specified if contained, None otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(1);
assert_eq!(*t.get(&1).unwrap(), 1);
assert_eq!(t.get(&2), None);

pub fn take(&mut self, val: &T) -> Option<T>

Removes an item the tree. Returns the matching item if it was contained in the tree, None otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(4);
t.insert(2);
assert_eq!(t.take(&2).unwrap(), 2);
assert_eq!(t.len(), 1);
assert_eq!(t.take(&2), None);

pub fn remove(&mut self, val: &T) -> bool

Removes an item the tree. Returns true if it was contained in the tree, false otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(4);
t.insert(2);
assert_eq!(t.remove(&2), true);
assert_eq!(t.len(), 1);
assert_eq!(t.remove(&2), false);

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

Removes the item at the front of the priority queue that the RBQueue represents if any elements are present, or None otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(2);
t.insert(1);
t.insert(3);
assert_eq!(t.pop().unwrap(), 1);

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

Peeks the item at the front of the priority queue that the RBQueue represents if any elements are present, or None otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(2);
t.insert(1);
t.insert(3);
assert_eq!(*t.peek().unwrap(), 1);

pub fn pop_back(&mut self) -> Option<T>

Removes the item at the back of the priority queue that the RBQueue represents if any elements are present, or None otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(2);
t.insert(1);
t.insert(3);
assert_eq!(t.pop_back().unwrap(), 3);

pub fn peek_back(&self) -> Option<&T>

Peeks the item at the back of the priority queue that the RBQueue represents if any elements are present, or None otherwise.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(2);
t.insert(1);
t.insert(3);
assert_eq!(*t.peek_back().unwrap(), 3);

pub fn iter(&self) -> Iter<'_, T>

Returns an iterator over the elements contained in this RBQueue.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<i8, _>::new(|l, r| l.partial_cmp(r).unwrap());
t.insert(3);
t.insert(1);
t.insert(5);
assert_eq!(t.iter().collect::<Vec<&i8>>(), vec!(&1, &3, &5));

pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F)

Retains in this RBQueue only those values for which the passed closure returns true.

Example:

use rb_tree::RBQueue;

let mut t = RBQueue::<usize, _>::new(|l, r| l.partial_cmp(r).unwrap());
for i in 0usize..10usize { t.insert(i); }
t.retain(|v| v % 2 == 0);
assert_eq!(t.iter().collect::<Vec<&usize>>(), vec!(&0, &2, &4, &6, &8));

impl<T, P> RBQueue<T, P> where
    T: PartialOrd,
    P: Fn(&T, &T) -> Ordering, 

pub fn into_set(self) -> RBTree<T>

Turns this queue into a set (RBTree)

Example:

use rb_tree::{RBQueue, RBTree};
use std::cmp::Ordering::{Equal, Less, Greater};

let mut q = RBQueue::new(|l, r| {
    match l - r {
        i32::MIN..=-1_i32 => Greater,
        0 => Equal,
        1_i32..=i32::MAX => Less
    }
});
q.insert(1);
q.insert(2);
q.insert(3);

let mut t = q.into_set();
assert_eq!(t.pop().unwrap(), 1);
assert_eq!(t.pop().unwrap(), 2);
assert_eq!(t.pop().unwrap(), 3);
assert_eq!(t.pop(), None);

Trait Implementations

impl<T: Clone, P: Clone> Clone for RBQueue<T, P> where
    P: Fn(&T, &T) -> Ordering, 

fn clone(&self) -> RBQueue<T, P>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, P> Debug for RBQueue<T, P> where
    P: Fn(&T, &T) -> Ordering, 

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

Formats the value using the given formatter.

impl<T: Debug, P> Display for RBQueue<T, P> where
    P: Fn(&T, &T) -> Ordering, 

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

Formats the value using the given formatter.

impl<'a, T, P> Extend<&'a T> for RBQueue<T, P> where
    T: Copy + 'a,
    P: Fn(&T, &T) -> Ordering, 

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, P> Extend<T> for RBQueue<T, P> where
    P: Fn(&T, &T) -> Ordering, 

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, P> From<RBQueue<T, P>> for RBTree<T> where
    T: PartialOrd,
    P: Copy + Fn(&T, &T) -> Ordering, 

fn from(q: RBQueue<T, P>) -> Self

Performs the conversion.

impl<T, P> IntoIterator for RBQueue<T, P> where
    P: Fn(&T, &T) -> Ordering, 

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value.