queue_queue/
lib.rs

1pub mod inverse;
2pub mod rusty;
3
4pub trait PriorityQueue<P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq> {
5    /// Add an item to the queue
6    fn enqueue(&mut self, priority: P, data: T);
7
8    /// Remove an item from the queue
9    fn dequeue(&mut self) -> Option<(P, T)>;
10
11    /// Peeks the next item in the queue
12    fn peek(&self) -> Option<(&P, &T)>;
13
14    /// Queue length
15    fn len(&self) -> usize;
16
17    /// Boolean if the queue is empty
18    fn is_empty(&self) -> bool;
19
20    /// Queue capacity
21    fn capacity(&self) -> usize;
22
23    /// Check if an item exists in the queue
24    /// true if it exists, false if it does not
25    fn contains(&self, data: &T) -> bool;
26
27    /// Check if an item exists in the queue at a certain priority
28    /// true if it exists, false if it does not
29    fn contains_at(&self, priority: &P, data: &T) -> bool;
30
31    /// Remove all existing items from the queue
32    /// true if it was removed, false if it was not
33    fn remove(&mut self, data: &T) -> bool;
34
35    /// Remove an item from the queue if exists at a certain priority
36    /// true if it was removed, false if it was not
37    fn remove_at(&mut self, priority: &P, data: &T) -> bool;
38
39    /// Create a new priority queue with a given capacity
40    ///
41    /// # Example:
42    ///
43    /// `RustyPriorityQueue::<usize, &str>::with_capacity(10)`
44    fn with_capacity(capacity: usize) -> Self;
45
46    /// Append another priority queue into this one
47    ///
48    /// * Consumes the other priority queue
49    fn append(&mut self, other: Self);
50
51    /// Extend the priority queue with an `IntoIterator` of `(P, T)` => `(Priority, Data)`
52    /// where `P: PartialOrd + PartialEq + Eq, T: PartialEq + Eq`
53    fn extend<I>(&mut self, iter: I)
54    where
55        I: IntoIterator<Item = (P, T)>;
56
57    /// Reserves capacity for at least additional elements more than the current length.
58    /// The allocator may reserve more space to speculatively avoid frequent allocations.
59    /// After calling reserve, capacity will be greater than or equal to `self.len() + additional`.
60    /// Does nothing if capacity is already sufficient.
61    ///
62    /// # Panics
63    /// Panics if the new capacity overflows usize.
64    fn reserve(&mut self, additional: usize);
65
66    /// Reserves the minimum capacity for at least additional elements more than the current length.
67    /// Unlike reserve, this will not deliberately over-allocate to speculatively avoid frequent allocations.
68    /// After calling `reserve_exact`, capacity will be greater than or equal to `self.len() + additional`.
69    /// Does nothing if the capacity is already sufficient.
70    ///
71    /// # Panics
72    /// Panics if the new capacity overflows usize.
73    fn reserve_exact(&mut self, additional: usize);
74
75    /// Discards as much additional capacity as possible.
76    fn shrink_to_fit(&mut self);
77
78    /// Discards capacity with a lower bound.
79    /// The capacity will remain at least as large as both the length and the supplied value.
80    /// If the current capacity is less than the lower limit, this is a no-op.
81    fn shrink_to(&mut self, capacity: usize);
82
83    /// Removes all items from the queue
84    fn clear(&mut self);
85
86    /// Clears the binary heap, returning an iterator over the removed elements
87    /// in arbitrary order. If the iterator is dropped before being fully
88    /// consumed, it drops the remaining elements in arbitrary order.
89    ///
90    /// The returned iterator keeps a mutable borrow on the heap to optimize
91    /// its implementation.
92    ///
93    /// # Examples
94    ///
95    /// Basic usage:
96    ///
97    /// ```
98    /// # use queue_queue::rusty::RustyPriorityQueue;
99    /// # use queue_queue::PriorityQueue;
100    ///
101    /// let mut prio = RustyPriorityQueue::<usize, String>::default();
102    /// prio.enqueue(2, "hello".to_string());
103    ///
104    /// assert!(!prio.is_empty());
105    ///
106    /// for x in prio.drain() {
107    ///     println!("{x:?}");
108    /// }
109    ///
110    /// assert!(prio.is_empty());
111    /// ```
112    fn drain(&mut self) -> impl Iterator<Item = (P, T)> + '_;
113
114    /// Returns the node the the highest priority in the queue.
115    /// If no nodes exist, `None` is returned.
116    fn max_node(&self) -> Option<(&P, &T)>;
117
118    /// Returns the node the the lowest priority in the queue.
119    /// If no nodes exist, `None` is returned.
120    fn min_node(&self) -> Option<(&P, &T)>;
121}
122
123pub mod prelude {
124    pub use super::PriorityQueue;
125    pub use crate::inverse::InversePriorityQueue;
126    pub use crate::rusty::RustyPriorityQueue;
127}
queue_queue/lib.rs

queue_queue/
lib.rs
