queue_queue/
inverse.rs

1use std::{cmp::Ordering, collections::BinaryHeap};
2
3use crate::PriorityQueue;
4
5#[derive(Debug, PartialEq, Eq, Clone)]
6struct Node<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> {
7    priority: P,
8    data: T,
9}
10
11impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> PartialOrd for Node<P, T> {
12    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
13        other.priority.partial_cmp(&self.priority)
14    }
15}
16
17impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> Ord for Node<P, T> {
18    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
19        other
20            .priority
21            .partial_cmp(&self.priority)
22            .unwrap_or(Ordering::Less)
23    }
24}
25
26#[derive(Debug)]
27/// A priority queue implementation based on Rust's `BinaryHeap`.
28/// Templated with `P` for priority and `T` for data.
29///
30/// - `P` must be `PartialOrd`, `PartialEq`, and `Eq`.
31/// - `T` must be `PartialEq` and `Eq`.
32///
33/// If Node A and Node B have the same priority, but Node A was added before Node B,
34/// then Node A will be prioritized over Node B.
35/// See [`PriorityQueue`](trait.PriorityQueue.html) for more information.
36///
37/// # Examples
38///
39/// ```rust
40/// # use queue_queue::inverse::InversePriorityQueue;
41/// # use queue_queue::PriorityQueue;
42///
43/// let mut prio = InversePriorityQueue::<usize, String>::default();
44/// prio.enqueue(2, "hello".to_string());
45/// prio.enqueue(3, "julia".to_string());
46/// prio.enqueue(1, "world".to_string());
47/// prio.enqueue(3, "naomi".to_string());
48///
49/// let mut new_prio: InversePriorityQueue<usize, String> = prio
50///     .into_iter()
51///     .map(|(priority, data)| (priority, data.to_owned() + " wow"))
52///     .collect();
53///
54/// assert_eq!(new_prio.dequeue(), Some((1, "world wow".to_string())));
55/// assert_eq!(new_prio.dequeue(), Some((2, "hello wow".to_string())));
56/// assert_eq!(new_prio.dequeue(), Some((3, "naomi wow".to_string())));
57/// assert_eq!(new_prio.dequeue(), Some((3, "julia wow".to_string())));
58/// ```
59pub struct InversePriorityQueue<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> {
60    queue: BinaryHeap<Node<P, T>>,
61}
62
63impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> Default for InversePriorityQueue<P, T> {
64    fn default() -> Self {
65        Self {
66            queue: BinaryHeap::new(),
67        }
68    }
69}
70
71impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> PriorityQueue<P, T>
72    for InversePriorityQueue<P, T>
73{
74    fn with_capacity(capacity: usize) -> Self {
75        Self {
76            queue: BinaryHeap::with_capacity(capacity),
77        }
78    }
79
80    fn enqueue(&mut self, priority: P, data: T) {
81        let node = Node { priority, data };
82
83        self.queue.push(node);
84    }
85
86    fn dequeue(&mut self) -> Option<(P, T)> {
87        let node = self.queue.pop();
88
89        node.map(|n| (n.priority, n.data))
90    }
91
92    fn peek(&self) -> Option<(&P, &T)> {
93        self.queue.peek().map(|node| (&node.priority, &node.data))
94    }
95
96    fn len(&self) -> usize {
97        self.queue.len()
98    }
99
100    fn is_empty(&self) -> bool {
101        self.queue.is_empty()
102    }
103
104    fn capacity(&self) -> usize {
105        self.queue.capacity()
106    }
107
108    fn append(&mut self, mut other: Self) {
109        self.queue.append(&mut other.queue);
110    }
111
112    /// Extend the priority queue with an iterator
113    ///
114    /// # Examples
115    ///
116    /// ```rust
117    /// # use queue_queue::inverse::InversePriorityQueue;
118    /// # use queue_queue::PriorityQueue;
119    ///
120    /// let mut prio = InversePriorityQueue::<usize, String>::default();
121    /// prio.extend(vec![(2, "world".to_string()), (3, "hello".to_string())]);
122    /// assert_eq!(prio.dequeue(), Some((2, "world".to_string())));
123    /// assert_eq!(prio.dequeue(), Some((3, "hello".to_string())));
124    /// assert_eq!(prio.dequeue(), None);
125    /// ```
126    fn extend<I>(&mut self, iter: I)
127    where
128        I: IntoIterator<Item = (P, T)>,
129    {
130        self.queue.extend(iter.into_iter().map(|(x, y)| Node {
131            priority: x,
132            data: y,
133        }));
134    }
135
136    fn reserve(&mut self, additional: usize) {
137        self.queue.reserve(additional);
138    }
139
140    fn reserve_exact(&mut self, additional: usize) {
141        self.queue.reserve_exact(additional);
142    }
143
144    fn shrink_to_fit(&mut self) {
145        self.queue.shrink_to_fit();
146    }
147
148    fn shrink_to(&mut self, capacity: usize) {
149        self.queue.shrink_to(capacity);
150    }
151
152    fn clear(&mut self) {
153        self.queue.clear();
154    }
155
156    fn drain(&mut self) -> impl Iterator<Item = (P, T)> + '_ {
157        self.queue.drain().map(|n| (n.priority, n.data))
158    }
159
160    fn contains(&self, data: &T) -> bool {
161        self.queue.iter().any(|node| &node.data == data)
162    }
163
164    fn contains_at(&self, priority: &P, data: &T) -> bool {
165        self.queue
166            .iter()
167            .any(|node| &node.data == data && &node.priority == priority)
168    }
169
170    fn remove(&mut self, data: &T) -> bool {
171        let original_size = self.queue.len();
172        self.queue.retain(|node| &node.data != data);
173        let new_size = self.queue.len();
174
175        original_size != new_size
176    }
177
178    fn remove_at(&mut self, priority: &P, data: &T) -> bool {
179        let original_size = self.queue.len();
180        self.queue.retain(|node| {
181            if &node.priority == priority {
182                &node.data != data
183            } else {
184                true
185            }
186        });
187        let new_size = self.queue.len();
188
189        original_size != new_size
190    }
191
192    fn max_node(&self) -> Option<(&P, &T)> {
193        self.queue
194            .iter()
195            .max_by(|a, b| {
196                a.priority
197                    .partial_cmp(&b.priority)
198                    .unwrap_or(Ordering::Equal)
199            })
200            .map(|node| (&node.priority, &node.data))
201    }
202
203    fn min_node(&self) -> Option<(&P, &T)> {
204        self.queue
205            .iter()
206            .min_by(|a, b| {
207                a.priority
208                    .partial_cmp(&b.priority)
209                    .unwrap_or(Ordering::Equal)
210            })
211            .map(|node| (&node.priority, &node.data))
212    }
213}
214
215impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> InversePriorityQueue<P, T> {
216    #[must_use]
217    /// Get an iterator over the priority queue
218    pub const fn iter(&self) -> InversePriorityQueueIterator<P, T> {
219        InversePriorityQueueIterator {
220            internal: &self.queue,
221            index: 0,
222        }
223    }
224
225    #[must_use]
226    /// Convert the priority queue into an iterator
227    pub fn into_iter(self) -> InversePriorityQueueIntoIterator<P, T> {
228        InversePriorityQueueIntoIterator { queue: self.queue }
229    }
230
231    /// Update the priority of an item in the queue.
232    ///
233    /// > This is a very slow operation!
234    /// > * it uses unsafe `std::mem::transmute_copy` under the hhod to guarantee allocation of priority `P` on every possible scenario.
235    ///
236    /// # Examples
237    ///
238    /// ```rust
239    /// # use queue_queue::inverse::InversePriorityQueue;
240    /// # use queue_queue::PriorityQueue;
241    ///
242    /// let mut prio = InversePriorityQueue::<usize, String>::default();
243    /// prio.enqueue(5, "julia".to_string());
244    /// prio.enqueue(2, "hello".to_string());
245    /// prio.enqueue(3, "julia".to_string());
246    /// prio.enqueue(1, "world".to_string());
247    /// prio.enqueue(3, "naomi".to_string());
248
249    /// let ref_str = "julia".to_string();
250    /// let mut new = prio.update(3, 7,&ref_str);
251
252    /// assert_eq!(new.dequeue(), Some((1, "world".to_string())));
253    /// assert_eq!(new.dequeue(), Some((2, "hello".to_string())));
254    /// assert_eq!(new.dequeue(), Some((3, "naomi".to_string())));
255    /// assert_eq!(new.dequeue(), Some((5, "julia".to_string())));
256    /// assert_eq!(new.dequeue(), Some((7, "julia".to_string())));
257    /// ```
258    #[must_use]
259    #[allow(clippy::needless_pass_by_value)]
260    pub fn update(mut self, old: P, new: P, data: &T) -> Self {
261        self.queue
262            .drain()
263            .map(|n| {
264                if n.priority == old && &n.data == data {
265                    let copy: P = unsafe { std::mem::transmute_copy(&new) };
266                    (copy, n.data)
267                } else {
268                    (n.priority, n.data)
269                }
270            })
271            .collect()
272    }
273
274    /// Update the priority of an item in the queue with a reference to the data.
275    #[allow(clippy::needless_pass_by_value)]
276    pub fn update_as(&mut self, old: P, new: P, data: T) {
277        self.queue
278            .retain(|n| !(n.priority == old && n.data == data));
279        self.enqueue(new, data);
280    }
281}
282
283/// An Iterator struct for `InversePriorityQueue`
284pub struct InversePriorityQueueIterator<'b, P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> {
285    internal: &'b BinaryHeap<Node<P, T>>,
286    index: usize,
287}
288
289impl<'b, P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> Iterator
290    for InversePriorityQueueIterator<'b, P, T>
291{
292    type Item = (&'b P, &'b T);
293
294    fn next(&mut self) -> Option<Self::Item> {
295        let val = self
296            .internal
297            .iter()
298            .nth(self.index)
299            .map(|n| (&n.priority, &n.data));
300        self.index += 1;
301        val
302    }
303}
304
305impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> FromIterator<(P, T)>
306    for InversePriorityQueue<P, T>
307{
308    fn from_iter<I: IntoIterator<Item = (P, T)>>(iter: I) -> Self {
309        let mut collection = Self::default();
310
311        for i in iter {
312            collection.enqueue(i.0, i.1);
313        }
314
315        collection
316    }
317}
318
319/// An `IntoIterator` struct for `InversePriorityQueue`
320pub struct InversePriorityQueueIntoIterator<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> {
321    queue: BinaryHeap<Node<P, T>>,
322}
323
324impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> Iterator
325    for InversePriorityQueueIntoIterator<P, T>
326{
327    type Item = (P, T);
328
329    fn next(&mut self) -> Option<Self::Item> {
330        self.queue.pop().map(|node| (node.priority, node.data))
331    }
332}
333
334impl<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> IntoIterator
335    for InversePriorityQueue<P, T>
336{
337    type Item = (P, T);
338    type IntoIter = InversePriorityQueueIntoIterator<P, T>;
339
340    fn into_iter(self) -> Self::IntoIter {
341        InversePriorityQueueIntoIterator { queue: self.queue }
342    }
343}
344
345impl<'b, P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> IntoIterator
346    for &'b InversePriorityQueue<P, T>
347{
348    type IntoIter = InversePriorityQueueIterator<'b, P, T>;
349    type Item = (&'b P, &'b T);
350    fn into_iter(self) -> Self::IntoIter {
351        self.iter()
352    }
353}
354
355#[cfg(test)]
356mod tests {
357    use super::*;
358
359    #[test]
360    fn default_is_empty() {
361        let prio = InversePriorityQueue::<usize, String>::default();
362
363        assert_eq!(prio.len(), 0);
364        assert!(prio.is_empty());
365    }
366
367    #[test]
368    fn enqueue_once_has_size_1() {
369        let mut prio = InversePriorityQueue::<usize, String>::default();
370
371        prio.enqueue(3, String::from("hello world"));
372        assert_eq!(prio.len(), 1);
373        assert_eq!(prio.peek(), Some((&3, &String::from("hello world"))));
374    }
375
376    #[test]
377    fn dequeues_in_order() {
378        let mut prio = InversePriorityQueue::<usize, &str>::default();
379        prio.enqueue(2, "hello");
380        prio.enqueue(3, "julia");
381        prio.enqueue(1, "world");
382        prio.enqueue(3, "naomi");
383
384        assert_eq!(prio.len(), 4);
385
386        assert_eq!(prio.dequeue(), Some((1, "world")));
387        assert_eq!(prio.dequeue(), Some((2, "hello")));
388        assert_eq!(prio.dequeue(), Some((3, "julia")));
389        assert_eq!(prio.dequeue(), Some((3, "naomi")));
390    }
391
392    #[test]
393    fn iterate_over_queue() {
394        let mut prio = InversePriorityQueue::<usize, String>::default();
395        prio.enqueue(2, "hello".to_string());
396        prio.enqueue(3, "julia".to_string());
397        prio.enqueue(1, "world".to_string());
398        prio.enqueue(3, "naomi".to_string());
399
400        let mut new_prio: InversePriorityQueue<usize, String> = prio
401            .iter()
402            .map(|(priority, data)| (*priority, data.clone() + " wow"))
403            .collect();
404
405        assert_eq!(new_prio.dequeue(), Some((1, "world wow".to_string())));
406        assert_eq!(new_prio.dequeue(), Some((2, "hello wow".to_string())));
407        assert_eq!(new_prio.dequeue(), Some((3, "julia wow".to_string())));
408        assert_eq!(new_prio.dequeue(), Some((3, "naomi wow".to_string())));
409    }
410
411    #[test]
412    fn into_iterate_over_queue() {
413        let mut prio = InversePriorityQueue::<usize, String>::default();
414        prio.enqueue(2, "hello".to_string());
415        prio.enqueue(3, "julia".to_string());
416        prio.enqueue(1, "world".to_string());
417        prio.enqueue(3, "naomi".to_string());
418
419        let ref_str = "julia".to_string();
420        assert!(prio.contains(&ref_str));
421        assert!(prio.contains_at(&3, &ref_str));
422        assert!(!prio.contains_at(&2, &ref_str));
423
424        let mut new_prio: InversePriorityQueue<usize, String> = prio
425            .into_iter()
426            .map(|(priority, data)| (priority, data.to_owned() + " wow"))
427            .collect();
428
429        let new_ref_str = "julia wow".to_string();
430        assert!(!new_prio.contains(&ref_str));
431        assert!(!new_prio.contains_at(&3, &ref_str));
432        assert!(!new_prio.contains_at(&2, &ref_str));
433        assert!(new_prio.contains(&new_ref_str));
434        assert!(new_prio.contains_at(&3, &new_ref_str));
435        assert!(!new_prio.contains_at(&2, &new_ref_str));
436
437        assert_eq!(new_prio.dequeue(), Some((1, "world wow".to_string())));
438        assert_eq!(new_prio.dequeue(), Some((2, "hello wow".to_string())));
439        assert_eq!(new_prio.dequeue(), Some((3, "naomi wow".to_string())));
440        assert_eq!(new_prio.dequeue(), Some((3, "julia wow".to_string())));
441    }
442
443    #[test]
444    fn node_order() {
445        let node1 = Node {
446            priority: 3,
447            data: "hello".to_string(),
448        };
449        let node2 = Node {
450            priority: 2,
451            data: "julia".to_string(),
452        };
453
454        assert!(node1 < node2);
455    }
456
457    #[test]
458    fn queue_with_capacity() {
459        let prio = InversePriorityQueue::<usize, String>::with_capacity(10);
460        assert_eq!(prio.len(), 0);
461        assert!(prio.is_empty());
462        assert_eq!(prio.capacity(), 10);
463
464        let default_prio = InversePriorityQueue::<usize, String>::default();
465        assert_eq!(default_prio.len(), 0);
466        assert!(default_prio.is_empty());
467        assert_eq!(default_prio.capacity(), 0);
468    }
469
470    #[test]
471    fn appends_into_queue() {
472        let mut prio = InversePriorityQueue::<usize, &str>::default();
473        assert_eq!(prio.len(), 0);
474        prio.extend([(2, "hello"), (3, "julia"), (1, "world"), (3, "naomi")]);
475        assert_eq!(prio.len(), 4);
476
477        let mut append_prio = InversePriorityQueue::<usize, &str>::default();
478        assert_eq!(append_prio.len(), 0);
479        append_prio.append(prio);
480        assert_eq!(append_prio.len(), 4);
481
482        assert_eq!(append_prio.dequeue(), Some((1, "world")));
483    }
484
485    #[test]
486    fn capacity_management() {
487        let mut prio = InversePriorityQueue::<usize, &str>::default();
488        assert_eq!(prio.capacity(), 0);
489        prio.reserve(3);
490        assert_eq!(prio.capacity(), 4);
491        prio.shrink_to_fit();
492        assert_eq!(prio.capacity(), 0);
493        prio.reserve_exact(3);
494        assert_eq!(prio.capacity(), 3);
495        prio.shrink_to(2);
496        assert_eq!(prio.capacity(), 2);
497    }
498
499    #[test]
500    fn clears_queue() {
501        let mut prio = InversePriorityQueue::<usize, String>::default();
502        prio.enqueue(2, "hello".to_string());
503        prio.enqueue(3, "julia".to_string());
504        prio.enqueue(1, "world".to_string());
505        prio.enqueue(3, "naomi".to_string());
506
507        assert_eq!(prio.len(), 4);
508        prio.clear();
509        assert_eq!(prio.len(), 0);
510    }
511
512    #[test]
513    fn drain_queue() {
514        let mut prio = InversePriorityQueue::<usize, String>::default();
515        prio.enqueue(2, "hello".to_string());
516
517        assert!(!prio.is_empty());
518
519        for x in prio.drain() {
520            assert_eq!(x, (2, "hello".to_string()));
521        }
522
523        assert!(prio.is_empty());
524    }
525
526    #[test]
527    fn remove_node() {
528        let mut prio = InversePriorityQueue::<usize, String>::default();
529        prio.enqueue(5, "julia".to_string());
530        prio.enqueue(2, "hello".to_string());
531        prio.enqueue(3, "julia".to_string());
532        prio.enqueue(1, "world".to_string());
533        prio.enqueue(3, "naomi".to_string());
534
535        let ref_str = "julia".to_string();
536        assert!(prio.remove(&ref_str));
537
538        // assert_eq!(prio.dequeue(), Some((3, "julia".to_string())));
539        assert_eq!(prio.dequeue(), Some((1, "world".to_string())));
540        assert_eq!(prio.dequeue(), Some((2, "hello".to_string())));
541        assert_eq!(prio.dequeue(), Some((3, "naomi".to_string())));
542    }
543
544    #[test]
545    fn remove_node_at_prio() {
546        let mut prio = InversePriorityQueue::<usize, String>::default();
547        prio.enqueue(5, "julia".to_string());
548        prio.enqueue(2, "hello".to_string());
549        prio.enqueue(3, "julia".to_string());
550        prio.enqueue(1, "world".to_string());
551        prio.enqueue(3, "naomi".to_string());
552
553        let ref_str = "julia".to_string();
554        assert!(prio.remove_at(&3, &ref_str));
555
556        assert_eq!(prio.dequeue(), Some((1, "world".to_string())));
557        assert_eq!(prio.dequeue(), Some((2, "hello".to_string())));
558        assert_eq!(prio.dequeue(), Some((3, "naomi".to_string())));
559        assert_eq!(prio.dequeue(), Some((5, "julia".to_string())));
560    }
561
562    #[test]
563    fn update() {
564        let mut prio = InversePriorityQueue::<usize, String>::default();
565        prio.enqueue(5, "julia".to_string());
566        prio.enqueue(2, "hello".to_string());
567        prio.enqueue(3, "julia".to_string());
568        prio.enqueue(1, "world".to_string());
569        prio.enqueue(3, "naomi".to_string());
570
571        let ref_str = "julia".to_string();
572        let mut new = prio.update(3, 7, &ref_str);
573
574        assert_eq!(new.dequeue(), Some((1, "world".to_string())));
575        assert_eq!(new.dequeue(), Some((2, "hello".to_string())));
576        assert_eq!(new.dequeue(), Some((3, "naomi".to_string())));
577        assert_eq!(new.dequeue(), Some((5, "julia".to_string())));
578        assert_eq!(new.dequeue(), Some((7, "julia".to_string())));
579    }
580
581    #[test]
582    fn min_max() {
583        let mut prio = InversePriorityQueue::<usize, String>::default();
584        prio.enqueue(5, "julia".to_string());
585        prio.enqueue(2, "hello".to_string());
586        prio.enqueue(3, "julia".to_string());
587        prio.enqueue(1, "world".to_string());
588        prio.enqueue(3, "naomi".to_string());
589
590        assert_eq!(prio.max_node(), Some((&5, &"julia".to_string())));
591        assert_eq!(prio.min_node(), Some((&1, &"world".to_string())));
592    }
593
594    #[test]
595    fn update_as() {
596        let mut prio = InversePriorityQueue::<usize, String>::default();
597        prio.enqueue(5, "julia".to_string());
598        prio.enqueue(2, "hello".to_string());
599        prio.enqueue(3, "julia".to_string());
600        prio.enqueue(1, "world".to_string());
601        prio.enqueue(3, "naomi".to_string());
602
603        let ref_str = "julia".to_string();
604        prio.update_as(3, 7, ref_str);
605
606        assert_eq!(prio.dequeue(), Some((1, "world".to_string())));
607        assert_eq!(prio.dequeue(), Some((2, "hello".to_string())));
608        assert_eq!(prio.dequeue(), Some((3, "naomi".to_string())));
609        assert_eq!(prio.dequeue(), Some((5, "julia".to_string())));
610        assert_eq!(prio.dequeue(), Some((7, "julia".to_string())));
611    }
612}
queue_queue/inverse.rs

queue_queue/
inverse.rs
