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

queue_queue/
rusty.rs
