gix_revwalk/
queue.rs

1use std::{cmp::Ordering, collections::BinaryHeap};
2
3use crate::PriorityQueue;
4
5pub(crate) struct Item<K, T> {
6    key: K,
7    value: T,
8}
9
10impl<K: Ord + std::fmt::Debug, T: std::fmt::Debug> std::fmt::Debug for Item<K, T> {
11    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
12        write!(f, "({:?}: {:?})", self.key, self.value)
13    }
14}
15
16impl<K: Ord + std::fmt::Debug, T: std::fmt::Debug> std::fmt::Debug for PriorityQueue<K, T> {
17    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
18        std::fmt::Debug::fmt(&self.0, f)
19    }
20}
21
22impl<K: Ord, T> PartialEq<Self> for Item<K, T> {
23    fn eq(&self, other: &Self) -> bool {
24        Ord::cmp(self, other).is_eq()
25    }
26}
27
28impl<K: Ord, T> Eq for Item<K, T> {}
29
30impl<K: Ord, T> PartialOrd<Self> for Item<K, T> {
31    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
32        Some(Ord::cmp(self, other))
33    }
34}
35
36impl<K: Ord, T> Ord for Item<K, T> {
37    fn cmp(&self, other: &Self) -> Ordering {
38        self.key.cmp(&other.key)
39    }
40}
41
42impl<K, T> Clone for Item<K, T>
43where
44    K: Clone,
45    T: Clone,
46{
47    fn clone(&self) -> Self {
48        Item {
49            key: self.key.clone(),
50            value: self.value.clone(),
51        }
52    }
53}
54
55impl<K, T> Clone for PriorityQueue<K, T>
56where
57    K: Clone + Ord,
58    T: Clone,
59{
60    fn clone(&self) -> Self {
61        Self(self.0.clone())
62    }
63}
64
65impl<K: Ord, T> PriorityQueue<K, T> {
66    /// Create a new instance.
67    pub fn new() -> Self {
68        PriorityQueue(Default::default())
69    }
70    /// Insert `value` so that it is ordered according to `key`.
71    pub fn insert(&mut self, key: K, value: T) {
72        self.0.push(Item { key, value });
73    }
74
75    /// Pop the highest-priority item value off the queue.
76    pub fn pop_value(&mut self) -> Option<T> {
77        self.0.pop().map(|t| t.value)
78    }
79
80    /// Pop the highest-priority item key and value off the queue.
81    pub fn pop(&mut self) -> Option<(K, T)> {
82        self.0.pop().map(|t| (t.key, t.value))
83    }
84
85    /// Iterate all items ordered from highest to lowest priority.
86    pub fn iter_unordered(&self) -> impl Iterator<Item = &T> {
87        self.0.iter().map(|t| &t.value)
88    }
89
90    /// Turn this instance into an iterator over its keys and values in arbitrary order.
91    pub fn into_iter_unordered(self) -> impl Iterator<Item = (K, T)> {
92        self.0.into_vec().into_iter().map(|item| (item.key, item.value))
93    }
94
95    /// Return true if the queue is empty.
96    pub fn is_empty(&self) -> bool {
97        self.0.is_empty()
98    }
99
100    /// Return true the amount of items on the queue.
101    pub fn len(&self) -> usize {
102        self.0.len()
103    }
104
105    /// Returns the greatest item `(K, T)` tuple, as ordered by `K`, if the queue is not empty, without removing it.
106    pub fn peek(&self) -> Option<(&K, &T)> {
107        self.0.peek().map(|e| (&e.key, &e.value))
108    }
109
110    /// Drop all items from the queue, without changing its capacity.
111    pub fn clear(&mut self) {
112        self.0.clear();
113    }
114}
115
116impl<K: Ord, T> FromIterator<(K, T)> for PriorityQueue<K, T> {
117    fn from_iter<I: IntoIterator<Item = (K, T)>>(iter: I) -> Self {
118        let mut q = PriorityQueue(BinaryHeap::new());
119        for (k, v) in iter {
120            q.insert(k, v);
121        }
122        q
123    }
124}
gix_revwalk/queue.rs

gix_revwalk/
queue.rs
