fpq

Struct PriorityQueue

Source 
pub struct PriorityQueue<T, S: Ord + Copy> { /* private fields */ }
Expand description

A priority queue with a score function.

Implementations§

Source§

impl<T, S: Ord + Copy> PriorityQueue<T, S>

Source

pub fn new(score_fn: Box<dyn Fn(&T) -> S>) -> Self

Creates a new priority queue with the given score function.

Examples found in repository?
examples/usage.rs (line 9)
5fn main() {
6    // a score function that returns the length of a string
7    let score_fn = Box::new(|s: &String| s.len());
8    // create a new priority queue with the score function
9    let mut queue = PriorityQueue::new(score_fn);
10
11    // the queue is empty at the beginning
12    assert!(queue.peek().is_none());
13
14    // push some items into the queue
15    // the score function is used to calculate the score of each item
16    queue.push("a".to_string()); // score = 1
17    queue.push("ccc".to_string()); // score = 3
18    queue.push("bb".to_string()); // score = 2
19
20    // you can also push an item with a explicit score
21    queue.push_with_score("b".to_string(), 10); // score = 10
22
23    // peek the item with the highest priority
24    assert_eq!(queue.peek(), Some((10, &"b".to_string())));
25
26    // pop the item with the highest priority
27    assert_eq!(queue.pop(), Some((10, "b".to_string())));
28    assert_eq!(queue.pop(), Some((3, "ccc".to_string())));
29    assert_eq!(queue.pop(), Some((2, "bb".to_string())));
30    assert_eq!(queue.pop(), Some((1, "a".to_string())));
31
32    // the queue is empty again
33    assert!(queue.peek().is_none());
34
35    // you can also use a reverse order
36    let score_fn = Box::new(|s: &String| Reverse(s.len()));
37    let mut queue = PriorityQueue::new(score_fn);
38
39    queue.push("a".to_string()); // score = -1
40    queue.push("ccc".to_string()); // score = -3
41    queue.push("bb".to_string()); // score = -2
42
43    // remember to use Reverse when pushing an item with an explicit score
44    queue.push_with_score("b".to_string(), Reverse(10)); // score = -10
45
46    assert_eq!(queue.peek(), Some((Reverse(1), &"a".to_string())));
47    assert_eq!(queue.pop(), Some((Reverse(1), "a".to_string())));
48    assert_eq!(queue.pop(), Some((Reverse(2), "bb".to_string())));
49    assert_eq!(queue.pop(), Some((Reverse(3), "ccc".to_string())));
50    assert_eq!(queue.pop(), Some((Reverse(10), "b".to_string())));
51
52    assert!(queue.peek().is_none());
53}
Source

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

Returns the reference to the first elements in the queue.

Examples found in repository?
examples/usage.rs (line 12)
5fn main() {
6    // a score function that returns the length of a string
7    let score_fn = Box::new(|s: &String| s.len());
8    // create a new priority queue with the score function
9    let mut queue = PriorityQueue::new(score_fn);
10
11    // the queue is empty at the beginning
12    assert!(queue.peek().is_none());
13
14    // push some items into the queue
15    // the score function is used to calculate the score of each item
16    queue.push("a".to_string()); // score = 1
17    queue.push("ccc".to_string()); // score = 3
18    queue.push("bb".to_string()); // score = 2
19
20    // you can also push an item with a explicit score
21    queue.push_with_score("b".to_string(), 10); // score = 10
22
23    // peek the item with the highest priority
24    assert_eq!(queue.peek(), Some((10, &"b".to_string())));
25
26    // pop the item with the highest priority
27    assert_eq!(queue.pop(), Some((10, "b".to_string())));
28    assert_eq!(queue.pop(), Some((3, "ccc".to_string())));
29    assert_eq!(queue.pop(), Some((2, "bb".to_string())));
30    assert_eq!(queue.pop(), Some((1, "a".to_string())));
31
32    // the queue is empty again
33    assert!(queue.peek().is_none());
34
35    // you can also use a reverse order
36    let score_fn = Box::new(|s: &String| Reverse(s.len()));
37    let mut queue = PriorityQueue::new(score_fn);
38
39    queue.push("a".to_string()); // score = -1
40    queue.push("ccc".to_string()); // score = -3
41    queue.push("bb".to_string()); // score = -2
42
43    // remember to use Reverse when pushing an item with an explicit score
44    queue.push_with_score("b".to_string(), Reverse(10)); // score = -10
45
46    assert_eq!(queue.peek(), Some((Reverse(1), &"a".to_string())));
47    assert_eq!(queue.pop(), Some((Reverse(1), "a".to_string())));
48    assert_eq!(queue.pop(), Some((Reverse(2), "bb".to_string())));
49    assert_eq!(queue.pop(), Some((Reverse(3), "ccc".to_string())));
50    assert_eq!(queue.pop(), Some((Reverse(10), "b".to_string())));
51
52    assert!(queue.peek().is_none());
53}
Source

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

Returns the first elements in the queue.

Examples found in repository?
examples/usage.rs (line 27)
5fn main() {
6    // a score function that returns the length of a string
7    let score_fn = Box::new(|s: &String| s.len());
8    // create a new priority queue with the score function
9    let mut queue = PriorityQueue::new(score_fn);
10
11    // the queue is empty at the beginning
12    assert!(queue.peek().is_none());
13
14    // push some items into the queue
15    // the score function is used to calculate the score of each item
16    queue.push("a".to_string()); // score = 1
17    queue.push("ccc".to_string()); // score = 3
18    queue.push("bb".to_string()); // score = 2
19
20    // you can also push an item with a explicit score
21    queue.push_with_score("b".to_string(), 10); // score = 10
22
23    // peek the item with the highest priority
24    assert_eq!(queue.peek(), Some((10, &"b".to_string())));
25
26    // pop the item with the highest priority
27    assert_eq!(queue.pop(), Some((10, "b".to_string())));
28    assert_eq!(queue.pop(), Some((3, "ccc".to_string())));
29    assert_eq!(queue.pop(), Some((2, "bb".to_string())));
30    assert_eq!(queue.pop(), Some((1, "a".to_string())));
31
32    // the queue is empty again
33    assert!(queue.peek().is_none());
34
35    // you can also use a reverse order
36    let score_fn = Box::new(|s: &String| Reverse(s.len()));
37    let mut queue = PriorityQueue::new(score_fn);
38
39    queue.push("a".to_string()); // score = -1
40    queue.push("ccc".to_string()); // score = -3
41    queue.push("bb".to_string()); // score = -2
42
43    // remember to use Reverse when pushing an item with an explicit score
44    queue.push_with_score("b".to_string(), Reverse(10)); // score = -10
45
46    assert_eq!(queue.peek(), Some((Reverse(1), &"a".to_string())));
47    assert_eq!(queue.pop(), Some((Reverse(1), "a".to_string())));
48    assert_eq!(queue.pop(), Some((Reverse(2), "bb".to_string())));
49    assert_eq!(queue.pop(), Some((Reverse(3), "ccc".to_string())));
50    assert_eq!(queue.pop(), Some((Reverse(10), "b".to_string())));
51
52    assert!(queue.peek().is_none());
53}
Source

pub fn push(&mut self, item: T)

Pushes an item into the queue. The score of the item is calculated by the score function.

Examples found in repository?
examples/usage.rs (line 16)
5fn main() {
6    // a score function that returns the length of a string
7    let score_fn = Box::new(|s: &String| s.len());
8    // create a new priority queue with the score function
9    let mut queue = PriorityQueue::new(score_fn);
10
11    // the queue is empty at the beginning
12    assert!(queue.peek().is_none());
13
14    // push some items into the queue
15    // the score function is used to calculate the score of each item
16    queue.push("a".to_string()); // score = 1
17    queue.push("ccc".to_string()); // score = 3
18    queue.push("bb".to_string()); // score = 2
19
20    // you can also push an item with a explicit score
21    queue.push_with_score("b".to_string(), 10); // score = 10
22
23    // peek the item with the highest priority
24    assert_eq!(queue.peek(), Some((10, &"b".to_string())));
25
26    // pop the item with the highest priority
27    assert_eq!(queue.pop(), Some((10, "b".to_string())));
28    assert_eq!(queue.pop(), Some((3, "ccc".to_string())));
29    assert_eq!(queue.pop(), Some((2, "bb".to_string())));
30    assert_eq!(queue.pop(), Some((1, "a".to_string())));
31
32    // the queue is empty again
33    assert!(queue.peek().is_none());
34
35    // you can also use a reverse order
36    let score_fn = Box::new(|s: &String| Reverse(s.len()));
37    let mut queue = PriorityQueue::new(score_fn);
38
39    queue.push("a".to_string()); // score = -1
40    queue.push("ccc".to_string()); // score = -3
41    queue.push("bb".to_string()); // score = -2
42
43    // remember to use Reverse when pushing an item with an explicit score
44    queue.push_with_score("b".to_string(), Reverse(10)); // score = -10
45
46    assert_eq!(queue.peek(), Some((Reverse(1), &"a".to_string())));
47    assert_eq!(queue.pop(), Some((Reverse(1), "a".to_string())));
48    assert_eq!(queue.pop(), Some((Reverse(2), "bb".to_string())));
49    assert_eq!(queue.pop(), Some((Reverse(3), "ccc".to_string())));
50    assert_eq!(queue.pop(), Some((Reverse(10), "b".to_string())));
51
52    assert!(queue.peek().is_none());
53}
Source

pub fn push_with_score(&mut self, item: T, score: S)

Pushes an item into the queue with the given score without using the score function.

Examples found in repository?
examples/usage.rs (line 21)
5fn main() {
6    // a score function that returns the length of a string
7    let score_fn = Box::new(|s: &String| s.len());
8    // create a new priority queue with the score function
9    let mut queue = PriorityQueue::new(score_fn);
10
11    // the queue is empty at the beginning
12    assert!(queue.peek().is_none());
13
14    // push some items into the queue
15    // the score function is used to calculate the score of each item
16    queue.push("a".to_string()); // score = 1
17    queue.push("ccc".to_string()); // score = 3
18    queue.push("bb".to_string()); // score = 2
19
20    // you can also push an item with a explicit score
21    queue.push_with_score("b".to_string(), 10); // score = 10
22
23    // peek the item with the highest priority
24    assert_eq!(queue.peek(), Some((10, &"b".to_string())));
25
26    // pop the item with the highest priority
27    assert_eq!(queue.pop(), Some((10, "b".to_string())));
28    assert_eq!(queue.pop(), Some((3, "ccc".to_string())));
29    assert_eq!(queue.pop(), Some((2, "bb".to_string())));
30    assert_eq!(queue.pop(), Some((1, "a".to_string())));
31
32    // the queue is empty again
33    assert!(queue.peek().is_none());
34
35    // you can also use a reverse order
36    let score_fn = Box::new(|s: &String| Reverse(s.len()));
37    let mut queue = PriorityQueue::new(score_fn);
38
39    queue.push("a".to_string()); // score = -1
40    queue.push("ccc".to_string()); // score = -3
41    queue.push("bb".to_string()); // score = -2
42
43    // remember to use Reverse when pushing an item with an explicit score
44    queue.push_with_score("b".to_string(), Reverse(10)); // score = -10
45
46    assert_eq!(queue.peek(), Some((Reverse(1), &"a".to_string())));
47    assert_eq!(queue.pop(), Some((Reverse(1), "a".to_string())));
48    assert_eq!(queue.pop(), Some((Reverse(2), "bb".to_string())));
49    assert_eq!(queue.pop(), Some((Reverse(3), "ccc".to_string())));
50    assert_eq!(queue.pop(), Some((Reverse(10), "b".to_string())));
51
52    assert!(queue.peek().is_none());
53}
Source

pub fn into_vec(self) -> Vec<(S, T)>

Converts the priority queue into a vector of (score, item) pairs.

Auto Trait Implementations§

§

impl<T, S> Freeze for PriorityQueue<T, S>

§

impl<T, S> !RefUnwindSafe for PriorityQueue<T, S>

§

impl<T, S> !Send for PriorityQueue<T, S>

§

impl<T, S> !Sync for PriorityQueue<T, S>

§

impl<T, S> Unpin for PriorityQueue<T, S>
where S: Unpin, T: Unpin,

§

impl<T, S> !UnwindSafe for PriorityQueue<T, S>

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.