SHARE
TWEET

binary_heap.rs

a guest Jan 16th, 2020 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #![allow(missing_docs)]
  2. #![feature(const_generics)]
  3. #![feature(trusted_len)]
  4. #![feature(exact_size_is_empty)]
  5.  
  6. use core::fmt;
  7. use core::iter::{FromIterator, FusedIterator, TrustedLen};
  8. use core::mem::{swap, ManuallyDrop};
  9. use core::ops::{Deref, DerefMut};
  10. use core::ptr;
  11.  
  12. use staticvec::StaticVec;
  13.  
  14. /// A priority queue implemented with a binary heap.
  15. ///
  16. /// This will be a max-heap.
  17. ///
  18. /// It is a logic error for an item to be modified in such a way that the
  19. /// item's ordering relative to any other item, as determined by the `Ord`
  20. /// trait, changes while it is in the heap. This is normally only possible
  21. /// through `Cell`, `RefCell`, global state, I/O, or unsafe code.
  22. ///
  23. /// # Examples
  24. ///
  25. /// ```
  26. /// use std::collections::BinaryHeap;
  27. ///
  28. /// // Type inference lets us omit an explicit type signature (which
  29. /// // would be `BinaryHeap<i32>` in this example).
  30. /// let mut heap = BinaryHeap::new();
  31. ///
  32. /// // We can use peek to look at the next item in the heap. In this case,
  33. /// // there's no items in there yet so we get None.
  34. /// assert_eq!(heap.peek(), None);
  35. ///
  36. /// // Let's add some scores...
  37. /// heap.push(1);
  38. /// heap.push(5);
  39. /// heap.push(2);
  40. ///
  41. /// // Now peek shows the most important item in the heap.
  42. /// assert_eq!(heap.peek(), Some(&5));
  43. ///
  44. /// // We can check the length of a heap.
  45. /// assert_eq!(heap.len(), 3);
  46. ///
  47. /// // We can iterate over the items in the heap, although they are returned in
  48. /// // a random order.
  49. /// for x in &heap {
  50. ///     println!("{}", x);
  51. /// }
  52. ///
  53. /// // If we instead pop these scores, they should come back in order.
  54. /// assert_eq!(heap.pop(), Some(5));
  55. /// assert_eq!(heap.pop(), Some(2));
  56. /// assert_eq!(heap.pop(), Some(1));
  57. /// assert_eq!(heap.pop(), None);
  58. ///
  59. /// // We can clear the heap of any remaining items.
  60. /// heap.clear();
  61. ///
  62. /// // The heap should now be empty.
  63. /// assert!(heap.is_empty())
  64. /// ```
  65. ///
  66. /// ## Min-heap
  67. ///
  68. /// Either `std::cmp::Reverse` or a custom `Ord` implementation can be used to
  69. /// make `BinaryHeap` a min-heap. This makes `heap.pop()` return the smallest
  70. /// value instead of the greatest one.
  71. ///
  72. /// ```
  73. /// use std::collections::BinaryHeap;
  74. /// use std::cmp::Reverse;
  75. ///
  76. /// let mut heap = BinaryHeap::new();
  77. ///
  78. /// // Wrap values in `Reverse`
  79. /// heap.push(Reverse(1));
  80. /// heap.push(Reverse(5));
  81. /// heap.push(Reverse(2));
  82. ///
  83. /// // If we pop these scores now, they should come back in the reverse order.
  84. /// assert_eq!(heap.pop(), Some(Reverse(1)));
  85. /// assert_eq!(heap.pop(), Some(Reverse(2)));
  86. /// assert_eq!(heap.pop(), Some(Reverse(5)));
  87. /// assert_eq!(heap.pop(), None);
  88. /// ```
  89. ///
  90. /// # Time complexity
  91. ///
  92. /// | [push] | [pop]    | [peek]/[peek\_mut] |
  93. /// |--------|----------|--------------------|
  94. /// | O(1)~  | O(log n) | O(1)               |
  95. ///
  96. /// The value for `push` is an expected cost; the method documentation gives a
  97. /// more detailed analysis.
  98. ///
  99. /// [push]: #method.push
  100. /// [pop]: #method.pop
  101. /// [peek]: #method.peek
  102. /// [peek\_mut]: #method.peek_mut
  103.  
  104. pub struct BinaryHeap<T, const K: usize> {
  105.     data: StaticVec<T, K>,
  106. }
  107.  
  108. /// Structure wrapping a mutable reference to the greatest item on a
  109. /// `BinaryHeap`.
  110. ///
  111. /// This `struct` is created by the [`peek_mut`] method on [`BinaryHeap`]. See
  112. /// its documentation for more.
  113. ///
  114. /// [`peek_mut`]: struct.BinaryHeap.html#method.peek_mut
  115. /// [`BinaryHeap`]: struct.BinaryHeap.html
  116.  
  117. pub struct PeekMut<'a, T: 'a + Ord, const K: usize> {
  118.     heap: &'a mut BinaryHeap<T, K>,
  119.    sift: bool,
  120. }
  121.  
  122. impl<T: Ord + fmt::Debug, const K: usize> fmt::Debug for PeekMut<'_, T, K> {
  123.     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  124.        f.debug_tuple("PeekMut").field(&self.heap.data[0]).finish()
  125.    }
  126. }
  127.  
  128. impl<T: Ord, const K: usize> Drop for PeekMut<'_, T, K> {
  129.     fn drop(&mut self) {
  130.         if self.sift {
  131.             self.heap.sift_down(0);
  132.         }
  133.     }
  134. }
  135.  
  136. impl<T: Ord, const K: usize> Deref for PeekMut<'_, T, K> {
  137.    type Target = T;
  138.    fn deref(&self) -> &T {
  139.        debug_assert!(!self.heap.is_empty());
  140.        // SAFE: PeekMut is only instantiated for non-empty heaps
  141.        unsafe { self.heap.data.get_unchecked(0) }
  142.    }
  143. }
  144.  
  145. impl<T: Ord, const K: usize> DerefMut for PeekMut<'_, T, K> {
  146.     fn deref_mut(&mut self) -> &mut T {
  147.         debug_assert!(!self.heap.is_empty());
  148.         // SAFE: PeekMut is only instantiated for non-empty heaps
  149.         unsafe { self.heap.data.get_unchecked_mut(0) }
  150.     }
  151. }
  152.  
  153. impl<'a, T: Ord, const K: usize> PeekMut<'a, T, K> {
  154.     /// Removes the peeked value from the heap and returns it.
  155.  
  156.     pub fn pop(mut this: PeekMut<'a, T, K>) -> T {
  157.        let value = this.heap.pop().unwrap();
  158.        this.sift = false;
  159.        value
  160.    }
  161. }
  162.  
  163. impl<T: Clone, const K: usize> Clone for BinaryHeap<T, K> {
  164.    fn clone(&self) -> Self {
  165.        BinaryHeap {
  166.            data: self.data.clone(),
  167.        }
  168.    }
  169.  
  170.    fn clone_from(&mut self, source: &Self) {
  171.        self.data.clone_from(&source.data);
  172.    }
  173. }
  174.  
  175. impl<T: Ord, const K: usize> Default for BinaryHeap<T, K> {
  176.    /// Creates an empty `BinaryHeap<T>`.
  177.    #[inline]
  178.    fn default() -> BinaryHeap<T, K> {
  179.        BinaryHeap::new()
  180.    }
  181. }
  182.  
  183. impl<T: fmt::Debug, const K: usize> fmt::Debug for BinaryHeap<T, K> {
  184.    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  185.         f.debug_list().entries(self.iter()).finish()
  186.     }
  187. }
  188.  
  189. impl<T: Ord, const K: usize> BinaryHeap<T, K> {
  190.     /// Creates an empty `BinaryHeap` as a max-heap.
  191.     ///
  192.     /// # Examples
  193.     ///
  194.     /// Basic usage:
  195.     ///
  196.     /// ```
  197.     /// use std::collections::BinaryHeap;
  198.     /// let mut heap = BinaryHeap::new();
  199.     /// heap.push(4);
  200.     /// ```
  201.  
  202.     pub fn new() -> BinaryHeap<T, K> {
  203.         BinaryHeap {
  204.             data: StaticVec::new(),
  205.         }
  206.     }
  207.  
  208.     /// Returns a mutable reference to the greatest item in the binary heap, or
  209.     /// `None` if it is empty.
  210.     ///
  211.     /// Note: If the `PeekMut` value is leaked, the heap may be in an
  212.     /// inconsistent state.
  213.     ///
  214.     /// # Examples
  215.     ///
  216.     /// Basic usage:
  217.     ///
  218.     /// ```
  219.     /// use std::collections::BinaryHeap;
  220.     /// let mut heap = BinaryHeap::new();
  221.     /// assert!(heap.peek_mut().is_none());
  222.     ///
  223.     /// heap.push(1);
  224.     /// heap.push(5);
  225.     /// heap.push(2);
  226.     /// {
  227.     ///     let mut val = heap.peek_mut().unwrap();
  228.     ///     *val = 0;
  229.     /// }
  230.     /// assert_eq!(heap.peek(), Some(&2));
  231.     /// ```
  232.     ///
  233.     /// # Time complexity
  234.     ///
  235.     /// Cost is O(1) in the worst case.
  236.  
  237.     pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, K>> {
  238.        if self.is_empty() {
  239.            None
  240.        } else {
  241.            Some(PeekMut {
  242.                heap: self,
  243.                sift: true,
  244.            })
  245.        }
  246.    }
  247.  
  248.    /// Removes the greatest item from the binary heap and returns it, or `None` if it
  249.    /// is empty.
  250.    ///
  251.    /// # Examples
  252.    ///
  253.    /// Basic usage:
  254.    ///
  255.    /// ```
  256.    /// use std::collections::BinaryHeap;
  257.    /// let mut heap = BinaryHeap::from(vec![1, 3]);
  258.    ///
  259.    /// assert_eq!(heap.pop(), Some(3));
  260.    /// assert_eq!(heap.pop(), Some(1));
  261.    /// assert_eq!(heap.pop(), None);
  262.    /// ```
  263.    ///
  264.    /// # Time complexity
  265.    ///
  266.    /// The worst case cost of `pop` on a heap containing *n* elements is O(log
  267.    /// n).
  268.  
  269.    pub fn pop(&mut self) -> Option<T> {
  270.        self.data.pop().map(|mut item| {
  271.            if !self.is_empty() {
  272.                swap(&mut item, &mut self.data[0]);
  273.                self.sift_down_to_bottom(0);
  274.            }
  275.            item
  276.        })
  277.    }
  278.  
  279.    /// Pushes an item onto the binary heap.
  280.    ///
  281.    /// # Examples
  282.    ///
  283.    /// Basic usage:
  284.    ///
  285.    /// ```
  286.    /// use std::collections::BinaryHeap;
  287.    /// let mut heap = BinaryHeap::new();
  288.    /// heap.push(3);
  289.    /// heap.push(5);
  290.    /// heap.push(1);
  291.    ///
  292.    /// assert_eq!(heap.len(), 3);
  293.    /// assert_eq!(heap.peek(), Some(&5));
  294.    /// ```
  295.    ///
  296.    /// # Time complexity
  297.    ///
  298.    /// The expected cost of `push`, averaged over every possible ordering of
  299.    /// the elements being pushed, and over a sufficiently large number of
  300.    /// pushes, is O(1). This is the most meaningful cost metric when pushing
  301.    /// elements that are *not* already in any sorted pattern.
  302.    ///
  303.    /// The time complexity degrades if elements are pushed in predominantly
  304.    /// ascending order. In the worst case, elements are pushed in ascending
  305.    /// sorted order and the amortized cost per push is O(log n) against a heap
  306.    /// containing *n* elements.
  307.    ///
  308.    /// The worst case cost of a *single* call to `push` is O(n). The worst case
  309.    /// occurs when capacity is exhausted and needs a resize. The resize cost
  310.    /// has been amortized in the previous figures.
  311.  
  312.    pub fn push(&mut self, item: T) {
  313.        let old_len = self.len();
  314.        self.data.push(item);
  315.        self.sift_up(0, old_len);
  316.    }
  317.  
  318.    /// Consumes the `BinaryHeap` and returns a vector in sorted
  319.    /// (ascending) order.
  320.    ///
  321.    /// # Examples
  322.    ///
  323.    /// Basic usage:
  324.    ///
  325.    /// ```
  326.    /// use std::collections::BinaryHeap;
  327.    ///
  328.    /// let mut heap = BinaryHeap::from(vec![1, 2, 4, 5, 7]);
  329.    /// heap.push(6);
  330.    /// heap.push(3);
  331.    ///
  332.    /// let vec = heap.into_sorted_vec();
  333.    /// assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);
  334.    /// ```
  335.  
  336.    pub fn into_sorted_vec(mut self) -> StaticVec<T, K> {
  337.        let mut end = self.len();
  338.        while end > 1 {
  339.            end -= 1;
  340.            self.data.swap(0, end);
  341.            self.sift_down_range(0, end);
  342.        }
  343.        self.into_vec()
  344.    }
  345.  
  346.    // The implementations of sift_up and sift_down use unsafe blocks in
  347.    // order to move an element out of the vector (leaving behind a
  348.    // hole), shift along the others and move the removed element back into the
  349.    // vector at the final location of the hole.
  350.    // The `Hole` type is used to represent this, and make sure
  351.    // the hole is filled back at the end of its scope, even on panic.
  352.    // Using a hole reduces the constant factor compared to using swaps,
  353.    // which involves twice as many moves.
  354.    fn sift_up(&mut self, start: usize, pos: usize) -> usize {
  355.        unsafe {
  356.            // Take out the value at `pos` and create a hole.
  357.            let mut hole = Hole::new(&mut self.data, pos);
  358.  
  359.            while hole.pos() > start {
  360.                let parent = (hole.pos() - 1) / 2;
  361.                if hole.element() <= hole.get(parent) {
  362.                    break;
  363.                }
  364.                hole.move_to(parent);
  365.            }
  366.            hole.pos()
  367.        }
  368.    }
  369.  
  370.    /// Take an element at `pos` and move it down the heap,
  371.    /// while its children are larger.
  372.    fn sift_down_range(&mut self, pos: usize, end: usize) {
  373.        unsafe {
  374.            let mut hole = Hole::new(&mut self.data, pos);
  375.            let mut child = 2 * pos + 1;
  376.            while child < end {
  377.                let right = child + 1;
  378.                // compare with the greater of the two children
  379.                if right < end && !(hole.get(child) > hole.get(right)) {
  380.                    child = right;
  381.                }
  382.                // if we are already in order, stop.
  383.                if hole.element() >= hole.get(child) {
  384.                    break;
  385.                }
  386.                hole.move_to(child);
  387.                child = 2 * hole.pos() + 1;
  388.            }
  389.        }
  390.    }
  391.  
  392.    fn sift_down(&mut self, pos: usize) {
  393.        let len = self.len();
  394.        self.sift_down_range(pos, len);
  395.    }
  396.  
  397.    /// Take an element at `pos` and move it all the way down the heap,
  398.    /// then sift it up to its position.
  399.    ///
  400.    /// Note: This is faster when the element is known to be large / should
  401.    /// be closer to the bottom.
  402.    fn sift_down_to_bottom(&mut self, mut pos: usize) {
  403.        let end = self.len();
  404.        let start = pos;
  405.        unsafe {
  406.            let mut hole = Hole::new(&mut self.data, pos);
  407.            let mut child = 2 * pos + 1;
  408.            while child < end {
  409.                let right = child + 1;
  410.                // compare with the greater of the two children
  411.                if right < end && !(hole.get(child) > hole.get(right)) {
  412.                    child = right;
  413.                }
  414.                hole.move_to(child);
  415.                child = 2 * hole.pos() + 1;
  416.            }
  417.            pos = hole.pos;
  418.        }
  419.        self.sift_up(start, pos);
  420.    }
  421.  
  422.    fn rebuild(&mut self) {
  423.        let mut n = self.len() / 2;
  424.        while n > 0 {
  425.            n -= 1;
  426.            self.sift_down(n);
  427.        }
  428.    }
  429.  
  430.    /// Returns an iterator which retrieves elements in heap order.
  431.    /// The retrieved elements are removed from the original heap.
  432.    /// The remaining elements will be removed on drop in heap order.
  433.    ///
  434.    /// Note:
  435.    /// * `.drain_sorted()` is O(n lg n); much slower than `.drain()`.
  436.    ///   You should use the latter for most cases.
  437.    ///
  438.    /// # Examples
  439.    ///
  440.    /// Basic usage:
  441.    ///
  442.    /// ```
  443.    /// #![feature(binary_heap_drain_sorted)]
  444.    /// use std::collections::BinaryHeap;
  445.    ///
  446.    /// let mut heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);
  447.    /// assert_eq!(heap.len(), 5);
  448.    ///
  449.    /// drop(heap.drain_sorted()); // removes all elements in heap order
  450.    /// assert_eq!(heap.len(), 0);
  451.    /// ```
  452.    #[inline]
  453.  
  454.    pub fn drain_sorted(&mut self) -> DrainSorted<'_, T, K> {
  455.         DrainSorted { inner: self }
  456.     }
  457. }
  458.  
  459. impl<T, const K: usize> BinaryHeap<T, K> {
  460.     /// Returns an iterator visiting all values in the underlying vector, in
  461.     /// arbitrary order.
  462.     ///
  463.     /// # Examples
  464.     ///
  465.     /// Basic usage:
  466.     ///
  467.     /// ```
  468.     /// use std::collections::BinaryHeap;
  469.     /// let heap = BinaryHeap::from(vec![1, 2, 3, 4]);
  470.     ///
  471.     /// // Print 1, 2, 3, 4 in arbitrary order
  472.     /// for x in heap.iter() {
  473.     ///     println!("{}", x);
  474.     /// }
  475.     /// ```
  476.  
  477.     pub fn iter(&self) -> staticvec::StaticVecIterConst<'_, T, K> {
  478.        self.data.iter()
  479.    }
  480.  
  481.    /// Returns an iterator which retrieves elements in heap order.
  482.    /// This method consumes the original heap.
  483.    ///
  484.    /// # Examples
  485.    ///
  486.    /// Basic usage:
  487.    ///
  488.    /// ```
  489.    /// #![feature(binary_heap_into_iter_sorted)]
  490.    /// use std::collections::BinaryHeap;
  491.    /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);
  492.    ///
  493.    /// assert_eq!(heap.into_iter_sorted().take(2).collect::<Vec<_>>(), vec![5, 4]);
  494.    /// ```
  495.  
  496.    pub fn into_iter_sorted(self) -> IntoIterSorted<T, K> {
  497.        IntoIterSorted { inner: self }
  498.    }
  499.  
  500.    /// Returns the greatest item in the binary heap, or `None` if it is empty.
  501.    ///
  502.    /// # Examples
  503.    ///
  504.    /// Basic usage:
  505.    ///
  506.    /// ```
  507.    /// use std::collections::BinaryHeap;
  508.    /// let mut heap = BinaryHeap::new();
  509.    /// assert_eq!(heap.peek(), None);
  510.    ///
  511.    /// heap.push(1);
  512.    /// heap.push(5);
  513.    /// heap.push(2);
  514.    /// assert_eq!(heap.peek(), Some(&5));
  515.    ///
  516.    /// ```
  517.    ///
  518.    /// # Time complexity
  519.    ///
  520.    /// Cost is O(1) in the worst case.
  521.  
  522.    pub fn peek(&self) -> Option<&T> {
  523.        self.data.get(0)
  524.    }
  525.  
  526.    /// Returns the number of elements the binary heap can hold without reallocating.
  527.    ///
  528.    /// # Examples
  529.    ///
  530.    /// Basic usage:
  531.    ///
  532.    /// ```
  533.    /// use std::collections::BinaryHeap;
  534.    /// let mut heap = BinaryHeap::with_capacity(100);
  535.    /// assert!(heap.capacity() >= 100);
  536.    /// heap.push(4);
  537.    /// ```
  538.  
  539.    pub fn capacity(&self) -> usize {
  540.        self.data.capacity()
  541.    }
  542.  
  543.    /// Consumes the `BinaryHeap` and returns the underlying vector
  544.    /// in arbitrary order.
  545.    ///
  546.    /// # Examples
  547.    ///
  548.    /// Basic usage:
  549.    ///
  550.    /// ```
  551.    /// use std::collections::BinaryHeap;
  552.    /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5, 6, 7]);
  553.    /// let vec = heap.into_vec();
  554.    ///
  555.    /// // Will print in some order
  556.    /// for x in vec {
  557.    ///     println!("{}", x);
  558.    /// }
  559.    /// ```
  560.  
  561.    pub fn into_vec(self) -> StaticVec<T, K> {
  562.        self.into()
  563.    }
  564.  
  565.    /// Returns the length of the binary heap.
  566.    ///
  567.    /// # Examples
  568.    ///
  569.    /// Basic usage:
  570.    ///
  571.    /// ```
  572.    /// use std::collections::BinaryHeap;
  573.    /// let heap = BinaryHeap::from(vec![1, 3]);
  574.    ///
  575.    /// assert_eq!(heap.len(), 2);
  576.    /// ```
  577.  
  578.    pub fn len(&self) -> usize {
  579.        self.data.len()
  580.    }
  581.  
  582.    /// Checks if the binary heap is empty.
  583.    ///
  584.    /// # Examples
  585.    ///
  586.    /// Basic usage:
  587.    ///
  588.    /// ```
  589.    /// use std::collections::BinaryHeap;
  590.    /// let mut heap = BinaryHeap::new();
  591.    ///
  592.    /// assert!(heap.is_empty());
  593.    ///
  594.    /// heap.push(3);
  595.    /// heap.push(5);
  596.    /// heap.push(1);
  597.    ///
  598.    /// assert!(!heap.is_empty());
  599.    /// ```
  600.  
  601.    pub fn is_empty(&self) -> bool {
  602.        self.len() == 0
  603.    }
  604.  
  605.    /// Clears the binary heap, returning an iterator over the removed elements.
  606.    ///
  607.    /// The elements are removed in arbitrary order.
  608.    ///
  609.    /// # Examples
  610.    ///
  611.    /// Basic usage:
  612.    ///
  613.    /// ```
  614.    /// use std::collections::BinaryHeap;
  615.    /// let mut heap = BinaryHeap::from(vec![1, 3]);
  616.    ///
  617.    /// assert!(!heap.is_empty());
  618.    ///
  619.    /// for x in heap.drain() {
  620.    ///     println!("{}", x);
  621.    /// }
  622.    ///
  623.    /// assert!(heap.is_empty());
  624.    /// ```
  625.  
  626.    #[inline]
  627.    pub fn drain(&mut self) -> Drain<'_, T, K> {
  628.         Drain {
  629.             iter: self.data.drain_iter(..),
  630.         }
  631.     }
  632.  
  633.     /// Drops all items from the binary heap.
  634.     ///
  635.     /// # Examples
  636.     ///
  637.     /// Basic usage:
  638.     ///
  639.     /// ```
  640.     /// use std::collections::BinaryHeap;
  641.     /// let mut heap = BinaryHeap::from(vec![1, 3]);
  642.     ///
  643.     /// assert!(!heap.is_empty());
  644.     ///
  645.     /// heap.clear();
  646.     ///
  647.     /// assert!(heap.is_empty());
  648.     /// ```
  649.  
  650.     pub fn clear(&mut self) {
  651.         self.drain();
  652.     }
  653. }
  654.  
  655. /// Hole represents a hole in a slice i.e., an index without valid value
  656. /// (because it was moved from or duplicated).
  657. /// In drop, `Hole` will restore the slice by filling the hole
  658. /// position with the value that was originally removed.
  659. struct Hole<'a, T: 'a> {
  660.     data: &'a mut [T],
  661.    elt: ManuallyDrop<T>,
  662.    pos: usize,
  663. }
  664.  
  665. impl<'a, T> Hole<'a, T> {
  666.    /// Create a new `Hole` at index `pos`.
  667.    ///
  668.    /// Unsafe because pos must be within the data slice.
  669.    #[inline]
  670.    unsafe fn new(data: &'a mut [T], pos: usize) -> Self {
  671.         debug_assert!(pos < data.len());
  672.         // SAFE: pos should be inside the slice
  673.         let elt = ptr::read(data.get_unchecked(pos));
  674.         Hole {
  675.             data,
  676.             elt: ManuallyDrop::new(elt),
  677.             pos,
  678.         }
  679.     }
  680.  
  681.     #[inline]
  682.     fn pos(&self) -> usize {
  683.         self.pos
  684.     }
  685.  
  686.     /// Returns a reference to the element removed.
  687.     #[inline]
  688.     fn element(&self) -> &T {
  689.         &self.elt
  690.     }
  691.  
  692.     /// Returns a reference to the element at `index`.
  693.     ///
  694.     /// Unsafe because index must be within the data slice and not equal to pos.
  695.     #[inline]
  696.     unsafe fn get(&self, index: usize) -> &T {
  697.         debug_assert!(index != self.pos);
  698.         debug_assert!(index < self.data.len());
  699.         self.data.get_unchecked(index)
  700.     }
  701.  
  702.     /// Move hole to new location
  703.     ///
  704.     /// Unsafe because index must be within the data slice and not equal to pos.
  705.     #[inline]
  706.     unsafe fn move_to(&mut self, index: usize) {
  707.         debug_assert!(index != self.pos);
  708.         debug_assert!(index < self.data.len());
  709.         let index_ptr: *const _ = self.data.get_unchecked(index);
  710.         let hole_ptr = self.data.get_unchecked_mut(self.pos);
  711.         ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
  712.         self.pos = index;
  713.     }
  714. }
  715.  
  716. impl<T> Drop for Hole<'_, T> {
  717.    #[inline]
  718.    fn drop(&mut self) {
  719.        // fill the hole again
  720.        unsafe {
  721.            let pos = self.pos;
  722.            ptr::copy_nonoverlapping(&*self.elt, self.data.get_unchecked_mut(pos), 1);
  723.        }
  724.    }
  725. }
  726.  
  727. /// An iterator over the elements of a `BinaryHeap`.
  728. ///
  729. /// This `struct` is created by the [`iter`] method on [`BinaryHeap`]. See its
  730. /// documentation for more.
  731. ///
  732. /// [`iter`]: struct.BinaryHeap.html#method.iter
  733. /// [`BinaryHeap`]: struct.BinaryHeap.html
  734.  
  735. pub struct Iter<'a, T: 'a, const K: usize> {
  736.    iter: staticvec::StaticVecIterConst<'a, T, K>,
  737. }
  738.  
  739. impl<T: fmt::Debug, const K: usize> fmt::Debug for Iter<'_, T, K> {
  740.    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  741.         f.debug_tuple("Iter").field(&self.iter.as_slice()).finish()
  742.     }
  743. }
  744.  
  745. // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
  746.  
  747. impl<T, const K: usize> Clone for Iter<'_, T, K> {
  748.    fn clone(&self) -> Self {
  749.        Iter {
  750.            iter: self.iter.clone(),
  751.        }
  752.    }
  753. }
  754.  
  755. impl<'a, T, const K: usize> Iterator for Iter<'a, T, K> {
  756.    type Item = &'a T;
  757.  
  758.     #[inline]
  759.     fn next(&mut self) -> Option<&'a T> {
  760.        self.iter.next()
  761.    }
  762.  
  763.    #[inline]
  764.    fn size_hint(&self) -> (usize, Option<usize>) {
  765.        self.iter.size_hint()
  766.    }
  767.  
  768.    #[inline]
  769.    fn last(self) -> Option<&'a T> {
  770.         self.iter.last()
  771.     }
  772. }
  773.  
  774. impl<'a, T, const K: usize> DoubleEndedIterator for Iter<'a, T, K> {
  775.     #[inline]
  776.     fn next_back(&mut self) -> Option<&'a T> {
  777.        self.iter.next_back()
  778.    }
  779. }
  780.  
  781. impl<T, const K: usize> ExactSizeIterator for Iter<'_, T, K> {
  782.     fn is_empty(&self) -> bool {
  783.         self.iter.is_empty()
  784.     }
  785. }
  786.  
  787. impl<T, const K: usize> FusedIterator for Iter<'_, T, K> {}
  788.  
  789. /// An owning iterator over the elements of a `BinaryHeap`.
  790. ///
  791. /// This `struct` is created by the [`into_iter`] method on [`BinaryHeap`]
  792. /// (provided by the `IntoIterator` trait). See its documentation for more.
  793. ///
  794. /// [`into_iter`]: struct.BinaryHeap.html#method.into_iter
  795. /// [`BinaryHeap`]: struct.BinaryHeap.html
  796.  
  797. //FIXME: ???
  798. //#[derive(Clone)]
  799. pub struct IntoIter<T, const K: usize> {
  800.    iter: staticvec::StaticVecIntoIter<T, K>,
  801. }
  802.  
  803. impl<T: fmt::Debug, const K: usize> fmt::Debug for IntoIter<T, K> {
  804.    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  805.         f.debug_tuple("IntoIter")
  806.             .field(&self.iter.as_slice())
  807.             .finish()
  808.     }
  809. }
  810.  
  811. impl<T, const K: usize> Iterator for IntoIter<T, K> {
  812.     type Item = T;
  813.  
  814.     #[inline]
  815.     fn next(&mut self) -> Option<T> {
  816.         self.iter.next()
  817.     }
  818.  
  819.     #[inline]
  820.     fn size_hint(&self) -> (usize, Option<usize>) {
  821.         self.iter.size_hint()
  822.     }
  823. }
  824.  
  825. impl<T, const K: usize> DoubleEndedIterator for IntoIter<T, K> {
  826.     #[inline]
  827.     fn next_back(&mut self) -> Option<T> {
  828.         self.iter.next_back()
  829.     }
  830. }
  831.  
  832. impl<T, const K: usize> ExactSizeIterator for IntoIter<T, K> {
  833.     fn is_empty(&self) -> bool {
  834.         self.iter.is_empty()
  835.     }
  836. }
  837.  
  838. impl<T, const K: usize> FusedIterator for IntoIter<T, K> {}
  839.  
  840. #[derive(Clone, Debug)]
  841. pub struct IntoIterSorted<T, const K: usize> {
  842.     inner: BinaryHeap<T, K>,
  843. }
  844.  
  845. impl<T: Ord, const K: usize> Iterator for IntoIterSorted<T, K> {
  846.     type Item = T;
  847.  
  848.     #[inline]
  849.     fn next(&mut self) -> Option<T> {
  850.         self.inner.pop()
  851.     }
  852.  
  853.     #[inline]
  854.     fn size_hint(&self) -> (usize, Option<usize>) {
  855.         let exact = self.inner.len();
  856.         (exact, Some(exact))
  857.     }
  858. }
  859.  
  860. impl<T: Ord, const K: usize> ExactSizeIterator for IntoIterSorted<T, K> {}
  861.  
  862. impl<T: Ord, const K: usize> FusedIterator for IntoIterSorted<T, K> {}
  863.  
  864. unsafe impl<T: Ord, const K: usize> TrustedLen for IntoIterSorted<T, K> {}
  865.  
  866. /// A draining iterator over the elements of a `BinaryHeap`.
  867. ///
  868. /// This `struct` is created by the [`drain`] method on [`BinaryHeap`]. See its
  869. /// documentation for more.
  870. ///
  871. /// [`drain`]: struct.BinaryHeap.html#method.drain
  872. /// [`BinaryHeap`]: struct.BinaryHeap.html
  873.  
  874. #[derive(Debug)]
  875. pub struct Drain<'a, T: 'a, const K: usize> {
  876.     iter: staticvec::StaticVecDrain<'a, T, K>,
  877. }
  878.  
  879. impl<T, const K: usize> Iterator for Drain<'_, T, K> {
  880.     type Item = T;
  881.  
  882.     #[inline]
  883.     fn next(&mut self) -> Option<T> {
  884.         self.iter.next()
  885.     }
  886.  
  887.     #[inline]
  888.     fn size_hint(&self) -> (usize, Option<usize>) {
  889.         self.iter.size_hint()
  890.     }
  891. }
  892.  
  893. impl<T, const K: usize> DoubleEndedIterator for Drain<'_, T, K> {
  894.    #[inline]
  895.    fn next_back(&mut self) -> Option<T> {
  896.        self.iter.next_back()
  897.    }
  898. }
  899.  
  900. impl<T, const K: usize> ExactSizeIterator for Drain<'_, T, K> {
  901.     fn is_empty(&self) -> bool {
  902.         self.iter.is_empty()
  903.     }
  904. }
  905.  
  906. impl<T, const K: usize> FusedIterator for Drain<'_, T, K> {}
  907.  
  908. /// A draining iterator over the elements of a `BinaryHeap`.
  909. ///
  910. /// This `struct` is created by the [`drain_sorted`] method on [`BinaryHeap`]. See its
  911. /// documentation for more.
  912. ///
  913. /// [`drain_sorted`]: struct.BinaryHeap.html#method.drain_sorted
  914. /// [`BinaryHeap`]: struct.BinaryHeap.html
  915.  
  916. #[derive(Debug)]
  917. pub struct DrainSorted<'a, T: Ord, const K: usize> {
  918.     inner: &'a mut BinaryHeap<T, K>,
  919. }
  920.  
  921. impl<'a, T: Ord, const K: usize> Drop for DrainSorted<'a, T, K> {
  922.    /// Removes heap elements in heap order.
  923.    fn drop(&mut self) {
  924.        while let Some(_) = self.inner.pop() {}
  925.    }
  926. }
  927.  
  928. impl<T: Ord, const K: usize> Iterator for DrainSorted<'_, T, K> {
  929.     type Item = T;
  930.  
  931.     #[inline]
  932.     fn next(&mut self) -> Option<T> {
  933.         self.inner.pop()
  934.     }
  935.  
  936.     #[inline]
  937.     fn size_hint(&self) -> (usize, Option<usize>) {
  938.         let exact = self.inner.len();
  939.         (exact, Some(exact))
  940.     }
  941. }
  942.  
  943. impl<T: Ord, const K: usize> ExactSizeIterator for DrainSorted<'_, T, K> {}
  944.  
  945. impl<T: Ord, const K: usize> FusedIterator for DrainSorted<'_, T, K> {}
  946.  
  947. unsafe impl<T: Ord, const K: usize> TrustedLen for DrainSorted<'_, T, K> {}
  948.  
  949. impl<T: Ord, const K: usize> From<StaticVec<T, K>> for BinaryHeap<T, K> {
  950.    /// Converts a `Vec<T>` into a `BinaryHeap<T>`.
  951.    ///
  952.    /// This conversion happens in-place, and has `O(n)` time complexity.
  953.    fn from(vec: StaticVec<T, K>) -> BinaryHeap<T, K> {
  954.        let mut heap = BinaryHeap { data: vec };
  955.        heap.rebuild();
  956.        heap
  957.    }
  958. }
  959.  
  960. impl<T, const K: usize> From<BinaryHeap<T, K>> for StaticVec<T, K> {
  961.    fn from(heap: BinaryHeap<T, K>) -> StaticVec<T, K> {
  962.        heap.data
  963.    }
  964. }
  965.  
  966. impl<T: Ord, const K: usize> FromIterator<T> for BinaryHeap<T, K> {
  967.    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BinaryHeap<T, K> {
  968.        BinaryHeap::from(iter.into_iter().collect::<StaticVec<_, K>>())
  969.    }
  970. }
  971.  
  972. impl<T, const K: usize> IntoIterator for BinaryHeap<T, K> {
  973.    type Item = T;
  974.    type IntoIter = IntoIter<T, K>;
  975.  
  976.    /// Creates a consuming iterator, that is, one that moves each value out of
  977.    /// the binary heap in arbitrary order. The binary heap cannot be used
  978.    /// after calling this.
  979.    ///
  980.    /// # Examples
  981.    ///
  982.    /// Basic usage:
  983.    ///
  984.    /// ```
  985.    /// use std::collections::BinaryHeap;
  986.    /// let heap = BinaryHeap::from(vec![1, 2, 3, 4]);
  987.    ///
  988.    /// // Print 1, 2, 3, 4 in arbitrary order
  989.    /// for x in heap.into_iter() {
  990.    ///     // x has type i32, not &i32
  991.    ///     println!("{}", x);
  992.    /// }
  993.    /// ```
  994.    fn into_iter(self) -> IntoIter<T, K> {
  995.        IntoIter {
  996.            iter: self.data.into_iter(),
  997.        }
  998.    }
  999. }
  1000.  
  1001. impl<'a, T, const K: usize> IntoIterator for &'a BinaryHeap<T, K> {
  1002.    type Item = &'a T;
  1003.     type IntoIter = Iter<'a, T, K>;
  1004.  
  1005.    fn into_iter(self) -> Iter<'a, T, K> {
  1006.         Iter { iter: self.iter() }
  1007.     }
  1008. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top