rsv_lib/utils/
priority_queue.rs

1use std::collections::BinaryHeap;
2use std::hash::Hash;
3
4pub struct Item<T> {
5    pub line_n: usize,
6    pub priority: f64,
7    pub item: T,
8}
9
10impl<T> PartialEq for Item<T> {
11    fn eq(&self, other: &Self) -> bool {
12        self.priority == other.priority
13    }
14}
15
16impl<T> Eq for Item<T> {}
17
18impl<T> PartialOrd for Item<T> {
19    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
20        self.priority.partial_cmp(&other.priority)
21    }
22}
23
24impl<T> Ord for Item<T> {
25    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
26        self.priority.partial_cmp(&other.priority).unwrap()
27    }
28}
29
30impl<T> Item<T> {
31    pub fn line_n_as_string(&self) -> String {
32        self.line_n.to_string()
33    }
34}
35pub struct PriorityQueue<T: Hash + Eq> {
36    pub max_priority: f64,
37    pub capacity: usize,
38    pub count: usize,
39    pub v: BinaryHeap<Item<T>>,
40}
41
42impl<T> PriorityQueue<T>
43where
44    T: Hash + Eq + Clone,
45{
46    pub fn with_capacity(n: usize) -> Self {
47        PriorityQueue {
48            max_priority: 0.0,
49            capacity: n,
50            count: 0,
51            v: BinaryHeap::new(),
52        }
53    }
54
55    pub fn can_insert(&self, priority: f64) -> bool {
56        // println!("{},{}", self.capacity, self.count);
57        priority <= self.max_priority || self.count < self.capacity
58    }
59
60    pub fn push(&mut self, line_n: usize, priority: f64, item: T) {
61        self.v.push(Item {
62            line_n,
63            priority,
64            item,
65        });
66
67        if self.max_priority < priority {
68            self.max_priority = priority;
69        }
70
71        if self.count >= self.capacity {
72            self.v.pop();
73        } else {
74            self.count += 1;
75        }
76    }
77
78    pub fn into_sorted_items(self) -> Vec<Item<T>> {
79        let mut v = self.v.into_vec();
80        v.sort_by_key(|a| a.line_n);
81        v
82    }
83}
rsv_lib/utils/priority_queue.rs

rsv_lib/utils/
priority_queue.rs
