use core::ptr;
use core::fmt;
-use slice;
-use vec::{self, Vec};
+use crate::slice;
+use crate::vec::{self, Vec};
use super::SpecExtend;
}
#[stable(feature = "collection_debug", since = "1.17.0")]
-impl<'a, T: Ord + fmt::Debug> fmt::Debug for PeekMut<'a, T> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+impl<T: Ord + fmt::Debug> fmt::Debug for PeekMut<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("PeekMut")
.field(&self.heap.data[0])
.finish()
}
#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
-impl<'a, T: Ord> Drop for PeekMut<'a, T> {
+impl<T: Ord> Drop for PeekMut<'_, T> {
fn drop(&mut self) {
if self.sift {
self.heap.sift_down(0);
}
#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
-impl<'a, T: Ord> Deref for PeekMut<'a, T> {
+impl<T: Ord> Deref for PeekMut<'_, T> {
type Target = T;
fn deref(&self) -> &T {
- &self.heap.data[0]
+ debug_assert!(!self.heap.is_empty());
+ // SAFE: PeekMut is only instantiated for non-empty heaps
+ unsafe { self.heap.data.get_unchecked(0) }
}
}
#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
-impl<'a, T: Ord> DerefMut for PeekMut<'a, T> {
+impl<T: Ord> DerefMut for PeekMut<'_, T> {
fn deref_mut(&mut self) -> &mut T {
- &mut self.heap.data[0]
+ debug_assert!(!self.heap.is_empty());
+ // SAFE: PeekMut is only instantiated for non-empty heaps
+ unsafe { self.heap.data.get_unchecked_mut(0) }
}
}
}
#[stable(feature = "binaryheap_debug", since = "1.4.0")]
-impl<T: fmt::Debug + Ord> fmt::Debug for BinaryHeap<T> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+impl<T: fmt::Debug> fmt::Debug for BinaryHeap<T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
BinaryHeap { data: Vec::with_capacity(capacity) }
}
- /// Returns an iterator visiting all values in the underlying vector, in
- /// arbitrary order.
- ///
- /// # Examples
- ///
- /// Basic usage:
- ///
- /// ```
- /// use std::collections::BinaryHeap;
- /// let heap = BinaryHeap::from(vec![1, 2, 3, 4]);
- ///
- /// // Print 1, 2, 3, 4 in arbitrary order
- /// for x in heap.iter() {
- /// println!("{}", x);
- /// }
- /// ```
- #[stable(feature = "rust1", since = "1.0.0")]
- pub fn iter(&self) -> Iter<T> {
- Iter { iter: self.data.iter() }
- }
-
- /// Returns the greatest item in the binary heap, or `None` if it is empty.
- ///
- /// # Examples
- ///
- /// Basic usage:
- ///
- /// ```
- /// use std::collections::BinaryHeap;
- /// let mut heap = BinaryHeap::new();
- /// assert_eq!(heap.peek(), None);
- ///
- /// heap.push(1);
- /// heap.push(5);
- /// heap.push(2);
- /// assert_eq!(heap.peek(), Some(&5));
- ///
- /// ```
- #[stable(feature = "rust1", since = "1.0.0")]
- pub fn peek(&self) -> Option<&T> {
- self.data.get(0)
- }
-
/// Returns a mutable reference to the greatest item in the binary heap, or
/// `None` if it is empty.
///
/// assert_eq!(heap.peek(), Some(&2));
/// ```
#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
- pub fn peek_mut(&mut self) -> Option<PeekMut<T>> {
+ pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> {
if self.is_empty() {
None
} else {
}
}
- /// Returns the number of elements the binary heap can hold without reallocating.
- ///
- /// # Examples
- ///
- /// Basic usage:
- ///
- /// ```
- /// use std::collections::BinaryHeap;
- /// let mut heap = BinaryHeap::with_capacity(100);
- /// assert!(heap.capacity() >= 100);
- /// heap.push(4);
- /// ```
- #[stable(feature = "rust1", since = "1.0.0")]
- pub fn capacity(&self) -> usize {
- self.data.capacity()
- }
-
- /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
- /// given `BinaryHeap`. Does nothing if the capacity is already sufficient.
- ///
- /// Note that the allocator may give the collection more space than it requests. Therefore
- /// capacity can not be relied upon to be precisely minimal. Prefer [`reserve`] if future
- /// insertions are expected.
- ///
- /// # Panics
- ///
- /// Panics if the new capacity overflows `usize`.
- ///
- /// # Examples
- ///
- /// Basic usage:
- ///
- /// ```
- /// use std::collections::BinaryHeap;
- /// let mut heap = BinaryHeap::new();
- /// heap.reserve_exact(100);
- /// assert!(heap.capacity() >= 100);
- /// heap.push(4);
- /// ```
- ///
- /// [`reserve`]: #method.reserve
- #[stable(feature = "rust1", since = "1.0.0")]
- pub fn reserve_exact(&mut self, additional: usize) {
- self.data.reserve_exact(additional);
- }
-
- /// Reserves capacity for at least `additional` more elements to be inserted in the
- /// `BinaryHeap`. The collection may reserve more space to avoid frequent reallocations.
- ///
- /// # Panics
- ///
- /// Panics if the new capacity overflows `usize`.
- ///
- /// # Examples
- ///
- /// Basic usage:
- ///
- /// ```
- /// use std::collections::BinaryHeap;
- /// let mut heap = BinaryHeap::new();
- /// heap.reserve(100);
- /// assert!(heap.capacity() >= 100);
- /// heap.push(4);
- /// ```
- #[stable(feature = "rust1", since = "1.0.0")]
- pub fn reserve(&mut self, additional: usize) {
- self.data.reserve(additional);
- }
-
- /// Discards as much additional capacity as possible.
- ///
- /// # Examples
- ///
- /// Basic usage:
- ///
- /// ```
- /// use std::collections::BinaryHeap;
- /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
- ///
- /// assert!(heap.capacity() >= 100);
- /// heap.shrink_to_fit();
- /// assert!(heap.capacity() == 0);
- /// ```
- #[stable(feature = "rust1", since = "1.0.0")]
- pub fn shrink_to_fit(&mut self) {
- self.data.shrink_to_fit();
- }
-
- /// Discards capacity with a lower bound.
- ///
- /// The capacity will remain at least as large as both the length
- /// and the supplied value.
- ///
- /// Panics if the current capacity is smaller than the supplied
- /// minimum capacity.
- ///
- /// # Examples
- ///
- /// ```
- /// #![feature(shrink_to)]
- /// use std::collections::BinaryHeap;
- /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
- ///
- /// assert!(heap.capacity() >= 100);
- /// heap.shrink_to(10);
- /// assert!(heap.capacity() >= 10);
- /// ```
- #[inline]
- #[unstable(feature = "shrink_to", reason = "new API", issue="56431")]
- pub fn shrink_to(&mut self, min_capacity: usize) {
- self.data.shrink_to(min_capacity)
- }
-
/// Removes the greatest item from the binary heap and returns it, or `None` if it
/// is empty.
///
self.sift_up(0, old_len);
}
- /// Consumes the `BinaryHeap` and returns the underlying vector
- /// in arbitrary order.
- ///
- /// # Examples
- ///
- /// Basic usage:
- ///
- /// ```
- /// use std::collections::BinaryHeap;
- /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5, 6, 7]);
- /// let vec = heap.into_vec();
- ///
- /// // Will print in some order
- /// for x in vec {
- /// println!("{}", x);
- /// }
- /// ```
- #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
- pub fn into_vec(self) -> Vec<T> {
- self.into()
- }
-
/// Consumes the `BinaryHeap` and returns a vector in sorted
/// (ascending) order.
///
self.sift_up(start, pos);
}
+ fn rebuild(&mut self) {
+ let mut n = self.len() / 2;
+ while n > 0 {
+ n -= 1;
+ self.sift_down(n);
+ }
+ }
+
+ /// Moves all the elements of `other` into `self`, leaving `other` empty.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// use std::collections::BinaryHeap;
+ ///
+ /// let v = vec![-10, 1, 2, 3, 3];
+ /// let mut a = BinaryHeap::from(v);
+ ///
+ /// let v = vec![-20, 5, 43];
+ /// let mut b = BinaryHeap::from(v);
+ ///
+ /// a.append(&mut b);
+ ///
+ /// assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
+ /// assert!(b.is_empty());
+ /// ```
+ #[stable(feature = "binary_heap_append", since = "1.11.0")]
+ pub fn append(&mut self, other: &mut Self) {
+ if self.len() < other.len() {
+ swap(self, other);
+ }
+
+ if other.is_empty() {
+ return;
+ }
+
+ #[inline(always)]
+ fn log2_fast(x: usize) -> usize {
+ 8 * size_of::<usize>() - (x.leading_zeros() as usize) - 1
+ }
+
+ // `rebuild` takes O(len1 + len2) operations
+ // and about 2 * (len1 + len2) comparisons in the worst case
+ // while `extend` takes O(len2 * log_2(len1)) operations
+ // and about 1 * len2 * log_2(len1) comparisons in the worst case,
+ // assuming len1 >= len2.
+ #[inline]
+ fn better_to_rebuild(len1: usize, len2: usize) -> bool {
+ 2 * (len1 + len2) < len2 * log2_fast(len1)
+ }
+
+ if better_to_rebuild(self.len(), other.len()) {
+ self.data.append(&mut other.data);
+ self.rebuild();
+ } else {
+ self.extend(other.drain());
+ }
+ }
+}
+
+impl<T> BinaryHeap<T> {
+ /// Returns an iterator visiting all values in the underlying vector, in
+ /// arbitrary order.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// use std::collections::BinaryHeap;
+ /// let heap = BinaryHeap::from(vec![1, 2, 3, 4]);
+ ///
+ /// // Print 1, 2, 3, 4 in arbitrary order
+ /// for x in heap.iter() {
+ /// println!("{}", x);
+ /// }
+ /// ```
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn iter(&self) -> Iter<'_, T> {
+ Iter { iter: self.data.iter() }
+ }
+
+ /// Returns the greatest item in the binary heap, or `None` if it is empty.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// use std::collections::BinaryHeap;
+ /// let mut heap = BinaryHeap::new();
+ /// assert_eq!(heap.peek(), None);
+ ///
+ /// heap.push(1);
+ /// heap.push(5);
+ /// heap.push(2);
+ /// assert_eq!(heap.peek(), Some(&5));
+ ///
+ /// ```
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn peek(&self) -> Option<&T> {
+ self.data.get(0)
+ }
+
+ /// Returns the number of elements the binary heap can hold without reallocating.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// use std::collections::BinaryHeap;
+ /// let mut heap = BinaryHeap::with_capacity(100);
+ /// assert!(heap.capacity() >= 100);
+ /// heap.push(4);
+ /// ```
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn capacity(&self) -> usize {
+ self.data.capacity()
+ }
+
+ /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
+ /// given `BinaryHeap`. Does nothing if the capacity is already sufficient.
+ ///
+ /// Note that the allocator may give the collection more space than it requests. Therefore
+ /// capacity can not be relied upon to be precisely minimal. Prefer [`reserve`] if future
+ /// insertions are expected.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the new capacity overflows `usize`.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// use std::collections::BinaryHeap;
+ /// let mut heap = BinaryHeap::new();
+ /// heap.reserve_exact(100);
+ /// assert!(heap.capacity() >= 100);
+ /// heap.push(4);
+ /// ```
+ ///
+ /// [`reserve`]: #method.reserve
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn reserve_exact(&mut self, additional: usize) {
+ self.data.reserve_exact(additional);
+ }
+
+ /// Reserves capacity for at least `additional` more elements to be inserted in the
+ /// `BinaryHeap`. The collection may reserve more space to avoid frequent reallocations.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the new capacity overflows `usize`.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// use std::collections::BinaryHeap;
+ /// let mut heap = BinaryHeap::new();
+ /// heap.reserve(100);
+ /// assert!(heap.capacity() >= 100);
+ /// heap.push(4);
+ /// ```
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn reserve(&mut self, additional: usize) {
+ self.data.reserve(additional);
+ }
+
+ /// Discards as much additional capacity as possible.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// use std::collections::BinaryHeap;
+ /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
+ ///
+ /// assert!(heap.capacity() >= 100);
+ /// heap.shrink_to_fit();
+ /// assert!(heap.capacity() == 0);
+ /// ```
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn shrink_to_fit(&mut self) {
+ self.data.shrink_to_fit();
+ }
+
+ /// Discards capacity with a lower bound.
+ ///
+ /// The capacity will remain at least as large as both the length
+ /// and the supplied value.
+ ///
+ /// Panics if the current capacity is smaller than the supplied
+ /// minimum capacity.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(shrink_to)]
+ /// use std::collections::BinaryHeap;
+ /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
+ ///
+ /// assert!(heap.capacity() >= 100);
+ /// heap.shrink_to(10);
+ /// assert!(heap.capacity() >= 10);
+ /// ```
+ #[inline]
+ #[unstable(feature = "shrink_to", reason = "new API", issue="56431")]
+ pub fn shrink_to(&mut self, min_capacity: usize) {
+ self.data.shrink_to(min_capacity)
+ }
+
+ /// Consumes the `BinaryHeap` and returns the underlying vector
+ /// in arbitrary order.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// use std::collections::BinaryHeap;
+ /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5, 6, 7]);
+ /// let vec = heap.into_vec();
+ ///
+ /// // Will print in some order
+ /// for x in vec {
+ /// println!("{}", x);
+ /// }
+ /// ```
+ #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
+ pub fn into_vec(self) -> Vec<T> {
+ self.into()
+ }
+
/// Returns the length of the binary heap.
///
/// # Examples
/// ```
#[inline]
#[stable(feature = "drain", since = "1.6.0")]
- pub fn drain(&mut self) -> Drain<T> {
+ pub fn drain(&mut self) -> Drain<'_, T> {
Drain { iter: self.data.drain(..) }
}
pub fn clear(&mut self) {
self.drain();
}
-
- fn rebuild(&mut self) {
- let mut n = self.len() / 2;
- while n > 0 {
- n -= 1;
- self.sift_down(n);
- }
- }
-
- /// Moves all the elements of `other` into `self`, leaving `other` empty.
- ///
- /// # Examples
- ///
- /// Basic usage:
- ///
- /// ```
- /// use std::collections::BinaryHeap;
- ///
- /// let v = vec![-10, 1, 2, 3, 3];
- /// let mut a = BinaryHeap::from(v);
- ///
- /// let v = vec![-20, 5, 43];
- /// let mut b = BinaryHeap::from(v);
- ///
- /// a.append(&mut b);
- ///
- /// assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
- /// assert!(b.is_empty());
- /// ```
- #[stable(feature = "binary_heap_append", since = "1.11.0")]
- pub fn append(&mut self, other: &mut Self) {
- if self.len() < other.len() {
- swap(self, other);
- }
-
- if other.is_empty() {
- return;
- }
-
- #[inline(always)]
- fn log2_fast(x: usize) -> usize {
- 8 * size_of::<usize>() - (x.leading_zeros() as usize) - 1
- }
-
- // `rebuild` takes O(len1 + len2) operations
- // and about 2 * (len1 + len2) comparisons in the worst case
- // while `extend` takes O(len2 * log_2(len1)) operations
- // and about 1 * len2 * log_2(len1) comparisons in the worst case,
- // assuming len1 >= len2.
- #[inline]
- fn better_to_rebuild(len1: usize, len2: usize) -> bool {
- 2 * (len1 + len2) < len2 * log2_fast(len1)
- }
-
- if better_to_rebuild(self.len(), other.len()) {
- self.data.append(&mut other.data);
- self.rebuild();
- } else {
- self.extend(other.drain());
- }
- }
}
/// Hole represents a hole in a slice i.e., an index without valid value
}
impl<'a, T> Hole<'a, T> {
- /// Create a new Hole at index `pos`.
+ /// Create a new `Hole` at index `pos`.
///
/// Unsafe because pos must be within the data slice.
#[inline]
unsafe fn new(data: &'a mut [T], pos: usize) -> Self {
debug_assert!(pos < data.len());
- let elt = ptr::read(&data[pos]);
+ // SAFE: pos should be inside the slice
+ let elt = ptr::read(data.get_unchecked(pos));
Hole {
data,
elt: ManuallyDrop::new(elt),
}
}
-impl<'a, T> Drop for Hole<'a, T> {
+impl<T> Drop for Hole<'_, T> {
#[inline]
fn drop(&mut self) {
// fill the hole again
}
#[stable(feature = "collection_debug", since = "1.17.0")]
-impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("Iter")
.field(&self.iter.as_slice())
.finish()
// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, T> Clone for Iter<'a, T> {
- fn clone(&self) -> Iter<'a, T> {
+impl<T> Clone for Iter<'_, T> {
+ fn clone(&self) -> Self {
Iter { iter: self.iter.clone() }
}
}
}
#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, T> ExactSizeIterator for Iter<'a, T> {
+impl<T> ExactSizeIterator for Iter<'_, T> {
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
#[stable(feature = "fused", since = "1.26.0")]
-impl<'a, T> FusedIterator for Iter<'a, T> {}
+impl<T> FusedIterator for Iter<'_, T> {}
/// An owning iterator over the elements of a `BinaryHeap`.
///
#[stable(feature = "collection_debug", since = "1.17.0")]
impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("IntoIter")
.field(&self.iter.as_slice())
.finish()
}
#[stable(feature = "drain", since = "1.6.0")]
-impl<'a, T: 'a> Iterator for Drain<'a, T> {
+impl<T> Iterator for Drain<'_, T> {
type Item = T;
#[inline]
}
#[stable(feature = "drain", since = "1.6.0")]
-impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> {
+impl<T> DoubleEndedIterator for Drain<'_, T> {
#[inline]
fn next_back(&mut self) -> Option<T> {
self.iter.next_back()
}
#[stable(feature = "drain", since = "1.6.0")]
-impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {
+impl<T> ExactSizeIterator for Drain<'_, T> {
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
#[stable(feature = "fused", since = "1.26.0")]
-impl<'a, T: 'a> FusedIterator for Drain<'a, T> {}
+impl<T> FusedIterator for Drain<'_, T> {}
#[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
impl<T: Ord> From<Vec<T>> for BinaryHeap<T> {
}
#[stable(feature = "rust1", since = "1.0.0")]
-impl<T: Ord> IntoIterator for BinaryHeap<T> {
+impl<T> IntoIterator for BinaryHeap<T> {
type Item = T;
type IntoIter = IntoIter<T>;
}
#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, T> IntoIterator for &'a BinaryHeap<T>
- where T: Ord
-{
+impl<'a, T> IntoIterator for &'a BinaryHeap<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
projects / rustc.git / blobdiff