splay_tree/
heap.rs

1//! A priority queue implemented with a splay tree.
2use crate::iter;
3use crate::tree_core;
4use std::cmp;
5
6/// `SplayHeap` iterator.
7pub struct Iter<'a, T: 'a> {
8    iter: iter::Iter<'a, Item<T>, ()>,
9}
10impl<'a, T: 'a> Iter<'a, T> {
11    fn new(tree: &'a tree_core::Tree<Item<T>, ()>) -> Self {
12        Iter { iter: tree.iter() }
13    }
14}
15impl<'a, T: 'a> Iterator for Iter<'a, T> {
16    type Item = &'a T;
17    fn next(&mut self) -> Option<Self::Item> {
18        self.iter.next().map(|(i, _)| &i.0)
19    }
20}
21
22/// An iterator that moves out of a `SplayHeap`.
23pub struct IntoIter<T>(iter::IntoIter<Item<T>, ()>);
24impl<T> Iterator for IntoIter<T> {
25    type Item = T;
26    fn next(&mut self) -> Option<Self::Item> {
27        self.0.next().map(|(k, _)| k.0)
28    }
29}
30
31#[derive(Debug, Clone, PartialEq, Eq)]
32#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
33struct Item<T>(T, u64);
34
35impl<T> PartialOrd for Item<T>
36where
37    T: PartialOrd,
38{
39    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
40        self.0.partial_cmp(&other.0).map(|order| match order {
41            cmp::Ordering::Equal => self.1.cmp(&other.1),
42            cmp::Ordering::Less => cmp::Ordering::Greater,
43            cmp::Ordering::Greater => cmp::Ordering::Less,
44        })
45    }
46}
47
48impl<T> Ord for Item<T>
49where
50    T: Ord,
51{
52    fn cmp(&self, other: &Self) -> cmp::Ordering {
53        match self.0.cmp(&other.0) {
54            cmp::Ordering::Equal => self.1.cmp(&other.1),
55            cmp::Ordering::Less => cmp::Ordering::Greater,
56            cmp::Ordering::Greater => cmp::Ordering::Less,
57        }
58    }
59}
60
61/// A priority queue implemented with a splay tree.
62///
63/// This will be a max-heap.
64///
65/// A splay tree based heap is a self-adjusting data structure.
66/// It performs pushing and popping in `O(log n)` amortized time.
67///
68/// It is a logic error for a key to be modified in such a way that
69/// the key's ordering relative to any other key,
70/// as determined by the `Ord` trait, changes while it is in the map.
71/// This is normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
72///
73/// # Examples
74/// ```
75/// use splay_tree::SplayHeap;
76///
77/// let mut heap = SplayHeap::new();
78///
79/// heap.push(0);
80/// heap.push(10);
81/// heap.push(7);
82///
83/// assert_eq!(heap.peek(), Some(&10));
84/// assert_eq!(heap.pop(), Some(10));
85/// assert_eq!(heap.pop(), Some(7));
86/// assert_eq!(heap.pop(), Some(0));
87/// assert_eq!(heap.pop(), None);
88/// ```
89#[derive(Debug, Clone)]
90#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
91pub struct SplayHeap<T> {
92    tree: tree_core::Tree<Item<T>, ()>,
93    seq: u64,
94}
95impl<T> SplayHeap<T>
96where
97    T: Ord,
98{
99    /// Creates an empty `SplayHeap` as a max-heap.
100    ///
101    /// # Examples
102    /// ```
103    /// use splay_tree::SplayHeap;
104    /// let mut heap = SplayHeap::new();
105    ///
106    /// heap.push(10);
107    /// assert_eq!(heap.pop(), Some(10));
108    /// ```
109    pub fn new() -> Self {
110        SplayHeap {
111            tree: tree_core::Tree::new(),
112            seq: 0,
113        }
114    }
115
116    /// Returns the greatest item in the heap, or `None` if it is empty.
117    ///
118    /// # NOTICE
119    /// Because `SplayHeap` is a self-adjusting amortized data structure,
120    /// this function requires the `mut` qualifier.
121    ///
122    /// # Examples
123    /// ```
124    /// use splay_tree::SplayHeap;
125    /// let mut heap = SplayHeap::new();
126    /// assert_eq!(heap.peek(), None);
127    ///
128    /// heap.push(1);
129    /// heap.push(5);
130    /// heap.push(2);
131    /// assert_eq!(heap.peek(), Some(&5));
132    /// ```
133    pub fn peek(&mut self) -> Option<&T> {
134        self.tree.get_lftmost().map(|(i, _)| &i.0)
135    }
136
137    /// Immutable version of [`SplayHeap::peek()`].
138    ///
139    /// Note that this method could be less efficient than the mutable version.
140    ///
141    /// # Examples
142    /// ```
143    /// use splay_tree::SplayHeap;
144    /// let mut heap = SplayHeap::new();
145    /// assert_eq!(heap.peek_immut(), None);
146    ///
147    /// heap.push(1);
148    /// heap.push(5);
149    /// heap.push(2);
150    /// assert_eq!(heap.peek_immut(), Some(&5));
151    /// ```
152    pub fn peek_immut(&self) -> Option<&T> {
153        self.tree.get_lftmost_immut().map(|(i, _)| &i.0)
154    }
155
156    /// Removes the greatest item from the heap and returns it, or `None` if it is empty.
157    ///
158    /// # Examples
159    /// ```
160    /// use splay_tree::SplayHeap;
161    /// let mut heap: SplayHeap<_> = vec![1, 3].into_iter().collect();
162    ///
163    /// assert_eq!(heap.pop(), Some(3));
164    /// assert_eq!(heap.pop(), Some(1));
165    /// assert_eq!(heap.pop(), None);
166    /// ```
167    pub fn pop(&mut self) -> Option<T> {
168        self.tree.take_lftmost().map(|(i, _)| i.0)
169    }
170
171    /// Pushes an item onto the heap.
172    ///
173    /// # Examples
174    /// ```
175    /// use splay_tree::SplayHeap;
176    /// let mut heap = SplayHeap::new();
177    /// heap.push(3);
178    /// heap.push(5);
179    /// heap.push(1);
180    ///
181    /// assert_eq!(heap.len(), 3);
182    /// assert_eq!(heap.peek(), Some(&5));
183    /// ```
184    pub fn push(&mut self, item: T) {
185        let seq = self.seq;
186        self.seq = seq.wrapping_add(1);
187        self.tree.insert(Item(item, seq), ());
188    }
189
190    /// Drops all items from the heap.
191    ///
192    /// # Examples
193    /// ```
194    /// use splay_tree::SplayHeap;
195    /// let mut heap: SplayHeap<_> = vec![1, 3].into_iter().collect();
196    ///
197    /// assert!(!heap.is_empty());
198    /// heap.clear();
199    /// assert!(heap.is_empty());
200    /// ```
201    pub fn clear(&mut self) {
202        self.tree = tree_core::Tree::new();
203    }
204}
205impl<T> SplayHeap<T> {
206    /// Returns an iterator visiting all items in sorted (descending) order.
207    ///
208    /// # Examples
209    /// ```
210    /// use splay_tree::SplayHeap;
211    /// let heap: SplayHeap<_> = vec![1, 4, 2, 3].into_iter().collect();
212    ///
213    /// // Print all values in `heap` in sorted order
214    /// for x in heap.iter() {
215    ///   println!("{}", x);
216    /// }
217    /// ```
218    pub fn iter(&self) -> Iter<T> {
219        Iter::new(&self.tree)
220    }
221
222    /// Returns the length of the heap.
223    ///
224    /// # Examples
225    /// ```
226    /// use splay_tree::SplayHeap;
227    /// let heap: SplayHeap<_> = vec![1, 3].into_iter().collect();
228    ///
229    /// assert_eq!(heap.len(), 2);
230    /// ```
231    pub fn len(&self) -> usize {
232        self.tree.len()
233    }
234
235    /// Checkes if the heap is empty.
236    ///
237    /// # Examples
238    /// ```
239    /// use splay_tree::SplayHeap;
240    /// let mut heap = SplayHeap::new();
241    ///
242    /// assert!(heap.is_empty());
243    ///
244    /// heap.push(1);
245    /// assert!(!heap.is_empty());
246    ///
247    /// heap.pop();
248    /// assert!(heap.is_empty());
249    /// ```
250    pub fn is_empty(&self) -> bool {
251        self.len() == 0
252    }
253}
254impl<T> Default for SplayHeap<T>
255where
256    T: Ord,
257{
258    fn default() -> Self {
259        SplayHeap::new()
260    }
261}
262impl<T> std::iter::FromIterator<T> for SplayHeap<T>
263where
264    T: Ord,
265{
266    fn from_iter<I>(iter: I) -> Self
267    where
268        I: IntoIterator<Item = T>,
269    {
270        let mut heap = SplayHeap::new();
271        for x in iter {
272            heap.push(x);
273        }
274        heap
275    }
276}
277impl<T> IntoIterator for SplayHeap<T> {
278    type Item = T;
279    type IntoIter = IntoIter<T>;
280    fn into_iter(self) -> Self::IntoIter {
281        IntoIter(self.tree.into_iter())
282    }
283}
284impl<'a, T> IntoIterator for &'a SplayHeap<T> {
285    type Item = &'a T;
286    type IntoIter = Iter<'a, T>;
287    fn into_iter(self) -> Self::IntoIter {
288        self.iter()
289    }
290}
291impl<T> Extend<T> for SplayHeap<T>
292where
293    T: Ord,
294{
295    fn extend<I>(&mut self, iter: I)
296    where
297        I: IntoIterator<Item = T>,
298    {
299        for x in iter {
300            self.push(x);
301        }
302    }
303}
304impl<'a, T> Extend<&'a T> for SplayHeap<T>
305where
306    T: Copy + 'a + Ord,
307{
308    fn extend<I>(&mut self, iter: I)
309    where
310        I: IntoIterator<Item = &'a T>,
311    {
312        for x in iter {
313            self.push(*x);
314        }
315    }
316}
splay_tree/heap.rs

splay_tree/
heap.rs
