fpq 0.4.0

Priority Queue with scoring Function
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

use std::collections::BinaryHeap;

use crate::scored_item::ScoredItem;

/// A priority queue with a score function.
pub struct PriorityQueue<T, S: Ord + Copy> {
    heap: BinaryHeap<ScoredItem<T, S>>,
    score_fn: Box<dyn Fn(&T) -> S>,
}

impl<T, S: Ord + Copy> PriorityQueue<T, S> {
    /// Creates a new priority queue with the given score function.
    pub fn new(score_fn: Box<dyn Fn(&T) -> S>) -> Self {
        let heap = BinaryHeap::new();
        Self { heap, score_fn }
    }

    /// Returns the reference to the first elements in the queue.
    pub fn peek(&self) -> Option<(S, &T)> {
        self.heap
            .peek()
            .map(|scored_item| (scored_item.score, &scored_item.item))
    }

    /// Returns the first elements in the queue.
    pub fn pop(&mut self) -> Option<(S, T)> {
        self.heap
            .pop()
            .map(|scored_item| (scored_item.score, scored_item.item))
    }

    /// Pushes an item into the queue.
    /// The score of the item is calculated by the score function.
    pub fn push(&mut self, item: T) {
        let score = (self.score_fn)(&item);
        self.push_with_score(item, score);
    }

    /// Pushes an item into the queue with the given score
    /// without using the score function.
    pub fn push_with_score(&mut self, item: T, score: S) {
        self.heap.push(ScoredItem { item, score });
    }

    /// Converts the priority queue into a vector of (score, item) pairs.
    pub fn into_vec(self) -> Vec<(S, T)> {
        self.heap.into_iter().map(|x| (x.score, x.item)).collect()
    }
}

#[cfg(test)]
mod test {
    use std::cmp::Reverse;

    use super::PriorityQueue;
    #[test]
    fn test_priority_queue() {
        let score_fn = Box::new(|s: &String| s.len());
        let mut queue = PriorityQueue::new(score_fn);

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

        queue.push("a".to_string()); // score = 1
        queue.push("ccc".to_string()); // score = 3
        queue.push("bb".to_string()); // score = 2
        queue.push_with_score("b".to_string(), 10); // score = 10

        assert_eq!(queue.peek(), Some((10, &"b".to_string())));
        assert_eq!(queue.pop(), Some((10, "b".to_string())));
        assert_eq!(queue.pop(), Some((3, "ccc".to_string())));
        assert_eq!(queue.pop(), Some((2, "bb".to_string())));
        assert_eq!(queue.pop(), Some((1, "a".to_string())));
        assert!(queue.peek().is_none());
    }

    #[test]
    fn test_priority_queue_reverse_order() {
        let score_fn = Box::new(|s: &String| Reverse(s.len()));
        let mut queue = PriorityQueue::new(score_fn);

        queue.push("a".to_string()); // score = -1
        queue.push("ccc".to_string()); // score = -3
        queue.push("bb".to_string()); // score = -2
        queue.push_with_score("b".to_string(), Reverse(10)); // score = -10

        assert_eq!(queue.peek(), Some((Reverse(1), &"a".to_string())));
        assert_eq!(queue.pop(), Some((Reverse(1), "a".to_string())));
        assert_eq!(queue.pop(), Some((Reverse(2), "bb".to_string())));
        assert_eq!(queue.pop(), Some((Reverse(3), "ccc".to_string())));
        assert_eq!(queue.pop(), Some((Reverse(10), "b".to_string())));
        assert!(queue.peek().is_none());
    }

    #[test]
    fn test_into_vec() {
        let score_fn = Box::new(|s: &String| s.len());
        let mut queue = PriorityQueue::new(score_fn);

        queue.push("a".to_string()); // score = 1
        queue.push("ccc".to_string()); // score = 3
        queue.push("bb".to_string()); // score = 2
        queue.push_with_score("b".to_string(), 10); // score = 10

        let mut vec = queue.into_vec();
        vec.sort_by_key(|x| x.0);
        assert_eq!(
            vec,
            vec![
                (1, "a".to_string()),
                (2, "bb".to_string()),
                (3, "ccc".to_string()),
                (10, "b".to_string()),
            ]
        );
    }
}