From 02477f6f99c22509825a85bd090e42f935b33983 Mon Sep 17 00:00:00 2001 From: Kevin Leimkuhler Date: Thu, 11 Oct 2018 15:59:54 -0700 Subject: Add is_sorted impl for [T] --- src/libcore/slice/mod.rs | 79 +++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 78 insertions(+), 1 deletion(-) (limited to 'src/libcore/slice') diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs index 7fdc2acb8cc..d4cac3e4f4b 100644 --- a/src/libcore/slice/mod.rs +++ b/src/libcore/slice/mod.rs @@ -1783,7 +1783,7 @@ impl [T] { /// 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,83 @@ impl [T] { 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()); + /// ``` + #[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. + #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")] + pub fn is_sorted_by(&self, mut compare: F) -> bool + where + F: FnMut(&T, &T) -> Option + { + let mut last = match self.first() { + Some(e) => e, + None => return true, + }; + + for curr in &self[1..] { + if compare(&last, &curr).map(|o| o == Ordering::Greater).unwrap_or(true) { + return false; + } + last = &curr; + } + + true + } + + /// 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. + /// + /// # 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())); + /// ``` + #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")] + pub fn is_sorted_by_key(&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"] -- cgit 1.4.1-3-g733a5 From ce47dde59f45d55fa27dce9a614d1a972f9d8a4f Mon Sep 17 00:00:00 2001 From: Kevin Leimkuhler Date: Fri, 12 Oct 2018 14:47:01 -0700 Subject: Add is_sorted unstable documentation --- .../src/library-features/is-sorted.md | 11 +++++++++++ src/libcore/iter/iterator.rs | 2 ++ src/libcore/slice/mod.rs | 2 ++ .../ui/feature-gates/feature-gate-is_sorted.rs | 7 +++++++ .../ui/feature-gates/feature-gate-is_sorted.stderr | 22 +++++++++++++++++++--- 5 files changed, 41 insertions(+), 3 deletions(-) create mode 100644 src/doc/unstable-book/src/library-features/is-sorted.md (limited to 'src/libcore/slice') 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 00000000000..e3b7dc3b28e --- /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 879cc8357cd..67591381fdc 100644 --- a/src/libcore/iter/iterator.rs +++ b/src/libcore/iter/iterator.rs @@ -2626,6 +2626,7 @@ pub trait Iterator { /// assert!(std::iter::empty::().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 @@ -2676,6 +2677,7 @@ pub trait Iterator { /// 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(self, mut f: F) -> bool where diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs index d4cac3e4f4b..ab160a6c0c4 100644 --- a/src/libcore/slice/mod.rs +++ b/src/libcore/slice/mod.rs @@ -2272,6 +2272,7 @@ impl [T] { /// 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 @@ -2319,6 +2320,7 @@ impl [T] { /// 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(&self, mut f: F) -> bool where diff --git a/src/test/ui/feature-gates/feature-gate-is_sorted.rs b/src/test/ui/feature-gates/feature-gate-is_sorted.rs index 82fee379a4f..f44e74838ed 100644 --- a/src/test/ui/feature-gates/feature-gate-is_sorted.rs +++ b/src/test/ui/feature-gates/feature-gate-is_sorted.rs @@ -9,8 +9,15 @@ // except according to those terms. fn main() { + // Assert `Iterator` methods are feature gated assert!([1, 2, 2, 9].iter().is_sorted()); //^ ERROR: use of unstable library feature 'is_sorted' assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs())); //^ ERROR: use of unstable library feature 'is_sorted' + + // Assert `[T]` methods are feature gated + assert!([1, 2, 2, 9].is_sorted()); + //^ ERROR: use of unstable library feature 'is_sorted' + assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs())); + //^ ERROR: use of unstable library feature 'is_sorted' } diff --git a/src/test/ui/feature-gates/feature-gate-is_sorted.stderr b/src/test/ui/feature-gates/feature-gate-is_sorted.stderr index e4c7891760c..873cee53370 100644 --- a/src/test/ui/feature-gates/feature-gate-is_sorted.stderr +++ b/src/test/ui/feature-gates/feature-gate-is_sorted.stderr @@ -1,5 +1,5 @@ error[E0658]: use of unstable library feature 'is_sorted': new API (see issue #53485) - --> $DIR/feature-gate-is_sorted.rs:12:33 + --> $DIR/feature-gate-is_sorted.rs:13:33 | LL | assert!([1, 2, 2, 9].iter().is_sorted()); | ^^^^^^^^^ @@ -7,13 +7,29 @@ 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:14:39 + --> $DIR/feature-gate-is_sorted.rs:15: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: aborting due to 2 previous errors +error[E0658]: use of unstable library feature 'is_sorted': new API (see issue #53485) + --> $DIR/feature-gate-is_sorted.rs:19: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:21: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`. -- cgit 1.4.1-3-g733a5 From ccc027eff7604bf75f1ad490f415a338e44c1038 Mon Sep 17 00:00:00 2001 From: Kevin Leimkuhler Date: Sat, 13 Oct 2018 17:26:57 -0700 Subject: Improve documentation and slice impl --- src/libcore/iter/iterator.rs | 8 ++++++-- src/libcore/slice/mod.rs | 21 ++++++++++++--------- 2 files changed, 18 insertions(+), 11 deletions(-) (limited to 'src/libcore/slice') diff --git a/src/libcore/iter/iterator.rs b/src/libcore/iter/iterator.rs index 67591381fdc..4035ad6b77c 100644 --- a/src/libcore/iter/iterator.rs +++ b/src/libcore/iter/iterator.rs @@ -2640,7 +2640,9 @@ pub trait Iterator { /// /// 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`]; 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(mut self, mut compare: F) -> bool where @@ -2666,9 +2668,11 @@ pub trait Iterator { /// 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 + /// 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 /// /// ``` diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs index ab160a6c0c4..9c82aca9ab2 100644 --- a/src/libcore/slice/mod.rs +++ b/src/libcore/slice/mod.rs @@ -2285,22 +2285,23 @@ impl [T] { /// /// 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`]; 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(&self, mut compare: F) -> bool where F: FnMut(&T, &T) -> Option { - let mut last = match self.first() { - Some(e) => e, - None => return true, - }; + let len = self.len(); + if len <= 1 { + return true; + } - for curr in &self[1..] { - if compare(&last, &curr).map(|o| o == Ordering::Greater).unwrap_or(true) { + for i in 1..len { + if compare(&self[i - 1], &self[i]).map(|o| o == Ordering::Greater).unwrap_or(true) { return false; } - last = &curr; } true @@ -2309,9 +2310,11 @@ impl [T] { /// 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 + /// 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 /// /// ``` -- cgit 1.4.1-3-g733a5 From 67729b4040a17508640af17c21876650b34ff6de Mon Sep 17 00:00:00 2001 From: Kevin Leimkuhler Date: Sun, 14 Oct 2018 20:45:28 -0700 Subject: Compare pairs with `slice::windows` --- src/libcore/iter/iterator.rs | 5 ++++- src/libcore/slice/mod.rs | 12 +++++------- 2 files changed, 9 insertions(+), 8 deletions(-) (limited to 'src/libcore/slice') diff --git a/src/libcore/iter/iterator.rs b/src/libcore/iter/iterator.rs index 4035ad6b77c..ac21586c0b8 100644 --- a/src/libcore/iter/iterator.rs +++ b/src/libcore/iter/iterator.rs @@ -2655,7 +2655,10 @@ pub trait Iterator { }; while let Some(curr) = self.next() { - if compare(&last, &curr).map(|o| o == Ordering::Greater).unwrap_or(true) { + if compare(&last, &curr) + .map(|o| o == Ordering::Greater) + .unwrap_or(true) + { return false; } last = curr; diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs index 9c82aca9ab2..11ce8115d30 100644 --- a/src/libcore/slice/mod.rs +++ b/src/libcore/slice/mod.rs @@ -2293,13 +2293,11 @@ impl [T] { where F: FnMut(&T, &T) -> Option { - let len = self.len(); - if len <= 1 { - return true; - } - - for i in 1..len { - if compare(&self[i - 1], &self[i]).map(|o| o == Ordering::Greater).unwrap_or(true) { + for pair in self.windows(2) { + if compare(&pair[0], &pair[1]) + .map(|o| o == Ordering::Greater) + .unwrap_or(true) + { return false; } } -- cgit 1.4.1-3-g733a5 From 54f11240b701f7d4031c3d1545232ebad4436c15 Mon Sep 17 00:00:00 2001 From: Lukas Kalbertodt Date: Mon, 17 Dec 2018 15:54:19 +0100 Subject: Override `Iterator::is_sorted_by` in `slice::Iter` impl Additionally, the root implementation was changed a bit: it now uses `all` instead of coding that logic manually. To avoid duplicate code, the inherent `[T]::is_sorted_by` method now calls `self.iter().is_sorted_by(...)`. This should always be inlined and not result in overhead. --- src/libcore/slice/mod.rs | 35 ++++++++++++++-------- .../ui/feature-gates/feature-gate-is_sorted.rs | 10 ------- .../ui/feature-gates/feature-gate-is_sorted.stderr | 8 ++--- 3 files changed, 26 insertions(+), 27 deletions(-) (limited to 'src/libcore/slice') diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs index 11ce8115d30..df4d97ee6a4 100644 --- a/src/libcore/slice/mod.rs +++ b/src/libcore/slice/mod.rs @@ -2293,16 +2293,7 @@ impl [T] { where F: FnMut(&T, &T) -> Option { - for pair in self.windows(2) { - if compare(&pair[0], &pair[1]) - .map(|o| o == Ordering::Greater) - .unwrap_or(true) - { - return false; - } - } - - true + 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. @@ -2853,7 +2844,13 @@ macro_rules! len { // 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)] @@ -3030,6 +3027,8 @@ macro_rules! iterator { i }) } + + $($extra)* } #[stable(feature = "rust1", since = "1.0.0")] @@ -3167,7 +3166,17 @@ impl<'a, T> Iter<'a, T> { } } -iterator!{struct Iter -> *const T, &'a T, const, /* no mut */} +iterator!{struct Iter -> *const T, &'a T, const, {/* no mut */}, { + fn is_sorted_by(self, mut compare: F) -> bool + where + Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Option, + { + 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 Clone for Iter<'_, T> { @@ -3268,7 +3277,7 @@ impl<'a, T> IterMut<'a, T> { } } -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/test/ui/feature-gates/feature-gate-is_sorted.rs b/src/test/ui/feature-gates/feature-gate-is_sorted.rs index f44e74838ed..432ead65b17 100644 --- a/src/test/ui/feature-gates/feature-gate-is_sorted.rs +++ b/src/test/ui/feature-gates/feature-gate-is_sorted.rs @@ -1,13 +1,3 @@ -// Copyright 2018 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - fn main() { // Assert `Iterator` methods are feature gated assert!([1, 2, 2, 9].iter().is_sorted()); diff --git a/src/test/ui/feature-gates/feature-gate-is_sorted.stderr b/src/test/ui/feature-gates/feature-gate-is_sorted.stderr index 873cee53370..8230c1e3a38 100644 --- a/src/test/ui/feature-gates/feature-gate-is_sorted.stderr +++ b/src/test/ui/feature-gates/feature-gate-is_sorted.stderr @@ -1,5 +1,5 @@ error[E0658]: use of unstable library feature 'is_sorted': new API (see issue #53485) - --> $DIR/feature-gate-is_sorted.rs:13:33 + --> $DIR/feature-gate-is_sorted.rs:3:33 | LL | assert!([1, 2, 2, 9].iter().is_sorted()); | ^^^^^^^^^ @@ -7,7 +7,7 @@ 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:15:39 + --> $DIR/feature-gate-is_sorted.rs:5:39 | LL | assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs())); | ^^^^^^^^^^^^^^^^ @@ -15,7 +15,7 @@ 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:19:26 + --> $DIR/feature-gate-is_sorted.rs:9:26 | LL | assert!([1, 2, 2, 9].is_sorted()); | ^^^^^^^^^ @@ -23,7 +23,7 @@ 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:21:32 + --> $DIR/feature-gate-is_sorted.rs:11:32 | LL | assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs())); | ^^^^^^^^^^^^^^^^ -- cgit 1.4.1-3-g733a5