Auto merge of #55045 - kleimkuhler:add-std-is_sorted, r=KodrAus
Add `is_sorted` to `Iterator` and `[T]`
This is an initial implementation for the first step of [RFC 2351](https://github.com/rust-lang/rfcs/blob/master/text/2351-is-sorted.md)
Tracking issue: https://github.com/rust-lang/rust/issues/53485
diff --git a/src/doc/unstable-book/src/library-features/is-sorted.md b/src/doc/unstable-book/src/library-features/is-sorted.md
new file mode 100644
index 0000000..e3b7dc3
--- /dev/null
+++ b/src/doc/unstable-book/src/library-features/is-sorted.md
@@ -0,0 +1,11 @@
+# `is_sorted`
+
+The tracking issue for this feature is: [#53485]
+
+[#53485]: https://github.com/rust-lang/rust/issues/53485
+
+------------------------
+
+Add the methods `is_sorted`, `is_sorted_by` and `is_sorted_by_key` to `[T]`;
+add the methods `is_sorted`, `is_sorted_by` and `is_sorted_by_key` to
+`Iterator`.
diff --git a/src/libcore/iter/iterator.rs b/src/libcore/iter/iterator.rs
index 0ad29af..ac21586 100644
--- a/src/libcore/iter/iterator.rs
+++ b/src/libcore/iter/iterator.rs
@@ -2605,6 +2605,95 @@
}
}
}
+
+ /// Checks if the elements of this iterator are sorted.
+ ///
+ /// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the
+ /// iterator yields exactly zero or one element, `true` is returned.
+ ///
+ /// Note that if `Self::Item` is only `PartialOrd`, but not `Ord`, the above definition
+ /// implies that this function returns `false` if any two consecutive items are not
+ /// comparable.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(is_sorted)]
+ ///
+ /// assert!([1, 2, 2, 9].iter().is_sorted());
+ /// assert!(![1, 3, 2, 4].iter().is_sorted());
+ /// assert!([0].iter().is_sorted());
+ /// assert!(std::iter::empty::<i32>().is_sorted());
+ /// assert!(![0.0, 1.0, std::f32::NAN].iter().is_sorted());
+ /// ```
+ #[inline]
+ #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
+ fn is_sorted(self) -> bool
+ where
+ Self: Sized,
+ Self::Item: PartialOrd,
+ {
+ self.is_sorted_by(|a, b| a.partial_cmp(b))
+ }
+
+ /// Checks if the elements of this iterator are sorted using the given comparator function.
+ ///
+ /// Instead of using `PartialOrd::partial_cmp`, this function uses the given `compare`
+ /// function to determine the ordering of two elements. Apart from that, it's equivalent to
+ /// [`is_sorted`]; see its documentation for more information.
+ ///
+ /// [`is_sorted`]: trait.Iterator.html#method.is_sorted
+ #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
+ fn is_sorted_by<F>(mut self, mut compare: F) -> bool
+ where
+ Self: Sized,
+ F: FnMut(&Self::Item, &Self::Item) -> Option<Ordering>
+ {
+ let mut last = match self.next() {
+ Some(e) => e,
+ None => return true,
+ };
+
+ while let Some(curr) = self.next() {
+ if compare(&last, &curr)
+ .map(|o| o == Ordering::Greater)
+ .unwrap_or(true)
+ {
+ return false;
+ }
+ last = curr;
+ }
+
+ true
+ }
+
+ /// Checks if the elements of this iterator are sorted using the given key extraction
+ /// function.
+ ///
+ /// Instead of comparing the iterator's elements directly, this function compares the keys of
+ /// the elements, as determined by `f`. Apart from that, it's equivalent to [`is_sorted`]; see
+ /// its documentation for more information.
+ ///
+ /// [`is_sorted`]: trait.Iterator.html#method.is_sorted
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(is_sorted)]
+ ///
+ /// assert!(["c", "bb", "aaa"].iter().is_sorted_by_key(|s| s.len()));
+ /// assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs()));
+ /// ```
+ #[inline]
+ #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
+ fn is_sorted_by_key<F, K>(self, mut f: F) -> bool
+ where
+ Self: Sized,
+ F: FnMut(&Self::Item) -> K,
+ K: PartialOrd
+ {
+ self.is_sorted_by(|a, b| f(a).partial_cmp(&f(b)))
+ }
}
/// Select an element from an iterator based on the given "projection"
diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs
index 33c0da8..df32cfa 100644
--- a/src/libcore/lib.rs
+++ b/src/libcore/lib.rs
@@ -79,6 +79,7 @@
#![feature(extern_types)]
#![feature(fundamental)]
#![feature(intrinsics)]
+#![feature(is_sorted)]
#![feature(iter_once_with)]
#![feature(lang_items)]
#![feature(link_llvm_intrinsics)]
diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index 7fdc2ac..df4d97e 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -1783,7 +1783,7 @@
/// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
/// a[1..5].rotate_left(1);
/// assert_eq!(a, ['a', 'c', 'd', 'e', 'b', 'f']);
- /// ```
+ /// ```
#[stable(feature = "slice_rotate", since = "1.26.0")]
pub fn rotate_left(&mut self, mid: usize) {
assert!(mid <= self.len());
@@ -2250,6 +2250,77 @@
from_raw_parts_mut(mut_ptr.add(rest.len() - ts_len), ts_len))
}
}
+
+ /// Checks if the elements of this slice are sorted.
+ ///
+ /// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the
+ /// slice yields exactly zero or one element, `true` is returned.
+ ///
+ /// Note that if `Self::Item` is only `PartialOrd`, but not `Ord`, the above definition
+ /// implies that this function returns `false` if any two consecutive items are not
+ /// comparable.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(is_sorted)]
+ /// let empty: [i32; 0] = [];
+ ///
+ /// assert!([1, 2, 2, 9].is_sorted());
+ /// assert!(![1, 3, 2, 4].is_sorted());
+ /// assert!([0].is_sorted());
+ /// assert!(empty.is_sorted());
+ /// assert!(![0.0, 1.0, std::f32::NAN].is_sorted());
+ /// ```
+ #[inline]
+ #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
+ pub fn is_sorted(&self) -> bool
+ where
+ T: PartialOrd,
+ {
+ self.is_sorted_by(|a, b| a.partial_cmp(b))
+ }
+
+ /// Checks if the elements of this slice are sorted using the given comparator function.
+ ///
+ /// Instead of using `PartialOrd::partial_cmp`, this function uses the given `compare`
+ /// function to determine the ordering of two elements. Apart from that, it's equivalent to
+ /// [`is_sorted`]; see its documentation for more information.
+ ///
+ /// [`is_sorted`]: #method.is_sorted
+ #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
+ pub fn is_sorted_by<F>(&self, mut compare: F) -> bool
+ where
+ F: FnMut(&T, &T) -> Option<Ordering>
+ {
+ self.iter().is_sorted_by(|a, b| compare(*a, *b))
+ }
+
+ /// Checks if the elements of this slice are sorted using the given key extraction function.
+ ///
+ /// Instead of comparing the slice's elements directly, this function compares the keys of the
+ /// elements, as determined by `f`. Apart from that, it's equivalent to [`is_sorted`]; see its
+ /// documentation for more information.
+ ///
+ /// [`is_sorted`]: #method.is_sorted
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(is_sorted)]
+ ///
+ /// assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
+ /// assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
+ /// ```
+ #[inline]
+ #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
+ pub fn is_sorted_by_key<F, K>(&self, mut f: F) -> bool
+ where
+ F: FnMut(&T) -> K,
+ K: PartialOrd
+ {
+ self.is_sorted_by(|a, b| f(a).partial_cmp(&f(b)))
+ }
}
#[lang = "slice_u8"]
@@ -2773,7 +2844,13 @@
// The shared definition of the `Iter` and `IterMut` iterators
macro_rules! iterator {
- (struct $name:ident -> $ptr:ty, $elem:ty, $raw_mut:tt, $( $mut_:tt )*) => {
+ (
+ struct $name:ident -> $ptr:ty,
+ $elem:ty,
+ $raw_mut:tt,
+ {$( $mut_:tt )*},
+ {$($extra:tt)*}
+ ) => {
impl<'a, T> $name<'a, T> {
// Helper function for creating a slice from the iterator.
#[inline(always)]
@@ -2950,6 +3027,8 @@
i
})
}
+
+ $($extra)*
}
#[stable(feature = "rust1", since = "1.0.0")]
@@ -3087,7 +3166,17 @@
}
}
-iterator!{struct Iter -> *const T, &'a T, const, /* no mut */}
+iterator!{struct Iter -> *const T, &'a T, const, {/* no mut */}, {
+ fn is_sorted_by<F>(self, mut compare: F) -> bool
+ where
+ Self: Sized,
+ F: FnMut(&Self::Item, &Self::Item) -> Option<Ordering>,
+ {
+ self.as_slice().windows(2).all(|w| {
+ compare(&&w[0], &&w[1]).map(|o| o != Ordering::Greater).unwrap_or(false)
+ })
+ }
+}}
#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Clone for Iter<'_, T> {
@@ -3188,7 +3277,7 @@
}
}
-iterator!{struct IterMut -> *mut T, &'a mut T, mut, mut}
+iterator!{struct IterMut -> *mut T, &'a mut T, mut, {mut}, {}}
/// An internal abstraction over the splitting iterators, so that
/// splitn, splitn_mut etc can be implemented once.
diff --git a/src/libcore/tests/iter.rs b/src/libcore/tests/iter.rs
index 3944bc7..0fa9974 100644
--- a/src/libcore/tests/iter.rs
+++ b/src/libcore/tests/iter.rs
@@ -2235,3 +2235,16 @@
assert_eq!((0..10).flat_map(f).flat_map(g).sum::<usize>(),
(0..10).flat_map(|x| f(x).flat_map(g)).sum::<usize>());
}
+
+#[test]
+fn test_is_sorted() {
+ assert!([1, 2, 2, 9].iter().is_sorted());
+ assert!(![1, 3, 2].iter().is_sorted());
+ assert!([0].iter().is_sorted());
+ assert!(std::iter::empty::<i32>().is_sorted());
+ assert!(![0.0, 1.0, std::f32::NAN].iter().is_sorted());
+ assert!([-2, -1, 0, 3].iter().is_sorted());
+ assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs()));
+ assert!(!["c", "bb", "aaa"].iter().is_sorted());
+ assert!(["c", "bb", "aaa"].iter().is_sorted_by_key(|s| s.len()));
+}
diff --git a/src/libcore/tests/lib.rs b/src/libcore/tests/lib.rs
index a9b8dec..3e8549f 100644
--- a/src/libcore/tests/lib.rs
+++ b/src/libcore/tests/lib.rs
@@ -10,6 +10,7 @@
#![feature(flt2dec)]
#![feature(fmt_internals)]
#![feature(hashmap_internals)]
+#![feature(is_sorted)]
#![feature(iter_copied)]
#![feature(iter_nth_back)]
#![feature(iter_once_with)]
diff --git a/src/libcore/tests/slice.rs b/src/libcore/tests/slice.rs
index 2c96efb..e210e83 100644
--- a/src/libcore/tests/slice.rs
+++ b/src/libcore/tests/slice.rs
@@ -1317,3 +1317,18 @@
// 2 is greater than 1, so this range is invalid.
bytes.copy_within(2..1, 0);
}
+
+#[test]
+fn test_is_sorted() {
+ let empty: [i32; 0] = [];
+
+ assert!([1, 2, 2, 9].is_sorted());
+ assert!(![1, 3, 2].is_sorted());
+ assert!([0].is_sorted());
+ assert!(empty.is_sorted());
+ assert!(![0.0, 1.0, std::f32::NAN].is_sorted());
+ assert!([-2, -1, 0, 3].is_sorted());
+ assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
+ assert!(!["c", "bb", "aaa"].is_sorted());
+ assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
+}
diff --git a/src/test/ui/feature-gates/feature-gate-is_sorted.rs b/src/test/ui/feature-gates/feature-gate-is_sorted.rs
new file mode 100644
index 0000000..078ecc5
--- /dev/null
+++ b/src/test/ui/feature-gates/feature-gate-is_sorted.rs
@@ -0,0 +1,13 @@
+fn main() {
+ // Assert `Iterator` methods are feature gated
+ assert!([1, 2, 2, 9].iter().is_sorted());
+ //~^ ERROR: use of unstable library feature 'is_sorted': new API
+ assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs()));
+ //~^ ERROR: use of unstable library feature 'is_sorted': new API
+
+ // Assert `[T]` methods are feature gated
+ assert!([1, 2, 2, 9].is_sorted());
+ //~^ ERROR: use of unstable library feature 'is_sorted': new API
+ assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
+ //~^ ERROR: use of unstable library feature 'is_sorted': new API
+}
diff --git a/src/test/ui/feature-gates/feature-gate-is_sorted.stderr b/src/test/ui/feature-gates/feature-gate-is_sorted.stderr
new file mode 100644
index 0000000..8230c1e
--- /dev/null
+++ b/src/test/ui/feature-gates/feature-gate-is_sorted.stderr
@@ -0,0 +1,35 @@
+error[E0658]: use of unstable library feature 'is_sorted': new API (see issue #53485)
+ --> $DIR/feature-gate-is_sorted.rs:3:33
+ |
+LL | assert!([1, 2, 2, 9].iter().is_sorted());
+ | ^^^^^^^^^
+ |
+ = help: add #![feature(is_sorted)] to the crate attributes to enable
+
+error[E0658]: use of unstable library feature 'is_sorted': new API (see issue #53485)
+ --> $DIR/feature-gate-is_sorted.rs:5:39
+ |
+LL | assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs()));
+ | ^^^^^^^^^^^^^^^^
+ |
+ = help: add #![feature(is_sorted)] to the crate attributes to enable
+
+error[E0658]: use of unstable library feature 'is_sorted': new API (see issue #53485)
+ --> $DIR/feature-gate-is_sorted.rs:9:26
+ |
+LL | assert!([1, 2, 2, 9].is_sorted());
+ | ^^^^^^^^^
+ |
+ = help: add #![feature(is_sorted)] to the crate attributes to enable
+
+error[E0658]: use of unstable library feature 'is_sorted': new API (see issue #53485)
+ --> $DIR/feature-gate-is_sorted.rs:11:32
+ |
+LL | assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
+ | ^^^^^^^^^^^^^^^^
+ |
+ = help: add #![feature(is_sorted)] to the crate attributes to enable
+
+error: aborting due to 4 previous errors
+
+For more information about this error, try `rustc --explain E0658`.
