base/collections/
pq.rs

1use std::cmp::Ordering;
2use std::fmt::{self, Debug, Formatter};
3use std::hash::Hash;
4
5use keyed_priority_queue::KeyedPriorityQueue;
6
7#[derive(Debug)]
8struct ReverseOrdered<T> {
9    inner: T,
10}
11
12impl<T> From<T> for ReverseOrdered<T> {
13    fn from(inner: T) -> ReverseOrdered<T> {
14        ReverseOrdered { inner }
15    }
16}
17
18impl<T: Ord> PartialOrd for ReverseOrdered<T> {
19    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
20        Some(self.cmp(other))
21    }
22}
23
24impl<T: Eq> Eq for ReverseOrdered<T> {}
25
26impl<T: Eq> PartialEq for ReverseOrdered<T> {
27    fn eq(&self, other: &Self) -> bool {
28        self.inner == other.inner
29    }
30}
31
32impl<T: Ord> Ord for ReverseOrdered<T> {
33    fn cmp(&self, other: &Self) -> Ordering {
34        match self.inner.cmp(&other.inner) {
35            Ordering::Less => Ordering::Greater,
36            Ordering::Equal => Ordering::Equal,
37            Ordering::Greater => Ordering::Less,
38        }
39    }
40}
41
42#[test]
43fn test_reverse_order() {
44    assert_eq!(ReverseOrdered::from(1), ReverseOrdered::from(1));
45    assert_ne!(ReverseOrdered::from(1), ReverseOrdered::from(0));
46    assert!(ReverseOrdered::from(1) < ReverseOrdered::from(0));
47    assert_ne!(ReverseOrdered::from(1), ReverseOrdered::from(0));
48    assert!(ReverseOrdered::from(1) <= ReverseOrdered::from(0));
49}
50
51pub struct KeyedReversePriorityQueueUnknownKeyError {}
52
53pub struct KeyedReversePriorityQueue<K: Hash + Eq + Ord, P: Ord> {
54    items: KeyedPriorityQueue<K, ReverseOrdered<P>>,
55}
56
57impl<K, P> KeyedReversePriorityQueue<K, P>
58where
59    K: Hash + Eq + Ord,
60    P: Ord,
61{
62    #[must_use]
63    pub fn new() -> KeyedReversePriorityQueue<K, P> {
64        KeyedReversePriorityQueue {
65            items: KeyedPriorityQueue::<K, ReverseOrdered<P>>::new(),
66        }
67    }
68
69    #[must_use]
70    pub fn peek(&self) -> Option<(&K, &P)> {
71        self.items.peek().map(|(k, p)| (k, &p.inner))
72    }
73
74    pub fn pop(&mut self) -> Option<(K, P)> {
75        self.items.pop().map(|(k, p)| (k, p.inner))
76    }
77
78    pub fn push(&mut self, key: K, priority: P) -> Option<P> {
79        self.items
80            .push(key, ReverseOrdered::from(priority))
81            .map(|rd| rd.inner)
82    }
83
84    /// Update the priority of a item (identified by `key`) in the
85    /// priority queue.
86    ///
87    /// # Errors
88    ///
89    /// Err(KeyedReversePriorityQueue) is returned when the indicated
90    /// key is not present.
91    pub fn set_priority(
92        &mut self,
93        key: &K,
94        priority: P,
95    ) -> Result<P, KeyedReversePriorityQueueUnknownKeyError> {
96        match self.items.set_priority(key, ReverseOrdered::from(priority)) {
97            Ok(priority) => Ok(priority.inner),
98            Err(_) => Err(KeyedReversePriorityQueueUnknownKeyError {}),
99        }
100    }
101
102    #[must_use]
103    pub fn len(&self) -> usize {
104        self.items.len()
105    }
106
107    #[must_use]
108    pub fn is_empty(&self) -> bool {
109        self.items.is_empty()
110    }
111}
112
113impl<K, P> Default for KeyedReversePriorityQueue<K, P>
114where
115    K: Hash + Eq + Ord,
116    P: Ord,
117{
118    fn default() -> Self {
119        Self::new()
120    }
121}
122
123impl<K, P> Debug for KeyedReversePriorityQueue<K, P>
124where
125    K: Hash + Eq + Ord + Debug,
126    P: Ord + Debug,
127{
128    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
129        f.debug_struct("KeyedReversePriorityQueue")
130            .field("items", &self.items)
131            .finish()
132    }
133}
134
135#[test]
136fn test_empty() {
137    let mut q: KeyedReversePriorityQueue<usize, usize> = KeyedReversePriorityQueue::default();
138    assert!(q.is_empty());
139    assert_eq!(0, q.len());
140    assert_eq!(q.peek(), None);
141    assert_eq!(q.pop(), None);
142}
143
144#[test]
145fn test_nonempty() {
146    let mut q: KeyedReversePriorityQueue<String, String> = KeyedReversePriorityQueue::new();
147    assert!(q.is_empty());
148    assert_eq!(
149        q.push(
150            "Muztagh Tower".to_string(),
151            "Joe Brown, Ian McNaught-Davis".to_string()
152        ),
153        None
154    );
155    assert!(!q.is_empty());
156}
157
158#[test]
159fn test_repeat_push() {
160    let mut q: KeyedReversePriorityQueue<usize, char> = KeyedReversePriorityQueue::new();
161    assert_eq!(q.push(0, '2'), None);
162    assert_eq!(q.push(0, '4'), Some('2'));
163    assert_eq!(q.push(0, '3'), Some('4'));
164    assert_eq!(q.pop(), Some((0, '3')));
165    assert!(q.is_empty());
166}
167
168#[test]
169fn test_ordering() {
170    let mut q: KeyedReversePriorityQueue<usize, char> = KeyedReversePriorityQueue::new();
171    assert_eq!(q.push(0, '2'), None);
172    assert_eq!(q.push(1, '8'), None);
173    assert_eq!(q.pop(), Some((0, '2')));
174    assert_eq!(q.pop(), Some((1, '8')));
175    assert!(q.is_empty());
176
177    // Now push them in the opposite order to prove that pop order
178    // depends on priority, not insertion order.
179    assert_eq!(q.push(1, '8'), None);
180    assert_eq!(q.push(0, '2'), None);
181    assert_eq!(q.pop(), Some((0, '2')));
182    assert_eq!(q.pop(), Some((1, '8')));
183    assert!(q.is_empty());
184}
base/collections/pq.rs

base/collections/
pq.rs
